I am reading the book of mezo 2016 . This is part of it .
Definition 1. An FPF permutation on $n + r$ letters will be called FPF r-permutation if in its cycle decomposition the first r letters appear to be in distinct cycles. The number of FPF r-permutations denote by $D_r(n)$ and call r-derangement number. The first r elements, as well as the cycles they are contained in, will be called distinguished.
This definition was motivated by the extensive study of the so-called r-Stirling numbers of the first kind which count permutations with a fixed number of cycles where the same restriction on the first distinguished elements is added. Without this restriction we get the classical Stirling numbers.
Some recent (and not so recent) papers are studying this restriction with respect to other combinatorial objects, like set partitions , ordered lists , permutation statistics. It follows from the definition that n must be greater than or equal to r, i.e., $D_r(n) = 0$ if $n < r$ and it is equally easy to see that $D_1(n) = D(n + 1), D_r(r) = r!, (r \ge 1)$, and $D_r(r + 1) = r(r + 1)! , (r \ge 2)$. These are the initial values for the below basic recursion of the r-derangement numbers.
Theorem 2. For all $n > 2$ and $r > 0$ we have that $D_r(n) = rD_{r−1}(n − 1) + (n − 1)D_r(n − 2) + (n + r − 1)D_r(n − 1)$
I am trying to prove this theorem by recurrence but I can't prove it.
please help me
The desired recurrence is
$$D_r(n)=rD_{r-1}(n-1)+(n-1)D_r(n-2)+(n+r-1)D_r(n-1)\;.\tag{1}$$
Let the letters be $1,2,\ldots,n+r$, with $1,\ldots,r$ being distinguished, and let $\pi$ be an $r$-derangement of $[n+r]=\{1,\ldots,n+r\}$. We’ll classify $\pi$ according to how it treats $n+r$.
Since $\pi$ is fixed-point free, $n+r$ must appear in a cycle with at least one other member of $[n+r]$.
$\pi$ may have a cycle $(n+r,k)$ for some distinguished $k$. There are $r$ ways to choose $k$, and the remaining $n+r-2$ letters can be $(r-1)$-deranged in $D_{r-1}(n-1)$ ways, so there are $rD_{r-1}(n-1)$ $r$-derangements $\pi$ of this type.
$\pi$ may have a cycle $(n+r,k)$ for some $k$ that is not distinguished. There are $n-1$ possible choices for $k$ and $D_r(n-2)$ $r$-derangements of the remaining $n+r-2$ letters, so there are $(n-1)D_r(n-2)$ $r$-derangements $\pi$ of this type.
In all of the remaining $r$-permutations of $[n+r]$, $n+r$ is in a cycle of length at least $3$. If we remove $n+r$, we’re left with an $r$-derangement $\pi'$ of $[n+r-1]$. There are exactly $n+r-1$ $r$-derangements of $[n+r]$ that reduce to $\pi'$ when $n+r$ is removed from its cycle, one for each $k\in[n+r-1]$. Specifically, if $\pi_k$ is given by
$$\pi(i)=\begin{cases} n+r,&\text{if }i=k\\ \pi'(k),&\text{if }i=n+r\\ \pi'(i),&\text{otherwise,} \end{cases}$$
then $\pi_k$ is an $r$-derangement of $[n+r]$ in which $n+r$ is in a cycle of length at least $3$, and $\pi_k'=\pi'$: we’ve simply inserted $n+r$ between $k$ and $\pi'(k)$ in their cycle of $\pi'$. There are $D_r(n-1)$ possible choices for $\pi'$, and each gives rise to $n+r-1$ $r$-derangements $\pi$ by insertion of $n+r$, so there are $(n+r-1)D_r(n-1)$ $r$-derangements of $[n+r]$ in which $n+r$ is in a cycle of length at least $3$.
This accounts for all of the $r$-derangements of $[n+r]$ and establishes the recurrence $(1)$.