Next post Previous post

Arrangements and derangements

May 20, 2020 at 10:19 PM by Dr. Drang

I’ve never thought of myself as particularly good at combinatorics or integer math in general. Most of my formal math study and the math I use in my professional life deals with the full continuity of real numbers, so that’s what I’m best at. But I do enjoy playing around outside my comfort zone.

I recently watched this Numberphile video from a few years ago. It’s about rearranging a set of items, with the goal being to determine the likelihood, after a random shuffle, that none of the items are in their original position.

When James Grime said the probability was 37%, I knew he was really talking about an asymptotic approach to 1/e1/e. Not because I’m a math genius, but because I’ve seen that come up many times in dealing with the binomial distribution and its asymptotic movement toward the Poisson distribution as the number of “events” gets large.

The description of why the probability of derangement (a lovely word choice there) tends toward 1/e1/e as the number of shuffled items gets larger is explained, although not fully explained, in the video’s extra footage.

While it’s nice to see the series expansion of e−1e^{-1}, what got me curious was the form of the individual terms of the series. It was the formula

n!k!\frac{n!}{k!}

for the alternating terms of the series. While writing out these terms (starting at about 3:30 in the second video), Dr. Grime says “You might have to think about this” and “Have a check about that.” So I did, and now I’m going to inflict my thinking on you.

I generally approach combinatoric problems by enumerating all the possibilities of a small number of items and then looking for the patterns of interest. Here, I started with a set of four cards, labeled A, B, C, and D. If we start with them in that order and shuffle, we could end up with any of the following 24 permutations:

A B C D        B A C D
A B D C        B A D C
A C B D        B C A D
A C D B        B C D A
A D B C        B D A C
A D C B        B D C A

C A B D        D A B C
C A D B        D A C B
C B A D        D B A C
C B D A        D B C A
C D A B        D C A B
C D B A        D C B A

Jumping immediately to the final answer of the first video, we can see there are 9 permutations in which none of the letters are in their original place, so the likelihood of a well-shuffled set of four cards coming out with none of the cards in their original place (i.e., zero fixed points) is

924=38=0.375\frac{9}{24} = \frac{3}{8} = 0.375

which is, as Dr. Grime says, pretty close to 1/e≈0.36791/e \approx 0.3679 or about 37%.

Now let’s try to come up with the individual terms of the series he wrote out in the second video. First, we’ll count up all the examples of where some of the cards are in their right places.

Card(s) in right place Count
A 6
B 6
C 6
D 6
A and B 2
A and C 2
A and D 2
B and C 2
B and D 2
C and D 2
A and B and C 1
A and B and D 1
A and C and D 1
B and C and D 1
A and B and C and D 1

Grouping these, we see that we have four 6s, six 2s, four 1s, and then another 1. These counts, of course, are not mutually exclusive. For example, the two cases in which A and B are in the right place overlap with cases of A being in the right place and B being in the right place. So if we wanted to count the permutations for which A or B are in their right place, we’d have to subtract off the overlap:

6+6−2=106 + 6 - 2 = 10

You can confirm this by going back to the list of all permutations. You’ll see that there are 10 with A or B in the right place: all six from the subset with A in first position, two from the subset with C in the first position, and two from the subset with D in the first position.

Returning to our table of counts, we can figure out the number of permutations with at least one fixed point:

4·6−6·2+4·1−1=24−12+4−1=154 \cdot 6 - 6 \cdot 2 + 4 \cdot 1 - 1 = 24 - 12 + 4 - 1 = 15

Therefore, the number of permutations with zero fixed points is

24−(24−12+4−1)=24−15=924 - (24 - 12 + 4 - 1) = 24 - 15 = 9

which is what we got by looking through the list directly.

How can we generalize this to any number of cards, nn? The leading term, the one outside the parentheses, is the total number of permutations, so we already know it’s general form: n!n!.

Now let’s think about the first term within the parentheses, which represents all the permutaions in which at least one card is in the right spot. We’ll start by consider the cases where the A card is in the right spot. The number of arrangements in which A is in the right spot is the number of permutations of the other cards, which is (n−1)!(n - 1)!. We can say the same thing for each of the nn cards, so the number of permutations for which at least one card is in the right spot is

n(n−1)!n (n - 1)!

In our example with n=4n = 4, that’s the four 6s (4·3!4\cdot3!) at the top of the counts table. (Yes, we could simplify this to n!n!, but we’ll see soon that it makes more sense to leave it in this form).

Now we move on to the permutations for which at least two cards are in their original spots. If there are two cards in their original places, there are n−2n - 2 other cards and (n−2)!(n - 2)! ways to arrange them. And how many ways can 2 cards out of nn be in their right places? It’s the number of combinations of nn items taken 2 at a time. Therefore, the second term inside the parentheses is

(n2)(n−2)!\binom{n}{2} (n - 2)!

which matches the six 2s we got for n=4n = 4.

At this point, we should step back and realize that our expression for the first term in the parentheses,

n(n−1)!n (n - 1)!

could have been written as

(n1)(n−1)!\binom{n}{1} (n - 1)!

The pattern should be clear. Each term for kk fixed points is

(nk)(n−k)!\binom{n}{k} (n - k)!

and the terms have alternating signs for the reasons given by Dr. Grime in the second video.

Now let’s look again at the leading term outside the parentheses: n!n!. It may seem silly to do so, but this can be written as

(n0)(n−0)!\binom{n}{0} (n - 0)!

because

(n0)=1\binom{n}{0} = 1

for all values of nn.

The method to this madness is that we now have all the terms—the leading term outside the parentheses and all the terms inside the parentheses—in the same form and we can bundle them together into nice compact summation:

∑k=0n(−1)k(nk)(n−k)!\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n - k)!

where the (−1)k(-1)^k term handles the alternating signs.

We still haven’t reached the form Dr. Grime showed. For that, we need to expand out the binomial terms and do a little algebra.

Recall that

(nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k! (n - k)!}

So

∑k=0n(−1)k(nk)(n−k)!=∑k=0n(−1)kn!k!(n−k)!(n−k)!=n!∑k=0n(−1)k1k!\sum_{k = 0}^n (-1)^k \binom{n}{k} (n - k)! = \sum_{k = 0}^n (-1)^k \frac{n!}{k! (n - k)!} (n - k)! = n! \sum_{k = 0}^n (-1)^k \frac{1}{k!}

The summation part is

∑k=0n(−1)kk!=10!−11!+12!−13!+…±1n!\sum_{k=0}^n \frac{(-1)^k}{k!} = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots \pm \frac{1}{n!}

which is exactly what the second video shows (at about 4:35).

Numberphile equation screenshot

This is a series that tends toward 1/e1/e as nn gets “large.” Since the denominators are growing by factorials, “large” isn’t very large at all. As we can see for n=4n = 4, the series is already within 2% of 1/e1/e.

Now that we know the formula for the number of permutations with zero fixed points, we should be able to figure out the formulas for the numbers of permutations with exactly one, two, three, etc. fixed points. And we can.

For exactly one fixed point, the number of permutations is

n!∑k=0n−1(−1)k1k!n! \sum_{k = 0}^{n-1} (-1)^k \frac{1}{k!}

For exactly two fixed points, it’s

n!2∑k=0n−2(−1)k1k!\frac{n!}{2} \sum_{k = 0}^{n-2} (-1)^k \frac{1}{k!}

For exactly three fixed points, it’s

n!6∑k=0n−3(−1)k1k!\frac{n!}{6} \sum_{k = 0}^{n-3} (-1)^k \frac{1}{k!}

You have the pattern now. For exactly mm fixed points,1 it’s

n!m!∑k=0n−m(−1)k1k!\frac{n!}{m!} \sum_{k = 0}^{n-m} (-1)^k \frac{1}{k!}

I’d like to say I worked these formulas out on my own, but I didn’t. I cheated. I do think, though, that I cheated in an interesting way.

I wrote a short, brute force Python program that calculated the number of fixed permutations for nn from 2 to 8 and mm from 2 to nn. It used the itertools library to generate all the permutations and looped through them, counting all the occurrences of zero, one, two, three, etc. fixed points. Here they are:2

                                   m
           0      1      2      3      4      5      6      7      8
     ----------------------------------------------------------------
  2 |      1      0      1
  3 |      2      3      0      1
  4 |      9      8      6      0      1
n 5 |     44     45     20     10      0      1
  6 |    265    264    135     40     15      0      1
  7 |   1854   1855    924    315     70     21      0      1
  8 |  14833  14832   7420   2464    630    112     28      0      1

I then took these sequences (the columns) and searched for them in the Online Encyclopedia of Integer Sequences. The sequence for one fixed point is A000240, the one for two fixed points is A000387, the one for three fixed points is A000449, and the general one for any number of fixed points is A008290.

The nice thing about the OEIS is that it doesn’t just identify the sequences, it also gives you formulas and recurrence relations in several forms, tables, graphs, references, connections to other sequences, and even musical interpretations.

Apart from helping me find the formulas in the OEIS, the table showed a few other things:

I think I’ve mentioned before that my doctor likes his patients to do puzzles and other mental stimulation as they move toward senior citizen status. Whether the “use it or lose it” theory is valid, it can’t hurt. Maybe I’ll show him this post at my next checkup as proof that I’m following doctor’s orders.

  1. I’ve carefully included the word “exactly” in these descriptions because I want to emphasize that they’re not the “at least” calculations we did earlier. Now that you’ve seen it a few times, we’ll take the “exactly” as given for the remainder of the post. ↩

  2. Sorry, I was too lazy to turn this into an HTML table. ↩

Next post Previous post