Associated Stirling Eulerian Numbers and Their q-Analogues

Imboa-Navalona Manjaka Rakotoson and Fanja Rakotondrajao Department of Mathematics and Computer Science Antananarivo University 101 Antananarivo Madagascar

                             2knaval@gmail.com
                             frakoton@yahoo.fr

Abstract In this paper, we study the excedance distribution over permutations while considering the parameters of cycle length and the number of cycles. We refer to the number of such permutations as the associated Stirling Eulerian number. Moreover, if we consider the permutations in which the first s integers are in different cycles, we denote their count as the associated s-Stirling Eulerian number. We provide a formula defining these numbers, along with their generating functions. We establish q-analogues and offer extensions of the results.

1 Introduction

The Stirling numbers of the first kind, denoted S_{n,k}, count the permutations with k cycles over n objects. These are classical numbers. Appell [1], Carlitz [5, 6], Comtet [7], Foata [8], Riordan [13], Tricomi [15] have defined the associated Stirling numbers of the first kind, denoted d(n, k), which count the numbers of permutations over n objects having exactly k cycles, where each cycle has a length 2 or greater. These numbers are defined as follows:

d(n + 1, k) = n(d(n, k) + d(n − 1, k − 1)),  (1)

with d(n, 1) = (n − 1)! and d(n, k) = 0 for n ≤ 2k − 1.

The generating function D(q, u) = ∑_{k} ∑_{n} d(n, k)q^{k} \frac{u^{n}}{n!} has the closed form

D(q, u) = (exp(−u)/(1 − u))^{q}.  (2)

Belbachir and Bousbaa [2], as well as Broder [4] have conducted in-depth studies of these numbers.

Definition 1. An r-cycle is a cycle in a permutation of length r. A circular permutation over [n] is a permutation consisting of an n-cycle. An r-cycle permutation is a permutation in which each cycle has length r.

An r^{−}-cycle (respectively, r^{+}-cycle) permutation is a permutation where each cycle length is at most r (respectively, greater than r). An involution is a 2^{−}-cycle permutation. Following Broder’s definitions [4], we define the number of r^{−}-cycle (respectively, r^{+}-cycle) permutations as the r^{−}-associated (respectively, r^{+}-associated) Stirling number of the first kind.

An (r^{−}, k)-cycle (respectively, (r^{+}, k)-cycle) permutation is an r^{−}-cycle (respectively, r^{+}-cycle) permutation consisting of k cycles. If each cycle has length r, we refer to it as an ((r), k)-cycle permutation. Furthermore, if the first s integers lie in distinct cycles, we define an (r^{−}, k, s)-cycle (respectively, (r^{+}, k, s)-cycle) permutation as an (r^{−}, k)-cycle (respectively, (r^{+}, k)-cycle) permutation. The r^{−}-associated s-Stirling number of the first kind (respectively, r^{+}-associated s-Stirling number of the first kind) counts the number of such permutations. If the length of each cycle is equal to r, we call it an ((r), k, s)-cycle permutation.

An (r^{−}, ⋆, s)-cycle permutation (respectively, (r^{+}, ⋆, s)-cycle permutation) is an r^{−}-cycle (respectively, r^{+}-cycle) permutation where the first s integers are in distinct cycles.

We can generalize this by considering an (r_{1}) ⋯ (r_{ℓ})-cycle permutation consisting of cycles of lengths 1 < r_{1} < ⋯ < r_{ℓ}, and r_{1} ⋯ r_{s}-cycle permutations, where the first s integers are in distinct cycles of lengths r_{i} > 1 for i = 1, …, s.

An ((r_{1}) ⋯ (r_{ℓ}), k)-cycle permutation is an (r_{1}) ⋯ (r_{ℓ})-cycle permutation with k cycles, and an ((r_{1}) ⋯ (r_{ℓ}), k, s)-cycle permutation has the first s integers in distinct cycles. An r_{1} ⋯ r_{s}(r_{s+1}) ⋯ (r_{ℓ})-cycle permutation is a permutation where the first s integers belong to different cycles, each of length r_{i} > 1 for i = 1, …, s, and the remaining cycles have lengths 1 < r_{s+1} < ⋯ < r_{ℓ}.

An r_{1}^{⋆} ⋯ r_{ℓ}^{⋆}-cycle permutation is a permutation that does not contain any cycles of length r_{i} for 1 ≤ i ≤ ℓ.

Definition 2. An integer i is a fixed point of a permutation σ if σ(i) = i.

A derangement is a permutation without fixed points. We can also define a derangement as a 1^{+}-cycle permutation.

Definition 3 (Rakotondrajao [12]). An s-fixed-points-permutation is a permutation whose set of fixed points is a subset of the set [s], and the first s integers lie in different cycles.

For example, the permutation (1 4)(2)(3)(5 7)(6) is a (0^{+}, 5, 3)-cycle permutation and not a 3-fixed-points-permutation.

Definition 4. An integer i is an excedance for a permutation σ if σ(i) > i.

The number of permutations of n objects with exactly m excedances is the classical Eulerian number A_{n,m}. They satisfy the following relation:

A_{n,m} = (n − m)A_{n−1,m−1} + (m + 1)A_{n−1,m},  (3)

with A_{0,0} = 1 and A_{0,1} = 0. The egf of the Eulerian polynomial

A_{n}(x) = ∑_{σ∈S_{n}} x^{e(σ)} = ∑_{m} A_{n,m}x^{m}  (4)

has the closed form

A(x, u) = ∑_{n} A_{n}(x)\frac{u^{n}}{n!} = \frac{x − 1}{x − exp ((x − 1)u)}.  (5)

Many works on Eulerian numbers can be easily found in the literature, including those by Foata and Schützenberger [8], Mantaci and Rakotondrajao [11], Riordan [13], Stanley [14]. The function P(x, u) defined by

P(x, u) = \frac{ln(A(x, u)) + u(x − 1)}{x},  (6)

is the primitive of A(x, u) and is computed combinatorially in Sec. 3.

Note that a permutation is a 0^{+}-cycle permutation, and a derangement a 1^{+}-cycle permutation. The length of an r-cycle permutation is a multiple of r and the length of an ((r), k)-cycle permutation is equal to kr. We are interested in the study of associated Stirling Eulerian numbers. More precisely, we consider the parameter of the number of cycles with the constraint on the length of cycles in the study of excedance distribution over permutations. We also study the same distribution by adding the placement of the first s integers. Recurrence relations, formulas, exponential generating functions, and their q-analogues are provided. We extend Brenti’s results [3, Sec. 7] on his study of a q-analogue of the Eulerian polynomials, as well as general identities. A general identity extends the result on derangement numbers established by Ksavrelof and Zeng [9], along with new identities. We provide generalizations of our results by specifying the lengths of cycles. Note that the associated Stirling numbers of the first kind d(n, k) in Equation (1) enumerate the (1^{+}, k)-cycle permutations, while D(q, x) in Equation (2) is a q-analogue of the exponential generating function (egf) of the derangement numbers. We denote by e(σ) the number of excedances of the permutation σ and by c(σ) the number of cycles of σ. The parameter q associated with the number of cycles defines the q-analogue in our study. We use the expression Stirling number to refer to the Stirling number of the first kind and introduce the notation in each section throughout this paper.

2 Circular permutations

C_{n}  the set of circular permutations over [n]
C_{n,m} |{σ ∈ C_{n} : e(σ) = m}| Th. 5 Eq. (7)
C_{n}(x) ∑_{m} C_{n,m}x^{m} = ∑_{σ∈C_{n}} x^{e(σ)}  Th. 5 Eq. (8)

C(x, u) ∑_{n} ∑_{σ∈C_{n}} x^{e(σ)} \frac{u^{n}}{n!} = ∑_{n} C_{n}(x)\frac{u^{n}}{n!}  Th. 6 Eq. (9)
C_{r^{−}}  the set of r^{−}-cycle circular permutations
C^{r^{−}}(x, u) ∑_{n=0}^{r} ∑_{σ∈C_{n}} x^{e(σ)} \frac{u^{n}}{n!} = ∑_{n=0}^{r} C_{n}(x)\frac{u^{n}}{n!}  Th. 7 Eq. (10)

Cor. 12 Eq. (15)

C_{r^{+}}  the set of r^{+}-cycle circular permutations
C^{(r)}(x, u) ∑_{σ∈C_{r}} x^{e(σ)} \frac{u^{r}}{r!} = C_{r}(x)\frac{u^{r}}{r!}  Th. 8 Eq. (11)
C^{r^{+}}(x, u) ∑_{n≥r+1} ∑_{σ∈C_{n}} x^{e(σ)} \frac{u^{n}}{n!} = ∑_{n≥r+1} C_{n}(x)\frac{u^{n}}{n!} Th. 9 Eq. (12)

Cor. 33 Eq. (33)

Table 1: Notation.

Theorem 5. For all integers n ≥ 2 and 1 ≤ m ≤ n, we have

C_{n,m} = A_{n−1,m−1} with C_{1,0} = 1  (7)

and

C_{n}(x) = xA_{n−1}(x).  (8)

Proof. Let n ≥ 2 and m ≥ 1. Let π ∈ C_{n} be a permutation such that e(π) = m. It is common to put the smallest letter at the beginning of the cycle. The integer 1 is always an excedance for a circular permutation. The remaining permutation after this integer, which is an ordinary permutation over the set {2, …, n}, has m − 1 excedances. Multiplying by x^{m} and summing over m in Equation (7), we get

C_{n}(x) = xA_{n−1}(x).

Theorem 6. The exponential generating function of the excedance distribution over circular permutations has the closed form

C(x, u) = ∑_{n≥0} ∑_{π∈C_{n}} x^{e(π)} \frac{u^{n}}{n!} = ln A(x, u).  (9)

Proof. Since C_{n}(x) = xA_{n−1}(x), we get

∑_{n≥2} C_{n}(x)\frac{u^{n}}{n!} = ∑_{n≥2}xA_{n−1}(x)\frac{u^{n}}{n!} ,
= x(P(x, u)) − xu.

Then, we obtain

u + ∑_{n≥2} C_{n}(x)\frac{u^{n}}{n!} = u + x\frac{ln(A(x, u)) + u(x − 1)}{x} − xu.

Therefore, we have

C(x, u) = ln(A(x, u)).

Theorem 7. For a fixed integer r ≥ 1, the exponential generating function of the excedance distribution over circular r^{−}-cycle permutations has the closed form

C^{r^{−}}(x, u) = ∑_{n=1}^{r} C_{n}(x)\frac{u^{n}}{n!} = u + x ∑_{n=1}^{r−1} A_{n}(x)\frac{u^{n+1}}{(n + 1)!} .  (10)

Proof. From Equation (8), we have

∑_{n=2}^{r} C_{n}(x)\frac{u^{n}}{n!} = x ∑_{n=2}^{r} A_{n−1}(x)\frac{u^{n}}{n!} .

∑_{n=1}^{r} C_{n}(x)\frac{u^{n}}{n!} = u + x ∑_{n=1}^{r−1} A_{n}(x)\frac{u^{n+1}}{(n + 1)!} .

Theorem 8. For a fixed integer r ≥ 2, the exponential generating function of the excedance distribution over circular r-cycle permutations has the closed form

C^{(r)}(x, u) = xA_{r−1}(x)\frac{u^{r}}{r!} .  (11)

Theorem 9. For a fixed integer r ≥ 2, the exponential generating function of the excedance distribution over circular r^{+}-cycle permutations has the closed form

C^{r^{+}}(x, u) = ∑_{n≥r+1} C_{n}(x)\frac{u^{n}}{n!} = ln(A(x, u) exp(−u − x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i+1}}{(i + 1)!} )). (12)

Proof. We have

C^{r^{+}}(x, u) = C(x, u) − C^{r^{−}}(x, u),

= ln A(x, u) − u − x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i+1}}{(i + 1)!} ,

= ln(A(x, u) exp(−u − x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i+1}}{(i + 1)!} )).

3 r^{−}-cycle permutations

(n_{1}, …, n_{k})! \frac{n_{1} + ⋯ + n_{k}}{n_{1}! ⋯ n_{k}!}
S_{n}^{r^{−}}  the set of r^{−}-cycle permutations
A_{n,m}^{r^{−}}  |{σ ∈ S_{n}^{r^{−}} : e(σ) = m}|  Th. 10 Eq. (13)

r^{−}-associated Stirling Eulerian number

A_{n}^{r^{−}}(x)  ∑_{m} A_{n,m}^{r^{−}}x^{m} = ∑_{σ∈S_{n}^{r^{−}}} x^{e(σ)}
A^{r^{−}}(x, u)  ∑_{n} ∑_{σ∈S_{n}^{r^{−}}} x^{e(σ)} \frac{u^{n}}{n!} = ∑_{n} A_{n}^{r^{−}}(x)\frac{u^{n}}{n!}  Th. 11 Eq. (14)
P(x, u)  the primitive of A(x, u) with respect to u  Cor. 13 Eq. (16)
S_{n}^{r^{−},k}  the set of (r^{−}, k)-cycle permutations
A_{n,m,k}^{r^{−}}  |{σ ∈ S_{n}^{r^{−},k} : e(σ) = m}|
A_{n,k}^{r^{−}}(x)  ∑_{m} A_{n,m,k}^{r^{−}}x^{m} = ∑_{σ∈S_{n}^{r^{−},k}} x^{e(σ)}
A_{k}^{r^{−}}(x, u)  ∑_{n} ∑_{σ∈S_{n}^{r^{−},k}} x^{e(σ)} \frac{u^{n}}{n!} = ∑_{n} A_{n,k}^{r^{−}}(x)\frac{u^{n}}{n!}  Th. 14 Eq. (17)
A^{r^{−}}(q, x, u) ∑_{n} ∑_{σ∈S_{n}^{r^{−},k}} x^{e(σ)}q^{c(σ)} \frac{u^{n}}{n!} q-analogue of A^{r^{−}}(x, u)  Th. 15 Eq. (18)

Cor. 16 Eq. (19)

S_{n}^{r^{−},⋆,s}  the set of (r^{−}, ⋆, s)-cycle permutations
[A_{n,m}^{r^{−}}]_{s}  |{σ ∈ S_{n}^{r^{−},⋆,s} : e(σ) = m}|
[A_{n}^{r^{−}}(x)]_{s}  ∑_{m}[A_{n,m}^{r^{−}}]_{s}x^{m} = ∑_{σ∈S_{n}^{r^{−},⋆,s}} x^{e(σ)}

[A^{r^{−}}(x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{r^{−},⋆,s}} x^{e(σ)} \frac{u^{n}}{n!} = ∑_{n}[A_{n}^{r^{−}}(x)]_{s} \frac{u^{n}}{n!}  Th. 17 Eq. (20)
[A_{n,m,k}^{r^{−}}]_{s}  |{σ ∈ S_{n}^{r^{−},k,s} : e(σ) = m}|
[A_{n,k}^{r^{−}}(x)]_{s}  ∑_{m}[A_{n,m,k}^{r^{−}}]_{s}x^{m} = ∑_{σ∈S_{n}^{r^{−},k,s}} x^{e(σ)}

[A_{k}^{r^{−}}(x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{r^{−},k,s}} x^{e(σ)} \frac{u^{n}}{n!} = ∑_{n}[A_{n,k}^{r^{−}}(x)]_{s} \frac{u^{n}}{n!}  Th. 18 Eq. (21)

[A^{r^{−}}(q, x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{r^{−},⋆,s}} x^{e(σ)}q^{c(σ)} \frac{u^{n}}{n!} q-analogue of [A^{r^{−}}(x, u)]_{s} Th. 19 Eq. (22)

Table 2: Notation.

Theorem 10. For a fixed integer r ≥ 2, for all integers n and m such that 0 ≤ m ≤ n, we have

A_{n+1,m}^{r^{−}} = ∑_{j=1}^{r−1} \binom{n}{j} ∑_{i≥0} C_{j+1,i}A_{n−j,m−i}^{r^{−}} + A_{n,m}^{r^{−}}.  (13)

Proof. Consider the integer n + 1 in an r^{−}-cycle permutation of S_{n+1}^{r^{−}}.

1. If n + 1 is a fixed point, the remaining elements form a permutation of [n] with m excedances, where the lengths of the cycles are at most r. Therefore, there are A_{n,m}^{r^{−}} possibilities.

2. Otherwise, we have \binom{n}{j}C_{j+1,i} ways to form a cycle of length j + 1 with i excedances that contains the integer n + 1, for 1 ≤ j ≤ n. The remaining elements of [n] form a permutation with m − i excedances, whose cycle lengths are at most r. Thus, we get ∑_{j=1}^{r−1} \binom{n}{j} ∑_{i≥0} C_{j+1,i}A_{n−j,m−i}^{r^{−}} possibilities.

Theorem 11. For a fixed integer r ≥ 2, the exponential generating function of the r^{−}- associated Stirling Eulerian numbers has the closed form

A^{r^{−}}(x, u) = exp (u + x ∑_{j=1}^{r−1} A_{j}(x)\frac{u^{j+1}}{(j + 1)!} ).  (14)

Proof. Since

A_{n+1,m}^{r^{−}} = ∑_{j=1}^{r−1} \binom{n}{j} ∑_{i≥0} C_{j+1,i}A_{n−j,m−i}^{r^{−}} + A_{n,m}^{r^{−}},

we have

A_{n+1}^{r^{−}}(x) = ∑_{j=1}^{r−1} \binom{n}{j}C_{j+1}(x)A_{n−j}^{r^{−}}(x) + A_{n}^{r^{−}}(x).

We get

\frac{∂}{∂u}A^{r^{−}}(x, u) = ∑_{n≥0} ∑_{j=1}^{r−1} \binom{n}{j}C_{j+1}(x)A_{n−j}^{r^{−}}(x)\frac{u^{n}}{n!} + A^{r^{−}}(x, u),

= ∑_{j=1}^{r−1} C_{j+1}(x)\frac{u^{j}}{j!} A_{n−j}^{r^{−}}(x)\frac{u^{n−j}}{(n − j)!} + A^{r^{−}}(x, u),

= ∑_{j=1}^{r−1} C_{j+1}(x)\frac{u^{j}}{j!} A^{r^{−}}(x, u) + A^{r^{−}}(x, u).

Hence,

ln (A^{r^{−}}(x, u)) = ∑_{j=1}^{r−1} C_{j+1}(x)\frac{u^{j+1}}{(j + 1)!} + u.

Finally, we have

A^{r^{−}}(x, u) = exp (u + ∑_{j=1}^{r−1}C_{j+1}(x)\frac{u^{j+1}}{(j + 1)!} ) = exp (u + x∑_{j=1}^{r−1}A_{j}(x)\frac{u^{j+1}}{(j + 1)!} ).

Corollary 12. For all integers r ≥ 2, we have

C^{r^{−}}(x, u) = ln A^{r^{−}}(x, u).  (15)

Corollary 13. The primitive of the exponential generating function of the Eulerian numbers has the closed form

P(x, u) = \frac{ln(A(x, u)) + u(x − 1)}{x}.  (16)

Proof. A permutation without restrictions on the cycle length can be considered an ordinary permutation. From Equation (14), we deduce

exp(u + x ∑_{n≥1} A_{n}(x)\frac{u^{n+1}}{(n + 1)!} ) = A(x, u),

u + x ∑_{n≥1} A_{n}(x)\frac{u^{n+1}}{(n + 1)!} = ln A(x, u),
u + x(P(x, u) − u) = ln A(x, u).

Thus, we have

P(x, u) = \frac{ln A(x, u) + u(x − 1)}{x}.

Theorem 14. For fixed integers r ≥ 2 and k, the exponential generating function of the excedance distribution over (r^{−}, k)-cycle permutations has the closed form

A_{k}^{r^{−}}(x, u) = \frac{(ln A^{r^{−}}(x, u))^{k}}{k!} = \frac{(u + x∑_{n=1}^{r−1}A_{n}(x)\frac{u^{n+1}}{(n + 1)!} )^{k}}{k!} .  (17)

Proof. A permutation of S_{n}^{r^{−},k} is a product of k disjoint circular permutations of length smaller or equal than r, hence

A_{n,m,k}^{r^{−}} = \frac{1}{k!} ∑_{\begin{matrix}i_{1},...,i_{k}≤r \\ i_{1}+···+i_{k}=n \end{matrix}} ∑_{j_{1}+···+j_{k}=m}(i_{1}, …, i_{k})! C_{i_{1},j_{1}} ⋯ C_{i_{k},j_{k}}.

We get

A_{n,k}^{r^{−}}(x) = \frac{1}{k!} ∑_{\begin{matrix}i_{1},...,i_{k}≤r \\ i_{1}+···+i_{k}=n \end{matrix}}(i_{1}, …, i_{k})! C_{i_{1}}(x) ⋯ C_{i_{k}}(x),

and

A_{k}^{r^{−}}(x, u) = \frac{1}{k!}(∑_{n=1}^{r} C_{n}(x)\frac{u^{n}}{n!} )^{k} = \frac{(C^{r^{−}}(x, u))^{k}}{k!} ,

= \frac{(ln A^{r^{−}}(x, u))^{k}}{k!} , from Equation (15),

= \frac{1}{k!}(u + x∑_{n=1}^{r−1}A_{n}(x)\frac{u^{n+1}}{(n + 1)!} )^{k}, from Equation (14).

Theorem 15. For a fixed integer r ≥ 2, a q-analogue exponential generating function of the r^{−}-associated Stirling Eulerian numbers has the closed form

A^{r^{−}}(q, x, u) = exp (q(u + x ∑_{j=1}^{r−1} A_{j}(x)\frac{u^{j+1}}{(j + 1)!} )).  (18)

Proof. From equation (17), we get

∑_{k≥0} A_{k}^{r^{−}}(x, u)q^{k} = ∑_{k≥0} \frac{(u + x∑_{j=1}^{r−1}A_{j}(x)\frac{u^{j+1}}{(j + 1)!} )^{k}}{k!} q^{k},

= exp (q(u + x∑_{j=1}^{r−1}A_{j}(x)\frac{u^{j+1}}{(j + 1)!} )).

Corollary 16. For all integer r ≥ 2, we have

A^{r^{−}}(q, x, u) = (A^{r^{−}}(x, u))^{q}.  (19)

Theorem 17. For a fixed integer r ≥ 2, the partial differential exponential generating function of the r^{−}-associated s-Stirling Eulerian numbers has the closed form

\frac{∂^{s}[A^{r^{−}}(x, u)]_{s}}{∂u^{s}} = (1 + x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i}}{i!} )^{s}A^{r^{−}}(x, u).  (20)

Proof. Considering the first s − 1 integers and their cycles, we have

[A_{n+s,m}^{r^{−}}]_{s} = ∑_{\begin{matrix}i_{1}+···+i_{s−1}=n \\ 0≤i_{1},...,i_{s−1}≤r−1 \end{matrix}}(i_{1}, …, i_{s−1})! ∑_{j_{1}+···+j_{s}=m} C_{i_{1}+1,j_{1}} ⋯ C_{i_{s−1}+1,j_{s−1}}A_{n+1−∑_{ℓ=1}^{s−1} i_{ℓ},j_{s}}^{r^{−}}.

We get

[A_{n+s}^{r^{−}}(x)]_{s} = ∑_{\begin{matrix}i_{1}+···+i_{s−1}=n \\ 0≤i_{1},...,i_{s−1}≤r−1 \end{matrix}}(i_{1}, …, i_{s−1})! C_{i_{1}+1}(x) ⋯ C_{i_{s−1}+1}(x)A_{n+1−∑_{ℓ=1}^{s−1} i_{ℓ}}^{r^{−}}(x),

and

\frac{∂^{s}[A^{r^{−}}(x, u)]_{s}}{∂u^{s}} = (∑_{i=0}^{r−1} C_{i+1}(x)\frac{u^{i}}{i!} )^{s−1} \frac{∂A^{r^{−}}(x, u)}{∂u},

= (1 + ∑_{i=1}^{r−1} C_{i+1}(x)\frac{u^{i}}{i!} )^{s−1}(1 + x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i}}{i!} )A^{r^{−}}(x, u),

= (1 + x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i}}{i!} )^{s}A^{r^{−}}(x, u).

Theorem 18. For fixed integers r, k and s, the partial differential exponential generating function of the excedance distribution over (r^{−}, k, s)−cycle permutations has the closed form

\frac{∂^{s}[A_{k}^{r^{−}}(x, u)]_{s}}{∂u^{s}} = (1 + x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i}}{i!} )^{s} \frac{(ln A^{r−}(x, u))^{k−s}}{(k − s)!} .  (21)

Proof. Considering the first s integers and their cycles, we have

[A_{n+s,m,k}^{r^{−}}]_{s} = ∑_{\begin{matrix}i_{1}+···+i_{s}=n \\ 0≤i_{1},...,i_{s}≤r−1 \end{matrix}}(i_{1}, …, i_{s})! ∑_{m_{1}+···+m_{s}+m_{t}=m} C_{i_{1}+1,m_{1}} ⋯ C_{i_{s}+1,m_{s}}A_{n−∑_{l=1}^{s} i_{l},m_{t},k−s}^{r^{−}}.

[A_{n+s,k}^{r^{−}}(x)]_{s} = ∑_{\begin{matrix}i_{1}+···+i_{s}=n \\ 0≤i_{1},...,i_{s}≤r−1 \end{matrix}}(i_{1}, …, i_{s})! C_{i_{1}+1}(x) ⋯ C_{i_{s}+1}(x)A_{n−∑_{l=1}^{s} i_{l},k−s}^{r^{−}}(x),

and

\frac{∂^{s}[A_{k}^{r^{−}}(x, u)]_{s}}{∂u^{s}} = (∑_{i=0}^{r−1} C_{i+1}(x)\frac{u^{i}}{i!} )^{s}A_{k−s}^{r^{−}}(x, u) = (1 + ∑_{i=1}^{r−1} C_{i+1}(x)\frac{u^{i}}{i!} )^{s} \frac{(ln A^{r^{−}}(x, u))^{k−s}}{(k − s)!} ,

= (1 + x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i}}{i!} )^{s} \frac{(ln A^{r^{−}}(x, u))^{k−s}}{(k − s)!} .

Theorem 19. For fixed integers r and s, a partial differential q-analogue exponential generating function of the excedance distribution over (r^{−}, ⋆, s)-cycle permutations has the closed form

\frac{∂^{s}[A^{r^{−}}(q, x, u)]_{s}}{∂u^{s}} = q^{s}(1 + x ∑_{i=1}^{r−1} A_{i}(x)\frac{u^{i}}{i!} )^{s}(A^{r^{−}}(x, u))^{q}.  (22)

Proof. We immediately have the result by multiplying by q^{k} the right member of Equation (21) and summing over k.

4 r-cycle permutations

S_{n}^{(r)}  the set of r-cycle permutations
A_{n,m}^{(r)} |{σ ∈ S_{n}^{(r)} : e(σ) = m}| Th. 20 Eq. (23)
A_{n}^{(r)}(x)  ∑_{m} A_{n,m}^{(r)}x^{m} = ∑_{σ∈S_{n}^{(r)}} x^{e(σ)}
A^{(r)}(x, u) ∑_{n} A_{n}^{(r)}(x)\frac{u^{n}}{n!} the egf  Th. 21 Eq. (24)
S_{n}^{(r),k}  the set of ((r), k)-cycle permutations
A_{n,m,k}^{(r)}  |{σ ∈ S_{n}^{(r),k} : e(σ) = m}|
A_{n,k}^{(r)}(x)  ∑_{m} A_{n,m,k}^{(r)}x^{m} = ∑_{σ∈S_{n}^{(r),k}} x^{e(σ)}
A_{k}^{(r)}(x, u) ∑_{n} ∑_{σ∈S_{n}^{(r),k}} x^{e(σ)} \frac{u^{n}}{n!} = ∑_{n} A_{n,k}^{(r)}(x)\frac{u^{n}}{n!}  Th. 22 Eq. (25)
A^{(r)}(q, x, u) ∑_{n} ∑_{σ∈S_{n}^{(r),k}} x^{e(σ)}q^{c(σ)} \frac{u^{n}}{n!} q-analogue of A^{(r)}(x, u)  Th. 23 Eq. (26)
S_{n}^{(r),⋆,s}  the set of ((r), ⋆, s)-cycle permutations

[A_{n,m}^{(r)}]_{s}  |{σ ∈ S_{n}^{(r),⋆,s} : e(σ) = m}|
[A_{n}^{(r)}(x)]_{s} ∑_{m}[A_{n,m}^{(r)}]_{s}x^{m} = ∑_{σ∈S_{n}^{(r),⋆,s}} x^{e(σ)}
[A^{(r)}(x, u)]_{s} ∑_{n}[A_{n}^{(r)}(x)]_{s} \frac{u^{n}}{n!} its egf  Th. 27 Eq. (27)
[A_{k}^{(r)}(x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{(r),⋆,s}} x^{e(σ)} \frac{u^{n}}{n!}  Th. 28 Eq. (28)
[A^{(r)}(q, x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{(r),k,s}} x^{e(σ)}q^{c(σ)} \frac{u^{n}}{n!} q-analogue of [A^{(r)}(x, u)]_{s} Th. 29 Eq. (29)

Table 3: Notation.

Theorem 20. For a fixed integer r ≥ 2, for all integers n ≥ m ≥ 0, we have the following formula

A_{n+1,m}^{(r)} = \binom{n}{r − 1} ∑_{k≥1} C_{r,k}A_{n−(r−1),m−k}^{(r)}.  (23)

Proof. First, consider the integer n + 1 and construct the cycle that contains it in a permutation of S_{n+1}^{r}. To do this, we choose r − 1 integers from [n] and form a circular permutation with n + 1 that has k excedances, where 1 ≤ k ≤ m − 1. There are \binom{n−1}{k}C_{r,k} possibilities for this step. Next, to obtain a permutation of [n + 1] with m excedances, where each cycle length is equal to r, we consider the remaining n − (r − 1) integers and form a permutation of [n − (r − 1)] with m − k excedances, ensuring that each cycle length is also equal to r. This construction gives us the desired result.

Theorem 21. For a fixed integer r ≥ 2, the exponential generating function of the numbers A_{n,m}^{(r)} has the closed form

A^{(r)}(x, u) = exp(xA_{r−1}(x)\frac{u^{r}}{r!} ).  (24)

Proof. From Equation (23), we get

A_{n+1}^{(r)}(x) = \binom{n}{r − 1}C_{r}(x)A_{n−r+1}^{(r)}(x).

Let us consider the following variable change r − 1 = r′, we have

A_{n+1}^{(r)}(x) = \binom{n}{r′}C_{r′+1}(x)A_{n−r′}^{(r)}(x).

We deduce

\frac{∂}{∂u}A^{(r)}(x, u) = ∑_{n≥0} \binom{n}{r′}C_{r′+1}(x)A_{n−r′}^{(r)}(x)\frac{u^{n}}{n!} = ∑_{n≥0} C_{r′+1}(x)\frac{u^{r′}}{r′!} A_{n−r′}^{(r)}(x)\frac{u^{n−r′}}{(n − r′)!} ,

= C_{r′+1}(x)\frac{u^{r′}}{r′!} A^{(r)}(x, u).

Thus,

\frac{(A^{r}(x, u))′_{u}}{A^{(r)}(x, u)} = C_{r′+1}(x)\frac{u^{r′}}{r′!} .

Integrating with respect to u, we have

A^{(r)}(x, u) = exp(C_{r′+1}(x)\frac{u^{r′+1}}{(r′ + 1)!} ) = exp(xA_{r′}(x)\frac{u^{r′+1}}{(r′ + 1)!} ).

Thus,

A^{(r)}(x, u) = exp(xA_{r−1}(x)\frac{u^{r}}{r!} ).

Theorem 22. For fixed integers r ≥ 2 and k, the exponential generating function of the excedance distribution over ((r), k)−cycle permutations has the closed form

A_{k}^{(r)}(x, u) = \frac{1}{k!} (xA_{r−1}(x)\frac{u^{r}}{r!} )^{k} = \frac{(ln A^{(r)}(x, u))^{k}}{k!} .  (25)

Proof. A permutation of S_{n}^{(r),k} is a product of k disjoints circular permutation of lenght r, hence

A_{n,m,k}^{(r)} = \frac{1}{k!}\binom{n}{r} ⋯ \binom{n − (k − 1)r}{r} ∑_{m_{1}+···+m_{k}=m} C_{r,m_{1}} × ⋯ × C_{r,m_{k}}.

We get

A_{n,k}^{(r)}(x) = \frac{1}{k!} \frac{n!}{(r!)^{k}} (C_{r}(x))^{k}.

We deduce

A_{k}^{(r)}(x, u) = \frac{1}{k!} \frac{(C_{r}(x))^{k}u^{kr}}{(r!)^{k}} = \frac{1}{k!}(xA_{r−1}(x)\frac{u^{r}}{r!} )^{k}.

Theorem 23. For a fixed integer r ≥ 2, a q-analogue exponential generating function of the number A_{n,m,k}^{(r)} has the closed form

A^{(r)}(q, x, u) = exp (qxA_{r−1}(x)\frac{u^{r}}{r!} ).  (26)

Proof. We immediately have the result by multiplying by q^{k} the Equation (25) and summing over k.

Corollary 24. For fixed integers r ≥ 2 and n, we have

∑_{π∈S_{n}^{r,k}} x^{e(π)}q^{c(π)} = \begin{cases}\frac{(rk)!}{(r!)^{k} k!}x^{k}q^{k}A_{r−1}(x)^{k}, & if n = kr ; \\ 0 & otherwise. \end{cases}

Corollary 25. For fixed integers r ≥ 2 and n, we have

|S_{n}^{r}| = \begin{cases}\frac{n!}{r^{n/r} (n/r)!} , & if r | n ; \\ 0 & otherwise. \end{cases}

Corollary 26. For a fixed integer r ≥ 2, we have

∑_{n≥0} |S_{n}^{r}|\frac{u^{n}}{n!} = exp (u^{r}/r).

Theorem 27. For fixed integers r ≥ 2 and s, we have

\frac{∂^{s}[A^{(r)}(x, u)]_{s}}{∂u^{s}} = x^{s}(A_{r−1}(x)\frac{u^{r−1}}{(r − 1)!} )^{s}A^{(r)}(x, u).  (27)

Proof. Since

[A_{n+s,m}^{(r)}]_{s} = \binom{n}{r − 1} ⋯ \binom{n − (s − 1)(r − 1)}{r − 1} ∑_{m_{1}+···+m_{s}+m_{t}=m} C_{r,m_{1}} ⋯ C_{r,m_{s}}A_{n−s(r−1),m_{t}}^{(r)},

we get

[A_{n+s}^{(r)}(x)]_{s} = \binom{n}{r − 1} ⋯ \binom{n − (s − 1)(r − 1)}{r − 1}(C_{r}(x))^{s}A_{n−s(r−1)}^{(r)}(x).

We deduce

\frac{∂^{s}[A^{(r)}(x, u)]_{s}}{∂u^{s}} = (C_{r}(x)\frac{u^{r−1}}{(r − 1)!} )^{s}A^{(r)}(x, u) = x^{s}(A_{r−1}(x)\frac{u^{r−1}}{(r − 1)!} )^{s}A^{(r)}(x, u).

Theorem 28. For fixed integers r ≥ 2, k and s, the partial differential exponential generating function of the excedance distribution over ((r), k, s)-cycle permutations has the closed form

\frac{∂^{s}[A_{k}^{(r)}(x, u)]_{s}}{∂u^{s}} = x^{s}(A_{r−1}(x)\frac{u^{r−1}}{(r − 1)!} )^{s} \frac{(ln A^{(r)}(x, u))^{k−s}}{(k − s)!} .  (28)

Proof. Let us consider the first s integers and their cycles

[A_{n+s,m,k}^{(r)}]_{s} = \binom{n}{r − 1} ⋯ \binom{n − (s − 1)(r − 1)}{r − 1}×

∑_{m_{1}+···+m_{s}+m_{t}=m} C_{r,m_{1}} ⋯ C_{r,m_{s}}A_{n−s(r−1),m_{t},k−s}^{(r)}.

\frac{∂^{s}[A_{k}^{(r)}(x, u)]_{s}}{∂u^{s}} = (C_{r}(x)\frac{u^{r−1}}{(r − 1)!} )^{s}A_{k−s}^{(r)}(x, u) = (xA_{r−1}(x)\frac{u^{r−1}}{(r − 1)!} )^{s} \frac{(ln A^{(r)}(x, u))^{k−s}}{(k − s)!} .

Theorem 29. For fixed integers r ≥ 2 and s, a partial differential q-analogue exponential generating function of the excedance distribution over ((r), ⋆, s)-cycle permutations has the closed form

\frac{∂^{s}[A^{(r)}(q, x, u)]_{s}}{∂u^{s}} = q^{s}x^{s}(A_{r−1}(x)\frac{u^{r−1}}{(r − 1)!} )^{s}(A^{(r)}(x, u))^{q}.  (29)

Proof. From Equation (28), we get

\frac{∂^{s}[A^{(r)}(q, x, u)]_{s}}{∂u^{s}} = ∑_{k≥0} x^{s}(A_{r−1}(x)\frac{u^{r−1}}{(r − 1)!} )^{s} \frac{(ln A^{(r)}(x, u))^{k−s}}{(k − s)!} q^{k−s}q^{s},

= q^{s}x^{s}(A_{r−1}(x)\frac{u^{r−1}}{(r − 1)!} )^{s} exp (q ln A^{(r)}(x, u)).

Hence, the result follows.

5 r^{+}-cycle permutations

S_{n}^{r^{+}}  the set of r^{+}-cycle permutations
A_{n,m}^{r}  |{σ ∈ S_{n}^{r^{+}} : e(σ) = m}|  Th. 30 Eq. (30)
r-associated Stirling Eulerian number  Th. 31 Eq. (31)
A_{n}^{r}(x)  ∑_{m} A_{n,m}^{r}x^{m} = ∑_{σ∈S_{n}^{r^{+}}} x^{e(σ)}
A^{r}(x, u) ∑_{n} A_{n}^{r}(x)\frac{u^{n}}{n!} the egf  Th. 32 Eq. (32)
S_{n}^{r^{+},k}  the set of (r^{+}, k)-cycle permutations
A_{n,m,k}^{r}  |{σ ∈ S_{n}^{r^{+},k} : e(σ) = m}|
A_{n,k}^{r}(x)  ∑_{m} A_{n,m,k}^{r}x^{m} = ∑_{σ∈S_{n}^{r^{+},k}} x^{e(σ)}
A_{k}^{r}(x, u) ∑_{n} A_{n,k}^{r}(x)\frac{u^{n}}{n!}  Th. 34 Eq. (34)
A^{r}(q, x, u) ∑_{k} ∑_{n} A_{n,k}^{r}(x)q^{k} \frac{u^{n}}{n!} q-analogue of A^{r}(x, u) Th. 35 Eq. (35)
S_{n}^{r^{+},⋆,s}  the set of (r^{+}, ⋆, s)-cycle permutations

[A_{n,m}^{r}]_{s}  |{σ ∈ S_{n}^{r^{+},⋆,s} : e(σ) = m}|
[A_{n}^{r}(x)]_{s} ∑_{m}[A_{n,m}^{r}]_{s}x^{m} = ∑_{σ∈S_{n}^{r^{+},⋆,s}} x^{e(σ)}

[A^{r}(x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{r^{+},⋆,s}} x^{e(σ)} \frac{u^{n}}{n!}  Th. 36 Eq. (36)

[A_{k}^{r}(x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{r^{+},k,s}} x^{e(σ)} \frac{u^{n}}{n!}  Th. 37 Eq. (37)
[A^{r}(q, x, u)]_{s} ∑_{k}[A_{k}^{r}(x, u)]_{s}q^{k} q-analogue of [A^{r}(x, u)]_{s}  Th. 38 Eq. (38)

Table 4: Notation.

Theorem 30. For a fixed integer r, for all integers n and m such that 0 ≤ m ≤ n and n ≥ r + 1, the r-associated Stirling Eulerian numbers satisfy the following formula

A_{n,m}^{r} = mA_{n−1,m}^{r} + (n − m)A_{n−1,m−1}^{r} + \binom{n − 1}{r} ∑_{s} C_{r+1,s}A_{n−r−1,m−s}^{r}.  (30)

Proof. Let n > r. Consider the integer n in an r^{+}-cycle permutation of S_{n}^{r^{+}}.

1. If n belongs to a cycle of length r + 1 with s excedances (1 ≤ s < m), there are \binom{n−1}{r} ways to choose the remaining r elements and C_{r+1,s} ways to form the specified cycle. We then create a permutation with m − s excedances, where the cycle lengths are greater than r using the remaining n − r − 1 elements, which gives A_{n−r−1,m−s}^{r} possibilities. Thus, the total number of possibilities is \binom{n−1}{r} ∑_{s} C_{r+1,s}A_{n−r−1,m−s}^{r}.

2. Otherwise, we consider τ as an r^{+}-cycle permutation in S_{n−1}^{r^{+}}:

(a) If τ has m excedances, we insert n after an excedance. There are mA_{n−1,m}^{r} possibilities.

(b) If τ has m − 1 excedances, we insert n after an anti-excedance. There are (n − m)A_{n−1,m−1}^{r} possibilities.

Theorem 31. For a fixed integer r, for all integers n and m such that 0 ≤ m ≤ n and n ≥ r + 1, we have

A_{n+1,m}^{r} = ∑_{j=r}^{n} \binom{n}{j} ∑_{i=1}^{m} C_{j+1,i}A_{n−j,m−i}^{r}.  (31)

Proof. Let r be a fixed integer with n ≥ r. Consider the integer n + 1, which belongs to a cycle of length j + 1 (r ≤ j) with i (1 ≤ i ≤ m) excedances. There are \binom{n}{j} ways to choose these j elements and C_{j+1,i} ways to form that cycle. We then form a permutation with m−i excedances, where the cycle lengths are greater than r, using the remaining n − j elements, resulting in A_{n−j,m−i}^{r} possibilities. Hence, we obtain the result.

Theorem 32. For a fixed integer r ≥ 1, the exponential generating function of the rassociated Stirling Eulerian numbers has the closed form

A^{r}(x, u) = A(x, u) exp(−u − x ∑_{j=1}^{r−1} A_{j}(x)\frac{u^{j+1}}{(j + 1)!} ).  (32)

Proof. From Equation (31), we get

A_{n+1}^{r}(x) = ∑_{j=r}^{n} \binom{n}{j}C_{j+1}(x)A_{n−j}^{r}(x) = ∑_{j=0}^{n} C_{j+1}(x)A_{n}^{r}(x) − ∑_{j=0}^{r−1} C_{j+1}(x)A_{n}^{r}(x),

= ∑_{j=0}^{n} C_{j+1}(x)A_{n}^{r}(x) − A_{n}(x) − ∑_{j=1}^{r−1} C_{j+1}(x)A_{n}^{r}(x).

We deduce

(A^{r}(x, u))′_{u} = \frac{(A(x, u))′_{u}}{A(x, u)} A^{r}(x, u) − A^{r}(x, u) − ∑_{j=1}^{r−1} C_{j+1}(x)\frac{u^{j}}{j!} A^{r}(x, u).

Thus,

\frac{(A^{r}(x, u))′_{u}}{A^{r}(x, u)} = \frac{(A(x, u))′_{u}}{A(x, u)} − 1 − ∑_{j=1}^{r−1} C_{j+1}(x)\frac{u^{j}}{j!} .

Integrating by u, we have

ln A^{r}(x, u) = ln A(x, u) − u − ∑_{j=1}^{r−1} C_{j+1}(x)\frac{u^{j+1}}{(j + 1)!} .

Hence

A^{r}(x, u) = A(x, u) exp(−u − ∑_{j=1}^{r−1} C_{j+1}(x)\frac{u^{j+1}}{(j + 1)!} ),

= A(x, u) exp(−u − x ∑_{j=1}^{r−1} A_{j}(x)\frac{u^{j+1}}{(j + 1)!} ).

Corollary 33. For a fixed integer r, the exponential generating function of the excedance distribution over circular r^{+}-cycle permutations has the closed form

C^{r^{+}}(x, u) = ln(A^{r}(x, u)).  (33)

Proof. It follows directly from Equation (12).

Theorem 34. For fixed integers r and k, the exponential generating function of the excedance distribution over (r^{+}, k)-cycle permutations has the closed form

A_{k}^{r}(x, u) = \frac{(ln(A^{r}(x, u)))^{k}}{k!} .  (34)

Proof. A permutation of S_{n}^{r^{+},k} is a product of k disjoint circular r^{+}-cycle permutations. Hence,

A_{n,m,k}^{r} = \frac{1}{k!} ∑_{\begin{matrix}i_{1},...,i_{k}>r \\ i_{1}+···+i_{k}=n \end{matrix}} ∑_{m_{1}+···+m_{k}=m}(i_{1}, …, i_{k})! C_{i_{1},m_{1}} ⋯ C_{i_{k},m_{k}}.

The result follows directly.

Theorem 35. For a fixed integer r, a q-analogue exponential generating function of the r-associated Stirling Eulerian numbers has the closed form

A^{r}(q, x, u) = (A^{r}(x, u))^{q}.  (35)

Proof. From Equation (34), we get

∑_{k} A_{k}^{r}(x, u)q^{k} = ∑_{k} \frac{(ln(A^{r}(x, u)))^{k}}{k!} q^{k} = exp(ln A^{r}(x, u)q),
= (A^{r}(x, u))^{q}.

Theorem 36. For a fixed integer r ≥ 1, the partial differential exponential generating function of the excedance distribution over (r^{+}, ⋆, s)-cycle permutations has the closed form

\frac{∂^{s}[A^{r}(x, u)]_{s}}{∂u^{s}} = x^{s}(A(x, u) − ∑_{n=0}^{r−1} A_{n}(x)\frac{u^{n}}{n!} )^{s}A^{r}(x, u).  (36)

Proof. Let us consider the first s integers and their cycles

[A_{n+s,m}^{r}]_{s} = ∑_{\begin{matrix}i_{1},...,i_{s}≥r \\ i_{1}+···+i_{s}=n \end{matrix}} ∑_{m_{1}+···+m_{t}=m}(i_{1}, …, i_{s})! C_{i_{1}+1,m_{1}} ⋯ C_{i_{s}+1,m_{s}}A_{n−∑_{ℓ=1}^{s} i_{ℓ},m_{t}}^{r}.

We get

[A_{n+s}^{r}(x)]_{s} = ∑_{\begin{matrix}i_{1},...,i_{s}≥r \\ i_{1}+···+i_{s}=n \end{matrix}}(i_{1}, …, i_{s})! x^{s}A_{i_{1}}(x) ⋯ A_{i_{s}}(x)A_{n−∑_{ℓ≥1}^{s} i_{ℓ}}^{r}(x).

We deduce

\frac{∂^{s}A^{r}(x, u)}{∂u^{s}} = x^{s}(A(x, u) − ∑_{n=0}^{r−1} A_{n}(x)\frac{u^{n}}{n!} )^{s}A^{r}(x, u).

Theorem 37. For fixed integers r ≥ 1, k and s, the partial differential exponential generating function of the excedance distribution over (r^{+}, k, s)-cycle permutations has the closed form

\frac{∂^{s}[A_{k}^{r}(x, u)]_{s}}{∂u^{s}} = x^{s}(A(x, u) − ∑_{n=0}^{r−1} A_{n}(x)\frac{u^{n}}{n!} )^{s} \frac{(ln A^{r}(x, u))^{k−s}}{(k − s)!} .  (37)

Proof. A permutation of S_{n+s}^{r^{+},k,s} is a product of k disjoint circular r^{+}-cycle permutations. Considering the first s integers and their cycles, we have

[A_{n+s,m,k}^{r}]_{s} = ∑_{\begin{matrix}i_{1},...,i_{s}≥r \\ i_{1}+···+i_{s}=n \end{matrix}} ∑_{m_{1}+···+m_{t}=m}(i_{1}, …, i_{s})! C_{i_{1}+1,m_{1}} ⋯ C_{i_{s}+1,m_{s}}A_{n−∑_{ℓ=1}^{s} i_{ℓ},m_{t},k−s}^{r}.

The result follows directly.

Theorem 38. For fixed integers r ≥ 1 and s, a partial differential q-analogue exponential generating function of the excedance distribution over (r^{+}, ⋆, s)-cycle permutations has the closed form

\frac{∂^{s}[A^{r}(q, x, u)]_{s}}{∂u^{s}} = q^{s}x^{s}(A(x, u) − ∑_{n=0}^{r−1} A_{n}(x)\frac{u^{n}}{n!} )^{s}(A^{r}(x, u))^{q}.  (38)

Proof. The result follows directly from Equation (37).

The following section contains the corollaries of the previous sections, obtained by setting different values for r and s in the q-analogues. Extensive results are provided for Brenti’s work [3] and for the results of Ksavrelof and Zeng [9]. Various identities are formulated.

6 Excedance distribution by cycle over involutions, permutations and derangements

S_{n}^{0^{+},k}  the set of (0^{+}, k)-cycle permutations
A_{n,m,k}  |{σ ∈ S_{n}^{0^{+},k} : e(σ) = m}|
A_{n,k}(x) ∑_{m} A_{n,m,k}x^{m} = ∑_{σ∈S_{n}^{0^{+},k}} x^{e(σ)}
A_{k}(x, u) ∑_{n} A_{n,k}(x)\frac{u^{n}}{n!}  Cor. 43 Eq. (40)
A(q, x, u) ∑_{n} ∑_{σ∈S_{n}} x^{e(σ)}q^{c(σ)} \frac{u^{n}}{n!} q-analogue of A(x, u) Cor. 44 Eq. (41)
[A(x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{0^{+},⋆,s}} x^{e(σ)} \frac{u^{n}}{n!}  Cor. 45 Eq. (42)

[A_{k}(x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{0^{+},k,s}} x^{e(σ)} \frac{u^{n}}{n!}  Cor. 46 Eq. (43)
[A(q, x, u)]_{s} ∑_{k}[A_{k}(x, u)]_{s}q^{k} q-analogue of [A(x, u)]_{s}  Cor. 47 Eq. (44)

Table 5: Notation.

Corollary 39. A q-analogue exponential generating function of the excedance distribution over 2^{−}-cycle permutations (involutions) has the closed form

A^{2^{−}}(q, x, u) = exp(q(u + xu^{2}/2)).  (39)

Corollary 40. For a fixed integer n, we have

∑_{π∈I_{2n}} x^{e(π)}(q)^{c(π)} = ∑_{j=0}^{n} \frac{(2n)!}{2^{n−k}(2k)! (n − k)!} q^{n+k}x^{n−k},

∑_{π∈I_{2n+1}} x^{e(π)}(q)^{c(π)} = ∑_{j=0}^{n} \frac{(2n + 1)!}{2^{n−k}(2k + 1)! (n − k)!} q^{n+k+1}x^{n−k}.

Corollary 41. A q-analogue exponential generating function of the excedance distribution over 2-cycle permutations (involution derangements) has the closed form

A^{(2)}(q, x, u) = exp(qxu^{2}/2).

Corollary 42. For a fixed integer n, we have

∑_{π∈I_{2n}∩D_{2n}} x^{e(π)}q^{c(π)} = ∑_{j=0}^{n} \frac{(2n)!}{2^{n}n!} q^{n}x^{n}.

Corollary 43. For a fixed integer k, the exponential generating function of the excedance distribution over (0^{+}, k)-cycle permutations has the closed form

A_{k}(x, u) = ∑_{n≥0} ∑_{σ∈S_{n}^{0^{+},k}} x^{e(σ)} \frac{u^{n}}{n!} = \frac{(ln(A(x, u)))^{k}}{k!} .  (40)

Proof. The proof follows from Theorem 34.

Corollary 44 (Brenti). A q-analogue exponential generating function of the excedance distribution by cycle over permutations has the closed form

A(q, x, u) = (A(x, u))^{q}.  (41)

(See [3, Proposition 7.3])

Proof. The proof follows from Theorem 35. Corollary 45. For a fixed integer s, the partial differential exponential generating function of the excedance distribution over (0^{+}, ⋆, s)-cycle permutations has the closed form

\frac{∂^{s}[A(x, u)]_{s}}{∂u^{s}} = (A(x, u) exp(u(x − 1)))^{s}A(x, u).  (42)

Proof. The proof follows from Theorem 36. Corollary 46. For fixed integers k and s, the partial differential exponential generating function of the excedance distribution over (0^{+}, k, s)-cycle permutations has the closed form

\frac{∂^{s}[A_{k}(x, u)]_{s}}{∂u^{s}} = (A(x, u) exp(u(x − 1)))^{s} \frac{(ln A(x, u))^{k−s}}{(k − s)!} .  (43)

Proof. It comes from Theorem 37. Corollary 47. A partial differential q-analogue exponential generating function of the excedance distribution over (0^{+}, ⋆, s)-cycle permutations has the closed form

\frac{∂^{s}[A(q, x, u)]_{s}}{∂u^{s}} = q^{s}(A(x, u) exp(u(x − 1)))^{s}(A(x, u))^{q}.  (44)

Proof. We immediately have the result by multiplying the equation (43) by q^{k} and summing over k. Corollary 48.

∑_{σ∈S_{n+s}^{0^{+},⋆,s}} x^{e(σ)}(−s)^{c(σ)} = (−1)^{s}s^{n+s}(x − 1)^{n}.

Proof. From Corollary 47, we have that

\frac{∂^{s}[A(q, x, u)]_{s}}{∂u^{s}} = q^{s}(A(x, u) exp(u(x − 1)))^{s}(A(x, u))^{q},

setting q = −s, gives

\frac{∂A(−s, x, u)}{∂u} = (−s)^{s}(A(x, u) exp(u(x − 1)))^{s}(A(x, u))^{−s}.

Hence,

\frac{∂^{s}[A(q, x, u)]_{s}}{∂u^{s}} = (−s)^{s} exp(su(x − 1)).  (45)

Identifying the coefficients of \frac{u^{n}}{n!} in Equation (45) gives the desired proof.

Corollary 49.

∑_{σ∈S_{n+s}^{0^{+},⋆,s}} x^{e(σ)}(−s − 1)^{c(σ)} = (−1)^{s}(s + 1)^{s}(xs^{n} − (s + 1)^{n})(x − 1)^{n−1}.

Proof. From Corollary 47, we have

\frac{∂^{s}[A(q, x, u)]_{s}}{∂u^{s}} = q^{s}(A(x, u) exp(u(x − 1)))^{s}(A(x, u))^{q}.

Setting q = −s − 1, we have

\frac{∂^{s}[A(−s − 1, x, u)]_{s}}{∂u^{s}} = (−s − 1)^{s}[A(x, u) exp(u(x − 1))]^{s}(A(x, u))^{−s−1},

= (−s − 1)^{s} \frac{exp(su(x − 1))}{A(x, u)},

= (−s − 1)^{s} \frac{exp(su(x − 1))(x − exp(u(x − 1)))}{x − 1},

= \frac{(−s − 1)^{s}}{x − 1} (x exp(su(x − 1)) − exp((s + 1)u(x − 1))).

Hence,

\frac{∂^{s}[A(−s − 1, x, u)]_{s}}{∂u^{s}} = \frac{(−s − 1)^{s}}{(x − 1)} (x exp(su(x − 1)) − exp((s + 1)u(x − 1))).  (46)

Identifying the coefficients of \frac{u^{n}}{n!} in Equation (46) gives the desired proof.

Remark 50. If we set s = 1 in Corollary 48 and Corollary 49, we get Brenti’s results [3, Corollary 7.4].

∑_{π∈S_{n}} x^{e(π)}(−1)^{c(π)} = −(x − 1)^{n−1},
∑_{π∈S_{n}} x^{e(π)}(−2)^{c(π)} = 2(2^{n−1} − x)(x − 1)^{n−2}.

Corollary 51. A partial differential q-analogue exponential generating function of the excedance distribution over (1^{+}, ⋆, s)-cycle permutations (derangements) has the closed form

\frac{∂^{s}[A^{1}(q, x, u)]_{s}}{∂u^{s}} = q^{s}x^{s}(A(x, u) − 1)^{s}(A(x, u) exp(−u))^{q}.  (47)

Proof. We immediately have the result by setting r = 1 in equation (38).

Corollary 52. For fixed integers n and s, we have

∑_{σ∈S_{n+s}^{1^{+},⋆,s}} x^{e(σ)}(−s)^{c(σ)} = (−1)^{s}(\frac{sx}{x − 1})^{s} ∑_{\begin{matrix}i_{1}≥1,...,i_{s}≥1 \\ i_{1}+···+i_{s}=n \end{matrix}}(i_{1}, …, i_{s})! ∏_{j=1}^{s}(x^{i_{j}} − 1).  (48)

Proof. From Corollary 51 Equation (47), setting q = −s, we have

\frac{∂^{s}[A^{1}(−s, x, u)]_{s}}{∂u^{s}} = (−s)^{s}x^{s}(A(x, u) − 1)^{s}(A^{1}(x, u))^{−s},

= (−s)^{s}x^{s}(\frac{A(x, u) − 1}{A(x, u)})^{s} exp(su),

= (−s)^{s}x^{s}(1 − 1/A(x, u))^{s} exp(su),

= (−s)^{s}x^{s}(1 − \frac{x − exp((x − 1)u)}{x − 1})^{s} exp(su),

= (\frac{−sx}{x − 1})^{s}(− exp(u) + exp(xu))^{s},

= (\frac{−sx}{x − 1})^{s}(∑_{n≥1}(−1 + x^{n})\frac{u^{n}}{n!} )^{s}.

Hence,

\frac{∂^{s}[A^{1}(−s, x, u)]_{s}}{∂u^{s}} = (−1)^{s}(\frac{sx}{x − 1})^{s} ∑_{\begin{matrix}i_{1}≥1,...,i_{s}≥1 \\ i_{1}+···+i_{s}=n \end{matrix}}(i_{1}, …, i_{s})! ∏_{j=1}^{s}(x^{i_{j}} − 1)\frac{u^{n}}{n!} .  (49)

Identifying the coefficients of \frac{u^{n}}{n!} in Equation (49) gives the desired result. Remark 53. If we set s = 1 in Equation (48), we get Ksavrelof and Zeng’s result [9]

∑_{σ∈D_{n}} x^{e(σ)}(−1)^{c(σ)} = −x − x^{2} − ⋯ − x^{n−1}.  (50)

Corollary 54. For fixed integers n and s, we have

∑_{σ∈S_{n+s}^{1^{+},⋆,s}} x^{e(σ)}(−s − 1)^{c(σ)} = (−1)^{s} \frac{(s + 1)^{s}x^{s}}{(x − 1)^{s}} ∑_{ℓ=0}^{n}(\frac{x − x^{ℓ}}{x − 1} ∑_{\begin{matrix}i_{1}≥1,...,i_{s}≥1 \\ i_{1}+···+i_{s}=n−ℓ \end{matrix}}(i_{1}, …, i_{s})! ∏_{j=1}^{s}(x^{i_{j}} − 1)).

Proof. From Corollary 51 Equation (47), setting q = −s − 1, we have

\frac{∂^{s}[A^{1}(−s − 1, x, u)]_{s}}{∂u^{s}} = (−s − 1)^{s}x^{s}(A(x, u) − 1)^{s}(A^{1}(x, u))^{−s−1},

= (−s − 1)^{s}x^{s}(\frac{A(x, u) − 1}{A(x, u)})^{s} exp((s + 1)u)A(x, u)^{−1},

= (−s − 1)^{s}x^{s}(1 − 1/A(x, u))^{s} exp(su)A(x, u)^{−1} exp(u),

= (−s − 1)^{s}x^{s}(1 − \frac{x − exp((x − 1)u)}{x − 1})^{s} exp(su)\frac{x − exp((x − 1)u)}{x − 1}e^{u},

= \frac{(−(s + 1)x)^{s}}{(x − 1)^{s+1}} (− exp(u) + exp(xu))^{s}(x exp(u) − exp(xu)),

= \frac{(−(s + 1)x)^{s}}{(x − 1)^{s}} (∑_{n≥1}(−1 + x^{n})\frac{u^{n}}{n!} )^{s}(∑_{n≥0} \frac{(x − x^{n})}{x − 1} \frac{u^{n}}{n!} ).

Hence,

\frac{∂^{s}[A^{1}(−s − 1, x, u)]_{s}}{∂u^{s}} = (−1)^{s} \frac{(s + 1)^{s}x^{s}}{(x − 1)^{s}} ( ∑_{\begin{matrix}i_{1}≥1,...,i_{s}≥1 \\ i_{1}+···+i_{s}=n \end{matrix}}(i_{1}, …, i_{s})! ∏_{j=1}^{s}(x^{i_{j}} − 1)\frac{u^{n}}{n!} )

(1 + ∑_{n≥1} \frac{(x − x^{n})}{x − 1} \frac{u^{n}}{n!} ),

= (−1)^{s} \frac{(s + 1)^{s}x^{s}}{(x − 1)^{s}} ∑_{n≥0}(∑_{ℓ=0}^{n} \frac{(x − x^{ℓ})}{x − 1}  (51)
( ∑_{\begin{matrix}i_{1}≥1,...,i_{s}≥1 \\ i_{1}+···+i_{s}=n−ℓ \end{matrix}}(i_{1}, …, i_{s})! ∏_{j=1}^{s}(x^{i_{j}} − 1)))\frac{u^{n}}{n!} .  (52)

Identifying the coefficients of \frac{u^{n}}{n!} in Equation (52) gives the desired result.

Corollary 55. For all integer n ≥ 1, we have

∑_{σ∈D_{n}} x^{e(σ)}(−2)^{c(σ)} = \frac{−2x(−2^{n−1}x − 2^{n−1}x^{n−1} + (x + 1)^{n})}{(x − 1)^{2}}.  (53)

Proof. From Corollary 51 Equation (47), setting s = 1 and q = −2, we get

\frac{∂A^{1}(−2, x, u)}{∂u} = −2x(A(x, u) − 1)(A^{1}(x, u))^{−2},

= −2x(A(x, u) − 1) (A(x, u) exp(−u))^{−2} , = −2x (1/A(x, u) − 1/A(x, u)^{2}) exp(2u),

= −2x (\frac{x − exp((x − 1)u)}{x − 1} − \frac{(x − exp((x − 1)u))^{2}}{(x − 1)^{2}} ) exp(2u).

That is,

\frac{∂A^{1}(−2, x, u)}{∂u} = \frac{−2x}{(x − 1)^{2}} (−x exp(2u) − exp (2xu) + (x + 1) exp((x + 1)u)).  (54)

Identifying the coefficients of \frac{u^{n}}{n!} in Equation (54) gives the desired proof.

Remark 56. Note that \frac{−2x(−2^{n−1}x − 2^{n−1}x^{n−1} + (x + 1)^{n})}{(x − 1)^{2}} ∈ ℤ[x]. Below we find a few

values of Equation (53).

1. ∑_{σ∈D_{2}} x^{e(σ)}(−2)^{c(σ)} = −2x.

2. ∑_{σ∈D_{3}} x^{e(σ)}(−2)^{c(σ)} = −2x(x + 1).

3. ∑_{σ∈D_{4}} x^{e(σ)}(−2)^{c(σ)} = −2x(x − 1)^{2}.

4. ∑_{σ∈D_{5}} x^{e(σ)}(−2)^{c(σ)} = −2x(x + 1)(x^{2} − 10x + 1).

7 s-fixed-points-permutations

F_{n}^{s}  the set of s-fixed-points-permutations
F_{n}^{k,s}  the set of s-fixed-points-permutations with k cycles
[F (x, u)]_{s} ∑_{n} ∑_{σ∈F_{n}^{s}} x^{e(σ)} \frac{u^{n}}{n!}  Th. 57 Eq. (55)
[F_{k}(x, u)]_{s} ∑_{n} ∑_{σ∈F_{n}^{k,s}} x^{e(σ)} \frac{u^{n}}{n!}  Th. 58 Eq. (56)
[F (q, x, u)]_{s} ∑_{k}[F_{k}(x, u)]_{s}q^{k} q-analogue of [F (x, u)]_{s}  Th. 59 Eq. (57)

Table 6: Notation.

Theorem 57. A partial differential exponential generating function of the excedance distribution over s-fixed-points-permutations has the closed form

\frac{∂^{s}[F (x, u)]_{s}}{∂u^{s}} = (A(x, u) exp(u(x − 1)))^{s}A(x, u) exp (−u).  (55)

Proof. Since

[F_{n+s,m}]_{s} = ∑_{\begin{matrix}i_{1},...,i_{s}≥0 \\ i_{1}+···+i_{s}=n \end{matrix}}(i_{1}, …, i_{s})! ∑_{m_{1}+···+m_{s}+m_{t}=m} C_{i_{1}+1,m_{1}} ⋯ C_{i_{s}+1,m_{s}}A_{n−∑_{j=1}^{s} i_{j},m_{t}}^{1},

we get

[F_{n+s}(x)]_{s} = ∑_{\begin{matrix}i_{1},...,i_{s}≥0 \\ i_{1}+···+i_{s}=n \end{matrix}}(i_{1}, …, i_{s})! C_{i_{1}+1}(x) ⋯ C_{i_{s}+1}(x)A_{n−∑_{j=1}^{s} i_{j}}^{1}(x).

We deduce

\frac{∂^{s}[F (x, u)]_{s}}{∂u^{s}} = (\frac{∂}{∂u}C(x, u))^{s}A^{1}(x, u),
= (A(x, u) exp (u(x − 1)))^{s}A(x, u) exp(−u).

Theorem 58. Let k ≥ s be fixed integers. The partial differential exponential generating function of the excedance distribution over s-fixed-points-permutations having k cycles has the closed form

\frac{∂^{s}[F_{k}(x, u)]_{s}}{∂u^{s}} = (A(x, u) exp(u(x − 1)))^{s} \frac{(ln (A(x, u) exp (−u)))^{k−s}}{(k − s)!} .  (56)

Proof. Let us consider the first s integers, we have

[F_{n+s,m,k}]_{s} = ∑_{\begin{matrix}i_{1},...,i_{s}≥0 \\ i_{1}+···+i_{s}=n \end{matrix}}(i_{1}, …, i_{s})! ∑_{m_{1}+···+m_{s}+m_{t}=m} C_{i_{1}+1,m_{1}} ⋯ C_{i_{s}+1,m_{s}}A_{n−∑_{l=1}^{s} i_{l},m_{t},k−s}^{1}.

We get

[F_{n+s,m}(x)]_{s} = ∑_{\begin{matrix}i_{1},...,i_{s}≥0 \\ i_{1}+···+i_{s}=n \end{matrix}}(i_{1}, …, i_{s})! C_{i_{1}+1}(x) ⋯ C_{i_{s}+1}(x)A_{n−∑_{l=1}^{s} i_{l},k−s}^{1}(x).

Hence,

\frac{∂^{s}[F_{k}(x, u)]_{s}}{∂u^{s}} = (\frac{∂C(x, u)}{∂u})^{s} A_{k−s}^{1}(x, u),

= (A(x, u) exp(u(x − 1)))^{s} \frac{(ln (A(x, u) exp (−u)))^{k−s}}{(k − s)!} .

Theorem 59. A partial differential q-analogue exponential generating function of the excedance distribution over s-fixed-points-permutations has the closed form

\frac{∂^{s}[F (q, x, u)]_{s}}{∂u^{s}} = q^{s}(A(x, u) exp(u(x − 1)))^{s}(A(x, u))^{q} exp(−qu).  (57)

Proof. We immediately have the result by multiplying by q^{k} and summing over k the right member of Equation (56) .

Corollary 60. For fixed integers n and s, we have

∑_{π∈F_{n}^{s}} x^{e(π)}(−s)^{c(π)} = (−1)^{s}s^{n}x^{n−s}.

Corollary 61. For fixed integers n and s, we have

∑_{π∈F_{n}^{s}} x^{e(π)}(−s − 1)^{c(π)} = (−1)^{s}(s + 1)^{s} \frac{x(sx + 1)^{n−s} − (s + 1)^{n−s}x^{n−s}}{x − 1} .

8 Generalizations

S_{n}^{(r_{1})···(r_{s})}  the set of (r_{1}) ⋯ (r_{s})-cycle permutations
S_{n}^{r_{1}···r_{s}}  the set of r_{1} ⋯ r_{s}-cycle permutations
S_{n}^{r_{1}···r_{s}(r_{s+1})···(r_{ℓ})}  the set of r_{1} ⋯ r_{s}(r_{s+1}) ⋯ (r_{ℓ})-cycle permutations
S_{n}^{r_{1}···r_{s}(r_{s+1})···(r_{ℓ}),k}  {σ ∈ S_{n}^{r_{1}···r_{s}(r_{s+1})···(r_{ℓ})} : c(σ) = k}
S_{n}^{r_{1}^{∗}···r_{ℓ}^{∗}}  the set of r_{1}^{∗} ⋯ r_{ℓ}^{∗}-cycle permutations
[A_{n+s,m,k}^{r_{1}···r_{s}}]_{s}  |{σ ∈ S_{n+s}^{r_{1}···r_{s},⋆,s} : e(σ) = m}|
[A_{n+s,k}^{r_{1}···r_{s}}(x)]_{s}  ∑_{σ∈S_{n+s}^{r_{1}···rs,k,s}} x^{e(σ)}
[A^{r_{1}···r_{s}}(x, u)]_{s}  ∑_{n} ∑_{σ∈S_{n}^{r_{1}···rs}} x^{e(σ)} \frac{u^{n}}{n!}  Th. 62 Eq. (58)
[A_{k}^{r_{1}···r_{s}}(x, u)]_{s}  ∑_{n} ∑_{σ∈S_{n}^{r_{1}···rs},k} x^{e(σ)} \frac{u^{n}}{n!}  Th. 63 Eq. (59)
[A^{r_{1}···r_{s}}(q, x, u)]_{s}  q-analogue of [A^{r_{1}···r_{s}}(x, u)]_{s}  Th. 64 Eq. (60)
A^{(r_{1})···(r_{ℓ})}(x, u)  ∑_{n} ∑_{σ∈S_{n}^{(r_{1})···(r_{ℓ})}} x^{e(σ)}q^{c(σ)} \frac{u^{n}}{n!}  Th. 65 Eq. (61)
[A^{r_{1}···r_{s}(r_{s+1})···(r_{ℓ})}(q, x, u)]_{s} ∑_{n} ∑_{σ∈S_{n}^{r_{1}···rs(r_{s+1})···(r_{ℓ}),⋆,s}} x^{e(σ)}q^{c(σ)} \frac{u^{n}}{n!}  Th. 66 Eq. (62)
A^{r_{1}^{∗}···r_{ℓ}^{∗}}(q, x, u)  ∑_{n} ∑_{σ∈S_{n}^{r^{∗}_{1}···r^{∗}_{ℓ}}} x^{e(σ)}q^{c(σ)} \frac{u^{n}}{n!}  Cor. 67 Eq. (63)

Table 7: Notation.

Theorem 62. For a fixed integer s, the exponential generating function of the excedance distribution over (r_{1} ⋯ r_{s}, ⋆, s)-cycle permutations has the differential closed form

\frac{∂^{s}[A^{r_{1}···r_{s}}(x, u)]_{s}}{∂u^{s}} = x^{s}(A_{r_{1}−1}(x)\frac{u^{r_{1}−1}}{(r_{1} − 1)!} ⋯ A_{r_{s}−1}(x)\frac{u^{r_{s}−1}}{(r_{s} − 1)!} )A(x, u).  (58)

Proof. Consider the first s integers in a permutation in S_{n+s}^{r_{1}···r_{s},⋆,s} and their cycles. We have

[A_{n+s,m}^{r_{1}···r_{s}}]_{s} = \binom{n}{r_{1} − 1, …, r_{s} − 1} ∑_{m_{1}+···+m_{s}+m_{t}=m} C_{r_{1},m_{1}} ⋯ C_{r_{s},m_{s}}A_{n−∑_{ℓ=1}^{s}(r_{ℓ}−1),m_{t}}.

The result follows directly.

Theorem 63. The partial differential exponential generating function of the excedance distribution over (r_{1} ⋯ r_{s}, k, s)-cycle permutations has the differential closed form

\frac{∂^{s}[A_{k}^{r_{1}···r_{s}}(x, u)]_{s}}{∂u^{s}} = x^{s}(A_{r_{1}−1}(x)\frac{u^{r_{1}−1}}{(r_{1} − 1)!} ⋯ A_{r_{s}−1}(x)\frac{u^{r_{s}−1}}{(r_{s} − 1)!} )\frac{(ln A(x, u))^{k−s}}{(k − s)!} . (59)

Proof. Let us consider again the first s integers in permutations of S_{n+s}^{r_{1}···r_{s},k}, we have

[A_{n+s,m,k}^{r_{1}···r_{s}}]_{s} = \binom{n}{r_{1} − 1, …, r_{s} − 1} ∑_{m_{1}+···+m_{s}+m_{t}=m} C_{r_{1},m_{1}} ⋯ C_{r_{s},m_{s}}A_{n−∑_{ℓ=1}^{s}(r_{ℓ}−1),m_{t},k−s}.

The result follows directly.

Theorem 64. For a fixed integer s, a partial differential q−analogue exponential generating function of the excedance distribution over r_{1} ⋯ r_{s}-cycle permutations has the closed form

\frac{∂^{s}[A^{r_{1}···r_{s}}(q, x, u)]_{s}}{∂u^{s}} = q^{s}x^{s}(A_{r_{1}−1}(x)\frac{u^{r_{1}−1}}{(r_{1} − 1)!} ⋯ A_{r_{s}−1}(x)\frac{u^{r_{s}−1}}{(r_{s} − 1)!} )(A(x, u))^{q}. (60)

Proof. We immediately get the result by multiplying by q^{k} and summing over k the right member of Equation (59).

Theorem 65. Let ℓ be a fixed integer. A q-analogue exponential generating function of the excedance distribution over (r_{1}) ⋯ (r_{ℓ})-cycle permutations has the closed form

A^{(r_{1})···(r_{ℓ})}(q, x, u) = exp(qx(A_{r_{1}−1}(x)\frac{u^{r_{1}}}{r_{1}!} + ⋯ + A_{r_{ℓ}−1}(x)\frac{u^{r_{ℓ}}}{r_{ℓ}!} )).  (61)

Proof. A permutation σ in S_{n}^{(r_{1})···(r_{ℓ}),k} is the product of (r_{j}, k_{j})-cycle permutations (j = 1, ⋯, ℓ) such that ∑_{j} k_{j} = k. Thus,

A_{n,m,k}^{(r_{1})···(r_{ℓ})} = ∑_{i_{1}+···+i_{ℓ}=n} ∑_{m_{1}+···+m_{ℓ}=m} ∑_{k_{1}+···+k_{ℓ}=k}(i_{1}, …, i_{ℓ})! A_{i_{1},m_{1},k_{1}}^{(r_{1})} ⋯ A_{i_{ℓ},m_{ℓ},k_{ℓ}}^{(r_{ℓ})}.

It follows that,

A^{(r_{1})···(r_{ℓ})}(q, x, u) = A^{(r_{1})}(q, x, u) ⋯ A^{(r_{ℓ})}(q, x, u),

= exp(qxA_{r_{1}−1}(x)\frac{u^{r_{1}}}{r_{1}!} ) ⋯ exp(qxA_{r_{ℓ}−1}(x)\frac{u^{r_{ℓ}}}{r_{ℓ}!} ).

This gives the result.

Theorem 66. Let ℓ be a fixed integer. Let (r_{1}, …, r_{ℓ}) be the sequence such that r_{i} > 1, i = 1, …, s and 1 < r_{s+1} < ⋯ < r_{ℓ}. A partial differential q-analogue exponential generating function of the excedance distribution over r_{1} ⋯ r_{s}(r_{s+1}) ⋯ (r_{ℓ})-cycle permutations has the closed form

\frac{∂^{s}[A^{r_{1}···r_{s}(r_{s+1})···(r_{ℓ})}(q, x, u)]_{s}}{∂u^{s}} = q^{s}x^{s}(A_{r_{1}−1}(x)\frac{u^{r_{1}−1}}{(r_{1} − 1)!} ⋯
A_{r_{s}−1}(x)\frac{u^{r_{s}−1}}{(r_{s} − 1)!} ) (A^{(r_{s+1})···(r_{ℓ})}(x, u))^{q} .  (62)

Proof. Consider the first s integers.

[A_{n+s,m,k}^{r_{1}···r_{s}(r_{s+1})···(r_{ℓ})}]_{s} = \binom{n}{r_{1} − 1, …, r_{s−1}} ∑_{m_{1}+···+m_{s}+m_{t}=m} C_{r_{1},m_{1}} ⋯ C_{r_{s},m_{s}}×
A_{n−∑_{i=1}^{s} r_{i}−1,m_{t},k−s}^{(r_{s+1})···(r_{ℓ})}.

Therefore, we obtain

\frac{∂^{s}[A^{r_{1}···r_{s}(r_{s+1})···(r_{ℓ})}(q, x, u)]_{s}}{∂u^{s}} = q^{s}C_{r_{1}}(x)\frac{u^{r_{1}−1}}{(r_{1} − 1)!} ⋯ C_{r_{s}}(x)\frac{u^{r_{s}−1}}{(r_{s} − 1)!} ×

(A^{(r_{s+1})···(r_{ℓ})}(x, u))^{q},

= q^{s}x^{s}(A_{r_{1}−1}(x)\frac{u^{r_{1}−1}}{(r_{1} − 1)!} ⋯ A_{r_{s}−1}(x)\frac{u^{r_{s}−1}}{(r_{s} − 1)!} )×

(A^{(r_{s+1})···(r_{ℓ})}(x, u))^{q}.

Corollary 67. For a fixed integer ℓ, let (r_{1}, …, r_{ℓ}) be a sequence such that 1 < r_{1} < ⋯ < r_{ℓ}. A q-analogue exponential generating function of the excedance distribution over r_{1}^{⋆} ⋯ r_{ℓ}^{⋆}-cycle permutations has the closed form

A^{r_{1}^{⋆}···r_{ℓ}^{⋆}}(q, x, u) = A(q, x, u) exp (−qx ∑_{i=1}^{ℓ} A_{r_{i}−1} \frac{u^{r_{i}}}{r_{i}!} ).  (63)

9 Acknowledgment

The authors are very grateful to the anonymous referees for their helpful comments and suggestions.

References

[1] P. Appell, Développements en série entière de (1 + ax)^{1/x}, Arch. Math. Phys. 65 (1880), 171–175.

[2] H. Belbachir and I. E. Bousbaa, Associated Lah numbers and r-Stirling numbers, arxiv preprint arXiv:1404.5573 [math.CO], 2014. Available at https://arxiv.org/

abs/1404.5573.

[3] F. Brenti, A class of q-symmetric functions arising from plethysm, J. Combin. Theory Ser. A 91 (2000), 137–170.

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

[5] L. Carlitz, On some polynomials of Tricomi, Boll. Unione Mat. Ital. 13 (1958), 58–64.

[6] L. Carlitz, Note on Nörlund’s polynomials B_{n}^{(z)}: Proc. Amer. Math. Soc. 11 (1990), 447–451.

[7] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, D. Reidel, 1974.

[8] D. Foata and M. P. Schützenberger, Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, Vol. 138, Springer, 1970.

[9] G. Ksavrelof and J. Zeng, Two involutions for signed excedance numbers, Sém. Lothar. Combin. 49 (2003), B49e.

[10] J. Ma, S. M. Ma, Y. Yeh, and Z. Xu, The cycle descent statistic on permutations, Electron. J. Combin. 23 (2016), #P4.20.

[11] R. Mantaci and F. Rakotondrajao, Exceedingly deranging!, Adv. Appl. Math. 30 (2003), 177–188.

[12] F. Rakotondrajao, k-fixed-points-permutations, INTEGERS 7 (2007), #A36.

[13] J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, 1978.

[14] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[15] F. G. Tricomi, A class of non-orthogonal polynomials related to those of Laguerre, J. Anal. Math. 1 (1951), 209–231.

2020 Mathematics Subject Classification: Primary 05A15; Secondary 05A05, 05A19, 05A30. Keywords: associated Stirling number, excedance, Eulerian number, associated Stirling Eulerian number, generating function, q-analogue. Received September 26 2023; revised versions received April 17 2024; September 2 2024; August 11 2025. Published in Journal of Integer Sequences, September 21 2025. Return to Journal of Integer Sequences home page.