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 of $n\,$ distinct objects (i.e. the number of permutations of $n\,$ distinct objects with $r\,$ fixed points).

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

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

## Triangle of rencontres numbers

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

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

The triangle shows that the first two columns have the relations

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

giving

$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}]\,$ $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 $r\,$ = 0 1 2 3 4 5 6 7 8 9 10 11 12

The triangle $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 $T(n,r)\,$ of rencontres numbers (number of permutations of $n\,$ elements with $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 $D_{n,n-j}\,$ of the $j\,$ th nontrivial, i.e. $j\geq 2\,$ , falling diagonal from the right (indexed from 0,) where $r\,=\,n-j\,$ , are divisible by the leftmost term $D_{j,0}\,$ of the falling diagonal.

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

$D_{n,r}={\binom {n}{r}}~D_{n-r,0},\quad n-r=j\geq 2.\,$ This is obvious since there are ${\binom {n}{r}}\,$ ways to choose the $r\,$ fixed objects and the remaining $n-r\,$ objects must be a complete derangement.

 $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 $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 $n\,$ and Euler's number

$D_{n,0}=\left[{n! \over e}\right],\quad n\geq 1,\,$ where the ratio is rounded up for even $n\,$ and rounded down for odd $n\,$ .

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

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

$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

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

## Recurrences

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

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

$\sum _{r=0}^{n}D_{n,r}=n!\,$ ## Generating function

### Ordinary generating function

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

$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 $n\,$ is

$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]

$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 )}.\,$ 