[EM] counting ballots
Warren Smith
wds at math.temple.edu
Wed Dec 14 17:02:06 PST 2005
>Kislanko:
The number of full ranked ballots is just the number of permutations of N
alternatives = N!
If equal ranknigs are allowed, it's N! + 2^N - 1
If truncation is allowed it is approximately N! * e
And if both truncation AND equal rankings are allowed it's approximately N!
* e + 2^N - 1
--the statements containing "2^N" are false.
The true answers are in one of the chapters of my (as yet unpublished)
book. Anyhow, letting E(N) denote the answer, there are various direct and indirect
expressions for E(N).
E(N) = #ballots for N candidates with equal rankings allowed. Truncation forbidden.
E(0)=E(1)=1, E(2)=3 E(3)=13 E(4)=75 E(5)=541
Amazingly, E(N) is the nearest integer to
N! / (2*ln(2)^(N+1)) when N=0,1,...,15,16
but this is false when N=17. It is true asymptitically for N large.
Generating function:
sum E(N) * x^N / N! = 1/(2-exp(x))
N>=0
I also have the exact result if truncatio is allowed too, but it is messier.
wds
More information about the Election-Methods
mailing list