On Wed, Aug 26, 2009 at 11:09 AM, Gregory Maxwell<[email protected]> 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. _______________________________________________ foundation-l mailing list [email protected] Unsubscribe: https://lists.wikimedia.org/mailman/listinfo/foundation-l
