On Wed, Aug 26, 2009 at 11:09 AM, Gregory Maxwellgmaxwell@gmail.com wrote:
Nitpicking, but the number of possible unique ballots is much greater than the factorial because of equality, and equality must be preserved in order produce the election calculations. The formula mostly easily represented is a messy multipart recursive formula, which I'll spare you (in part because I don't know that I have all the boundary conditions right). It's less than X!*2^(X-1).
I think it's the sum from k = 1 to n of S(n, k)*k!, where S(n, k) is a Stirling number of the second kind.
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
S(n, k) is the number of ways to divide an n-element set into k partitions. So there are S(n, k) ways to obtain k distinct "levels" of candidates after tying, and then there are k! different ways to order the levels against each other. Maxima gives the following results:
(%i3) sum(stirling2(18,k)*(k!), k, 1, 18); (%o3) 3385534663256845323 (%i4) 18!; (%o4) 6402373705728000
So it's about 529 times more than 18!. Admittedly, determining this was a completely pointless exercise, but it was kind of fun.