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.

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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2018
permutation, derangement, rencontres number, rencontres polynomial, problème des rencontres, permanent, Ryser’s formula, Appell polynomial, Sheffer matrix, connection constant, generating function, umbral calculus, orthogonal polynomial, r-Stirling number, r-exponential polynomial, Bell number, Lah number, Lah polynomial.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11311/1050931`
• ND
• 10
• 10