# Generating Functionology Examples

Question 1:
There are 50 students in a class and 6 students are to be selected to form placement committee.  In how many ways this can be done?
Solution:
Each student is selected or not selected. ${x^0}$ indicates not selected and ${x^1}$ is selected.  So total options for one student = $1 + x$.
Let there by $n$ students.  Number of ways of choosing $r$ students is nothing but coefficient of ${x^r}$ in ${\left( {1 + x} \right)^n}$
We know that the coefficients of the above expansion is $1,~{}^n{C_1},{}^n{C_2},...$.  So ${k^{th}}$ coefficient is ${}^n{C_k}$
If each of the 50 students contribute one factor of $1 + x$, then $f\left( x \right) = {\left( {1 + x} \right)^{50}}$
The number of ways of selecting 6 students is nothing but ${x^6}$ coefficient.  We know that this is ${}^{50}{C_6}$

Question 2:
Find the coefficient of ${x^{17}}$ in the expansion of ${\left( {1 + {x^5} + {x^7}} \right)^{20}}$
(IMO 2001 HK Preliminary Selection Contest)
Solution:
The only way to form an ${x^{17}}$ term is to gather two ${x^5}$ and one ${x^7}$.  To understand the application of GF, let us describe the above problem in another way. Suppose there are 20 questions in an exam.  Each question may award 5 or 7 marks. If a question is not attempted then no marks will be awarded.  So in how many ways a student can get exactly 17 marks? 17 marks can be achieved by getting 2 questions correct and securing 5 marks each and one question with 7 marks. So there are ${}^{20}{C_2}$ = 190 ways to choose two 5 marks questions from the 20 questions, and ${}^{18}{C_1}$ ways to choose a 7 mark question from the remaining 18 questions.  So total ways = 190 x 18 = 3420

Question 3:
A four digit number (0000 to 9999) is said to be lucky, if sum of its first two digits is equal to sum of its last two digits.   Find the number of lucky numbers
Solution:
Let the first two digits are x and y. The generating function for the first digit = $1 + x + {x^2} + ...{x^9}$ ($\because$ single digit number varies from 0 to 9)
Similarly, generating function for the second digit = $1 + x + {x^2} + ...{x^9}$
So the sum is given by the coefficient of ${x^n}$ in ${\left( {1 + x + {x^2} + ...{x^9}} \right)^2}$
Let ${\left( {1 + x + {x^2} + ...{x^9}} \right)^2}$ = ${a_0} + {a_1}x + ... + {a_{18}}{x^{18}}$ - - - (1)
Similarly, the generating function for the remaining two digits = ${\left( {1 + x + {x^2} + ...{x^9}} \right)^2}$ = ${a_0} + {a_1}x + ... + {a_{18}}{x^{18}}$ - - - (2)
To get the sum equal for both pairs of numbers, we have to find the value of ${a_0}^2 + {a_1}^2... + {a_{18}}^2$.  Here ${a_0}$ is the number of ways sum of the digits is 0, ${a_1}$ is the number of ways the sum of digits is 1 and so on.
To make things easy, we can substitute $x = \dfrac{1}{x}$ in equation (2)
${\left( {1 + \dfrac{1}{x} + \dfrac{1}{{{x^2}}} + ... + \dfrac{1}{{{x^9}}}} \right)^2}$ = ${a_0} + \dfrac{{{a_1}}}{x} + ... + \dfrac{{{a_{18}}}}{{{x^{18}}}}$ - - - (3)
If you observe it carefully, there is no $x$ term in the coefficients of ${a_0}^2, {a_1}^2, . . . {a_{18}}^2$ in the product (1) and (3).
(1) x (3) = ${a_0}^2 + {a_1}^2... + {a_{18}}^2$  = ${\left( {1 + x + {x^2} + ...{x^9}} \right)^2}$ x ${\left( {1 + \dfrac{1}{x} + \dfrac{1}{{{x^2}}} + ... + \dfrac{1}{{{x^9}}}} \right)^2}$
= ${\left( {\dfrac{{1 - {x^{10}}}}{{1 - x}}} \right)^2} \times {\left( {\dfrac{{{x^9} + {x^8} + ... + 1}}{{{x^9}}}} \right)^2}$
Therefore, we find constant term in RHS too.
= $\dfrac{1}{{{x^{18}}}}{\left( {\dfrac{{1 - {x^{10}}}}{{1 - x}}} \right)^2} \times {\left( {\dfrac{{1 - {x^{10}}}}{{1 - x}}} \right)^2}$
= ${x^{ - 18}} \times {\left( {1 - {x^{10}}} \right)^4} \times {\left( {1 - x} \right)^{ - 4}}$
To find the constant term, we have to find ${x^{18}}$ coefficient in ${\left( {1 - {x^{10}}} \right)^4}{\left( {1 - x} \right)^{ - 4}}$
= $\left( {1 - 4{x^{10}}} \right)\left( {1 + {}^4{C_1}x + {}^5{C_2}{x^2} + ...} \right)$
= ${}^{21}{C_{18}} - 4.{}^{11}{C_8}$
= 1330 - 660 = 670

Alternative Method:
Let the number be $aabb$
If the sum of the first two digits = 0, Then number of ways of choosing aa, bb = [(0, 0)], [(0,0)]. ie., one way.
If the sum of the first two digits = 1, then total ways of choosing aa is 2 ways. i.e.,  (0, 1), (0, 1).  Also bb can be chosen in two ways.   Total ways = 2 x 2 = 4
If sum of the first two digits = 2, then total ways of choosing aa is 3 ways. i.e., (0, 2), (1, 1), (2, 0).   Also bb can be chosen in 3 ways.  Total ways = 3 x 3 = 9
Continuing the same pattern, sum 9 can be achieved by ${10^2}$ ways, but sum 10 can be achieved by ${9^2}$ ways so on upto sum 18 can be achieved by ${1^2}$ ways.
Total ways = $2 \times \left( {{1^2} + {2^2} + ... + {9^2}} \right) + {10^2}$
= $2 \times \left( {\dfrac{{9\left( {9 + 1)\left( {18 + 1} \right)} \right)}}{6}} \right) + {10^2}$
= 670

Question 4:
Two persons each makes a single throw with a pair of dice.  The probability that the throws are equal is
Solution:
The generating function for the sum of a pair of dice = ${\left( {{x^1} + {x^2} + ... + {x^6}} \right)^2}$ = ${a_2}{x^2} + {a_3}{x^3} +$. . . $+ {a_{12}}{x^{12}}$ - - - (1)
Similarly the generating function the the second person = ${\left( {{x^1} + {x^2} + ... + {x^6}} \right)^2}$ = ${a_2}{x^2} + {a_3}{x^3} +$. . . $+ {a_{12}}{x^{12}}$ - - - (2)
To get the sum equal for both pairs of dice, we have to find the value of ${a_2}^2 + {a_3}^2... + {a_{12}}^2$.  Here ${a_2}$ is the number of ways sum of the dice 2, ${a_3}$ is the number of ways the sum of digits is 3 and so on.
To make things easy, we can substitute $x = \dfrac{1}{x}$ in equation (2)
${\left( {\dfrac{1}{x} + \dfrac{1}{{{x^2}}} + ... + \dfrac{1}{{{x^6}}}} \right)^2}$ = $\dfrac{{{a_2}}}{{{x^2}}} + ... + \dfrac{{{a_{12}}}}{{{x^{12}}}}$ - - - (3)
Multiplying 2 and 3, we get constant term.
= ${\left( {{x^1} + {x^2} + ... + {x^6}} \right)^2}$$\times$${\left( {\dfrac{1}{x} + \dfrac{1}{{{x^2}}} + ... + \dfrac{1}{{{x^6}}}} \right)^2}$
= ${x^2}{\left( {1 + x + ... + {x^5}} \right)^2}$$\times$$\dfrac{1}{{{x^{12}}}}\left( {1 + x + ... + {x^5}} \right)^2$
= ${x^{ - 10}} \times {\left( {\dfrac{{1 - {x^6}}}{{1 - x}}} \right)^2} \times {\left( {\dfrac{{1 - {x^6}}}{{1 - x}}} \right)^2}$
= ${x^{ - 10}} \times {\left( {1 - {x^6}} \right)^4} \times {\left( {1 - x} \right)^{ - 4}}$
We need to find ${x^10}$ in ${\left( {1 - {x^6}} \right)^4} \times {\left( {1 - x} \right)^{ - 4}}$
= $\left( {1 - {}^4{C_1}\left( {{x^6}} \right) + ..} \right)$$\left( {1 + {}^4{C_1}x + {}^5{C_2}{x^2} + ...} \right)$
= ${}^{13}{C_{10}} - {}^7{C_4}$
= 146

Alternative Method:
Sum of the digits on the two dice vary from 2 to 12.   Number of ways of getting these on a single dice = 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1
So the number of ways of getting the sum equal on both the throws = ${1^2} + {2^2} + ... + {5^2}$ $+ {6^2} + {5^2} + ... + {1^2}$
= $2 \times \left( {{1^2} + {2^2} + ... + {5^2}} \right) + {6^2}$
= 146

Question 5:
A student goes in for an exam in which there are 4 papers with a maximum of 10 marks for each paper.  The number of ways of getting 20 marks on the whole is
Solution:
The Generating Function (GF) for one paper = $1 + x + ... + {x^{10}}$
The GF for four papers = ${\left( {1 + x + ... + {x^{10}}} \right)^4}$
We have to find ${x^{20}}$ coefficient in the above expression.
$1 + x + ... + {x^{10}}$ = ${\left( {\dfrac{{1 - {x^{11}}}}{{1 - x}}} \right)^4}$
( $\because$ The terms are in G.P.  $1 + x + ... + {x^r} = \dfrac{{1 - {x^{(r + 1)}}}}{{1 - x}}$ )
$\Rightarrow {\left( {1 - {x^{11}}} \right)^4} \times {\left( {1 - x} \right)^{ - 4}}$
$\Rightarrow \left( {1 - {}^4{C_1}{x^{11}} + {}^4{C_2}{x^{22}} + ..} \right) \times {\left( {1 - x} \right)^{ - 4}}$
The terms from ${x^{22}}$ or later are not required as the power we need to find is only ${x^{20}}$.
So Required answer = ${}^{ - 4}{C_{20}} + \left( { - 4 \times {}^{ - 4}{C_9}} \right)$
= ${}^{4 + (20 - 1)}{C_{20}} - 4 \times {}^{4 + (9 - 1)}{C_9}$
= ${}^{23}{C_{20}} - 4 \times {}^{12}{C_9}$
= ${}^{23}{C_3} - 4 \times {}^{12}{C_3}$
= $\dfrac{{23.22.21 - 4.12.11.10}}{6}$
= $891$

Question 6:
Out of 5 apples, 10 mangoes, and 15 oranges, the number of ways of selecting 15 fruits is
Solution:
GF for apples = $1 + x + {x^2} + ... + {x^5}$ = $\dfrac{{1 - {x^6}}}{{1 - x}}$
GF for mangoes = $1 + x + {x^2} + ... + {x^{10}}$ = $\dfrac{{1 - {x^{11}}}}{{1 - x}}$
GF for oranges = $1 + x + {x^2} + ... + {x^{15}}$ = $\dfrac{{1 - {x^{16}}}}{{1 - x}}$
Final GF = $\left( {\dfrac{{1 - {x^6}}}{{1 - x}}} \right) \times \left( {\dfrac{{1 - {x^{11}}}}{{1 - x}}} \right) \times \left( {\dfrac{{1 - {x^{16}}}}{{1 - x}}} \right)$
We have to find ${x^{15}}$ coefficient in the above expression.
$\Rightarrow \left( {1 - {x^6}} \right)\left( {1 - {x^{11}}} \right)\left( {1 - {x^{16}}} \right){\left( {1 - x} \right)^{ - 3}}$
$\Rightarrow \left( {1 - {x^6} - {x^{11}} + ..} \right){\left( {1 - x} \right)^{ - 3}}$
Because we need to find only ${x^{15}}$ coefficient, any power greater than 15 can be omitted. So we took only upto ${x^{11}}$.
$\Rightarrow {}^{ - 3}{C_{15}} - {}^{ - 3}{C_9} - {}^{ - 3}{C_4}$
$\Rightarrow {}^{3 + (15 - 1)}{C_{15}} - {}^{3 + (9 - 1)}{C_9} - {}^{3 + (4 - 1)}{C_4}$
$\Rightarrow {}^{17}{C_{15}} - {}^{11}{C_9} - {}^6{C_4}$
$\Rightarrow {}^{17}{C_2} - {}^{11}{C_2} - {}^6{C_2}$
= $66$