#set document(title: "5.5 Permutations and Combinations", author: "OpenStax") #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")) == 5.5#h(0.6em)Permutations and Combinations #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Prerequisites] none #linebreak() #linebreak() ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Learning Objectives] + Calculate the probability of two independent events occurring + Define permutations and combinations + List all permutations and combinations + Apply formulas for permutations and combinations ] This section covers basic formulas for determining the number of various possible types of outcomes. The topics covered are: (1) counting the number of possible orders, (2) counting using the multiplication rule, (3) counting the number of permutations, and (4) counting the number of combinations. === Possible Orders Suppose you had a plate with three pieces of candy on it: one green, one yellow, and one red. You are going to pick up these three pieces one at a time. The question is: In how many different orders can you pick up the pieces? Table 1 lists all the possible orders. There are two orders in which red is first: red, yellow, green and red, green, yellow. Similarly, there are two orders in which yellow is first and two orders in which green is first. This makes six possible orders in which the pieces can be picked up. Table 1. Six Possible Orders. #figure(table( columns: 4, align: left, inset: 6pt, table.header([Number], [First], [Second], [Third]), [1], [red], [yellow], [green], [2], [red], [green], [yellow], [3], [yellow], [red], [green], [4], [yellow], [green], [red], [5], [green], [red], [yellow], [6], [green], [yellow], [red], )) The formula for the number of orders is shown below. Number of orders = n! where n is the number of pieces to be picked up. The symbol "!" stands for factorial. Some examples are: 3! = 3 x 2 x 1 = 6 #linebreak() 4! = 4 x 3 x 2 x 1 = 24 #linebreak() 5! = 5 x 4 x 3 x 2 x 1 = 120 This means that if there were 5 pieces of candy to be picked up, they could be picked up in any of 5! = 120 orders. === Multiplication Rule Imagine a small restaurant whose menu has 3 soups, 6 entrées, and 4 desserts. How many possible meals are there? The answer is calculated by multiplying the numbers to get 3 x 6 x 4 = 72. You can think of it as first there is a choice among 3 soups. Then, for #emph[each] of these choices there is a choice among 6 entrées resulting in 3 x 6 = 18 possibilities. Then, for each of these 18 possibilities there are 4 possible desserts yielding 18 x 4 = 72 total possibilities. === Permutations Suppose that there were four pieces of candy (red, yellow, green, and brown) and you were only going to pick up exactly two pieces. How many ways are there of picking up two pieces? Table 2 lists all the possibilities. The first choice can be any of the four colors. For each of these 4 first choices there are 3 second choices. Therefore there are 4 x 3 = 12 possibilities. Table 2. Twelve Possible Orders. #figure(table( columns: 3, align: left, inset: 6pt, table.header([Number], [First], [Second]), [1], [red], [yellow], [2], [red], [green], [3], [red], [brown], [4], [yellow], [red], [5], [yellow], [green], [6], [yellow], [brown], [7], [green], [red], [8], [green], [yellow], [9], [green], [brown], [10], [brown], [red], [11], [brown], [yellow], [12], [brown], [green], )) More formally, this question is asking for the number of permutations of four things taken two at a time. The general formula is: #math.equation(block: true, alt: "n P sub r equals the fraction n ! over open parenthesis n minus r close parenthesis !")[$n P_(r) = frac(n !, ( n − r ) !)$] where #sub[n]P#sub[r] is the number of permutations of n things taken r at a time. In other words, it is the number of ways r things can be selected from a group of n things. In this case, #math.equation(block: true, alt: "4 P sub 2 equals the fraction 4 ! over open parenthesis 4 minus 2 close parenthesis ! equals the fraction 4 times 3 times 2 times 1 over 2 times 1 equals 12")[$4 P_(2) = frac(4 !, ( 4 − 2 ) !) = frac(4 × 3 × 2 × 1, 2 × 1) = 12$] It is important to note that order counts in permutations. That is, choosing red and then yellow is counted separately from choosing yellow and then red. Therefore permutations refer to the number of ways of choosing rather than the number of possible outcomes. When order of choice is not considered, the formula for combinations is used. === Combinations Now suppose that you were not concerned with the way the pieces of candy were chosen but only in the final choices. In other words, how many different combinations of two pieces could you end up with? In counting combinations, choosing red and then yellow is the same as choosing yellow and then red because in both cases you end up with one red piece and one yellow piece. Unlike permutations, order does not count. Table 3 is based on Table 2 but is modified so that repeated combinations are given an "x" instead of a number. For example, "yellow then red" has an "x" because the combination of red and yellow was already included as choice number 1. As you can see, there are six combinations of the three colors. Table 3. Six Combinations. #figure(table( columns: 3, align: left, inset: 6pt, table.header([Number], [First], [Second]), [1], [red], [yellow], [2], [red], [green], [3], [red], [brown], [x], [yellow], [red], [4], [yellow], [green], [5], [yellow], [brown], [x], [green], [red], [x], [green], [yellow], [6], [green], [brown], [x], [brown], [red], [x], [brown], [yellow], [x], [brown], [green], )) where #sub[n]C#sub[r] is the number of combinations for n things taken r at a time. #math.equation(block: true, alt: "n C sub r equals the fraction n ! over open parenthesis n minus r close parenthesis ! r !")[$n C_(r) = frac(n !, ( n − r ) ! #h(0.167em) r !)$] For our example, #math.equation(block: true, alt: "4 C sub 2 equals the fraction 4 ! over open parenthesis 4 minus 2 close parenthesis ! 2 ! equals the fraction 4 times 3 times 2 times 1 over open parenthesis 2 times 1 close parenthesis open parenthesis 2 times 1 close parenthesis equals 6")[$4 C_(2) = frac(4 !, ( 4 − 2 ) ! #h(0.167em) 2 !) = frac(4 × 3 × 2 × 1, ( 2 × 1 ) ( 2 × 1 )) = 6$] which is consistent with Table 3. As an example application, suppose there were six kinds of toppings that one could order for a pizza. How many combinations of exactly 3 toppings could be ordered? Here n = 6 since there are 6 toppings and r = 3 since we are taking 3 at a time. The formula is then: #math.equation(block: true, alt: "6 C sub 3 equals the fraction 6 ! over open parenthesis 6 minus 3 close parenthesis ! 3 ! equals the fraction 6 times 5 times 4 times 3 times 2 times 1 over open parenthesis 3 times 2 times 1 close parenthesis open parenthesis 3 times 2 times 1 close parenthesis equals 20")[$6 C_(3) = frac(6 !, ( 6 − 3 ) ! #h(0.167em) 3 !) = frac(6 × 5 × 4 × 3 × 2 × 1, ( 3 × 2 × 1 ) ( 3 × 2 × 1 )) = 20$]