[EM] counts of possible rank-order votes

[Warren Smith]

as RBJ (and I earlier, and probably many others earlier) proved,
the number of possible rank-order votes
among C candidates is
C!
if rank-equality forbidden and all candidates must be ranked.

And if only some candidates must be ranked it is
floor( C! * e )
...and subtract 1 if disallow empty ballot, and
replace by   floor(C! * (e-1))
if regard ballots ranking all C to be equivalent to those ranking C-1.
(Or do both modifications.)

If rank-equalities permitted, but  all candidates must be ranked, then
one formula should be
    F(C) = sum(for r=1 to C)of    r! * S(C, r)
where the rth summand is for ballots with r rank-levels
and S(n,k) is Stirling number of 2nd kind, pronounced "n subset k".
Those obey the recurrence
S(n, k) = k S(n - 1, k) + S(n - 1, k - 1).
and
S(n,1)=1
and
S(k, k)=1.
Sequence F(C) for C=1,2,3,... is
1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563,
1622632573, 28091567595, 526858348381, 10641342970443,
230283190977853, 5315654681981355, 130370767029135901,
338553466325684532
H.Wilf in book Generatingfunctionology gives the nice infinite sum
    F(C) = sum(j>=0)of j^C / 2^(j+1)
and the exponential generating function is
   1/(2-exp(z)).
A superb asymptotic approximation Wilf finds from that is
    F(C) =~= C! / (2 * (ln2)^(C+1))

If rank-equalities permitted, and not all candidates must be ranked, then
one formula should be
   G(C) = sum(for J=0 to C) sum(for r=1 to J)of    r! * S(J, r) *
binomial( C, J )
where the (J,r)th summand is for ballots with J candidates on r ranking levels,
with C-J candidates unranked.  The sequence G(C) for C=1,2,3... is
1, 5, 25, 149, 1081, 9365, 94585, 1091669, 14174521, 204495125,
3245265145, 56183135189, 1053716696761, 21282685940885,
460566381955705, 10631309363962709, 260741534058271801,
6771069326513690645
Expl generating fn: (exp(2x)-exp(x))/(2-exp(x)).
Formula as single not double sum:
   G(C) = sum(for k=0..C)of (-1)^(C-k) * k! * S(n, k) * (2^k-1)

Amazingly simply, it appears that
   G(C) = 2*F(C) - 1

so there really is only one counting problem here, not two problems.
The underlying reason for that is basically that the unranked
pseudolevel can be regarded as just another ranking level...

-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)
and
math.temple.edu/~wds/homepage/works.html