6 ms·
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
by wnoise 16y ago
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.
- efnx 16y agoI see, they're talking about the number of configurations of pairs, not the number of unique pairs themselves.
- 27182818284 16y agoThanks for this! I was confused myself. http://www.wolframalpha.com/input/?i=n%21%2F%28%28n%2F2%29%21%282^%28n%2F2%29%29%29%2C+n%3D40 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.