Section 3.5

n elements, how many lists of length n (w/o repetition)? n! n elements, how many lists of length r (w/o repetition)? P(n,r) = n! / (n-r)!

1. Select element for pos 1 (n)

2. Select element for pos 2 (n-1)

3. Select element for pos 3 (n-2)

4. ...

5. Select element for pos r (n-(r-1))

   Multiplication rule says (n)(n-1)(n-2)...(n-(r-1)) outcomes = n! / (n-r)!

    

   n elements, how many SETS of length r?

   For each set of length r, there are r! lists that can be made from the elements.

   Ratio of (sets of size r) : (lists of size r) is 1 : r!

   C(n,r) = P(n,r) / r! = n! / ( r! (n-r)! )

2) Suppose A is a set for which |A| = 100. How many subsets of A have 5 elements? How many subsets have 10 elements? How many have 99 elements?

C(100,5) = 100! / (5! x 95!)

C(100,99) = 100! / (99! 1!) = 100

4) Suppose a set B has the property that $|\{X : X \in \mathscr{P}(B), |X|=6\}|=28$ Find |B|.􏰝􏰛􏰛 􏰜􏰜􏰝

What is the size of B if B has 28 subsets of size 6?

C(n,6) = 28

n! / (6! x (n-6)!) = 28 n=8

6) $|\{X \in \mathscr{P}(\{0,1,2,3,4,5,6,7,8,9\}) : |X|=4\}|$ = ?

C(10,4) = 10! / (4! x 6!)

8)􏰝􏰛􏰛 􏰜􏰜􏰝This problem concerns lists made from the symbols A, B, C, D, E, F, G, H, I. (a) How many length-5 lists can be made if there is no repetition and the list is in alphabetical order? (Example: BDEFI or ABCGH, but not BACGH.) (b) How many length-5 lists can be made if repetition is not allowed and the list is not in alphabetical order?

1. Select a set of five from ABCDEFGHI. (C(9,5))

2. List them in alphabetical order. (1)

   (b) P(9,5)

10) A department consists of 5 men and 7 women. From this department you select a committee with 3 men and 2 women. In how many ways can you do this?

1. Select set of 3 men on committee (C(5,3))
2. Select set 2 women on committee (C(7,2))

C(5,3) x C(7,2)