#set document(title: "7.2 Permutations", author: "OpenStax / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 7.2#h(0.6em)Permutations #figure(figph[Three swimmers are racing in separate lanes in a swimming pool. The swimmer in the top lane is in first place, the swimmer in the bottom lane is in second place, and the swimmer in the middle lane is in third place.], alt: "Three swimmers are racing in separate lanes in a swimming pool. The swimmer in the top lane is in first place, the swimmer in the bottom lane is in second place, and the swimmer in the middle lane is in third place.", caption: [We can use permutations to calculate the number of different orders of finish in an Olympic swimming heat.]) === Learning Objectives After completing this section, you should be able to: + Use the Multiplication Rule for Counting to determine the number of permutations. + Compute expressions containing factorials. + Compute permutations. + Apply permutations to solve problems. Swimming events are some of the most popular events at the summer Olympic Games. In the finals of each event, 8 swimmers compete at the same time, making for some exciting finishes. How many different orders of finish are possible in these events? In this section, we’ll extend the Multiplication Rule for Counting to help answer questions like this one, which relate to #strong[permutations]. A permutation is an ordered list of objects taken from a given population. The length of the list is given, and the list cannot contain any repeated items. === Applying the Multiplication Rule for Counting to Permutations In the case of the swimming finals, one possible permutation of length 3 would be the list of medal winners (first, second, and third place finishers). A permutation of length 8 would be the full order of finish (first place through eighth place). Let’s use the Multiplication Rule for Counting to figure out how many of each of these permutations there are. #examplebox("Example 1")[Using the Multiplication Rule for Counting to Find the Number of Permutations][ The final heat of Olympic swimming events features 8 swimmers (or teams of swimmers). + How many different podium placements (first place, second place, and third place) are possible? + How many different complete orders of finish (first place through eighth place) are possible? #solutionbox[ + Let’s start with the first place finisher. How many options are there? Since 8 swimmers are competing, there are 8 possibilities. Once that first swimmer completes the race, there are 7 swimmers left competing for second place. After the second finisher is decided, there are 6 swimmers remaining who could possibly finish in third place. Thus, there are 8 possibilities for first place, 7 for second place, and 6 for third place. The Multiplication Rule for Counting then tells us there are #math.equation(block: false, alt: "8 times 7 times 6 equals 336")[$8 × 7 × 6 = 336$] different ways the winners’ podium can be filled out. + To look at the complete order of finish, we can continue the pattern we can see in part 1 of this example: There are 5 possibilities for fourth place, 4 for fifth place, 3 for sixth place, 2 for seventh place, and then just 1 swimmer is left to finish in eighth place. Using the Multiplication Rule for Counting, we see that there are #math.equation(block: false, alt: "8 times 7 times 6 times 5 times 4 times 3 times 2 times 1 equals 40 , 320")[$8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40 , 320$] possible orders of finish. ] ] === Factorials The pattern we see in Example 1 occurs commonly enough that we have a name for it: #strong[factorial]. #linebreak() For any positive whole number #math.equation(block: false, alt: "n")[$n$], we define the factorial of #math.equation(block: false, alt: "n")[$n$] (denoted #math.equation(block: false, alt: "n !")[$n !$] and read "#math.equation(block: false, alt: "n")[$n$] factorial") to be the product of every whole number less than or equal to #math.equation(block: false, alt: "n")[$n$]. We also define 0! to be equal to one. We will use factorials in a couple of different contexts, so let's get some practice doing computations with them. #examplebox("Example 2")[Computing Factorials][ Compute the following: + #math.equation(block: false, alt: "4 !")[$4 !$] + #math.equation(block: false, alt: "the fraction 8 ! over 6 !")[$frac(8 !, 6 !)$] + #math.equation(block: false, alt: "the fraction 9 ! over 3 ! 4 !")[$frac(9 !, 3 ! 4 !)$] #solutionbox[ + #math.equation(block: false, alt: "4 ! equals 4 times 3 times 2 times 1 equals 24")[$4 ! = 4 × "3" × "2" × 1 = 24$] + There are two ways to approach this calculation. The first way is to compute the factorials first, then divide: #math.equation(block: true, alt: "the fraction 8 ! over 6 ! equals the fraction 8 times 7 times 6 times 5 times 4 times 3 times 2 times 1 over 6 times 5 times 4 times 3 times 2 times 1 equals the fraction 40,320 over 720 equals 56")[$frac(8 !, 6 !) = frac(8 × 7 × 6 × 5 × 4 × 3 × 2 × 1, 6 × 5 × 4 × 3 × 2 × 1) = frac(40","320, 720) = 56$]However, there is an easier way! You may notice in the second step that there are several terms that can be canceled; that’s always the case whenever we divide factorials. In this case, notice that we can rewrite the numerator like this: #math.equation(block: true, alt: "8 ! equals 8 times 7 times open parenthesis 6 times 5 times 4 times 3 times 2 times 1 close parenthesis equals 8 times 7 times 6 !")[$8 ! = 8 × 7 × ( 6 × 5 × 4 × 3 × 2 × 1 ) = 8 × 7 × 6 !$]With that in mind, we can proceed this way by canceling out the 6!: #math.equation(block: true, alt: "the fraction 8 ! over 6 ! equals the fraction 8 times 7 times 6 ! over 6 ! equals 8 times 7 equals 56")[$frac(8 !, 6 !) = frac(8 × 7 × 6 !, 6 !) = 8 × 7 = 56$]That’s much easier! + Let’s approach this one using our canceling technique. When we see two factorials in either the numerator or denominator, we should focus on the larger one first. So: #math.equation(block: true, alt: "the fraction 9 ! over 3 ! 4 ! equals the fraction 9 times 8 times 7 times 6 times 5 times 4 ! over 3 ! 4 ! equals the fraction 9 times 8 times 7 times 6 times 5 over 3 times 2 times 1 equals 9 times 8 times 7 times 5 equals 2,520")[$frac(9 !, 3 ! 4 !) = frac(9 × 8 × 7 × 6 × 5 × 4 !, 3 ! 4 !) = frac(9 × 8 × 7 × 6 × 5, 3 × 2 × 1) = 9 × 8 × 7 × 5 = 2,520$] ] ] === Permutations As we’ve seen, factorials can pop up when we’re computing permutations. In fact, there is a formula that we can use to make that connection explicit. Let’s define some notation first. If we have a collection of #math.equation(block: false, alt: "n")[$n$] objects and we wish to create an ordered list of #math.equation(block: false, alt: "r")[$r$] of the objects (where #math.equation(block: false, alt: "1 less than or equal to r less than or equal to n")[$1 ≤ r ≤ n$]), we’ll call the number of those permutations #math.equation(block: false, alt: "sub n P sub r")[$n P_(r)$] (read “the number of permutations of #math.equation(block: false, alt: "n")[$n$] objects taken #math.equation(block: false, alt: "r")[$r$] at a time”). We formalize the formula we'll use to compute permutations below. #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[ #math.equation(block: true, alt: "sub n P sub r equals the fraction n ! over open parenthesis n minus r close parenthesis !")[$n P_(r) = frac(n !, ( n − r ) !)$] ] If you wondered why we defined #math.equation(block: false, alt: "0 ! equals 1")[$0 ! = 1$] earlier, it was to make formulas like this one work; if we have #math.equation(block: false, alt: "n")[$n$] objects and want to order all of them (so, we want the number of permutations of #math.equation(block: false, alt: "n")[$n$] objects taken #math.equation(block: false, alt: "n")[$n$] at a time), we get #math.equation(block: false, alt: "sub n P sub n equals the fraction n ! over open parenthesis n minus n close parenthesis ! equals the fraction n ! over 0 ! equals the fraction n ! over 1 equals n !")[$n P_(n) = frac(n !, ( n − n ) !) = frac(n !, 0 !) = frac(n !, 1) = n !$]. Next, we’ll get some practice computing these permutations. #examplebox("Example 3")[Computing Permutations][ Find the following numbers: + The number of permutations of 12 objects taken 3 at a time + The number of permutations of 8 objects taken 5 at a time + The number of permutations of 32 objects taken 2 at a time #solutionbox[ + #math.equation(block: true, alt: "sub 12 P sub 3 equals the fraction 12 ! over open parenthesis 12 minus 3 close parenthesis ! equals the fraction 12 ! over 9 ! equals the fraction 12 times 11 times 10 times 9 ! over 9 ! equals 12 times 11 times 10 equals 1,320")[$12 P_(3) = frac(12 !, ( 12 − 3 ) !) = frac(12 !, 9 !) = frac(12 × 11 × 10 × 9 !, 9 !) = 12 × 11 × 10 = 1,320$] + #math.equation(block: true, alt: "sub 8 P sub 5 equals the fraction 8 ! over open parenthesis 8 minus 5 close parenthesis ! equals the fraction 8 times 7 times 6 times 5 times 4 times 3 ! over 3 ! equals 8 times 7 times 6 times 5 times 4 equals 6,720")[$8 P_(5) = frac(8 !, ( 8 − 5 ) !) = frac(8 × 7 × 6 × 5 × 4 × 3 !, 3 !) = 8 × 7 × 6 × 5 × 4 = 6,720$] + #math.equation(block: true, alt: "sub 32 P sub 2 equals the fraction 32 ! over open parenthesis 32 minus 2 close parenthesis ! equals the fraction 32 times 31 times 30 ! over 30 ! equals 32 times 31 equals 992")[$32 P_(2) = frac(32 !, ( 32 − 2 ) !) = frac(32 × 31 × 30 !, 30 !) = 32 × 31 = 992$] ] ] #examplebox("Example 4")[Applying Permutations][ + A high school graduating class has 312 students. The top student is declared valedictorian, and the second-best is named salutatorian. How many possible outcomes are there for the valedictorian and salutatorian? + In the card game blackjack, the dealer’s hand of 2 cards is dealt with 1 card faceup and 1 card facedown. If the game is being played with a single deck of (52) cards, how many possible hands could the dealer get? + The University Combinatorics Club has 3 officers: president, vice president, and treasurer. If there are 18 members of the club, how many ways are there to fill the officer positions? #solutionbox[ + This is the number of permutations of 312 students taken 2 at a time, and #math.equation(block: false, alt: "sub 312 P sub 2 equals 97,032")[$312 P_(2) = 97,032$]. + We want the number of permutations of 52 cards taken 2 at a time, and #math.equation(block: false, alt: "sub 52 P sub 2 equals 2,652")[$52 P_(2) = 2,652$]. + Here we’re looking for the number of permutations of 18 members taken 3 at a time, and #math.equation(block: false, alt: "sub 18 P sub 3 equals 4,896")[$18 P_(3) = 4,896$]. ] ] #notebox("Who Knew?", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[ #emph[Very Big Permutations] Permutations involving relatively small sets of objects can get very big, very quickly. A standard deck contains 52 cards. So, the number of different ways to shuffle the cards—in other words, the number of permutations of 52 objects taken 52 at a time—is #math.equation(block: false, alt: "52 ! approximately equals 8 times 10 to the power 67")[$52 ! ≈ 8 × 10^(67)$] (written out, that’s an 8 followed by 67 zeroes). The estimated age of the universe is #emph[only] about #math.equation(block: false, alt: "4 times 10 to the power 17")[$4 × 10^(17)$] seconds. So, if a very bored all-powerful being started shuffling cards at the instant the universe began, it would have to have averaged at least #math.equation(block: false, alt: "the fraction 8 times 10 to the power 67 over 4 times 10 to the power 17 approximately equals 2 times 10 to the power 50")[$frac(8 × 10^(67), 4 × 10^(17)) ≈ 2 × 10^(50)$] shuffles #emph[per second since the beginning of time] to have covered every possible arrangement of a deck of cards. That means the next time you pick up a deck of cards and give it a good shuffle, it’s almost certain that the particular arrangement you created has never been created before and likely never will be created again. ] === Key Terms - permutation - factorial === Key Concepts - Using the Multiplication Rule for Counting to enumerate permutations. - Simplifying and computing expressions involving factorials. - Using factorials to count permutations. === Formulas - #math.equation(block: false, alt: "P n sub r equals the fraction n ! over open parenthesis n minus r close parenthesis !")[$attach(P, bl: n) r = frac(n !, ( n − r ) !)$]