A lot of permutation counting problems contain a restriction that looks like

Sometimes this restriction is required for every position, sometimes only for a few positions, and sometimes the statement hides it behind something like "exactly $$$k$$$ elements move".

The completely symmetric case is called a derangement.

A permutation $$$p$$$ of $$${1,2,\ldots,n}$$$ is a derangement if

for every $$$i$$$.

I will denote the number of derangements of size $$$n$$$ by $$$D_n$$$.

For example, for $$$n=3$$$ the only derangements are

so $$$D_3=2$$$.

The first few values are

The formula for $$$D_n$$$ is classical, but IMO the more interesting part is how we get it, because the same reasoning survives in much less symmetric permutation problems.

Starting with a small case

Before writing a general formula, consider $$$n=4$$$.

There are $$$4!=24$$$ permutations in total, and we want to remove every permutation having at least one fixed point.

Suppose position $$$1$$$ is fixed. The remaining three elements can be permuted arbitrarily, so there are $$$3!$$$ such permutations. The same is true for every position, which makes

a tempting first guess.

It is not correct, because a permutation having two fixed points was subtracted twice. We have to add these permutations back.

There are $$$\binom42$$$ ways to choose two fixed positions, and after fixing them the remaining two elements can be permuted in $$$2!$$$ ways.

Now permutations having three fixed points are counted incorrectly again, so we subtract them. Continuing the same correction gives

This is exactly the kind of repeated overcounting that the Inclusion-Exclusion Principle is designed for.

Generalizing the previous argument

For every $$$i$$$, define

So $$$A_i$$$ is the set of permutations in which position $$$i$$$ is fixed.

A derangement belongs to none of

Hence the usual closed form is

The formula is useful, but there is another way to count the same permutations which gives a very convenient recurrence.

Looking at the cycle containing $$$1$$$

Take a derangement of size $$$n$$$ and look at the value in position $$$1$$$.

Since $$$1$$$ cannot remain fixed, suppose

There are $$$n-1$$$ possible choices for $$$j$$$.

After choosing $$$j$$$, exactly one of the following conditions holds:

The recurrence is therefore

with initial values $$$D_0=1$$$ and $$$D_1=0$$$. The first few values follow immediately:

Why is $$$D_0=1$$$?

Defining $$$D_0=1$$$ may look artificial at first, but there is exactly one permutation of the empty set: the empty permutation.

This convention also makes the combinatorial formulas behave naturally. For example, the number of permutations with all $$$n$$$ positions fixed is

which is exactly the identity permutation.

Another recurrence falls out of Inclusion-Exclusion

The Inclusion-Exclusion formula also gives a surprisingly short recurrence:

Equivalently,

Exactly $$$k$$$ fixed points

Now suppose we no longer want zero fixed points. Instead, we want exactly $$$k$$$ of them.

First choose the $$$k$$$ positions which remain fixed. There are

ways to do this.

After fixing these positions, none of the remaining $$$n-k$$$ positions may be fixed, otherwise the permutation would contain more than $$$k$$$ fixed points.

So the remaining part has to be a derangement, which gives

These numbers are sometimes called Rencontres numbers.

A simple identity appears

Every permutation has some number of fixed points, from $$$0$$$ to $$$n$$$.

If we group all permutations according to that number, we get

Replacing $$$n-k$$$ by $$$j$$$ gives another form of the same identity:

There is also a nice connection between this identity and the Inclusion-Exclusion formula.

Counting moved positions instead

Sometimes the statement never mentions fixed points directly and instead talks about positions satisfying

Suppose exactly $$$k$$$ positions move.

First choose these positions in $$$\binom nk$$$ ways. Inside the chosen positions, every element has to move, so they must form a derangement of size $$$k$$$.

Therefore the number of permutations with exactly $$$k$$$ moved positions is

It follows immediately that the number of permutations with at most $$$k$$$ moved positions is

Observation. Since $$$D_1=0$$$, a permutation cannot have exactly one moved position. If one value leaves its position, another value necessarily has to move as well.

Example: 888D - Almost Identity Permutations

The problem asks for permutations having at least $$$n-k$$$ fixed positions.

It is easier to reverse the condition:

Now the previous formula applies directly.

What if only some fixed points are forbidden?

The ordinary derangement problem is very symmetric: every index $$$i$$$ has exactly one forbidden assignment,

Many permutation problems break this symmetry.

Suppose there are $$$r$$$ remaining positions and $$$r$$$ remaining values, but only $$$m$$$ assignments can create forbidden fixed points.

For example, position $$$3$$$ may be free while value $$$3$$$ has already been used somewhere else. In that situation $$$p_3=3$$$ is impossible anyway, so position $$$3$$$ should not be considered a bad event.

Assume there are exactly $$$m$$$ dangerous fixed assignments.

The ordinary derangement problem is just the special case

Substituting these values gives

which is exactly $$$D_n$$$.

Example: 340E - Iahub and Permutations

We are given a partially known permutation. Some entries already contain values and the remaining positions contain -1.

The goal is to restore the permutation without creating fixed points.

The important question is not only how many positions are free, but also which free positions can actually become fixed points.

This example shows why thinking only in terms of the recurrence

can be too restrictive.

The recurrence works nicely when every position behaves in the same way. Once that symmetry disappears, the Inclusion-Exclusion interpretation is much more flexible.

Forbidden positions in general

The previous problems still have a special structure because every forbidden assignment has the form

Now suppose arbitrary assignments are forbidden, for example

A useful way to visualize this is with an $$$n\times n$$$ board.

Row $$$i$$$ represents position $$$i$$$, column $$$j$$$ represents value $$$j$$$, and cell $$$(i,j)$$$ represents the assignment

Mark every forbidden cell.

A permutation is exactly a choice of $$$n$$$ cells with one chosen cell in every row and every column.

So the problem becomes: how many such choices avoid all marked cells?

Rook numbers

Definition. Let $$$r_k$$$ be the number of ways to choose $$$k$$$ forbidden cells such that no two chosen cells share a row or a column.

Then the number of valid permutations is

Derangements as a special rook problem

For an ordinary derangement, the forbidden cells are exactly the diagonal cells

Any $$$k$$$ diagonal cells automatically use different rows and columns, so

Substituting this into the general rook formula gives

which is exactly the derangement formula.

The partial-permutation situation from 340E - Iahub and Permutations behaves similarly. There are only $$$m$$$ relevant forbidden diagonal cells, so

and the general formula becomes

So these are not separate tricks. They are different forms of the same Inclusion-Exclusion argument.

A cycle decomposition view

Every permutation can be decomposed uniquely into disjoint cycles.

For example,

can be written as

A fixed point is simply a cycle of length $$$1$$$, so a derangement is exactly a permutation whose cycle decomposition contains no $$$1$$$-cycles.

This gives another way to count $$$D_n$$$.

Suppose the cycle containing $$$1$$$ has length $$$k$$$. Since the permutation is a derangement,

This recurrence is not usually the one we implement, but it makes the cycle structure behind derangements explicit.

Generating functions

This part is not necessary for solving the standard contest problems, but it gives a compact explanation of several formulas above.

Why does $$$e$$$ appear?

Compare the derangement formula

with the Taylor expansion

Taking $$$n$$$ to infinity gives

So the probability that a uniformly random permutation is a derangement approaches

There is actually a stronger statement:

This identity is nice mathematically, but using floating point is usually not the best way to compute derangements in a programming contest. The recurrence is exact and much safer.

How many fixed points does a random permutation have?

Let $$$X$$$ be the number of fixed points in a uniformly random permutation.

A slightly surprising fact is

for every $$$n$$$, not only asymptotically.

Distribution of the number of fixed points

We already know that the number of permutations with exactly $$$k$$$ fixed points is

Therefore

After simplifying,

For fixed $$$k$$$, as $$$n$$$ grows,

Hence

This is exactly the probability mass function of a Poisson random variable with parameter $$$1$$$.

So the number of fixed points in a large random permutation approaches

The case $$$k=0$$$ gives the familiar probability $$$1/e$$$.

Implementation

For combinatorics problems, I usually keep factorials, inverse factorials and derangements in the same precomputation.

The recurrence

fits directly into the same template.

long long power(long long a, long long b, long long MOD) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % MOD;
    }
    a = (a * a) % MOD;
    b >>= 1;
  }
  return res;
}
const int N = 1e6 + 9;
const int MOD = 1e9 + 7;
int f[N], inv[N], finv[N], d[N];
void init() {
  f[0] = 1;
  for (int i = 1; i < N; i++) {
    f[i] = 1LL * i * f[i - 1] % MOD;
  }
  inv[1] = 1;
  for (int i = 2; i < N; i++) {
    inv[i] = (-(1LL * MOD / i) * inv[MOD % i]) % MOD;
    inv[i] = (inv[i] + MOD) % MOD;
  }
  finv[0] = 1;
  for (int i = 1; i < N; i++) {
    finv[i] = 1LL * inv[i] * finv[i - 1] % MOD;
  }
  d[0] = 1;
  d[1] = 0;
  for (int i = 2; i < N; ++i) {
    d[i] = 1LL * (i - 1) * (d[i - 1] + d[i - 2]) % MOD;
  }
}
int ncr(int n, int r) {
  if (n < r || n < 0 || r < 0) {
    return 0;
  }
  return 1LL * f[n] * finv[n - r] % MOD * finv[r] % MOD;
}
int npr(int n, int r) {
  if (n < r || n < 0 || r < 0) {
    return 0;
  }
  return 1LL * f[n] * finv[n - r] % MOD;
}

After calling init(), the array stores

The same precomputation also gives

For example, the number of permutations with exactly $$$k$$$ fixed points modulo MOD is

1LL * ncr(n, k) * d[n - k] % MOD;

while the number of permutations with exactly $$$k$$$ moved positions is

1LL * ncr(n, k) * d[k] % MOD;

The only thing to keep in mind is that this template computes everything modulo MOD. If a problem asks for the exact answer, such as 888D - Almost Identity Permutations, ordinary integer arithmetic should be used instead of the modular ncr().

A useful way to recognize these problems

The recurrence for $$$D_n$$$ is easy to memorize, but it is also the least reusable part of the topic.

The more useful pattern is the bad event

When some assignments are forbidden, the natural question is whether forcing a set of forbidden assignments makes the remaining objects easy to count.

For ordinary derangements, forcing $$$k$$$ bad assignments leaves

possibilities.

For partial permutations, it leaves

possibilities.

For arbitrary forbidden positions, the extra difficulty is deciding which sets of bad assignments can happen simultaneously. This is exactly where the rook numbers $$$r_k$$$ appear.

So the progression is really

The formula changes, but the Inclusion-Exclusion idea does not.

Problems

888D - Almost Identity Permutations

A direct application of choosing the moved positions and deranging them.

340E - Iahub and Permutations

A partial permutation where only some remaining assignments can become fixed points.

347B - Fixed Points

This one is not a counting problem, but it is a good exercise in thinking about fixed points and how a swap changes them.

1741B - Funny Permutation

A constructive permutation problem involving the condition

It is useful for seeing the difference between counting derangements and constructing one.

The standard formula

is worth knowing.

But if I had to keep only one thing from this topic, it would be the Inclusion-Exclusion interpretation.

A fixed point is a bad assignment.

Once that is clear, ordinary derangements, partial derangements and permutations with forbidden positions stop looking like unrelated formulas.