Misplaced Priorities - Part 1 [Solution]

Solution for the week of 1/5/25

Our problem from 1/5/25 was

Let’s assume for a moment that the first 10 people are in line but they are a completely random order. What’s the probability that everyone is in the correct position except two people (which are definitely in the incorrect position)? What about exactly 3 people in incorrect positions? Exactly 4? Now let’s generalize. What’s the probability that out of N randomly ordered people, there are exactly k people in an incorrect position?

Hopefully some readers found that this problem was set up to help guide the puzzler to derive the formula for a derangement.

Starting with exactly 2 incorrectly located people, there is 10 choose 8 ways to select the fixed (correct) people. For the 2 people in the incorrect position, we will note that there are two possible permutations of two elements but we should only be considering those permutations that don’t leave any positions fixed. In the case of two, these is one such permutation (swapping).

\(\frac{\binom{10}{8}}{10!} \cdot \text{# of non-fixed 2 permutations} = \frac{\binom{10}{8}}{10!} \cdot 1\)

Now let’s consider the situation where exactly 3 people are swapped. If we formulate is similarly to the case with 2 we would get

\(\frac{\binom{10}{7}}{10!} \cdot \text{# of non-fixed 3 permutations}\)

The non-obvious term here is the number of non-fixed 3 permutation. There are of course 3! permutation but we need to subtract the permutations with fixed elements. We can first start by fixing 1 of the 3 elements and considering the permutations of the remaining 2 elements. There are, of course, 2! different permutations of the other elements yielding 3*2! possibilities. But we need to be careful here because the permutations of 2 elements, as discussed before, contains permutations that are fixed. Consider for a moment two different situations: (1) we had selected element 1 to be fixed and the particular permutation of 2 elements was 2→2 and 3→3, and (2) we had selected element 3 to be fixed and the particular permutation of 2 elements was 1→1 and 2→2. Obviously both of these fix every element so they are the same permutation, but both would be included in the 3*2! possibilities we described above, so we obviously over-counted. To be more precise, we over-counted by 2 . To address the over-counting, we’ll add 2.

\(\frac{\binom{10}{7}}{10!} \cdot \text{# of non-fixed 3 permutations} = \frac{\binom{10}{7}}{10!} \cdot (3! - 3 \cdot 2! + 2)\)

Ok, now let’s consider 4. We can start the same way:

\(\frac{\binom{10}{6}}{10!} \cdot \text{# of non-fixed 4 permutations} = \frac{\binom{10}{6}}{10!} \cdot (4!-1-4 \cdot \text{# of fixed permutations})\)

To count the number of non-fixed permutations, we can again start by considering all of them and then removing. We’ll start by removing all the permutations where we fix some i and then permute the 3 remaining elements, yielding [4 choose 1]*3! possibilities. As before, we will have over-counted on a number of occasions but it’s a little harder to just enumerate the ones we over-counted so let’s be a little more systematic.

Let’s now consider all the permutations with 2 fixed elements i and j that we over-counted. Let’s also define the “n-fixed permutations” to be those permutations where “n” is the number of elements that are fixed and all other elements are permuted. We’ll also use the notation S_i to be the 1-fixed, S_ij the 2-fixed, S_ijk the 3-fixed permutations and so on. Then our first removal—the 1-fixed permutations—included S_i∩S_j twice since each S_i includes every permutation with i fixed, which would also include permutations with both i and j fixed). We want to ensure we’ve only subtracted them once from the whole permutation set S, so let’s re-add. In this case there are [4 choose 2] ways to select two fixed elements and 2! permutations for the remaining elements

Of course, the first subtraction didn’t just include the permutations with 2 fixed elements. It also included the permutations with 3 fixed elements—S_ijk—and so on. In general we can construct any set of n-fixed permutations by taking the intersection of n different 1-fixed permutations (for example S_ijk= S_i∩S_j∩S_k for n=3). So it should hopefully be clear that we have counted the number of permutations with 3 fixed elements 3 times, meaning we over-counted by 2. But our attempt to correct the 2-fixed elements also factors into this since that term also over-counts the number permutations with >2 fixed elements. How much does the “2-correction” over-count the 3-fixed permutations? Well, how many different interactions of 2 elements result in a particular set of 3? That would be 3, and more generally, if we want to know how much a set of n-fixed permutations over-counted any other set if m-fixed permutations (where n<m), it will be [n choose m].

Ok, now we’re getting somewhere! We know that each time add a correction term—n-fixed permutations—to S, it will be an overcorrection for all m>n. What’s more, know the precise amount by which we’re overcorrecting. Using all this information we should have enough to pull together an expression.

\(|S| - c_1 \cdot |\text{1-fixed permutations}| + c_2 \cdot |\text{2-fixed permutations}| + c_3 \cdot |\text{3-fixed permutations}|\)

where c_i satisfies

\(-1 = c_i + \sum_{j<i} \text{corrections}_j\)

Recall that the -1 comes from the fact that we want to remove these sets with fixed elements from S exactly once. So what values does the sum of corrections yield?

Well for a given correction n we need to consider all correction i<n and each term is [n choose i]. Let’s see if enumerating for different values of n reveals anything.

We can see the pattern emerging. The even terms end up summing to -2—which requires that we add one back (recall that our goal is to remove the permutations with fixed elements so we want to remove -1)—and the odd terms end up summing to 0—which requires that we remove 1. If you would like some additional verification that this pattern continues, I wrote up a bit more algebra here since Substack’s support for LaTeX is a bit lacking. You can also consult the Inclusion-Exclusion Principal, which is exactly what we’re doing here.

So we pretty much have it! A way of counting the number of permutations that leave a subset fixed. Let’s see if we can’t do a little algebra to simplify the expression though. Again, I leave the algebra here and just present you with the final result.

\(D_n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}\)

As we said at the top, this is the formula for a derangement and we can use this to make answer our problem much easier. Now we can pretty easily compute the probability that exactly k people are in the incorrect position in line.

\(\frac{\binom{10}{k}}{10!} \cdot D_k\)

Here is the value for various k.

k=0 → 2.76e-07

k=1 → 0

k=2 → 1.24e-05

k=3 → 6.61e-05

k=4 → 5.21e-04

k=5 → 3.06e-03

k=6 → 0.0153

k=7 → 0.0613

k=8 → 0.184

k=9 → 0.368

k=10 → 0.368