Permutations and Combinations · Lesson 5 of 6
Combining Counting Methods
“Choose and combine methods for group conditions, dictionary order, repeated digits and separated seating.”
• Count outcomes that first require selection and then arrangement. • Translate “exactly” and “at least” into complete, separate cases. • Locate an arrangement in dictionary order using prefix counts. • Count repeated-digit numbers with a leading-zero restriction in two ways. • Use gaps to ensure that specified people are not adjacent.
Choose a method for each part of the task
A harder counting problem may need more than one formula. Selecting the objects and arranging the selected objects are different decisions. Repetition, fixed positions and adjacency conditions may affect different stages. Write those stages down before doing arithmetic, so every factor has a clear purpose.
A useful approach is to describe the final outcome, note which objects are distinct, identify whether order matters, and translate every restriction. Then decide whether the task is a product of required choices, a sum of alternatives, or a total with forbidden outcomes removed. The method follows from this description.
Select first, then arrange
When a word must contain a stated number of vowels and consonants, choosing its letters does not determine their order. First choose which letters will be used. Then arrange that fixed collection. Because all letters are distinct in the following example, every selected collection has the same number of arrangements.
Problem
How many five-letter strings contain 3 vowels and 2 consonants chosen from INVOLUTE, without repeating a letter?
- 1.The four vowels are I, O, U and E; the four consonants are N, V, L and T. All eight letters are different.
- 2.Choose three vowels in ⁴C₃=4 ways and two consonants in ⁴C₂=6 ways. Together these choices produce 4 × 6 = 24 five-letter sets.
- 3.Each set contains five distinct letters. Arrange it in 5! = 120 ways.
- 4.Multiply: 24 × 120 = 2880. Every resulting string identifies its selected set uniquely, so there is no double counting.
When the output is a word or seating arrangement, selection alone may be incomplete. When the output is a committee, adding an arrangement factor may overcount. Also, do not assume a common r! arrangement factor if selected collections can contain different repeated-letter patterns.
Exact and “at least” conditions
An exact condition specifies one composition. “At least” often allows several compositions, and each must be checked against the available objects. Cases based on the number of girls, boys, red cards or another category are naturally separate because one outcome has one definite category count.
Problem
From 4 girls and 7 boys, select a five-person team with (a) no girl, (b) at least one boy and one girl, or (c) at least three girls.
- 1.(a) Choose all five from the seven boys: ⁷C₅=21.
- 2.(b) The possible girl counts are 1, 2, 3 and 4. The corresponding counts are ⁴C₁ × ⁷C₄=140, ⁴C₂ × ⁷C₃=210, ⁴C₃ × ⁷C₂=84 and ⁴C₄ × ⁷C₁=7.
- 3.Add the cases: 140 + 210 + 84 + 7 = 441. Alternatively, all teams number ¹¹C₅=462. Subtract the 21 all-boy teams; an all-girl five-person team is impossible because only four girls are available. This again gives 441.
- 4.(c) At least three girls means exactly three or exactly four. The count is ⁴C₃ × ⁷C₂+⁴C₄ × ⁷C₁=84+7=91. Five girls cannot be selected from four.
The direct-case solution and the complement solution in part (b) count the same set in different ways. Comparing them is a useful check. A complement is convenient only if the forbidden outcomes are easy to count and any overlapping forbidden cases are handled correctly.
Dictionary order counts blocks of prefixes
Dictionary order compares letters from left to right. At the first position where two strings differ, the alphabetically earlier letter comes first. All strings beginning with A therefore precede all those beginning with G, which precede those beginning with I, and so on.
Instead of listing every word, count how many have each first letter. Each group forms a consecutive block in the dictionary list. Once you find the block containing the required position, fix that prefix and repeat the same reasoning with the remaining letters. Repeated letters must be treated as identical during these counts.
Problem
Use every letter of AGAIN. Count the distinct arrangements and find the 50th in dictionary order.
- 1.There are five letters with two identical As, so the total is 5!/2! = 60. The alphabetical order of available letter kinds is A, G, I, N.
- 2.Fix A first: the remaining A, G, I and N are distinct, giving 4! = 24 words, positions 1–24.
- 3.Fix G first: remaining A, A, I, N give 4!/2! = 12 words, positions 25–36. Fix I first: remaining A, A, G, N likewise give 12, positions 37–48.
- 4.The 50th word is therefore second in the block beginning with N. The earliest remaining arrangement is AAGI, producing NAAGI at position 49. The next is AAIG, producing NAAIG at position 50.
- 5.To justify the last step without guessing, fix NA and then NAA. Only G and I remain. Their two orders GI and IG give the first two words of the N block.
| First letter | Number of arrangements | Positions |
|---|---|---|
| A | 24 | 1–24 |
| G | 12 | 25–36 |
| I | 12 | 37–48 |
| N | 12 | 49–60 |
Repeated digits and a forbidden first position
A list such as 1, 2, 0, 2, 4, 2, 4 gives a fixed inventory. It supplies three copies of 2 and two copies of 4, rather than an unlimited option to repeat any digit. Use the repeated-object formula, then impose the number restriction.
Problem
Using all digits 1, 2, 0, 2, 4, 2, 4 exactly as supplied, how many numbers greater than 1000000 can be formed?
- 1.All seven digits must be used. Any arrangement with nonzero first digit is a seven-digit number greater than 1000000: a number beginning with 2 or 4 clearly exceeds it, and one beginning with 1 has nonzero digits among its remaining positions.
- 2.Method 1: split by first digit. Starting with 1 leaves 0, 2, 2, 2, 4, 4 and gives 6!/(3!2!) = 60.
- 3.Starting with 2 leaves two 2s and two 4s, giving 6!/(2!2!) = 180. Starting with 4 leaves three 2s and one 4, giving 6!/3! = 120. Add: 60 + 180 + 120 = 360.
- 4.Method 2: all seven-symbol arrangements give 7!/(3!2!) = 420. Those beginning with zero give 6!/(3!2!) = 60. Subtract: 420 − 60 = 360.
- 5.Notice that fixing a repeated first digit reduces its multiplicity. The denominator for a number beginning with 2 therefore differs from that for a number beginning with 1.
Gaps keep people separated
To stop two boys from sitting next to one another, first arrange the girls. The spaces before the first girl, between successive girls and after the last girl form possible gaps for boys. Allowing at most one boy in each chosen gap ensures separation.
Five girls create six gaps, including both ends. After a particular arrangement of the girls, the gaps are distinct positions from left to right. Choose which gaps are used and which boy occupies each one. These are both necessary decisions because the boys are distinct people.
Problem
Seat five distinct girls and three distinct boys in a row so that no two boys are adjacent.
- 1.Arrange the five girls in 5! = 120 ways. Every such arrangement produces six gaps.
- 2.Choose three of those gaps in ⁶C₃=20 ways, then assign the three boys to them in 3! = 6 ways.
- 3.For each girl order, this gives 20 × 6 = 120 placements. Equivalently assign the boys directly to different gaps in ⁶P₃=120 ways.
- 4.Multiply by the girl orders: 5! × ⁶P₃ = 120 × 120 = 14400.
- 5.Each valid seating uniquely determines the left-to-right girl order, the occupied gaps and the boy assignments, so the stages do not duplicate outcomes.
The gap method imposes “no two boys adjacent”, which is stronger than “the boys are not all together”. A block method counts all boys together; its complement still permits a neighbouring pair with the remaining boy elsewhere. The diagram helps keep these two requirements separate.
Quiz
Choose 3 of 4 distinct vowels and 2 of 4 distinct consonants, then form a five-letter string. What is the count?
A five-person team from 4 girls and 7 boys has at least 3 girls. Which girl counts are possible?
What is the 50th dictionary arrangement of AGAIN?
Five people in a row create how many gaps, including the two ends?
When the first digit is fixed as 2 in the inventory 0, 1, 2, 2, 2, 4, 4, which denominator remains?
Why is choosing gaps alone insufficient for seating distinct boys?
Practice Problems
- Create five-letter strings with 2 vowels and 3 consonants chosen from DAUGHTER without repetition.
- For a five-person team from 4 girls and 7 boys, count teams with exactly 2 girls and teams with at most 2 girls.
- Find the first and last dictionary arrangements of AGAIN, then explain how prefix counts locate the 37th.
- Verify the count 360 for the supplied repeated-digit inventory by a first-digit case table.
- Seat four distinct girls and two distinct boys with no boys adjacent. Include end gaps.
- Explain why using a single boy block and subtracting its count from 8! does not solve the five-girl, three-boy separation problem.
Key Takeaways
• Selection and arrangement are separate stages when both affect the result. • List feasible category counts before adding “at least” cases. • Dictionary order forms consecutive blocks with the same prefix. • Fixing a repeated symbol changes its remaining multiplicity. • g separators in a row create g + 1 gaps, including the ends. • Assign distinct objects to chosen gaps; choosing gaps alone is incomplete.