Restricted line arrangements

Arranging people or objects in a line becomes interesting when there are rules: two friends must sit together, two rivals must be apart, a particular person must take an end seat. This lesson starts from the unrestricted count n!, then handles each kind of rule with its own technique: glue objects into a block, place objects into the gaps between others, or fill restricted positions first. It ends by turning those counts into probabilities for a random arrangement.

Start from the unrestricted line

An arrangement in a line fills positions 1, 2, 3, … from left to right. With n distinct objects, the first position has n choices, the next n-1, and so on, so there are n! arrangements. Seven different people can stand in a queue in 7! = 5040 ways.

A restriction removes some of those orders. Before counting, decide which kind of restriction you have:

• Together: specified objects must form one unbroken group.
• Apart: specified objects must not stand next to each other.
• Position: an object must, or must not, occupy a particular place such as an end.
• Relative order: one object must come somewhere before another, not necessarily next to it.

Each kind has a natural method. Use the method that matches the wording; a calculation that answers a different restriction can look reasonable and still be wrong.

Glue objects that must be together

When k specified objects must be together, treat them as one block. The block and the other n-k objects make n-k + 1 units, giving (n-k + 1)! unit orders. The block’s own objects can then be ordered in k! ways. Multiply the two stages.

Separate objects with gaps

For three or more objects, “no two of them together” and “not all of them together” are different restrictions. The first forbids every adjacent pair. The second only forbids the single block of all of them.

For “no two together”, place the other objects first. Their arrangement creates gaps: one before the first object, one between each neighbouring pair and one after the last. Put at most one restricted object in each gap. Then no two restricted objects can touch.

Fill restricted positions first

When an object must occupy a named place, fill that place first and then arrange everything that remains. Two teachers and five students, all different, stand in a line of seven. If the teachers must stand at both ends, the ends have 2! orders and the middle five places have 5!:

For “at least one end”, a direct count needs separate cases. The complement is often shorter: count the lines with no teacher at either end and subtract them from all lines.

A relative-order restriction is different again. In half of all arrangements A stands somewhere to the left of B, because swapping A and B pairs each such line with one where B is to the left of A. Five different people therefore have 5!/2 = 60 lines with A to the left of B. Adjacency is not required.

A random line turns counts into probabilities

If the objects are arranged at random, every one of the n! orders is equally likely. A probability is then the restricted count divided by n!:

For two specified people in a random line of n, the block method gives 2 × (n-1)! arrangements with them together, so

This only applies when every order is equally likely. A queue formed by people arriving in groups, for example, is not a random arrangement of individuals.

Common mistakes

• Forgetting to multiply by the internal arrangements of a block.
• Counting the gaps between k objects as k-1 when the ends are also available; there are k + 1 gaps in a line.
• Filling unrestricted positions first and running out of valid choices for the restricted ones.
• Subtracting “together” from the total to get “apart” when more than two objects must be separated.
• Using a probability’s numerator and denominator from different counting conventions.

Before you move on