How many permutations of numbers $(1,2,3, .., n)$ are there in which at least $2$ elements are in their original place?

Question

How many permutations of numbers $$(1,2,3, .., n)$$ are there in which at least $2$ elements are in their original place?

My idea for solving: $n! - |\text{no element stands in its original place}| - |\text{exactly one element is in its original place}|$

Is it correct?

Answer 1

We split the problem into subproblems.

How many exist with exactly one element in the same place?

Select one element to remain in the same place. For each selection, we find the derangement of the remaining (n-1) elements. . This tells us that there are $\frac{(n-1)!}{e}$ (rounded to the nearest integer so written $\left\lfloor \frac{(n-1)!}{e} +0.5 \right \rfloor$ ) ways to permutate n-1 elements so none are in the same place. This gives us $n \times \left\lfloor \frac{(n-1)!}{e} +0.5 \right \rfloor$ as we multiply by n for all the choices of fixed elements.

How many exist elements with none in the same place?

Similarly we get $\left\lfloor \frac{(n)!}{e} +0.5\right\rfloor$.

So the final answer is $n! - \left\lfloor \frac{(n)!}{e} +0.5\right\rfloor - n \times \left\lfloor \frac{(n-1)!}{e} +0.5\right\rfloor $

Answer 2

We first compute the number of permutations with zero or one elements in their original place. Using combinatorial classes we have the following class $\mathcal{P}$ of permutations with fixed points marked:

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{P} = \textsc{SET}( \mathcal{U} \times \textsc{CYC}_{=1}(\mathcal{Z}) + \textsc{CYC}_{=2}(\mathcal{Z}) + \textsc{CYC}_{=3}(\mathcal{Z}) + \cdots).$$

This gives the EGF

$$G(z, u) = \exp\left(uz+\frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} + \cdots \right) \\ = \exp\left(\log\frac{1}{1-z} + (u-1)z\right) = \frac{1}{1-z} \exp\left((u-1)z\right) \\ = \frac{1}{1-z} \exp\left(-z\right) \exp\left(uz\right).$$

We have for the desired statistic

$$n! [z^n] ([u^0] + [u^1]) G(z, u) = n! [z^n] \frac{1}{1-z} \exp(-z) (1 + z).$$

Extracting the coefficients we find

$$n! \times \left( \sum_{k=0}^n \frac{(-1)^k}{k!} + \sum_{k=0}^{n-1} \frac{(-1)^k}{k!} \right).$$

This is

$$2 n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} - (-1)^n.$$

The desired answer is thus

$$\bbox[5px,border:2px solid #00A000]{ n! + (-1)^n - 2n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.}$$

which is

$$\bbox[5px,border:2px solid #00A000]{ n! + (-1)^n - 2 \times !n.}$$

This gives the sequence

$$0, 1, 1, 7, 31, 191, 1331, 10655, 95887, 958879, \ldots$$

which is OEIS A155521, where these data are confirmed.