Generating Function (g.f.) is one of the most important tools in combinatorics. Many problems which are difficult to do by combinatorial arguments and by cases are trivial when g.f. is applied. Below are some typical problems where g.f. are very useful.
1 Solving diophantine equations (d.e.)
- What are the number of solutions for the linear d.e.
\begin{align*}
\displaystyle x_1+x_2+x_3+x_4=35\\ 1\le x_1,x_2\le 20\\ 20\le x_3,x_4 \le 30
\end{align*}
Answer can be easily found by representing the variables as polynomials and multiplying them, i.e.
\begin{equation*}
\displaystyle [z^{35}](z+z^2+z^3+\cdots +z^{20})^2\, (z^{20}+z^{21}+z^{22}+\cdots +z^{30})^2 = 11
\end{equation*}
Hence, there are 11 solutions for the d.e under the constraints.
In Sage, this can be found by the taylor expansion:
|
taylor((x-x^21)/(1-x)*(x^20-x^31)/(1-x),x,0,35).coefficient(x,35)
|
We can even get a closed form if the problem is changed to
\begin{align*}
\displaystyle x_1+x_2+x_3+x_4=n\\ 0\le x_1,x_2, x_3,x_4
\end{align*}
The g.f. for this is written as
\begin{equation*}
\displaystyle (1+z+z^2+z^3+\cdots)^4=\dfrac{1}{(1-z)^4}
\end{equation*}
and the nth coeffiecient is
\begin{equation*}
\displaystyle [z^n]\dfrac{1}{(1-z)^4}=\dbinom{n+3}{3}
\end{equation*}
b) Number of ways to make changes for n units using coins of denominations 1,2 and 5 units.
The d.e. for this problem is written as
\begin{equation*}
\displaystyle x_1+2\, x_2+5\, x_3=n
\end{equation*}
and the g.f. is
\begin{equation*}
\displaystyle G(z)=\dfrac{1}{(1-z)(1-z^2)(1-z^5)}
\end{equation*}
The \(n^{th}\) coefficient gets the exact answer, but having a g.f. allows us to do more, like having an asymptotic form.
In this case, factor the denominator
\begin{equation*}
\displaystyle G(z)=\dfrac{1}{(1-z)^3}\cdot \dfrac{1}{(1+z)(1+z+z^2+z^3+z^4)}
\end{equation*}
The first part of the two fractions contributes the most to the coefficients, and an approximation can be written as
\begin{equation*}
\displaystyle [z^n]G(z)\sim [z^n]\dfrac{1}{(1-z)^3}\cdot \lim_{z\to 1}\dfrac{1}{(1+z)(1+z+z^2+z^3+z^4)} =\dfrac{\dbinom{n+2}{2}}{10}
\end{equation*}
Comparing the precise and approximate answers:
for \(n=1000\)
\(50401\) and \(50150.1\),
for \(n=2000\)
200801 and 200301.1,
respectively.
2 Partial and infinite sums
- Finding a closed form for
\begin{equation*}
\displaystyle \sum_{k=1}^n k
\end{equation*}
For problems like this, we can make use of the property of g.f:
\begin{align*}
\displaystyle G(z)=\sum_{i\ge 0} a_i\, x^i\\ \implies \dfrac{1}{1-z}G(z)=\sum_{i\ge 0}\left(\sum_{j=0}^i a_j \right)z^i
\end{align*}
G.f. for \(<0,1,2,3,\ldots>\) is given by
\begin{equation*}
\displaystyle G(z)=\dfrac{z}{(1-z)^2}
\end{equation*}
Hence, to find the sum, it's simply
\begin{align*}
\displaystyle \dfrac{1}{1-z}\, G(z)=\dfrac{z}{(1-z)^3}\\ \implies [z^n]\dfrac{1}{1-z}\, G(z)=\sum_{k=1}^n k = \dbinom{n+1}{2}
\end{align*}
We can then proceed to find more complicated sums like
\begin{equation*}
\displaystyle \sum_{k=1}^n k^2
\end{equation*}
which are usually done in high school by mathematical induction, but never shown how to derive in the first place.
To derive it from g.f., we must first find the g.f. for , which can be easily obtained by differentation. i.e.
\begin{equation*}
\displaystyle z\, \dfrac{d}{dz}\left(\frac{z}{(1-z)^2}\right)=\dfrac{z+z^2}{(1-z)^3}
\end{equation*}
and the sum of the squares is
\begin{equation*}
\displaystyle [z^n]\dfrac{z+z^2}{(1-z)^4}=\dbinom{n+2}{3}+\dbinom{n+1}{3}=\dfrac{1}{6} \, {\left(2 \, n + 1\right)} {\left(n + 1\right)} n
\end{equation*}
which can be verified by Sage
|
var('n');
show(factor(sum(x^2,x,0,n)))
|
- Summation of infinite series
For this purpose, the dummy variable in the g.f. is replaced by a constant to obtain the closed form. E.g.
i)
\begin{equation*}
\displaystyle \sum_{i\ge 0}\frac{1}{5^i}
\end{equation*}
We have the g.f. for \(< 1,1,1,\ldots >\)
\begin{align*}
\displaystyle G(z)=\dfrac{1}{1-z}\\ \implies G(1/5)=\dfrac{5}{4}
\end{align*}
- We can also solve seemingly complicated sums like
\begin{equation*}
\displaystyle \sum_{i\ge 0} \dfrac{i^2\, F_i}{12^i}
\end{equation*}
where \(F_i\) is the \(i^{th}\) fibonacci term.
The g.f. for \(F_i\) can be shown to be (derived from the linear recurrence relation)
\begin{equation*}
\displaystyle G(z)=\dfrac{z}{1-z-z^2}
\end{equation*}
Next, obtain the g.f. for \(i^2 F_i\)
\begin{equation*}
\displaystyle G_1(z)= z\, D\left(z\, D\left( \dfrac{z}{1-z-z^2} \right) \right) = \dfrac{z^5 - z^4 + 6\, z^3 + z^2 + z}{(1-z-z^2)^3}
\end{equation*}
where \(D\) is the differential operator \(d/dz\) and
\begin{equation*}
\displaystyle \sum_{i\ge 0} \dfrac{i^2\, F_i}{12^i} = G_1(1/12) = \dfrac{279804}{2248091} \approx 0.124462933217561
\end{equation*}
In Sage, it's written as
|
(x*diff(x*diff(x/(1-x-x^2),x),x)).subs(x=1/12)
|
3 As probability g.f. and obtain expected values
In probability g.f., the coefficients are the probability of occurance of the value. The p.g.f. for a die with 6 faces numbered 1 to 6 is given by
\begin{equation*}
\displaystyle P(x)=\dfrac{x+x^2+x^3+x^4+x^5+x^6}{6}
\end{equation*}
and the probability of the sums when two dice are thrown
\begin{equation*}
\displaystyle P_2(x)=P(x)^2=\frac{1}{36} \, x^{12} + \frac{1}{18} \, x^{11} + \frac{1}{12} \, x^{10} + \frac{1}{9} \, x^{9} + \frac{5}{36} \, x^{8} + \frac{1}{6} \, x^{7} + \frac{5}{36} \, x^{6} + \frac{1}{9} \, x^{5} + \frac{1}{12} \, x^{4} + \frac{1}{18} \, x^{3} + \frac{1}{36} \, x^{2}
\end{equation*}
and the expected value shown when the die is thrown:
\begin{equation*}
\displaystyle E_1=P'(1)=\dfrac{7}{2}
\end{equation*}
and when two dice are thrown:
\begin{equation*}
\displaystyle E_2=P_2'(1)=\dfrac{7\cdot 2}{2}
\end{equation*}
