Tasks 07-03 - Combinatorics

Section 07: Probability & Statistics

Problem 1: Fundamental Counting Principle (x)

  1. A restaurant offers 4 appetizers, 6 main courses, and 3 desserts. How many different three-course meals can be ordered?

  2. A password consists of 2 letters followed by 4 digits. How many different passwords are possible?

  3. A product code has 3 letters followed by 2 digits. If letters and digits can repeat, how many codes are possible?

  1. \(4 \times 6 \times 3 = 72\) different meals

  2. \(26 \times 26 \times 10 \times 10 \times 10 \times 10 = 26^2 \times 10^4 = 676 \times 10000 = 6,760,000\) passwords

  3. \(26 \times 26 \times 26 \times 10 \times 10 = 26^3 \times 10^2 = 17,576 \times 100 = 1,757,600\) codes

Problem 2: Factorials (x)

Calculate:

  1. \(5!\)
  2. \(8!\)
  3. \(\frac{10!}{8!}\)
  4. \(\frac{12!}{10! \cdot 2!}\)

  1. \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)

  2. \(8! = 40320\)

  3. \(\frac{10!}{8!} = \frac{10 \times 9 \times 8!}{8!} = 10 \times 9 = 90\)

  4. \(\frac{12!}{10! \cdot 2!} = \frac{12 \times 11 \times 10!}{10! \times 2} = \frac{132}{2} = 66\)

Problem 3: Permutations (x)

  1. In how many ways can 5 different books be arranged on a shelf?

  2. How many different 3-letter “words” (not necessarily real words) can be formed from the letters A, B, C, D, E if no letter can be repeated?

  3. A race has 8 runners. In how many ways can gold, silver, and bronze medals be awarded?

  1. \(5! = 120\) arrangements

  2. \(P(5,3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60\) words

  3. \(P(8,3) = \frac{8!}{5!} = 8 \times 7 \times 6 = 336\) ways

Problem 4: Combinations (x)

  1. A committee of 3 people must be selected from a group of 10. How many different committees are possible?

  2. A pizza shop offers 8 toppings. How many different 3-topping pizzas can be made?

  3. From a deck of 52 cards, how many different 5-card hands can be dealt?

  1. \(C(10,3) = \binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120\) committees

  2. \(C(8,3) = \binom{8}{3} = \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{6} = 56\) pizzas

  3. \(C(52,5) = \binom{52}{5} = \frac{52!}{5! \cdot 47!} = \frac{52 \times 51 \times 50 \times 49 \times 48}{120} = 2,598,960\) hands

Problem 5: Permutations vs. Combinations (xx)

Determine whether each situation involves permutations or combinations, then solve:

  1. Selecting 4 students from a class of 20 to represent the class at a conference.

  2. Arranging 4 students from a class of 20 in a line for a photo (positions matter).

  3. Choosing 3 flavors of ice cream from 12 available flavors.

  4. Ranking your top 3 favorite movies from a list of 10.

  1. Combination (order doesn’t matter - just selecting representatives) \(C(20,4) = \frac{20!}{4! \cdot 16!} = \frac{20 \times 19 \times 18 \times 17}{24} = 4845\)

  2. Permutation (order matters - different positions in photo) \(P(20,4) = \frac{20!}{16!} = 20 \times 19 \times 18 \times 17 = 116,280\)

  3. Combination (order doesn’t matter - just choosing flavors) \(C(12,3) = \frac{12!}{3! \cdot 9!} = \frac{12 \times 11 \times 10}{6} = 220\)

  4. Permutation (order matters - 1st, 2nd, 3rd favorite) \(P(10,3) = 10 \times 9 \times 8 = 720\)

Problem 6: Permutations with Repetition (xx)

  1. How many different “words” can be formed using all the letters in MISSISSIPPI?

  2. How many different arrangements are possible for the letters in STATISTICS?

  3. A shelf has 3 identical math books, 4 identical physics books, and 2 identical chemistry books. How many ways can they be arranged?

  1. MISSISSIPPI has 11 letters: M(1), I(4), S(4), P(2) \(\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = \frac{39916800}{1152} = 34,650\)

  2. STATISTICS has 10 letters: S(3), T(3), A(1), I(2), C(1) \(\frac{10!}{3! \cdot 3! \cdot 1! \cdot 2! \cdot 1!} = \frac{3628800}{6 \times 6 \times 1 \times 2 \times 1} = \frac{3628800}{72} = 50,400\)

  3. 9 books total: 3 math, 4 physics, 2 chemistry \(\frac{9!}{3! \cdot 4! \cdot 2!} = \frac{362880}{6 \times 24 \times 2} = \frac{362880}{288} = 1,260\)

Problem 7: Combinations with Conditions (xx)

From a group of 8 men and 6 women:

  1. How many committees of 5 can be formed?

  2. How many committees of 5 with exactly 3 men and 2 women can be formed?

  3. How many committees of 5 with at least 3 women can be formed?

  1. Total people = 14 \(C(14,5) = \frac{14!}{5! \cdot 9!} = 2002\)

  2. Choose 3 men from 8 AND 2 women from 6: \(C(8,3) \times C(6,2) = 56 \times 15 = 840\)

  3. At least 3 women means: 3W+2M OR 4W+1M OR 5W+0M

    3W, 2M: \(C(6,3) \times C(8,2) = 20 \times 28 = 560\) 4W, 1M: \(C(6,4) \times C(8,1) = 15 \times 8 = 120\) 5W, 0M: \(C(6,5) \times C(8,0) = 6 \times 1 = 6\)

    Total: \(560 + 120 + 6 = 686\)

Problem 8: Probability with Counting (xx)

A standard deck has 52 cards (13 cards in each of 4 suits).

  1. If 5 cards are dealt, what is the probability of getting all hearts?

  2. What is the probability of getting exactly 3 aces in a 5-card hand?

  3. What is the probability of getting a “full house” (3 of one rank, 2 of another)?

Total 5-card hands: \(C(52,5) = 2,598,960\)

  1. All hearts: Choose 5 from 13 hearts \(P = \frac{C(13,5)}{C(52,5)} = \frac{1287}{2598960} = 0.000495\) (about 0.05%)

  2. Exactly 3 aces: Choose 3 aces from 4, AND choose 2 non-aces from 48 \(P = \frac{C(4,3) \times C(48,2)}{C(52,5)} = \frac{4 \times 1128}{2598960} = \frac{4512}{2598960} = 0.00174\) (about 0.17%)

  3. Full house:

    • Choose rank for three-of-a-kind: 13 ways
    • Choose 3 suits from 4: \(C(4,3) = 4\) ways
    • Choose rank for pair: 12 ways (remaining ranks)
    • Choose 2 suits from 4: \(C(4,2) = 6\) ways

    Full houses: \(13 \times 4 \times 12 \times 6 = 3744\)

    \(P = \frac{3744}{2598960} = 0.00144\) (about 0.14%)

Problem 9: Business Applications (xx)

  1. A company needs to select 4 employees from 12 for a project team. How many ways can this be done?

  2. A manager must assign 4 different tasks to 4 of her 10 employees (one task per person). How many ways can this be done?

  3. A product code consists of 2 letters (A-Z) followed by 3 digits (0-9). If repetition is allowed, how many codes are possible? If repetition is NOT allowed?

  1. \(C(12,4) = \frac{12!}{4! \cdot 8!} = \frac{12 \times 11 \times 10 \times 9}{24} = 495\) ways

  2. This is assigning specific tasks, so order matters: \(P(10,4) = 10 \times 9 \times 8 \times 7 = 5040\) ways

  3. With repetition: \(26 \times 26 \times 10 \times 10 \times 10 = 676,000\) codes

    Without repetition: \(26 \times 25 \times 10 \times 9 \times 8 = 468,000\) codes

Problem 10: Pascal’s Triangle and Binomial Coefficients (xx)

  1. Write out the first 6 rows of Pascal’s triangle.

  2. Use Pascal’s triangle to find \(\binom{5}{2}\) and \(\binom{5}{3}\).

  3. Verify that \(\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}\) using \(n=4\), \(r=2\).

  4. Expand \((x+y)^4\) using binomial coefficients.

  1. Pascal’s Triangle (rows 0-5):

    Row 0:           1
Row 1:          1 1
Row 2:         1 2 1
Row 3:        1 3 3 1
Row 4:       1 4 6 4 1
Row 5:      1 5 10 10 5 1

  2. From row 5: \(\binom{5}{2} = 10\) and \(\binom{5}{3} = 10\)

  3. \(\binom{4}{2} + \binom{4}{3} = 6 + 4 = 10\) \(\binom{5}{3} = 10\) ✓

  4. \((x+y)^4 = \binom{4}{0}x^4 + \binom{4}{1}x^3y + \binom{4}{2}x^2y^2 + \binom{4}{3}xy^3 + \binom{4}{4}y^4\) \(= x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4\)

Problem 11: Complex Counting Problems (xxx)

  1. How many 4-digit numbers can be formed using digits 1, 2, 3, 4, 5, 6 if:

    • Repetition is allowed?
    • Repetition is not allowed?
    • The number must be even (no repetition)?

  2. A club with 15 members needs to elect a president, vice president, secretary, and treasurer. No one can hold more than one position. How many ways can this be done?

  3. From 8 different books, how many ways can you select 3 to give as gifts to 3 different friends (each friend gets one book)?

  1. With repetition: \(6^4 = 1296\)

    Without repetition: \(P(6,4) = 6 \times 5 \times 4 \times 3 = 360\)

    Even, no repetition: Last digit must be 2, 4, or 6

    • If last digit is 2: \(5 \times 4 \times 3 \times 1 = 60\) ways
    • If last digit is 4: \(5 \times 4 \times 3 \times 1 = 60\) ways
    • If last digit is 6: \(5 \times 4 \times 3 \times 1 = 60\) ways
    • Total: \(60 + 60 + 60 = 180\)

  2. \(P(15,4) = 15 \times 14 \times 13 \times 12 = 32,760\) ways

  3. First select 3 books: \(C(8,3) = 56\) Then arrange them among 3 friends: \(3! = 6\) Total: \(56 \times 6 = 336\) ways

    Or equivalently: \(P(8,3) = 8 \times 7 \times 6 = 336\)

Problem 12: Comprehensive Problem (xxxx)

A small business has 5 managers and 10 regular employees.

  1. How many ways can a committee of 4 be formed from all employees?

  2. How many ways can a committee of 4 be formed with at least 2 managers?

  3. If the committee must have a chair, vice-chair, secretary, and member, and the chair must be a manager, how many ways can the committee be formed?

  4. What is the probability that a randomly selected 4-person committee has exactly 1 manager?

Total employees: 15 (5 managers + 10 regular)

  1. \(C(15,4) = \frac{15!}{4! \cdot 11!} = 1365\) ways

  2. At least 2 managers: 2M+2R OR 3M+1R OR 4M+0R

    2M, 2R: \(C(5,2) \times C(10,2) = 10 \times 45 = 450\) 3M, 1R: \(C(5,3) \times C(10,1) = 10 \times 10 = 100\) 4M, 0R: \(C(5,4) \times C(10,0) = 5 \times 1 = 5\)

    Total: \(450 + 100 + 5 = 555\) ways

  3. Chair (must be manager): 5 choices Remaining 3 positions from remaining 14 people: \(P(14,3) = 14 \times 13 \times 12 = 2184\)

    Total: \(5 \times 2184 = 10,920\) ways

  4. Exactly 1 manager: \(C(5,1) \times C(10,3) = 5 \times 120 = 600\)

    \(P = \frac{600}{1365} = \frac{40}{91} \approx 0.440\) (about 44%)