# Number of possible results in election with one of candidates getting more then 50% votes

I have been trying to solve a question in combinatorics which is as follows:

How many possible results are there for an election where 80 people voted for 4 different candidates where one of the candidates received more then 50% of the votes?

I have tried to figure out how to do this and can't seem to manage I started with calculating the entire possible results which came out to be $\frac{83!}{3!}$ and continue from there. But I can't seem to find the way. I know I need to use the inclusive exclusive principle but I am not sure how to apply it.

Thanks a million.

-
Are A:51 B:10 C:15 D:4 and A:51 B:4 C:10 D:15 different results? – Ross Millikan Aug 21 '11 at 16:55
Yes they are (this is an election so it matters I guess even though it was specifically stated in the question) – Dan Aug 21 '11 at 16:57
@Ross: I would suppose that they're different too; B would be happier in the first case than in the second, I reckon. :) – J. M. Aug 21 '11 at 17:07

Since A must have at least 41 votes, go ahead and set the problem up like A: 41, B: 0, C: 0, D: 0.

The problem now is how to distribute the remaining 39 votes among the 4 candidates where candidates might receive no votes. That is, we must arrange 39 unlabeled balls (votes) into 4 labeled boxes (candidates) where boxes may be empty.

In general, we can arrange $n$ unlabeled balls into $m$ labeled boxes with some possibly empty in $$\binom{n + m - 1}{n}$$ ways. (See, for example, here if you'd like more on this result.)

Thus, for the problem at hand, we get $$\binom{42}{39}$$ possible outcomes for the election.

EDIT: This solution assumes that candidate A is the winner. To account for the possibility of any candidate being the winner, multiply the previous result by 4: $$4 \binom{42}{39}.$$

-
Hmm interesting :) but there is still a problem of having only accounted for the first participant (A) having more then 50% of the votes I'm trying to think if just multiplying by 4 fixes this problem – Dan Aug 21 '11 at 17:23
My first post had some problems (I switched the roles of $n$ and $m$ and forgot to subtract 1), but it should be correct now. – Austin Mohr Aug 21 '11 at 17:23
I misread the problem and thought it had to be A was the winner. Multiplying by 4 will indeed fix the problem. – Austin Mohr Aug 21 '11 at 17:25
I think you have a good starting point but because any candidate can be the one with 41+ votes then this needs at the very least to be multiplied by 4 – Dan Aug 21 '11 at 17:26
The multiplication by 4 is exactly what is needed. Just think of it in four cases: A wins, B wins, C wins, or D wins. I first did the case where A wins. If we set it up for B wins, we will again get $\binom{42}{39}$ ways and they are all distinct since a different candidate is winning. Similarly for C and D. – Austin Mohr Aug 21 '11 at 17:30

There are $n+1$ compositions of $n$ into two parts. For compositions into three parts, let the first part be $i$ and sum over $i$, so there are $\sum_{i=0}^n (n-i)+1=n+1+\frac{n(n+1)}{2}=\frac{(n+1)(n+2)}{2}$ compositions of $n$ into three parts. Now let the winner have $j$. If the winner is the first part, there are $\sum_{j=41}^{80}\frac{(n-j+1)(n-j+2)}{2}$ compositions. Now multiply by $4$ to move the winner to any location.

-