Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.