0
$\begingroup$

Suppose there are n voters and k candidates. In how many different ways can the vote be split among the candidates?

To be clear, I am only concerned with the number of votes that each candidate gets, not with how individual voters vote.

Each voter can and must vote for only one candidate.

$\endgroup$
2
$\begingroup$

You have $n$ votes for $k$ candidates.

If you line up the votes by candidate, you'll have groups of votes for each one. (Unpopular candidates may not have any votes.)

We can insert $k-1$ dividers in the line of votes to cordon them off by candidate. So if we have $n+k-1$ spaces, we'll have room for all of the votes and the dividers.

Now the problem gets down to how many ways you can choose the spaces for the $k-1$ dividers in the line of $n+k-1$ spaces.

This is the essence of Stars and Bars. Can you take it from here?

$\endgroup$
  • $\begingroup$ Your answer explained the solution very well. Thank you! $\endgroup$ – Chaitanya Gupta May 23 at 19:09
  • $\begingroup$ You're quite welcome. Glad it helped! $\endgroup$ – John May 23 at 19:22
2
$\begingroup$

We seek to find the number of solutions to $x_1 + x_2 + \ldots + x_k =n$ in nonnegative integers. Consider $n$ dots and $k-1$ dividers arranged in a row. The dividers divide the row into $k$ sections, and the number of dots in each gives the $x_i$. There are $n+k-1 \choose k-1$ ways to arrange these, and so this is the number of ways votes can be cast.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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