Permutations & Combinations - Finite Mathematics

1. A company has 10 software engineers. A team of 4 is to be selected for a new project. Among the engineers, there are 3 senior engineers: Alex, Ben, and Carla. How many teams can be formed if the team must include at least one of these three senior engineers?
   Answer: 175 This problem is most efficiently solved using the complement rule. First, calculate the total number of 4-person teams that can be formed from 10 engineers, without any restrictions. This is $\binom{10}{4}$. Total teams = $\binom{10}{4} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 10 \times 3 \times 7 = 210$. Next, calculate the number of teams that have none of the specified senior engineers. This means selecting a team of 4 from the other $10 - 3 = 7$ engineers. Teams with no seniors = $\binom{7}{4} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$. The number of teams with at least one senior engineer is the total number of teams minus the number of teams with no senior engineers: $210 - 35 = 175$.
2. A host is seating 8 guests around a circular table. Two of the guests, Alice and Bob, must not be seated next to each other. How many seating arrangements are possible?
   Answer: 3,600 This problem is best solved using the complement rule. First, find the total number of ways to seat 8 guests around a circular table, which is $(8-1)! = 7! = 5,040$. Next, find the number of arrangements where Alice and Bob do sit together. Treat Alice and Bob as a single unit. Now we are arranging 7 entities (the Alice-Bob unit and the other 6 guests) in a circle, which can be done in $(7-1)! = 6! = 720$ ways. The Alice-Bob unit can be arranged in $2! = 2$ ways (Alice on the left or Bob on the left). So, there are $720 \times 2 = 1,440$ arrangements where they are together. The number of arrangements where they are not together is the total minus this amount: $5,040 - 1,440 = 3,600$.
3. How many 6-digit numbers can be formed using the digits 1, 2, 3, 4, 5, 6 (without repetition) such that the number is divisible by 5 and the digits are in non-decreasing order?
   Answer: 0 For a number to be divisible by 5, it must end in 0 or 5. Since we can only use digits 1, 2, 3, 4, 5, 6, the number must end in 5. For the digits to be in non-decreasing order, we need: $d_1 ≤ d_2 ≤ d_3 ≤ d_4 ≤ d_5 ≤ d_6$. Since the last digit must be 5, we need $d_1 ≤ d_2 ≤ d_3 ≤ d_4 ≤ d_5 ≤ 5$. However, we must use each of the 6 digits exactly once (without repetition). If $d_6 = 5$, then we need to arrange digits 1, 2, 3, 4, 6 in non-decreasing order for the first 5 positions. This would require $1 ≤ 2 ≤ 3 ≤ 4 ≤ 6 ≤ 5$. But $6 ≤ 5$ is false since $6 > 5$. Therefore, it's impossible to arrange the digits 1, 2, 3, 4, 6 in non-decreasing order when followed by 5. Hence, no such 6-digit numbers exist.
4. A bookshelf contains 5 distinct fantasy books, 4 distinct mystery books, and 3 distinct science fiction books. In how many ways can a person choose 4 books to read, if they must select at least one fantasy book and at least one mystery book?
   Answer: 390 We use the complement rule. The total number of books is $5+4+3=12$. The total number of ways to choose 4 books from 12 is $\binom{12}{4} = 495$. The forbidden selections are those with no fantasy books OR no mystery books. Let $A$ be the set of selections with no fantasy books and $B$ be the set of selections with no mystery books. We want to find $|A \cup B| = |A| + |B| - |A \cap B|$. $|A|$ (no fantasy): Choose 4 from the 7 non-fantasy books (4 mystery, 3 sci-fi). $\binom{7}{4} = 35$. $|B|$ (no mystery): Choose 4 from the 8 non-mystery books (5 fantasy, 3 sci-fi). $\binom{8}{4} = 70$. $|A \cap B|$ (no fantasy AND no mystery): Choose 4 from the 3 sci-fi books. $\binom{3}{4} = 0$. The number of forbidden selections is $35 + 70 - 0 = 105$. The number of valid selections is the total minus the forbidden: $495 - 105 = 390$.
5. A bakery sells 6 different types of donuts. A customer wants to buy a dozen (12) donuts. How many different selections of 12 donuts are possible?
   Answer: 6,188 This is a problem of combinations with repetition, often solved using the "stars and bars" method. We are choosing $k=12$ items (donuts) from $n=6$ categories (types). The formula for combinations with repetition is $\binom{n+k-1}{k}$ or $\binom{n+k-1}{n-1}$. Using the formula, we have $n=6$ and $k=12$. The number of possible selections is: $\binom{6+12-1}{12} = \binom{17}{12} = \binom{17}{5}$ $\binom{17}{5} = \frac{17 \times 16 \times 15 \times 14 \times 13}{5 \times 4 \times 3 \times 2 \times 1} = 17 \times 2 \times 1 \times 14 \times 13 = 6,188$
6. A company's board of directors consists of 7 men and 5 women. A 4-person subcommittee for a special project is to be formed. How many different subcommittees can be formed if the subcommittee must contain at most 2 men?
   Answer: 285 The condition "at most 2 men" means the subcommittee can have 0, 1, or 2 men. We calculate the number of ways for each case and sum them. Case 1: 0 men and 4 women. This requires choosing 0 from 7 men and 4 from 5 women: $\binom{7}{0} \binom{5}{4} = 1 \times 5 = 5$. Case 2: 1 man and 3 women. This requires choosing 1 from 7 men and 3 from 5 women: $\binom{7}{1} \binom{5}{3} = 7 \times 10 = 70$. Case 3: 2 men and 2 women. This requires choosing 2 from 7 men and 2 from 5 women: $\binom{7}{2} \binom{5}{2} = 21 \times 10 = 210$. The total number of possible subcommittees is the sum of these cases: $5 + 70 + 210 = 285$.
7. A manager needs to assign 5 different projects to 3 employees. Each employee must be assigned at least one project. In how many ways can the projects be assigned?
   Answer: 150 This is a surjective (onto) function problem. We use the Principle of Inclusion-Exclusion. First, the total number of ways to assign 5 distinct projects to 3 distinct employees without restrictions is $3^5 = 243$. From this, we subtract the assignments where at least one employee gets no projects. Let $A_i$ be the set of assignments where employee $i$ gets no project. We want to find $3^5 - |A_1 \cup A_2 \cup A_3|$. $|A_1|$: All 5 projects go to the other 2 employees, so $2^5=32$. Similarly, $|A_2|=|A_3|=32$. Sum is $\binom{3}{1} \times 2^5 = 3 \times 32 = 96$. $|A_1 \cap A_2|$: All 5 projects go to employee 3, so $1^5=1$. Similarly, $|A_1 \cap A_3|=|A_2 \cap A_3|=1$. Sum is $\binom{3}{2} \times 1^5 = 3 \times 1 = 3$. $|A_1 \cap A_2 \cap A_3|$: All projects go to 0 employees, which is 0. By PIE, $|A_1 \cup A_2 \cup A_3| = 96 - 3 + 0 = 93$. The number of valid assignments is $243 - 93 = 150$.
8. A committee of 5 people is to be selected from a group of 6 married couples. What is the total number of committees that can be formed if no married couple is on the committee together?
   Answer: 192 To form a committee with no married couple, we must select 5 people from 5 different couples. First, choose which 5 of the 6 couples will contribute a member. This can be done in $\binom{6}{5}$ ways. Then, from each of these 5 chosen couples, we must choose one of the two people. This can be done in $2^5$ ways. By the multiplication principle, the total number of committees is $\binom{6}{5} \times 2^5 = 6 \times 32 = 192$.
9. In how many ways can 4 different math books and 3 different physics books be arranged on a shelf if no two physics books can be next to each other?
   Answer: 1,440 This is a spacing problem. First, arrange the 4 distinct math books. This can be done in $4! = 24$ ways. These books create 5 possible spaces where the physics books can be placed (one at each end and one between each pair of books): _ M _ M _ M _ M _. To ensure no two physics books are adjacent, we must place each of the 3 physics books in a different space. Since the physics books are distinct, the order in which we place them matters. We need to choose 3 of the 5 spaces and arrange the 3 books in them. This is a permutation: $P(5, 3) = \frac{5!}{(5-3)!} = 5 \times 4 \times 3 = 60$. By the multiplication principle, the total number of arrangements is $4! \times P(5, 3) = 24 \times 60 = 1,440$.
10. A code consists of 5 symbols. The first 3 symbols must be uppercase letters from the English alphabet (A-Z), and the last 2 symbols must be digits (0-9). The code must satisfy the following conditions: all three letters are distinct, and the two digits are distinct. Additionally, exactly one of the letters must be a vowel (A, E, I, O, U). How many such codes are possible?
    Answer: 567,000 We calculate the number of possibilities for the letter part and the digit part separately. Letter Part (3 distinct letters, 1 vowel, 2 consonants): 1. Choose which of the 3 positions will contain the vowel: $\binom{3}{1} = 3$ ways. 2. Choose which of the 5 vowels goes in that position: 5 ways. 3. Fill the other two positions with distinct consonants (there are 21 consonants). The first can be chosen in 21 ways, the second in 20 ways. So, $21 \times 20 = 420$ ways. Total for letters: $3 \times 5 \times 21 \times 20 = 6,300$ ways. Digit Part (2 distinct digits): 1. The first digit can be any of 10 digits: 10 ways. 2. The second digit must be different from the first: 9 ways. Total for digits: $10 \times 9 = 90$ ways. Total Codes: Multiply the possibilities for both parts: $6,300 \times 90 = 567,000$.
11. From a standard 52-card deck, a 5-card hand is dealt. How many distinct hands contain exactly one pair and three other cards of different ranks from each other and from the pair?
    Answer: 1,098,240 The construction of the hand can be broken into steps: 1. Choose the rank for the pair (e.g., Kings). There are 13 ranks: $\binom{13}{1} = 13$ ways. 2. Choose 2 of the 4 suits for that rank: $\binom{4}{2} = 6$ ways. 3. Choose 3 other ranks for the remaining three cards. These must be different from the pair's rank and from each other. We choose 3 ranks from the remaining 12: $\binom{12}{3} = 220$ ways. 4. For each of these 3 ranks, choose 1 suit. There are 4 suits for each, so $\binom{4}{1} \times \binom{4}{1} \times \binom{4}{1} = 4^3 = 64$ ways. By the multiplication principle, the total number of such hands is $13 \times 6 \times 220 \times 64 = 1,098,240$.
12. A robot must travel from point A(0,0) to point B(6,4) on a Cartesian grid. The robot can only move one unit up (U) or one unit right (R) at each step. How many distinct paths are there from A to B that must pass through point P(3,2)?
    Answer: 100 The problem is broken into two independent parts: the path from A to P, and the path from P to B. 1. Path from A(0,0) to P(3,2): This requires 3 Right moves and 2 Up moves, for a total of 5 moves. The number of distinct paths is the number of ways to arrange these moves: $\binom{5}{2} = \frac{5!}{2!3!} = 10$. 2. Path from P(3,2) to B(6,4): This requires $6-3=3$ Right moves and $4-2=2$ Up moves, for a total of 5 moves. The number of distinct paths is $\binom{5}{2} = \frac{5!}{2!3!} = 10$. By the multiplication principle, the total number of paths from A to B passing through P is the product of the number of paths for each part: $10 \times 10 = 100$.
13. How many distinct arrangements of the letters in the word ENGINEERING are possible if the three Es must be kept together?
    Answer: 15,120 The word ENGINEERING has 11 letters: E(3), N(3), G(2), I(2), R(1). To keep the three E's together, we can treat EEE as a single block. Now we are arranging 9 items: (EEE), N, N, N, G, G, I, I, R. The number of permutations of these 9 items, with repetitions of N (3 times), G (2 times), and I (2 times), is given by the multinomial formula: $\frac{9!}{3!2!2!} = \frac{362,880}{6 \times 2 \times 2} = \frac{362,880}{24} = 15,120$

Start this quiz