#set document(title: "7.3 Combinations", 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.3#h(0.6em)Combinations #figure(figph[A person is shown holding 5 playing cards. The hand of another player is shown near a pile of plastic chips.], alt: "A person is shown holding 5 playing cards. The hand of another player is shown near a pile of plastic chips.", caption: [Combinations help us count things like the number of possible card hands, when the order in which the cards were drawn doesn’t matter.]) === Learning Objectives After completing this section, you should be able to: + Distinguish between permutation and combination uses. + Compute combinations. + Apply combinations to solve applications. In Permutations, we studied permutations, which we use to count the number of ways to generate an ordered list of a given length from a group of objects. An important property of permutations is that the order of the list matters: The results of a race and the selection of club officers are examples of lists where the order is important. In other situations, the order is not important. For example, in most card games where a player receives a hand of cards, the order in which the cards are received is irrelevant; in fact, players often rearrange the cards in a way that helps them keep the cards organized. === Combinations: When Order Doesn’t Matter In situations in which the order of a list of objects doesn’t matter, the lists are no longer permutations. Instead, we call them #strong[combinations]. #examplebox("Example 1")[Distinguishing Between Permutations and Combinations][ For each of the following situations, decide whether the chosen subset is a permutation or a combination. + A social club selects 3 members to form a committee. Each of the members has an equal share of responsibility. + You are prompted to reset your email password; you select a password consisting of 10 characters without repeats. + At a dog show, the judge must choose first-, second-, and third-place finishers from a group of 16 dogs. + At a restaurant, the special of the day comes with the customer’s choice of 3 sides taken from a list of 6 possibilities. #solutionbox[ + Since there is no distinction among the responsibilities of the 3 committee members, the order isn’t important. So, this is a combination. + The order of the characters in a password matter, so this is a permutation. + The order of finish matters in a dog show, so this is a permutation. + A plate with mashed potatoes, peas, and broccoli is functionally the same as a plate with peas, broccoli, and mashed potatoes, so this is a combination. ] ] === Counting Combinations Permutations and combinations are certainly related, because they both involve choosing a subset of a large group. Let’s explore that connection, so that we can figure out how to use what we know about permutations to help us count combinations. We’ll take a basic example. How many ways can we select 3 letters from the group A, B, C, D, and E? If order matters, that number is #math.equation(block: false, alt: "sub 5 P sub 3 equals 60")[$5 P_(3) = 60$]. That’s small enough that we can list them all out in the table below. #figure(table( columns: 6, align: left, inset: 6pt, table.header([ABC], [ABD], [ABE], [ACB], [ACD], [ACE]), [ADB], [ADC], [ADE], [AEB], [AEC], [AED], [BAC], [BAD], [BAE], [BCA], [BCD], [BCE], [BDA], [BDC], [BDE], [BEA], [BEC], [BED], [CAB], [CAD], [CAE], [CBA], [CBD], [CBE], [CDA], [CDB], [CDE], [CEA], [CEB], [CED], [DCA], [DAC], [DAE], [DBA], [DBC], [DBE], [DCA], [DCB], [DCE], [DEA], [DEB], [DEC], [EAB], [EAC], [EAD], [EBA], [EBC], [EBD], [ECA], [ECB], [ECD], [EDA], [EDB], [EDC], )) Now, let’s look back at that list and color-code it so that groupings of the same 3 letters get the same color, as shown in : #figure( stdfig([#align(center)[*Possible combinations*] #v(0.4em) #table( columns: (auto,) * 7, align: center+horizon, inset: 5pt, stroke: 0.5pt + black, table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, colspan: 6, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[Column]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[Row]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[1]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[2]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[3]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[4]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[5]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[6]), table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[1]), [ABC], [ABD], [ABE], [ACB], [ACD], [ACE], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[2]), [ADB], [ADC], [ADE], [AEB], [AEC], [AED], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[3]), [BAC], [BAD], [BAE], [BCA], [BCD], [BCE], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[4]), [BDA], [BDC], [BDE], [BEA], [BEC], [BED], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[5]), [CAB], [CAD], [CAE], [CBA], [CBD], [CBE], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[6]), [CDA], [CDB], [CDE], [CEA], [CEB], [CED], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[7]), [DAB], [DAC], [DAE], [DBA], [DBC], [DBE], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[8]), [DCA], [DCB], [DCE], [DEA], [DEB], [DEC], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[9]), [EAB], [EAC], [EAD], [EBA], [EBC], [EBD], table.cell(fill: rgb("#f0f0f0"), align: center+horizon, text(font: sys.inputs.at("title-font", default: "STIX Two Text"), weight: "bold", size: 9pt)[10]), [ECA], [ECB], [ECD], [EDA], [EDB], [EDC], )]), alt: "A table of possible combinations. The table has 10 rows and 6 columns. The data is as follows: Row 1, ABC, ABD, ABE, ACB, ACD, ACE. Row 2, ADB, ADC, ADE, AEB, AEC, AED. Row 3, BAC, BAD, BAE, BCA, BCD, BCE. Row 4, BDA, BDC, BDE, BEA, BEC, BED. Row 5, CAB, CAD, CAE, CBA, CBD, CBE. Row 6, CDA, CDB, CDE, CEA, CEB, CED. Row 7, DAB, DAC, DAE, DBA, DBC, DBE. Row 8, DCA, DCB, DCE, DEA, DEB, DEC. Row 9, EAB, EAC, EAD, EBA, EBC, EBD. Row 10, ECA, ECB, ECD, EDA, EDB, EDC. The combinations are color-coded as follows: Dark red, ABC, ACB, BAC, BCA, CAB, CBA. Light red, ABD, ADB, BAD, BDA, DAB, DBA. Orange, ABE, AEB, BAE, BEA, EAB, EBA. Yellow, ACD, ADC, CAD, CDA, DAC, DCA. Light green, ACE, AEC, CAE, CEA, EAC, ECA. Dark green, ADE, AED, DAE, DEA, EAD, EDA. Light blue, BCD, BDC, CBD, CDB, DBC, DCB. Dark blue, BCE, BEC, CBE, CEB, EBC, ECB. Dark purple, BDE, BED, DBE, DEB, EBD, EDB. Light purple, CDE, CED, DCE, DEC, ECD, EDC.", caption: none, ) After color-coding, we see that the 60 cells can be seen as 10 groups (colors) of 6. That’s no coincidence! We’ve already seen how to compute the number of permutations using the formula To compute the number of combinations, let’s count them another way using the Multiplication Rule for Counting. We’ll do this in two steps: #strong[Step 1:] Choose 3 letters (paying no attention to order). #strong[Step 2:] Put those letters in order. The number of ways to choose 3 letters from this group of 5 (A, B, C, D, E) is the number of combinations we’re looking for; let’s call that number #math.equation(block: false, alt: "sub 5 C sub 3")[$5 C_(3)$] (read “the number of combinations of 5 objects taken 3 at a time”). We can see from our chart that this is ten (the number of colors used). We can generalize our findings this way: remember that the number of permutations of #math.equation(block: false, alt: "n")[$n$] things taken #math.equation(block: false, alt: "r")[$r$] at a time is #math.equation(block: false, 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 ) !)$]. That number is #emph[also] equal to #math.equation(block: false, alt: "sub n C sub r times r !")[$n C_(r) × r !$], and so it must be the case that #math.equation(block: false, alt: "the fraction n ! over open parenthesis n minus r close parenthesis ! equals sub n C sub r times r !")[$frac(n !, ( n − r ) !) =_(n) C_(r) × r !$]. Dividing both sides of that equation by #math.equation(block: false, alt: "r !")[$r !$] gives us the formula below. #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[ #math.equation(block: true, alt: "sub n C sub r equals the fraction n ! over r ! open parenthesis n minus r close parenthesis !")[$n C_(r) = frac(n !, r ! ( n − r ) !)$] ] #examplebox("Example 2")[Using the Combination Formula][ Compute the following: + #math.equation(block: false, alt: "sub 8 C sub 3")[$8 C_(3)$] + #math.equation(block: false, alt: "sub 12 C sub 5")[$12 C_(5)$] + #math.equation(block: false, alt: "sub 15 C sub 9")[$15 C_(9)$] #solutionbox[ + #math.equation(block: false, alt: "sub 8 C sub 3 equals the fraction 8 ! over 3 ! open parenthesis 8 minus 3 close parenthesis ! equals the fraction 8 times 7 times 6 times 5 ! over 3 times 2 times 1 times 5 ! equals 8 times 7 equals 56")[$8 C_(3) = frac(8 !, 3 ! ( 8 − 3 ) !) = frac(8 × 7 × 6 × 5 !, 3 × 2 × 1 × 5 !) = 8 × 7 = 56$] + #math.equation(block: false, alt: "sub 12 C sub 5 equals the fraction 12 ! over 5 ! open parenthesis 12 minus 5 close parenthesis ! equals the fraction 12 times 11 times 10 times 9 times 8 times 7 ! over 5 times 4 times 3 times 2 times 1 times 7 ! equals 11 times 9 times 8 equals 792")[$12 C_(5) = frac(12 !, 5 ! ( 12 − 5 ) !) = frac(12 × 11 × 10 × 9 × 8 × 7 !, 5 × 4 × 3 × 2 × 1 × 7 !) = 11 × 9 × 8 = 792$] + #math.equation(block: false, alt: "sub 15 C sub 9 equals the fraction 15 ! over 9 ! open parenthesis 15 minus 9 close parenthesis ! equals the fraction 15 times 14 times 13 times 12 times 11 times 10 times 9 ! over 9 ! times 6 times 5 times 4 times 3 times 2 times 1 equals the fraction 14 times 13 times 11 times 10 over 4 equals 5,005")[$15 C_(9) = frac(15 !, 9 ! ( 15 − 9 ) !) = frac(15 × 14 × 13 × 12 × 11 × 10 × 9 !, 9 ! × 6 × 5 × 4 × 3 × 2 × 1) = frac(14 × 13 × 11 × 10, 4) = 5,005$] ] ] #examplebox("Example 3")[Applying the Combination Formula][ + In the card game Texas Hold’em (a variation of poker), players are dealt 2 cards from a standard deck to form their hands. How many different hands are possible? + The board game #emph[Clue] uses a deck of 21 cards. If 3 people are playing, each person gets 6 cards for their hand. How many different 6-card #emph[Clue] hands are possible? + Palmetto Cash 5 is a game offered by the South Carolina Education Lottery. Players choose 5 numbers from the whole numbers between 1 and 38 (inclusive); the player wins the jackpot of \$100,000 if the randomizer selects those numbers in any order. How many different sets of winning numbers are possible? #solutionbox[ + A standard deck has 52 cards, and a hand has 2 cards. Since the order doesn’t matter, we use the formula for counting combinations: #math.equation(block: true, alt: "sub 52 C sub 2 equals the fraction 52 ! over 2 ! open parenthesis 52 minus 2 close parenthesis ! equals the fraction 52 times 51 times 50 ! over 2 times 1 times 50 ! equals the fraction 52 times 51 over 2 equals 1,326 .")[$52 C_(2) = frac(52 !, 2 ! ( 52 − 2 ) !) = frac(52 × 51 × 50 !, 2 × 1 × 50 !) = frac(52 × 51, 2) = 1,326 "."$] + Again, the order doesn’t matter, so the number of combinations is: #math.equation(block: true, alt: "sub 21 C sub 6 equals the fraction 21 ! over 6 ! open parenthesis 21 minus 6 close parenthesis ! equals the fraction 21 times 20 times 19 times 18 times 17 times 16 times 15 ! over 6 times 5 times 4 times 3 times 2 times 1 times 15 ! equals the fraction 21 times 19 times 17 times 16 over 2 equals 54,264 .")[$21 C_(6) = frac(21 !, 6 ! ( 21 − 6 ) !) = frac(21 × 20 × 19 × 18 × 17 × 16 × 15 !, 6 × 5 × 4 × 3 × 2 × 1 × 15 !) = frac(21 × 19 × 17 × 16, 2) = 54,264 "."$] + There are 38 numbers to choose from, and we must pick 5. Since order doesn’t matter, the number of combinations is: #math.equation(block: true, alt: "sub 38 C sub 5 equals the fraction 38 ! over 5 ! open parenthesis 38 minus 5 close parenthesis ! equals the fraction 38 times 37 times 36 times 35 times 34 times 33 ! over 5 times 4 times 3 times 2 times 1 times 33 ! equals 501,492 .")[$38 C_(5) = frac(38 !, 5 ! ( 38 − 5 ) !) = frac(38 × 37 × 36 × 35 × 34 × 33 !, 5 × 4 × 3 × 2 × 1 × 33 !) = 501,492 "."$] ] ] #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[ #emph[The notation and nomenclature used for the number of combinations is not standard across all sources. You’ll sometimes see] #math.equation(block: false, alt: "open parenthesis n; r close parenthesis")[$( n \ r )$] #emph[instead of] #math.equation(block: false, alt: "sub n C sub r")[$n C_(r)$] #emph[. Sometimes you’ll hear that expression read as “#math.equation(block: false, alt: "n")[$n$] choose #math.equation(block: false, alt: "r")[$r$]” as shorthand for “the number of combinations of #math.equation(block: false, alt: "n")[$n$] objects taken #math.equation(block: false, alt: "r")[$r$] at a time.”] ] #notebox("People in Mathematics", rgb("#183B6F"), rgb("#183B6F"), rgb("#EFF1F5"))[ #emph[Early Eastern Mathematicians] Although combinations weren’t really studied in Europe until around the 13th century, mathematicians of the Middle and Far East had already been working on them for hundreds of years. The Indian mathematician known as Pingala had described them by the second century BCE; Varāhamihira (fl. sixth century) and Halayudha (fl. 10th century) extended Pingala’s work. In the ninth century, a Jain mathematician named Mahāvīra gave the formula for combinations that we use today. In 10th-century Baghdad, a mathematician named Al-Karaji also knew formulas for combinations; though his work is now lost, it was known to (and repeated by) Persian mathematician Omar Khayyam, whose work survives. Khayyam is probably best remembered as a poet, with his #emph[Rubaiyat] being his most famous work. Meanwhile, in 11th-century China, Jia Xian also was working with combinations, as was his 13th-century successor Yang Hui. It is not known whether the discoveries of any of these men were known in the other regions, or if the Indians, Persians, and Chinese all came to their discoveries independently. We do know that mathematical knowledge and sometimes texts did get passed along trade routes, so it can’t be ruled out. ] #examplebox("Example 4")[Combining Combinations with the Multiplication Rule for Counting][ The student government at a university consists of 10 seniors, 8 juniors, 6 sophomores, and 4 first-years. + How many ways are there to choose a committee of 8 people from this group? + How many ways are to choose a committee of 8 people if the committee must consist of 2 people from each class? #solutionbox[ + There are 28 people to choose from, and we need 8. So, the number of possible committees is #math.equation(block: false, alt: "sub 28 C sub 8 equals 3,108,105")[$28 C_(8) = 3,108,105$]. + Break the selection of the committee members down into a 4-step process: Choose the seniors, then choose the juniors, then the sophomores, and then the first-years, as shown in the table below: #figure(table( columns: 2, align: left, inset: 6pt, table.header([Class], [Number of Ways to Choose Committee Representatives]), [senior], [#math.equation(block: false, alt: "sub 10 C sub 2 equals 45")[$10 C_(2) = 45$]], [junior], [#math.equation(block: false, alt: "sub 8 C sub 2 equals 28")[$8 C_(2) = 28$]], [sophomore], [#math.equation(block: false, alt: "sub 6 C sub 2 equals 15")[$6 C_(2) = 15$]], [first-year], [#math.equation(block: false, alt: "sub 4 C sub 2 equals 6")[$4 C_(2) = 6$]], )) The Multiplication Rule for Counting tells us that we can get the total number of ways to complete this task by multiplying together the number of ways to do each of the four subtasks. So, there are #math.equation(block: false, alt: "45 times 28 times 15 times 6 equals 113,400")[$45 × 28 × 15 × 6 = 113,400$] possible committees with these restrictions. ] ] === Key Terms - combination === Key Concepts - Permutations are used to count subsets when order matters; combinations work when order doesn't matter. - Combinations can also be computed using factorials. === Formulas - The formula for counting combinations is: #linebreak() #math.equation(block: false, alt: "sub n C sub r equals the fraction n ! over r ! open parenthesis n minus r close parenthesis !")[$n C_(r) = frac(n !, r ! ( n − r ) !)$]