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 [email protected] > > "Imagination is more important than knowledge." > > > > > -----Original Message----- > From: "Kristofer Munsterhjelm" [[email protected]] > Date: 02/03/2010 14:24 > To: "robert bristow-johnson" <[email protected]> > CC: "election-methods List" <[email protected]> > 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 <[email protected]> > To: election-methods <[email protected]> > Subject: [EM] counts of possible rank-order votes > Message-ID: > <[email protected]> > 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 ---- Election-Methods mailing list - see http://electorama.com/em for list info
