# Proof of combinatorial equality via bijection.

There are $150$ identical persons who have to vote for one of three politicians $(a,b,c)$. In how many ways can the votes be distributed so none of them has absolute majority(76 votes or more)? We can classify the ways by the number of votes $a$ gets.

Doing this we see there are $1+2+3+\dots+75+76$ ways to do so. This is $\binom{77}{2}$. Can someone show me a simple bijection between the ways to distribute the votes and the number of ways to pick to distinct integer numbers between $0$ and $76$?

• Maybe I'm too silly, but if it were $6$ people, the possibilities would be $(3,0,3)$, $(3,3,0)$, $(2,2,2)$ and $(0,3,3)$, wouldn't it? And what would your formula give? – mathse May 11 '14 at 22:58
• the formula would give $\binom{\frac{6}{2}+2}{2}=\binom{5}{2}=10$ the ways to to it are $(0,3,3),(1,2,3),(1,3,2),(2,1,3),(2,2,2),(2,3,1),(3,0,3),(3,1,2),(3,2,1),(3,3,0)$ – Jorge Fernández Hidalgo May 11 '14 at 23:24
• But $(1,2,3)$: here $c$ has a majority. Maybe you should make this clear what you want. – mathse May 12 '14 at 7:17
• Alternatively, from your formula and your enumeration, I think what you want is maybe the number of weak integer compositions of $n$ into $3$ parts, such that no part is greater than $n/2$. In your case, $n=150$. – mathse May 12 '14 at 11:45
• majority means having more than 50% of the votes. – Jorge Fernández Hidalgo May 12 '14 at 12:56

## Answer to the actual question

Note that $\binom{75+2}{2}=\binom{77}{2}$ denotes the number of ways you can split $75$ elements into three groups since if you line up $77$ elements and point out two of those as splitting points the remaining $75$ have been divided in three.

Suppose $75$ has been split in this manner into portions $(x,y,z)$ i.e. $x+y+z=75$ where $x,y$ and $z$ are natural numbers. As mentioned this can be constructed in bijection with $\binom{77}{2}$. Then $(x,y,z)$ can be translated into $(a,b,c)$ as follows \begin{align} a&=75-x\\ \quad\\ \quad\\ b&=75-y\\ \quad\\ \quad\\ c&=75-z \end{align} Then clearly $a,b,c\leq 75$ and furthermore $a+b+c=3\cdot 75-(x+y+z)=150$ as desired.

String has answered this wonderfully, but I wanted to point out how with a little introduction of concepts we can very easily generalize the results.

First, it is easy to see that the original question asks for the number of solutions, in nonnegative integers, of $a+b+c=150$ such that $0\le a,b,c\le 75$. More generally, we can ask for the number of solutions, in nonnegative integers, of $x_1+\cdots+x_k=n$ such that $0\le x_1,x_2,\ldots,x_k\le m$ for some $n$ and $m$ and $k$. This problem is known as the restricted integer composition problem, see for example http://en.wikipedia.org/wiki/Composition_(combinatorics). Let us denote the number of solutions to this problem by $c(n,k,0,m)$ ($k$ is called the number of parts).

Now, to each solution $(x_1,\ldots,x_k)$ of $x_1+\cdots+x_k=n$ with $0\le x_1,\ldots,x_k\le m$, we may associate the tuple $(y_1,\ldots,y_k)$ where $y_i=m-x_i$, whence $0\le y_1,\ldots,y_k\le m$. Then $y_1+\cdots+y_k=km-n$ and, as stated, $0\le y_1,\ldots,y_k\le m$. In other words,

$$c(n,k,0,m) = c(km-n,k,0,m).$$

Now, when we let $m=n/2$ and $k=3$, then $km-n=3n/2-n=n/2$ and the RHS specializes to $c(n/2,3,0,n/2)$, which is the number of weak compositions of $n/2$ in $3$ parts (the upper bound is of no importance here as the lower bound zero ensures that no part is greater than $n/2$ anyway), for which the well-known formula $\binom{n/2+k-1}{k-1}$ holds, which gives the solution for the original problem. (In general $c(N,K,0,N)=\binom{N+K-1}{K-1}$.)

For which other $m$, $n$, and $k$ do we get 'nice' solutions? When $km-n=m$ holds, or equivalently, $m=\frac{n}{k-1}$ (assuming this to be integral), then we have that the above RHS is $c(n/(k-1),k,0,n/(k-1))=\binom{\frac{n}{k-1}+k-1}{k-1}$ and the LHS gives $c(n,k,0,n/(k-1))$. So, if there are $n$ voters and $k$ candidates (such that $n$ is a multiple of $k-1$), then there are precisely $\binom{\frac{n}{k-1}+k-1}{k-1}$ ways to distribute the votes such that no candidate has a majority of more than $n/(k-1)$ votes.

• Very interesting generalizations, indeed! – String May 12 '14 at 20:42

This was answered before I knew what was meant by "majority", so this answer does not meet the requirements of the task

## Configurations with no majority

There is one way all three can have the same number of votes, namely $(50,50,50)$. For the other situations assume $x\in\{a,b,c\}$ has received fewest votes. Since the remaining votes must be divided into two equal parts $x$ has to be even. So we have $0\leq x=2k\leq 50$ equivalent to $0\le1 k\leq 24$. This makes a total of $3\cdot 25+1=76$ configurations.

Doing a similar analysis for the general case with $6m$ people voting for $(a,b,c)$ we get $3m+1$ configurations. For $m=1$ (as in the comments) this makes $4$ configurations which was what mathse correctly gave.

## Configurations as a total

If we make no restrictions regarding majority of vote etc. the votes can be distributed in the following manner:

We must divide $150$ people into three parts. This can be done by adding two blanks to define the points of division. So now we have $152$ items and must choose $2$ of them as blanks dividing the remaining $150$ into three parts. This can be done in $\binom{150+2}{2}$ ways.

This seems somehow related to the figure you gave, but I do not see what your suggested figure is about. Sorry for that, maybe you can comment or edit in order to make me and other able to answer your question?

• by no one having majority I mean no one has 76 or more votes. – Jorge Fernández Hidalgo May 12 '14 at 13:48
• OK, thanks. I clearly misunderstood that! – String May 12 '14 at 15:15