Am I supposed to use generating functions or combinatorics or something for this question?

Question

If there are 201 seats in the Parliamentary chamber, how many different ways are there for the numbers of seats to be allocated amongst three political parties, subject to no one party having an overall majority?

I could figure it out manually. 201/3 = 67 per party. Thats one way. Then divide 67/2 (because you can move 2 from one party at a time to ensure the other 2 are equal) = 33.5 but use lower bound as a person cannot be split in half. That makes it 100+100+1 = 201. So now thats 33 ways. But party that gives up 2 each time can change. i.e. Party A gives up 2 members to B&C until 1 remain. Then party B gives up... then C. So would it be 1+(33*3) = 100 ways?

Is there a cleaner way to do this, say using generating funtions or combinatorics of some sort? If not I dont know why the would ask this question.

Any help appreciated.

Answer 1

Method one: a solution by manual inspection

First, note that no party can have more than $100$ seats otherwise they have an overall majority.

Let's call the parties $A$, $B$ and $C$ and look at the possible seats for $B$ and $C$ as we change the number of seats won by $A$.

• If $A$ has $0$ seats, then either $B$ or $C$ must have at least $101$ seats, so this is not possible.
• If $A$ has $1$ seat, then the remaining $200$ seats must be split $100$ each to $B$ and $C$. $1$ way.
• If $A$ has $2$ seats, then the remaining $199$ seats can be split $(99,100)$ or $(100,99)$. $2$ ways.
• If $A$ has $3$ seats, then $198$ seats can be split $(98,100)$, $(99,99)$ or $(100,98)$. $3$ ways.
• If $A$ has $4$ seats, then $197$ seats can be split $(97,100)$, $(98,99)$, $(98,99)$ or $(100,97)$. $4$ ways.

Hopefully this is enough to establish the pattern which continues up to $A$ having $100$ seats and leads to the solution.

---

Method two: a solution by combinatorics

This can be solved using the stars and bars method and using inclusion-exclusion to eliminate combinations where one party has a majority.

The total number of ways to allocate the seats is$$\binom{201+3-1}{3-1}=\binom{203}{2}$$ but if we force the first group to have at least $101$ seats we can use$$\binom{203-101}{2}=\binom{102}{2}$$ to get the number of combinations where party $A$ has at least $101$ seats. As there are three parties we need to multiply this by $3$ when we exclude these combinations. The overall number of ways to allocate the seats is$$\binom{203}{2}-3\binom{102}{2}=5050$$

Answer 2

We seek the number of integer solutions to the equation $$ x_1+x_2+x_3=201\tag{1} $$ where $ 0\leq x _i \leq 100$. You can solve this using generating functions by noting that this is equivalent to finding the coefficient of $x^{201}$ in the generating function of $$ (1+x+\dotsb x^{100})^3 =\frac{(1-x^{101})^3}{(1-x)^3} =(1-3x^{101}+3x^{202}+x^{303})\left(\frac{1}{(1-x)^3}\right).\tag{2} $$ Use the identity $$ \frac{1}{(1-x)^3}=\sum_{n=0}^\infty \binom{n+2}{2}x^n.\tag{3} $$ (which can be obtained by repeatedly differentiating the geometric series) to find that the coefficient of $x^{201}$ is $$ \binom{201+2}{2}-3\binom{(201-101)+2}{2}\tag{4} $$ which can be obtained equivalently using inclusion exclusion.