3
$\begingroup$

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.

Could anyone please help?

Thanks a million.

  • 0
    @Ross: I would suppose that they're different too; B would be happier in the first case than in the second, I reckon. :)2011-08-21

2 Answers 2

2

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

  • 0
    Yep I was thinking at first of having 40+ votes and not 41+ which caused problems of duplicates. Thanks :)2011-08-21
0

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.