1.1 Introduction to Generating Functions
Consider a simple problem where we have to calculate the number of ways to choose 2 fruits from 5 distinct fruits. Let’s call them A,B,C,D,E. So we have 1 each of these 5 fruits and we need to choose 2 of them (ignoring the order). A simple way would be to calculate \(C(5,2)=\frac{5!}{2!\times 3!} =10\). Note the notation, henceforth we’d use \(C(n,r)\) to denote \(^nC_r\).
If we were to approach this through a new method of generating functions, we’d try to estimate the number of ways of achieving our goal, in this case choosing 2 fruits, through the coefficient of some polynomial terms.
Let’s analyse the choices that we have:
We can either choose 0 A or 1 A
We can either choose 0 B or 1 B
We can either choose 0 C or 1 C..etc
Each choice over here is independent of whether my goal has yet been achieved or not.
So, let’s try to mock our first choice by a polynomial. Let’s denote the choice to choose 0 A by a polynomial term – \(x^0\). Similarly, we denote our choice to choose 1 A by \(x^1\). Together, we denote the first choice by the polynomial \(x^0+x^1=(1+x)\).
Incidentally, we can denote each of the remaining choices by the same polynomial – \((1+x)\) following a very similar argument like what we discussed above.
If we combine all the possible options that we have, and we mimic the same through a polynomial, we get \((1+x)\times (1+x)\times…(1+x)=(1+x)^5\). We thus have all our possible choices of choosing any number of fruits mocked by this polynomial.
\(P(x)=(1+x)^5=1+5x+10x^2+10x^3+5x^4+x^5\)Here, the coefficient of the term \(x^2\) denotes the number of ways in which we can choose 2 fruits.
Let’s think of another version of the same example, and fankly this is where Generating Functions become so handy in combinatorial calculations.
Let’s suppose that we now have 2 A fruits – identical. Rest B,C,D,E are 1 piece each. In this case how many ways can we choose 2 fruits?
Following a very similar line of argument, our generating polynomial will now be \(\underbrace{(1+x+x^2)}_{\text{Number of ways of choosing A}}\times (1+x)^3\). The coefficient of \(x^2\) denotes the number of ways we can choose 2 fruits. Can you try solving this without generating functions?
Ex -1
In how many ways can 3 persons, each throwing a dice make a sum of 15?
Solution:
We need to find the coefficient of \(x^{15}\) in \(P(x) = (x^1+x^2+x^3+x^4+x^5+x^6)^3\).
\(P(x) = x^3(1+x+x^2+x^3+x^4+x^5)^3\) thus we need the coefficient of \(x^{12}\) in \((1+x+x^2+x^3+x^4+x^5)^3=\frac{(1-x^6)^3}{(1-x)^3}\). We’d learn about bionomial expansions of positive and negative powers in the next chapter, but for now assume that \((1-x)^{-3}=1+3x+6x^2+….28x^6+…91x^{12}+…\)
Thus we need the coefficient of \(x^{12}\) in \((1-3x^6+3x^{12}+…-x^{18})(1+3x+6x^2+….+28x^6+…+91x^{12}+…)\).
The coefficient thus turns out to be \(91-84+3=10\).
Test Your Concepts:
Can we solve the abve problem by finding the number of positive integer solutions of \(x_1+x_2+x_3=15\) ?
We can thus generalise this to the following:
If there are l objects of one kind, m objects of another kind, n ojects of another…then the number of ways of choosing r objects from this is the coefficient of \(x^r\) in \((1+x+x^2+..+x^l)(1+x+x^2+…+x^m)(1+x+x^2+…x^n)…\)
This is sometimes referred to as the Multinomial Theorem.
Using this, we can try to look at the number of non-negative integer solutions of equations of the type
\(\alpha +2\beta +3\gamma+…q\theta =n\)
If we assume \(x_1=\alpha\), \(x_2=2\beta\), \(x_3=3\gamma\), and so on then we’re basically looking at non-negative integer solutions of the equation
\(x_1+x_2+…+x_r=n\)
But there’s a catch – \(x_2\) has to be divisible by 2, \(x_3\) by 3 and so on. In other words, \(x_2 \in \{0,2,4,6…\}\), \(x_3 \in \{0,3,6,9,12,…\}\) and so on. Thus, falling back on what we have learnt, we create the generating polynomial of this, and then get the coefficient of \(x^n\) to get the number of solutions for the equation.
The number of non-negative solutions of the above equation is the coefficient of \(x^n\) in \((1+x+x^2+x^3+…)(1+x^2+x^4+x^6+…)(1+x^3+x^6+x^9+…)…(1+x^q+x^{2q}+…)\).
This further simplifies to finding the coefficient of \(x^n\) in \((1-x)^{-1}(1-x^2)^{-1}(1-x^3)^{-1}…(1-x^q)^{-1}\).
1.2 Derangements
A derangement is a permutation with no fixed points. That is, a derangement of a set leaves no element in its original place. For example, the derangements of \(\{1,2,3\}\) are \(\{2,3,1\}\) and \(\{3,1,2\}\), but \(\{3,2,1\}\) is not a derangement of \(\{1,2,3\}\) because 2 is a fixed point.
To make things simpler, if \(n\) elements are arranged in a row, then the number of ways in which they can be arranged such that no element occupies its original place is give by the formula:
The proof of this uses the PIE (Principle of Inclusion and Exclusion), which we’ll be covering as an optional addon in this module.
Ex-2
A person writes 6 letters to his friends and addressess the corresponding envelopes. How many ways can he place the letters in the envelopes such that at least 2 of them are in the wrong envelopes?
Solution:
We start with 2 – so the number of ways in which 2 letters do not go into the right envelopes = \(C(6,2)\times D_2\).
Similarly for 3 letters, the number of ways in which they don’t go to their right envelopes = \(C(6,3)\times D_3\).
Thus the total number of ways for which at least 2 letters are wrongly placed in the envelopes is
\(\sum\limits_{r=2}^{r=6}C(6,r).D_r = 719\).