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.
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.