Counting with restrictions
Seven cars park in a row of seven spaces, and the two red cars must be side by side. How many ways are there, when a rule ties some objects to places or to each other?
Where you are 10 in Counting
When you reach for it
The factorial counts every order of a set, and P(n, r) counts the rows of r objects chosen from n. Both assume that any object may go in any place. Real arrangements usually come with a rule attached: a given speaker must go last, the leader must hold a first-aid certificate, two cars must park side by side, a word must not start with a given letter, a number must be even.
A rule like that is a restriction. Reach for this move whenever the question still asks “how many orders” or “how many rows”, but some of the rows are not allowed. The tools are the ones already known, the fundamental counting principle and the complement; what is new is the order in which the places are filled, and the habit of choosing which side of the rule to count.
The procedure
Fill the restricted place first. The counting principle multiplies the number of choices at each stage, and that is only allowed when the number at a stage is the same whatever happened before. A free place does not care what went earlier, but a restricted place does. Suppose the leader of a hiking group of 10 must be one of the 3 members with a first-aid certificate. If the leader is chosen first there are exactly 3 choices, and then the free places take what is left. If the leader were chosen last, the number of certificate holders still available would depend on whether some had already been used in the earlier places, and the product would have no single factor to write down. So the place carrying the rule goes first, and the free places, which always have “however many are left”, go after.
When the restricted place still depends on earlier choices, split into cases. Sometimes two places carry rules that reach into each other: a four-digit number may not start with 0 and must end in an even digit, and 0 is itself even. Then no order of filling gives one fixed count at every stage. Split the rows into cases that do not overlap (last digit 0, last digit not 0), count each case by filling its restricted places first, and add, since every row is in exactly one case.
Objects that must be together: make a block. If some objects must stand next to one another, glue them into a single block and treat the block as one unit. Arrange the units, then arrange the objects inside the block. The two stages multiply because the order inside the block does not depend on where the block stands. Each allowed row comes from exactly one choice at each stage: the row shows where the block is and what order it is in, and that rebuilds the choices.
Objects that must be apart: count the other side, or use gaps. “Not next to each other” is awkward to count head on, but for two objects its complement is easy: every row either has the two side by side or does not, and not both. So
For three or more objects that must have no two side by side, the complement is no longer just “all of them together”, and a direct count is cleaner. Place the other objects first; they leave a gap between each pair of neighbors and one at each end. Put the separated objects into different gaps, in order. Two objects in different gaps always have something between them, and every row with no two side by side arises this way exactly once.
“Not”, “at least one” and “not first”: count the complement. When the rule says what must not happen, it is often quicker to count the rows where it does happen and subtract from the total. This is the complement used for counting rather than for probability: the rows that break the rule and the rows that keep it are complements of each other inside the set of all rows, so their counts add up to the total.
Worked examples
One place fixed, then two
Persimmon is one of seven speakers at a school assembly, and the organizers must choose the order in which the seven speak.
(a) In how many orders can they speak if Persimmon must speak last?
(b) In how many orders if the two head students must speak first and last, either way round?
Solution(a) The last place carries the rule, so fill it first: it has exactly 1 choice, Persimmon. The other six places are free and take the other six speakers in any order:
Without the rule there would be 7! = 5{,}040 orders. Fixing one speaker in one place is the same as removing both that speaker and that place, which leaves a smaller problem with no rule at all.
(b) Fill the two restricted places first. The first place goes to either head student, 2 choices, and the last place must then go to the other one, 1 choice. The five middle places take the remaining five speakers in 5! orders:
A leader with a first-aid certificate
A hiking group has 10 members, 3 of whom hold a first-aid certificate. For a day on the hills it chooses a leader, a navigator and a back marker (who walks last), three different people.
(a) How many choices are there with no rule?
(b) How many if the leader must hold a certificate?
(c) How many if the leader must hold a certificate and the back marker must not?
Solution(a) The three jobs are different, so this is a permutation of 3 people from 10:
(b) Fill the leader first, from the 3 certificate holders. Whoever it is, 9 members are left for navigator and then 8 for back marker:
(c) Both the leader and the back marker carry a rule, so fill both before the free job. The leader is one of the 3 certificate holders. The back marker must be one of the 7 members without a certificate, and none of them has been used, since the leader holds one: 7 choices whatever happened. The navigator is then anyone of the 8 still free:
Filling the navigator before the back marker would have spoiled the count: the number of members without a certificate left for back marker would be 7 or 6 depending on who became navigator.
Two red cars, together and apart
Seven different cars, two of them red, park in a row of seven spaces.
(a) In how many ways can they park if the two red cars must be next to each other?
(b) In how many ways if the two red cars must not be next to each other?
Solution(a) Glue the red cars into one block, as in the first figure. There are now 6 units: the block and the five other cars. The units can stand in 6! orders, and whatever that order is, the block can be read in 2! ways, red car \text{R}_1 on the left or \text{R}_2 on the left:
(b) Every parking either has the red cars side by side or does not, and not both. With no rule there are 7! = 5{,}040 parkings, so subtract the ones from part (a):
Check by gaps. Park the five other cars first, in 5! = 120 orders. They leave 6 gaps, one between each pair and one at each end. The first red car goes in any of the 6 gaps and the second in one of the other 5, so
Both ways agree. Of the 5{,}040 parkings, fewer than a third keep the red cars together.
A word that must not start with W
(a) In how many ways can the six letters of WINTER be arranged so that the arrangement does not start with W?
(b) In how many ways so that it neither starts with W nor ends with R?
SolutionThe six letters W, I, N, T, E, R are all different, so with no rule there are 6! = 720 arrangements.
(a) Count the other side. The arrangements that do start with W have W fixed in the first place and the other five letters free, 5! = 120 of them. Every arrangement starts with W or does not, so
Check directly: the first place, carrying the rule, takes any of the 5 letters other than W, and the remaining five places take the remaining five letters in 5! orders, 5 \times 120 = 600.
(b) Now two rules. Count the arrangements that break at least one of them. 120 start with W and, by the same reasoning, 120 end with R; but the arrangements that do both, W first and R last with four free letters between, number 4! = 24, and they have been counted in both groups. Counting the union this way is the rule for the size of a union:
arrangements break a rule, so the ones that keep both rules number
Check by cases on the first letter, which must not be W. If the first letter is R, the rule about the end is already kept, and the other five letters are free: 5! = 120. If the first letter is one of I, N, T, E (4 choices), the last place may be any of the 5 letters left except R, so 4 choices, and the middle four places take the other four letters in 4! = 24 ways: 4 \times 4 \times 24 = 384. The cases do not overlap, and 120 + 384 = 504.
Even four-digit numbers with different digits
How many four-digit whole numbers, from 1{,}000 to 9{,}999, are even and have four different digits?
SolutionTwo places carry rules: the first digit cannot be 0, and the last digit must be even, one of 0, 2, 4, 6, 8. Fill the last digit first, since it has the stricter rule. But the number of choices left for the first digit then depends on whether 0 was used at the end, so split into two cases that do not overlap.
Last digit 0. Then 0 is used up and the first digit may be any of the other 9 digits. The two middle places take any of the 8 and then 7 digits left:
Last digit 2, 4, 6 or 8. That is 4 choices. The first digit may not be 0 and may not be the digit just used, so 8 choices remain. The second digit may now be 0: any of the 8 digits not yet used, then 7 for the third:
Every such number ends in 0 or in one of the other even digits, never both, so add:
At least one vowel
Three-letter rows are made from the seven letters A, E, I, B, C, D, F, with no letter used twice. How many rows contain at least one vowel?
Solution“At least one” covers rows with one, two or three vowels, three cases to add. Its complement is a single case: no vowel at all. All rows number P(7, 3) = 7 \times 6 \times 5 = 210. The rows with no vowel use only the four consonants B, C, D, F, so they number P(4, 3) = 4 \times 3 \times 2 = 24. Every row has at least one vowel or has none, so
Check by cases. One vowel: choose which of the 3 places holds it (3 ways), the vowel (3), then the other two places in order from the 4 consonants (4 \times 3), giving 3 \times 3 \times 12 = 108. Two vowels: the place of the consonant (3), the consonant (4), the two vowels in order (3 \times 2), giving 72. Three vowels: 3! = 6. And 108 + 72 + 6 = 186.
No two children side by side
Five adults and four children sit in a row of nine seats. In how many ways can they sit so that no two children are next to each other?
SolutionSeat the adults first, in 5! = 120 orders. As the second figure shows, they leave 6 gaps: one between each pair of neighboring adults and one at each end. Put the four children into four different gaps, in order: the first child has 6 gaps to choose from, the next 5, then 4, then 3. That is P(6, 4) = 360, the same for every order of the adults:
Each gap gets at most one child, so between any two children there is at least one adult. And every seating with no two children side by side comes from this process exactly once, since removing the children leaves the adults in some order and the children sitting in distinct gaps. The gaps line up with seats because the nine seats are exactly filled: the children’s gaps and the adults between them make a row of nine.
Here the complement would be hard: “some two children are side by side” splits into many overlapping cases. Out of all 9! = 362{,}880 seatings, 43{,}200 keep the rule.
Boundaries
The count at each stage must not depend on the earlier choices. Filling the restricted place first works only when, after it, every later place has a fixed number of choices. When two rules interfere, as with the leading 0 and the even last digit, the rows must be split into cases that do not overlap and the cases added.
The complement needs the total to be countable and to contain the rows being removed. Both counts must be over the same set of rows. Subtracting the “start with W” arrangements from all arrangements works because every arrangement either starts with W or does not.
“Apart” is the complement of “together” only for two objects. For three objects, “no two side by side” is not the opposite of “all three together”: rows where exactly two of them touch belong to neither. Use gaps, or count the unions with inclusion-exclusion.
Gaps run out. m objects in a row leave m + 1 gaps, so at most m + 1 objects can be kept apart. With more than that there is no allowed row, and P(m + 1, k) is 0 for k > m + 1 in the product form.
A row is not a circle. The block and gap counts above are for a row with two ends. Around a round table the two end seats are neighbors, so there is one gap fewer and the counts change.
The objects must be different. If some objects are identical, each count above counts some rows more than once, and the repeats have to be divided out as for permutations with repeated objects.
Where this goes next
A count with a restriction, divided by the count with no restriction, is a probability: the chance that a random parking puts the red cars together is \dfrac{1{,}440}{5{,}040} = \dfrac{2}{7}. That is how counting feeds compound events and the probabilities of drawing without replacement. When the order does not matter, the same moves (fix the required members first, count the complement for “at least one”) work with combinations. And when several rules overlap, the union count grows into the inclusion-exclusion principle, which also counts the arrangements in which nothing stays in its own place. The whole family lives under counting.
Exercises
One place fixed
- Six different lanterns hang in a row, and the largest must hang at the right-hand end. How many orders are possible?
- Nine different bottles stand in a row on a shelf. The two tallest must stand at the two ends, either way round. How many arrangements are there?
- How many arrangements of the eight letters of TRIANGLE begin with a vowel?
- Twelve people enter a contest with a gold, a silver and a bronze prize, each to a different person. In how many ways can the prizes go if Ambrosine wins gold?
Together and apart
- Six people sit in a row of six seats, and two friends among them must sit next to each other. How many seatings are there?
- In Exercise 5, how many seatings keep the two friends apart?
- Seven different floats go along a parade route in a line, and the three floats from one school must go one straight after another, in any order among themselves. How many parade orders are there?
- How many arrangements of the letters of COMPUTER keep the three vowels O, U and E together?
- A school show has six different comedy sketches and four different dances. In how many orders can they be performed if no two dances come one straight after another?
Counting the complement
- Five friends sit in a row of five seats, and Hesketh will not take the middle seat. How many seatings are there?
- Rows of 4 different letters are made from the eight letters A to H. How many rows contain A or B or both?
- A locker number is a row of 4 different digits from 0 to 9. How many locker numbers contain the digit 7?
Restrictions while choosing some
- A choir of 9 members chooses a conductor and a librarian, two different people. The conductor must be one of the 4 founding members. How many choices are there?
- How many three-digit whole numbers are odd and have three different digits?
- How many whole numbers from 5{,}000 to 9{,}999 have four different digits?
- How many three-digit whole numbers are even and have three different digits?
More than one rule
- Seven people stand in a queue. Ambrosine must not be at the front and Hesketh must not be at the back. How many queues are there?
- Five people sit in a row of five seats on a bench. Two of them, who are twins, must sit next to each other, and the tallest person, who is not a twin, must sit at one end. How many seatings are there?
Reasoning
- A committee of 8 chooses a chair, a vice-chair and a secretary, three different people. The secretary must be one of the 2 members who write shorthand. Someone fills the chair, then the vice-chair, then the secretary, and writes 8 \times 7 \times 2 = 112. Explain what is wrong and give the right count.
- Five people stand in a row, and three of them must have no two side by side. Someone counts all rows minus the rows with all three together. Find that number, find the right count by gaps, and explain why the two differ.
- Show that for two objects among n \ge 2 in a row, the gap count (n - 2)! \times (n - 1)(n - 2) equals the complement count n! - 2 \times (n - 1)!.
- Explain why the block method multiplies the count of unit orders by the number of orders inside the block, and why it neither misses a row nor counts one twice.
Answers
- 120. The right-hand end has 1 choice; the other five lanterns fill the rest in 5! = 120 orders.
- 10{,}080. The ends take the two tallest in 2 ways and the middle seven people stand in 7! = 5{,}040 orders: 2 \times 5{,}040 = 10{,}080.
- 15{,}120. The eight letters are all different and three are vowels (I, A, E). The first place has 3 choices and the other seven letters follow in 7! = 5{,}040 orders: 3 \times 5{,}040 = 15{,}120.
- 110. Gold has 1 choice; silver then any of the other 11, bronze any of 10: 11 \times 10 = 110.
- 240. The friends form a block, so 5 units in 5! = 120 orders, times 2 orders inside the block.
- 480. All seatings number 6! = 720, and 720 - 240 = 480.
- 720. The three school floats form a block, leaving 5 units in 5! = 120 orders, and the block has 3! = 6 orders inside: 120 \times 6 = 720.
- 4{,}320. COMPUTER has eight different letters. The vowels form a block with the five consonants, 6 units in 6! = 720 orders, and the block has 3! = 6 orders: 720 \times 6 = 4{,}320.
- 604{,}800. The sketches go first in 6! = 720 orders, leaving 7 gaps. The four dances go in different gaps in P(7, 4) = 7 \times 6 \times 5 \times 4 = 840 ways: 720 \times 840 = 604{,}800.
- 96. All seatings number 5! = 120; with Hesketh in the middle the others sit in 4! = 24 ways: 120 - 24 = 96.
- 1{,}320. All rows number P(8, 4) = 1{,}680. Rows with neither A nor B use the six letters C to H: P(6, 4) = 360. So 1{,}680 - 360 = 1{,}320.
- 2{,}016. There are P(10, 4) = 5{,}040 locker numbers in all; those with no 7 number P(9, 4) = 3{,}024; 5{,}040 - 3{,}024 = 2{,}016.
- 32. The conductor has 4 choices, then the librarian any of the other 8: 4 \times 8 = 32.
- 320. Fill the last digit first: 1, 3, 5, 7 or 9, 5 choices. The first digit is not 0 and not the last digit: 8 choices. The middle digit is any of the 8 left: 5 \times 8 \times 8 = 320.
- 2{,}520. The first digit is 5, 6, 7, 8 or 9, 5 choices, and the other three places take 9 \times 8 \times 7 = 504: 5 \times 504 = 2{,}520.
- 328. Last digit 0: 9 \times 8 = 72. Last digit 2, 4, 6 or 8: 4 choices, then 8 for the first digit (not 0, not the last) and 8 for the middle: 4 \times 8 \times 8 = 256. Total 72 + 256 = 328.
- 3{,}720. All queues number 7! = 5{,}040. Ambrosine at the front: 6! = 720; Hesketh at the back: 720; both: 5! = 120. Queues breaking a rule: 720 + 720 - 120 = 1{,}320, so 5{,}040 - 1{,}320 = 3{,}720.
- 24. The tallest takes an end, 2 ways. The other four places are side by side, and in them the twins’ block and the two others make 3 units in 3! = 6 orders, times 2 inside the block: 2 \times 6 \times 2 = 24.
- 84. The secretary carries the rule but was filled last, and the number of shorthand writers still free then depends on whether one of them became chair or vice-chair: it could be 2, 1 or 0, not always 2. Fill the secretary first: 2 choices, then chair 7, vice-chair 6: 2 \times 7 \times 6 = 84.
- All rows minus all three together gives 5! - 3! \times 3! = 120 - 36 = 84. By gaps: the other two people stand in 2! = 2 orders, leaving 3 gaps, and the three go into them in P(3, 3) = 6 ways, so the right count is 12. The subtraction leaves in every row where exactly two of the three are side by side, and those rows break the rule too.
- Both equal (n - 1)! \times (n - 2). On the left, (n - 2)! \times (n - 1) = (n - 1)!, so the gap count is (n - 1)! \times (n - 2). On the right, n! = n \times (n - 1)!, so n! - 2(n - 1)! = (n - 1)!\,(n - 2) by the distributive property. For n = 7 both give 720 \times 5 = 3{,}600.
- A row with the objects together is built in two stages: the order of the units, then the order inside the block. The number of inside orders is the same whatever the unit order, so the counting principle multiplies. Every allowed row shows where the block stands and the order of the units, and the order inside the block, so it comes from exactly one pair of choices: none is missed and none is counted twice.