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

stefano.capparelli@sbai.uniroma1.it

Margherita Maria Ferrari Department of Mathematics and Statistics

University of South Florida

4202 E. Fowler Avenue

Tampa, FL 33620

USA

mmferrari@usf.edu

Emanuele Munarini and Norma Zagaglia Salvi^{1}

Dipartimento di Matematica

Politecnico di Milano Piazza Leonardo da Vinci 32

20133 Milano

Italy

emanuele.munarini@polimi.it
norma.zagaglia@polimi.it

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 π ∈ 𝕊_{n} with k fixed points, and, in particular, to enumerate all permutations π ∈ 𝕊_{n} with no fixed points (derangements). Specifically, here we study this problem for the permutations of the n + m symbols 1, 2, …, n, v_{1}, v_{2}, …, v_{m}, where v_{i} ∉ {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.

1This work is partially supported by MIUR (Ministero dell’Istruzione, dell’Università e della Ricerca).

1 Introduction

The problème des rencontres, or problem of coincidences (also called problème de Montmort, or problème des chapeaux; see ([13], [8, pp. 9–12, 32], [18, p. 57], [1]), is one of the classical problems in enumerative combinatorics and in probability. From a combinatorial point of view, it is the problem of enumerating all permutations π ∈ 𝕊_{n} with k fixed points. In particular, for k = 0, it reduces to the problem of enumerating all permutations π ∈ 𝕊_{n} with no fixed points. For the history of the original problem and its solutions, see Takacs [24].

The aim of this paper is to extend the problème des rencontres to the permutations of the symbols 1, 2, …, n, v_{1}, v_{2}, …, v_{m}, where v_{i} ∉ {1, 2, …, n} for every i = 1, 2, …, m. The set of these generalized permutations is denoted by 𝕊_{n}^{(m)}. A fixed point of a permutation π = a_{1} ⋯ a_{n}a_{n+1} ⋯ a_{n+m} ∈ 𝕊_{n}^{(m)} is, by definition, an index i ∈ {1, 2, …, n} such that a_{i} = i. The permutations in 𝕊_{n}^{(m)} with no fixed points are called generalized derangements and their number is denoted by d_{n}^{(m)}. Clearly, for m = 0 we have the ordinary derangements and the ordinary derangement numbers d_{n} (\underline{A000166} in the On-Line Encyclopedia of Integer Sequences).

The permutations in 𝕊_{n}^{(m)} can be interpreted as particular bijective functions, generalizing the widened permutations (corresponding to the case m = 1) introduced and studied in [4]. For any m ∈ ℕ, an m-widened permutation is a bijection between two (n + m)-sets having n elements in common. More precisely, given an n-set X and two m-sets U and V, such that X, U and V are pairwise disjoint, we have a bijection f : X ∪ U → X ∪ V. If U = {u_{1}, …, u_{m}} and V = {v_{1}, …, v_{m}}, then f is equivalent to an (m+1)-tuple (λ_{1}, …, λ_{m}, σ), where each λ_{i} is a linear order and σ is a permutation, defined as follows: λ_{i} = [u_{i}, f(u_{i}), f^{2}(u_{i}), …, f^{h}(u_{i}), v_{j}] where h + 1 is the minimum positive integer such that there exists a j ∈ {1, 2, …, m} such that f^{h+1}(u_{i}) = v_{j}, and σ is the remaining permutation on X \ (X_{λ_{1}} ∪ ⋯ ∪ X_{λ_{m}}), where X_{λ_{i}} = {f(u_{i}), f^{2}(u_{i}), …, f^{h}(u_{i})} ⊆ X. For instance, the 4-widened permutation

f = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & u_{1} & u_{2} & u_{3} & u_{4} \\ 7 & 1 & v_{2} & 4 & 8 & v_{4} & 2 & 6 & v_{3} & 9 & v_{1} & 5 & 3 \end{matrix} )

is equivalent to the quintuple (λ_{1}, λ_{2}, λ_{3}, λ_{4}, σ), where λ_{1} = [u_{1}, 9, v_{3}], λ_{2} = [u_{2}, v_{1}], λ_{3} = [u_{3}, 5, 8, 6, v_{4}], λ_{4} = [u_{4}, 3, v_{2}], and σ = (172)(4). If we consider only the second line in the two-line representation of f, we have the corresponding generalized permutation π = 7 1 v_{2} 4 8 v_{4} 2 6 v_{3} 9 v_{1} 5 3 ∈ 𝕊_{9}^{(4)}. Notice that π, or f, has only one fixed point in position 4. In particular, π is a generalized derangement when the corresponding m-widened permutation f, with decomposition (λ_{1}, …, λ_{m}, σ), is an m-widened derangement, that is when σ is an ordinary derangement. In the rest of the paper, the generalized permutations in 𝕊_{n}^{(m)} and the generalized derangements in 𝕊_{n}^{(m)} are identified with the corresponding m-widened permutations and the m-widened derangements, respectively.

The paper is organized as follows. In Section 2, we obtain an explicit formula for the generalized derangement numbers d_{n}^{(m)} and their exponential generating series. Moreover, we establish the connection between these numbers and the r-derangement numbers [26]. In Section 3, we introduce the generalized rencontres numbers D_{n,k}^{(m)} and the associated polynomials D_{n}^{(m)}(x). Then, we obtain their exponential generating series, some recurrences and some representations (in terms of determinants and integrals). In Sections 4 and 5, we obtain several identities involving the generalized rencontres polynomials and other combinatorial polynomials and numbers. In Section 6, we compute the expectation and the variance of the random variable X_{n}^{(m)} giving the number of fixed points of a permutation in 𝕊_{n}^{(m)}. In particular, we obtain that the expectation and the variance tend to 1 as n → +∞. Finally, in Section 7, we obtain some asymptotic formulas for the generalized rencontres numbers D_{n,k}^{(m)} and the generalized derangement numbers d_{n}^{(m)}.

2 Generalized derangement numbers

Given n ∈ ℕ, let [n] = {1, 2, …, n}. Given m, n ∈ ℕ, let 𝕊_{n}^{(m)} be the set of all permutations of the symbols 1, 2, …, n, v_{1}, v_{2}, …, v_{m}. Clearly |𝕊_{n}^{(m)}| = (m + n)!, and for m = 0 we have the ordinary permutations. A permutation π = a_{1}a_{2} ⋯ a_{m+n} ∈ 𝕊_{n}^{(m)} has a fixed point when there exists an index i ∈ [n] such that a_{i} = i. For instance, in π = 4 v_{2} 3 v_{3} 5 v_{1} 2 1 we have only two fixed points in position 3 and 5. Notice that, in the general case, a fixed point can appear only in the first n positions. A generalized derangement is a permutation in 𝕊_{n}^{(m)} with no fixed points. The generalized derangement number d_{n}^{(m)} is the number of generalized derangements in 𝕊_{n}^{(m)}. For m = 0, we have the ordinary derangement numbers d_{n} [8, p. 182] [18, p. 65] (\underline{A000166}).

Theorem 1. The generalized derangement numbers can be expressed as

d_{n}^{(m)} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}(m + n − k)!  (1)

and have exponential generating series

d^{(m)}(t) = ∑_{n≥0} d_{n}^{(m)} \frac{t^{n}}{n!} = \frac{m! e^{−t}}{(1 − t)^{m+1}} .  (2)

Proof. Identity (1) can be proved combinatorially using the inclusion-exclusion principle. Let A_{i} be the set of permutations π = a_{1}a_{2} ⋯ a_{m+n} ∈ 𝕊_{n}^{(m)} such that a_{i} = i, and let A′_{i} be its complementary with respect to 𝕊_{n}^{(m)}, for every i = 1, …, n. Then, by the inclusion-exclusion principle, we have

d_{n}^{(m)} = |A′_{1} ∩ A′_{2} ∩ ⋯ ∩ A′_{n}| = ∑_{I⊆[n]}(−1)^{|I|} |⋂_{i∈I} A_{i}| .

The set ⋂_{i∈I} A_{i} consists of all permutations π = a_{1}a_{2} ⋯ a_{m+n} ∈ 𝕊_{n}^{(m)} such that a_{i} = i, for every i ∈ I. So, it is equivalent to the set 𝕊_{n−|I|}^{(m)} and consequently its size is (m + n − |I|)!. Hence, we have the identity

d_{n}^{(m)} = ∑_{I⊆[n]}(−1)^{|I|}(m + n − |I|)!

which is equivalent to identity (1). Now, by identity (1), we have the generating series

d^{(m)}(t) = ∑_{n≥0}(−1)^{n} \frac{t^{n}}{n!} · ∑_{n≥0}(m + n)!\frac{t^{n}}{n!} = m! e^{−t} · ∑_{n≥0} \binom{m + n}{m}t^{n}

which is equivalent to series (2).

For the first values of n, we have the generalized derangement numbers

\begin{matrix}d_{0}^{(m)} = m! \\ d_{1}^{(m)} = m! · m \\ d_{2}^{(m)} = m! · (m^{2} + m + 1) \\ d_{3}^{(m)} = m! · (m^{3} + 3m^{2} + 5m + 2) \\ d_{4}^{(m)} = m! · (m^{4} + 6m^{3} + 17m^{2} + 20m + 9) . \end{matrix}  (3)

Remark 2. The generalized derangement numbers d_{n}^{(m)} appear also in [16, 17] and form sequences \underline{A000166}, \underline{A000255}, \underline{A055790}, \underline{A277609}, \underline{A277563}, \underline{A280425}, \underline{A280920}, \underline{A284204}, \underline{A284205}, \underline{A284206}, \underline{A284207} in [23] for m = 0, 1, …, 10, respectively. Similarly, the numbers d_{n}^{(m)}/m! form sequences \underline{A000166}, \underline{A000255}, \underline{A000153}, \underline{A000261}, \underline{A001909}, \underline{A001910}, \underline{A176732}, \underline{A176733}, \underline{A176734}, \underline{A176735}, \underline{A176736} in [23] for m = 0, …, 10, respectively. Notice that, the numbers d_{n}^{(m)}/m! count the generalized derangements when v_{1} = ⋯ = v_{m} = v.

An r-permutation of the set {1, 2, …, r, r + 1, …, n + r} is a permutation in which the elements 1, 2, …, r belong to different cycles [6]. An r-derangement is an r-permutation with no fixed points [26]. The generalized derangement numbers d_{n}^{(m)} and the r-derangement numbers D_{r}(n) [26] are related as follows.

Theorem 3. For every r, n ∈ ℕ, we have

D_{r}(n) = \binom{n}{r}d_{n−r}^{(r)}  (n ≥ r) .  (4)

Proof. We have the exponential generating series [26]

∑_{n≥r} D_{r}(n)\frac{t^{n}}{n!} = \frac{t^{r}e^{−t}}{(1 − t)^{r+1}} = \frac{t^{r}}{r!} d^{(r)}(t) = \frac{t^{r}}{r!} ∑_{n≥0} d_{n}^{(r)} \frac{t^{n}}{n!}

= ∑_{n≥0} \binom{n + r}{r}d_{n}^{(r)} \frac{t^{n+r}}{(n + r)!} = ∑_{n≥r} \binom{n}{r}d_{n−r}^{(r)} \frac{t^{n}}{n!} .

Comparing the coefficients of t^{n}/n!, we have identity (4).

Remark 4. Let f : X ∪ U → X ∪ V be an m-widened permutation on a set X of size n, and let (λ_{1}, …, λ_{m}, σ) be its decomposition. Suppose that in f each linear order λ_{i} (starting with u_{i}) ends with v_{i}, i.e., λ_{i} = [u_{i}, b_{1}, …, b_{h}, v_{i}]. If we replace each linear order λ_{i} with a cycle γ_{i} = (b_{1} ⋯ b_{h} n + i), by setting u_{i} = n + i and by removing v_{i}, we obtain a permutation of the set {1, 2, …, n + m} where the elements n + 1, …, n + m belong to different cycles. So, these m-widened permutations are equivalent to the m-permutations. In particular, if each λ_{i} contains at least one element of X, i.e., λ_{i} ≠ [u_{i}, v_{i}], and σ does not have fixed points, then we have the m-derangements [26].

Other properties for the generalized derangement numbers are obtained in next sections as specialization of the more general properties of the generalized rencontres polynomials.

3 Generalized rencontres numbers and polynomials

Let D_{n,k}^{(m)} be the generalized rencontres numbers, i.e., the number of permutations π ∈ 𝕊_{n}^{(m)} with k fixed points. Removing the k fixed points and normalizing the remaining letters, we obtain a derangement δ ∈ 𝕊_{n−k}^{(m)}. So, we have at once the identity

D_{n,k}^{(m)} = \binom{n}{k}d_{n−k}^{(m)} .  (5)

For m = 0 we have the ordinary rencontres numbers D_{n,k}, [18, pp. 57, 58, 65], forming sequence \underline{A008290}. For m = 1 we have sequence \underline{A123513}, while for m ≥ 2 the sequences do not appear in [23]. Let D^{(m)} = [D_{n,k}^{(m)}]_{n,k≥0} be the infinite lower triangular matrix generated by the generalized rencontres numbers. For m = 1 and m = 2, we have the matrices

D^{(1)} = [\begin{matrix}1 \\ 1 & 1 \\ 3 & 2 & 1 \\ 11 & 9 & 3 & 1 \\ 53 & 44 & 18 & 4 & 1 \\ 309 & 265 & 110 & 30 & 5 & 1 \\ 2119 & 1854 & 795 & 220 & 45 & 6 & 1 \\ … \end{matrix}] , \frac{1}{2}D^{(2)} = [\begin{matrix}1 \\ 2 & 1 \\ 7 & 4 & 1 \\ 32 & 21 & 6 & 1 \\ 181 & 128 & 42 & 8 & 1 \\ 1214 & 905 & 320 & 70 & 10 & 1 \\ 9403 & 7284 & 2715 & 640 & 105 & 12 & 1 \\ … \end{matrix}] .

A polynomial sequence {p_{n}(x)}_{n∈ℕ} is an Appell sequence [3, 15] [20, p. 86] [21] [25, p. 314] when its exponential generating series has the form

∑_{n≥0} p_{n}(x) \frac{t^{n}}{n!} = g(t) e^{xt}

where g(t) = ∑_{n≥0} g_{n} \frac{t^{n}}{n!} is an exponential series with g_{0} = 1. From this definition it follows that p_{n}(x) is a polynomial of degree n of the form

p_{n}(x) = ∑_{k=0}^{n} \binom{n}{k}g_{n−k}x^{k}

such that p′_{n}(x) = np_{n−1}(x). Several classical polynomial sequences are of this kind [20, p. 86] [21, 7]. This is true also for the generalized rencontres polynomials, defined by

D_{n}^{(m)}(x) = ∑_{k=0}^{n} D_{n,k}^{(m)}x^{k} = ∑_{k=0}^{n} \binom{n}{k}d_{n−k}^{(m)}x^{k} .  (6)

Indeed, using series (2), we have at once

Theorem 5. The polynomials D_{n}^{(m)}(x) form an Appell sequence having exponential generating series

D^{(m)}(x; t) = ∑_{n≥0} D_{n}^{(m)}(x) \frac{t^{n}}{n!} = d^{(m)}(t) e^{xt} = \frac{m! e^{(x−1)t}}{(1 − t)^{m+1}} .  (7)

In particular, D_{n}^{(m)}(x) has degree n and (D_{n}^{(m)}(x))′ = nD_{n−1}^{(m)}(x).

Clearly, we have D_{n}^{(m)}(0) = D_{n,0}^{(m)} = d_{n}^{(m)} and D_{n}^{(m)}(1) = (m + n)!. Moreover, for m = 0, we have the ordinary rencontres polynomials D_{n}(x) = D_{n}^{(0)}(x), [18], whose exponential generating series are denoted simply by D(x; t). For the first values of n, we have the polynomials

\begin{matrix}D_{0}^{(m)}(x) = m! \\ D_{1}^{(m)}(x) = m!(x + m) \\ D_{2}^{(m)}(x) = m!(x^{2} + 2mx + m^{2} + m + 1) \\ D_{3}^{(m)}(x) = m!(x^{3} + 3mx^{2} + 3(m^{2} + m + 1)x + m^{3} + 3m^{2} + 5m + 2) \\ D_{4}^{(m)}(x) = m!(x^{4} + 4mx^{3} + 6(m^{2} + m + 1)x^{2}+ \\ + 4(m^{3} + 3m^{2} + 5m + 2)x + m^{4} + 6m^{3} + 17m^{2} + 20m + 9) . \end{matrix}  (8)

Theorem 6. The polynomials D_{n}^{(m)}(x) admit the explicit expression

D_{n}^{(m)}(x) = ∑_{k=0}^{n} \binom{n}{k}(m + k)!(x − 1)^{n−k}  (9)

and satisfy the recurrences

D_{n+2}^{(m)}(x) = (x + m + n + 1)D_{n+1}^{(m)}(x) − (n + 1)(x − 1)D_{n}^{(m)}(x)  (10)

and

D_{n+1}^{(m+1)}(x) = (n + 1)D_{n}^{(m+1)}(x) + (m + 1)D_{n+1}^{(m)}(x) .  (11)

In particular, for x = 0, we have that the numbers d_{n}^{(m)} satisfy the recurrences

d_{n+2}^{(m)} = (m + n + 1)d_{n+1}^{(m)} + (n + 1)d_{n}^{(m)}  (12)

and

d_{n+1}^{(m+1)} = (n + 1)d_{n}^{(m+1)} + (m + 1)d_{n+1}^{(m)} .  (13)

Proof. Writing series (7) as

D^{(m)}(x; t) = \frac{m!}{(1 − t)^{m+1}} · e^{(x−1)t} ,

we obtain at once identity (9). Moreover, again by series (7), we have

\frac{∂}{∂t}D^{(m)}(x; t) = \frac{x + m − (x − 1)t}{1 − t} D^{(m)}(x; t) .

Hence, we have the identity

(1 − t)\frac{∂}{∂t}D^{(m)}(x; t) = (x + m − (x − 1)t) D^{(m)}(x; t)

which is equivalent to recurrence (10).

Replacing m by m + 1 in (7), we obtain the identity

(1 − t)D^{(m+1)}(x; t) = (m + 1)\frac{m! e^{(x−1)t}}{(1 − t)^{m+1}} = (m + 1)D^{(m)}(x; t)

which is equivalent to recurrence (11).

Remark 7. By Favard’s theorem [2, p. 294], a polynomial sequence {p_{n}(x)}_{n∈ℕ} form an orthogonal polynomial system if the polynomials p_{n}(x) have degree n with leading coefficient 1 and satisfy a recurrence p_{n+2}(x) = (a_{n+1} + x)p_{n+1} − b_{n+1}p_{n}(x) with p_{0}(x) = 1 and p_{1}(x) = x + a_{0}. So, by recurrence (10) and the initial conditions listed in (8), we have that the polynomials D_{n}^{(m)}(x)/m! are orthogonal, with a_{n} = m + n and b_{n} = n(x − 1).

Remark 8. Identity (12) can be proved with a combinatorial argument, which generalizes Euler’s proof of the corresponding recurrence for the ordinary derangement numbers [18, p. 60] [24]. Let π = a_{1}a_{2} ⋯ a_{m+n+2} ∈ 𝕊_{n+2}^{(m)} be a derangement. Since a_{1} ≠ 1, we have the following three cases. (i) If a_{1} = v_{i}, then a_{1} can be chosen in m different ways and the permutation of the remaining elements is equivalent to a derangement π′ of the symbols 1, …, n + 1, v_{1}, …, v_{i−1}, w_{i}, v_{i+1}, …, v_{m}. Indeed, π′ can be obtained by deleting v_{i} from π, by replacing 1 by a new symbol w_{i} and by normalizing the remaining numerical letters. In all, we have m d_{n+1}^{(m)} such permutations. (ii) If a_{1} = k with k ∈ {2, 3, …, n + 2} and a_{k} ≠ 1, then, since 1 is not in position k, we have that the permutation π′ obtained by deleting a_{1} = k from π, by replacing 1 by k and by normalizing the other numerical letters, is a derangement in 𝕊_{n+1}^{(m)}. In all, we have (n + 1) d_{n+1}^{(m)} such permutations. (iii) Finally, if a_{1} = k with k ∈ {2, 3, …, n + 2} and a_{k} = 1, then the permutation π′ obtained by deleting 1 and k from π and by normalizing the other numerical letters, is a derangement in 𝕊_{n}^{(m)}. In all, we have (n + 1) d_{n}^{(m)} such permutations. This proves identity (12).

Theorem 9. The numbers D_{n,k}^{(m)} satisfy the recurrences

(k + 1)D_{n+1,k+1}^{(m)} = (n + 1)D_{n,k}^{(m)}  (14)

D_{n+2,k+1}^{(m)} = (m + n + 1)D_{n+1,k+1}^{(m)} + D_{n+1,k}^{(m)} + (n + 1)D_{n,k+1}^{(m)} − (n + 1)D_{n,k}^{(m)}  (15)
D_{n+1,k}^{(m+1)} = (n + 1)D_{n,k}^{(m+1)} + (m + 1)D_{n+1,k}^{(m)}  (16)

and

D_{n+1,k+1}^{(m)} = D_{n,k}^{(m)} + (m + n − k − 1)D_{n,k+1}^{(m)} + (k + 2)D_{n,k+2}^{(m)} .  (17)

Proof. Recurrence (14) is an immediate consequence of definition (5). Recurrences (15) and (16) are consequences of recurrences (10) and (11), respectively. Recurrence (17) is equivalent to the identity

RD_{n+1}(x) = D_{n}(x) + (m + n)RD_{n}(x) − D′_{n}(x) + RD′_{n}(x) ,

where we write simply D_{n}(x) for D_{n}^{(m)}(x) and where R is the incremental ratio, i.e., the linear operator defined, on every polynomial p(x), by Rp(x) = \frac{p(x)−p(0)}{x}. So, if p(x) = ∑_{k=0}^{n} p_{k}x^{k}, then Rp(x) = ∑_{k=0}^{n−1} p_{k+1}x^{k}. The previous identity is equivalent to

\frac{D_{n+1}(x) − D_{n+1}(0)}{x} = D_{n}(x) + (m + n)\frac{D_{n}(x) − D_{n}(0)}{x} − D′_{n}(x) + \frac{D′_{n}(x) − D′_{n}(0)}{x}

that is

D_{n+1}(x) − D_{n+1,0} = xD_{n}(x) + (m + n)(D_{n}(x) − D_{n,0}) − xD′_{n}(x) + D′_{n}(x) − D_{n,1}

that is

D_{n+1}(x) − d_{n+1} = xD_{n}(x) + (m + n)(D_{n}(x) − d_{n}) − nxD_{n−1}(x) + nD_{n−1}(x) − nd_{n−1}

that is

D_{n+1}(x) − d_{n+1} = (x + m + n)D_{n}(x) − n(x − 1)D_{n−1}(x) − (m + n)d_{n} − nd_{n−1}

and this identity is true by (10) and (12).

Theorem 10. We have the identity

D_{n+1}^{(m)}(x) = D_{n}^{(m+1)}(x) + (x − 1)D_{n}^{(m)}(x) .  (18)

In particular, for x = 0, we have the identity

d_{n+1}^{(m)} = d_{n}^{(m+1)} − d_{n}^{(m)} .  (19)

More in general, we have the identities

D_{n+r}^{(m)}(x) = ∑_{k=0}^{r} \binom{r}{k}(x − 1)^{r−k}D_{n}^{(m+k)}(x)  (20)

and

D_{n}^{(m+r)}(x) = ∑_{k=0}^{r} \binom{r}{k}(−1)^{r−k}(x − 1)^{r−k}D_{n+k}^{(m)}(x) .  (21)

In particular, for x = 0, we have the identities

d_{n+r}^{(m)} = ∑_{k=0}^{r} \binom{r}{k}(−1)^{r−k}d_{n}^{(m+k)}  (22)

and

d_{n}^{(m+r)} = ∑_{k=0}^{r} \binom{r}{k}d_{n+k}^{(m)} .  (23)

Finally, we also have the identity

d_{n}^{(m)} = ∑_{k=0}^{m} \binom{m}{k}d_{n+k} .  (24)

Proof. Identity (18) is an immediate consequence of the identity

\frac{∂}{∂t}D^{(m)}(x; t) = \frac{x + m − (x − 1)t}{1 − t} D^{(m)}(x; t) = D^{(m+1)}(x; t) + (x − 1)D^{(m)}(x; t) .

From the above identity, we can prove, by induction, that

\frac{∂^{r}}{∂t^{r}} D^{(m)}(x; t) = ∑_{k=0}^{r} \binom{r}{k}(x − 1)^{r−k}D^{(m+k)}(x; t) .

This identity is equivalent to identity (20). Then, by applying the binomial inversion formula [20, p. 147] to identity (20), we obtain identity (21). Finally, identity (24) can be obtained from identity (23) by setting m = 0 and r = m.

Remark 11. Identity (19) can be proved with the following combinatorial argument. Let f be an m-widened derangement on a set X of size n, and let (λ_{1}, …, λ_{m}, σ) be its decomposition. We have two cases. (i) The last linear order λ_{m} does not contain elements of X, i.e., λ_{m} = [u_{m}, v_{j}] for a suitable j ∈ [m]. By deleting λ_{m}, and by replacing v_{m} by v_{j} whenever j ≠ m, we obtain an (m − 1)-widened derangement on X. (ii) The last linear order λ_{m} contains at least one element of X, i.e., λ_{m} = [u_{m}, i_{1}, …, i_{h}, v_{j}] for a suitable j ∈ [m]. In this case, f is equivalent to an (m − 1)-widened derangement on X ∪ {n + 1} obtained by replacing the linear order λ_{m} with the cycle γ = (i_{1} ⋯ i_{h} n + 1), and by replacing v_{m} with v_{j} whenever j ≠ m. Since γ has at least two elements, the new (m − 1)-widened permutation is without fixed points. So, in conclusion, we have the identity d_{n}^{(m)} = d_{n}^{(m−1)} + d_{n+1}^{(m−1)}.

Theorem 12. We have the identity

\frac{D_{n}^{(m+1)}(x)}{n!} = (m + 1) ∑_{k=0}^{n} \frac{D_{k}^{(m)}(x)}{k!} .  (25)

In particular, for x = 0, we have the identity

\frac{d_{n}^{(m+1)}}{n!} = (m + 1) ∑_{k=0}^{n} \frac{d_{k}^{(m)}}{k!} .  (26)

Proof. By series (7), we have

D^{(m+1)}(x; t) = \frac{m + 1}{1 − t} D^{(m)}(x; t)

and consequently we have the identity

D_{n}^{(m+1)}(x) = (m + 1) ∑_{k=0}^{n} \binom{n}{k}(n − k)!D_{k}^{(m)}(x)

which simplifies in identity (25).

Theorem 13. Let U_{m,n} be the m × n matrix all of whose entries are equal to 1, U_{n} = U_{n,n}, U_{n}(x) = U_{n} + (x − 1)I_{n} (where I_{n} is the identity matrix of order n), and let

A_{n}^{(m)}(x) = [\begin{matrix}U_{n}(x) & U_{n,m} \\ U_{m,n} & U_{m} \end{matrix}] .

Then, we have

D_{n}^{(m)}(x) = per A_{n}^{(m)}(x) .  (27)

Proof. Let A_{n}^{(m)}(x) = [a_{i,j}], where a_{i,i} = x for i = 1, 2, …, n, and a_{i,j} = 1 in all other cases. Let Fix(π) be the set of fixed points of a permutation π ∈ 𝕊_{n}^{(m)}. By the definition of the permanent of a matrix, we have

per A_{n}^{(m)}(x) = ∑_{σ∈𝕊_{m+n}} a_{1,σ(1)} ⋯ a_{m+n,σ(m+n)} = ∑_{S⊆[n]} ∑_{{π∈𝕊{(m) \atop n} \atop Fix(π)=S}} x^{|S|} = ∑_{k=0}^{n} \binom{n}{k}d_{n−k}^{(m)}x^{k} .

By definition (6), we have identity (27).

Remark 14. Expanding the permanent of A_{n}^{(m)}(x) along the last column, we obtain recurrence (11).

Theorem 15. The polynomials D_{n}^{(m)}(x) can be expressed as the double sum

D_{n}^{(m)}(x) = ∑_{i=0}^{n} ∑_{j=0}^{m} \binom{n}{i}\binom{m}{j}(−1)^{m+n−i−j}(x + i + j − 1)^{i}(i + j)^{m+n−i} .  (28)

Proof. By identity (27) and by using Ryser’s formula [22, p. 26] [12] to evaluate the permanent of A = A_{n}^{(m)}(x) = [a_{i,j}], we have

D_{n}^{(m)}(x) = ∑_{S⊆[m+n]}(−1)^{m+n−|S|}w(A_{S}) = ∑_{{I⊆[n] \atop J⊆[m]}}(−1)^{m+n−|I|−|J|}w(A_{I∪J})

where A_{S} = [a_{i,j}]_{i∈[m+n], j∈S} and w(A_{S}) = ∏_{k=1}^{m+n} r_{k}(A_{S}), where r_{k}(A_{S}) is the sum of all elements of the kth row of A_{S}. Since

w(A_{I∪J}) = (x + |I| + |J| − 1)^{i}(|I| + |J|)^{m+n−i}

we obtain at once identity (28).

Identity (28) generalizes the formula obtained by Ryser [22, p. 28] [1] for the ordinary derangement numbers (for m = 0 and x = 0).

Theorem 16. The polynomials D_{n}^{(m)}(x) admit the integral representation

D_{n}^{(m)}(x) = ∫_{0}^{+∞} t^{m}(t + x − 1)^{n} e^{−t} dt .  (29)

In particular, for x = 0, we have

d_{n}^{(m)} = ∫_{0}^{+∞} t^{m}(t − 1)^{n} e^{−t} dt .  (30)

Proof. By identity (9) and the well-known identity

∫_{0}^{+∞} t^{k}e^{−t} dt = k! k ∈ ℕ ,

we have

\begin{matrix}D_{n}^{(m)}(x) = ∑_{k=0}^{n} \binom{n}{k}(m + k)!(x − 1)^{n−k} = ∑_{k=0}^{n} \binom{n}{k}(x − 1)^{n−k} ∫_{0}^{+∞} t^{m+k}e^{−t} dt \\ = ∫_{0}^{+∞} t^{m} [∑_{k=0}^{n} \binom{n}{k}t^{k}(x − 1)^{n−k}] e^{−t} dt = ∫_{0}^{+∞} t^{m}(t + x − 1)^{n}e^{−t} dt . \end{matrix}

Theorem 17. We have the identities

D_{n}^{(m)}(x) = ∑_{k=0}^{m} \binom{m}{k}(1 − x)^{k}D_{m+n−k}(x)  (31)

D_{n}(x) = ∑_{k=0}^{n} \binom{n}{k}\frac{(−1)^{k}}{(m − k)!}D_{n−k}^{(m)}(x) .  (32)

Proof. By identity (29), we have

D_{n}^{(m)}(x) = ∫_{0}^{+∞} t^{m}(t + x − 1)^{n} e^{−t} dt

= ∫_{0}^{+∞}(1 − x + t + x − 1)^{m}(t + x − 1)^{n} e^{−t} dt

= ∫_{0}^{+∞} ∑_{k=0}^{m} \binom{m}{k}(1 − x)^{k}(t + x − 1)^{m−k}(t + x − 1)^{n} e^{−t} dt

= ∑_{k=0}^{m} \binom{m}{k}(1 − x)^{k} ∫_{0}^{+∞}(t + x − 1)^{m+n−k} e^{−t} dt

= ∑_{k=0}^{m} \binom{m}{k}(1 − x)^{k}D_{m+n−k}^{(0)}(x) .

This is identity (31). Then, by identity (7), we obtain the identity

(1 − t)^{m}D^{(m)}(x; t) = m! \frac{e^{(x−1)t}}{1 − t} = m! D(x; t)

which is equivalent to identity (32). Theorem 18. The polynomials D_{n}^{(m)}(x)/m! admit the determinantal representation

\frac{D_{n}^{(m)}(x)}{m!} = |\begin{matrix}a_{1} & 1 \\ b_{1} & a_{2} & 1 \\ & b_{2} & a_{3} & 1 \\ & & ... & ... & ... \\ & & & b_{n−2} & a_{n−1} & 1 \\ & & & & b_{n−1} & a_{n} \end{matrix}|_{n×n}  (33)

where a_{k} = x + m + k − 1 and b_{k} = k(x − 1) for k ≥ 1. Proof. The tridiagonal determinants (also called continuants [14, pp. 516–525] [25]) defined on the right-hand side of formula (33) satisfy the recurrence y_{n+2} − a_{n+2}y_{n+1} + b_{n+1}y_{n} = 0 with the initial values y_{0} = 1 and y_{1} = a_{1}. So, the claim follows from recurrence (10) and the initial values D_{0}^{(m)}(x) = m! and D_{1}^{(m)}(x) = m!(x + m). Theorem 19. The polynomials D_{n}^{(m)}(x)/m! admit the determinantal representation

\frac{D_{n}^{(m)}(x)}{m!} = |\begin{matrix}a_{0} & −1 \\ a_{1} & a_{0} & −1 \\ a_{2} & 2a_{1} & a_{0} & −1 \\ a_{3} & 3a_{2} & 3a_{1} & a_{0} & −1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ... \\ \binom{n−2}{0}a_{n−2} & \binom{n−2}{1}a_{n−3} & \binom{n−2}{2}a_{n−4} & \binom{n−2}{3}a_{n−5} & ⋯ & \binom{n−2}{n−2}a_{0} & −1 \\ \binom{n−1}{0}a_{n−1} & \binom{n−1}{1}a_{n−2} & \binom{n−1}{2}a_{n−3} & \binom{n−1}{3}a_{n−4} & ⋯ & \binom{n−1}{n−2}a_{1} & \binom{n−1}{n−1}a_{0} \end{matrix}| (34)

where a_{0} = x + m and a_{k} = (m + 1)k! for k ≥ 1. In particular, for x = 0, we have a similar representation for the generalized derangement numbers d_{n}^{(m)}, with a_{0} = m and a_{k} = (m+1)k! for k ≥ 1. For x = 1, we have a similar representation for the factorial numbers (m + n)!, with a_{0} = m + 1 and a_{k} = (m + 1)k! for k ≥ 1.

Proof. Let b_{n} be the n × n determinant appearing on the right-hand side of (34). Then, expanding the determinant along the last column, we have the recurrence

b_{n+1} = ∑_{k=0}^{n} \binom{n}{k}a_{k}b_{n−k}

with the initial value b_{0} = 1. If a(t) = ∑_{n≥0} a_{n} \frac{t^{n}}{n!} and b(t) = ∑_{n≥0} b_{n} \frac{t^{n}}{n!}, then we have the differential equation b′(t) = a(t)b(t). So, if we set

b(t) = \frac{1}{m!} D^{(m)}(x; t) = \frac{e^{(x−1)t}}{(1 − t)^{m+1}} ,

then we have b_{0} = 1, as requested, and

a(t) = \frac{b′(t)}{b(t)} = \frac{(x − 1)(1 − t) + m + 1}{1 − t} = x − 1 + \frac{m + 1}{1 − t} .

Hence a_{0} = x + m and a_{k} = (m + 1)k! for k ≥ 1. This proves identity (34).

4 Combinatorial identities

For the polynomials D_{n}^{(m)}(x) there are many combinatorial identities. In this section, we derive some of them.

Theorem 20. We have the identities

∑_{k=0}^{n} \binom{n}{k}α^{n−k}D_{k}^{(m)}(x) = D_{n}^{(m)}(x + α)  (35)

and

∑_{k=0}^{n} \binom{n}{k}D_{k}^{(r)}(x)D_{n−k}^{(s)}(y) = \frac{1}{\binom{r+s}{r}} \frac{1}{r + s + 1} D_{n}^{(r+s+1)}(x + y − 1) .  (36)

In particular, for x = 0 and y = 0, we have the identity

∑_{k=0}^{n} \binom{n}{k}d_{k}^{(r)}d_{n−k}^{(s)} = \frac{1}{\binom{r+s}{r}} \frac{1}{r + s + 1} ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}d_{k}^{(r+s+1)} .  (37)

Proof. Identity (35) is equivalent to the identity

e^{αt}D^{(m)}(x; t) = \frac{m! e^{(x+α−1)t}}{(1 − t)^{m+1}} = D^{(m)}(x + α; t) .

Similarly, identity (36) is equivalent to the identity

D^{(r)}(x; t)D^{(s)}(y; t) = \frac{r!s! e^{(x+y−2)t}}{(1 − t)^{r+s+2}} = \frac{r!s!}{(r + s + 1)!} D^{(r+s+1)}(x + y − 1; t) .

Finally, identity (37) derives from the fact that

D^{(r+s+1)}(−1; t) = d^{(r+s+1)}(t) · e^{−t} .

A Sheffer matrix [20, 21] [2, p. 309] is an infinite lower triangular matrix S = [s_{n,k}]_{n,k≥0} = (g(t), f(t)) whose columns have exponential generating series

s_{k}(t) = ∑_{n≥k} s_{n,k} \frac{t^{n}}{n!} = g(t)\frac{f(t)^{k}}{k!} ,

where g(t) and f(t) are exponential formal series with g_{0} = 1, f_{0} = 0, f_{1} ≠ 0, and

s_{n,k} = \frac{n!}{k!} [t^{n}] g(t)f(t)^{k} .

The Sheffer transform associated with the Sheffer matrix S = [s_{n,k}]_{n,k≥0} = (g(t), f(t)) is defined, for every exponential series h(t) = ∑_{n≥0} h_{n} \frac{t^{n}}{n!}, by

(g(t), f(t))h(t) = g(t)h(f(t)) = ∑_{n≥0} [∑_{k=0}^{n} s_{n,k}h_{k}] \frac{t^{n}}{n!} .

The r-Stirling numbers of the first kind [6] are defined as the entries of the Sheffer matrix (\frac{1}{(1−t)^{r}} , log \frac{1}{1−t}), so that

\frac{1}{(1 − t)^{r}} \frac{1}{k!} (log \frac{1}{1 − t})^{k} = ∑_{n≥k} \left[{n \atop k}\right]_{r} \frac{t^{n}}{n!} .

In particular, for r = 0 and r = 1, we have the Stirling numbers of the first kind [8, p. 310] [18, p. 48] (\underline{A132393}, \underline{A008275}): \left[{n \atop k}\right]_{0} = \left[{n \atop k}\right] and \left[{n \atop k}\right]_{1} = \left[{n+1 \atop k+1}\right]. For r = 1, 2, …, 10, we have sequences \underline{A130534}, \underline{A143491}, \underline{A143492}, \underline{A143493}, \underline{A049460}, \underline{A051338}, \underline{A051339}, \underline{A051379}, \underline{A051380}, \underline{A051523} in [23].

The r-Stirling numbers of the second kind [6] are defined as the entries of the Sheffer matrix S^{(r)} = (e^{rt}, e^{t} − 1), so that

e^{rt} \frac{(e^{t} − 1)^{k}}{k!} = ∑_{n≥k} \left\{{n \atop k}\right\}_{r} \frac{t^{n}}{n!} .

In particular, for r = 0 and r = 1, we have the Stirling numbers of the second kind [8, p. 310] [18, p. 48] (\underline{A008277}): \left\{{n \atop k}\right\}_{0} = \left\{{n \atop k}\right\} and \left\{{n \atop k}\right\}_{1} = \left\{{n+1 \atop k+1}\right\}. For r = 2, 3, 4, 5 we have sequences \underline{A143494}, \underline{A143495}, \underline{A143496}, \underline{A193685} in [23]. The row polynomials of S^{(r)} are the r-exponential polynomials

S_{n}^{(r)}(x) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{r}x^{k}

with exponential generating series

S^{(r)}(x; t) = ∑_{n≥0} S_{n}^{(r)}(x) \frac{t^{n}}{n!} = e^{rt}e^{x(e^{t}−1)} .

For r = 0, we have the ordinary exponential polynomials S_{n}(x), whose exponential generating series are denoted by S(x; t). Moreover, the row sums of S^{(r)} are the r-Bell numbers b_{n}^{(r)} = S_{n}^{(r)}(1) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{r}, [11], with exponential generating series

b^{(r)}(t) = ∑_{n≥0} b_{n}^{(r)} \frac{t^{n}}{n!} = e^{rt}e^{e^{t}−1} .

For r = 0, we have the ordinary Bell numbers b_{n} [8, p. 210] (\underline{A000110}).

The Lah numbers [8, p. 156] [18, p. 44] (\underline{A008297}) are defined as the entries of the Sheffer matrix L = (1, \frac{t}{1−t}), so that

\frac{1}{k!} (\frac{t}{1 − t})^{k} = ∑_{n≥k} |{n \atop k}| \frac{t^{n}}{n!} .

The row polynomials of L are the Lah polynomials

L_{n}(x) = ∑_{k=0}^{n} |{n \atop k}|x^{k} ,

with exponential generating series

L(x; t) = ∑_{n≥0} L_{n}(x) \frac{t^{n}}{n!} = e^{\frac{xt}{1−t}} .

The row sums of L are the cumulative Lah numbers ℓ_{n} = ∑_{k=0}^{n} |_{k}^{n}|, [19, p. 194] (\underline{A000262}), with exponential generating series

ℓ(t) = ∑_{n≥0} ℓ_{n} \frac{t^{n}}{n!} = e^{\frac{t}{1−t}} .

Theorem 21. We have the identity

∑_{k=0}^{n} \left\{{n \atop k}\right\}_{r}(−1)^{k}D_{k}^{(m)}(x) = m! ∑_{k=0}^{n} \binom{n}{k}(r − m − 1)^{n−k}S_{k}(1 − x) .  (38)

In particular, for r = 0 and x = 0, we have the identity

∑_{k=0}^{n} \left\{{n \atop k}\right\}(−1)^{k}d_{k}^{(m)} = m! ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}(m + 1)^{n−k}b_{k}  (39)

and, for r = 1 and x = 0, we have the identity

∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}(−1)^{k}d_{k}^{(m)} = m! ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}m^{n−k}b_{k} .  (40)

Proof. We have

(e^{rt}, −e^{t} + 1) D^{(m)}(x; t) = e^{rt} \frac{m! e^{(x−1)(−e^{t}+1)}}{e^{(m+1)t}} = m! e^{(r−m−1)t}S(1 − x; t)

from which we obtain identity (38). Theorem 22. The polynomials D_{n}^{(m)}(x) can be expressed as

D_{n}^{(m)}(x) = \frac{m!}{\binom{m+n}{m}} ∑_{k=0}^{n} \binom{m + n}{m + k}|{m + k \atop m}|D_{n−k}(x) .  (41)

In particular, for x = 0, we have

d_{n}^{(m)} = \frac{m!}{\binom{m+n}{m}} ∑_{k=0}^{n} \binom{m + n}{m + k}|{m + k \atop m}|d_{n−k} ,

and for x = 1, we have

(m + n)! = \frac{m!}{\binom{m+n}{m}} ∑_{k=0}^{n} \binom{m + n}{m + k}|{m + k \atop m}|(n − k)! .

Proof. By series (7), we have

D^{(m)}(x; t) = \frac{m!^{2}}{t^{m}} \frac{1}{m!} (\frac{t}{1 − t})^{m} · \frac{e^{(x−1)t}}{1 − t}

= \frac{m!^{2}}{t^{m}} ∑_{n≥m} |{n \atop m}|\frac{t^{n}}{n} · ∑_{n≥0} D_{n}(x) \frac{t^{n}}{n!}

= \frac{m!^{2}}{t^{m}} ∑_{n≥m} [∑_{k=m}^{n} \binom{n}{k}|{k \atop m}|D_{n−k}(x)] \frac{t^{n}}{n!}

= m!^{2} ∑_{n≥m} [∑_{k=m}^{n} \binom{n}{k}|{k \atop m}|D_{n−k}(x)] \frac{t^{n−m}}{n!}

= m!^{2} ∑_{n≥0} [∑_{k=m}^{m+n} \binom{m + n}{k}|{k \atop m}|D_{m+n−k}(x)] \frac{t^{n}}{(m + n)!}

= ∑_{n≥0} \frac{m!^{2}n!}{(m + n)!} [∑_{k=0}^{n} \binom{m + n}{m + k}|{m + k \atop m}|D_{n−k}(x)] \frac{t^{n}}{n!}

from which we obtain identity (41). Theorem 23. We have the identity

∑_{k=0}^{n} \binom{m + n}{m + k}\frac{n!}{k!}(−1)^{k}D_{k}^{(m)}(x) = m!L_{n}(1 − x) .  (42)

In particular, for x = 0, we have

∑_{k=0}^{n} \binom{m + n}{m + k}\frac{n!}{k!}(−1)^{k}d_{k}^{(m)} = m!ℓ_{n} .  (43)

Proof. Consider the Sheffer matrix

[L_{n,k}^{(m)}]_{n,k≥0} = (\frac{1}{(1 + t)^{m+1}} , \frac{t}{1 + t})

whose entries are

L_{n,k}^{(m)} = \frac{n!}{k!}[t^{n}]\frac{1}{(1 + t)^{m+1}} (\frac{t}{1 + t})^{k} = \frac{n!}{k!}[t^{n}]\frac{t^{k}}{(1 + t)^{m+k+1}} = \binom{m + n}{m + k}\frac{n!}{k!}(−1)^{n−k} .

Since

(\frac{1}{(1 + t)^{m+1}} , \frac{t}{1 + t}) D^{(m)}(x; t) = \frac{1}{(1 + t)^{m+1}} D^{(m)}(x; \frac{t}{1 + t}) = m! e^{\frac{(x−1)t}{1+t}} = m! L(1 − x; −t) ,

we obtain at once identity (42).

5 Connection identities

Let {p_{n}(x)}_{n∈ℕ} and {q_{n}(x)}_{n∈ℕ} be two polynomial sequences. If deg p_{n}(x) = n for all n ∈ ℕ, then the sequence {p_{n}(x)}_{n∈ℕ} forms a basis for the vector space ℝ[x] of polynomials and consequently there exist some coefficients C_{n,k} for which

q_{n}(x) = ∑_{k=0}^{n} C_{n,k} p_{k}(x) .

The coefficients C_{n,k} are unique and are called connection constants [20, p. 131] [21, 9, 10]. In this section, we consider some connection identities for the polynomials D_{n}^{(m)}(x). Identities (6), (9), (35), (41) are examples of this kind. We use an umbral approach due to G.-C. Rota. Suppose to have a connection identity

q_{n}(x) = ∑_{k=0}^{n} C_{n,k} D_{k}^{(m)}(x) .

To obtain the connection constants, we define the linear map φ_{m} : ℝ[x] → ℝ[x] by setting φ_{m}(D_{n}^{(m)}(x)) = x^{n}, for every n ∈ ℕ, and then by extending it by linearity. Then, the preceding identity becomes

φ_{m}(q_{n}(x)) = ∑_{k=0}^{n} C_{n,k} x^{k} .

Now, we extend φ_{m} to exponential formal series, as follows. First, we have

φ_{m}(D^{(m)}(x; t)) = φ_{m} (∑_{n≥0} D_{n}^{(m)}(x) \frac{t^{n}}{n!}) = ∑_{n≥0} φ_{m}(D_{n}^{(m)}(x)) \frac{t^{n}}{n!} = ∑_{n≥0} x^{n} \frac{t^{n}}{n!} = e^{xt} ,

that is

φ_{m} (\frac{m! e^{(x−1)t}}{(1 − t)^{m+1}} ) = e^{xt}

from which we have

φ_{m}(e^{(x−1)t}) = \frac{1}{m!} (1 − t)^{m+1} e^{xt} .  (44)

Now, let q(x; t) = ∑_{n≥0} q_{n}(x) \frac{t^{n}}{n!} be the exponential generating series for the polynomials q_{n}(x). Then, the connection constants C_{n,k} are determined by the series

∑_{n≥0} [∑_{k=0}^{n} C_{n,k} x^{k}] \frac{t^{n}}{n!} = ∑_{n≥0} φ_{m}(q_{n}(x))\frac{t^{n}}{n!} = φ_{m}(q(x; t)) .

In the next few theorems, we use this method.

Theorem 24. We have the connection identity

(x − 1)^{n} = \frac{1}{m!} ∑_{k=0}^{n} \binom{n}{k}\binom{m + 1}{n − k}(−1)^{n−k}(n − k)! D_{k}^{(m)}(x) .  (45)

Proof. In this case, we have q_{n}(x) = (x − 1)^{n} and q(x; t) = e^{(x−1)t}. So, by applying (44), we have the series

φ_{m}(e^{(x−1)t}) = \frac{1}{m!} (1 − t)^{m+1} e^{xt} = \frac{1}{m!} ∑_{n≥0} [∑_{k=0}^{n} \binom{n}{k}\binom{m + 1}{n − k}(−1)^{n−k}(n − k)!x^{k}] \frac{t^{n}}{n!}

from which we obtain the coefficients

C_{n,k}^{(m)} = \frac{1}{m!}\binom{n}{k}\binom{m + 1}{n − k}(−1)^{n−k}(n − k)! .

This proves identity (45).

Theorem 25. We have the connection identity

D_{n}^{(r)}(x) = ∑_{k=0}^{n} \binom{n}{k}\binom{s − r}{n − k}\frac{r!}{s!} (−1)^{n−k}(n − k)! D_{k}^{(s)}(x) .  (46)

Proof. In this case, we have q_{n}(x) = D_{n}^{(r)}(x) and q(x; t) = D^{(r)}(x; t). So, by applying (44), we have the series

φ_{s}(D^{(r)}(x; t)) = \frac{r!}{(1 − t)^{r+1}} φ_{s}(e^{(x−1)t}) = \frac{r!}{s!} (1 − t)^{s−r} e^{xt}

= \frac{r!}{s!} ∑_{n≥0} [∑_{k=0}^{n} \binom{n}{k}\binom{s − r}{n − k}(−1)^{n−k}(n − k)!x^{k}] \frac{t^{n}}{n!}

from which we have

C_{n,k}^{(r,s)} = \binom{n}{k}\binom{s − r}{n − k}\frac{r!}{s!} (−1)^{n−k}(n − k)! .

This proves identity (46).

Theorem 26. We have the connection identities

S_{n}^{(r)}(1 − x) = \frac{1}{m!} ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{r+m+1}(−1)^{k} D_{k}^{(m)}(x)  (47)

and

D_{n}^{(m)}(x) = m! ∑_{k=0}^{n} \left[{n \atop k}\right]_{r+m+1}(−1)^{k} S_{k}^{(r)}(1 − x) .  (48)

In particular, for x = 1, we have the identities

∑_{k=0}^{n} \left\{{n \atop k}\right\}_{r+m+1}(−1)^{k} (m + k)! = m! r^{n}  (49)

∑_{k=0}^{n} \left[{n \atop k}\right]_{r+m+1}(−1)^{k} r^{k} = \frac{(m + n)!}{m!} .  (50)

Proof. In this case, we have q_{n}(x) = S_{n}^{(r)}(1 − x) and q(x; t) = e^{rt}e^{(1−x)(e^{t}−1)}. So, by applying (44), we have the series

φ_{m}(e^{rt}e^{(1−x)(e^{t}−1)}) = e^{rt}φ_{m}(e^{(x−1)(−e^{t}+1)}) = \frac{1}{m!} e^{(r+m+1)t} e^{−x(e^{t}−1)}

= \frac{1}{m!} S^{(r+m+1)}(−x; t) = \frac{1}{m!} ∑_{n≥0} [∑_{k=0}^{n} \left\{{n \atop k}\right\}_{r+m+1}(−1)^{k}x^{k}] \frac{t^{n}}{n!}

from which we have

C_{n,k}^{(m)} = \frac{(−1)^{k}}{m!} \left\{{n \atop k}\right\}_{r+m+1} .

This proves identity (47). Then, using the inversion formula for the r-Stirling numbers, we obtain identity (48).

6 Expectation and variance

Let X_{n}^{(m)} be the random variable counting the number of fixed points of a permutation in 𝕊_{n}^{(m)}. Then D_{n,k}^{(m)} is the number of permutations π ∈ 𝕊_{n}^{(m)} such that X_{n}^{(m)}(π) = k. So, the expectation of X_{n}^{(m)}, i.e., the expected number of fixed points in a random permutation π ∈ 𝕊_{n}^{(m)}, can be expressed [5, p. 284] as

E_{n}^{(m)} = 𝔼[X_{n}^{(m)}] = \frac{1}{|𝕊_{n}^{(m)}|} ∑_{k=0}^{n} kD_{n,k}^{(m)} = \frac{1}{(m + n)!} ∑_{k=0}^{n} kD_{n,k}^{(m)} .

Similarly, since

𝔼[(X_{n}^{(m)})^{2}] = \frac{1}{|𝕊_{n}^{(m)}|} ∑_{k=0}^{n} k^{2}D_{n,k}^{(m)} = \frac{1}{(m + n)!} ∑_{k=0}^{n} k^{2}D_{n,k}^{(m)} ,

the variance of X_{n}^{(m)}, defined by 𝕍ar[X_{n}^{(m)}] = 𝔼[(X_{n}^{(m)})^{2}] − 𝔼[X_{n}^{(m)}]^{2}, can be expressed as

V_{n}^{(m)} = 𝕍ar[X_{n}^{(m)}] = \frac{1}{(m + n)!} ∑_{k=0}^{n} k^{2}D_{n,k}^{(m)} − (\frac{1}{(m + n)!} ∑_{k=0}^{n} kD_{n,k}^{(m)})^{2} .

To compute the expectation and the variance of X_{n}^{(m)}, we need next Theorem 27. We have the identity

∑_{k=0}^{n} k^{r}D_{n,k}^{(m)} = n! ∑_{k=0}^{min(n,r)} \left\{{r \atop k}\right\}\frac{(m + n − k)!}{(n − k)!} .  (51)

In particular, for r = 1, 2, we have the identities

∑_{k=0}^{n} kD_{n,k}^{(m)} = n(m + n − 1)!  (n ≥ 1)  (52)

∑_{k=0}^{n} k^{2}D_{n,k}^{(m)} = n(m + 2n − 2)(m + n − 2)!  (n ≥ 2) .  (53)

Proof. Let Θ_{x} = xD_{x}. Then, we have the generating series

∑_{n≥0} [∑_{k=0}^{n} k^{r}D_{n,k}^{(m)}] \frac{t^{n}}{n!} = ∑_{n≥0} [∑_{k=0}^{n} k^{r}D_{n,k}^{(m)}x^{k}]_{x=1} \frac{t^{n}}{n!} = [∑_{n≥0} Θ_{x}^{r}D_{n}^{(m)}(x)\frac{t^{n}}{n!}]_{x=1}

= [Θ_{x}^{r}D_{n}^{(m)}(x; t)]_{x=1} = \frac{m! e^{−t}}{(1 − t)^{m+1}} [Θ_{x}^{r}e^{xt}]_{x=1} = \frac{m! e^{−t}}{(1 − t)^{m+1}} [S_{r}(xt) e^{xt}]_{x=1}

= \frac{m!}{(1 − t)^{m+1}} S_{r}(t) = ∑_{k=0}^{r} \left\{{r \atop k}\right\}\frac{m!t^{k}}{(1 − t)^{m+1}} = ∑_{n≥0} [ ∑_{k=0}^{min(n,r)} \left\{{r \atop k}\right\}\binom{m + n − k}{m}m!] t^{n}

from which we have identity (51). For r = 1 and n ≥ 1, we have

n! ∑_{k=0}^{1} \left\{{1 \atop k}\right\}\frac{(m + n − k)!}{(n − k)!} = n! \frac{(m + n − 1)!}{(n − 1)!} = n(m + n − 1)! .

For r = 2 and n ≥ 2, we have

n! ∑_{k=0}^{2} \left\{{2 \atop k}\right\}\frac{(m + n − k)!}{(n − k)!} = n! (\frac{(m + n − 1)!}{(n − 1)!} + \frac{(m + n − 2)!}{(n − 2)!})
= n(m + 2n − 2)(m + n − 2)! .

In the ordinary case (m = 0), we have the well known remarkable fact that the expectation and variance of the number of fixed points in a random permutation in 𝕊_{n} are always equal to 1. In the general case (m ≥ 1), the expectation and variance of the number of fixed points in a random permutation in 𝕊_{n}^{(m)} are no more always equal to 1, even though this is true asymptotically. More precisely, we have Theorem 28. For n ≥ 2, we have

E_{n}^{(m)} = \frac{n}{m + n} and V_{n}^{(m)} = \frac{n(m^{2} + 2mn + n^{2} − 2m − n)}{(m + n)^{2}(m + n − 1)} . (54)

Moreover, we have

lim_{n→+∞} E_{n}^{(m)} = 1 and lim_{n→+∞} V_{n}^{(m)} = 1 . (55)

Proof. By identity (52), we have that the expectation is given by

E_{n}^{(m)} = \frac{1}{(m + n)!} ∑_{k=0}^{n} kD_{n,k}^{(m)} = \frac{n(m + n − 1)!}{(m + n)!} = \frac{n}{m + n} .

Similarly, by identities (52) and (53), we have that the variance is given by

V_{n}^{(m)} = \frac{1}{(m + n)!} ∑_{k=0}^{n} k^{2}D_{n,k}^{(m)} − (\frac{1}{(m + n)!} ∑_{k=0}^{n} kD_{n,k}^{(m)})^{2}

= \frac{n(m + 2n − 2)(m + n − 2)!}{(m + n)!} − (\frac{n}{(m + n)})^{2}

= \frac{n(m + 2n − 2)}{(m + n)(m + n − 1)} − \frac{n^{2}}{(m + n)^{2}}

= \frac{n(m^{2} + 2mn + n^{2} − 2m − n)}{(m + n)^{2}(m + n − 1)} .

Finally, it is easy to see that E_{n}^{(m)} ∼ 1 and V_{n}^{(m)} ∼ 1 for n → +∞.

7 Asymptotics

We conclude by obtaining some asymptotic results for the generalized rencontres numbers D_{n,k}^{(m)} and the generalized derangement numbers d_{n}^{(m)}. Theorem 29. We have the asymptotic equivalence

\frac{d_{n}^{(m)}}{n!} ∼ n^{m}e^{−1} for n → +∞ . (56)

Proof. Wang et al. [26] proved that

D_{r}(n) ∼ \frac{(n + r)!}{r!} e^{−1} for n → +∞ .

Then, by relation (4), for n → +∞, we have

\frac{d_{n}^{(m)}}{n!} = \frac{1}{n!} \frac{1}{\binom{n+m}{m}} D_{m}(n + m) ∼ \frac{1}{n!} \frac{1}{\binom{n+m}{m}} \frac{(n + 2m)!}{m!} e^{−1} = \frac{(n + 2m)!}{(n + m)!} e^{−1} .

By applying the Stirling formula n! ∼ n^{n}e^{−n}\sqrt{2nπ}, for n → +∞, we have

\frac{d_{n}^{(m)}}{n!} ∼ \frac{(n + 2m)^{n+2m}e^{−n−2m}\sqrt{2(n + 2m)π}}{(n + m)^{n+m}e^{−n−m}\sqrt{2(n + m)π}} e^{−1}

= (1 + \frac{m}{n + m})^{n} \frac{(n + 2m)^{2m}}{(n + m)^{m}} \sqrt{\frac{n + 2m}{n + m}} e^{−m−1} ∼ e^{m} \frac{n^{2m}}{n^{m}} e^{−m−1} = n^{m} e^{−1} .

Remark 30. From the asymptotic relation (56), we have that the series d^{(m)}(t) converges for |t| < 1. So, for instance, for t = 1/2 and t = −1/2, by series (2), we have

∑_{n≥0} \frac{d_{n}^{(m)}}{2^{n}n!} = m! 2^{m+1} e^{−1/2} and  ∑_{n≥0}(−1)^{n} \frac{d_{n}^{(m)}}{2^{n}n!} = m! (\frac{2}{3})^{m+1} e^{1/2} .

Theorem 31. We have the asymptotic equivalences

\frac{D_{n,k}^{(m)}}{n!} ∼ \frac{(n − k)^{m}}{k!} e^{−1}  for n → +∞  (57)

and

\frac{D_{n,k}^{(m)}}{(m + n)!} ∼ \frac{e^{−1}}{k!}  for n → +∞ .  (58)

Proof. By definition (5) and equivalence (56), for n → +∞, we have

\frac{D_{n,k}^{(m)}}{n!} = \frac{1}{k!} \frac{d_{n−k}^{(m)}}{(n − k)!} ∼ \frac{1}{k!} (n − k)^{m} e^{−1} .

Then, by using this equivalence and the Stirling formula n! ∼ n^{n}e^{−n}\sqrt{2nπ}, we have

\frac{D_{n,k}^{(m)}}{(m + n)!} ∼ \frac{n!}{(n + m)!} \frac{(n − k)^{m}}{k!} e^{−1} ∼ \frac{n^{n}e^{−n}\sqrt{2nπ}}{(n + m)^{n+m}e^{−n−m}\sqrt{2(n + m)π}} \frac{(n − k)^{m}}{k!} e^{−1}

= (1 + \frac{m}{n})^{−n} \sqrt{\frac{n}{n + m}} (\frac{n − k}{n + m})^{m} \frac{e^{m−1}}{k!} ∼ e^{−m} \frac{e^{m−1}}{k!} = \frac{e^{−1}}{k!} .

This completes the proof.

References

[1] M. Abramson, A note on permanents, Canad. Math. Bull. 14 (1971), 1–4.

[2] M. Aigner, A Course in Enumeration, Springer, 2007.

[3] P. Appell, Sur une classe de polynômes, Ann. Sci. École Norm. Sup. (2) 9 (1880), 119–144.

[4] F. Beggas, M. M. Ferrari and N. Zagaglia Salvi, Combinatorial interpretations and enumeration of particular bijections, Riv. Mat. Univ. Parma 8 (2017), 161–169.

[5] E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications, Dover, 2006.

[6] A. Z. Broder, The r-Stirling numbers, Discrete Math. 49 (1984), 241–259.

[7] B. C. Carlson, Polynomials satisfying a binomial theorem, J. Math. Anal. Appl. 32 (1970), 543–558.

[8] L. Comtet, Advanced Combinatorics, Reidel, 1974.

[9] E. Damiani, O. D’Antona and G. Naldi, On the connection constants, Stud. Appl. Math. 85 (1991), 289–302.

[10] O. M. D’Antona and E. Munarini, A combinatorial interpretation of the connection constants for persistent sequences of polynomials, European J. Combin. 26 (2005), 1105– 1118.

[11] I. Mezö, The r-Bell numbers, J. Integer Seq. 14 (2011), Article 11.1.1.

[12] H. Minc, Permanents, Addison-Wesley, 1978.

[13] P. R. Montmort, Essay d’Analyse sur les Jeux de Hazard, 1708, (Second edition, 1713).

[14] T. Muir, The Theory of Determinants in the Historical Order of Developement, Dover, 1960.

[15] E. Munarini, Combinatorial identities for Appell polynomials, Appl. Anal. Discrete Math., to be published.

[16] E. Navarrete, Forbidden patterns and the alternating derangement sequence, preprint,

    2016, https://arxiv.org/abs/1610.01987.

[17] E. Navarrete, Generalized k-shift forbidden substrings in permutations, preprint, 2017,

    https://arxiv.org/abs/1610.06217.

[18] J. Riordan, An Introduction to Combinatorial Analysis, John Wiley & Sons, 1958.

[19] J. Riordan, Combinatorial Identities, John Wiley & Sons, 1968.

[20] S. Roman, The Umbral Calculus, Academic Press, 1984.

[21] S. M. Roman and G.-C. Rota, The umbral calculus, Adv. in Math. 27 (1978), 95–188.

[22] H. J. Ryser, Combinatorial Mathematics, John Wiley and Sons, 1963.

[23] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, http://oeis.org/.

[24] L. Takács, The problem of coincidences, Arch. Hist. Exact Sci. 21 (1979/80), 229–244.

[25] R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer-Verlag, 1999.

[26] C. Wang, P. Miska and I. Mezö, The r-derangement numbers, Discrete Math. 340 (2017), 1681–1692.

2000 Mathematics Subject Classification: Primary: 05A19, Secondary: 05A05, 05A15, 05A40, 11B73. Keywords: 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.

(Concerned with sequences \underline{A000110}, \underline{A000153}, \underline{A000166}, \underline{A000255}, \underline{A000261}, \underline{A000262}, \underline{A001909}, \underline{A001910}, \underline{A008275}, \underline{A008277}, \underline{A008290}, \underline{A008297}, \underline{A049460}, \underline{A051338}, \underline{A051339}, \underline{A051379}, \underline{A051380}, \underline{A051523}, \underline{A055790}, \underline{A123513}, \underline{A130534}, \underline{A132393}, \underline{A143491}, \underline{A143492}, \underline{A143493}, \underline{A143494}, \underline{A143495}, \underline{A143496}, \underline{A176732}, \underline{A176733}, \underline{A176734}, \underline{A176735}, \underline{A176736}, \underline{A193685}, \underline{A277563}, \underline{A277609}, \underline{A280425}, \underline{A280920}, \underline{A284204}, \underline{A284205}, \underline{A284206}, and \underline{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.