From the beginning of the article:
"We know which students are compatible with each other and we want to put them in compatible groups of two. We could search all possible pairings but even for 40 students we would have more than 300 billion trillion possible pairings."
Can someone explain why there are 300 billion trillion pairings instead of 40^2 pairings - 40 repeat pairings - incompatible pairings ?
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.
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.
Can someone explain why there are 300 billion trillion pairings instead of 40^2 pairings - 40 repeat pairings - incompatible pairings ?