Associated Topics || Dr. Math Home || Search Dr. Math

### Word Derangements and Arrangements

```
Date: 11/30/98 at 15:34:52
From: julie
Subject: Derangements

Hi Dr. Math,

I have to write this paper on derangements but I'm a little stuck.
First you have to find the arrangements on let's say a 3 letter word,
JOE. JOE has 6 arrangements: J,O,E  J,E,O  O,J,E  O,E,J  E,J,O  E,O,J.
Now to find the derangements, you have to put the letters in
alphabetical order, which is E J O. This means that E cannot be the 1st
letter, J cannot be the 2nd letter, and O cannot be the 3rd letter.
Since there are only two arrangements that meet this criterion, JOE
has 2 derangements, J,O,E and O,E,J.

I figured out all the derangements for 2, 3, 4, and 5 lettered words
by listing them, but when I got up to the 6th lettered word, I got
stuck because a 6 lettered word has 720 arrangements. It'll be
impossible for me to list all the derangements. Is there a formula
that I can use to find the derangements of arrangements?
```

```
Date: 11/30/98 at 17:00:38
From: Doctor Rob
Subject: Re: derrangements

Yes, there is. The formula is:

D(n) = n! - n!/1! + n!/2! - n!/3! + n!/4! - ... + (-1)^n*n!/n!

When n = 6, this gives:

D(6) = 720 - 720 + 720/2 - 720/6 + 720/24 - 720/120 + 720/720
= 720 - 720 + 360 - 120 + 30 - 6 + 1
= 265

This formula is gotten by starting with the n! arrangements, then
subtracting those with one object fixed, C(n,1)*(n-1)! = n!/1!, then
adding those with two objects fixed, C(n,2)*(n-2)! = n!/2!, because
they had been subtracted twice. Then we subtract those with three
objects fixed, C(n,3)*(n-3)! = n!/3!, because they had been subtracted
thrice, but added back in thrice. We continue thus until we run out
of objects.

A short way to compute this is to pick the closest integer to n!/e.
Here e is the base of natural logarithms, 2.718281828459045.... If
n = 6, this gives 720/2.718281828459045... = 264.8731976..., so
D(6) = 265, the same answer we got above. The first few answers are
0, 1, 2, 9, 44, 265, 1854, 14833, 133496, and 1334961.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 12/02/98 at 17:40:36
From: julie
Subject: Derangements

Hello Dr. Math,

I wrote to you before to ask if there was a formula to find the
derangements of arrangements. You replied by sending me this formula:

D(n) = n! - n!/1! + n!/2! - n!/3! + n!/4! - ......+ (-1)^n*n!/n!

I understand how to use the formula, but I'm not sure how to derive
it. You gave me an explanation, but it was a bit confusing. Can you
please explain it again? Thank you!
```

```
Date: 12/03/98 at 10:02:41
From: Doctor Rob
Subject: Re: Derangements

This is an application of the Inclusion-Exclusion Principle. We want
to know the number of arrangements with exactly zero items in the
designated spots. That is D(n).

We can count the number C(n,k) of ways to choose k spots out of n to
be designated; then there are (n-k)! ways to arrange the other n-k
letters. This makes a total of C(n,k)*(n-k)! = n!/k!. This is, however,
more than the number of arrangements with k items in their designated
spots, since some arrangements are counted more than once.

We start with all the arrangements; that is, those with at least zero
items in the designated spots. There are n!/0! = n! of them. From this
number we subtract the number we computed above, n!/1!. This is too
much to subtract, because there are arrangements with two items in
their designated spots which are counted twice, once for each of the
two. To compensate, we add back in the then number of arrangements
with two or more items in the designated spots, namely n!/2!. But we
have overcompensated, so we subtract the number of arrangements with
three or more items, and so on.

Example: RUST, alphabetically RSTU. There are 4! = 24 arrangements:

RSTU, RSUT, RTSU, RTUS, RUST, RUTS, SRTU, SRUT, STRU, STUR, SURT,
SUTR, TRSU, TRUS, TSRU, TSUR, TURS, TUSR, URST, URTS, USRT, USTR,
UTRS, UTSR.

There are C(4,1) = 4 ways to pick a single letter to be in its
designated spot, and for each, there are (4-1)! = 3! = 6 ways to
rearrange the other letters, for a total of 4*6 = 24 = 4!/1!:

R fixed:  RSTU, RSUT, RTSU, RTUS, RUST, RUTS
S fixed:  RSTU, RSUT, TSRU, TSUR, USRT, USTR
T fixed:  RSTU, RUTS, SRTU, SUTR, URTS, USTR
U fixed:  RSTU, RTSU, SRTU, STRU, TRSU, TSRU

We have to discard these, but some of them appear twice (or more). To
compensate, we add back in the number of arrangements with two letters
in their designated spots. There are C(4,2) = 6 ways to pick two
letters to be in their designated spots, and for each there are 2! = 2
ways to rearrange the other letters, for a total of 6*2 = 12 = 4!/2!:

R,S fixed:  RSTU, RSUT
R,T fixed:  RSTU, RUTS
R,U fixed:  RSTU, RTSU
S,T fixed:  RSTU, USTR
S,U fixed:  RSTU, TSRU
T,U fixed:  RSTU, SRTU

Now we have overcompensated, since some arrangements with two letters
fixed also have three letters fixed, so we have to subtract the number
of these to compensate. There are C(4,3) = 4 ways to choose the three
letters to be in their designated spots, and for each there is 1! = 1
way to rearrange the other letter, for a total of 4*1 = 4 = 4!/3!:

R,S,T fixed:  RSTU
R,S,U fixed:  RSTU
R,T,U fixed:  RSTU
S,T,U fixed:  RSTU

Again, we have overcompensated, since some (actually all) arrangements
with three letters fixed also have four letters fixed, so we have to
add back in the number of these to compensate. There is C(4,4) = 1 way
to choose the four letters to be in their designated spots, and for
each there is 0! = 1 way to arrange the remaining zero letters, for a
total of 1*1 = 1 = 4!/4!:

R,S,T,U fixed:  RSTU

That makes the total:

D(4) = 4!/0! - 4!/1! + 4!/2! - 4!/3! + 4!/4!
= 24 - 24 + 12 - 4 + 1
= 9

The arrangement RSTU with four letters fixed was counted once in the
original tally, subtracted four times, added six times, subtracted four
times, then added once, for a net count of 0. There are no arrangements
with exactly three letters fixed. You can verify each arrangement with
exactly two letters fixed was counted once, subtracted twice, and added
once, for a net count of 0. You can verify each arrangement with
exactly one letter fixed was counted once, and subtracted once, for a
net count of 0. All those with no letter fixed were counted once and
never subtracted, for a net count of 1. For any arrangement with
exactly k > 0 letters fixed, the net count is
C(k,0) - C(k,1) + C(k,2) - ... = (1-1)^k = 0, by the Binomial Theorem.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```

```Date: 09/14/2017 at 14:41:06
From: Thayer
Subject: "Physical" meaning of terms in Inclusion-Exclusion for n=4

I understand that the inclusion-exclusion formula for n = 4 gives the
proper 9 derangements. But I don't understand the meaning of the terms
when applied to the set {1, 2, 3, 4}.

In particular, I can't figure out the actual arrangements in its terms.

Put another way: The number of derangements with 3 fixed elements is
4C3*1! = 4. But if 3 elements are fixed, there is only one choice for the
4th element.

What are the 4 derangements of {1234} that have three elements fixed?
Isn't there only one -- namely, 1234?

```

```
Date: 09/14/2017 at 21:06:46
From: Doctor Peterson
Subject: Re:

Hi, Thayer.

I suppose you are referring to a variation of the formula above:

D(n) = n! - n!/1! + n!/2! - n!/3! + n!/4! - ... + (-1)^n*n!/n!

Your version, though you didn't state it, is the unsimplified form of the
same formula.

In your case, n = 4, and we have

D(4) = 4! - 4!/1! + 4!/2! - 4!/3! + 4!/4!
= 24 -   24  +   12  -   4   +   1
= 9

The first term is the total number of possible arrangements; the second is
the number of those with some one element fixed (i.e., A fixed, or B
fixed, or C fixed, or D fixed, so that those with at least two fixed are
counted twice); the next is the number of those with some pair of elements
fixed (AB, AC, AD, BC, BD, or CD), and so on.

Let's make a table showing the arrangements counted in each term. To avoid
confusing an element with a number of elements, I'm going to use letters
(ABCD) rather than digits (1234). This also lets me put an element in
lower case when it is in its place, to make them easy to see.

# fixed --> 1          |              2              |   3   |   4
------------------- ----------------------------- ------- -----
all|  A    B    C    D    AB   AC   AD   BC   BD   CD
---- ---- ---- ---- ---- |---- ---- ---- ---- ---- ----|-------|-----
abcd abcd abcd abcd abcd  abcd abcd abcd abcd abcd abcd  abcd*4  abcd
abDC abDC abDC            abDC
aCBd aCBd           aCBd            aCBd
aCDB aCDB
BAcd           BAcd BAcd                           BAcd
BCDA
BDAC
BDcA           BDcA
CABd                CABd
CbDA      CbDA
CDAB
CDBA
DABC
DAcB           DAcB
DbAC      DbAC
DbcA      DbcA DbcA                      DbcA
DCAB
DCBA
---- ---- ---- ---- ---- |---- ---- ---- ---- ---- ----|-------| ----
24    6    6    6    6     2    2    2    2    2    2       4     1
---- ------------------- |-----------------------------|-------| ----
24                  24                             12       4     1

The main idea is that when we say we are counting "arrangements with one
object fixed," what we really mean is "arrangements with x fixed, for each
possible x." This counts many arrangements twice, so we have to subtract
those duplicates.

In the column above that enumerates 3 fixed arrangements, abcd is counted
four times (once each for ABC, ABD, ACD, and BCD), which I didn't bother
breaking out into four sub-columns. This is what you were specifically
asking about: yes, there is only one such arrangement. But we count it
four times, once for each possible choice of 3.

I liked your idea of listing everything explicitly, which is why I wrote
more than just the one paragraph above. A table does make the whole idea
a lot clearer. What do you think?

- Doctor Peterson, The Math Forum at NCTM
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search