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
Italy
Margherita Maria Ferrari
Department of Mathematics and Statistics
University of South Florida
4202 E. Fowler Avenue
Tampa, FL 33620
USA
Emanuele Munarini and Norma Zagaglia Salvi
Dipartimento di Matematica Politecnico di Milano
Piazza Leonardo da Vinci 32
20133 Milano
Italy
Abstract:
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