Counting and Arrangements
Listing outcomes, the multiplication principle, factorial notation, arrangements in a line and around a circle, and arrangements when some items are identical.
45 min · Combinatorics
The full teaching. Start here.
The short version
- Multiplication principle: if one choice can be made in ways and then another in ways, together they can be made in ways. "Or" between separate cases means add.
- , and .
- different items in a line: .
- different items in a circle: .
- items with of one kind, of another, … alike: .
- Restrictions: fill restricted positions first; glue items that must be together (then count their internal order); use the complement for "not together".
Listing and the multiplication principle
For small problems, list the outcomes systematically, using a table or tree. For larger ones, count without listing.
- Multiplication principle
If a task is done in stages, with ways for the first stage, then ways for the second whatever happened in the first, and so on, then the whole task can be done in ways.
The words to watch: stages done one and then another multiply; separate cases, one or another, add.
CheckpointAnswer before reading on.
A coin is tossed and a six-sided die is rolled. How many outcomes are there?
Hint 1List or multiply.
Hint 22 × 6.
Hint 312.
CheckpointAnswer before reading on.
Two dice are rolled. In how many ways can the total be 5?
Hint 1List ordered pairs.
Hint 2(1, 4), (2, 3), …
Hint 3Dice are distinguishable.
CheckpointAnswer before reading on.
An outfit is a shirt, a pair of pants and a pair of shoes. From 3 shirts, 4 pants and 2 pairs of shoes, how many outfits are possible?
Hint 1Multiplication principle.
Hint 23 × 4 × 2.
Hint 324.
CheckpointAnswer before reading on.
A café offers 5 mains and 3 desserts. You order exactly one item. How many choices do you have?
Hint 1One item, not one of each.
Hint 2Either a main or a dessert.
Hint 3Add.
CheckpointAnswer before reading on.
A number plate has 3 letters followed by 3 digits, with repetition allowed. How many plates are possible?
Hint 126 choices per letter.
Hint 210 per digit.
Hint 3.
CheckpointAnswer before reading on.
How many 4-digit PINs (digits 0 to 9, leading zero allowed) have all digits different?
Hint 110 choices, then 9, …
Hint 210 × 9 × 8 × 7.
Hint 35040.
When some positions have restrictions, fill those first, because they have fewer options.
CheckpointAnswer before reading on.
How many 3-digit even numbers can be made from the digits 1, 2, 3, 4, 5, 6 without repetition? (2 marks)
Hint 1Restricted position first.
Hint 2Last digit: 2, 4 or 6.
Hint 3Then 5 × 4.
CheckpointAnswer before reading on.
How many 4-digit numbers greater than 5000 can be made from the digits 1 to 7 without repetition? (2 marks)
Hint 1First digit 5, 6 or 7.
Hint 2Then 6 × 5 × 4.
Hint 3360.
Arrangements in a line
Arranging different items in a line: choices for the first place, for the second, and so on.
- Factorial
for positive integers , with . It counts the arrangements of different items in a line.
A useful fact for simplifying: .
CheckpointAnswer before reading on.
Evaluate .
Hint 1.
Hint 230 × 24.
Hint 3720.
CheckpointAnswer before reading on.
Simplify .
Hint 1.
Hint 2Cancel.
Hint 3.
CheckpointAnswer before reading on.
In how many ways can 7 people stand in a line?
Hint 17 choices for first place, …
Hint 27!.
Hint 35040.
Two standard restrictions:
- Together: glue the items into one block, arrange the blocks, then multiply by the arrangements inside the block.
- Not together: total minus together.
Worked example3 marks
Arrangements in a line with restrictions
Three boys and four girls stand in a line. In how many ways can this be done if (a) the three boys stand together; (b) no two boys stand next to each other?
(a) Glue the boys
Together means one block.
The block and the girls make units: orders. The boys arrange within the block in ways. Total .
(b) Girls first, boys in the gaps
Gaps between girls keep the boys apart.
Arrange the girls: . They create gaps (including both ends). Put the boys in different gaps, in order: . Total .
Answer
(a) . (b) .
Is that answer sensible?
Total arrangements: . The "no two boys together" count must be less than this, and . Note that (b) is not : that would only remove cases where all three boys are together.
CheckpointAnswer before reading on.
Six people stand in a line. In how many ways can this be done if Ali is at the left end and Bo is at the right end?
Hint 1Fix Ali and Bo.
Hint 2Arrange the other 4.
Hint 34!.
CheckpointAnswer before reading on.
Six people, including Ali and Bo, stand in a line. In how many ways can Ali and Bo not stand together?
Hint 1Complement.
Hint 2720 − 240.
Hint 3480.
Exam question
Standard · about 3 min
2 marks
Six people, including Ali and Bo, stand in a line. In how many ways can this be done if Ali and Bo stand together? (2 marks)
Hint 1Glue Ali and Bo.
Hint 25 units in a line.
Hint 3The pair can be in 2 orders.
Where students lose marks on this one
Answering 120.
Why it happens: Forgetting the pair can swap.
Count internal arrangements of the block.
Written for this site.
Common mistake
Seven people, A and B together: 6! = 720.
Why it happens: Forgetting that A and B can swap within their block.
The block AB can also be BA. Multiply by : . Any glued block of distinct items contributes a factor .
Arrangements in a circle
Around a circular table, only the positions of people relative to each other matter. Rotating everyone one seat gives the same arrangement.
- Circular arrangements
different items can be arranged in a circle in ways. Each circular arrangement corresponds to line arrangements (one for each rotation), so there are . Equivalently, fix one item and arrange the others relative to it.
Worked example3 marks
Circular seating with restrictions
Seven people, including Chen and Dana, sit around a circular table. In how many ways can they sit if (a) Chen and Dana sit together; (b) there is exactly one person between Chen and Dana?
(a) Glue Chen and Dana
6 units around a circle.
units in a circle: . Times for the pair: .
(b) Fix Chen
Fixing one person removes rotations.
With Chen fixed, Dana must be two seats to Chen's left or two to the right: choices. The remaining people fill the other seats in ways. Total .
Answer
(a) . (b) .
Is that answer sensible?
Total . With Chen fixed, Dana is equally often in each of the other seats. are adjacent to Chen and are two seats away, so both answers are . Correct.
CheckpointAnswer before reading on.
In how many ways can 6 people sit around a circular table?
Hint 1.
Hint 25!.
Hint 3120.
CheckpointAnswer before reading on.
Why are there arrangements of people around a circle, rather than ?
Hint 1Rotations.
Hint 2Each circle corresponds to n lines.
Hint 3.
CheckpointAnswer before reading on.
Eight people sit around a circular table. In how many ways can this be done if two particular people sit together?
Hint 1Glue the pair: 7 units.
Hint 2(7 − 1)! × 2.
Hint 31440.
Exam question
Standard · about 3 min
2 marks
Eight people sit around a circular table. In how many ways can two particular people not sit together? (2 marks)
Hint 1Total 7!.
Hint 2Subtract together.
Hint 35040 − 1440.
Where students lose marks on this one
Using 8! for the total.
Why it happens: Forgetting circular arrangements.
Circle total is (n − 1)!.
Written for this site.
Exam question
Harder · about 4 min
2 marks
Four men and four women sit around a circular table, alternating men and women. How many seatings are possible? (2 marks)
Hint 1Seat the men first around the circle.
Hint 23!.
Hint 3Women in the 4 gaps: 4!.
Where students lose marks on this one
Using 3! × 3!.
Why it happens: Treating the women as another circle.
Once the men are seated, the gaps are distinct.
Written for this site.
Arrangements with identical items
If some items are identical, overcounts. Label the identical items to make them different, count, then remove the labels: each arrangement was counted once for every order of the labelled copies.
- Arrangements with repetition
The number of arrangements of items in a line, of which are alike of one kind, alike of another, and so on, is .
Worked example3 marks
Letters with repeats and restrictions
Consider arrangements of the letters of COMMITTEE. (a) How many are there? (b) How many have the two M's together?
(a) Count the repeats
9 letters: M ×2, T ×2, E ×2.
.
(b) Glue MM
The block MM is one unit; swapping identical M's changes nothing.
Units: C, O, MM, I, T, T, E, E: units with T and E repeated. .
Answer
(a) . (b) .
Is that answer sensible?
The fraction with the M's together should be the chance two particular positions are adjacent. For two identical letters among positions: , and . Correct.
CheckpointAnswer before reading on.
How many arrangements are there of the letters of the word LETTER?
Hint 16 letters.
Hint 2E twice, T twice.
Hint 3.
CheckpointAnswer before reading on.
How many arrangements are there of the letters of MISSISSIPPI?
Hint 111 letters.
Hint 2I four times, S four times, P twice.
Hint 3.
CheckpointAnswer before reading on.
Why do we divide by when arranging a word containing two identical E’s?
Hint 1Label them E₁ and E₂.
Hint 2Swapping gives the same word.
Hint 3Each word is counted twice.
CheckpointAnswer before reading on.
On a grid, a path moves only right (R) or up (U). How many paths go from (0, 0) to (3, 2)?
Hint 1Each path is a word in R and U.
Hint 23 R’s and 2 U’s.
Hint 3.
Exam question
Standard · about 3 min
2 marks
How many arrangements of BANANA begin with B? (2 marks)
Hint 1Fix B.
Hint 2Arrange ANANA.
Hint 3.
Where students lose marks on this one
Using 5!.
Why it happens: Ignoring repeats.
Three A’s and two N’s repeat.
Written for this site.
Exam question
Harder · about 3 min
2 marks
How many arrangements of BANANA have the two N’s together? (2 marks)
Hint 1Treat NN as one block.
Hint 2Units: B, A, A, A, NN.
Hint 3.
Where students lose marks on this one
Multiplying by 2 for the block.
Why it happens: Treating identical N’s as distinct.
Swapping identical letters gives nothing new.
Written for this site.
What lifts this to a Band 6
Before counting, decide what makes two arrangements "the same". In a line, position matters. At a round table, only relative position matters. With identical items, swapping them changes nothing. Most errors come from answering a slightly different question from the one asked, so state the model in a line of working, for example "circular, so fix Chen".
Necklaces and reflections
For a bracelet or necklace, which can be flipped over, a clockwise arrangement and its mirror image are the same. So different beads on a necklace give arrangements. The general idea is to divide by the number of symmetries that give the same arrangement. This only works when no arrangement is its own mirror image. Once items repeat, some arrangements are symmetric and simple division fails. Counting those correctly needs a more careful tool (Burnside's lemma), which is beyond the course.