The number of distinct piles of ranked ballots in Ranked-Choice Voting.

Question

This is about Ranked-Choice Voting (RCV) where the ballot has $C$ candidates, and there are $C$ levels of ranking of preference. Equal ranking of candidates is not allowed and no voter is required to rank any candidates that they don't want to, but any candidate not ranked is tied for lowest preference with all other unranked candidates on the ballot.

We want to know how many operationally distinct ways a ballot can be marked so that all like-marked ballots can go onto a single pile and handled as a block in the Single Transferable Vote operation that occurs in rounds in an RCV election. Besides the pile of blank ballots in which no candidates were ranked, how do we prove the number of piles is:

$$ \sum\limits_{n=1}^{C-1} \frac{C!}{n!} $$

Then using nothing more advanced than what we get from calculus, what would be a concise proof that:

$$ \sum\limits_{n=1}^{C-1} \frac{C!}{n!} = \big\lfloor (e-1)C! \big\rfloor - 1 $$

for all $C \in \mathbb{Z} \ge 2$ and $e$ is the base of the natural logarithm?

(I'm hoping for something more concise than what I got. If no one posts, I'll post my not-so-concise proof.)

Answer 1

Consider the ballots that operationally have $n$ unranked candidates; we’re ignoring the blank ballots, so $1\le n\le C-1$. The remaining $C-n$ candidates must, operationally speaking, occupy ranks $1$ through $C-n$. There are $\binom{C}{C-n}$ ways to choose these candidates and $(C-n)!$ ways to assign ranks to them, so there are

$$\binom{C}{C-n}(C-n)!=\frac{C!}{(C-n)!n!}(C-n)!=\frac{C!}{n!}$$

operationally distinct ballots with $n$ unranked candidates. Summing over the possible values of $n$, we get a total of $\sum_{n=1}^{C-1}\frac{C!}{n!}$ possibilities.

If a more elementary calculation is wanted, argue that there are $C$ choices of candidate for rank $1$, then $C-1$ choice for rank $2$, and so on, with $C-(k-1)$ choice for rank $C_k$. Thus, for ranks $1$ through $C-n$ there are

$$C(C-1)\ldots\big(C-(C-n-1)\big)=C(C-1)\ldots(n+1)=\frac{C!}{n!}$$

ways to pick $C-n$ candidates and rank them.

Granted, even this very basic counting doesn’t usually appear in calculus courses, but it really is very basic, and I see no way to avoid it altogether.

The Maclaurin series $e^x=\sum_{n\ge 0}\frac{x^n}{n!}$, however, does generally appear in calculus courses and gives us the approximation

$$e-1=\sum_{n\ge 1}\frac1{n!}$$

and hence

$$\sum_{n\ge 1}\frac{C!}{n!}=(e-1)C!\,.$$

Thus,

$$\begin{align*} (e-1)C!&=\sum_{n\ge 1}\frac{C!}{n!}\\ &=\sum_{n=1}^{C-1}\frac{C!}{n!}+\sum_{n\ge C}\frac{C!}{n!}\\ &=\sum_{n=1}^{C-1}\frac{C!}{n!}+1+\sum_{n\ge C+1}\frac{C!}{n!}\\ &=\sum_{n=1}^{C-1}\frac{C!}{n!}+1+\sum_{k\ge 1}\frac{C!}{(C+k)!}\,, \end{align*}$$

and the problem reduces to showing that

$$\sum_{k\ge 1}\frac{C!}{(C+k)!}<1\,.$$

And finally,

$$\frac{C!}{(C+k)!}=\prod_{i=1}^k\frac1{C+i}\le\prod_{i=1}^k\frac1{1+i}=\frac{1!}{(1+k)!}\,,$$

so

$$\sum_{k\ge 1}\frac{C!}{(C+k)!}\le\sum_{k\ge 1}\frac{1!}{(1+k)!}=\sum_{k\ge 2}\frac1{k!}=e-2<1\,.$$

Answer 2

Okay, I am on board with Dr. Scott's derivation. It depends on knowing that $e<3$, which is something my calculator says, dunno other than adding a few terms of the Maclauren series and showing that the remaining terms are small enough, I dunno a pure mathematical proof that $e<3$, but we know that it is.

We both have (of course):

$$\begin{align} (e-1)C! &= \sum\limits_{n=1}^{\infty} \frac{C!}{n!} \\ &= \sum\limits_{n=1}^{C-1} \frac{C!}{n!} + \frac{C!}{C!} + \sum\limits_{n=C+1}^{\infty} \frac{C!}{n!}\\ &= \sum\limits_{n=1}^{C-1} \frac{C!}{n!} + \ 1 \ \ \ + \sum\limits_{n=1}^{\infty} \frac{C!}{(C+n)!} \\ \end{align}$$

We know that any integer added to the argument of the floor() function can be taken out and added to what remains:

$$ \big\lfloor n + a \big\rfloor = n + \big\lfloor a \big\rfloor \qquad \forall n\in\mathbb{Z}, a\in\mathbb{R}$$

That means that

$$\begin{align} \big\lfloor (e-1)C! \big\rfloor &= \left\lfloor \sum\limits_{n=1}^{C-1} \frac{C!}{n!} + 1 + \sum\limits_{n=1}^{\infty} \frac{C!}{(C+n)!} \right\rfloor \\ &= \sum\limits_{n=1}^{C-1} \frac{C!}{n!} + 1 + \left\lfloor \sum\limits_{n=1}^{\infty} \frac{C!}{(C+n)!} \right\rfloor \\ \end{align}$$

because the first two terms are clearly integers.

The way I dealt with that inequality

$$\sum_{n=1}^{\infty} \frac{C!}{(C+n)!} < 1$$

is

$$\begin{align} \sum_{n=1}^{\infty} \frac{C!}{(C+n)!} &= \sum_{n=1}^{\infty} \ \prod_{k=1}^{n} \frac{1}{C+k} \\ &< \sum_{n=1}^{\infty} \ \prod_{k=1}^{n} \frac{1}{C} \\ &= \sum_{n=1}^{\infty} \ \frac{1}{C^n} \\ &= \sum_{n=0}^{\infty} \left( \tfrac1C \right)^n - 1 \\ &= \frac{1}{1-\tfrac1C} - 1 \\ &= \frac{C}{C-1} - 1 \\ &= \frac{1}{C-1} \qquad \le \ 1 \qquad \forall C \ge 2 \\ \end{align}$$

then that proves

$$ \sum\limits_{n=1}^{C-1} \frac{C!}{n!} = \big\lfloor (e-1)C! \big\rfloor - 1 $$

Number of operationally distinct piles grows proportional to $C!$ which is why we say that Hare RCV is not "precinct summable". Compare to First-Past-The-Post (FPTP) where the number of subtotals each voting precinct needs to report is $C$. Essentially most Condorcet methods would require $C(C-1)$ subtotals to report. Far less than $\big\lfloor (e-1)C! \big\rfloor - 1$ when $C>3$. I think it's valid to say that both Condorcet and FPTP are precinct summable and Hare RCV is not.