Constrained permutations

A row of chairs, a shelf of books, a string of digits — plain permutations count every possible order. Real problems are rarely that free. A rule sneaks in: three friends insist on sitting together, two rivals refuse to sit next to each other, a phone number must start with a particular digit, a number formed from given digits must come out even. These are constrained (restricted) permutations, and the good news is that almost every such rule falls into one of a handful of standard patterns — glue objects into a block, force gaps between objects, or fix a position and count what remains freely. This section builds on the basic nPr^nP_r formula and the fundamental principle of counting from earlier in the Permutations and Combinations sub-unit, and shows how to recognise which pattern a given constraint calls for, then execute it cleanly without double-counting or missing a case.

The core insight

Every "things together," "things never together," or "fixed-position" constraint on a permutation reduces to counting units instead of individual objects, using the glue method ((n−k+1)!×k!(n-k+1)!\times k!), the gap method ((n−k)!×(n−k+1)Pk(n-k)!\times{}^{(n-k+1)}P_k), or position-first counting, respectively.

The core idea

Things always together — the glue method. When kk specific objects out of nn must stay together (in some internal order), tape them into one super-object. Now (n−k+1)(n-k+1) units need arranging, and the glued block can be internally shuffled in k!k! ways:

Arrangements=(n−k+1)!×k!\text{Arrangements} = (n-k+1)!\times k!

where: nn is the total number of objects, kk is the size of the group that must stay together, (n−k+1)!(n-k+1)! counts arrangements of the block-plus-remaining-objects, and k!k! counts internal orders within the block.

Things never together — the gap method. To keep kk specific objects apart, first arrange the other (n−k)(n-k) objects in (n−k)!(n-k)! ways. This creates (n−k+1)(n-k+1) gaps (including both ends). Placing the kk restricted objects into distinct gaps, at most one per gap, is a permutation of gaps taken kk at a time:

Arrangements=(n−k)!×(n−k+1)Pk\text{Arrangements} = (n-k)!\times{}^{(n-k+1)}P_k

where: (n−k)!(n-k)! arranges the unrestricted objects first, and (n−k+1)Pk{}^{(n-k+1)}P_k selects and orders kk of the (n−k+1)(n-k+1) gaps so no two restricted objects share a gap.

Fixed-position problems (word starts with a vowel, number is even, digit occupies a specific slot) are handled by filling the constrained position(s) first — counting the choices available there — then filling the remaining positions freely using the fundamental principle of counting (multiply choices across positions).

Leading-zero care. When digits include 00 and the arrangement forms a number, the leading position cannot take 00. This one exception is exactly why digit problems often need to split into cases rather than use one clean formula throughout — see the worked example below.

Figure
Three arrangement strategies shown as chairs in a row: a glued block for things together, forced gaps for things never together, and a fixed first seat for position constraints
Three constraint patterns, three counting tricks glue (together) A B C (n-k+1)! x k! gap (never together) (n-k)! x P(n-k+1,k) fixed position even fix, then count freely Recognise the pattern first, then apply the matching formula. Glue shrinks the object count; gaps prevent adjacency; fixing a position spends its choices before the rest are free.
Derivation AWhy the gap method never double-counts adjacent placements

Show that arranging (n−k)(n-k) unrestricted objects first and then placing the remaining kk restricted objects one per gap among the (n−k+1)(n-k+1) available gaps correctly counts every arrangement in which no two restricted objects are adjacent, exactly once, with no restricted pair ever forced into contact.

Step 1. Arrange the (n−k)(n-k) unrestricted objects in a row; there are (n−k)!(n-k)! ways to do this. Once fixed, this row has a definite left end, a definite right end, and (n−k−1)(n-k-1) slots strictly between consecutive objects — together with the two ends, that is (n−k)−1+2=(n−k+1)(n-k)-1+2=(n-k+1) distinct gaps.

Step 2. Any restricted object placed into a gap sits between two unrestricted objects (or at an end), so it can never be adjacent to another restricted object unless two restricted objects share the same gap. The construction is therefore only valid if each gap receives at most one restricted object.

Step 3. Counting ordered selections of kk gaps out of (n−k+1)(n-k+1), one restricted object per chosen gap, is precisely the permutation (n−k+1)Pk{}^{(n-k+1)}P_k — it selects which kk gaps are used and, since the objects are distinct, which object goes into which gap, without any gap repeating.

Step 4. By the fundamental principle of counting, the two independent stages (arranging the unrestricted objects, then placing the restricted ones into distinct gaps) multiply together: (n−k)!×(n−k+1)Pk(n-k)!\times{}^{(n-k+1)}P_k. Every arrangement produced has each restricted object flanked by non-restricted neighbours, so no two restricted objects are ever adjacent, and every valid "never together" arrangement is reachable exactly once this way, since it uniquely determines which gap each restricted object occupies.

Worked example

Seat 3 boys and 4 girls in a row of 7 chairs so that all 3 boys sit together, and separately, seat 4 men and 4 women in a row so that no two women sit next to each other.

Step 1. Boys together: treat the 3 boys as one block, giving 44 girls + 1+\ 1 block =5=5 units. These arrange in 5!=1205! = 120 ways.

Step 2. The 3 boys inside the block can be reordered among themselves in 3!=63! = 6 ways, independent of how the 5 units are arranged.

Step 3. By the fundamental principle of counting, multiply: Total=5!×3!=120×6=720\text{Total} = 5!\times3! = 120\times6 = \mathbf{720} seatings.

Step 4. No two women adjacent: arrange the 4 men first, 4!=244! = 24 ways, which creates 4+1=54+1=5 gaps (both ends plus 3 between men).

Step 5. Place the 4 women into these 5 gaps, at most one per gap, which is 5P4=5×4×3×2=120{}^5P_4 = 5\times4\times3\times2 = 120 ways.

Step 6. Multiply the two independent stages: 4!×5P4=24×120=28804!\times{}^5P_4 = 24\times120 = \mathbf{2880} seatings with no two women adjacent.

Competitive stretch

Extend the digit problem from the syllabus: how many 5-digit even numbers can be formed from {0,1,2,3,4,5}\{0,1,2,3,4,5\} without repetition? Split on the last digit. If it is 00: remaining 4 positions from {1,2,3,4,5}\{1,2,3,4,5\} give 5P4=120{}^5P_4=120. If it is 22 or 44 (2 choices): the first digit excludes 00 and the fixed last digit, leaving 44 choices, and the middle 3 positions fill from the remaining 4 digits, giving 4P3=24{}^4P_3=24, so 4×24=964\times24=96 per choice, totalling 2×96=1922\times96=192. Grand total: 120+192=312120+192=\mathbf{312}.

Common traps

  • Forgetting the internal-arrangement factor k!k! in a things-together problem — the glued block can usually still be rearranged inside itself.
  • In "never together" problems, allowing more than one restricted object per gap — the whole method only works because (n−k+1)Pk{}^{(n-k+1)}P_k enforces at most one per gap.
  • Treating a leading-zero digit set with a single clean formula instead of splitting into cases — as soon as 00 is among the digits and a number is being formed, the first position needs separate handling.
  • Applying glue or gap methods to a circular arrangement — both formulas assume a row; circular seating needs its own separate treatment.

Ask the tutor: If you're unsure whether a problem needs the glue method, the gap method, or a fixed-position count, ask the AI tutor to restate the constraint in your own words before picking a formula.

Why does the glue method use (n-k+1)! and not n!

Because once the kk objects are taped into a single block, there are no longer nn separate objects to arrange — there are (n−k)(n-k) untouched objects plus 11 block, which is (n−k+1)(n-k+1) units in total. You arrange those units in (n−k+1)!(n-k+1)! ways, then separately account for the k!k! orders inside the block. Using n!n! would wrongly treat the glued objects as still independently placeable across the whole row.

Can I use the gap method when more than one group must avoid each other

Only if it is genuinely one set of kk objects that must pairwise avoid each other. If instead you have two separate groups with different restrictions (say, group A must avoid group B but both can sit anywhere relative to a third group C), the plain gap formula does not directly apply — you typically need to arrange the least restricted objects first, then place each restricted group into gaps created by the appropriate reference objects, checking carefully whether the gaps for different groups overlap or not. Always re-derive the gap count for the specific problem rather than reusing the two-group formula blindly.

Why does the even-digit problem need cases but the boys-together problem does not

The boys-together problem has a fixed, uniform block size at every step, so one formula covers it completely. The even-digit problem has an extra rule — no leading zero — that behaves differently depending on which digit lands in the fixed (last) position: if that digit is 00, the leading digit has no extra exclusion beyond avoiding 00 itself (already used); if it is 22 or 44, the leading digit must avoid both 00 and the used digit. That branching in the number of available choices is exactly what forces a case split rather than one clean formula.

Before this

Where this leads