Séminaire Lotharingien de Combinatoire 93 (2025), Article B93b

FACTORIAL EULER–SEIDEL MATRIX: REFINEMENT AND q-ANALOGUE

Dimbiniaina Ratovilebamboavison^{∗}, Mamy Laingo Nomenjanahary Rakotoarison^{⋆}, and Fanja Rakotondrajao^{⋄}

∗ISTRALMA Ambatondrazaka, Université de Toamasina, Toamasina 503, Madagascar

                       Email: ratovilebamboavison@gmail.com

⋆Département de Mathématiques et Informatiques, Université d’Antananarivo, Antananarivo 101, Madagascar

                         Email: rmlnomenjanahary@gmail.com

⋄Département de Mathématiques et Informatiques, Université d’Antananarivo, Antananarivo 101, Madagascar

                             Email: frakoton@yahoo.fr

Abstract. We determine the Riordan matrix associated to Eulerian numbers and establish a formula defining Eulerian polynomials as well. We refine the factorial Euler–Seidel matrix considering the excedance distribution over permutations and derangements. We introduce the so called (n, k)-permutations. Combining with the number of cycles, we establish exponential generating functions and their q-analogues as well.

1. Reminder and introduction

Clarke et al. [2], Dumont and Randrianarivony [4], and Rakotondrajao [9] studied Euler’s difference table (d_{n}^{k})_{n,k≥0}, also called difference factorial numbers, which are given by

(1.1)  \begin{cases}d_{n}^{n} = n!, \\ d_{n}^{k} = d_{n}^{k+1} − d_{n−1}^{k}, & for 1 ≤ k ≤ n − 1. \end{cases}

Their matrix is presented in Table 1.

Table 1. Euler’s difference matrix (d_{n}^{k})_{n,k≥0}
d_{n}^{k}
n\k 0 1 2 3 4 ⋯
0 0!
1  0 1!
2  1 1 2!
3  2 3 4 3!
4  9 11 14 18 4!
⋮  ⋮ ⋮ ⋮ ⋮ ⋮ ...

2020 Mathematics Subject Classification. 05A05; 05A15. Key words and phrases. Excedance distribution; Euler–Seidel matrix; Eulerian polynomial; Riordan matrix;

q-analogue; generating function.

Dumont [5] reintroduced the Euler–Seidel matrix associated to a given sequence (a_{n})_{n≥0}. It is an infinite matrix and is determined recursively by the formula

(1.2)  \begin{cases}a_{n}^{0} = a_{n}, & for n ≥ 0, \\ a_{n}^{k} = a_{n}^{k−1} + a_{n+1}^{k−1}, & for n ≥ 0, k ≥ 1. \end{cases}

The sequence (a_{n}^{0})_{n≥0} is called the initial sequence, and (a_{0}^{n})_{n≥0} is called the final sequence.

Theorem 1.1 (Dumont [5]). The relation between any entry and the initial sequence is determined by

(1.3)  a_{n}^{k} = ∑_{i=0}^{k} \binom{k}{i}a_{n+i}^{0}, for n ≥ 0, k ≥ 0.

Firengiz and Dil [6] reconsidered the Euler–Seidel matrix, by introducing the parameters p and q as follows:

a_{n}^{k} = a_{n}^{k}(p, q)

= p a_{n}^{k−1} + q a_{n+1}^{k−1}, for n ≥ 0, k ≥ 1. (1.4)

Theorem 1.2 (Firengiz and Dil [6]). The relation between any entry and the initial sequence is determined by

(1.5)  a_{n}^{k} = ∑_{i=0}^{k} \binom{k}{i}p^{k−i}q^{i}a_{n+i}^{0}.

Theorem 1.3 (Firengiz and Dil [6]). The exponential generating function of (a_{n}^{k})_{k,n≥0} has the closed form

(1.6)  ∑_{n≥0} ∑_{k≥0} a_{n}^{k} \frac{u^{k}}{k!} \frac{t^{n}}{n!} = exp(pu) A(t + qu), where A(t) = ∑_{n≥0} a_{n}^{0} \frac{t^{n}}{n!}.

We study the factorial Euler–Seidel matrix deduced from Euler’s difference table as follows. The initial sequence is (n!)_{n≥0}, and the infinite matrix is determined recursively by

(1.7)  \begin{cases}a_{n}^{0} = n!, \\ a_{n}^{k} = −a_{n}^{k−1} + a_{n+1}^{k−1}, for n ≥ 0, k ≥ 1. \end{cases}

Definition 1.1 (Shapiro [12], Sprugnoli [14]). Consider an infinite matrix R = (r_{n,k})_{n,k≥0} with complex coefficients and two formal power series g(x) = ∑_{k=0}^{∞} g_{k}x^{k}, f(x) = ∑_{k=1}^{∞} f_{k}x^{k} with g_{0} = 1, f_{1} ≠ 0. Let R_{k}(x) = ∑_{n=0}^{∞} r_{n,k}x^{n} be the formal power series of the k-th column of R. Then R is called a Riordan matrix if

(1.8)  R_{k}(x) = g(x)[f(x)]^{k}.

R is an infinite lower-triangular matrix which we denote by a pair R = (g(x), f(x)). Note that the identity I = (1, x) is a Riordan matrix.

Remark 1.1. If we have g(x) = ∑_{k=0}^{∞} g_{k} \frac{x^{k}}{k!} and f(x) = ∑_{k=1}^{∞} f_{k} \frac{x^{k}}{k!} , with g_{0} = 1 and f_{1} ≠ 0, then

R_{k}(x) = g(x)^{\frac{[f(x)]^{k}}{k!}} . We denote the matrix by R = [g(x), f(x)].

FACTORIAL EULER–SEIDEL MATRIX: REFINEMENT AND q-ANALOGUE 3

Theorem 1.4 (Shapiro [12], Shapiro et al. [13]). Let (a_{n})_{n≥0} and (b_{n})_{n≥0} be two sequences. Set a(x) = ∑_{k=0}^{∞} a_{k}x^{k} and b(x) = ∑_{k=0}^{∞} b_{k}x^{k}. Then we have

(1.9)  (g(x), f(x)) [a_{0} ; a_{1} ; a_{2} ; ⋮] = [b_{0} ; b_{1} ; b_{2} ; ⋮] ⟺ g(x)a(f(x)) = b(x).

Theorem 1.5 (Shapiro [12], Shapiro et al. [13]). For any Riordan matrix (g(x), f(x)), its inverse R^{−1} is given by

R^{−1} = (g(x), f(x))^{−1}

= (\frac{1}{g(f̄(x))}, f̄(x)) , (1.10)

where f̄(f(x)) = f(f̄(x)) = x.

Let us write [n] = {1, 2, …, n}. We say that an integer i ∈ [n] is a fixed point for a permutation σ if σ(i) = i. We denote by FIX(σ) the set of fixed points of σ. A derangement is a permutation without fixed points, that is, a permutation σ such that FIX(σ) = ∅. We denote by D_{n} the set of all derangements of the symmetric group S_{n}. We say that a permutation σ is an (n, k)-permutation if the length of σ is equal to (n + k) and FIX(σ) ⊂ [n].

This class of (n, k)-permutations should not be confused with the ”n-fixed-points-permutations” introduced by Rakotondrajao [10]. An n-fixed-points-permutation is an (n, k)-permutation. For example, (1)(2, 3)(4)(5, 6) is a (4, 2)-permutation, but it is not a 4-fixed-points-permutation.

We denote by E_{n}^{k} the set of (n, k)-permutations. Note that the coefficient of the n-th column and k-th row of the classical Euler–Seidel matrix is the cardinality of E_{n}^{k}. Since n + 1 is either a fixed point or not for a permutation σ ∈ E_{n+1}^{k}: if n + 1 is, then σ ∈ E_{n}^{k}; otherwise σ ∈ E_{n}^{k+1}.

We say that an integer i is an excedance for σ if σ(i) > i. We denote the number of excedances by e(σ) and the number of cycles of σ by c(σ). The numbers E_{n,k} count the number of permutations of size n having k excedances. They are given by the formula

(1.11)  E_{n,k} = \begin{cases}1, & if n = 0, k = 0, \\ (n − k)E_{n−1,k−1} + (k + 1)E_{n−1,k}, & if 0 < k ≤ n, \\ 0, & otherwise. \end{cases}

The Eulerian numbers E_{n,k} are classical numbers in mathematics. They can be found in many places in the literature (Brenti [1], Comtet [3], Foata and Schützenberger [7], Roselle [11], Stanley [15], Worpitzky [16]).

We are interested in refining the factorial Euler–Seidel matrix using the excedance distribution over permutations. The Eulerian polynomials E_{n}(x) = ∑_{i=0}^{n} E_{n,i}x^{i} = ∑_{i≥0} E_{n,i}x^{i} become the initial sequence. We have

(1.12)  \begin{cases}e_{n}^{0}(x) = E_{n}(x), & for n ≥ 0, \\ e_{n}^{k}(x) = −e_{n}^{k−1}(x) + e_{n+1}^{k−1}(x), & for n ≥ 0, k ≥ 1, \end{cases}

and their matrix is presented in Table 2.

Table 2. Refined factorial Euler–Seidel matrix

e_{n}^{k}(x)
k\n 0  1  2  3  ⋯
0  1  1  1 + x 1 + 4x + x^{2} ⋯
1  0  x  3x + x^{2}  ⋯  ⋯
2  x 2x + x^{2} ⋯  ⋯  ⋯
3 x + x^{2} ⋯  ⋯  ⋯  ⋯
⋮  ⋮  ⋮  ⋮  ⋮  ...

The Hurwitz generating function of the classical Eulerian polynomials [7] is

E(x, t) = ∑_{n≥0} ∑_{k≥0} E_{n,k}x^{k} \frac{t^{n}}{n!}

= \frac{x − 1}{x − exp (t(x − 1))}. (1.13)

We define the q-analogue of the refined factorial Euler–Seidel matrix combining the excedance distribution and the number of cycles. We write

(1.14)  e_{n}^{k}(x) = ∑_{σ∈E_{n}^{k}} x^{e(σ)},

(1.15)  e_{n}^{k}(x, q) = ∑_{σ∈E_{n}^{k}} x^{e(σ)} q^{c(σ)}.

Mantaci and Rakotondrajao [8] extensively studied the excedance distribution over derangements. The number a_{n,k} counts derangements over [n] having k excedances,

(1.16)  a_{n,k} = |{δ ∈ D_{n} | δ has k excedances}|.

Let us write A_{k}(x) = ∑_{i=0}^{k} a_{k,i}x^{i}, and let A_{k}(x, q) be its q-analogue.

Remark 1.2. Note that a derangement of D_{n} is a (0, n)-permutation, and a permutation of S_{n} is a (n, 0)-permutation.

Let us denote by E_{n}(x, q) the q-analogue of the Eulerian polynomials E_{n}(x) = ∑_{i=0}^{n} E_{n,i}x^{i} given by

(1.17)  E_{n}(x, q) = ∑_{σ∈S_{n}} x^{e(σ)}q^{c(σ)}.

Theorem 1.6 (Brenti [1]). The polynomials E_{n}(x, q) satisfy the recursion relation

(1.18)  E_{n}(x, q) = (x(n − 1) + q) E_{n−1}(x, q) + x(1 − x)\frac{d}{dx}E_{n−1}(x, q)

with initial condition E_{0}(x, q) = 1.

Theorem 1.7 (Brenti [1]). The exponential generating function of E_{n}(x, q) is given by

(1.19)  E(x, t, q) = ∑_{n≥0} \frac{E_{n}(x, q)}{n!}t^{n} = (\frac{x − 1}{x − exp (t(x − 1))})^{q} , E_{0}(x, q) = 1.

FACTORIAL EULER–SEIDEL MATRIX: REFINEMENT AND q-ANALOGUE 5

2. Riordan matrix representation of Worpitzky identity

For a fixed integer n with n ≥ 0, let us consider the infinite matrix R_{n} = (r_{k,ℓ}^{(n)})_{k,ℓ≥0} given by

(2.1)  R_{n} = (\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 2^{n} & 1 & 0 & 0 & 0 & ⋯ \\ 3^{n} & 2^{n} & 1 & 0 & 0 & ⋯ \\ 4^{n} & 3^{n} & 2^{n} & 1 & 0 & ⋯ \\ 5^{n} & 4^{n} & 3^{n} & 2^{n} & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Theorem 2.1. R_{n} is a Riordan matrix and

(2.2)  R_{n} = (\frac{E_{n}(x)}{(1 − x)^{n+1}} , x) .

Its inverse R_{n}^{−1} is given by

(2.3)  R_{n}^{−1} = (\frac{(1 − x)^{n+1}}{E_{n}(x)} , x) .

Proof. We have

\frac{E_{n}(x)}{(1 − x)^{n+1}} = ∑_{k≥0}(k + 1)^{n}x^{k}.

Let U = R_{n}. If U = (g(x), f(x)), from Definition 1.1, we have Equation (2.2), that is

\{ U_{0}(x) = g(x) = \frac{E_{n}(x)}{(1−x)^{n+1}} , ; U_{1}(x) = g(x)f(x) = x\frac{E_{n}(x)}{(1−x)^{n+1}} , ; ⋮ ; U_{i}(x) = g(x) (f(x))^{i} = x^{i} \frac{E_{n}(x)}{(1−x)^{n+1}} , ; ⋮

Then U^{−1} = (\frac{(1−x)^{n+1}}{E_{n}(x)} , x) = R_{n}^{−1} (cf. Theorem 1.5). □

For a fixed integer n with n ≥ 0, let us consider the Eulerian number vector E_{n} and the signed binomial coefficient vector B_{n} given by

E_{n} = [ E_{n,0} ; E_{n,1} ; ⋮ ; E_{n,n+1}] and B_{n} = [ 1 ; −\binom{n+1}{1} ; ⋮ ; (−1)^{i}\binom{n+1}{i} ; ⋮ ; (−1)^{n+1}\binom{n+1}{n+1}] .

Theorem 2.2. For a fixed integer n with n ≥ 0, we have

(2.4)  [ E_{n,0} ; E_{n,1} ; E_{n,2} ; E_{n,3} ; E_{n,4} ; ⋮ ] = (\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 2^{n} & 1 & 0 & 0 & 0 & ⋯ \\ 3^{n} & 2^{n} & 1 & 0 & 0 & ⋯ \\ 4^{n} & 3^{n} & 2^{n} & 1 & 0 & ⋯ \\ 5^{n} & 4^{n} & 3^{n} & 2^{n} & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) [ 1 ; −\binom{n+1}{1} ; \binom{n+1}{2} ; −\binom{n+1}{3} ; \binom{n+1}{4} ; ⋮ ] .

Proof. Equation (2.4) is a matrix representation of the Worpitzky [16] formula

{□ \atop (2.5)} E_{n,k} = ∑_{i=0}^{k}(−1)^{i} (k + 1 − i)^{n}\binom{n + 1}{i}.

Theorem 2.3. Let us consider the infinite matrix R = (r_{k,ℓ})_{k,ℓ≥0} given by

r_{k,ℓ} = \begin{cases}(k − ℓ + 1)^{p}, & if k ≥ ℓ and \frac{2+(5+p)p}{2} ≥ k ≥ \frac{(3+p)p}{2}, \\ 0, & otherwise, \end{cases} with p = ⌊\frac{−3 + \sqrt{9 + 8ℓ}}{2}⌋ .

We have

(2.6)  (\begin{matrix}E_{0} \\ & E_{1} & & 0 \\ & & E_{2} \\ & 0 & & E_{3} \\ & & & & . & . & . \end{matrix}) = R (\begin{matrix}B_{0} \\ & B_{1} & & 0 \\ & & B_{2} \\ & 0 & & B_{3} \\ & & & & . & . & . \end{matrix}) .

Proof. For a fixed integer n with n ≥ 0, let us consider the matrix R̄_{n} = (r̄_{k,ℓ}^{(n)})_{k,ℓ≥0} of the first (n + 2) rows and (n + 2) columns extracted from R_{n} in Equation (2.1), that is,

R̄_{n} = (\begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ 2^{n} & 1 & 0 & ⋯ & 0 \\ 3^{n} & 2^{n} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ (n + 2)^{n} & (n + 1)^{n} & n^{n} & ⋯ & 1 \end{matrix}) .

From Theorem 2.2, we have E_{n} = R̄_{n} B_{n}. Hence, we have

(\begin{matrix}E_{0} \\ & E_{1} & & 0 \\ & & E_{2} \\ & 0 & & E_{3} \\ & & & & . & . & . \end{matrix}) = (R̄_{0} ; R̄_{1}  0 ; R̄_{2} ; 0  R̄_{3} ; ...) (\begin{matrix}B_{0} \\ & B_{1} & & 0 \\ & & B_{2} \\ & 0 & & B_{3} \\ & & & & . & . & . \end{matrix}) .

FACTORIAL EULER–SEIDEL MATRIX: REFINEMENT AND q-ANALOGUE 7

That is,

( \begin{matrix}\begin{matrix}E_{0,0} \\ 0 \end{matrix} & 0 & ⋯ \\ 0 & \begin{matrix}E_{1,0} \\ E_{1,1} \\ 0 \end{matrix} & ⋯ \\ ⋮ & ⋮ & ... \end{matrix}) = ( \begin{matrix}1 0 1 1 & 0 & ⋯ \\ 0 & 1 0 0 2 1 0 3 2 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix}) ( \begin{matrix}\begin{matrix}( & {1 \atop 0} & ) \\ −\binom{1}{1} \end{matrix} & 0 & ⋯ \\ 0 & \begin{matrix}( & {2 \atop 0} & ) \\ −\binom{2}{1} \\ ( & {2 \atop 2} & ) \end{matrix} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

Identifying the coefficients, we get

r_{k,ℓ} = \begin{cases}(k − ℓ + 1)^{p}, & if k ≥ ℓ and \frac{2+(5+p)p}{2} ≥ k ≥ \frac{(3+p)p}{2}, \\ 0, & otherwise, \end{cases} with p = ⌊\frac{−3 + \sqrt{9 + 8ℓ}}{2}⌋ . □

3. Refined factorial Euler–Seidel matrix and q-analogue

Let us consider the refined factorial Euler–Seidel matrix coefficient e_{n}^{k}(x). Theorem 3.1. For any integers n ≥ 0 and k ≥ 0, we have

(3.1)  e_{n}^{k}(x) = ∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}E_{n+i}(x).

Proof. Setting p = −1 and q = 1 in Theorem 1.2, we get

e_{n}^{k}(x) = ∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}e_{n+i}^{0}(x)
= ∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}E_{n+i}(x).  □

Corollary 3.1. For any integer k ≥ 0, we have

(3.2)  e_{0}^{k}(x) = ∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}E_{i}(x).

Proof. Set n = 0 in Theorem 3.1. □ Remark 3.1. We have e_{0}^{k}(x) = A_{k}(x) = ∑_{i=0}^{k} a_{k,i}x^{i}. Theorem 3.2. The polynomial e_{n}^{k}(x) is the polynomial of the excedance distribution over E_{n}^{k}. Proof. From the construction of set E_{n+1}^{k−1}, we have

e_{n+1}^{k−1}(x) = e_{n}^{k}(x) + e_{n}^{k−1}(x).

This follows from the interpretation of e_{n}^{k}(x) as the excedance distribution over E_{n+1}^{k−1} where n + 1 is not a fixed point, and e_{n}^{k−1}(x) as the excedance distribution over E_{n+1}^{k−1} where n + 1 is a fixed point (Equation (1.14)). □ Theorem 3.3. The exponential generating function of e_{n}^{k}(x) has the closed form

(3.3)  F (x, u, t) = ∑_{n≥0} ∑_{k≥0} e_{n}^{k}(x)\frac{u^{k}}{k!} \frac{t^{n}}{n!} = \frac{(x − 1) exp(−u)}{x − exp ((t + u)(x − 1))}.

8 D. RATOVILEBAMBOAVISON, M. L. N. RAKOTOARISON AND F. RAKOTONDRAJAO

Proof. From Equation (1.12) and Theorem 1.3, we have

∑_{n≥0} ∑_{k≥0} e_{n}^{k}(x)\frac{u^{k}}{k!} \frac{t^{n}}{n!} = exp(−u) ∑_{n≥0} E_{n}(x)\frac{(t + u)^{n}}{n!} .

From Equation (1.13), we have

∑_{n≥0} E_{n}(x)\frac{t^{n}}{n!} = \frac{x − 1}{x − exp (t(x − 1))}.

Hence,

∑_{n≥0} ∑_{k≥0} e_{n}^{k}(x)\frac{u^{k}}{k!} \frac{t^{n}}{n!} = \frac{(x − 1) exp(−u)}{x − exp ((t + u)(x − 1))}.  □

Corollary 3.2. The exponential generating function of A_{k}(x) has the closed form

(3.4)  A(x, u) = F (x, u, 0) = \frac{(x − 1) exp(−u)}{x − exp (u(x − 1))}.

Moreover, we can express the initial sequence (e_{n}^{0}(x))_{n≥0} as an infinite matrix. The coefficient [x^{ℓ}]e_{n}^{0}(x) is the classical Eulerian number E_{n,ℓ}, and Equation (1.12) becomes

[x^{ℓ}]e_{n}^{k}(x) = −[x^{ℓ}]e_{n}^{k−1}(x) + [x^{ℓ}]e_{n+1}^{k−1}(x).

That is,

(3.5)  \begin{cases}[x^{ℓ}]e_{n}^{0}(x) = E_{n,ℓ}, & for n ≥ 0, \\ [x^{ℓ}]e_{n}^{k}(x) = −[x^{ℓ}]e_{n}^{k−1}(x) + [x^{ℓ}]e_{n+1}^{k−1}(x), & for n ≥ 0, k ≥ 1. \end{cases}

Theorem 3.4. For fixed integers k and ℓ, the coefficient of x^{ℓ} in e_{0}^{k}(x) is

(3.6)  [x^{ℓ}]e_{0}^{k}(x) = a_{k,ℓ} = ∑_{i=0}^{k}(−1)^{k−i}\binom{k}{i}E_{i,ℓ}, for k ≥ 0 and l ≥ 0.

Proof. We have

a_{k,ℓ} = [x^{ℓ}]e_{0}^{k}(x)

= ∑_{i=0}^{k} \binom{k}{i}(−1)^{k−i} ([x^{ℓ}]e_{i}^{0}(x)) ,

= ∑_{i=0}^{k} \binom{k}{i}(−1)^{k−i}E(i, ℓ).

Here, we obtained the second line by setting p = −1 and q = 1 in Equation (1.5). □ Theorem 3.5. We have

(3.7) (\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 1 & 0 & 0 & ⋯ \\ 0 & 1 & 7 & 1 & 0 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ −1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & −2 & 1 & 0 & 0 & ⋯ \\ −1 & 3 & −3 & 1 & 0 & ⋯ \\ 1 & −4 & 6 & −4 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) (\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 4 & 1 & 0 & 0 & ⋯ \\ 1 & 11 & 11 & 1 & 0 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

FACTORIAL EULER–SEIDEL MATRIX: REFINEMENT AND q-ANALOGUE 9

That is,

(3.8)  (a_{k,ℓ})_{k,ℓ≥0} = [ exp(−t), t] (E_{n,ℓ})_{n,ℓ≥0} ,

with S = [ exp(−t), t] the Riordan matrix associated to the refined factorial Euler–Seidel matrix. Theorem 3.6. For all integers k ≥ 0 and l ≥ 0, we have

(3.9)  a_{k,ℓ} = ∑_{i=0}^{k} ∑_{j=0}^{ℓ}(−1)^{k−i+j}\binom{k}{i}\binom{i + 1}{j}(ℓ + 1 − j)^{i}, for k ≥ 0, ℓ ≥ 0.

Proof. Using the Worpitzky identity in Equation (2.5) with n = i and k = ℓ and Theorem 3.4, we have

a_{k,ℓ} = ∑_{i=0}^{k} \binom{k}{i}(−1)^{k−i} ∑_{j=0}^{ℓ} ((−1)^{j}(ℓ + 1 − j)^{i}) \binom{i + 1}{j}
= ∑_{i=0}^{k} ∑_{j=0}^{ℓ}(−1)^{k−i+j}\binom{k}{i}\binom{i + 1}{j}(ℓ + 1 − j)^{i}.  □

Theorem 3.7. We have

(3.10)  (\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 4 & 1 & 0 & 0 & ⋯ \\ 1 & 11 & 11 & 1 & 0 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) = (\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & 0 & ⋯ \\ 1 & 2 & 1 & 0 & 0 & ⋯ \\ 1 & 3 & 3 & 1 & 0 & ⋯ \\ 1 & 4 & 6 & 4 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) (\begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 0 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 0 & 0 & 0 & ⋯ \\ 0 & 1 & 1 & 0 & 0 & ⋯ \\ 0 & 1 & 7 & 1 & 0 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}) .

That is,

(3.11)  (E_{k,ℓ})_{k,ℓ≥0} = [ exp(t), t] (a_{n,ℓ})_{n,ℓ≥0} , with [ exp(t), t] = S^{−1}.

Proof. This is obtained from Equation (3.8) and Theorem 1.5. □ Corollary 3.3. We have

(3.12)  (E_{k,ℓ})_{k,ℓ≥0} = (\binom{k}{n})_{k,n≥0} (a_{n,ℓ})_{n,ℓ≥0} .

Corollary 3.4. For a fixed integer ℓ ≥ 0, the sequence (E(n, ℓ))_{n≥0} of a row of the Eulerian number matrix is given by

(3.13)  [E_{0,ℓ} ; E_{1,ℓ} ; E_{2,ℓ} ; E_{3,ℓ} ; E_{4,ℓ} ; ⋮] = [ exp(t), t] [a_{0,ℓ} ; a_{1,ℓ} ; a_{2,ℓ} ; a_{3,ℓ} ; a_{4,ℓ} ; ⋮] .

Theorem 3.8. The Euler–Seidel matrix preserves the excedance distribution.

Proof. This process is derived from the construction of the (n + 1, k − 1)-permutation. Consider first the case where n + 1 is a fixed point. By removing n + 1 from the permutation and reordering the sequence, that is, decreasing by 1 all integers greater than n + 1 in the remaining permutation, we obtain an (n, k − 1)-permutation. Conversly, if n + 1 is not a fixed point, then the (n + 1, k − 1)-permutation is, by definition, an (n, k)-permutation. This construction leads directly to the recurrence relation

e_{n}^{k}(x) = −e_{n}^{k−1}(x) + e_{n+1}^{k−1}(x).  □

Theorem 3.9. For a fixed integer ℓ ≥ 0, the exponential generating function of [x^{ℓ}]e_{n}^{k}(x), that is, the exponential generating function of all (n, k)-permutations with ℓ excedances, is given by

e_{ℓ}(t, u) = ∑_{n≥0} ∑_{k≥0}[x^{ℓ}]e_{n}^{k}(x)\frac{u^{k}}{k!} \frac{t^{n}}{n!}

= ∑_{i=0}^{ℓ} \frac{(−1)^{i}}{i!} ((ℓ − i + 1)(t + u))^{i−1}((ℓ − i + 1)(t + u) + i) exp (t + (ℓ − i)(t + u)). (3.14)

Proof. For fixed integers ℓ and n, from the Worpitzky identity in Equation (2.5), we consider the initial term of the sequence

E_{n,ℓ} = ∑_{i=0}^{ℓ}(−1)^{i}(ℓ + 1 − i)^{n}\binom{n + 1}{i}.

Hence,

∑_{n≥0} E_{n,ℓ} \frac{t^{n}}{n!} = ∑_{n≥i−1} ∑_{i=0}^{ℓ}(−1)^{i}(ℓ + 1 − i)^{n} \frac{(n + 1)t^{n}}{(n − i + 1)! i!}

= ∑_{i=0}^{ℓ} [ ∑_{n≥i} \frac{(−1)^{i}}{i!} \frac{((ℓ + 1 − i) t)^{n−i+1}}{(n − i)!}

+ ∑_{n≥i−1} \frac{(−1)^{i} i}{i!} \frac{((ℓ + 1 − i) t)^{n−i+1}}{(n − i + 1)!} ](t(ℓ + 1 − i))^{i−1}

= ∑_{i=0}^{ℓ} \frac{(−1)^{i}}{i!} (t(ℓ + 1 − i))^{i−1}(t (ℓ + 1 − i) + i) exp (t(ℓ + 1 − i))

= ∑_{i=0}^{ℓ} \frac{(−1)^{i}}{i!} (t(ℓ + 1 − i))^{i−1}(t (ℓ + 1) + i(1 − t)) exp (t (ℓ + 1 − i)). (3.15)

From Equations (1.6) and (3.5), setting p = −1 and q = 1, we obtain

∑_{n≥0} ∑_{k≥0}[x^{ℓ}]e_{n}^{k}(x)\frac{u^{k}}{k!} \frac{t^{n}}{n!} = exp(−u) ∑_{n≥0} E_{n,ℓ} \frac{(t + u)^{n}}{n!} .

By Equation (3.15), we have

∑_{n≥0} ∑_{k≥0}[x^{ℓ}]e_{n}^{k}(x)\frac{u^{k}}{k!} \frac{t^{n}}{n!} = exp(−u) ∑_{i=0}^{ℓ} \frac{(−1)^{i}}{i!} ((ℓ + 1 − i)(t + u))^{i−1}

· ((t + u)(ℓ + 1) + i(1 − t − u)) exp ((ℓ + 1 − i)(t + u))

= ∑_{i=0}^{ℓ} \frac{(−1)^{i}}{i!} ((ℓ + 1 − i)(t + u))^{i−1}((t + u)(ℓ + 1) + i(1 − t − u))

· exp (t(ℓ + 1 − i) + u(ℓ − i)).  □

Corollary 3.5. For a fixed integer ℓ ≥ 0, the exponential generating function a_{ℓ}(u) = ∑_{k≥0} a_{k,ℓ} \frac{u^{k}}{k!} of derangements with ℓ excedances has the closed form

(3.16)  a_{ℓ}(u) = ∑_{i=0}^{ℓ} \frac{(−1)^{i}}{i!} (u(ℓ − i + 1))^{i−1}(u(ℓ − i + 1) + i) exp (u(ℓ − i)).

Proof. Setting t = 0 in Equation (3.14), we get a_{ℓ}(u) = e_{ℓ}(0, u). □

Corollary 3.6. For a fixed integer ℓ ≥ 0, the exponential generating function e_{ℓ}(t) = ∑_{n≥0} E_{n,ℓ} \frac{t^{n}}{n!} of permutations with ℓ excedances has the closed form

(3.17)  e_{ℓ}(t) = ∑_{i=0}^{ℓ} \frac{(−1)^{i}}{i!} (t(ℓ − i + 1))^{i−1}(t(ℓ − i + 1) + i) exp (t(ℓ − i + 1)).

Proof. Setting u = 0 in Equation (3.14), we get e_{ℓ}(t) = e_{ℓ}(t, 0). □

Theorem 3.10. The q-analogue of the refined factorial Euler–Seidel matrix (e_{n}^{k}(x))_{k,n≥0} is determined by the formula

(3.18)  e_{n}^{k}(x, q) = −q e_{n}^{k−1}(x, q) + e_{n+1}^{k−1}(x, q).

Proof. From the construction of (n + 1, k + 1)-permutations, we distinguish whether the integer (n + 1) is a fixed point or not. By doing the corresponding case analysis, we get the result. □

Theorem 3.11. We have

(3.19)  e_{n}^{k}(x, q) = ∑_{i=0}^{k}(−q)^{k−i}\binom{k}{i}E_{n+i}(x, q).

Proof. From Equation (3.18) and Theorem 1.2, we get the result. □

Theorem 3.12. We have

(3.20)  [e_{n}^{0}(x, q) ; e_{n}^{1}(x, q) ; e_{n}^{2}(x, q) ; e_{n}^{3}(x, q) ; e_{n}^{4}(x, q) ; ⋮] = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ −q & 1 & 0 & 0 & 0 & ⋯ \\ q^{2} & −2q & 1 & 0 & 0 & ⋯ \\ −q^{3} & 3q^{2} & −3q & 1 & 0 & ⋯ \\ q^{4} & −4q^{3} & 6q^{2} & −4q & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) [ E_{n}(x, q) ; E_{n+1}(x, q) ; E_{n+2}(x, q) ; E_{n+3}(x, q) ; E_{n+4}(x, q) ; ⋮] .

That is,

(3.21)  [e_{n}^{k}(x, q)]_{k≥0} = [exp(−qt), t] [E_{n+k}(x, q)]_{k≥0} .

Proof. Equation (3.20) follows from Equation (3.19). □

Theorem 3.13. The matrix T given by

(3.22)  T = [exp(−qt), t] = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ −q & 1 & 0 & 0 & 0 & ⋯ \\ q^{2} & −2q & 1 & 0 & 0 & ⋯ \\ −q^{3} & 3q^{2} & −3q & 1 & 0 & ⋯ \\ q^{4} & −4q^{3} & 6q^{2} & −4q & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

is the q-analogue of [exp(−t), t]. Proof. We have

∑_{ℓ≥0}(−q)^{ℓ} \frac{t^{ℓ}}{ℓ!} = exp(−qt).

If T = [g(t), f(t)], from Definition 1.1, we have Equation (3.22), that is,

{ T_{0}(t) = g(t) = exp(−qt), ; T_{1}(t) = g(t)f(t) = tg(t), ; ⋮ ; T_{i}(t) = g(t) (f(t))^{i} = t^{i}g(t), ; ⋮  □

Remark 3.2. T^{−1} = [exp(qt), t] is the q-analogue of the inverse Riordan matrix of T. Theorem 3.14. We have

(3.23)  [e_{0}^{k}(x, q) ; e_{1}^{k}(x, q) ; e_{2}^{k}(x, q) ; e_{3}^{k}(x, q) ; e_{4}^{k}(x, q) ; ⋮] = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ q & 1 & 0 & 0 & 0 & ⋯ \\ q^{2} & 2q & 1 & 0 & 0 & ⋯ \\ q^{3} & 3q^{2} & 3q & 1 & 0 & ⋯ \\ q^{4} & 4q^{3} & 6q^{2} & 4q & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) [ A_{k}(x, q) ; A_{k+1}(x, q) ; A_{k+2}(x, q) ; A_{k+3}(x, q) ; A_{k+4}(x, q) ; ⋮] .

That is,

(3.24)  [e_{n}^{k}(x, q)]_{n≥0} = [exp(qt), t] [A_{k+n}(x, q)]_{n≥0} , with [exp(qt), t] = T^{−1}.

Proof. From Equation (3.18), we get

e_{n+1}^{k−1}(x, q) = q e_{n}^{k−1}(x, q) + e_{n}^{k}(x, q).

Let us consider b_{k}^{n}(x, q) = e_{n+1}^{k−1}(x, q). Then

b_{k}^{n}(x, q) = q b_{k}^{n−1}(x, q) + b_{k+1}^{n−1}(x, q) and b_{k}^{0} = A_{k}(x, q).

Combining this with Theorem 1.2, we get the result. □ Theorem 3.15. We have

(3.25)  [E_{0}(x, q) ; E_{1}(x, q) ; E_{2}(x, q) ; E_{3}(x, q) ; E_{4}(x, q) ; ⋮] = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & ⋯ \\ q & 1 & 0 & 0 & 0 & ⋯ \\ q^{2} & 2q & 1 & 0 & 0 & ⋯ \\ q^{3} & 3q^{2} & 3q & 1 & 0 & ⋯ \\ q^{4} & 4q^{3} & 6q^{2} & 4q & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) [A_{0}(x, q) ; A_{1}(x, q) ; A_{2}(x, q) ; A_{3}(x, q) ; A_{4}(x, q) ; ⋮] .

FACTORIAL EULER–SEIDEL MATRIX: REFINEMENT AND q-ANALOGUE 13

That is,

(3.26)  [E_{n}(x, q)]_{n} = [exp(qt), t] [A_{n}(x, q)]_{n} .

Proof. Setting k = 0 in Equation (3.23), we get the result. □ Theorem 3.16. For a fixed integer n with n ≥ 0, the exponential generating function A(x, t, q) = ∑_{n≥0} A_{n}(x, q)\frac{t^{n}}{n!} has the closed form

(3.27)  A(x, t, q) = exp(−qt) (\frac{x − 1}{x − exp (t(x − 1))})^{q} .

Proof. Setting n = 0 in Equation (3.21), we get

[e_{0}^{k}(x, q)]_{k≥0} = [exp(−qt), t] [E_{k}(x, q)]_{k≥0} .

Hence

∑_{k≥0} \frac{E_{k}(x, q)}{k!}t^{k} = (\frac{x − 1}{x − exp (t(x − 1))})^{q} (cf. Brenti [1]),

and from Theorem 1.4 we get the result. □ Corollary 3.7. We have

(3.28)  A(x, t, q) = (A(x, t))^{q} .

Proof. We have

A(x, t) = \frac{(1 − x) exp(−xt)}{1 − x exp ((1 − x)t)} (cf. Mantaci and Rakotondrajao [8])

= \frac{(x − 1) exp(−t)}{x − exp (t(x − 1))}.

Hence

A(x, t, q) = exp(−qt) (\frac{x − 1}{x − exp (t(x − 1))})^{q}

= (\frac{(x − 1) exp(−t)}{x − exp (t(x − 1))})^{q} .

It follows that A(x, t, q) = (A(x, t))^{q}. □ Theorem 3.17. For a fixed integer n with n ≥ 0, the exponential generating function F_{n}(x, t, q) = ∑_{k≥0} e_{n}^{k}(x, q)\frac{t^{k}}{k!} of (n, k)-permutations has the closed form

(3.29)  F_{n}(x, t, q) = exp(−qt)\frac{d^{n}}{dt^{n}} (\frac{x − 1}{x − exp (t(x − 1))})^{q} .

Proof. From Equation (3.21) and Theorem 1.4, we get

F_{n}(x, t, q) = exp(−qt) ∑_{k≥0} E_{n+k}(x, q)\frac{t^{k}}{k!}

= exp(−qt)\frac{d^{n}}{dt^{n}} (∑_{k≥0} E_{k}(x, q)\frac{t^{k}}{k!})

= exp(−qt)\frac{d^{n}}{dt^{n}} (\frac{x − 1}{x − exp (t(x − 1))})^{q} .  □

14 D. RATOVILEBAMBOAVISON, M. L. N. RAKOTOARISON AND F. RAKOTONDRAJAO

Corollary 3.8. We have

(3.30)  F_{n}(x, t, q) = exp(−qt) \frac{d^{n}}{dt^{n}} E(x, t, q).

Theorem 3.18. For a fixed integer k with k ≥ 0, the exponential generating function F_{k}(x, t, q) = ∑_{n≥0} e_{n}^{k}(x, q)\frac{t^{n}}{n!} of (n, k)-permutations has the closed form

(3.31)  F_{k}(x, t, q) = exp(qt)\frac{d^{k}}{dt^{k}} (\frac{(x − 1) exp(−t)}{x − exp (t(x − 1))})^{q} .

Proof. From Equation (3.24) and Theorem 1.4, we get

F_{k}(x, t, q) = exp(qt) ∑_{k≥0} A_{k+n}(x, q)\frac{t^{k}}{k!}

= exp(qt)\frac{d^{k}}{dt^{k}} (∑_{n≥0} A_{n}(x, q)\frac{t^{n}}{n!})

= exp(qt)\frac{d^{k}}{dt^{k}} (\frac{(x − 1) exp(−t)}{x − exp (t(x − 1))})^{q} .  □

Corollary 3.9. We have

(3.32)  F_{k}(x, t, q) = exp(qt) \frac{d^{k}}{dt^{k}} A(x, t, q).

Theorem 3.19. The exponential generating function

F (x, t, u, q) = ∑_{n≥0} ∑_{k≥0} e_{n}^{k}(x, q)\frac{u^{k}}{k!} \frac{t^{n}}{n!}

of (n, k)-permutations has the closed form

(3.33)  F (x, t, u, q) = exp(−qu) (\frac{x − 1}{x − exp ((x − 1)(u + t))})^{q} .

Proof. From Equation (3.18) and Theorem 1.3, we have

F (x, t, u, q) = ∑_{n≥0} ∑_{k≥0} e_{n}^{k}(x, q)\frac{u^{k}}{k!} \frac{t^{n}}{n!}

= exp(−qu)E(x, t + u, q)

= exp(−qu) (\frac{x − 1}{x − exp ((x − 1)(u + t))})^{q} .

Here, the last line follows from Equation (1.19). □ Corollary 3.10. We have

(3.34)  F (x, t, u, q) = (F (x, t, u))^{q} .

Proof. We have

(F (x, t, u))^{q} = (\frac{(x − 1) exp(−u)}{x − exp ((x − 1)(u + t))})^{q}
= exp(−qu) (\frac{x − 1}{x − exp ((x − 1)(u + t))})^{q} .  □

Acknowledgements

One of the authors, Ratovilebamboavison Dimbiniaina, would like to thank the European Union for the financial support through the project “Appui à la Formation, à la Recherche et à l’Innovation pour le Développement Intra-Afrique (AFRIDI)”.

References

[1] F. Brenti, A class of q-symmetric functions arising from plethysm, Journal of Combinatorial Theory, Series A, 91 (2000) 137–170.

[2] R. J. Clarke, G.-N. Han and J. Zeng, A combinatorial interpretation of the Seidel generation of q-derangement numbers, Annals of Combinatorics, 4 (1997) 313–327.

[3] L. Comtet, Analyse combinatoire, tome second, PUF, 1970.

[4] D. Dumont, A. Randrianarivony, Dérangements et nombres de Genocchi, Discrete Mathematics, 132 (1994) 37–49.

[5] D. Dumont, Matrices d’Euler–Seidel, Séminaire Lotharingien de Combinatoire, 5 (1981) Art. B05c, 16 pp., formely Publ. I.R.M.A. Strasbourg, 182 (1981) 59–76.

[6] M. C. Firengiz and Q. Dil, Generalized Euler–Seidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, ISSN 1310-5132, 20(4) (2014) 21–32.

[7] D. Foata and M.-P. Schützenberger, Théorie géométrique des polynômes eulériens, Berlin, Heidelberg, New York, Springer-Verlag, 1970.

[8] R. Mantaci and F. Rakotondrajao, Exceedingly deranging!, Advances in Mathematics, 30 (2003) 177–188.

[9] F. Rakotondrajao, On Euler’s difference table, Proc. FPSAC’07, Nankai University, Tianjin, China, 2007;

   available at http://igm.univ-mlv.fr/~fpsac/FPSAC07/SITE07/PDF-Proceedings/Posters/22.pdf.

[10] F. Rakotondrajao, k-Fixed-points-permutations, Pure Mathematics and Applications, 17 (2006) 165–173.

[11] D. P. Roselle, Permutations by number of rises and successions, Proceedings of the American Mathematical Society, 19 (1968) 8–16.

[12] L. W. Shapiro, Bijections and the Riordan group, Theoretical Computer Science, 307 (2003) 403–413.

[13] L. W. Shapiro, S. Getu, W. J. Woan and L.C. Woodson, The Riordan group, Discrete Applied Mathematics, 34 (1991) 229–239.

[14] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Mathematics, 132 (1994) 267–290.

[15] R. P. Stanley, Enumerative Combinatorics, Volume I, Cambridge University Press, Cambridge, UK, 1997.

[16] J. Worpitzky, Studien über die Bernoullischen und Eulerschen Zahlen, Crelle’s Journal, 94 (1883) 203–232.