Counting Subsets

1 .Counting Subsets

2 .Permutations How many arrangements of n = 52 cards? First card can be any of 52 Second card can be any of the remaining 51 … Once you have chosen 51 there is only one choice for the last So by the product rule, n ∙ (n-1) ∙ (n-2) ∙ … ∙ 2.1 = n !

3 .How Many 4-Letter Words Using Each Letter at Most Once? 26 choices for first letter Only 25 for second letter 24 for third letter 23 for fourth letter So 26∙25∙24∙23 or 26!/22!

4 .Generalized Product Rule Let Q be a set of length- k sequences if n 1 possible 1st elements, n 2 possible 2nd elements (for each first entry), n 3 possible 3rd elements (for each 1st & 2nd entry,...) then, |Q| = n 1 ⋅n 2 ⋅⋅⋅n k

5 .How Many Hands with 5 Cards? I.e., how many 5- element subsets of a set with 52 elements? We know there are 52! sequences of 52 cards. Each sequence uniquely identifies a set of 5 cards: the first 5 Many-to-one mapping from sequences of 52 cards to sets of 5 cards!

6 .map sequence a 1 a 2 a 3 a 4 …a 52 to set {a 1 ,a 2 ,a 3 , a 4 ,a 5 } How many different sequences map to the same set? Any way of permuting the first 5 elements maps to the same set (5! ways) For each of those, any way of permuting the last 47 elements maps to the same set

7 .Counting Subsets By the product rule, 5! ∙ 47! different sequences map to the same set Therefore the number of 5- element subsets of a set of 52 elements is The number of ways of picking 5 cards to include is the same as the number of ways of picking 47 cards to omit!

8 .“ n Choose m ” The number of m -element subsets of a set of size n is

9 .lec 10W. 9 Counting Doughnut Selections From 5 kinds of doughnuts select a dozen. let A ::= all selections of 12 doughnuts ( none) 3/22/12

10 . B ::= 16-bit words with four 1’s Counting Doughnut Selections 00 000000 00 00 1 1 1 1 0011000000100100 3/22/12 10 Bijection A↔B so |A|=|B|

11 .# of 16-bit-strings with 4 1’s = # of ways of choosing 4 from the set of possible positions {1, …, 16} = 3/22/12 11

12 .How Many Poker Hands (5 cards) with 2 Jacks? ways of picking three non-jacks ways of picking two jacks So by the product rule the number of hands with exactly 2 jacks is

13 .FINIS