Derangement Puzzles: How to Count Mix-Ups With Nothing in Place

A derangement puzzle asks you to mix up a set of labelled objects so that not one of them ends up in its own place, and then to count the ways or find the single way that fits some clues. The quick route is to list small cases by where the first object goes, then use the counting rule that builds each total from the two before it: 0, 1, 2, 9, 44, 265 and so on.

This guide explains the idea with jars, lids, keys and numbered tiles, gives two ways to count, compares the totals in a table, and solves a full clue puzzle before handing you one to try.

What is a derangement puzzle?

Picture four jars labelled A, B, C and D, and four lids with the same labels. Someone has put every lid on a jar, but no lid sits on the jar with its own label. How many ways could that happen?

Mathematicians write an arrangement of the numbers 1 to n as a single line, so 3 1 2 means the first spot holds 3, the second holds 1 and the third holds 2 ^[2]. In a paper published on 4 March 2009, a fixed point is a spot that holds its own number, and an arrangement with no fixed points is called a derangement ^[1].

Every puzzle in this guide is that idea in a different costume. Lids on jars, keys in locks and tiles on numbered squares all ask the same thing: nothing may stay at home.

How do you count derangements by hand?

Start tiny. With one tile, the only arrangement leaves it at home, so there are no derangements. With two tiles, the only option is to swap them, so there is one.

With three tiles, list them carefully. Spot 1 must hold tile 2 or tile 3. If it holds tile 2, spot 2 cannot hold tile 1, because tile 3 would then stay at home, so spot 2 holds tile 3 and the order is 2 3 1. If spot 1 holds tile 3, spot 2 must hold tile 1 and the order is 3 1 2. Three tiles have exactly two derangements, and both simply rotate the tiles one step.

With four tiles, use the same habit: decide what spot 1 holds. It can hold tile 2, 3 or 4, and each choice leaves exactly three ways to finish. That gives 9 derangements of four tiles.

What is the counting rule?

Listing gets slow after four objects, so use a step rule. Put tile 1 in some other spot, say spot k; there are n minus 1 choices for k. Now look at tile k.

• Tile k swaps into spot 1. The pair is settled, and the other tiles form a smaller derangement with two fewer tiles.
• Tile k avoids spot 1. Treat spot 1 as tile k's forbidden home. The other tiles then form a derangement with one fewer tile.

So the number for n tiles is n minus 1 times the sum of the two previous numbers. The 2009 paper calls this the well-known recursion for derangements and also gives a second one: multiply the previous number by n, then add 1 when n is even or take away 1 when n is odd ^[1].

Both rules give the same list. For five tiles, the first rule gives 4 times the sum of 9 and 2, which is 44, and the second gives 5 times 9 minus 1, which is also 44.

How does taking away the fixed ones work?

A second method starts from every arrangement and removes the bad ones. For four tiles there are 24 arrangements in all.

1. Take away the arrangements that fix one chosen tile. There are 4 tiles to choose and 6 ways to arrange the other three, so subtract 24.
2. Add back the ones that fix two chosen tiles. Step 1 removed each of them twice. There are 6 pairs of tiles and 2 ways to arrange the rest, so add 12.
3. Take away the ones that fix three tiles, then add back the one that fixes all four. Subtract 4 and add 1.

The result is 24 minus 24 plus 12 minus 4 plus 1, which is 9, the same as the hand count. This take-away-and-add-back pattern is the main tool against counting a case twice.

How do the totals compare as the objects grow?

The share settles very quickly. The 2009 paper notes that the share of all arrangements with no fixed point comes close to 1/e, and that the derangement total can be found as the whole number nearest to n! divided by e ^[1]. Here e is the constant that governs steady growth, and 1/e is close to 0.37, the value the table settles on.

That gives a useful sanity check. If your count for six objects is far from 0.37 of 720, something has gone wrong.

What if exactly some objects must stay in place?

Many puzzles ask for exactly two lids on the right jars, or exactly one key in its own lock. Choose which objects stay home, then derange the rest.

The ways add up to 24, every arrangement of four lids. Exactly three in place is impossible, a neat trick question to keep in mind.

What is the step-by-step method for clue puzzles?

1. Write the homes. List each object with the place it may not take.
2. Place the sure clues first. A clue that names a spot outright fills one object and one place at once.
3. Cross out homes and filled places. For each remaining object, list the spots still open to it.
4. Use only one left. If a place can be taken by only one object, or an object has only one place, fill it.
5. Check every clue and every home. Make sure no object sits in its own place at the end.

How does the method solve a full example?

Here is an original puzzle. Five keys, numbered 1 to 5, have been put into five locks, also numbered 1 to 5, one key per lock. No key is in the lock with its own number. Also:

1. Key 1 is in lock 3.
2. Key 4 is in lock 5.
3. Key 3 is not in lock 2.
4. Key 2 is in a lock with a lower number than the lock holding key 5.

Which key is in which lock? Before any clue there are 44 possible arrangements, and a computer check of all of them confirms that the four clues leave exactly one.

Step 1: the sure clues. Clues 1 and 2 place key 1 in lock 3 and key 4 in lock 5. Locks 1, 2 and 4 are left for keys 2, 3 and 5.

Step 2: cross out homes. Key 2 cannot use lock 2, its own, so it is in lock 1 or lock 4. Clue 3 says key 3 is not in lock 2, so it is also in lock 1 or lock 4.

Step 3: only one left. Keys 2 and 3 share locks 1 and 4 between them, so lock 2 must hold key 5.

Step 4: the last clue. Key 5 is in lock 2, and key 2 must sit in a lower-numbered lock, so key 2 is in lock 1. That leaves lock 4 for key 3.

Check. No key is in its own lock, and all four clues hold. Each clue is needed: drop any one of them and more than one arrangement fits.

Where do derangements meet other patterns?

Mixed-up orders are often counted together with a second feature of their shape. The 2009 paper counts derangements whose drops, the places where a larger number is followed by a smaller one, fall in prescribed positions ^[1]. It also shows that, apart from one special case, having drops in set places and having no fixed point tend to occur together ^[1].

Another shape is a record. In a paper published on 28 February 2010, a right-maximal value is an entry larger than everything that comes after it, so in 5 1 6 4 2 3 the values 6, 4 and 3 qualify ^[2]. The same paper lists eight kinds of record, depending on direction, on largest or smallest, and on whether the position or the value is recorded ^[2].

You can mix these into puzzles of your own: ask for arrangements with nothing in place and exactly two records, then count them by listing.

What are the most common mistakes?

• Forgetting the swap case. In the counting rule, the case where two objects simply trade places is easy to miss.
• Taking away too much. When removing arrangements with fixed objects, add back the ones removed twice.
• Ignoring one home. Write every forbidden place down before placing anything.
• Skipping the final check. One object left at home breaks the whole answer.

Can you solve this practice puzzle?

Four jars, labelled A, B, C and D, each carry one lid from a set labelled A, B, C and D. No lid is on the jar with its own letter. Lid A is on jar B, and lid C is not on jar D. Which lid is on which jar?

Try it before reading on. A hint: with lid A on jar B, only three arrangements of the other lids keep every lid off its own jar.

Answer: lid A is on jar B, lid B is on jar D, lid C is on jar A and lid D is on jar C. Lid C cannot use jar C or jar D, and jar B is taken, so it is on jar A. Lid D cannot use its own jar, so it takes jar C, and lid B takes the last jar, D.

Now try a lock riddle. Work out which digit belongs in which position, testing each place in turn and crossing out every option the clues rule out.