Counting Subsets

本章主讲Counting Subsets的基本概念及运用。举例说明了排列的概念,引出了广义乘积法则的运用。通过实例和例题来讨论了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