Rencontres numbers

In combinatorial mathematics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set { 1, ..., n } with specified numbers of fixed points: in other words, partial derangements. (Rencontre is French for encounter. By some accounts, the problem is named after a solitaire game.) For n ≥ 0 and 0 ≤ k ≤ n, the rencontres number Dn, k is the number of permutations of { 1, ..., n } that have exactly k fixed points. In combinatorial mathematics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set { 1, ..., n } with specified numbers of fixed points: in other words, partial derangements. (Rencontre is French for encounter. By some accounts, the problem is named after a solitaire game.) For n ≥ 0 and 0 ≤ k ≤ n, the rencontres number Dn, k is the number of permutations of { 1, ..., n } that have exactly k fixed points. For example, if seven presents are given to seven different people, but only two are destined to get the right present, there are D7, 2 = 924 ways this could happen. Another often cited example is that of a dance school with 7 couples, where, after tea-break, the participants are told to randomly find a partner to continue, and there are D7, 2 = 924 possibilities once more, now, that 2 previous couples meet again just by chance. Here is the beginning of this array (sequence A008290 in the OEIS): The numbers in the k = 0 column enumerate derangements. Thus for non-negative n. It turns out that where the ratio is rounded up for even n and rounded down for odd n. For n ≥ 1, this gives the nearest integer. More generally, for any k ≥ 0 {displaystyle kgeq 0} , we have The proof is easy after one knows how to enumerate derangements: choose the k fixed points out of n; then choose the derangement of the other n − k points. The numbers Dn,0/(n!) are generated by the power series e−z/(1 − z); accordingly,an explicit formula for Dn, m can be derived as follows: