NOTES ON STATISTICS, PROBABILITY and MATHEMATICS

Calculating with Generating Functions:

From this online post:

Find the number of ordered partitions of \(n\) into exactly \(r\) parts (\(r\) summands):

\(n = \color{brown}{6}\) can be partitioned into exactly \(r = 4\) ordered parts as follows:

\[(3,1,1,1), (1,3,1,1), (1,1,3,1), (1,1,1,3), (2,2,1,1), (2,1,2,1) (2,1,1,2), (1,2,2,1), (1,2,1,2), (1,1,2,2).\]

We require the number of solutions of the following Diophantine equation:

\[x_1 + x_2 + x_3 + x_4 = \color{brown}{6}\]

The generating function is

\[(x^1+x^2+x^3+x^4+\dots)^4\]

Why does it start at \(x=x^1\), instead of at \(1=x^0\), as explained here? Because each \(x^1 + x^2 + x^3 +x^4 + \dots\) is to be read as \((x^1)^1\) (i.e. \(1\) number \(1\)); \((x^2)^1\) (i.e. \(1\) number \(2\)); etc. There can’t be a \(1=x^0\) because it would leave an empty (\(0\) contributing exponent) to whatever combination of, for example,

\[(x^1 + x^{\color{red}{2}} + x^3 + x^4 + x^5 +\dots)(x^{\color{red}{1}} + x^2 + x^3+ x^4 + x^5 +\dots)(x^1 + x^2 + x^{\color{red}{3}} + x^4 + x^5+\dots)(x^1 + x^2 + x^3+ x^4 + x^{\color{red}{5}} +\dots)\]

which means \(\color{red}{2 + 1 + 3 + 5} = 11.\) This doesn’t add up to 6. It would rather be a way to getting to \(11\) with \(4\) parts. When multiplied, the different exponents are add to \(11\): \(x^{\color{red}{2}}x^{\color{red}{1}}x^{\color{red}{3}} x^{\color{red}{5}}=x^{\color{red}{11}}.\) Same for \(x^{\color{red}{4}}x^{\color{red}{5}}x^{\color{red}{1}} x^{\color{red}{1}}=x^{\color{red}{11}}\). Hence, when all the \(x^i\) in the \(4\) polynomial series are multiplied, it will be the coefficient \(\color{blue}{\bullet}x^{\color{red}{11}}\) that tells us that there are \(\color{blue}{\bullet}\) ways of getting \(4\)-part partitions of \(11\). Naturally, for \(\color{color}{brown}{6}\), we will have to unlock the coefficient for \(x^{\color{red}{6}}.\)

And how do we do that? This is nicely explained in this youtube video, and requires turning the generating function into a form that contains the geometric series. Since \(x\)’s are just placeholders, there is no issue with convergence (we can pretend that \(x<1\)), and apply the formula:

\[\color{purple}{x^4}[\color{green}{1+x+x^2+x^3+\dots}]^4\]

\[x^4\left[\color{green}{\frac{1}{1-x}}\right]^4=\frac{x^4}{(1-x)^4}\]

To find the coefficient of any generating function, we need to know that:

\[\begin{align}(1 + x + x^2 +\dots)^r&=\frac{1}{(1-x)^r}\\[2ex] &=1+\binom{1+r-1}{1}x+\binom{2+r-1}{2}x^2+\dots+\color{red}{\binom{c+r-1}{c}}x^c+\dots\tag{1} \end{align}\]

Since we have the \(\color{purple}{x^4}\) in front of the expansion of the geometric series, we will need to find, NOT the coefficient in front of \(x^{\color{brown}{6}}\), BUT RATHER the coefficient in front of \(x^c=x^{n-r}=x^{\color{brown}{6}-4}=x^2.\)

The coefficient will be for \(c=2\) and \(r=4\) (\(4\) parts) in Eq.1:

\[\binom{2+4-1}{2}=\binom{5}{2}=10\]

But since \(\binom{2+4-1}{2}=\binom{n-r+r-1}{n-r}\), the final formula for \(n\) (number or sum to be partitioned) and \(r\) (number of partitions or “parts”) will be:

\[\binom{n-1}{n-r}\]

Here is more on generating functions.


How many ways are there to get a sum of \(12\) tossing \(3\) fair \(6\)-sided die:

The generating function is:

\[(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)^3\]

Notice that there are no zeroes, and the function stops at \(x^6\)

We can get the coefficient through derivatives, or just feed it to Wolfram Alpha as such:

\[x^{18}+3 x^{17}+6 x^{16}+10 x^{15}+15 x^{14}+21 x^{13}+\color{red}{25} x^{\color{blue}{12}}+27 x^{11}+27 x^{10}+25 x^9+21 x^8+15 x^7+10 x^6+6 x^5+3 x^4+x^3\]

Raw computation:

dice = 3
faces = 6
sum = 12
sam = replicate(1e5, sample(1:faces, dice, rep = T))
s = sam[,colSums(sam)==sum]
ncol(unique(s, MARGIN = 2))
## [1] 25
PARTITIONS (are understood to be UNORDERED):

How many partitions are there for the number \(n?\)

How many \(1\)’s? \(x^0+x^1+x^2+\cdots=1+x^1+x^2+\cdots=\frac{1}{1-x}\)

How many \(2\)’s? \(1+x^2+x^4+\cdots=\frac{1}{1-x^2}\)

How many \(3\)’s? \(1+x^3+x^6+\cdots=\frac{1}{1-x^3}\)

Therefore the generating functions is:

\[\begin{align}(1+x^1+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots&=\left(\frac{1}{1-x}\right)\left(\frac{1}{1-x^2}\right)\left(\frac{1}{1-x^3}\right)\left(\frac{1}{1-x^n}\right)\cdots\\ &=\prod_{i\geq \large{1}} \frac{1}{1-x^i} \end{align}\]

And the coefficient \(n\) is represented as:

\[[x^n]\left(\prod_{i\geq \large{1}} \frac{1}{1-x^i}\right)\]

So the partitions of \(4\) are \((1,1,1,1),(1,1,2),(1,3),(2,2),(4):\)

\[[x^4]\prod_{i=1}^{4}\left(\frac{1}{1-x^i}\right)=5\]

“We wouldn’t expect you to find it. This is not an easy thing to compute. Don’t worry about the coefficient, because the computer can find it for you.”

(l= lapply(seq_len(4)-1, function(i) rep(c(1, integer(i)), length.out=6)))
## [[1]]
## [1] 1 1 1 1 1 1
## 
## [[2]]
## [1] 1 0 1 0 1 0
## 
## [[3]]
## [1] 1 0 0 1 0 0
## 
## [[4]]
## [1] 1 0 0 0 1 0
(v = round(Reduce(f = function(x, y) convolve(x, rev(y), type = "open"), x = l)))
##  [1] 1 1 2 3 5 6 6 8 8 8 6 6 5 3 2 1 1 0 0 0 0

This is consistent with the results in Wolfram Alpha:

Input:

\[\small (1+x+x^2+x^3+x^4+x^5) \times (1 + x^2 + x^4) \times (1 + x^3) \times (1 + x^4)\]

Output:

\[\small x^{16}+x^{15}+2 x^{14}+3 x^{13}+5 x^{12}+6 x^{11}+6 x^{10}+8 x^9+8 x^8+8 x^7+6 x^6+6 x^5+\color{blue}{5} x^4+3 x^3+2 x^2+x+1\]

compared to:

rev(v)
##  [1] 0 0 0 0 1 1 2 3 5 6 6 8 8 8 6 6 5 3 2 1 1

What is the generating functions for all the ways to make \(n\) cents, using pennies (\(1\) cent), nickels (\(5\) cents), and dimes (\(10\) cents)?

\[\begin{align}\,\,\left[x^n\right](1+x^1+x^2+x^3+\cdots)(1+x^5+x^{10}+\cdots)(1+x^{10}+x^{20}+\cdots)\\ =\frac{1}{1-x}\frac{1}{1-x^5}\frac{1}{1-x^{10}} \end{align}\]

Generating function for the Fibonacci series:

For the generating function we want the following:

\[F = \sum_{n=0}^\infty a_n\, x^n\]

but since the initial recurrence is

\[f_n = f_{n-1} + f_{n-2}\]

the power series resulting from multiplying by \(x^n\) will have to start summing at \(n = 2\) as in:

\[\sum_{n \geq 2}^\infty f_n\,x^n = \sum_{n \geq 2}^\infty f_{n - 1}\,x^n + \sum_{n \geq 2}^\infty f_{n - 2}\,x^n\tag 1\]

The term on the LHS is almost \(F\) except that it is missing the two initial values \(a_0 = 0\) and \(a_1 = 1\) in the Fibonacci sequence \(0,1.1,2,3,5,\dots\). Therefore,

\[\sum_{n \geq 2}^\infty f_n\,x^n = F -a_0\,x^0 - a_1\,x^1\]

Now, for the first term in the RHS the index of the coefficient does not match the exponent, and to make them match we have to extract an \(x\) out of the sum:

\[\sum_{n \geq 2}^\infty f_{n - 1}\,x^n= x \sum_{n \geq 2}^\infty f_{n - 1}\,x^{n-1}\] Further, the expression right above will be equivalent to \(x\,F\) except that it will start adding at \(2 - 1 = 1,\) which implies that it misses out on the \(a_0\) coefficient. Accounting for this:

\[\sum_{n \geq 2}^\infty f_{n - 1}\,x^n= x \left( F - a_0 \right)\]

As for the second term of the RHS of \((1)\):

\[\sum_{n \geq 2}^\infty f_{n - 2}\,x^n=x^2 \sum_{n \geq 2}^\infty f_{n - 2}\,x^{n-2}\]

but this starts at \(2 - 2 = 0,\) so there is no need to subtract any coefficients to state that:

\[\sum_{n \geq 2}^\infty f_{n - 2}\,x^n=x^2 \sum_{n \geq 2}^\infty f_{n - 2}\,x^{n-2}=x^2 \, F\]

Therefore \((1)\) is equal to

\[x\,F -a_0 - a_1\,x= x\, \left(F - a_0 \right) + x^2 \,F\]

since \(a_0 = 0\) and \(a_1 =1,\) the above expression turns into:

\[x\,F - x= x\, F + x^2 \,F\]

or

\[x = F(1 - x - x^2)\]

yielding the GF

\[F = \frac{x}{1-x-x^2}\]

Let’s take it for a spin on Wolfram Alpha:

SeriesCoefficient[x/(1-x-x^2),{x,0,15}]

yields the correct term \(610.\)

\[\begin{align}a_0=0, a_1=1, a_2=1, a_3=2, a_4=3,\\ a_5=5, a_6=8, a_7=13,\\ a_8=21, a_9=34, a_{10}=55, a_{11}=89, \\a_{12}=144, a_{13}=233, a_{14}=377, \color{red}{a_{15}=610}, \\ a_{16}=987, a_{17}=1597, a_{18}=2584,\dots \end{align}\]

Home Page

NOTE: These are tentative notes on different topics for personal use - expect mistakes and misunderstandings.