7.4Permutations and Combinations - Washington State …

1 Permutations and CombinationsThe multiplication principle discussed in the preceding section can beused to develop two additional counting devices that are extremelyuseful in more complicated counting problems. Both of these using the multiplication principle, we encountered expressionssuch as26 25 24or8 7 6where each natural number factor is decreased by 1 as we move fromleft to right. The factors in the following product continue to decreaseby 1 until a factor of 1 is reached:5 4 3 2 1 Products like this are encountered so frequently in counting problemsthat it is useful to express them in a concise notation. The product ofthe first n natural numbers is callednfactorialand is denoted byn!. Also, we definezero factorial, 0!

2 , to be (Factorial)For a natural numbern,n! =n (n 1) (n 2) .. 2 1or, equivalently,n! =n (n 1)!,provided0! = 7. Sets and CountingExample 1 Compute:(a) 1!(b) 6!(c)10!9!(d)10!7!(e)5!0!3!(f)20!3!17!Pe rmutationsDefinition (Permutation of a Set)Given a setS, apermutationofS, is an arrangement of theelements ofSin a specific order without :Recall that setSitself cannot have repeated elements. Aset in which some elements are repeated is called :Two permutations of the same set are distinct if order ofelements in these permutations is :The textbook uses the term permutations ofndistinctobjects without repetition which is essentially the same as per-mutations of a setSof sizen(S) =n .2Ch 7. Sets and CountingFor example, given setS={a, b, c, d, e},Question:How would we count all possible permutations of a givenset?

3 ConsiderS={a, b, c, d, e}.Theorem 1 (Number of Permutations of a Set)The number of permutations of setSof sizen(S) =n, denotedbyPn n, isPn n=n (n 1) .. 2 1 =n!3Ch 7. Sets and CountingConsiderS={a, b, c, d, e}. Suppose that we want to construct or-dered arrangements (sequences) of length 3 using elements fromS, ,Definition (r-permutation of a Set)Given a setSof sizen(S) =n, anr-permutation(r n) ofSis an arrangement ofrelements ofSin a specific order :The textbook uses the term permutation ofnobjectstakenrat a time which is essentially the same :How would we count all possibler-permutations of a givenset?ConsiderS={a, b, c, d, e}. Suppose that we want to count all orderedarrangements (sequences) of length 3 using elements 7.

4 Sets and CountingTheorem 2 (Number ofr-permutations of a Set)The number ofr-permutations of setSof sizen(S) =n, denotedbyPn r, isPn r=n!(n r)!=n (n 1) (n 2) .. (n r+ 1).Note: Pn n=n!(n n)!=n!0!=n!1=n! is the number ofn-permutations of 2 Given a set{A, B, C, D}how many permutations are possible forthis set of 4 objects taken 2 at a time? Answer the question(a) Using a tree diagram(b) Using the multiplication principle(c) Using the two formulas forPn r5Ch 7. Sets and CountingExample 3In how many ways can 3 people sit in a row of 7 chairs?Example 4 Find the number of permutations of 30 objects taken 4 at a the answer using a 7. Sets and CountingCombinationsConsiderS={a, b, c}. Suppose that we want to construct sets (sub-sets ofS) using 2 letters fromS, wherewe do not care about theorderof letters in the resulting sets, ,Definition (r-combination of a Set)Given a setSof sizen(S) =n, anr-combination(r n) ofSis a subset ofkdistinct elements of S (no repetition of elementsallowed).

5 Note:The arrangement (order) of the elements in the subset doesnot matter. That is, twor- Combinations are assumed to be thesame if they composed of the same :The textbook uses the term combination ofnobjectstakenrat a time which is essentially the same :How would we count all possibler- Combinations of a givenset?ConsiderS={a, b, c}again. Let s construct all possible 7. Sets and Counting8Ch 7. Sets and CountingTheorem 3 (Number ofr- Combinations of a Set)The number ofr- Combinations of setSof sizen(S) =n, denotedbyCn r, isCn r=(nr)=Pn rr!=n!r!(n r)!.Example 5 From a committee of 12 people,(a) In how many ways can we choose a chairperson , a vice - chairperson , a secretary, and a treasurer, assuming that oneperson cannot hold more than one position?

6 (b) In how many ways can we choose a subcommittee of 4 people?9