Skip to main content

Rencontres Number

By

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, then once more there are D7, 2 = 924 possibilities that 2 previous couples meet again by chance.


function rencontres(n, m)
{
    //Logic
    if (n == 0 && m == 0) return 1;
    if (n == 1 && m == 0) return 0;
    //Refer to Post nCrModPFermat for details of the function
    if (m == 0) return (n - 1) * (Rencontres(n - 1, 0) + Rencontres(n - 2, 0));
    return nCrModPFermat(n, m, R) * Rencontres(n - m, 0);
}