This site is supported by donations to The OEIS Foundation.

# Rencontres numbers

(Redirected from Number of partial derangements)

The rencontres numbers (partial derangement numbers) are the number of partial derangements, or number of permutations with r rencontres[1] of ${\displaystyle \scriptstyle n\,}$ distinct objects (i.e. the number of permutations of ${\displaystyle \scriptstyle n\,}$ distinct objects with ${\displaystyle \scriptstyle r\,}$ fixed points).

For ${\displaystyle \scriptstyle n\,\geq \,0\,}$ and ${\displaystyle \scriptstyle 0\,\leq \,r\,\leq \,n,\,}$ the rencontres number ${\displaystyle \scriptstyle D_{n,r}\,}$ is the number of permutations of ${\displaystyle \scriptstyle [n]\,=\,{\{1,\,2,\,3,\,\dots ,\,n\}}\,}$ that have exactly ${\displaystyle \scriptstyle r\,}$ fixed points.

The number of permutations with 0 rencontres ${\displaystyle \scriptstyle D_{n,0}\,}$ (number of complete derangements) are the number of derangements ${\displaystyle \scriptstyle D_{n}\,}$.

## Triangle of rencontres numbers

The terms ${\displaystyle \scriptstyle D_{n,n-j}\,}$ of the ${\displaystyle \scriptstyle j\,}$th trivial, i.e. ${\displaystyle \scriptstyle j\,\in \,\{0,\,1\}\,}$, falling diagonals from the right (indexed from 0,) where ${\displaystyle \scriptstyle r\,=\,n-j\,}$, are

• the number of permutations of n with n rencontres ${\displaystyle \scriptstyle D_{n,n}\,}$ (i.e. ${\displaystyle \scriptstyle j\,=\,0\,}$) is obviously 1, since this is the identity permutation.
• the number of permutations of n with n-1 rencontres ${\displaystyle \scriptstyle D_{n,n-1}\,}$ (i.e. ${\displaystyle \scriptstyle j\,=\,1\,}$) is obviously 0, since once you reach ${\displaystyle \scriptstyle n-1\,}$ rencontres, you necessarily have ${\displaystyle \scriptstyle n\,}$ rencontres.

The triangle shows that the first two columns have the relations

${\displaystyle D_{n,1}=n~D_{n-1,0}\,}$ (obviously, since there are ${\displaystyle \scriptstyle n\,}$ ways to choose the fixed point)
${\displaystyle D_{n,0}=D_{n,1}+(-1)^{n}\,}$ (since ${\displaystyle \scriptstyle !n=!(n-1)\cdot n+(-1)^{n},\,n\,\geq \,1,\,}$ see number of derangements (recurrences))

giving

${\displaystyle D_{n,0}=n~[(n-1)~D_{n-2,0}+(-1)^{n-1}]+(-1)^{n}=n~(n-1)~D_{n-2,0}+(-1)^{n-1}~(n-1)=(n-1)[n~D_{n-2,0}+(-1)^{n-1}]\,}$

 ${\displaystyle \scriptstyle n\,}$ = 0 1 1 0 1 2 1 0 1 3 2 3 0 1 4 9 8 6 0 1 5 44 45 20 10 0 1 6 265 264 135 40 15 0 1 7 1854 1855 924 315 70 21 0 1 8 14833 14832 7420 2464 630 112 28 0 1 9 133496 133497 66744 22260 5544 1134 168 36 0 1 10 1334961 1334960 667485 222480 55650 11088 1890 240 45 0 1 11 14684570 14684571 7342280 2447445 611820 122430 20328 2970 330 55 0 1 12 176214841 176214840 88107426 29369120 7342335 1468368 244860 34848 4455 440 66 0 1 ${\displaystyle \scriptstyle r\,}$ = 0 1 2 3 4 5 6 7 8 9 10 11 12

The triangle ${\displaystyle \scriptstyle T(n,r)\,}$ of rencontres numbers gives the infinite sequence of finite sequences

{{1}, {0, 1}, {1, 0, 1}, {2, 3, 0, 1}, {9, 8, 6, 0, 1}, {44, 45, 20, 10, 0, 1}, {265, 264, 135, 40, 15, 0, 1}, {1854, 1855, 924, 315, 70, 21, 0, 1}, {14833, 14832, 7420, 2464, 630, 112, 28, 0, 1}, {133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0, 1}, ...}

Triangle ${\displaystyle \scriptstyle T(n,r)\,}$ of rencontres numbers (number of permutations of ${\displaystyle \scriptstyle n\,}$ elements with ${\displaystyle \scriptstyle r\,}$ fixed points). (Cf. A008290)

{1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 9, 8, 6, 0, 1, 44, 45, 20, 10, 0, 1, 265, 264, 135, 40, 15, 0, 1, 1854, 1855, 924, 315, 70, 21, 0, 1, 14833, 14832, 7420, 2464, 630, 112, 28, 0, 1, 133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0, 1, ...}

## Triangle of D_{n, r} / D_{n−r, 0}

The following triangle reveals that the terms ${\displaystyle \scriptstyle D_{n,n-j}\,}$ of the ${\displaystyle \scriptstyle j\,}$th nontrivial, i.e. ${\displaystyle \scriptstyle j\geq 2\,}$, falling diagonal from the right (indexed from 0,) where ${\displaystyle \scriptstyle r\,=\,n-j\,}$, are divisible by the leftmost term ${\displaystyle \scriptstyle D_{j,0}\,}$ of the falling diagonal.

Furthermore, the subtriangle excluding the rightmost two (trivial) falling diagonals (i.e. for ${\displaystyle \scriptstyle n-r\,=\,j\,\geq \,2\,}$) is now the corresponding subtriangle of the Pascal triangle, thus we have

${\displaystyle D_{n,r}={\binom {n}{r}}~D_{n-r,0},\quad n-r=j\geq 2.\,}$

This is obvious since there are ${\displaystyle \scriptstyle {\binom {n}{r}}\,}$ ways to choose the ${\displaystyle \scriptstyle r\,}$ fixed objects and the remaining ${\displaystyle \scriptstyle n-r\,}$ objects must be a complete derangement.

 ${\displaystyle \scriptstyle n\,}$ = 0 1 1 0 1 2 1 0 1 3 1 3 0 1 4 1 4 6 0 1 5 1 5 10 10 0 1 6 1 6 15 20 15 0 1 7 1 7 21 35 35 21 0 1 8 1 8 28 56 70 56 28 0 1 9 1 9 36 84 126 126 84 36 0 1 10 1 10 45 120 210 252 210 120 45 0 1 11 1 11 55 165 330 462 462 330 165 55 0 1 12 1 12 66 220 495 792 924 792 495 220 66 0 1 ${\displaystyle \scriptstyle r\,}$ = 0 1 2 3 4 5 6 7 8 9 10 11 12

## Formulae

The number of derangements of a nonempty set may be obtained from the ratio of the factorial of ${\displaystyle \scriptstyle n\,}$ and Euler's number

${\displaystyle D_{n,0}=\left[{n! \over e}\right],\quad n\geq 1,\,}$

where the ratio is rounded up for even ${\displaystyle \scriptstyle n\,}$ and rounded down for odd ${\displaystyle \scriptstyle n\,}$.

${\displaystyle D_{n,r}={n \choose r}\cdot D_{n-r,0}.\,}$

The proof is easy after one knows how to enumerate derangements: choose the ${\displaystyle \scriptstyle r\,}$ fixed points out of ${\displaystyle \scriptstyle n\,}$; then choose the derangement of the other ${\displaystyle \scriptstyle n-r\,}$ points.

An explicit formula for ${\displaystyle \scriptstyle D_{n,r}\,}$ can be derived as follows

${\displaystyle D(n,r)={\frac {n!}{r!}}[z^{n-r}]{\frac {e^{-z}}{1-z}}={\frac {n!}{r!}}\sum _{k=0}^{n-r}{\frac {(-1)^{k}}{k!}}.}$

This immediately implies that

${\displaystyle D_{n,r}={n \choose r}D_{n-r,0}\;\;{\mbox{ and }}\;\;{\frac {D_{n,r}}{n!}}\approx {\frac {e^{-1}}{r!}}}$

for ${\displaystyle \scriptstyle n\,}$ large, ${\displaystyle \scriptstyle r\,}$ fixed.

## Recurrences

The numbers in the ${\displaystyle \scriptstyle r\,=\,0\,}$ column are the number of derangements (number of permutations with 0 rencontres or number of permutations of n with n derangements.) Thus

${\displaystyle D_{0,0}=1,\,}$
${\displaystyle D_{1,0}=0,\,}$
${\displaystyle D_{n,0}=(n-1)(D_{n-1,0}+D_{n-2,0}),\quad n\geq 2.\,}$

## Other formulae

${\displaystyle \sum _{r=0}^{n}D_{n,r}=n!\,}$

## Generating function

### Ordinary generating function

O.g.f. for column ${\displaystyle \scriptstyle r\,}$ is [TO BE VERIFIED]

${\displaystyle G_{\{D_{n,r}\}}(x)\equiv \sum _{n=r}^{\infty }D_{n,r}~x^{n}={\frac {1}{r!}}\sum _{n=r}^{\infty }n!{\frac {x^{n}}{(1+x)^{n+1}}},\quad r\geq 0.\,}$

O.g.f. for row ${\displaystyle \scriptstyle n\,}$ is

${\displaystyle G_{\{D_{n,r}\}}(x)\equiv \sum _{r=0}^{n}D_{n,r}~x^{r}=n!\sum _{r=0}^{n}{\frac {1}{r!}}(-1)^{r}(1-x)^{r},\quad n\geq 0.\,}$

### Exponential generating function

[TO BE VERIFIED]

${\displaystyle E_{\{D_{n,r}\}}(x,y)\equiv \sum _{n=0}^{\infty }\sum _{r=0}^{n}{\frac {D_{n,r}}{n!~r!}}x^{n}y^{r}=\exp {\Bigg (}{\frac {x(y-1)}{1-x}}{\Bigg )}.\,}$