#set document(title: "4.4 Counting Techniques", author: "Kathryn Kozak") #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")) == 4.4#h(0.6em)Counting Techniques There are times when the sample space or event space are very large, that it isn’t feasible to write it out. In that case, it helps to have mathematical tools for counting the size of the sample space and event space. These tools are known as counting techniques. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #strong[Multiplication Rule in Counting Techniques] If task 1 can be done #strong[#math.equation(block: false, alt: "m sub 1")[$m_(1)$]] ways, task 2 can be done #strong[#math.equation(block: false, alt: "m sub 2")[$m_(2)$]] ways, and so forth to task #emph[n] being done #strong[#math.equation(block: false, alt: "m sub n")[$m_(n)$]] ways. Then the number of ways to do task 1, 2,…, #emph[n] together would be #strong[#math.equation(block: false, alt: "m 1 * m 2 * r Δ * m sub n")[$m_(1)^(*) m_(2)^(*) limits(r)^(Δ *) m_(n)$]]. ] #examplebox("Example 1")[multiplication rule in counting][ A menu offers a choice of 3 salads, 8 main dishes, and 5 desserts. How many different meals consisting of one salad, one main dish, and one dessert are possible? #solutionbox[ There are three tasks, picking a salad, a main dish, and a dessert. The salad task can be done 3 ways, the main dish task can be done 8 ways, and the dessert task can be done 5 ways. The ways to pick a salad, main dish, and dessert are #math.equation(block: false, alt: "the fraction 3 over salad the fraction 8 over main the fraction 5 over dessert equals 120")[$frac(3, " salad ") frac(8, " main ") frac(5, " dessert ") = 120$] different meals ] ] #examplebox("Example 2")[Multiplication rule in counting][ How many three letter “words” can be made from the letters a, b, and c with no letters repeating? A “word” is just an ordered group of letters. It doesn’t have to be a real word in a dictionary. #solutionbox[ There are three tasks that must be done in this case. The tasks are to pick the first letter, then the second letter, and then the third letter. The first task can be done 3 ways since there are 3 letters. The second task can be done 2 ways, since the first task took one of the letters. The third task can be done 1 ways, since the first and second task took two of the letters. There are #math.equation(block: true, alt: "the fraction 3 over first letter * the fraction 2 over second letter * the fraction 1 over third letter")[$frac(3, " first letter ") * frac(2, " second letter ") * frac(1, " third letter ")$] Which is #math.equation(block: true, alt: "3 to the power * 2 to the power * 1 equals 6")[$3^(*) 2^(*) 1 = 6$] You can also look at this in a tree diagram: #figure(figph[A tree diagram showing the six possible orderings abc, acb, bac, bca, cab, and cba from sequential choices of a, b, and c.], alt: "A tree diagram showing the six possible orderings abc, acb, bac, bca, cab, and cba from sequential choices of a, b, and c.", caption: [Figure #math.equation(block: false, alt: "1")[$1$]: Tree diagram]) So, there are 6 different “words.” ] ] In Example #math.equation(block: false, alt: "2")[$2$], the solution was found by find #math.equation(block: false, alt: "3 * 2 * 1 equals 6")[$3 * 2 * 1 = 6$]. Many counting problems involve multiplying a list of decreasing numbers. This is called a #strong[factorial]. There is a special symbol for this and a special button on your calculator. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #strong[Factorial] #math.equation(block: true, alt: "n ! equals n open parenthesis n minus 1 close parenthesis open parenthesis n minus 2 close parenthesis ⋯ open parenthesis 3 close parenthesis open parenthesis 2 close parenthesis open parenthesis 1 close parenthesis")[$n ! = n ( n − 1 ) ( n − 2 ) ⋯ ( 3 ) ( 2 ) ( 1 )$] ] As an example: #math.equation(block: true, alt: "5 ! equals 5 * 4 * 3 * 2 * 1 equals 120")[$5 ! = 5 * 4 * 3 * 2 * 1 = 120$] #math.equation(block: true, alt: "8 ! equals 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 equals 40320")[$8 ! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320$] 0 factorial is defined to be 0!=1 and 1 factorial is defined to be 1!=1. Sometimes you are trying to select #emph[r] objects from #emph[n] total objects. The number of ways to do this depends on if the order you choose the #emph[r]objects matters or if it doesn’t. As an example if you are trying to call a person on the phone, you have to have their number in the right order. Otherwise, you call someone you didn’t mean to. In this case, the order of the numbers matters. If however you were picking random numbers for the lottery, it doesn’t matter which number you pick first. As long as you have the same numbers that the lottery people pick, you win. In this case the order doesn’t matter. A #strong[permutation]is an arrangement of items with a specific order. You use permutations to count items when the order matters. When the order doesn’t matter you use combinations. A #strong[combination]is an arrangement of items when order is not important. When you do a counting problem, the first thing you should ask yourself is “does order matter?” #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #strong[Permutation Formula] Picking #emph[r] objects from #emph[n]total objects when order matters #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 ) !)$] ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #strong[Combination Formula] Picking #emph[r] objects from #emph[n] total objects when order doesn’t matter #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 3")[calculating the number of ways][ In a club with 15 members, how many ways can a slate of 3 officers consisting of a president, vice-president, and secretary/treasurer be chosen? #solutionbox[ In this case the order matters. If you pick person 1 for president, person 2 for vice-president, and person 3 for secretary/treasurer you would have different officers than if you picked person 2 for president, person 1 for vice-president, and person 3 for secretary/treasurer. This is a permutation problem with n=15 and r=3. #math.equation(block: true, alt: "sub 15 P sub 3 equals the fraction 15 ! over open parenthesis 15 minus 3 close parenthesis ! equals the fraction 15 ! over 12 ! equals 2730")[$15 P_(3) = frac(15 !, ( 15 − 3 ) !) = frac(15 !, 12 !) = 2730$] ] ] #examplebox("Example 4")[calculating the number of ways][ Suppose you want to pick 7 people out of 20 people to take part in a survey. How many ways can you do this? #solutionbox[ In this case the order doesn’t matter, since you just want 7 people. This is a combination with n=20 and r=7. #math.equation(block: true, alt: "sub 20 C sub 7 equals the fraction 20 ! over 7 ! open parenthesis 20 minus 7 close parenthesis ! equals the fraction 20 ! over 7 ! 13 ! equals 77520")[$20 C_(7) = frac(20 !, 7 ! ( 20 − 7 ) !) = frac(20 !, 7 ! 13 !) = 77520$] ] ] Most calculators have a factorial button on them, and many have the combination and permutation functions also. R has a combination command. === Homework #notebox("Your Turn", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ + You are going to a benefit dinner, and need to decide before the dinner what you want for salad, main dish, and dessert. You have 2 different salads to choose from, 3 main dishes, and 5 desserts. How many different meals are available? + How many different phone numbers are possible in the area code 928? + You are opening a T-shirt store. You can have long sleeves or short sleeves, three different colors, five different designs, and four different sizes. How many different shirts can you make? + The California license plate has one number followed by three letters followed by three numbers. How many different license plates are there? + Find #math.equation(block: false, alt: "sub 9 P sub 4")[$9 P_(4)$] + Find #math.equation(block: false, alt: "sub 10 P sub 6")[$10 P_(6)$] + Find #math.equation(block: false, alt: "sub 10 P sub 5")[$10 P_(5)$] + Find #math.equation(block: false, alt: "sub 20 P sub 4")[$20 P_(4)$] + You have a group of twelve people. You need to pick a president, treasurer, and secretary from the twelve. How many different ways can you do this? + A baseball team has a 25-man roster. A batting order has nine people. How many different batting orders are there? + An urn contains five red balls, seven yellow balls, and eight white balls. How many different ways can you pick two red balls? + How many ways can you choose seven people from a group of twenty? Answer 1. 30 meals 3. 120 shirts 5. 3024 7. 252 9. 1320 11. 10 ] ==== Data sources #emph[Aboriginal deaths in custody.] (2013, September 26). Retrieved from #link("http://www.statsci.org/data/oz/custody.html")[http://www.statsci.org/data/oz/custody.html] #emph[Activities of dolphin groups.] (2013, September 26). Retrieved from #link("http://www.statsci.org/data/general/dolpacti.html")[http://www.statsci.org/data/general/dolpacti.html] #emph[Car preferences.] (2013, September 26). Retrieved from #link("http://www.statsci.org/data/oz/carprefs.html")[http://www.statsci.org/data/oz/carprefs.html] #emph[Encyclopedia Titanica.] (2013, November 09). Retrieved from www.encyclopediatitanica.org/ #emph[Leprosy: Number of reported cases by country.] (2013, September 04). Retrieved from #link("http://apps.who.int/gho/data/node.main.A1639")[http://apps.who.int/gho/data/node.main.A1639] Madison, J. (2013, October 15). #emph[M&M's color distribution analysis.] Retrieved from #link("http://joshmadison.com/2007/12/02/mms-color-distribution-analysis/")[http://joshmadison.com/2007/12/02/mm...tion-analysis/]