Counting Il 5 Combinatorial Proof Suppose you have n different T-shirts only want to keep k. You could equally well select the k shirts you want to keep or select the complementary set of n-k shirts you want to throw out. Thus, the number of ways to select k shirts from among n must be equal to th number of ways to select n- k shirts from among n. Therefore This is easy to prove algebraically, since both sides are equal to k!(n-k) But we didnt really have to resort to algebra; we just used counting principles mn 5.1 Boxing Ishan, famed 6.042 TA, has decided to try out for the US Olympic boxing team. After all, he's watched all of the Rocky movies and spent hours in front of a mirror sneering, Yo, you wanna piece a' me? Ishan figures that n people(including himself)are competing for spots on the team and only k will be selected. As part of maneuvering for a spot on the team, he need to work out how many different teams are possible. There are two cases to consider. Ishan is selected for the team, and his k- 1 teammates are selected from among the other n-1 competitors. The number of different teams that be formed in this way k Ishan is not selected for the team, and all k team members are selected from among the other n-1 competitors. The number of teams that can be formed this way is: k All teams of the first type contain Ishan, and no team of the second type does; therefore, the two sets of teams are disjoint. Thus, by the Sum Rule, the total number of possible Olympic boxing teams is k� � � � � � � � � � Counting III 13 5 Combinatorial Proof Suppose you have n different T­shirts only want to keep k. You could equally well select the k shirts you want to keep or select the complementary set of n − k shirts you want to throw out. Thus, the number of ways to select k shirts from among n must be equal to the number of ways to select n − k shirts from among n. Therefore: n n = k n − k This is easy to prove algebraically, since both sides are equal to: n! k! (n − k)! But we didn’t really have to resort to algebra; we just used counting principles. Hmm. 5.1 Boxing Ishan, famed 6.042 TA, has decided to try out for the US Olympic boxing team. After all, he’s watched all of the Rocky movies and spent hours in front of a mirror sneering, “Yo, you wanna piece a’ me?!” Ishan figures that n people (including himself) are competing for spots on the team and only k will be selected. As part of maneuvering for a spot on the team, he need to work out how many different teams are possible. There are two cases to consider: • Ishan is selected for the team, and his k − 1 teammates are selected from among the other n − 1 competitors. The number of different teams that be formed in this way is: � � n − 1 k − 1 • Ishan is not selected for the team, and all k team members are selected from among the other n − 1 competitors. The number of teams that can be formed this way is: n − 1 k All teams of the first type contain Ishan, and no team of the second type does; therefore, the two sets of teams are disjoint. Thus, by the Sum Rule, the total number of possible Olympic boxing teams is: n − 1 n − 1 + k − 1 k