News for hackers. Stuff that matters.
Re:What if P = NP? by wnoise on Friday April 01, 2011 @01:53PM (#2397228)
Pairings involve matching everybody. There are indeed O(n^2) (well n*(n-1)/2) ways of constructing the first match. But then the other n-2 people still need to be paired up.

The exact number is n!/((n/2)!(2^(n/2))). There are n! ways to order them. Pair each with his neighbor. The order of the pairs doesn't matter (divide by (n/2)!). The order within each pair doesn't matter (divide by 2^(n/2)).

Using Stirling's approximation, the log of this is about n log n - (n/2) log (n/2) - (n/2) log 2 = (n/2) log n. The exponential is then n^(n/2). 40^20 is rather large at 109 nonillion. Because we approximated the log, this significantly off. The right answer is 319 sextillion.

Re:What if P = NP? by 27182818284 on Saturday April 02, 2011 @10:55PM (#2401622)
Thanks for this! I was confused myself.

http://www.wolframalpha.com/input/?i=n%21%2F%28%28n%2F2%29%2...

seems to give 319830986772877770815625

It can also be done by thinking 39 * 37 * 35 * ... * 1 which also yields the same number. In that way, it is like selecting 1 person, who then has 39 people remaining, then selecting another, who has 37 left to choose from and so on.

I was super confused at first why it wasn't just 40 choose 2.

Re:What if P = NP? by efnx on Friday April 01, 2011 @01:58PM (#2397254)
I see, they're talking about the number of configurations of pairs, not the number of unique pairs themselves.