Counting Arrangements with Restrictions

Why Restricted Arrangements Need Care

Counting an unrestricted arrangement is often a direct application of factorials. Restrictions change the task: a required position removes choices, adjacency links objects into a unit, and separation forces objects into different gaps. The main challenge is to represent the restriction correctly before multiplying.

This tutorial treats objects as distinct and positions as ordered. For example, arranging seven different folders on a shelf is not the same as arranging seven identical folders. The methods also apply to people in seats, labeled tasks in a schedule, or distinct components in a sequence. Each scenario below is hypothetical.

A useful starting point is to name the positions and translate each condition literally. “A is in position 3” fixes A in one slot. “A and B are adjacent” means they occupy consecutive slots, in either order. “A, B, and C are never adjacent to one another” means no two of those three occupy consecutive slots. These are different conditions and require different counting models.

A Reliable Counting Plan

Required Positions and Disjoint Cases

A fixed position is handled by placing the required object first and then arranging the objects that remain. If an object is allowed in several positions, split the count according to its position. The cases must not overlap: an object cannot occupy two different positions in the same arrangement.

Adjacency: Treat a Pair as a Block

To require two specified objects to be adjacent, temporarily combine them into one block. Arrange that block with the other objects, then account for the orders inside the block. For two distinct objects, there are two internal orders: AB and BA. The block method works because an adjacent pair occupies consecutive positions and can therefore be represented by one unit in the larger ordering.

An additional position restriction must still be checked in the original arrangement. In particular, if a person outside the block is forbidden from the first position, the block can occupy the first position without violating that condition. The person is at the start of the row only when that person’s unit is first.

Separation: Use Gaps

When designated objects must not be adjacent to one another, first arrange the objects that are not restricted. This creates gaps before, between, and after them. Put at most one designated object in each gap. That guarantees a separating object between every pair of designated objects.

To justify the result, fix an ordering of the \(m\) other objects. Every permitted arrangement of the designated objects determines exactly which gaps they occupy and which designated object goes in each chosen gap. Conversely, selecting distinct gaps and assigning the designated objects to them yields an arrangement with no two designated objects adjacent. Therefore, for each fixed ordering of the other objects, the number of placements is \(\binom{m+1}{r}r!\). There are \(m!\) possible orderings of those other objects, so the total is \(m!\binom{m+1}{r}r!\).

Combining Restrictions Without Losing Track

Several restrictions can be handled in one count, but it is important to check how they interact. A block reduces the number of units being ordered. A fixed-position condition removes a position from the remaining choices. A gap condition controls where designated objects can be placed. Apply each step to the objects and positions still available, rather than multiplying separate counts that may describe the same choices or incompatible arrangements.

For example, if two objects must be adjacent while a third must occupy a specified position, first check whether the specified position could belong to the block. If it does, the block may have more possible placements than if it does not. Similarly, if one object has two allowed positions and another has a fixed position, verify that the positions do not coincide in a way that would require two distinct objects in one slot. If they do, separate the valid cases explicitly.

The methods here are useful whenever the event of interest is defined by an arrangement condition. Once the valid arrangements have been counted, a probability can be found in a finite model if outcomes are equally likely. The counting step itself does not establish that outcomes are equally likely; that is a separate modeling assumption.

Common Mistakes

• Forgetting internal orders in a block. A two-object block has two orders. A block of \(r\) distinct objects has \(r!\) internal orders.
• Using overlapping cases. “A is in position 1” and “A is in position 8” are disjoint. Cases such as “A is in an odd position” and “A is before B” may overlap, so they cannot automatically be added.
• Confusing a block position with an actual position. A block is one unit for ordering purposes but occupies multiple consecutive positions in the original row.
• Leaving out assignments to gaps. Choosing gaps selects locations, but distinct designated objects must also be assigned to those gaps.
• Applying a method to the wrong restriction. A block enforces adjacency. Separate gaps enforce nonadjacency. Reversing these models gives the wrong set of arrangements.