I'm considering making a more "self contained" animation for the original proof, it takes some time but might be worth it as well.

EDIT: No animations, I replaced the pics and text to make the answer more self contained. ]]>

Just for the record, the word-version, minus the parts that refer to the picture, seems to boil down to the following. Consider the pairs of the form (S,i) where S is a k-element subset of [n] and i is an element of [n]-S. One way to count such pairs says that there are (n choose k) options for S, each with n-k options for i, hence (n choose k)(n-k) pairs altogether. Another way to count the same pairs says that there are n options for i, each with ((n-1) choose k) options for S (namely all the k-element subsets of [n]-{i}), hence n((n-1) choose k) pairs altogether. Equating the two counts gives the desired formula.

Returning to the picture, its rows correspond to the various i's, and the off-diagonal squares in row i correspond to the elements of [n]-{i}. Unfortunately, the picture can depict only a single S, and that seems to make it difficult to see the relevance of the picture to the formula. ]]>

I just wrote the proof, using words:

This is a proof by induction in n. I took the base case and the n = k case for granted.

Now take k < n. (a set with k-elements is included in a set with n-1 elements, and I can apply induction)

The right hand side of the product at the hint means "number of ways to choose sets of k elements in a set of n-1 elements". Then it's multiplied by n and divided by n-k, giving the expected result, explanation for these two factors and the induction step follow:

As I want to prove it for n, I make n copies of the n-1 subsets for which I know how to apply the inductive hypothesis, and arrange each of them as rows in the nxn square, with the diagonal excluded.

The number of subsets of k elements is independent of where I choose to exclude that one element.

Now, given a subset of k < n elements in a set of n elements, it will appear in at least one of those copies of n-1 elements (the rows). In fact, it will appear n-k times, but no more because of the excluded diagonal.

In the example, k = 6 and n-k=2, the k-subset being the "clear-gray squares", which appear 2 times in the two marked rows, and which can't appear more times because of the black squares.

I hope with more pictures it still can be without-words (or with few words). I'll think about that, but I'm open to suggestions. ]]>

http://mathoverflow.net/questions/8846?sort=newest#sort-top

(Should be the newest answer these days, I don't know how to point to it directly)

First of all I'd like to know is understandable as it stands (if not, I'll add more words down here to review them, and edit my answer).

I'd also like to hear about improvements, and even if it applies at all for an answer to Mariano's "Proofs without words", as it might really need lots of new words (which I think, can be seen in the picture at least after you know what the proof is meant to be). ]]>