2
$\begingroup$

My problem is similar to this one, but different in some significant ways.

As in the above question, I have voting with $n$ voters and $m$ candidates. However, I care about which voter voted for which candidate. As such, there are a total of $m^n$ possible configurations.

Also, of these possible configurations, how many did candidate 1 have a plurality (see below). That is, how many did candidate 1 win (I choose candidate 1 arbitrarily. Of course it is symmetric across candidates). Further, how many configurations are ties in which candidate 1 participated.

For example, here are some situations ($n=6, m=5$) where candidate 1 wins.

v1 v2 v3 v4 v5 v6
-----------------
1  1  1  1  1  1
1  1  1  1  3  3
1  1  1  2  2  3
1  1  2  3  4  5

(Notice that what I want is a plurality and not a majority: a candidate does not need to have more than 50% of the votes, just more votes than anyone else.)

Here is a two-way tie:

v1 v2 v3 v4 v5 v6
-----------------
1  1  2  2  3  4

Candidates 1 and 2 are tied for the most number of votes. Here are some situations ($n=5, m=3$) where candidate 1 loses.

v1 v2 v3 v4 v5
--------------
1  2  2  2  3
1  2  2  3  3
2  2  2  2  2

This would just be stars and bars, except I care about the order. That is, I want to count the following situations as distinct:

v1 v2 v3 v4 v5
--------------
1  1  1  2  3
1  1  1  3  2
1  1  1  3  3
1  1  2  1  3
...
$\endgroup$
  • $\begingroup$ You explain the setup very well, but it would be better to put the "winning plurality" criterion early on in the problem statement, just where you state what it is that is being asked for (winning configurations for candidate 1). $\endgroup$ – hardmath Dec 2 '14 at 21:04
  • $\begingroup$ Good point. Thanks. $\endgroup$ – mayhewsw Dec 2 '14 at 21:07
  • $\begingroup$ @mayhewsw Any solution since the time you posted the question? $\endgroup$ – Antonin Feb 11 '15 at 21:51
  • $\begingroup$ Nope. Still looking. $\endgroup$ – mayhewsw Feb 11 '15 at 22:28
0
$\begingroup$

One possible answer is found in this paper, although the solution involves simplifying the problem. That is, allow only an odd number of votes.

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