In the parliament of a certain country there are 201 seats, and 3 political parties. How many ways can these seats be divided among the parties such that no single party has a majority? Is there any generalization of solution of this problem?
Majority in Parliament Problem
3 Answers
A minimal majority is $101$ seats, so the problem is to count the number of solutions in non-negative integers $a,b,c$ of the equation $a+b+c=201$, subject to the restriction that $a,b,c\le 100$. (Think of $a,b$, and $c$ as the numbers of seats given to parties $A,B$, and $C$, respectively.) If we ignore the restriction for the moment, this is a standard stars-and-bars problem, and the solution is that there are
$\binom{201+3-1}{3-1}=\binom{203}2=\frac{203\cdot202}2=20,503\tag{1}$
ways to divide up the seats. However, some of these ways are unacceptable, because they give more than $100$ seats to some party, so we have to count the unacceptable distributions of seats and subtract that from the provisional answer in $(1)$.
The number of distributions giving party $A$ more than $100$ seats can be counted as follows. First allot $101$ seats to $A$; this leaves $100$ seats that can be freely distributed amongst the three parties, so we’re just counting the solutions to $x+y+z=100$ in non-negative integers:
$\binom{100+3-1}{3-1}=\binom{102}2=\frac{102\cdot101}2=5151\;.$
Clearly there are just as many distributions that give too many seats to party $B$, and just as many that give too many seats to party $C$. There are obviously no distributions that give a majority to more than one party, so the final answer is
$20,503-3\cdot5151=5050\;.$
It’s not hard to see how to generalize this solution to different numbers of seats and parties: if there are $n$ seats and $p$ parties, let $m=\lfloor n/2\rfloor$; $m$ is the largest number of seats that a party can have without having a majority, and the number of distributions of seats giving no party a majority is
$\binom{n+p-1}{p-1}-p\binom{m+p-1}{p-1}\;.$
We can begin by experimenting. If party $A$ has $1$ seat, then $B$ must have $100$, else $C$ has too many. If party $A$ has $2$ seats, then $B$ can have $100$ or $99$. If $A$ has $3$ seats, then $B$ can have $100$, $99$, or $98$. And so on. Finally, if $A$ has $100$ seats, then $B$ can have anywhere from $100$ down to $1$. So the number of possibilities is $1+2+3+\cdots+100.$ This is a familiar sum, simply evaluated as $5050$ by various methods. A quick method for summing the series was known, it is said, by the $8$-year old Gauss, and undoubtedly by many $8$-year olds before and since.
For three parties, the same idea works for any number of seats $n$.
This is meant to be an alternative way to arrive at Brian's answer.
Let the size of the parliament be $2m+1$.
Let $(k_1,k_2,k_3)$ denote the tuple of number of seats that each party got. We require that $k_1,k_2,k_3 \leqslant m$.
The answer to the problem is the number of such tuples that meet the requirement: $ \sum_{k_1=0}^m \sum_{k_2=0}^m \sum_{k_3=0}^m \delta_{k_1+k_2+k_3, 2m+1} = [t^{2m+1}] \sum_{k_1=0}^m \sum_{k_2=0}^m \sum_{k_3=0}^m t^{k_1+k_2+k_3} = [t^{2m+1}] \left(\frac{1-t^{m+1}}{1-t}\right)^3 = [t^{2m+1}] \frac{1-3 t^{m+1}}{\left(1-t\right)^3} = [t^{2m+1}] \frac{1}{\left(1-t\right)^3} - 3 [t^{m}] \frac{1}{\left(1-t\right)^3} = \binom{2m+1+3-1}{2m+1} - 3 \binom{m+3-1}{m} = \frac{m(m+1)}{2} $
Generalization to $p$ parties gives: $ [t^{2m+1}] \left(\frac{1-t^{m+1}}{1-t}\right)^p = \binom{2m+p}{2m+1} - p \binom{m+p-1}{m} $