[EM] number of possible ranked ballots given N candidates

[Jobst Heitzig]

Dear Rob and Paul!

> 24 of the form A>B>C>D
> 12 of the form A=B>C>D
> 12 of the form A>B=C>D
> 12 of the form A>B>C=D
>  4 of the form A=B=C>D
>  4 of the form A=B>C=D
That latter must be 6
>  4 of the form A>B=C=D
>  1 of the form A=B=C=D

So it's 75 in total.

In general, Paul's formula is wrong. The number sought is known as the
ordered Bell numbers, see the following comprehensive reference:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000670

(you may have to try several times since the server seems to be weak today)

By the way, when the preferences are not required to be total, that is,
when voters can not only put candidates equal but also leave candidates
uncompared as in X>Z,Y>Z,X?Z, then the question becomes even more
complicated. For example, the number of such quasi-orders on  n
elements is surprisingly equal to the number of topologies with  n
points. That sequence can be found here:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000798

The online encyclopedia of integer sequences is a nice thing if one
loves numbers. For example, I found the above result by just entering
the first four numbers (1,3,13,75) in it's search form at
http://www.research.att.com/~njas/sequences/
Try entering 6,28,496,8128

Yours, Jobst


> 
> --
> Rob LeGrand, psephologist
> rob at approvalvoting.org
> Citizens for Approval Voting
> http://www.approvalvoting.org/
> 
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around 
> http://mail.yahoo.com 
> ----
> election-methods mailing list - see http://electorama.com/em for list info
>