2
$\begingroup$

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.

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

2 Answers 2

3
$\begingroup$

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}.$$

$\endgroup$
3
$\begingroup$

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.

When I ask Wolfram :

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 :
POLYNOMIAL

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – qwr
    Commented May 18 at 3:09
  • $\begingroup$ 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. $\endgroup$
    – Prem
    Commented May 18 at 5:11
  • $\begingroup$ Idk the Mathematica syntax. Maybe you can work mod X^7 to not consider higher powers. $\endgroup$
    – qwr
    Commented May 18 at 16:30
  • $\begingroup$ That sounds like a Workable Suggestion , @qwr , thanks !! $\endgroup$
    – Prem
    Commented May 19 at 6:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .