#set document(title: "4.7 Counting Rules", author: "Rachel Webb") #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.7#h(0.6em)Counting Rules There are times when the sample space is very large and is not feasible to write out. In that case, it helps to have mathematical tools for counting the size of the sample space. These tools are known as counting techniques or counting rules. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #strong[Fundamental Counting Rule:] If task 1 can be done m1 ways, task 2 can be done m#sub[2] ways, and so forth to task n being done mn ways. Then the number of ways to do task 1, 2,…, n together would be to multiply the number of ways for each task m#sub[1]·m#sub[2]···m#sub[n]. ] #examplebox("Example 1")[][ 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 times the fraction 2 over main times the fraction 1 over dessert")[$frac(3, " salad ") · frac(2, " main ") · frac(1, " dessert ")$] = 120 different meals. ] ] #examplebox("Example 2")[][ How many 4-digit debit card personal identification numbers (PIN) can be made? #solutionbox[ Four tasks must be done in this example. The tasks are to pick the first number, then the second number, then the third number, and then the fourth number. The first task can be done 10 ways since there are digits 1 through 9 or a zero. We can use the same numbers over again (repeats are allowed) to find that the second task can also be done 10 ways. The same with the third and fourth tasks, which also have 10 ways. There are #math.equation(block: false, alt: "the fraction 10 over first number times the fraction 10 over second number times the fraction 10 over third number times the fraction 10 over fourth number")[$frac(10, " first number ") · frac(10, " second number ") · frac(10, " third number ") · frac(10, " fourth number ")$] = 10,000 possible PINs. ] ] #examplebox("Example 3")[][ How many ways can the three letters a, b, and c be arranged with no letters repeating? #solutionbox[ Three tasks 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 (repeats are not allowed). The third task can be done 1 way, since the first and second task took two of the letters. There are #math.equation(block: false, alt: "the fraction 3 over 1 to the power st letter times the fraction 2 over 2 to the power nd letter times the fraction 1 over 3 to the power rd letter")[$frac(3, 1^("st ") " letter ") · frac(2, 2^("nd ") " letter ") · frac(1, 3^("rd ") " letter ")$] You can also look at this example in a tree diagram, see Figure 4-17. There are 6 different arrangements of the letters. The solution was found by multiplying 3·2·1 = 6. #figure(figph[Tree diagram of the six arrangements of the letters a, b, and c: each choice of first letter branches to the two remaining letters, tracing the paths abc, acb, bac, bca, cab, and cba.], alt: "Tree diagram of the six arrangements of the letters a, b, and c: each choice of first letter branches to the two remaining letters, tracing the paths abc, acb, bac, bca, cab, and cba.", caption: none) Figure 4-17 ] ] If we have 10 different letters for, say, a password, the tree diagram would be very time-consuming to make because of the length of options and tasks, so we have some shortcut formulas that help count these arrangements. Many counting problems involve multiplying a list of decreasing numbers, which is called a #strong[factorial]. The factorial is represented mathematically by the starting number followed by an exclamation point, in this case 3! = 3·2·1 = 6. There is a special symbol for this and a special button on your calculator or computer. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #strong[Factorial Rule:] The number of different ways to arrange n objects is n! = n·(n – 1)·(n – 2) ···3·2·1, where repetitions are not allowed. Zero factorial is defined to be 0! = 1, and 1 factorial is defined to be 1! = 1. ] #strong[TI-84:] On the home screen, enter the number of which you would like to find the factorial. Press \[MATH\]. Use cursor keys to move to the PRB menu. Press 4 (4:!) Press \[ENTER\] to calculate. #strong[TI-89:] On the home screen, enter the number of which you would like to find the factorial. Press \[2#super[nd]\] \[Math\] \> 7:Probability \> 1:!. Press \[ENTER\] to calculate. #strong[Excel:] In an empty cell type in =FACT(n) where n is the number so 4! would be =FACT(4). #examplebox("Example 4")[][ How many ways can you arrange five people standing in line? #solutionbox[ No repeats are allowed since you cannot reuse a person twice. Order is important since the first person is first in line and will be selected first. This meets the requirements for the factorial rule, 5! = 5·4·3·2·1 = 120 ways. ] ] Sometimes we do not want to select the entire group but only select #emph[r] objects from 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 does not matter. As an example, if you are trying to call a person on the phone, you have to have the digits of their number in the correct order. In this case, the order of the numbers matters. If you were picking random numbers for the lottery, it does not matter which number you pick first since they always arrange the numbers from the smallest to largest once the numbers are drawn. As long as you have the same numbers that the lottery officials pick, you win. In this case, the order does not matter. A #strong[permutation]is an arrangement of items with a specific order. You use permutations to count items when the order matters. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #strong[Permutation Rule:] The number of different ways of picking r objects from n total objects when repeats are not allowed and order matters #math.equation(block: false, alt: "n P sub r equals the fraction n ! over open parenthesis n minus r close parenthesis !")[$n P_(r) = frac(n !, ( n − r ) !)$]. ] When the order does not 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 “are repeats allowed,” then ask yourself “does order matter?” #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #strong[Combination Rule:] The number of ways to select r objects from n total objects when repeats are not allowed and order does not matter #math.equation(block: false, alt: "n C sub r equals the fraction n ! over open parenthesis r ! open parenthesis n minus r close parenthesis ! close parenthesis")[$n C_(r) = frac(n !, ( r ! ( n − r ) ! ))$]. ] #strong[TI-84:] Enter the number “trials” (n) on the home screen. Press \[MATH\]. Use cursor keys to move to the PRB menu. Press 2 for permutation (2: #sub[n]P#sub[r]), 3 for combination (3: #sub[n]C#sub[r]). Enter the number of “successes” (r). Press \[ENTER\] to calculate. #strong[TI-89:] Press \[2nd\] Math \> 7:Probability \> Press 2 for permutation (2: #sub[n]P#sub[r]), 3 for combination (3: #sub[n]C#sub[r]). Enter the sample size on the home screen, then a comma, then enter the number of “successes,” then end the parenthesis. Press \[ENTER\] to calculate. #strong[Excel:] In a blank cell type in the formula =COMBIN(n, r) or =PERMUT(n, r) where n is the total number of objects and r is the smaller number of objects that you are selecting out of n. For example =COMBIN(8, 3). The following flow chart in Figure 4-18 may help with deciding which counting rule to use. Start on the left; ask yourself if the same item can be repeated. For instance, a person on a committee cannot be counted as two distinct people; however, a number on a car license plate may be used twice. If repeats are not allowed, then ask, does the order in which the item is chosen matter? If it does not then we use the combinations, if it does then ask are you ordering the entire group, use factorial, or just some of the group, use permutation. #figure(figph[Decision flowchart for counting rules: if repeats are allowed, use the Fundamental Counting Rule (multiply the total number of outcomes in each event); if not and order matters, ordering all of n gives n! while ordering r out of n gives permutations nPr = n!/(n−r)!; if order does not matter, use combinations nCr = n!/(r!(n−r)!).], alt: "Decision flowchart for counting rules: if repeats are allowed, use the Fundamental Counting Rule (multiply the total number of outcomes in each event); if not and order matters, ordering all of n gives n! while ordering r out of n gives permutations nPr = n!/(n−r)!; if order does not matter, use combinations nCr = n!/(r!(n−r)!).", caption: none) Figure 4-18 #examplebox("Example 5")[][ Critical Miss, PSU's Tabletop Gaming Club, has 15 members this term. How many ways can a slate of 3 officers consisting of a president, vice-president, and treasurer be chosen? #solutionbox[ In this case, repeats are not allowed since we don’t want the same member to hold more than one position. The order matters, since if you pick person 1 for president, person 2 for vice-president, and person 3 for treasurer, you would have different members in those positions than if you picked person 2 for president, person 1 for vice-president, and person 3 for treasurer. This is a permutation problem with n = 15 and r = 3. \\( #linebreak() { }\_{15} \\mathrm{P}\_{3}=\\frac{15 !}{(15-3) !}=\\frac{15 !}{12 !}=2730 #linebreak() \\) #linebreak() There are 2,730 ways to elect these three positions. In general, if you were selecting items that involve rank, a position title, 1#super[st], 2#super[nd], or 3#super[rd] place or prize, etc. then the order in which the items are arranged is important and you would use permutation. ] ] #examplebox("Example 6")[][ Critical Miss, PSU's Tabletop Gaming Club, has 15 members this term. They need to select 3 members to have keys to the game office. How many ways can the 3 members be chosen? #solutionbox[ In this case, repeats are not allowed, because we don’t want one person to have more than one key. The order in which the keys are handed out does not matter. This is a combination problem with n = 15 and r = 3. #math.equation(block: true, alt: "15 C sub 3 equals the fraction 15 ! over open parenthesis 3 ! open parenthesis 15 minus 3 close parenthesis ! close parenthesis equals the fraction 15 ! over open parenthesis 3 ! times 12 ! close parenthesis equals 455 There are 455 ways to hand out the three keys.")[$15 C_(3) = frac(15 !, ( 3 ! ( 15 − 3 ) ! )) = frac(15 !, ( 3 ! · 12 ! )) = 455 #h(1em) " There are " 455 " ways to hand out the three keys. "$] We can use these counting rules in finding probabilities. For instance, the probability of winning the lottery can be found using these counting rules. ] ] #examplebox("Example 7")[][ What is the probability of winning the jackpot in the Pick-4 Lottery? To play Pick-4, you choose 4 numbers from 0 to 9. This will give you a number between 0000 and 9999. You win the jackpot if you match your 4 numbers in the exact order they are drawn. https://www.oregonlottery.org/jackpot/pick-4/ Solution There is only one winning number, so the numerator for the probability will just be 1. The denominator will be all the ways to select the 4 numbers. Repeat numbers are allowed, for example you can have 4242 with repeating 4s and 2s. The order in which the balls are selected does matter by the rules of the game. Use the fundamental counting rule combined with the fundamental counting rule and we would get 10·10·10·10 = 10,000. Thus, the probability of winning the jackpot would be #math.equation(block: false, alt: "the fraction 1 over 10000 equals 0.0001")[$frac(1, 10000) = 0.0001$] ] #examplebox("Example 8")[][ What is the probability of getting a full house if 5 cards are randomly dealt from a standard deck of cards? #solutionbox[ A full house is a combined three of a kind and pair, for example, QQQ22. There are #sub[13]C#sub[1] ways to choose a card between Ace, 2, 3, … , King. Once a number is chosen, there are 4 cards with that rank and there are #sub[4]C#sub[3] ways to choose a three of kind from that rank. Once we use up one of the ranks, such as the three queens, there are #sub[12]C#sub[1] ways to choose the rank for the pair. Once the pair is chosen there are #sub[4]C#sub[2] ways to choose a pair from that rank. All together there are #sub[52]C#sub[5] ways to randomly deal out 5 cards. The probability of getting a full house with then be #math.equation(block: false, alt: "the fraction 13 C sub 1 times 4 C sub 3 times 12 C sub 1 times 4 C sub 2 over 52 C sub 5")[$frac(13 C_(1) · 4 C_(3) · 12 C_(1) · 4 C_(2), 52 C_(5))$] = #math.equation(block: false, alt: "the fraction 3744 over 2598960")[$frac(3744, 2598960)$] = 0.00144 ] ] #examplebox("Example 9")[][ What is the probability of winning the Powerball jackpot? As of 2021, the Powerball lottery consists of drawing five white balls in any order numbered 1 through 69, and one red Powerball numbered 1 through 26. https://www.oregonlottery.org/jackpot/powerball/ Solution There is only one winning number, so the numerator for the probability will just be 1. The denominator will be all the ways to select the 5 white balls and 1 red ball. The order in which the balls are selected does not matter and repeat numbers are not allowed. Using the combination rule combined with the fundamental counting rule we would get #sub[69]C#sub[5] ∙ #sub[26]C#sub[1]. Thus, the probability of winning the jackpot would be #math.equation(block: false, alt: "the fraction 1 over 69 C sub 5 times 26 C sub 1")[$frac(1, 69 C_(5) · 26 C_(1))$] = 0.000000003422. ] #examplebox("Example 10")[][ ]