# Using Generating Functions To Count Things

At the theater, the movie X is currently showing. However, there are only $$7$$ tickets left in row $$F$$, $$8$$ tickets left in row $$G$$, and $$9$$ tickets left in row $$H$$.
A group of students enters the theater and wants to buy $$6$$ tickets with the requirement that there must be tickets in each of the three rows $$F$$, $$G$$, and $$H$$.
How many ways can the ticket seller sell tickets to the group of students?

I have done Direct Counting.
The answer to the counting problem is $$C_{24}^6-[C_{15}^6+C_{17}^6+C_{16}^6-\left(C_7^6+C_8^6+C_9^6\right)]=109326.$$

I think the problem can use generating functions.
I am looking for such a way.

• Does it matter to which student each ticket is distributed to? Or just the seats?
– qwr
Commented May 18 at 3:25

This is a math problem from my school, the solution is purely combinatorial. Here is the solution using generating functions. The problem of taking $$n$$ coins from $$24$$ people, with each person taking at most $$1$$ coin, can be represented by the generating function: $$[(1+x)^7-1] \cdot[(1+x)^8-1]\cdot [(1+x)^9-1]$$ $$=(1+x)^{24}-[(1+x)^{17}+(1+x)^{16}+(1+x)^{15}]+(1+x)^9+(1+x)^8+(1+x)^7-1.$$ The coefficient containing $$x^n$$ will be $$\binom{24}{n}-\left[\binom{17}{n}+\binom{16}{n}+\binom{15}{n}\right]+\binom{9}{n}+\binom{8}{n}+\binom{7}{n}.$$

Applying generating function is not much use here.
Still , using that might help in getting familiarity with that concept.

Let us make the Polynomial where the Co-efficients are the number of ways to select $$0$$ or $$1$$ or $$2$$ or more tickets out of $$7$$ seats :
It is this :
$$(1+7X+21X^2+35X^3+35X^4+21X^5+7X^6+1X^7)$$

Similarly , we can make the Polynomial where the Co-efficients are the number of ways to select $$0$$ or $$1$$ or $$2$$ or more tickets out of $$8$$ seats :
$$(1+8X+28X^2+56X^3+70X^4+56X^5+28X^6+8X^7+1X^8)$$

Like-wise , we can make the Polynomial where the Co-efficients are the number of ways to select $$0$$ or $$1$$ or $$2$$ or more tickets out of $$8$$ seats :
$$(1+9X+36X^2+84X^3+126X^4+126X^5+84X^6+36X^7+9X^8+1X^9)$$

When we multiply these , we will get the ways , which includes $$0$$ tickets in some rows.
We do not want $$0$$ tickets , hence we remove that term in the Polynomials & then multiply.
$$(7X+21X^2+35X^3+35X^4+21X^5+7X^6+1X^7)(8X+28X^2+56X^3+70X^4+56X^5+28X^6+8X^7+1X^8)(9X+36X^2+84X^3+126X^4+126X^5+84X^6+36X^7+9X^8+1X^9)$$
Pick the Co-efficent of $$X^6$$ to get the Count.

EXPAND (7X+21X^2+35X^3+35X^4+21X^5+7X^6+1X^7)(8X+28X^2+56X^3+70X^4+56X^5+28X^6+8X^7+1X^8)(9X+36X^2+84X^3+126X^4+126X^5+84X^6+36X^7+9X^8+1X^9)


It says :

We can see that the Co-efficent of $$X^6$$ is indeed $$109326$$
It is more work here.
We can get familiarity with the technique to use elsewhere.

• In actual computation, you can ignore all the powers above 6. This is still small enough to do by hand. And I think you can multiply polynomials in O(n log n) with FFT?
– qwr
Commented May 18 at 3:09
• Nice Point ignoring larger Powers , @qwr , though not sure what syntax I have to use with Wolfram. I am not much aware of Polynomial Multiplication with FFT , though I think what you say is right.
– Prem
Commented May 18 at 5:11
• Idk the Mathematica syntax. Maybe you can work mod X^7 to not consider higher powers.
– qwr
Commented May 18 at 16:30
• That sounds like a Workable Suggestion , @qwr , thanks !!
– Prem
Commented May 19 at 6:51