“It’s one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.”
“It’s one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.”
I was scanning that article, and came across what looks to me as a glaring error.
The article states: “Suppose we have a large group of students that we need to pair up to work on projects. 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.”
Huh? Where in the world did he get that number? By my calculation the number of possible pairings is 40C2 which is 780. Much less than the 300 billion trillion he’s claiming.
I’m not sure what the “C2” part of your answer refers to, and I’m definitely no math whiz, but I assumed he’s using factorials somehow. That’s the construct I use for figuring out the number of combinations for something, and it does build up extremely fast.
xCy is notation denoting the calculation of combinations, in other words, the number of ways to choose y items from a total set of x items, where order is not important. A good online article explaining the math can be found at http://www.mathsisfun.com/combinatorics/combinations-permutations.html.
Basically, to find out how many ways there are to choose two students out of a set of 40, you take:
40!
(40-2)!2!
= 40*39/2
= 780 (I hope the formatting comes out well on that)
Another way of looking at this is, if you’re choosing two students, there’s forty ways to choose the first student and then 39 ways to choose the second. The total number of ways of choosing two students then is 40*39, and since pairing Jimmy with Sally is exactly the same as pairing Sally with Jimmy, you can divide that result by two to eliminate the repeating pairs.
Now, say you were trying to organize those 40 students into two groups of 20, then the calculation would be 40!/((40-20)!20!) which is 137,846,528,820. It’s a big number, but still well shy of his purported 300 billion trillion.
That first calculation is supposed to have dashes between the 40! and the (40-2)!2!. Here’s what it should look like on one line:
40!/((40-2)!2!)
I’m not sure I understand your equations (my blog software probably messed with the formatting, which doesn’t help), but if I follow it, that only accounts for the selection of the first pair. I think you need to multiply it by the selection of the other pairs (second, third, etcetera) to get the number that the article is talking about.