[EM] Completion methods for Smith Sets

[Buddha Buck]

LAYTON Craig <Craig.LAYTON at add.nsw.gov.au> writes:

> >The problem is that step C requires examining every ballot at least 
> >once.  If this is a public election, that could require examining and 
> >recounting possibly millions of ballots.  With large numbers of candidates,
> 
> >the number of possible rankings grows hyper-exponentially, and even 13 
> >candidates under consideration would yield more possible rankings than the 
> >population of the Earth.  There is no way to represent ranking data in the 
> >aggregate; re-examining the entire collection of ballots is the only way to
> go.
> 
> What is the formula for the number of possible ballots (assuming equal
> rankings are possible, as long as at least one rank distinction is made)?

I don't know -- it's a messy problem, and I'm not certain that there
is a concise formula.

Working under a different condition: assuming equal rankings are not
possible, and all candidates are ranked, it's easier:  N candidates
have N! rankings.  With 13 candidates, that's 6,227,020,800, which is
close to the current population.

Let's see...

If equal rankings are possible, we can look at it as a labelling
problem: equally-ranked candidates get equal labels, and then we just
sort the labels.

For N candidates, there are

N^N ways to affix up to N different labels.

Unfortunately, those N^N ways have lots of duplicates (N ways with
only 1 label, N(N-1)*(2^N-2) ways with exactly 2 labels, etc), all of
which have to be subtracted.

So, we have a lower bound of N!, and an upper bound of N^N.  Since
both N! and N^N are hyperexponential, I felt confident with my claims
;-).


> 
> Craig