### 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 $$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