Permutations with Restrictions

Five friends — Aarav, Bhumi, Chirag, Diya, and Eshan — line up for a photograph. There are 5! = 120 ways to arrange them. But the photographer has a request: Aarav and Bhumi, who are siblings, must stand next to each other. How does this constraint change the count?

Your first instinct might be to list cases, but that gets unmanageable quickly. A cleaner method: treat Aarav and Bhumi as a single block [AB]. Now there are 4 objects to arrange — [AB], Chirag, Diya, Eshan — giving 4! = 24 arrangements. But inside the block, Aarav can be on the left or the right, so each block arrangement comes in 2 internal orders. Total: 4! \times 2! = 24 \times 2 = 48.

This is the block method, and it is the first of four techniques covered here: objects always together, objects never together, relative positions fixed, and finding the rank of a word in dictionary order.

Objects always together (the block method)

The block method turns an "always together" constraint into an unrestricted permutation of fewer objects.

The recipe:

1. Bundle the constrained objects into a single block.
2. Count the arrangements of the blocks (and remaining objects) as if each block were a single item.
3. Multiply by the internal arrangements within each block.

What if more than two objects must be together? The same idea works. If 3 specific friends must stand together, bundle them into one block. You now have n - 3 + 1 = n - 2 objects to arrange, and the block's internal arrangements multiply by 3!.

What if multiple groups must each be together? Bundle each group separately. If k_1 objects form one block and k_2 objects form another, you have n - k_1 - k_2 + 2 objects to arrange, and you multiply by k_1! \times k_2! for the internal arrangements.

The block method in circular arrangements. The same principle works at a round table. If n people sit in a circle and k of them must sit together, form a block of k people. There are now n - k + 1 objects around the circle, giving (n-k)! circular arrangements (fixing one reference point). Multiply by k! for the block's internal order: total = (n-k)! \times k!.

Objects never together (complementary counting)

Suppose the photographer now says: Aarav and Bhumi must not stand next to each other. Directly counting valid arrangements is tricky — you would need to handle where Aarav stands, then ensure Bhumi avoids the adjacent spots, and the casework branches quickly.

The cleaner route: complementary counting. Count the total arrangements without any restriction, then subtract the "bad" ones (where Aarav and Bhumi are together).

Why complementary counting works. The "together" arrangements and the "never together" arrangements are disjoint and exhaustive — every arrangement falls into exactly one of the two groups. By the addition principle, their counts sum to the total. So the "never together" count is the total minus the "together" count.

A slightly harder version. In a row of 7 people, persons P, Q, and R must not all three be adjacent (but any two of them may be adjacent). Direct counting is complex. Complementary counting: 7! - (\text{all three together}) = 5040 - (5! \times 3!) = 5040 - 720 = 4320.

General pattern. Whenever a restriction says "must not" or "never," think: can I count the complementary case ("must" or "always") and subtract? Often the "always" version is a block-method problem, which is easier.

Relative position fixed

Seven books are placed on a shelf: 3 mathematics books (M₁, M₂, M₃) and 4 science books (S₁, S₂, S₃, S₄). The total arrangements are 7! = 5{,}040. But now a constraint: the 3 mathematics books must maintain their mutual order — M₁ must be to the left of M₂, which must be to the left of M₃ — though they need not be adjacent.

The 3 mathematics books can appear in 3! = 6 possible mutual orderings among themselves. Only one of these 6 orderings (M₁ before M₂ before M₃) is valid. By symmetry, exactly 1/6 of all arrangements satisfy this constraint:

Why it works. Consider all n! arrangements. The k constrained objects occupy k positions, and among those k positions, they can appear in k! different orderings. By symmetry (each ordering is equally likely in a random arrangement), exactly n!/k! of the arrangements have the desired ordering.

This technique applies whenever you fix the relative order of some objects without requiring them to be adjacent. If they must also be adjacent, you would use the block method instead (with only 1 valid internal arrangement, the block gives (n - k + 1)! \times 1).

Rank of a word

Take the letters of the word JUMBLE and arrange them in dictionary (alphabetical) order. The sorted letters are: B, E, J, L, M, U. Every arrangement of these 6 distinct letters is a 6-letter "word," and there are 6! = 720 such words. The rank of a word is its position when all 720 words are listed in alphabetical order.

What is the rank of JUMBLE?

The method: count how many words come before JUMBLE in dictionary order, then add 1.

Position 1: J. How many words start with a letter before J? The letters before J in alphabetical order are B and E — that is 2 letters. Each of them can be followed by any arrangement of the remaining 5 letters: 2 \times 5! = 2 \times 120 = 240 words.

Position 2: U (with J fixed in position 1). Remaining letters after J is used: B, E, L, M, U. How many words start with J and have a second letter before U? The letters before U among {B, E, L, M, U} are B, E, L, M — that is 4 letters. Each gives 4! arrangements of the remaining 4 letters: 4 \times 4! = 4 \times 24 = 96 words.

Position 3: M (with JU fixed). Remaining letters: B, E, L, M. Before M: B, E, L — 3 letters. Each gives 3! arrangements: 3 \times 3! = 3 \times 6 = 18 words.

Position 4: B (with JUM fixed). Remaining letters: B, E, L. Before B: none — 0 letters. Contribution: 0.

Position 5: L (with JUMB fixed). Remaining letters: E, L. Before L: E — 1 letter. Each gives 1! = 1 arrangement: 1 \times 1! = 1 word.

Position 6: E (with JUMBL fixed). Only E remains. No letter comes before E. Contribution: 0.

Total words before JUMBLE: 240 + 96 + 18 + 0 + 1 + 0 = 355.

Rank of JUMBLE = 355 + 1 = 356.

The algorithm for rank. For a word with n distinct letters:

1. At each position i (from left to right), count the number of remaining unused letters that are alphabetically smaller than the letter at position i. Call this c_i.
2. Multiply c_i by (n - i)! — the number of arrangements of the remaining positions.
3. Sum all contributions: \sum c_i \times (n-i)!.
4. The rank is this sum plus 1 (because the word itself is the next one after all the words counted).

When the word has repeated letters, the algorithm adjusts: at each position, instead of multiplying by (n-i)!, multiply by the number of distinct arrangements of the remaining letters (using the "not all different" formula).

Two worked examples

Common confusions

• "For 'never together,' subtract 2 from n instead of using the block method." There is no such shortcut. The correct approach is: total arrangements minus the "always together" count (computed via the block method). The block method bundles the constrained objects, reducing the number of items to permute — the reduction depends on how many objects are bundled, not on a fixed rule of "subtract 2."

• "Fixing relative order means the objects must be adjacent." It does not. "M₁ must be to the left of M₂" allows any number of objects between them. If they must also be adjacent (and in order), that is a block with a single valid internal arrangement.

• "The rank formula works only for distinct letters." The algorithm can be extended to repeated letters, but the factorial at each step must be replaced by the multinomial count for the remaining letters. For distinct letters, the formula is simpler because each remaining arrangement count is a plain factorial.

• "Complementary counting always involves subtraction." It does — that is the definition. You compute total minus the complement. The power is that the complement is often easier to count than the desired set directly.

• "The block method does not work for circular arrangements." It does. Form the block, count circular arrangements of the reduced set (using (m-1)! where m is the number of objects after blocking), then multiply by the block's internal arrangements.

Going deeper

The gap method (objects never together — an alternative)

Instead of complementary counting, you can directly place objects into gaps. Arrange the unrestricted objects first, then place the restricted objects in the gaps between them.

For example: arrange 5 people so that A and B are never adjacent. First arrange the other 3 (C, D, E) in a row: 3! = 6 ways. This creates 4 gaps (including the two ends):

Now place A and B in 2 of these 4 gaps (one person per gap, since if they shared a gap they would be adjacent). The number of ways to choose 2 gaps from 4 and assign A and B to them (order matters) is {}^4P_2 = 4 \times 3 = 12.

Total: 3! \times {}^4P_2 = 6 \times 12 = 72.

This matches the complementary counting result (120 - 48 = 72), confirming both methods. The gap method is especially useful when more than two objects must all be separated from each other.

Rank with repeated letters

Suppose you want the rank of AABA among all arrangements of \{A, A, A, B\}. The distinct arrangements number 4!/(3!\cdot 1!) = 4, and listing them in order gives: AAAB (rank 1), AABA (rank 2), ABAA (rank 3), BAAA (rank 4).

The algorithm: at position 1, the letter is A. Are there letters before A? No. Contribution: 0. At position 2, the letter is A again. Before A? No. Contribution: 0. At position 3, the letter is B. Remaining letters are \{A, B\}. Before B: A (1 letter). If A were placed here, the remaining letters are \{B\} giving 1!/1! = 1 arrangement. Contribution: 1. At position 4: only A remains. Contribution: 0.

Total before AABA: 0 + 0 + 1 + 0 = 1. Rank = 1 + 1 = 2. Correct.

The key adjustment: at each position, when letters repeat, you compute the number of distinct arrangements of the remaining letters (using the multinomial formula), not a plain factorial. This makes the computation slightly more involved but follows the same structure.

Derangements revisited

A derangement is a permutation where every object is in a "wrong" position — no object occupies its original place. The derangement count D_n = n! \sum_{k=0}^{n} (-1)^k / k! is a restriction problem at heart: you have n constraints (object i cannot be in position i), and the inclusion-exclusion principle computes the count of arrangements satisfying all n constraints simultaneously. The connection to this article is that "never in position i" is a position-based restriction, just like the "never adjacent" problems above — but with n simultaneous constraints instead of one.

Where this leads next

• Combinations — Basics — when order does not matter, the counting changes from permutations to combinations.
• Combinations with Restrictions — the selection counterpart of these restriction techniques, applied to unordered selections.
• Permutations — Special Cases — circular permutations, necklaces, and identical objects: the other set of modifications to the basic formula.
• Permutations — Basics — review the {}^nP_r formula and its derivation.
• Fundamental Principle of Counting — the addition and multiplication principles that power every technique here.