A special case of Vandermonde’s identity

Waking up this morning, I was somehow reminded of this combinatorial identity that appeared on an exam in a “math problem solving” class I took, which I didn’t actually solve during the test because back then I was an idiot. It was

\displaystyle\binom{2n}{n} = \displaystyle\sum_{k=0}^n \binom{n}{k}^2.

Basically, it’s observing that \binom{n}{k}^2 = \binom{n}{k}\binom{n}{n-k} and then seeing that we have an instance of Vandermonde’s identity. The square is basically a form of obfuscation.

This stuff feels so obvious to me now yet it wasn’t back then. To make this entirely self-contained, I will prove Vandermonde’s identity as well for this specific case.

Let’s say we have n men and n women. How many ways are there to select n people among those 2n?

Easy. \displaystyle\binom{2n}{n}.

Or we can for every k from 0 to n, take the number of ways to pick k men (\binom{n}{k}) and then the number of ways to pick the k women to exclude (\binom{n}{k}) so that there are total of n people picked. This value is the one given by the right hand side of the identity.

There really is very little to this once you see how it works. But I guess the thought process behind this is unnatural for (most) humans to develop. It might take a while before one can visualize it accurately and clearly. Again, it would have been somewhat mind-boggling to the high school me.

Certainly this loads much more on math IQ than on verbal IQ, and testing has indicated I’m somewhat stronger at the former.

Math seems to have a strong either you can get it or you can’t component, being more exclusive. It seems a much higher percentage of people can do software engineering than this kind of math. I’ve seem plenty of good, reliable, hardworking software engineers who simply do not have the brain to grok this type of math. Those people tend to go to state schools whereas the ones who are good at computers and good at math are more likely to go to, say, MIT, but they may well eventually end up doing more or less the same type of software work. Plenty of MIT students who did well in math contests don’t go into quant finance but end up at big software/internet company or Dropbox and even though they seem much sexier (in terms of how they appear on paper overall, their being much smarter), at work, what they do is not much different. Experience has told me that software engineering is much more about being able to grind computer stuff (not minding it too much or even enjoying it, and in that regard, I’m not very high) than about IQ.

Advertisements