<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.2900.2769" name=GENERATOR></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=025183520-14122005><FONT face=Arial
color=#0000ff size=2>The number of full ranked ballots is just the number of
permutations of N alternatives = N!</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=025183520-14122005><FONT face=Arial
color=#0000ff size=2></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=025183520-14122005><FONT face=Arial
color=#0000ff size=2>If equal ranknigs are allowed, it's N! + 2^N -
1</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=025183520-14122005><FONT face=Arial
color=#0000ff size=2> </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=025183520-14122005><FONT face=Arial
color=#0000ff size=2>If truncation is allowed it is approximately N! *
e</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=025183520-14122005><FONT face=Arial
color=#0000ff size=2> </FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=025183520-14122005><FONT face=Arial
color=#0000ff size=2>And if both truncation AND equal rankings are allowed it's
approximately N! * e + 2^N - 1</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=025183520-14122005><FONT face=Arial
color=#0000ff size=2></FONT></SPAN> </DIV><BR>
<BLOCKQUOTE
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> election-methods-bounces@electorama.com
[mailto:election-methods-bounces@electorama.com] <B>On Behalf Of </B>rob
brown<BR><B>Sent:</B> Wednesday, December 14, 2005 2:30 PM<BR><B>To:</B>
Election Methods Mailing List<BR><B>Subject:</B> [EM] number of possible
ranked ballots given N candidates<BR></FONT><BR></DIV>
<DIV></DIV>Condorcet voting methods typically preprocess ballots into a
pairwise matrix, which is convenient because the tabulation methods have a
significantly reduced set of "input data" vs. having to process all individual
ballots. This is particularly convenient if we wish to allow the "2nd
stage" of tabulation to happen on the client, such as in javascript on a web
page (for instance, I have been building a javascript vote tabulator which, if
provided with a matrix, can do the processing client side: <A
href="http://www.karmatics.com/voting/testharness.html">http://www.karmatics.com/voting/testharness.html</A>
). If we have to process all ballots, this could be inconvenient because
all ballots must now be delivered to the client, which could be bulky if their
are a large number of voters. In other words, the quantity of input data
of a matrix is determined by the number of candidates, while ballot data is
determined by the number of voters. <BR><BR>Unfortunately, as Paul K has
pointed out, the pairwise matrix is "lossy", as you can never retrieve the
actual ballots from it. Whether the voting method itself actually uses
this data or not, people who want to see how everyone actually voted, and
possibly do various statistical analysis on it, are limited in what they can
do because they cannot see all the data. <BR><BR>Since I am now exploring
methods that rely directly on ballot data, rather than on the matrix, I
especially interested in finding a convenient non-lossy way to compress the
ballot data. This compression will not only make it convenient to pass
the data around (such as delivering it to a client side javascript
application), it can also potentially make it much more efficient to batch
process. <BR><BR>So lets say I have the following ballot
data:<BR><BR>A>B>C=D<BR>A>C=D>B<BR>D>B<BR>A>B>C=D<BR>D>B<BR><BR>Since
there are two pairs of identical ballots, this can obviously be compressed
into <BR><BR>2: A>B>C=D<BR>1: A>C=D>B<BR>2: D>B<BR><BR>As the
number of ballots becomes large (say, in the thousands or tens of thousands),
this becomes quite significant. Given N candidates, there is a fixed
number of possible unique ballots, capping the quantity of data. It will
still be more data than the pairwise matrix, but far less than having to store
each ballot as a separate piece of data. <BR><BR>My question is, what is this
number? I'm sure I could work it out but I'm sure someone has already
done it....<BR><BR>Thanks,<BR>-rob<BR><BR></BLOCKQUOTE></BODY></HTML>