A Generalization of the ``Problème des Rencontres''

In this paper, we study a generalization of the classical problème des rencontres (problem of coincidences), where you are asked to enumerate all permutations π ∈ Sn with k fixed points, and, in particular, to enumerate all permutations π ∈ Sn with no fixed points (derangements). Specifically, here we study this problem for the permutations of the n + m symbols 1, 2, ..., n, v1, v2, ..., vm, where vi ∉ {1,2,...,n} for every i = 1,2,...,m. In this way, we obtain a generalization of the derangement numbers, the rencontres numbers and the rencontres polynomials. For these numbers and polynomials, we obtain the exponential generating series, some recurrences and representations, and several combinatorial identities. Moreover, we obtain the expectation and the variance of the number of fixed points in a random permutation of the considered kind. Finally, we obtain some asymptotic formulas for the generalized rencontres numbers and the generalized derangement numbers.