Journal of Integer Sequences, Vol. 21 (2018), Article 18.2.8

A Generalization of the "Problème des Rencontres"

Stefano Capparelli
Dipartimento di Scienze di Base e Applicate per l'Ingegneria
Universitá di Roma "La Sapienza"
Via A. Scarpa 16
00161 Roma

Margherita Maria Ferrari
Department of Mathematics and Statistics
University of South Florida
4202 E. Fowler Avenue
Tampa, FL 33620

Emanuele Munarini and Norma Zagaglia Salvi
Dipartimento di Matematica Politecnico di Milano
Piazza Leonardo da Vinci 32
20133 Milano


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000110 A000153 A000166 A000255 A000261 A000262 A001909 A001910 A008275 A008277 A008290 A008297 A049460 A051338 A051339 A051379 A051380 A051523 A055790 A123513 A130534 A132393 A143491 A143492 A143493 A143494 A143495 A143496 A176732 A176733 A176734 A176735 A176736 A193685 A277563 A277609 A280425 A280920 A284204 A284205 A284206 A284207.)

Received October 1 2017; revised version received February 19 2018. Published in Journal of Integer Sequences, March 7 2018.

Return to Journal of Integer Sequences home page