Counting Ill Christos, equally-famed 6.042 TA, thinks Ishan isnt so tough and so he might as well try out also. He reasons that n people (including himself)are trying out for k spots. Thus, the number of ways to select the team is simply Christos and ishan each correctly counted the number of possible boxing teams thus their answers must be equal. So we know: k This is called Pascal's Identity. And we proved it without any algebra! Instead, we relied urely on counting techniques 5.2 Combinatorial Proof A combinatorial proof is an argument that establishes an algebraic fact by relying on counting principles. Many such proofs follow the same basic outline 1. Define a set s 2. Show that S|=n by counting one way 3. Show that SI=m by counting another way. 4. Conclude that n= m In the preceding example, S was the set of all possible Olympic boxing teams computed IS=( k by counting one way, and Christos computed ISI counting another. equating these two expressions gave pascals identity More typically, the set S is defined in terms of simple sequences or sets rather than an elaborate story. Here is less-colorful example of a combinatorial argument Theorem 3 2n Proof. We give a combinatorial proof. Let s be all n-card hands that can be dealt from a deck containing n red cards(numbered 1,..., n)and 2n black cards(numbered 1,..., 2n) First, note that every 3n-element set has n� � � � � � � � � � � � � � � � 14 Counting III Christos, equally­famed 6.042 TA, thinks Ishan isn’t so tough and so he might as well try out also. He reasons that n people (including himself) are trying out for k spots. Thus, the number of ways to select the team is simply: n k Christos and Ishan each correctly counted the number of possible boxing teams; thus, their answers must be equal. So we know: n − 1 n − 1 n + = k − 1 k k This is called Pascal’s Identity. And we proved it without any algebra! Instead, we relied purely on counting techniques. 5.2 Combinatorial Proof A combinatorial proof is an argument that establishes an algebraic fact by relying on counting principles. Many such proofs follow the same basic outline: 1. Define a set S. 2. Show that |S| = n by counting one way. 3. Show that |S| = m by counting another way. 4. Conclude that n = m. In the preceding example, S was the set of all possible Olympic boxing teams. Ishan n computed |S| = n−1 + n−1 by counting one way, and Christos computed |S| = by k−1 k k counting another. Equating these two expressions gave Pascal’s Identity. More typically, the set S is defined in terms of simple sequences or sets rather than an elaborate story. Here is less­colorful example of a combinatorial argument. Theorem 3. �n � �� � � � n 2n 3n = r n − r n r=0 Proof. We give a combinatorial proof. Let S be all n­card hands that can be dealt from a deck containing n red cards (numbered 1, . . . , n) and 2n black cards (numbered 1, . . . , 2n). First, note that every 3n­element set has 3n | | S = n