Tasks 07-03 - Combinatorics

Section 07: Probability & Statistics

A: Skills

Problem 1: Fundamental Counting Principle (x)

  1. A sandwich bar lets customers build their own sandwich. They choose one of 3 kinds of bread, one of 5 fillings and one of 4 sauces. Determine the number of different sandwiches.

  2. A library labels its shelves with 1 letter (A to Z) followed by 3 digits (0 to 9), e.g. K047. Letters and digits may repeat. Determine the number of possible labels.

  3. Determine the number of labels from b) in which the 3 digits are all different.

  4. An online survey has 6 questions. Each question is answered with “yes”, “no” or “don’t know”. Determine the number of different ways to fill in the survey.

  1. Three choices one after the other, so multiply the numbers of options:

    \[3 \cdot 5 \cdot 4 = 60 \text{ sandwiches}\]

  2. 26 options for the letter and 10 options for each digit:

    \[26 \cdot 10 \cdot 10 \cdot 10 = 26 \cdot 10^3 = 26{,}000 \text{ labels}\]

  3. The letter still has 26 options. The first digit has 10 options, the second digit 9 (it must differ from the first), the third digit 8:

    \[26 \cdot 10 \cdot 9 \cdot 8 = 18{,}720 \text{ labels}\]

  4. Each of the 6 questions has 3 possible answers, and answers may repeat:

    \[3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 = 3^6 = 729 \text{ ways}\]

Typical mistake: in d), computing \(6^3 = 216\). The base is the number of options per step (3 answers), the exponent is the number of steps (6 questions).

Problem 2: Factorials (x)

  1. Compute \(7!\), \(1!\) and \(0!\).

  2. Compute \(\frac{9!}{7!}\) and \(\frac{11!}{9! \cdot 2!}\) without a calculator. Cancel before you multiply.

  3. Show that \(\frac{n!}{(n-2)!} = n(n-1)\) for every natural number \(n \geq 2\). Use this to compute \(\frac{25!}{23!}\).

  1. \(7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5{,}040\), \(\quad 1! = 1\), \(\quad 0! = 1\) (by definition)

  2. Write the larger factorial down to the smaller one and cancel:

    \[\frac{9!}{7!} = \frac{9 \cdot 8 \cdot 7!}{7!} = 9 \cdot 8 = 72\]

    \[\frac{11!}{9! \cdot 2!} = \frac{11 \cdot 10 \cdot 9!}{9! \cdot 2} = \frac{110}{2} = 55\]

  3. \(n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 1 = n \cdot (n-1) \cdot (n-2)!\), so

    \[\frac{n!}{(n-2)!} = \frac{n \cdot (n-1) \cdot (n-2)!}{(n-2)!} = n(n-1)\]

    For \(n = 25\): \(\frac{25!}{23!} = 25 \cdot 24 = 600\).

Typical mistake: in b), writing \(\frac{9!}{7!} = 2!\) or \(\left(\frac{9}{7}\right)!\). A quotient of factorials is not the factorial of a difference or a quotient: \(\frac{9!}{7!} = 72\), but \(2! = 2\).

Problem 3: Permutations and Combinations (x)

  1. A courier has 6 parcels for 6 different addresses. Determine the number of possible orders in which the courier can deliver them.

  2. A cooking contest has 11 finalists. The jury awards a first, a second and a third prize. Determine the number of possible results.

  3. A tea shop sells 14 teas. For a tasting box, it chooses 3 different teas. Determine the number of possible tasting boxes.

  4. The tea shop now puts the 3 teas into a box with 3 numbered compartments, so the order matters. Determine the number of possible filled boxes and explain why it is \(3!\) times the result of c).

Give probabilities as fractions and as decimals rounded to four decimal places, and keep all intermediate results unrounded. This rule holds for the whole sheet.

  1. 4 of the 14 teas are green teas. The shop fills a tasting box as in c) at random, so every box is equally likely. Compute the probability that the box contains only green teas and the probability that it contains no green tea.

  1. All 6 parcels are arranged in a row, so this is a permutation of all 6:

    \[P(6, 6) = 6! = 720 \text{ orders}\]

  2. The order matters (first prize is not second prize), and no finalist wins twice:

    \[P(11, 3) = \frac{11!}{8!} = 11 \cdot 10 \cdot 9 = 990 \text{ results}\]

  3. The order does not matter (a box with teas 1, 2, 3 is the same as a box with teas 3, 1, 2), and no tea is chosen twice:

    \[\binom{14}{3} = \frac{14!}{3! \cdot 11!} = \frac{14 \cdot 13 \cdot 12}{3 \cdot 2 \cdot 1} = \frac{2{,}184}{6} = 364 \text{ boxes}\]

  4. Now the order matters:

    \[P(14, 3) = 14 \cdot 13 \cdot 12 = 2{,}184 = 364 \cdot 6\]

    Each set of 3 teas from c) can be put into the 3 compartments in \(3! = 6\) ways, so every box from c) turns into 6 filled boxes.

  5. All 364 boxes are equally likely, so \(P = \frac{\text{favourable boxes}}{\text{all boxes}}\).

    Only green teas: choose 3 of the 4 green teas, \(\binom{4}{3} = 4\):

    \[P(\text{only green}) = \frac{4}{364} = \frac{1}{91} \approx 0.0110\]

    No green tea: choose all 3 teas from the \(14 - 4 = 10\) other teas, \(\binom{10}{3} = 120\):

    \[P(\text{no green}) = \frac{120}{364} = \frac{30}{91} \approx 0.3297\]

Typical mistake: in b), computing \(\binom{11}{3} = 165\). This counts “finalist A first, finalist B second” and “finalist B first, finalist A second” as the same result, although the prizes differ.

Problem 4: Permutation or Combination? (xx)

For each situation, decide first whether the order matters and whether repetition is allowed. Then compute the number of possibilities.

  1. An airline chooses 4 of its 17 cabin crew members for a charter flight. All 4 have the same job on board.

  2. A radio show plays 5 of 9 new songs, one after the other.

  3. A web shop asks every customer to rate the delivery, the packaging, the price and the service, each with 1 to 5 stars.

  4. A car dealer gives one fuel voucher each to 3 of its 15 regular customers. The vouchers are identical.

  5. The car dealer lends a van, an SUV and a convertible for one weekend to 3 of its 15 regular customers, one car per customer. Check that the result is \(3!\) times the result of d).

  1. Combination: the 4 crew members have the same job, so the order does not matter. Nobody is chosen twice.

    \[\binom{17}{4} = \frac{17 \cdot 16 \cdot 15 \cdot 14}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{57{,}120}{24} = 2{,}380\]

  2. Permutation: the order matters (first song, second song, …), and no song is played twice.

    \[P(9, 5) = 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 15{,}120\]

  3. Counting principle with repetition: the order matters (5 stars for the delivery and 1 star for the price is not the same as 1 star for the delivery and 5 stars for the price), and two aspects may get the same number of stars.

    \[5 \cdot 5 \cdot 5 \cdot 5 = 5^4 = 625\]

  4. Combination: the vouchers are identical, so it only matters who gets one.

    \[\binom{15}{3} = \frac{15 \cdot 14 \cdot 13}{3 \cdot 2 \cdot 1} = \frac{2{,}730}{6} = 455\]

  5. Permutation: the cars differ, so it matters who gets which car.

    \[P(15, 3) = 15 \cdot 14 \cdot 13 = 2{,}730\]

    Check: \(455 \cdot 3! = 455 \cdot 6 = 2{,}730\) \(\checkmark\) Each group of 3 customers from d) can share out the 3 cars in \(3! = 6\) ways.

Typical mistake: in c), computing \(P(5, 4) = 120\). The stars may repeat, so each of the 4 aspects has all 5 options.

Problem 5: Pascal’s Triangle (xx)

  1. Write down the rows \(n = 0\) to \(n = 7\) of Pascal’s triangle.

  2. Read \(\binom{6}{2}\) and \(\binom{6}{4}\) off the triangle. Check \(\binom{6}{2}\) with the formula and explain why \(\binom{6}{2} = \binom{6}{4}\).

  3. Each entry of Pascal’s triangle is the sum of the two entries above it. Verify this rule for \(n = 6\) and \(r = 3\), i.e. check with the triangle that \(\binom{6}{3} + \binom{6}{4} = \binom{7}{4}\).

  4. A juice bar mixes smoothies from 7 fruits. Every smoothie contains 2 different fruits. Use row 7 of the triangle to give the number of different smoothies and check your answer with the formula.

  1. Each row starts and ends with 1. All entries in between are the sum of the two entries above them:

    \(n\) Row
    0 1
    1 1, 1
    2 1, 2, 1
    3 1, 3, 3, 1
    4 1, 4, 6, 4, 1
    5 1, 5, 10, 10, 5, 1
    6 1, 6, 15, 20, 15, 6, 1
    7 1, 7, 21, 35, 35, 21, 7, 1

  2. In row 6, count the entries from \(r = 0\): \(\binom{6}{2} = 15\) and \(\binom{6}{4} = 15\).

    Formula: \(\binom{6}{2} = \frac{6!}{2! \cdot 4!} = \frac{6 \cdot 5}{2 \cdot 1} = 15\) \(\checkmark\)

    Choosing the 2 objects you take from 6 is the same as choosing the 4 objects you leave behind. So both numbers count the same selections.

  3. \(\binom{6}{3} + \binom{6}{4} = 20 + 15 = 35\), and \(\binom{7}{4} = 35\) (row 7, \(r = 4\)) \(\checkmark\)

  4. The order of the fruits in a smoothie does not matter, so the number is \(\binom{7}{2}\). Row 7, \(r = 2\): \(21\) smoothies.

    Formula: \(\binom{7}{2} = \frac{7 \cdot 6}{2 \cdot 1} = 21\) \(\checkmark\)

Typical mistake: reading \(\binom{6}{2}\) as the second entry of row 6 (that is 6). The rows and the entries both start counting at 0, so \(\binom{6}{2}\) is the third entry.

B: Set Up & Check

Problem 6: From Words to Counts (xx)

Translate each situation into a counting formula. Then answer the check question: it tells you whether your formula works.

  1. A cycling magazine tests 16 new e-bike models. It names its “top 3” of the year as first, second and third place. It also chooses 3 of the 16 models for a long-term test. Write both numbers of possibilities as formulas and compute them.

    Check: A classmate uses \(\binom{16}{3}\) for the top 3. Explain why this is wrong and how the two results are connected.

  2. An online shop gives every customer a customer number with 5 digits (0 to 9). Write the number of customer numbers if digits may repeat and the number if all 5 digits must be different, and compute both.

    Check: A classmate computes the number with different digits as \(\binom{10}{5} = 252\). Explain the mistake with the customer numbers 12345 and 54321.

  3. A driving school chooses 4 of its 14 driving instructors at random for a customer survey. 5 of the 14 instructors started this year. Write the number of selections with exactly 2 new instructors as a formula and compute it.

    Check: A classmate adds \(\binom{5}{2} + \binom{9}{2} = 46\). Explain why the two numbers must be multiplied.

  4. A museum lends 4 of its 18 audio guides at random to a school group. 3 of the 18 audio guides have an empty battery. Write the probability that at least one of the 4 audio guides has an empty battery with the complement and compute it.

    Check: A classmate computes \(4 \cdot \frac{3}{18} \approx 0.6667\). Explain why this method is wrong. What would it give if the museum lent 8 audio guides?

  5. An online shop shows 3 of the 21 customer reviews of a product on the product page, chosen at random. 8 of the 21 reviews give 5 stars. Write the probability that all 3 reviews shown give 5 stars as a quotient of counts and compute it.

    Check: A classmate counts ordered selections instead and computes \(\frac{P(8, 3)}{P(21, 3)}\). Compute this quotient and explain why it gives the same result.

  1. Top 3: the order matters (first place is not third place), no model twice:

    \[P(16, 3) = 16 \cdot 15 \cdot 14 = 3{,}360\]

    Long-term test: the order does not matter, no model twice:

    \[\binom{16}{3} = \frac{16 \cdot 15 \cdot 14}{3 \cdot 2 \cdot 1} = \frac{3{,}360}{6} = 560\]

    Check: \(\binom{16}{3}\) counts groups of 3 models, so “A first, B second, C third” and “C first, B second, A third” would be the same top 3. Each group of 3 models can be ranked in \(3! = 6\) ways: \(560 \cdot 6 = 3{,}360\).

    Typical mistake: deciding by the verb. The magazine “chooses” in both cases. Ask instead whether swapping two of the chosen models gives a different result.

  2. With repetition, each of the 5 positions has 10 options:

    \[10 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 10^5 = 100{,}000\]

    All digits different, the order matters:

    \[P(10, 5) = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 30{,}240\]

    Check: 12345 and 54321 contain the same digits but are two different customer numbers. \(\binom{10}{5}\) only counts which 5 digits appear, not their order. Each set of 5 digits gives \(5! = 120\) customer numbers: \(252 \cdot 120 = 30{,}240\) \(\checkmark\)

    Typical mistake: computing \(5^{10}\). The base is the number of options per position (10 digits), the exponent the number of positions (5).

  3. Choose 2 of the 5 new instructors and 2 of the \(14 - 5 = 9\) other instructors:

    \[\binom{5}{2} \cdot \binom{9}{2} = 10 \cdot 36 = 360\]

    Check: the selection is made in two steps, first the 2 new instructors, then the 2 others. Each of the 10 choices in the first step can be combined with each of the 36 choices in the second step, so by the counting principle the numbers are multiplied. The sum 46 would count “2 new instructors” and “2 other instructors” as separate selections, but each selection needs both.

    Typical mistake: computing \(\binom{5}{2} \cdot \binom{14}{2}\). The other 2 instructors must come from the 9 who are not new, otherwise the selection could contain 3 or 4 new instructors.

  4. The complement of “at least one empty battery” is “no empty battery”, i.e. all 4 audio guides come from the \(18 - 3 = 15\) good ones:

    \[P(\text{at least one empty}) = 1 - \frac{\binom{15}{4}}{\binom{18}{4}} = 1 - \frac{1{,}365}{3{,}060} = \frac{1{,}695}{3{,}060} = \frac{113}{204} \approx 0.5539\]

    Check: \(4 \cdot \frac{3}{18}\) counts the groups with 2 or 3 empty audio guides more than once. For 8 audio guides, it would give \(8 \cdot \frac{3}{18} \approx 1.3333 > 1\), which is not a probability. Adding the cases “exactly 1”, “exactly 2” and “exactly 3” is correct but longer:

    \[\frac{3 \cdot 455 + 3 \cdot 105 + 1 \cdot 15}{3{,}060} = \frac{1{,}365 + 315 + 15}{3{,}060} = \frac{1{,}695}{3{,}060} \;\checkmark\]

    Typical mistake: computing only “exactly one”, \(\frac{3 \cdot 455}{3{,}060} \approx 0.4461\). “At least one” also contains the groups with 2 or 3 empty audio guides.

  5. All \(\binom{21}{3}\) selections are equally likely. Favourable: 3 of the 8 five-star reviews.

    \[P(\text{all three 5 stars}) = \frac{\binom{8}{3}}{\binom{21}{3}} = \frac{56}{1{,}330} = \frac{4}{95} \approx 0.0421\]

    Check: \(\frac{P(8, 3)}{P(21, 3)} = \frac{8 \cdot 7 \cdot 6}{21 \cdot 20 \cdot 19} = \frac{336}{7{,}980} = \frac{4}{95}\) \(\checkmark\) Ordered counting makes the numerator and the denominator both \(3! = 6\) times larger, so the quotient stays the same.

    Typical mistake: mixing both ways, \(\frac{56}{7{,}980} \approx 0.0070\). The favourable and the total outcomes must be counted in the same way.

Problem 7: One Paragraph, All Selections (xx)

A city theatre plans its next season. 18 plays were submitted, 5 of them comedies. The artistic director chooses 6 of the plays for the season and then fixes the order in which they are shown. At the season opening, 3 of the 10 actors of the ensemble give a short speech, one after the other. Every ticket gets a code of 3 letters (A to Z) followed by 3 digits (0 to 9), and letters and digits may repeat. The director wants to know the number of possible seasons (which plays), the number of possible schedules (which plays in which order), the number of possible line-ups for the speeches and the number of ticket codes. The board also asks: if the 6 plays were drawn by lot, how likely would a season with exactly 2 comedies be, and how likely a season with at least one comedy?

List every count and every probability in this paragraph. For each count, write what is chosen from what, whether the order matters and whether repetition is allowed, and give the formula. Do not compute anything.

Check: An assistant writes the number of seasons as \(P(18, 6)\). Explain what \(P(18, 6)\) counts and how it is connected to the number of seasons.

  1. Seasons: 6 of 18 plays, order does not matter, no repetition: \(\binom{18}{6}\)
  2. Schedules: 6 of 18 plays in an order, no repetition: \(P(18, 6)\). Equivalently, choose the season and then arrange its 6 plays: \(\binom{18}{6} \cdot 6!\)
  3. Speeches: 3 of 10 actors, order matters, no repetition: \(P(10, 3)\)
  4. Ticket codes: 3 letters with 26 options each and 3 digits with 10 options each, repetition allowed: \(26^3 \cdot 10^3\)
  5. Exactly 2 comedies by lot: 2 of the 5 comedies and 4 of the 13 other plays, \(P = \frac{\binom{5}{2} \cdot \binom{13}{4}}{\binom{18}{6}}\)
  6. At least one comedy by lot: complement of “no comedy”, \(P = 1 - \frac{\binom{13}{6}}{\binom{18}{6}}\)

Check: \(P(18, 6)\) counts ordered selections, i.e. the schedules. Each season appears \(6! = 720\) times in it, once for each order of its 6 plays. So \(P(18, 6) = \binom{18}{6} \cdot 6!\) answers the question about the schedules, not the one about the seasons.

Typical mistake: writing “at least one comedy” as \(\frac{\binom{5}{1} \cdot \binom{13}{5}}{\binom{18}{6}}\). This is “exactly one comedy”. “At least one” also contains the seasons with 2, 3, 4 or 5 comedies, so the complement “no comedy” is much shorter.

C: Applied

Problem 8: Team for a Pop-up Store (xx)

A fashion label opens a pop-up store (a shop that is only open for a short time) at a Christmas market. It sends a team of 6 people. The label has 8 sales assistants and 5 tailors, who alter clothes on the spot.

  1. Determine the number of possible teams and give a reason for your method.

  2. Determine the number of teams with exactly 2 tailors.

  3. The team needs at least 2 tailors. Determine the number of teams that meet this condition, once by adding cases and once with the complement. Compare the two ways.

(for verification: 1,408 teams)

  1. The store manager is one of the 8 sales assistants and has the keys, so the store manager must be in the team. Determine the number of teams with the store manager and at least 2 tailors.

Hint: Put the store manager into the team first. Then choose the other 5 team members from the remaining 12 people.

  1. Two of the tailors share one sewing machine, so they cannot both go. Without the conditions from c) and d), determine the number of teams that do not contain both of these tailors.

Hint: Count the teams that contain both of these tailors first.

a) A team is a group of people without roles, so the order does not matter, and nobody is chosen twice. Combination of 6 from \(8 + 5 = 13\) people:

\[\binom{13}{6} = \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{1{,}235{,}520}{720} = 1{,}716 \text{ teams}\]

b) 2 of the 5 tailors and 4 of the 8 sales assistants, combined by the counting principle:

\[\binom{5}{2} \cdot \binom{8}{4} = 10 \cdot 70 = 700 \text{ teams}\]

c) Adding cases, 2, 3, 4 or 5 tailors (the rest are sales assistants):

\[\binom{5}{2}\binom{8}{4} + \binom{5}{3}\binom{8}{3} + \binom{5}{4}\binom{8}{2} + \binom{5}{5}\binom{8}{1} = 700 + 10 \cdot 56 + 5 \cdot 28 + 1 \cdot 8 = 700 + 560 + 140 + 8 = 1{,}408\]

Complement: “at least 2 tailors” is the opposite of “at most 1 tailor”, i.e. 0 or 1 tailor:

\[1{,}716 - \binom{8}{6} - \binom{5}{1}\binom{8}{5} = 1{,}716 - 28 - 5 \cdot 56 = 1{,}716 - 308 = 1{,}408\]

Both ways give 1,408 teams. The complement needs two cases instead of four.

d) The store manager is already in the team. The other 5 members come from the remaining 7 sales assistants and 5 tailors, with at least 2 tailors. Complement within these 12 people:

\[\binom{12}{5} - \binom{7}{5} - \binom{5}{1}\binom{7}{4} = 792 - 21 - 5 \cdot 35 = 792 - 196 = 596 \text{ teams}\]

Check by cases: \(\binom{5}{2}\binom{7}{3} + \binom{5}{3}\binom{7}{2} + \binom{5}{4}\binom{7}{1} + \binom{5}{5}\binom{7}{0} = 350 + 210 + 35 + 1 = 596\) \(\checkmark\)

e) Teams with both of these tailors: the other 4 members come from the remaining 11 people, \(\binom{11}{4} = 330\). All other teams are allowed:

\[1{,}716 - 330 = 1{,}386 \text{ teams}\]

Typical mistake: in c), computing \(\binom{5}{2} \cdot \binom{11}{4} = 10 \cdot 330 = 3{,}300\) (“first 2 tailors, then any 4 others”). This is more than all 1,716 teams: a team with 3 tailors is counted \(\binom{3}{2} = 3\) times, once for each pair of its tailors that could have been chosen first.

Problem 9: Pallet Labels and Loading Docks at a Frozen-Food Warehouse (xx)

A frozen-food warehouse labels every pallet with a code of 2 letters followed by 3 digits (0 to 9), e.g. KM042. The letters I and O are not used, because they look like the digits 1 and 0, so 24 letters are left. Letters and digits may repeat.

  1. Determine the number of possible codes.

  2. The warehouse labels 40,000 pallets per year and may not use a code again within 10 years. Decide whether the codes are enough.

  3. A colleague suggests using only codes with two different letters and three different digits, because they are easier to read. Determine the number of these codes and decide whether they are still enough.

(for verification: 397,440 codes)

  1. The software picks each new code at random from all codes in a). Compute the probability that the code has two different letters and three different digits.

  2. Each evening, 4 trucks for 4 different customers are loaded at the warehouse. The warehouse has 7 loading docks (places where a truck is loaded), and each truck gets its own dock. Determine the number of ways to assign the 4 trucks to the docks.

  3. One of the 4 trucks is older, and its cooling unit needs a power connection. Only dock 1 has one. Determine the number of assignments in which this truck is at dock 1. If the docks were assigned at random, compute the probability that the older truck gets dock 1 and explain the result without counting.

a) Counting principle with repetition, 24 options for each letter and 10 for each digit:

\[24 \cdot 24 \cdot 10 \cdot 10 \cdot 10 = 24^2 \cdot 10^3 = 576{,}000 \text{ codes}\]

b) In 10 years, the warehouse needs \(10 \cdot 40{,}000 = 400{,}000\) codes. Since \(400{,}000 \leq 576{,}000\), the codes are enough (176,000 codes are left over).

c) Without repetition, each letter and each digit has one option less than the one before:

\[24 \cdot 23 \cdot 10 \cdot 9 \cdot 8 = 552 \cdot 720 = 397{,}440 \text{ codes}\]

Since \(397{,}440 < 400{,}000\), these codes are not enough: 2,560 codes are missing for the 10 years.

d) All 576,000 codes are equally likely:

\[P(\text{different letters and digits}) = \frac{397{,}440}{576{,}000} = 0.69\]

So about 69 % of the random codes are “easy to read”, and 31 % contain a repeated letter or digit.

e) The trucks go to different customers, so it matters which truck stands at which dock: the order matters, and no dock is used twice.

\[P(7, 4) = 7 \cdot 6 \cdot 5 \cdot 4 = 840 \text{ assignments}\]

f) The older truck has 1 option (dock 1). The other 3 trucks go to 3 of the remaining 6 docks:

\[1 \cdot P(6, 3) = 6 \cdot 5 \cdot 4 = 120 \text{ assignments}\]

With a random assignment, all 840 assignments are equally likely:

\[P(\text{older truck at dock 1}) = \frac{120}{840} = \frac{1}{7} \approx 0.1429\]

Without counting: in a random assignment, the older truck is equally likely to stand at any of the 7 docks, so dock 1 has the probability \(\frac{1}{7}\).

Typical mistake: in e), computing \(\binom{7}{4} = 35\). This only says which 4 docks are used, not which truck stands where. Each choice of 4 docks can be shared out among the 4 trucks in \(4! = 24\) ways: \(35 \cdot 24 = 840\).

Problem 10: Pilot Stores of a Pet Supply Chain (xxx)

A pet supply chain has 19 stores, 6 of them in shopping centres. It wants to test a new self-checkout (customers scan and pay for their items themselves) in 4 of its stores. At first, the 4 pilot stores are drawn by lot, so every group of 4 stores is equally likely.

  1. Determine the number of possible groups of pilot stores and give a reason for your method.

  2. Compute the probability that exactly one of the pilot stores is in a shopping centre.

  3. Compute the probability that at least one of the pilot stores is in a shopping centre.

(for verification: the probability that no pilot store is in a shopping centre is about 0.1845)

  1. The management wants at least 2 pilot stores in shopping centres, because these stores have the most customers. Compute the probability that a group drawn by lot meets this wish.

  2. The management decides to choose the pilot stores itself. First, it chooses a lead store, which trains the staff of the other pilot stores and must be in a shopping centre. Then it chooses 3 more stores from the remaining 18. Determine the number of ways to do this. Explain why this number is larger than the number of groups in a).

a) The pilot stores form a group without an order, and no store is drawn twice, so this is a combination of 4 from 19:

\[\binom{19}{4} = \frac{19 \cdot 18 \cdot 17 \cdot 16}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{93{,}024}{24} = 3{,}876 \text{ groups}\]

b) 1 of the 6 shopping-centre stores and 3 of the \(19 - 6 = 13\) other stores:

\[P(\text{exactly one}) = \frac{\binom{6}{1} \cdot \binom{13}{3}}{\binom{19}{4}} = \frac{6 \cdot 286}{3{,}876} = \frac{1{,}716}{3{,}876} \approx 0.4427\]

c) Complement: no pilot store in a shopping centre, i.e. all 4 from the 13 other stores:

\[P(\text{none}) = \frac{\binom{13}{4}}{\binom{19}{4}} = \frac{715}{3{,}876} \approx 0.1845\]

\[P(\text{at least one}) = 1 - \frac{715}{3{,}876} = \frac{3{,}161}{3{,}876} \approx 0.8155\]

d) The complement of “at least 2” is “at most 1”, i.e. none or exactly one:

\[P(\text{at least 2}) = 1 - \frac{715 + 1{,}716}{3{,}876} = \frac{1{,}445}{3{,}876} \approx 0.3728\]

A group drawn by lot meets the wish only with a probability of about 37 %. So the lot is not a good way to get the pilot group that the management wants.

e) Counting principle: 6 options for the lead store, then a combination of 3 from the remaining 18 stores:

\[6 \cdot \binom{18}{3} = 6 \cdot \frac{18 \cdot 17 \cdot 16}{3 \cdot 2 \cdot 1} = 6 \cdot 816 = 4{,}896\]

This is larger than 3,876 because a result now consists of a group and its lead store. A group with 2 shopping-centre stores appears twice (each of the two can be the lead store), a group with 3 such stores three times, a group with 4 such stores four times. Only the groups without a shopping-centre store do not appear at all.

Check with the counts of b), c) and \(\binom{6}{2}\binom{13}{2} = 1{,}170\), \(\binom{6}{3}\binom{13}{1} = 260\), \(\binom{6}{4} = 15\):

\[1 \cdot 1{,}716 + 2 \cdot 1{,}170 + 3 \cdot 260 + 4 \cdot 15 = 1{,}716 + 2{,}340 + 780 + 60 = 4{,}896 \;\checkmark\]

Typical mistake: in d), computing \(P(\text{at least 2}) = 1 - P(\text{none}) \approx 0.8155\). This is “at least 1”. The complement of “at least 2” also removes the groups with exactly one shopping-centre store.

D: FSP Problem

Work on this problem as in the exam: write down every step. The points show what each part is worth.

FSP Problem: Granola of a Breakfast Start-up [20 pts. total]

A start-up sells granola (baked oat flakes with nuts and fruit) in its web shop. Give probabilities as decimals with four decimal places.

Part a)

In the web shop, customers can put together their own granola in a configurator (a tool in which customers choose the parts of their product). They choose one of 3 bases (oats, spelt, buckwheat), one of 6 fruit mixes and one of 3 sweeteners (honey, maple syrup, none). Determine the number of different granolas. For technical reasons, the buckwheat base cannot be combined with honey. Determine the number of granolas that the configurator offers. [3 pts.]

Counting principle: three choices one after the other:

\[3 \cdot 6 \cdot 3 = 54 \text{ granolas}\]

Excluded granolas: buckwheat (1 option) with honey (1 option) and any of the 6 fruit mixes: \(1 \cdot 6 \cdot 1 = 6\).

\[54 - 6 = 48 \text{ granolas}\]

Check by cases: oats or spelt with any sweetener, \(2 \cdot 6 \cdot 3 = 36\), plus buckwheat with maple syrup or none, \(1 \cdot 6 \cdot 2 = 12\), gives \(36 + 12 = 48\) \(\checkmark\)

Grading: 1 Pt. 54 by the counting principle, 1 Pt. the 6 excluded granolas, 1 Pt. 48.

Part b)

Apart from the configurator, the start-up sells 16 fixed recipes, 7 of them without added sugar. For a consumer test, it selects 4 of the 16 recipes. Determine the number of possible selections and give a reason for your method. [3 pts.]

Method: the test contains the same 4 recipes no matter in which order they were selected, so the order does not matter, and no recipe is selected twice. This is a combination:

\[\binom{16}{4} = \frac{16!}{4! \cdot 12!} = \frac{16 \cdot 15 \cdot 14 \cdot 13}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{43{,}680}{24} = 1{,}820 \text{ selections}\]

Grading: 1 Pt. reason (order does not matter, no repetition), 1 Pt. combination formula, 1 Pt. 1,820.

Part c)

Each tester tastes the 4 granolas of the test one after the other. Determine the number of possible orders. After the tasting, each tester names a favourite and a second favourite among the 4 granolas. Determine the number of possible answers and explain why it is not \(\binom{4}{2}\). [3 pts.]

Tasting orders: all 4 granolas in a row, a permutation of all 4:

\[4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 \text{ orders}\]

Favourite and second favourite: the order matters, because “A favourite, B second” is a different answer from “B favourite, A second”, and no granola is named twice:

\[P(4, 2) = 4 \cdot 3 = 12 \text{ answers}\]

\(\binom{4}{2} = 6\) only counts which 2 granolas are named, not which of them is the favourite. Each of these 6 pairs gives \(2! = 2\) answers: \(6 \cdot 2 = 12\).

Grading: 1 Pt. 24 orders, 1 Pt. 12 answers, 1 Pt. explanation.

Part d)

The 4 recipes for the test are drawn by lot from the 16 recipes. Compute the probability for the following events:

(1) exactly 3 of the 4 granolas are without added sugar

(2) at least one of the 4 granolas is without added sugar

(3) the test contains both kinds, i.e. at least one granola with and at least one granola without added sugar

[6 pts.]

All 1,820 selections from part b) are equally likely. 7 recipes are without added sugar, \(16 - 7 = 9\) recipes have added sugar.

(1) 3 of the 7 recipes without added sugar and 1 of the 9 others:

\[P(\text{exactly } 3) = \frac{\binom{7}{3} \cdot \binom{9}{1}}{\binom{16}{4}} = \frac{35 \cdot 9}{1{,}820} = \frac{315}{1{,}820} \approx 0.1731\]

(2) Complement: none of the 4 is without added sugar, i.e. all 4 come from the 9 recipes with added sugar:

\[P(\text{at least one}) = 1 - \frac{\binom{9}{4}}{\binom{16}{4}} = 1 - \frac{126}{1{,}820} = \frac{1{,}694}{1{,}820} \approx 0.9308\]

(3) Complement: all 4 granolas are of one kind, i.e. all 4 without added sugar (\(\binom{7}{4} = 35\)) or all 4 with added sugar (\(\binom{9}{4} = 126\)):

\[P(\text{both kinds}) = 1 - \frac{35 + 126}{1{,}820} = \frac{1{,}659}{1{,}820} \approx 0.9115\]

Grading: 2 Pts. per event: (1) 1 Pt. \(\binom{7}{3} \cdot \binom{9}{1}\), 1 Pt. quotient. (2) 1 Pt. complement “none”, 1 Pt. result. (3) 1 Pt. the two cases of one kind, 1 Pt. result.

Part e)

In a second test, each tester compares the granolas in pairs: for every pair of two different granolas, the tester says which one tastes better. Show that for \(n\) granolas there are \(\frac{n(n-1)}{2}\) pairs. The start-up wants every tester to make exactly 91 comparisons. Determine the number of granolas in the second test. [5 pts.]

Number of pairs: a pair is a selection of 2 of the \(n\) granolas, and the pair “A and B” is the same as “B and A”, so the order does not matter:

\[\binom{n}{2} = \frac{n!}{2! \cdot (n-2)!} = \frac{n \cdot (n-1) \cdot (n-2)!}{2 \cdot (n-2)!} = \frac{n(n-1)}{2}\]

Equation in zero form:

\[\frac{n(n-1)}{2} = 91 \iff n^2 - n = 182 \iff n^2 - n - 182 = 0\]

Quadratic formula with \(a = 1\), \(b = -1\), \(c = -182\):

\[n = \frac{1 \pm \sqrt{(-1)^2 - 4 \cdot 1 \cdot (-182)}}{2 \cdot 1} = \frac{1 \pm \sqrt{729}}{2} = \frac{1 \pm 27}{2}\]

\[n_1 = 14, \qquad n_2 = -13\]

A number of granolas cannot be negative, so the second test contains 14 granolas.

Check: \(\frac{14 \cdot 13}{2} = \frac{182}{2} = 91\) \(\checkmark\)

Grading: 1 Pt. \(\binom{n}{2} = \frac{n(n-1)}{2}\) with the reason, 1 Pt. equation in zero form, 1 Pt. quadratic formula with the discriminant 729, 1 Pt. both solutions and \(n = 14\) with the reason, 1 Pt. check.

Calculator Practice

The FX-991DE X has three keys for this session: \(n!\) is SHIFT + x⁻¹ (x!), \(P(n, r)\) is SHIFT + × (nPr) and \(\binom{n}{r}\) is SHIFT + ÷ (nCr). Always type \(n\) first, then the keys, then \(r\). In the exam you still write the formula and your steps. The calculator does the arithmetic and checks your result.

Problem 11: Calculator: Factorials (x)

  1. Compute \(12!\) with the x! key.

  2. Check your hand result from Problem 2 b), \(\frac{11!}{9! \cdot 2!} = 55\), with the calculator.

  3. Try to compute \(\frac{80!}{78!}\) with the x! key. Then compute it by cancelling as in Problem 2 c) and with the nPr key, and explain the difference.

  1. \(12!\)
    • Enter: 12 SHIFT x⁻¹ =
    • Result: 479,001,600
  2. \(\frac{11!}{9! \cdot 2!}\)
    • Enter: 11 SHIFT x⁻¹ ÷ ( 9 SHIFT x⁻¹ × 2 SHIFT x⁻¹ ) =
    • Result: 55, the same as by hand ✓
  3. \(\frac{80!}{78!}\)
    • Enter: 80 SHIFT x⁻¹ =
    • Result: an error message. \(80!\) has 119 digits, but the calculator only works with numbers below \(10^{100}\) (the largest factorial it can show is \(69!\)).
    • By cancelling: \(\frac{80!}{78!} = \frac{80 \cdot 79 \cdot 78!}{78!} = 80 \cdot 79 = 6{,}320\)
    • With nPr: \(\frac{80!}{78!} = P(80, 2)\), Enter: 80 SHIFT × 2 =, Result: 6,320 ✓

So for large \(n\), cancel first or use nPr. The x! key alone fails.

Problem 12: Calculator: nPr and nCr (x)

  1. Check your hand results from Problem 4 a) and b), \(\binom{17}{4} = 2{,}380\) and \(P(9, 5) = 15{,}120\), with the calculator.

  2. Compute \(\binom{22}{3}\) and \(\binom{22}{19}\) and explain why the two numbers are equal.

  3. Compute \(P(22, 3)\) and check that it is \(3!\) times \(\binom{22}{3}\).

  1. \(\binom{17}{4}\) and \(P(9, 5)\)
    • Enter: 17 SHIFT ÷ 4 =
    • Result: 2,380 ✓
    • Enter: 9 SHIFT × 5 =
    • Result: 15,120 ✓
  2. \(\binom{22}{3}\) and \(\binom{22}{19}\)
    • Enter: 22 SHIFT ÷ 3 =, then 22 SHIFT ÷ 19 =
    • Result: 1,540 both times
    • Choosing the 3 objects you take from 22 is the same as choosing the 19 objects you leave behind, as in Problem 5 b).
  3. \(P(22, 3)\)
    • Enter: 22 SHIFT × 3 =
    • Result: 9,240
    • Check: \(1{,}540 \cdot 3! = 1{,}540 \cdot 6 = 9{,}240\) ✓

Problem 13: Calculator: Choosing the Right Key (x)

For each situation, decide whether you need a power, nPr or nCr. Then compute the number with the calculator.

  1. A bike lock has 4 rings, and each ring shows one of 8 symbols. Symbols may repeat. How many settings does the lock have?

  2. A company chooses 5 of its 25 trainees for a trade fair. All 5 do the same job at the stand. How many groups are possible?

  3. The 25 trainees present their projects, and a jury gives a first, a second and a third prize. How many results are possible?

  1. Power: 4 rings, 8 options each, repetition allowed
    • Enter: 8 x^ 4 =
    • Result: \(8^4 = 4{,}096\) settings
  2. nCr: the order does not matter, nobody is chosen twice
    • Enter: 25 SHIFT ÷ 5 =
    • Result: \(\binom{25}{5} = 53{,}130\) groups
  3. nPr: the order matters (first prize is not third prize), nobody wins twice
    • Enter: 25 SHIFT × 3 =
    • Result: \(P(25, 3) = 13{,}800\) results

Problem 14: Calculator: Large Counts (xx)

A bakery chain has 36 branches, 10 of them at train stations. The food safety office inspects 6 of the branches, chosen at random.

  1. Determine the number of possible groups of 6 branches.

  2. The office visits the 6 branches on 6 different days, so the order matters. Determine the number of possible visit plans and check that it is \(6!\) times the result of a).

  3. Compute the probability that exactly 2 of the 6 inspected branches are at train stations.

  4. Compute the probability that at least one of the 6 inspected branches is at a train station.

  1. Groups: combination of 6 from 36
    • Enter: 36 SHIFT ÷ 6 =
    • Result: \(\binom{36}{6} = 1{,}947{,}792\) groups
  2. Visit plans: permutation of 6 from 36
    • Enter: 36 SHIFT × 6 =
    • Result: \(P(36, 6) = 1{,}402{,}410{,}240\) visit plans
    • Check: \(1{,}947{,}792 \cdot 720 = 1{,}402{,}410{,}240\) ✓
  3. Exactly 2 at train stations: 2 of the 10 station branches and 4 of the \(36 - 10 = 26\) other branches
    • Enter: 10 SHIFT ÷ 2 × 26 SHIFT ÷ 4 ÷ 36 SHIFT ÷ 6 =
    • Result: \(\frac{45 \cdot 14{,}950}{1{,}947{,}792} = \frac{672{,}750}{1{,}947{,}792} \approx 0.3454\)
  4. At least one: complement of “no branch at a train station”, all 6 from the 26 other branches
    • Enter: 1 − 26 SHIFT ÷ 6 ÷ 36 SHIFT ÷ 6 =
    • Result: \(1 - \frac{230{,}230}{1{,}947{,}792} \approx 0.8818\)

By hand, \(\binom{36}{6}\) alone needs a product of six numbers divided by \(720\). The calculator does it in one step.