## Derangements and Generalizations

```Given any sequence of n distinct objects, in how many ways can those
objects be rearranged so that none of the objects is in its original
position?  This is known as the number of "derangements" of n,
denoted by D(n).  Obviously D(1)=0 and D(2)=1.

One way (not the most efficient) of determining the value of D(n) for
any given n is by means of the inclusion/exclusion principle.  For
example, with n=5 we begin with 5! possible re-arrangements, but of
those we know that 4! leave the first object unmoved, and 4! leave
the 2nd object unmoved, and so on.  Thus there are 5*4! that leave
one specific object unmoved, so we have to subtract this number.
However, in doing so we have subtracted some of the arrangements
twice, because some of them leave both the 1st AND the 2nd element
unchanged (for example).  So we need to add back the number of
arrangements that leave any two of the objects unmoved, of which
there are C(5,2)*3!.  But then we need to subtract the number of
arrangements that leave THREE objects unmoved, and so on.  The
final result is

D(5) = 1*5! - 5*4! + 10*3! - 10*2! + 5*1! - 1*0!

= 44

In general we have

n      j  / n \
D(n)  =  SUM  (-1)  (     ) (n-j)!
j=0        \ j /

If we examine the effect of multiplying each term of this sum by n+1,
we see that the value of D(n) can easily be computed from the value
of D(n-1) by the simple recurrence formula

D(n) = n D(n-1) + (-1)^n

The first several values of D(n) for n=1,2,3,... are

0, 1, 2, 9, 44, 265, 1854, 14833, ...

The Encyclopedia of Integer Sequences (Sloane & Plouffe) lists the
values up to D(17), and also notes the exponential generating function

1          inf      x^n
---------  =  SUM  D(n) ---
(1-x) e^x      n=0       n!

Now suppose that, instead of being given just a single arrangement
of objects, we specify TWO arrangements (not necessarily distinct),
and consider the number of permutations that have no object in the
same position as it occupies in EITHER of the two given arrangements.

In this case the number clearly depends on the relation between the
two given arrangements.  If they are the same, then the number of
derangements is simply D(n), just as before.  On the other hand,
if the two given arrangements are some non-trivial permutation of
each other, the number of derangements relative to both of them is
less.

The permutation represented by going from the 1st given arrangement
to the 2nd can be expressed in terms of its cyclic components.  For
example, with n=5 objects there are seven possible cyclic structures,
corresponding to the seven partitions of 5.  The identity permutation
consists of five cycles of length 1, denoted by [1][1][1][1][1], and
in this case there are D(5)=44 derangements relative to any pair of
arrangements that are related by the identity permutation.  Also, note
that for any given 1st arrangement there is only one 2nd arrangement
that is related in this way.  On the other hand, for any given 1st
arrangement there are 10 distinct 2nd arrangements related to it
according to a permutation with the cyclic structure [1][1][1][2],
and in these cases there are only 24 derangements relative to both
of the given arrangements.

The complete list of possibilities for derangements relative to TWO
given arrangements of n objects for n=3,4,5 and 6 are listed below:

n=3:
Number of         Number of
Relation between  distinct 2nd      derangements
the two given     arrangements      relative to
arrangements      for any given     both given
1st arrangement   arrangements  Product
---------------   ------------  -------
[1][1][1]          1                  2            2
[1][2]             2                  1            2
[3]                3                  0            0
----
4 = 2^2

n=4:
# of       # of two-fold
pairs      derangements    product
------      ------------    -------
[1][1][1][1]       1            9              9
[1][1][2]          6            4             24
[2][2]             3            4             12
[1][3]             8            3             24
[4]                6            2             12
----
81 = 9^2

n=5
# of       # of two-fold
pairs      derangements      product
----------   -------------    ----------
[1][1][1][1][1]        1             44              44
[1][1][1][2]          10             24             240
[1][1][3]             20             19             380
[1][2][2]             15             16             240
[1][4]                30             16             480
[2][3]                20             12             240
[5]                   24             13             312
------
Total    1936 = 44^2

n=6:
# of     # of two-fold
pairs    derangements  product
------    ------------  -------
[1][1][1][1][1][1]       1          265         265
[1][1][1][1][2]         15          168        2520
[1][1][2][2]            45          116        5220
[1][1][1][3]            40          137        5480
[2][2][2]               15           80        1200
[1][2][3]              120           96       11520
[1][1][4]               90          114       10260
[3][3]                  40           82        3280
[2][4]                  90           80        7200
[1][5]                 144           95       13680
[6]                    120           80        9600
-----
70225 = 265^2

Of course the numbers in the second column are just the multinomial
coefficients related to the corresponding partition.  (These are called
M_2 in Abramowitz and Stegun.)

Notice that the sum of the "products" in each table is the square of
D(n).  This sum represents the number of all possible two-fold
derangements, with no restriction on the relation between the two
"given" arrangements.  Therefore, up to permutation of the identities
of the n objects, we can fix the "derangement" X, and then construct
any two "prior" arrangements, which are only required to be
derangements of X.  Each has a choice of D(n) arrangements, so
the number of possible combinations of two "priors" is D(n)^2.

So, if Q(n,j) denotes the number of two-fold derangements of n objects
relative to TWO given arrangements whose cyclic structure corresponds
to the jth partition of n, then we have the identity

SUM  M_2(j) Q(n,j)   =   D(n)^2
j

To summarize, the basic definition of an ordinary derangement can be
expressed in terms of constructs of the form

/   p1[1,2,..,n]      \
\   de[1,2,..,n/p1]   /

where p1[1,2,..,n] signifies an arbitrary arrangement of the numbers
1 through n and de[1,2,..,n/p1] signifies a derangement relative to p1,
and there are essentially D(n) distinct constructs of this kind (up to
permutation of the elements, i.e., we can always label the objects so
that p1 is the identity permutation).  In addition, we've seen that if
we define "two-fold derangements" as constructs of the form

/   p1[1,2,..,n]         \
|    p2[1,2,..,n]          |
\   de[1,2,..,n/p1,p2]   /

where p1 and p2 are arbitrary arrangements and de[1,2,..,n/p1,p2] is a
derangement relative to both p1 and p2, we find the number of distinct
such constructs (up to labelling of the objects) is D(n)^2.

Obviously this generalize to higher orders.  For example, if we consider
THREE-fold derangements of n objects relative to three given arrangements,
represented by constructs of the form

/   p1[1,2,..,n]           \
|    p2[1,2,..,n]            |
|    p3[1,2,..,n]            |
\   de[1,2,..,n/p1,p2,p3]  /

the total number of distinct constructs of this kind equals D(n)^3.

We can also consider constructs consisting of k>2 strings that are
pairwise derangements of each other.  There is only one set of
3 pairwise derangements of 3 objects:

{0 1 2}
{1 2 0}
{2 0 1}

but there are 12 distinct sets of 3 pairwise derangements of 4
objects, and 276 of 5 objects, and 10640 of 6 obbjects.

Another useful generalization is to regard ordinary derangements as
pairs of strings with the condition that the permutation from one
to the other contains no cycles of length 1 (i.e., fixed values),
and then to consider "2nd order derangements" as pairs of strings
such that the permutation from one to the other contains no cycles
of length 1 OR 2.  Likewise for higher order.  For n=5 or 6 objects
we have the following numbers of derangements of two strings:

order     n=5       n=6
-----     ---       ---
1        44       265
2        24       160
3        24       120
4        24       120
5         0       120
6         0         0

These numbers clearly reflect the possible partitions of n into
cyclic structure.
```