Not signed in (Sign In)

Vanilla 1.1.9 is a product of Lussumo. More Information: Documentation, Community Support.

Community: Proofs without words

Bottom of Page

1 to 6 of 6

  1.  
    • CommentAuthorroberto
    • CommentTimeFeb 14th 2012 edited
     
    I re-uploaded my answer as it was before I deleted it (after a comment (which was unrelated but I think applies to my answer), and an unexplained down-vote):

    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).
  2.  
    Maybe the proof is understandable for some people, but I don't understand it. (I did not cast the down-vote on the previous posting of the same proof, so I suppose I'm not the only one who doesn't understand.)
    • CommentAuthorMariano
    • CommentTimeFeb 14th 2012
     

    Roberto, this has been discussed before: there is no rule that downvotes have to be explained, just as upvoted need not be explained. In any case, a downvote does not mean the answer should be deleted—only, in this particular question, that someone does not like your answer. I, for one, don't understand it, so I am at a stage before liking or not liking...

    • CommentAuthorroberto
    • CommentTimeFeb 14th 2012
     
    Point taken.

    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.
  5.  
    Roberto, the word-version of the argument is easy to understand, but I'm not convinced that the picture adds much to the clarity.

    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.
    • CommentAuthorroberto
    • CommentTimeFeb 15th 2012 edited
     
    The word-version boils down to your second way of counting, and then considering repetitions (thus dividing by n-k). Your version takes a cartesian product at both sides of the equation, which is mathematically cleaner, but I (maybe it's just me) find it harder to depict.

    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.

1 to 6 of 6

  1.  
Back to Discussions Top of Page