# [EM] Completion methods for Smith Sets

Buddha Buck bmbuck at 14850.com
Mon Jun 18 20:02:14 PDT 2001

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