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.

  • 1
    Are A:51 B:10 C:15 D:4 and A:51 B:4 C:10 D:15 different results?2011-08-21
  • 0
    Yes they are (this is an election so it matters I guess even though it was specifically stated in the question)2011-08-21
  • 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
    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 problem2011-08-21
  • 0
    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.2011-08-21
  • 0
    I misread the problem and thought it had to be A was the winner. Multiplying by 4 will indeed fix the problem.2011-08-21
  • 0
    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 42011-08-21
  • 0
    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.2011-08-21
  • 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.