[EM] IRV ballot pile count (proof of closed form)

Thu Feb 4 16:51:53 PST 2010

People on this list seem to still be sending around their incorrect or
incomplete formulas for the number of possible rank orders for rank
order ballots.  This number BTW does *not* correspond to the number of
piles needed to count IRV which is a lesser number but does correspond
to the only method of making IRV precinct-summable.

The general formula for the number of possible rankings (for strict
ordering, without allowing equal rankings) for N candidates when
partial rankings are allowed and voters may rank up to R candidates
(N=R if voters are allowed to rank all candidates) on a ballot is
given on p. 6 of this doc:

http://electionmathematics.org/ucvAnalysis/US/RCV-IRV/InstantRunoffVotingFlaws.pdf

In the US, R=3 in most IRV elections.

Allowing equal rankings does of course greatly increase that number
and change the formula.  There are 15 possible ballot rankings for 3
candidates but as was pointed out on this list, some of the full
rankings of 3 candidates are equivalent to partial rankings of 2
candidates for the purposes of counting when voters are allowed to
rank only strictly.

The number of unique possible combinations when equal ranking is
allowed would be astronomical. I'm working on other issues currently
and don't have time (or interest) in deriving the formula at present.

I just note that none of the formulas I've seen here include the
necessary term for how many rankings are allowed to voters on a ballot
and assume that all N candidates may be ranked.

Kathy

> this all just started with my anal-retentive need to establish how many IRV piles one would have to maintain to have "precinct summability".  i am still convinced that for 3 candidates, the number is 9 (not 15) and for 4 candidates, you would need 40 piles (it *does* grow pretty rapidly).
>
> --
>
> r b-j                  rbj at audioimagination.com
>
> "Imagination is more important than knowledge."
>
>
>
>
> -----Original Message-----
> From: "Kristofer Munsterhjelm" [km-elmet at broadpark.no]
> Date: 02/03/2010 14:24
> To: "robert bristow-johnson" <rbj at audioimagination.com>
> CC: "election-methods List" <election-methods at electorama.com>
> Subject: Re: [EM] IRV ballot pile count (proof of closed form)
>
> robert bristow-johnson wrote:
>>
>> On Feb 2, 2010, at 2:28 PM, robert bristow-johnson wrote:
>>
>>>
>>> Warren tells me that
>>>
>>>     C-1
>>>     SUM{ C!/n! }
>>>     n=1
>>>
>>> has a closed form, but didn't tell me what it is.  does someone have
>>> the closed form for it?  i fiddled with it a little, and i can
>>> certainly see an asymptotic limit of
>>>
>>>     (e-1)(C!)
>>>
>>> as C gets large, but i don't see an exact closed form for it.  if
>>> someone has such a closed form, would you mind sharing it?
>>
>> Okay, I spent a little time working on this and figgered it out.  The
>> fact that the number of distinct piles needed to represent all possible
>> manners of *relatively* ranking C candidates (no ties except unranked
>> candidates are tied for lowest rank) is
>>
>>     C-1
>>     SUM{ C!/n! }  =  floor( (e-1) C! ) - 1
>>     n=1
>
> Now I wonder if there's a closed form for the number of orders with both
> equality and truncation permitted. Since I don't quite get the proof, I
> can't answer, though!
>
>
>
>
> ------------------------------
>
> Message: 2
> Date: Wed, 3 Feb 2010 16:31:35 -0500
> From: Warren Smith <warren.wds at gmail.com>
> To: election-methods <election-methods at electorama.com>
> Subject: [EM] counts of possible rank-order votes
> Message-ID:
>        <bb5343bc1002031331s2d6a3b9vd5f295791ec80aba at mail.gmail.com>
> Content-Type: text/plain; charset=ISO-8859-1
>
> 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
-- 

Kathy Dopp
http://electionmathematics.org
Town of Colonie, NY 12304
"One of the best ways to keep any conversation civil is to support the
discussion with true facts."

Realities Mar Instant Runoff Voting
http://electionmathematics.org/ucvAnalysis/US/RCV-IRV/InstantRunoffVotingFlaws.pdf

Voters Have Reason to Worry
http://utahcountvotes.org/UT/UtahCountVotes-ThadHall-Response.pdf

Checking election outcome accuracy
http://electionmathematics.org/em-audits/US/PEAuditSamplingMethods.pdf