COUNTING 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}\]

Home Page