2 Counting Ill 1.2 Bit Sequences How many n-bit sequences contain exactly k ones? Each such sequence also contains n-k zeroes, so there are k!(m-k)! by the bookkeeper Rule 1.3 k-element Subsets of an n-element Set How many k-elements subsets of an n-element set are there? This question arises all the time in various guises In how many ways can I select 5 books from my collection of 100 to bring on vaca- How many different 13-card Bridge hands can be dealt from a 52-card deck? In how many ways can I select 5 toppings for my pizza if there are 14 available? There is a natural bijection between k-element subsets of an n-element set and n-bit sequences with exactly k ones. For example, here is a 3-element subset of (a1,t2 and the associated 8-bit sequence with exactly 3 ones (1,0,0,1,1,0,0.,0) Therefore, the answer to this problem is the same as the answer to the earlier question about bit sequences Rule 2 ( Subset Rule). The number of k-element subsets of an n-element set is k!(n-k)!一 The factorial expression in the Subset Rule comes up so often that there is a shorthand, ) This is read"n choose k"since it denotes the number of ways to choose k items from among n. We can immediately knock off all three questions above using the Sum Rule i can select 5 books from 100 in ways There are(13)different Bridge hands� � � � � � � � 2 Counting III 1.2 Bit Sequences How many n­bit sequences contain exactly k ones? Each such sequence also contains n − k zeroes, so there are n! k! (n − k)! by the Bookkeeper Rule. 1.3 k­element Subsets of an n­element Set How many k­elements subsets of an n­element set are there? This question arises all the time in various guises: • In how many ways can I select 5 books from my collection of 100 to bring on vaca￾tion? • How many different 13­card Bridge hands can be dealt from a 52­card deck? • In how many ways can I select 5 toppings for my pizza if there are 14 available? There is a natural bijection between k­element subsets of an n­element set and n­bit sequences with exactly k ones. For example, here is a 3­element subset of {x1, x2, . . . , x8} and the associated 8­bit sequence with exactly 3 ones: { x1, x4, x5 } ( 1, 0, 0, 1, 1, 0, 0, 0 ) Therefore, the answer to this problem is the same as the answer to the earlier question about bit sequences. Rule 2 (Subset Rule). The number of k­element subsets of an n­element set is: n! n = k! (n − k)! k The factorial expression in the Subset Rule comes up so often that there is a shorthand, . This is read “n choose k” since it denotes the number of ways to choose k items from among n. We can immediately knock off all three questions above using the Sum Rule: • I can select 5 books from 100 in 100 ways. 5 • There are 52 different Bridge hands. 13 n k