q-Derangement Identities

Emanuele Munarini Dipartimento di Matematica Politecnico di Milano Piazza Leonardo da Vinci 32 Milano Italy

              emanuele.munarini@polimi.it

Abstract

In this paper, we derive several combinatorial identities involving the q-derangement numbers (for the major index) and many other q-numbers and q-polynomials of combinatorial interest, such as the q-binomial coefficients, the q-Stirling numbers, the q-Bell numbers, the q-Pochhammer symbol, the Gaussian polynomials, the Rogers-Szegő polynomials and the Galois numbers, and the Al-Salam-Carlitz polynomials. We also obtain two determinantal identities expressing the q-derangement numbers as tridiagonal determinants and as Hessenberg determinants.

1 Introduction

The derangement number d_{n} (sequence \underline{A000166} in the On-Line Encyclopedia of Integer Sequences) counts the derangements (i.e., permutation with no fixed points) of an n-set. By a simple application of the principle of inclusion-exclusion, we have the formula

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

Moreover, these numbers satisfy the recurrences

d_{n+1} = (n + 1) d_{n} + (−1)^{n+1}  (2)
d_{n+2} = (n + 1) d_{n+1} + (n + 1) d_{n}  (3)

with initial conditions d_{0} = 1 and d_{1} = 0.

The q-derangement numbers [32, 5] are defined by the formula

d_{n}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}[n − k]_{q}! (−1)^{k}q^{\binom{k}{2}} ,  (4)

where [n]_{q} = 1 + q + q^{2} + ⋯ + q^{n−1}, and satisfy the recurrences

d_{n+1}(q) = [n + 1]_{q} d_{n}(q) + (−1)^{n+1}q^{\binom{n+1}{2}}  (5)
d_{n+2}(q) = [n + 1]_{q} d_{n+1}(q) + [n + 1]_{q} q^{n+1}d_{n}(q)  (6)

with initial conditions d_{0}(q) = 1 and d_{1}(q) = 0.

The major index maj(σ) of a permutation σ of {1, 2, …, n} is the sum of all positions k for which σ(k) > σ(k + 1). The q-numbers d_{n}(q) arise from the q-counting of derangements by major index and have several interesting combinatorial properties. Indeed, if 𝒟_{n} is the set of all derangements of {1, 2, …, n}, then we have [32]

d_{n}(q) = ∑_{σ∈𝒟_{n}} q^{maj(σ)} .

Moreover, considered as a polynomial in q, the q-derangement number d_{n}(q) has non-negative integer coefficients forming a unimodal sequence [5]. These coefficients have a spiral property [33], which implies their unimodality and also the fact that the maximum coefficient of d_{n}(q) appears exactly in the middle of the polynomial, i.e., is the coefficient of q^{⌊n(n−1)/4⌋} (as conjectured by Chen and Rota [5]). Furthermore, they have the ratio monotonicity property (for n ≥ 6) [7] which implies log-concavity and the spiral property.

For the ordinary derangement numbers d_{n} (and their generalizations [3, 10, 23, 24, 25]) there are a lot of combinatorial identities. In this paper, we derive several q-analogues of these identities. They involve the q-derangement numbers d_{n}(q) and many other q-numbers or q-polynomials, such as the q-binomial coefficients, the q-Stirling numbers and the q-Bell numbers, the q-Pochhammer symbol, the Gaussian polynomials, the Rogers-Szegő polynomials and the Galois numbers, and the Al-Salam-Carlitz polynomials. Finally, we obtain two determinantal identities expressing the q-derangement numbers as tridiagonal determinants and as Hessenberg determinants.

2 q-binomial identities

We start by recalling some basic definitions of q-number theory. For every n ∈ ℕ, we have the q-natural number [n]_{q} = 1 + q + q^{2} + ⋯ + q^{n−1} and the q-factorial number [n]_{q}! = [n]_{q}[n − 1]_{q} ⋯ [2]_{q}[1]_{q}. Then, for every n, k ∈ ℕ, we have the q-binomial coefficients (or Gaussian coefficients [12]) defined by

\binom{n}{k}_{q} = \begin{cases}\frac{[n]_{q}!}{[k]_{q}![n − k]_{q}!}, & if k ≤ n; \\ 0, & otherwise, \end{cases}

and satisfying the recurrence

\binom{n + 1}{k + 1}_{q} = \binom{n}{k}_{q} + q^{n+1}\binom{n}{k + 1}_{q}  (7)

with initial conditions \binom{n}{0}_{q} = 1 and \binom{0}{k}_{q} = δ_{k,0}. Moreover, we have the relations

[n]_{q^{−1}} = \frac{1}{q^{n−1}} [n]_{q} ,  [n]_{q^{−1}}! = [n]_{q}! q^{−\binom{n}{2}} ,  \binom{n}{k}_{q^{−1}} = \binom{n}{k}_{q}q^{−k(n−k)} .  (8)

In this first section, we derive some q-binomial identities using an elementary approach [21] which exploits the properties of the q-binomial coefficients and the recurrences of the q-derangement numbers. In Section 5, we derive some other q-binomial identities by using the more advanced technique of the q-exponential series.

Our first result is the following:

Theorem 1. For every n ∈ ℕ, we have the identity

1 + ∑_{k=1}^{n} \binom{n}{k}_{q} \frac{d_{k+1}(q)}{[k]_{q}} = ∑_{k=0}^{n} \binom{n + 1}{k + 1}_{q}d_{k}(q) .  (9)

Proof. By recurrence (6), we have

\frac{d_{k+2}(q)}{[k + 1]_{q}} = d_{k+1}(q) + q^{k+1}d_{k}(q) .

Consequently, we have

∑_{k=0}^{n−1} \binom{n}{k + 1}_{q} \frac{d_{k+2}(q)}{[k + 1]_{q}} = ∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}d_{k+1}(q) + ∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}q^{k+1}d_{k}(q)

or

∑_{k=1}^{n} \binom{n}{k}_{q} \frac{d_{k+1}(q)}{[k]_{q}} = ∑_{k=1}^{n} \binom{n}{k}_{q}d_{k}(q) + ∑_{k=0}^{n} \binom{n}{k + 1}_{q}q^{k+1}d_{k}(q)

or

∑_{k=1}^{n} \binom{n}{k}_{q} \frac{d_{k+1}(q)}{[k]_{q}} = ∑_{k=0}^{n} (\binom{n}{k}_{q} + q^{k+1}\binom{n}{k + 1}_{q}) d_{k}(q) − d_{0}(q) .

By recurrence (7) and the initial condition d_{0}(q) = 1, we have identity (9).

Similarly, we have the following formula.

Theorem 2. For every n ∈ ℕ, we have the identity

∑_{k=0}^{n} \binom{n}{k}_{q}d_{k+1}(q) = ∑_{k=0}^{n} \binom{n + 1}{k + 1}_{q}[k]_{q}d_{k}(q) + ∑_{k=1}^{n} \binom{n}{k}_{q}q^{2k−1}d_{k−1}(q) .  (10)

Proof. By recurrence (6), we have

∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}d_{k+2}(q) = ∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}[k + 1]_{q}d_{k+1}(q) + ∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}[k + 1]_{q}q^{k+1}d_{k}(q)

or

∑_{k=1}^{n} \binom{n}{k}_{q}d_{k+1}(q) = ∑_{k=1}^{n} \binom{n}{k}_{q}[k]_{q}d_{k}(q) + ∑_{k=0}^{n} \binom{n}{k + 1}_{q}[k + 1]_{q}q^{k+1}d_{k}(q)

or

∑_{k=0}^{n} \binom{n}{k}_{q}d_{k+1}(q) − d_{1}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}[k]_{q}d_{k}(q) + ∑_{k=0}^{n} \binom{n}{k + 1}_{q}([k]_{q} + q^{k})q^{k+1}d_{k}(q)

or

∑_{k=0}^{n} \binom{n}{k}_{q}d_{k+1}(q) − d_{1}(q) = ∑_{k=0}^{n} (\binom{n}{k}_{q} + q^{k+1}\binom{n}{k + 1}_{q}) [k]_{q}d_{k}(q) + ∑_{k=0}^{n} \binom{n}{k + 1}_{q}q^{2k+1}d_{k}(q) .

By recurrence (7) and the initial condition d_{1}(q) = 0, we have identity (10).

We also have the following formula. Theorem 3. For every m, n ∈ ℕ, we have the identity

∑_{k=0}^{n} \binom{m + n + 1}{m + k + 1}_{q} \frac{[n]_{q}!}{[k]_{q}!} (−1)^{k}q^{\binom{m+k+1}{2}}d_{k}(q) = ∑_{k=0}^{n} \binom{m + n}{m + k}_{q} \frac{[n]_{q}!}{[k]_{q}!} (−1)^{k}q^{\binom{m+k+1}{2}+\binom{k}{2}} . (11)

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

∑_{k=0}^{n} \binom{n + 1}{k + 1}_{q} \frac{[n]_{q}!}{[k]_{q}!} (−1)^{k}q^{\binom{k+1}{2}}d_{k}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q} \frac{[n]_{q}!}{[k]_{q}!} (−1)^{k}q^{k^{2}}.  (12)

Proof. From recurrence (5), we have

\frac{d_{k+1}(q)}{[k + 1]_{q}!} = \frac{d_{k}(q)}{[k]_{q}!} + (−1)^{k+1} \frac{q^{\binom{k+1}{2}}}{[k + 1]_{q}!} .

and consequently

∑_{k=0}^{n−1} \binom{m + n}{m + k + 1}_{q}(−1)^{k+1}[n]_{q}!q^{\binom{m+k+2}{2}} \frac{d_{k+1}(q)}{[k + 1]_{q}!}

= ∑_{k=0}^{n−1} \binom{m + n}{m + k + 1}_{q}(−1)^{k+1}[n]_{q}!q^{\binom{m+k+2}{2}} \frac{d_{k}(q)}{[k]_{q}!} + ∑_{k=0}^{n−1} \binom{m + n}{m + k + 1}_{q}[n]_{q}!q^{\binom{m+k+2}{2}} \frac{q^{\binom{k+1}{2}}}{[k + 1]_{q}!} ;

that is,

∑_{k=1}^{n} \binom{m + n}{m + k}_{q} \frac{[n]_{q}!}{[k]_{q}!} (−1)^{k}q^{\binom{m+k+1}{2}}d_{k}(q) + ∑_{k=0}^{n−1} \binom{m + n}{m + k + 1}_{q} \frac{[n]_{q}!}{[k]_{q}!} (−1)^{k}q^{\binom{m+k+1}{2}}q^{m+k+1}d_{k}(q)

= ∑_{k=1}^{n} \binom{m + n}{m + k}_{q} \frac{[n]_{q}!}{[k]_{q}!}q^{\binom{m+k+1}{2}}q^{\binom{k}{2}} ,

or

∑_{k=0}^{n} (\binom{m + n}{m + k}_{q} + q^{m+k+1}\binom{m + n}{m + k + 1}_{q}) \frac{[n]_{q}!}{[k]_{q}!} (−1)^{k}q^{\binom{m+k+1}{2}}d_{k}(q)

= \binom{m + n}{m}_{q}[n]_{q}!q^{\binom{m+1}{2}} + ∑_{k=1}^{n} \binom{m + n}{m + k}_{q} \frac{[n]_{q}!}{[k]_{q}!}q^{\binom{m+k+1}{2}+\binom{k}{2}} .

Hence, by formula (7), we have identity (11).

Using the same approach, we also have the following result. Theorem 4. We have the identity

q ∑_{k=0}^{n}[k]_{q}d_{k}(q) + ∑_{k=0}^{n}(−1)^{k}q^{\binom{k}{2}} = [n + 1]_{q}d_{n}(q) .  (13)

Proof. Since [k + 1]_{q} = 1 + q[k]_{q}, recurrence (5) can be rewritten as

d_{k+1}(q) = (1 + q[k]_{q}) d_{k}(q) + (−1)^{k+1}q^{\binom{k+1}{2}}

or

d_{k+1}(q) − d_{k}(q) = q[k]_{q} d_{k}(q) + (−1)^{k+1}q^{\binom{k+1}{2}} .

Hence, we have

∑_{k=0}^{n} d_{k+1}(q) − ∑_{k=0}^{n} d_{k}(q) = q ∑_{k=0}^{n}[k]_{q} d_{k}(q) + ∑_{k=0}^{n}(−1)^{k+1}q^{\binom{k+1}{2}}

or

∑_{k=1}^{n+1} d_{k}(q) − ∑_{k=0}^{n} d_{k}(q) = q ∑_{k=0}^{n}[k]_{q} d_{k}(q) + ∑_{k=1}^{n+1}(−1)^{k}q^{\binom{k}{2}}

or

d_{n+1}(q) − d_{0}(q) = q ∑_{k=0}^{n}[k]_{q} d_{k}(q) + ∑_{k=0}^{n+1}(−1)^{k}q^{\binom{k}{2}} − 1 .

Hence, by the recurrence (5) once again, we have the identity

[n + 1]_{q}d_{n}(q) + (−1)^{n+1}q^{\binom{n+1}{2}} = q ∑_{k=0}^{n}[k]_{q} d_{k}(q) + ∑_{k=0}^{n}(−1)^{k}q^{\binom{k}{2}} + (−1)^{n+1}q^{\binom{n+1}{2}}

which simplifies to identity (13).

Similarly, we also have the following property. Theorem 5. We have the identity

∑_{k=0}^{n} \binom{n + 1}{k + 1}_{q}(−1)^{k}q^{\binom{k+1}{2}}d_{k}(q) = q ∑_{k=1}^{n} \binom{n}{k}_{q}(−1)^{k}q^{\binom{k+1}{2}}[k − 1]_{q}d_{k−1}(q) + ∑_{k=0}^{n} \binom{n}{k}_{q}q^{k^{2}}. (14)

Proof. Once again, we start by the recurrence (5) written as

d_{k+1}(q) − d_{k}(q) = q[k]_{q} d_{k}(q) + (−1)^{k+1}q^{\binom{k+1}{2}} .

Then we have

\begin{matrix}∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}(−1)^{k+1}q^{\binom{k+2}{2}}d_{k+1}(q) − ∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}(−1)^{k+1}q^{\binom{k+2}{2}}d_{k}(q) = \\ q ∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}(−1)^{k+1}q^{\binom{k+2}{2}}[k]_{q} d_{k}(q) + ∑_{k=0}^{n−1} \binom{n}{k + 1}_{q}q^{\binom{k+2}{2}}q^{\binom{k+1}{2}}, \end{matrix}

which is

\begin{matrix}∑_{k=1}^{n} \binom{n}{k}_{q}(−1)^{k}q^{\binom{k+1}{2}}d_{k}(q) + ∑_{k=0}^{n} \binom{n}{k + 1}_{q}(−1)^{k}q^{\binom{k+1}{2}}q^{k+1}d_{k}(q) = \\ q ∑_{k=1}^{n} \binom{n}{k}_{q}(−1)^{k}q^{\binom{k+1}{2}}[k − 1]_{q} d_{k−1}(q) + ∑_{k=1}^{n} \binom{n}{k}_{q}q^{\binom{k+1}{2}}q^{\binom{k}{2}} \end{matrix}

or

\begin{matrix}∑_{k=0}^{n} (\binom{n}{k}_{q} + q^{k+1}\binom{n}{k + 1}_{q}) (−1)^{k}q^{\binom{k+1}{2}}d_{k}(q) − 1 \\ = q ∑_{k=1}^{n} \binom{n}{k}_{q}(−1)^{k}q^{\binom{k+1}{2}}[k − 1]_{q} d_{k−1}(q) + ∑_{k=0}^{n} \binom{n}{k}_{q}q^{\binom{k+1}{2}}q^{\binom{k}{2}} − 1 . \end{matrix}

By recurrence (7), this last identity simplifies to identity (14).

3 q-Stirling identities

The q-Stirling numbers of the second kind are defined as the connection constants [9, 21] between the ordinary powers x^{n} and the q-falling factorials x\underline{n} ; q = x(x − [1]_{q})(x − [2]_{q}) ⋯ (x − [n − 1]_{q}), that is, as the coefficients \left\{{n \atop k}\right\}_{q} for which

x^{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}x\underline{k} ; q .

Equivalently, they are the numbers defined by the recurrence

\left\{{n + 1 \atop k + 1}\right\}_{q} = \left\{{n \atop k}\right\}_{q} + [k + 1]_{q}\left\{{n \atop k + 1}\right\}_{q}  (15)

with initial values \left\{{n \atop 0}\right\}_{q} = δ_{n,0} and \left\{{0 \atop k}\right\}_{q} = δ_{k,0}.

Similarly, the q-Stirling numbers of the first kind are defined as the connection constants [9, 21] between the q-rising factorials x\overline{n} ; q = x(x + [1]_{q})(x + [2]_{q}) ⋯ (x + [n − 1]_{q}) and the ordinary powers x^{n}, that is, as the coefficients \left[{n \atop k}\right]_{q} for which

x\overline{n} ; q = ∑_{k=0}^{n} \left[{n \atop k}\right]_{q}x^{k} .

Equivalently, they are the numbers defined by the recurrence

\left[{n + 1 \atop k + 1}\right]_{q} = \left[{n \atop k}\right]_{q} + [n]_{q}\left[{n \atop k + 1}\right]_{q}  (16)

with initial values \left[{n \atop 0}\right]_{q} = δ_{n,0} and \left[{0 \atop k}\right]_{q} = δ_{k,0}.

For the q-Stirling numbers, we have the inverse relations

f_{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}g_{k}  ⟺  g_{n} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{q}(−1)^{n−k}f_{k}  (17)

and

f_{n} = ∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}g_{k}  ⟺  g_{n} = ∑_{k=0}^{n} \left[{n + 1 \atop k + 1}\right]_{q}(−1)^{n−k}f_{k} .  (18)

Consider the q-Bell numbers defined by

b_{n}(q) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}q^{\binom{k}{2}} .  (19)

Although they are not the cumulative constants of the q-Stirling numbers considered above, we have the following formulas relating the q-derangement numbers and the q-Bell numbers, Theorem 6. We have the identities

∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}(−1)^{k}d_{k}(q) = b_{n}(q)  (20)
∑_{k=0}^{n} \left[{n + 1 \atop k + 1}\right]_{q}(−1)^{k}b_{k}(q) = d_{n}(q) .  (21)

Proof. By recurrence (5), we have

d_{k+1}(q) − [k + 1]_{q}d_{k}(q) = (−1)^{k+1}q^{\binom{k+1}{2}} .

Hence, we have the identity

∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k+1}d_{k+1}(q) − ∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k+1}[k + 1]_{q}d_{k}(q) = ∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}q^{\binom{k+1}{2}}

or

∑_{k=1}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}d_{k}(q) + ∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k}[k + 1]_{q}d_{k}(q) = ∑_{k=1}^{n} \left\{{n \atop k}\right\}_{q}q^{\binom{k}{2}}

or

∑_{k=0}^{n} (\left\{{n \atop k}\right\}_{q} + [k + 1]_{q}\left\{{n \atop k + 1}\right\}_{q}) (−1)^{k}d_{k}(q) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}q^{\binom{k}{2}}

By recurrence (15) and definition (19), we have identity (20). Then, by this identity, we get identity (21) at once as its inverse relation (by property (18)).

To prove the next theorem, we need the following result. Lemma 7. For every n, k ∈ ℕ, we have the identity

\left\{{n + 1 \atop k + 1}\right\}_{q} = ∑_{i=k}^{n} \binom{n}{i}\left\{{i \atop k}\right\}_{q}q^{i−k} .  (22)

Proof. Since

x^{n+1} = ∑_{k=1}^{n+1} \left\{{n + 1 \atop k}\right\}_{q}x\underline{k} ; q = ∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}x\underline{k+1} ; q = ∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}x(x − [1]_{q}) ⋯ (x − [k]_{q}) ,

we have

x^{n} = ∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}(x − [1]_{q})(x − [2]_{q}) ⋯ (x − [k]_{q})

= ∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}(x − 1)(x − 1 − q[1]_{q}) ⋯ (x − 1 − q[k − 1]_{q})

or

(qx + 1)^{n} = ∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}q^{k}x(x − [1]_{q}) ⋯ (x − [k − 1]_{q}) = ∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}q^{k}x\underline{k} ; q .

Then, from this relation, we have

∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}q^{k}x\underline{k} ; q = ∑_{i=0}^{n} \binom{n}{i}q^{i}x^{i} = ∑_{i=0}^{n} \binom{n}{i}q^{i} ∑_{k=0}^{i} \left\{{i \atop k}\right\}_{q}x\underline{k} ; q = ∑_{k=0}^{i} (∑_{i=k}^{n} \binom{n}{i}\left\{{i \atop k}\right\}_{q}q^{i}) x\underline{k} ; q .

By equating the coefficients of x\underline{k} ; q, we obtain identity (22).

Now we can prove the following result. Theorem 8. We have the identity

∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}q^{n−k}d_{k}(q) = ∑_{k=0}^{n} \binom{n}{k}(−1)^{n−k}b_{k}(q) .  (23)

Proof. By identities (20) and (22), we have

b_{n}(q) = ∑_{k=0}^{n} (∑_{i=0}^{n} \binom{n}{i}\left\{{i \atop k}\right\}_{q}q^{i−k}) (−1)^{k}d_{k}(q) = ∑_{i=0}^{n} \binom{n}{i} ∑_{k=0}^{i} \left\{{i \atop k}\right\}_{q}(−1)^{k}q^{i−k}d_{k}(q) .

Thus, if we set

z_{n}(q) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}q^{n−k}d_{k}(q) ,

then we have the identity

b_{n}(q) = ∑_{i=0}^{n} \binom{n}{i}z_{i}(q),

whose inverse is

z_{n}(q) = ∑_{i=0}^{n} \binom{n}{i}(−1)^{n−i}b_{i}(q) .

This is identity (23).

We also have the following result. Theorem 9. We have the identity

∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}(−1)^{k}d_{k+1}(q) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}q^{k}[k]_{q}d_{k−1}(q) .  (24)

Proof. By recurrence (6), we have

d_{k+2}(q) − [k + 1]_{q}d_{k+1}(q) = [k + 1]_{q}q^{k+1}d_{k}(q) .

Then we have

\begin{matrix}∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k+1}d_{k+2}(q) − ∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k+1}[k + 1]_{q}d_{k+1}(q) = \\ = ∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k+1}[k + 1]_{q}q^{k+1}d_{k}(q), \end{matrix}

or

∑_{k=1}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}d_{k+1}(q) + ∑_{k=0}^{n} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k}[k + 1]_{q}d_{k+1}(q) = ∑_{k=1}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}[k]_{q}q^{k}d_{k−1}(q),

or

∑_{k=1}^{n} (\left\{{n \atop k}\right\}_{q} + [k + 1]_{q}\left\{{n \atop k + 1}\right\}_{q}) (−1)^{k}d_{k+1}(q) = ∑_{k=1}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}[k]_{q}q^{k}d_{k−1}(q) .

By recurrence (15), we have identity (24).

Similarly, we also have the following formula. Theorem 10. We have the identity

∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}q^{−\binom{k+1}{2}}d_{k}(q)^{2} = ∑_{k=0}^{n} \left\{{n + 1 \atop k + 1}\right\}_{q}(−1)^{k}q^{−\binom{k+1}{2}}d_{k}(q)d_{k+1}(q) .  (25)

Proof. By recurrence (6), we have

d_{k+1}(q)d_{k+2}(q) = [k + 1]_{q}d_{k+1}(q)^{2} + [k + 1]_{q}q^{k+1}d_{k}(q)d_{k+1}(q),

or

[k + 1]_{q}d_{k+1}(q)^{2} = d_{k+1}(q)d_{k+2}(q) − [k + 1]_{q}q^{k+1}d_{k}(q)d_{k+1}(q) .

Hence, we have

∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k+1}q^{−\binom{k+2}{2}}[k + 1]_{q}d_{k+1}(q)^{2}

= ∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k+1}q^{−\binom{k+2}{2}}d_{k+1}(q)d_{k+2}(q)

− ∑_{k=0}^{n−1} \left\{{n \atop k + 1}\right\}_{q}(−1)^{k+1}q^{−\binom{k+2}{2}}[k + 1]_{q}q^{k+1}d_{k}(q)d_{k+1}(q)

or

∑_{k=1}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}q^{−\binom{k+1}{2}}[k]_{q}d_{k}(q)^{2}

= ∑_{k=1}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}q^{−\binom{k+1}{2}}d_{k}(q)d_{k+1}(q)

+ ∑_{k=0}^{n} \left\{{n \atop k + 1}\right\}_{q}[k + 1]_{q}(−1)^{k}q^{−\binom{k+1}{2}}d_{k}(q)d_{k+1}(q) .

Since [0]_{q} = 0 and d_{1}(q) = 0, we have

∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q}(−1)^{k}q^{−\binom{k+1}{2}}[k]_{q}d_{k}(q)^{2}

= ∑_{k=0}^{n} (\left\{{n \atop k}\right\}_{q} + [k + 1]_{q}\left\{{n \atop k + 1}\right\}_{q}) (−1)^{k}q^{−\binom{k+1}{2}}d_{k}(q)d_{k+1}(q) .

Finally, by the recurrence (15), this identity simplifies to identity (25).

Now consider the q-Bell numbers B_{n}(q) defined by the recurrence

B_{n+1}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}q^{n(n−k)}B_{k}(q)  (26)

with initial value B_{0}(q) = 1. Notice that the q-numbers b_{n}(q) and B_{n}(q) are different qanalogues of the ordinary Bell numbers (\underline{A000110}). For these q-Bell numbers, we have the following result.

Theorem 11. We have the identity

∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{n−k}q^{−\binom{k+1}{2}}B_{k}(q) d_{n−k}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{n−k}q^{−\binom{k+1}{2}}B_{k+1}(q) [n − k]_{q}! (27)

Proof. Let σ_{n}(q) be the sum on the right-hand side of identity (27). Then, by the recurrence (26), we have

σ_{n}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{n−k}q^{−\binom{k+1}{2}}[n − k]_{q}! B_{k+1}(q)

= ∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{n−k}q^{−\binom{k+1}{2}}[n − k]_{q}! ∑_{i=0}^{k} \binom{k}{i}_{q}q^{k(k−i)}B_{i}(q)

= ∑_{i=0}^{n} (∑_{k=i}^{n} \binom{n}{k}_{q}\binom{k}{i}_{q}[n − k]_{q}!(−1)^{n−k}q^{−\binom{k+1}{2}}q^{k(k−i)}) B_{i}(q)

= ∑_{i=0}^{n} \binom{n}{i}_{q} (∑_{k=i}^{n} \binom{n − i}{k − i}_{q}[n − k]_{q}!(−1)^{n−k}q^{−\binom{k+1}{2}}q^{k(k−i)}) B_{i}(q)

= ∑_{i=0}^{n} \binom{n}{i}_{q} (∑_{k=0}^{n−i} \binom{n − i}{k}_{q}[n − k − i]_{q}!(−1)^{n−k−i}q^{−\binom{k+i+1}{2}}q^{(k+i)k}) B_{i}(q)

= ∑_{i=0}^{n} \binom{n}{i}_{q}(−1)^{n−i} (∑_{k=0}^{n−i} \binom{n − i}{k}_{q}[n − k − i]_{q}!(−1)^{k}q^{−\binom{i+1}{2}−\binom{k+1}{2}−ik}q^{(k+i)k}) B_{i}(q)

= ∑_{i=0}^{n} \binom{n}{i}_{q}(−1)^{n−i}q^{−\binom{i+1}{2}} (∑_{k=0}^{n−i} \binom{n − i}{k}_{q}[n − k − i]_{q}!(−1)^{k}q^{\binom{k}{2}}) B_{i}(q) .

Finally, by formula (4), we have

σ_{n}(q) = ∑_{i=0}^{n} \binom{n}{i}_{q}(−1)^{n−i}q^{−\binom{i+1}{2}}d_{n−i}(q) B_{i}(q),

and this is the claimed identity.

4 Elementary identities

Several combinatorial identities can be derived from the following property of linear recurrences of the first order: the general solution of the recurrence

y_{n+1} = a_{n+1}y_{n} + b_{n+1}

is given by

y_{n} = a_{n}^{∗}y_{0} + ∑_{k=1}^{n} \frac{a_{n}^{∗}}{a_{k}^{∗}} b_{k},  (28)

where a_{n}^{∗} = a_{1}a_{2} ⋯ a_{n}, provided that a_{n} ≠ 0 for all n ∈ ℕ.

First of all, we have the following simple result.

Theorem 12. For every m, n ∈ ℕ, we have the identity

\begin{matrix}d_{m+n+2}(q) = \binom{m + n + 1}{m}_{q}[n + 1]_{q}!d_{m+1}(q) \\ + [m + n + 1]_{q} ∑_{k=0}^{n} \binom{m + n}{m + k}_{q}[n − k]_{q}!q^{k+m+1}d_{m+k}(q) \end{matrix}  (29)

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

d_{n+2}(q) = [n + 1]_{q} ∑_{k=0}^{n} \binom{n}{k}_{q}[n − k]_{q}!q^{k+1}d_{k}(q) .  (30)

Proof. Let y_{n}(q) = d_{m+n+1}(q). By recurrence (6), we have

y_{n+1}(q) = d_{m+n+2}(q) = [m + n + 1]_{q} d_{m+n+1}(q) + [m + n + 1]_{q} q^{m+n+1}d_{m+n}(q),

or

y_{n+1}(q) = [m + n + 1]_{q} y_{n}(q) + [m + n + 1]_{q} q^{m+n+1}d_{m+n}(q) .

This is a linear recurrence of the first order with coefficients a_{n} = [m + n]_{q} and b_{n} = [m + n]_{q} q^{m+n}d_{m+n−1}(q). Since

a_{n}^{∗} = [m + n]_{q} ⋯ [m]_{q} = \frac{[m + n]_{q}}{[m]_{q}} = \binom{m + n}{m}_{q}[n]_{q}! ,

then the solution, being y_{0}(q) = d_{m+1}(q), is

y_{n}(q) = \binom{m + n}{m}_{q}[n]_{q}!d_{m+1}(q) + ∑_{k=1}^{n} \frac{[m + n]_{q}}{[m]_{q}} \frac{[m]_{q}}{[m + k]_{q}} [m + k]_{q} q^{m+k}d_{m+k−1}(q)

= \binom{m + n}{m}_{q}[n]_{q}!d_{m+1}(q) + ∑_{k=1}^{n} \frac{[m + n]_{q}}{[m + k]_{q}} [m + k]_{q} q^{m+k}d_{m+k−1}(q)

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

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

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

Finally, by replacing n by n + 1, we obtain formula (29).

\frac{d_{m+n+2}(q)}{[m + n + 1]_{q}!} = \frac{d_{m+1}(q)}{[m]_{q}!} + ∑_{k=0}^{n} q^{m+k+1} \frac{d_{m+k}(q)}{[m + k]_{q}!} .  (31)

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

\frac{d_{n+2}(q)}{[n + 1]_{q}!} = ∑_{k=0}^{n} q^{k+1} \frac{d_{k}(q)}{[k]_{q}!} .  (32)

Proof. Let y_{n}(q) = \frac{d_{m+n+1}(q)}{[m+n]_{q}!}. By recurrence (6), we have

y_{n+1}(q) = \frac{d_{m+n+2}(q)}{[m + n + 1]_{q}!} = \frac{[m + n + 1]_{q}(d_{m+n+1}(q) + q^{m+n+1}d_{m+n}(q))}{[m + n + 1]_{q}!}

= \frac{d_{m+n+1}(q)}{[m + n]_{q}!} + q^{m+n+1} \frac{d_{m+n}(q)}{[m + n]_{q}!},

or

y_{n+1}(q) = y_{n}(q) + q^{m+n+1} \frac{d_{m+n}(q)}{[m + n]_{q}!} .

This is a linear recurrence of the first order with a_{n} = 1 and b_{n} = q^{m+n} \frac{d_{m+n−1}(q)}{[m+n−1]_{q}!} for n ≥ 1. So, by formula (28), we have the solution

y_{n}(q) = y_{0}(q) + ∑_{k=1}^{n} q^{m+k} \frac{d_{m+k−1}(q)}{[m + k − 1]_{q}!} = y_{0}(q) + ∑_{k=0}^{n−1} q^{m+k+1} \frac{d_{m+k}(q)}{[m + k]_{q}!},

or

\frac{d_{m+n+1}(q)}{[m + n]_{q}!} = \frac{d_{m+1}(q)}{[m]_{q}!} + ∑_{k=0}^{n−1} q^{m+k+1} \frac{d_{m+k}(q)}{[m + k]_{q}!} .

Now by replacing n by n + 1, we obtain identity (31).

Theorem 14. For every m, n ∈ ℕ, we have the identity

\frac{d_{m+n+1}(q)d_{m+n+2}(q)}{q^{\binom{n+2}{2}}[m + n + 1]_{q}!} = q^{m(n+1)} \frac{d_{m}(q)d_{m+1}(q)}{[m]_{q}!} + ∑_{k=0}^{n} q^{m(n−k)} \frac{d_{m+k+1}(q)^{2}}{q^{\binom{k+2}{2}}[m + k]_{q}!}  (33)

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

\frac{d_{n+1}(q)d_{n+2}(q)}{q^{\binom{n+2}{2}}[n + 1]_{q}!} = ∑_{k=0}^{n} \frac{d_{k+1}(q)^{2}}{q^{\binom{k+2}{2}}[k]_{q}!}  (34)

Proof. Let y_{n}(q) = \frac{d_{m+n}(q)d_{m+n+1}(q)}{[m+n]_{q}!}. By recurrence (6), we have

y_{n+1}(q) = \frac{d_{m+n+1}(q)d_{m+n+2}(q)}{[m + n + 1]_{q}!} = \frac{d_{m+n+1}(q) (d_{m+n+1}(q) + q^{m+n+1}d_{m+n}(q))}{[m + n]_{q}!}

= \frac{d_{m+n+1}(q)^{2}}{[m + n]_{q}!} + q^{m+n+1} \frac{d_{m+n}(q)d_{m+n+1}(q)}{[m + n]_{q}!},

or

y_{n+1}(q) = q^{m+n+1}y_{n}(q) + \frac{d_{m+n+1}(q)^{2}}{[m + n]_{q}!} .

This is a linear recurrence of the first order with a_{n} = q^{m+n} and b_{n} = \frac{d_{m+n}(q)^{2}}{[m+n−1]_{q}!} for n ≥ 1. Since a_{n}^{∗} = q^{mn+\binom{n+1}{2}}, by formula (28), we have the solution

y_{n}(q) = q^{mn+\binom{n+1}{2}}y_{0}(q) + ∑_{k=1}^{n} \frac{q^{mn+\binom{n+1}{2}}}{q^{mk+\binom{k+1}{2}}} \frac{d_{m+k}(q)^{2}}{[m + k − 1]_{q}!}

= q^{mn+\binom{n+1}{2}}y_{0}(q) + q^{\binom{n+1}{2}} ∑_{k=0}^{n−1} q^{m(n−k−1)} \frac{d_{m+k+1}(q)^{2}}{q^{\binom{k+2}{2}}[m + k]_{q}!},

or

\frac{d_{m+n}(q)d_{m+n+1}(q)}{q^{\binom{n+1}{2}}[m + n]_{q}!} = q^{mn} \frac{d_{m}(q)d_{m+1}(q)}{[m]_{q}!} + ∑_{k=0}^{n−1} q^{m(n−k−1)} \frac{d_{m+k+1}(q)^{2}}{q^{\binom{k+2}{2}}[m + k]_{q}!} .

Now by replacing n by n + 1, we obtain identity (33).

The next formula can be obtained with the same elementary approach used in Section 2. Theorem 15. We have the identity

\begin{matrix}\frac{d_{m+n+1}(q)^{2} − q^{2\binom{m+n+1}{2}}}{[m + n + 1]_{q}!^{2}} = \frac{d_{m}(q)^{2} − q^{2\binom{m}{2}}}{[m]_{q}!^{2}} + \\ + 2 ∑_{k=0}^{n}(−1)^{m+k+1}q^{\binom{m+k+1}{2}} \frac{d_{m+k}(q)}{[m + k]_{q}![k + m + 1]_{q}!} + ∑_{k=0}^{n} \frac{q^{2\binom{m+k}{2}}}{[m + k]_{q}!^{2}} . \end{matrix}  (35)

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

\frac{d_{n+1}(q)^{2} − q^{n(n+1)}}{[n + 1]_{q}!^{2}} = 2 ∑_{k=0}^{n}(−1)^{k+1}q^{\binom{k+1}{2}} \frac{d_{k}(q)}{[k]_{q}![k + 1]_{q}!} + ∑_{k=0}^{n} \frac{q^{k(k−1)}}{[k]_{q}!^{2}} .  (36)

Proof. By recurrences (5), we have

\begin{matrix}d_{m+k+1}(q)^{2} = ([m + k + 1]_{q}d_{m+k}(q) + (−1)^{m+k+1}q^{\binom{m+k+1}{2}})^{2} \\ = [m + k + 1]_{q}^{2}d_{m+k}(q)^{2} + 2(−1)^{m+k+1}q^{\binom{m+k+1}{2}}[m + k + 1]_{q}d_{m+k}(q) + q^{2\binom{m+k+1}{2}} . \end{matrix}

Hence, we can write

\frac{d_{m+k+1}(q)^{2}}{[m + k + 1]_{q}!^{2}} = \frac{d_{m+k}(q)^{2}}{[m + k]_{q}!^{2}} + 2(−1)^{m+k+1}q^{\binom{m+k+1}{2}} \frac{d_{m+k}(q)}{[m + k]_{q}![m + k + 1]_{q}!} + \frac{q^{2\binom{m+k+1}{2}}}{[m + k + 1]_{q}!^{2}}

and, consequently, we have

\begin{matrix}∑_{k=0}^{n} \frac{d_{m+k+1}(q)^{2}}{[m + k + 1]_{q}!^{2}} = ∑_{k=0}^{n} \frac{d_{m+k}(q)^{2}}{[m + k]_{q}!^{2}} \\ + 2 ∑_{k=0}^{n}(−1)^{m+k+1}q^{\binom{m+k+1}{2}} \frac{d_{m+k}(q)}{[m + k]_{q}![m + k + 1]_{q}!} + ∑_{k=0}^{n} \frac{q^{2\binom{m+k+1}{2}}}{[m + k + 1]_{q}!^{2}} , \end{matrix}

or

\begin{matrix}∑_{k=1}^{n+1} \frac{d_{m+k}(q)^{2}}{[m + k]_{q}!^{2}} = ∑_{k=0}^{n} \frac{d_{m+k}(q)^{2}}{[m + k]_{q}!^{2}} \\ + 2 ∑_{k=0}^{n}(−1)^{m+k+1}q^{\binom{m+k+1}{2}} \frac{d_{m+k}(q)}{[m + k]_{q}![m + k + 1]_{q}!} + ∑_{k=1}^{n+1} \frac{q^{2\binom{m+k}{2}}}{[m + k]_{q}!^{2}} . \end{matrix}

By simplifying, we get the identity

\begin{matrix}\frac{d_{m+n+1}(q)^{2}}{[m + n + 1]_{q}!^{2}} = \frac{d_{m}(q)^{2}}{[m]_{q}!^{2}} + 2 ∑_{k=0}^{n}(−1)^{m+k+1}q^{\binom{m+k+1}{2}} \frac{d_{m+k}(q)}{[m + k]_{q}![m + k + 1]_{q}!} \\ + ∑_{k=0}^{n} \frac{q^{2\binom{m+k}{2}}}{[m + k]_{q}!^{2}} + \frac{q^{2\binom{m+n+1}{2}}}{[m + n + 1]_{q}!^{2}} − \frac{q^{2\binom{m}{2}}}{[m]_{q}!^{2}} \end{matrix}

which yields identity (35) at once.

5 q-exponential series

Many identities can be obtained by using the q-exponential generating series. Recall that the product of two q-exponential series f(t) = ∑_{n≥0} f_{n} \frac{t^{n}}{[n]_{q}!} and g(t) = ∑_{n≥0} g_{n} \frac{t^{n}}{[n]_{q}!} is given by

f(t) · g(t) = ∑_{n≥0} (∑_{k=0}^{n} \binom{n}{k}_{q}f_{k}g_{n−k}) \frac{t^{n}}{[n]_{q}!},

and that the q-derivative (Jackson’s derivative) 𝔇_{q} of a q-exponential generating series f(t) = ∑_{n≥0} f_{n} \frac{t^{n}}{[n]_{q}!} is defined [16, 17, 18] by the formula

𝔇_{q}f(t) = \frac{f(qt) − f(t)}{(q − 1)t} = ∑_{n≥0} f_{n+1} \frac{t^{n}}{[n]_{q}!} .

The q-exponential series (Jackson’s q-exponential) [16]

E_{q}(t) = ∑_{n≥0} \frac{t^{n}}{[n]_{q}!} = ∏_{k≥0} \frac{1}{1 + (q − 1)q^{k}t}  (37)

is the eigenfunction of the q-derivative, that is,

𝔇_{q}E_{q}(λt) = λE_{q}(t) .

In particular, since 𝔇_{q}E_{q}(t) = E_{q}(t), we have the relation

E_{q}(qt) = (1 − (1 − q)t) E_{q}(t) .  (38)

Consequently, considering the q-Pochhammer symbol (x; q)_{m} = (1−x)(1−qx) ⋯ (1−q^{m−1}x), we have, for every m ∈ ℕ, the identity

E_{q}(q^{m}t) = ∏_{k=0}^{m−1}(1 − (1 − q)q^{k}t) · E_{q}(t) = ((1 − q)t; q)_{m} E_{q}(t) .  (39)

Moreover, the inverse of the q-exponential series is

E_{q}(t)^{−1} = ∑_{n≥0}(−1)^{n}q^{\binom{n}{2}} \frac{t^{n}}{[n]_{q}!}  (40)

and we have the identities [30]

E_{q}(−t) E_{q^{−1}}(t) = 1  (41)
E_{q}(t) E_{q}(−t) = E_{q^{2}}(\frac{1 − q}{1 + q} t^{2}) .  (42)

By definition (4) and series (40), we have at once that the q-exponential generating series of the q-derangement numbers is

D_{q}(t) = ∑_{n≥0} d_{n}(q)\frac{t^{n}}{[n]_{q}!} = \frac{E_{q}(t)^{−1}}{1 − t} .  (43)

We consider the following q-polynomials:

• the q-Pochhammer symbol

(x; q)_{n} = (1 − x)(1 − qx) ⋯ (1 − q^{n−1}x) = ∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{k}q^{\binom{k}{2}}x^{k} ,  (44)

• the Gaussian polynomials [13, 14, 9]

g_{n}(q; x) = (x − 1)(x − q) ⋯ (x − q^{n−1}) = ∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{n−k}q^{\binom{n−k}{2}}x^{k} ,

• the q-Hermite polynomials (or Rogers-Szegő polynomials) ([29, 4, 1, 13], [27, p. 180])

H_{n}(q; x) = ∑_{k=0}^{n} \binom{n}{k}_{q}x^{k}

and the Galois numbers [13, 26]

G_{n}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q} ,  (45)

• the q-Carlitz polynomials (or Al-Salam-Carlitz polynomials) ([2], [8, p. 195], [15, 6, 19])

U_{n}^{(α)}(q; x) = ∑_{k=0}^{n} \binom{n}{k}_{q}(−α)^{n−k}g_{k}(x) ,

having q-exponential generating series

P_{q}(x, t) = ∑_{n≥0}(x; q)_{n} \frac{t^{n}}{[n]_{q}!} = \frac{E_{q}(t)}{E_{q}(xt)} = E_{q}(t) E_{q}(xt)^{−1}  (46)
g_{q}(x, t) = ∑_{n≥0} g_{n}(q; x)\frac{t^{n}}{[n]_{q}!} = \frac{E_{q}(xt)}{E_{q}(t)} = E_{q}(t)^{−1}E_{q}(xt)  (47)
H_{q}(x, t) = ∑_{n≥0} H_{n}(q; x)\frac{t^{n}}{[n]_{q}!} = E_{q}(t) E_{q}(xt)  (48)
G_{q}(t) = ∑_{n≥0} G_{n}(q)\frac{t^{n}}{[n]_{q}!} = E_{q}(t)^{2}  (49)
U_{q}(x, t) = ∑_{n≥0} U_{n}^{(α)}(q; x)\frac{t^{n}}{[n]_{q}!} = \frac{E_{q}(xt)}{E_{q}(t)E_{q}(αt)} = E_{q}(αt)^{−1}g_{q}(x, t) .  (50)

Using the properties of the q-exponential series, we have at once the following results. Theorem 16. We have the identities

∑_{k=0}^{n} \binom{n}{k}_{q}d_{n−k}(q) (x; q)_{k} = ∑_{k=0}^{n} \binom{n}{k}_{q}[n − k]_{q}! (−1)^{k}q^{\binom{k}{2}}x^{k}  (51)
∑_{k=0}^{n} \binom{n}{k}_{q}d_{n−k}(q) x^{k} = ∑_{k=0}^{n} \binom{n}{k}_{q}[n − k]_{q}! g_{k}(q; x)  (52)
∑_{k=0}^{n} \binom{n}{k}_{q}d_{n−k}(q) G_{k}(q, x) = ∑_{k=0}^{n} \binom{n}{k}_{q}[n − k]_{q}! x^{k}  (53)
∑_{k=0}^{n} \binom{n}{k}_{q}α^{n−k}d_{n−k}(q) g_{k}(x) = ∑_{k=0}^{n} \binom{n}{k}_{q}α^{n−k}[n − k]_{q}! U_{k}^{(α)}(q; x) .  (54)

Proof. By series (43), (46), (47), (48), (50) and (40), we have the identities

D_{q}(t) P_{q}(x, t) = \frac{E_{q}(xt)^{−1}}{1 − t}

D_{q}(t) E_{q}(x, t) = \frac{g_{q}(x, t)}{1 − t}

D_{q}(t) H_{q}(x, t) = \frac{E_{q}(xt)}{1 − t}

D_{q}(αt) g_{q}(x, t) = \frac{U_{q}^{(α)}(xt)}{1 − αt}

which are equivalent to identities (51), (52), (53) and (54), respectively.

Moreover, we also have the next result. Theorem 17. We have the identity

∑_{k=0}^{n}(−1)^{k} \frac{d_{k}(q)}{[k]_{q}!} \frac{d_{n−k}(q^{−1})}{[n − k]_{q^{−1}}!} = \frac{1 + (−1)^{n}}{2}  (55)

or, equivalently,

∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{k}d_{k}(q) d_{n−k}(q^{−1}) = \frac{1 + (−1)^{n}}{2} [n]_{q}! .  (56)

Proof. By identity (41), we have

D_{q}(−t) D_{q^{−1}}(t) = \frac{E_{q}(−t) E_{q^{−1}}(t)}{(1 − t)(1 + t)} = \frac{1}{1 − t^{2}} .

Now we have

D_{q}(−t) D_{q^{−1}}(t) = ∑_{i≥0}(−1)^{i}d_{i}(q)\frac{t^{i}}{[i]_{q}!} ∑_{j≥0} d_{j}(q^{−1})\frac{t^{j}}{[j]_{q^{−1}}!} = ∑_{i,j≥0}(−1)^{i} \frac{d_{i}(q)}{[i]_{q}!} \frac{d_{j}(q^{−1})}{[j]_{q^{−1}}!} t^{i+j} .

Setting i + j = n and replacing i by k, we have

D_{q}(−t) D_{q^{−1}}(t) = ∑_{n≥0} (∑_{k=0}^{n}(−1)^{k} \frac{d_{k}(q)}{[k]_{q}!} \frac{d_{n−k}(q^{−1})}{[n − k]_{q^{−1}}!}) t^{n} .

Hence, we have the identity

∑_{n≥0} (∑_{k=0}^{n}(−1)^{k} \frac{d_{k}(q)}{[k]_{q}!} \frac{d_{n−k}(q^{−1})}{[n − k]_{q^{−1}}!}) t^{n} = ∑_{n≥0} \frac{1 + (−1)^{n}}{2} t^{n}

and this yields identity (55). This identity and [n]_{q^{−1}}! = [n]_{q}! q^{−\binom{n}{2}}, immediately yield identity (56).

Theorem 18. We have the identity

∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{k}d_{k}(q) d_{n−k}(q) = \frac{1 + (−1)^{n}}{2} ∑_{k=0}^{n/2}(−1)^{k}q^{k^{2}−k} (\frac{1 − q}{1 + q} )^{k} \frac{[n]_{q}!}{[k]_{q^{2}}!} .  (57)

Proof. By identity (42), we have

D_{q}(t)D_{q}(−t) = \frac{E_{q}(t)^{−1}E_{q}(−t)^{−1}}{(1 − t)(1 + t)}

= \frac{1}{1 − t^{2}} E_{q^{2}}(\frac{1 − q}{1 + q} t^{2})^{−1}

= ∑_{i≥0} t^{2i} · ∑_{k≥0}(−1)^{k}q^{2\binom{k}{2}} (\frac{1 − q}{1 + q} )^{k} \frac{t^{2k}}{[k]_{q^{2}}!}

= ∑_{i,k≥0}(−1)^{k}q^{k^{2}−k} (\frac{1 − q}{1 + q} )^{k} \frac{[2i + 2k]_{q}!}{[k]_{q^{2}}!} \frac{t^{2i+2k}}{[2i + 2k]_{q}!}

= ∑_{n≥0} (∑_{k=0}^{n}(−1)^{k}q^{k^{2}−k} (\frac{1 − q}{1 + q} )^{k} \frac{[2n]_{q}!}{[k]_{q^{2}}!}) \frac{t^{2n}}{[2n]_{q}!}

= ∑_{n≥0} (\frac{1 + (−1)^{n}}{2} ∑_{k=0}^{n/2}(−1)^{k}q^{k^{2}−k} (\frac{1 − q}{1 + q} )^{k} \frac{[n]_{q}!}{[k]_{q^{2}}!}) \frac{t^{n}}{[n]_{q}!} .

Taking the coefficients of \frac{t^{n}}{[n]_{q}!} in the first and in the last series, we have identity (57).

Recall that for the q-binomial coefficients we have the q-series

∑_{n≥0} \binom{m + n}{m}_{q}t^{n} = \frac{1}{(1 − t)(1 − qt)(1 − q^{2}t) ⋯ (1 − q^{m}t)} = \frac{1}{(t; q)_{m+1}} .  (58)

Then we have the following result. Theorem 19. For every m, n ∈ ℕ, we have the identities

∑_{k=0}^{n} \binom{n}{k}_{q}\binom{m + k}{m}_{q}[k]_{q}!q^{k}d_{n−k}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}\binom{m + k + 1}{m + 1}_{q}(−1)^{n−k}[k]_{q}!q^{\binom{n−k}{2}}  (59)
∑_{k=0}^{n} \binom{n}{k}_{q}\binom{α + k}{k}[k]_{q}!d_{n−k}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}\binom{α + k + 1}{k}(−1)^{n−k}[k]_{q}!q^{\binom{n−k}{2}} .  (60)

Proof. From the q-series (58), we have the q-exponential series

\frac{1}{(1 − t)(1 − qt) ⋯ (1 − q^{m}t)} = ∑_{n≥0} \binom{m + n}{m}_{q}[n]_{q}!\frac{t^{n}}{[n]_{q}!}
\frac{1}{(1 − qt)(1 − q^{2}t) ⋯ (1 − q^{m+1}t)} = ∑_{n≥0} \binom{m + n}{m}_{q}[n]_{q}!q^{n} \frac{t^{n}}{[n]_{q}!} .

Then, by formula (43), we have the identity

\frac{D_{q}(t)}{(1 − qt)(1 − q^{2}t) ⋯ (1 − q^{m+1}t)} = \frac{E_{q}(t)^{−1}}{(1 − t)(1 − qt)(1 − q^{2}t) ⋯ (1 − q^{m+1}t)}

which is equivalent to identity (59). Similarly, we have the identity

\frac{D_{q}(t)}{(1 − t)^{α+1}} = \frac{E_{q}(t)^{−1}}{(1 − t)^{α+2}}

which is equivalent to identity (60).

To prove the next theorem, we need the following result. Lemma 20. We have the q-exponential series

E_{q}(t)^{−2} = ∑_{n≥0}(−1)^{n}q^{\binom{n}{2}} G_{n}(q^{−1}) \frac{t^{n}}{[n]_{q}!} .  (61)

Proof. By formula (40) and relations (8), the coefficient of \frac{t^{n}}{[n]_{q}!} in the q-exponential series E_{q}(t)^{−2} is

∑_{k=0}^{n} \binom{n}{k}_{q}(−1)^{k}q^{\binom{k}{2}}(−1)^{n−k}q^{\binom{n−k}{2}} = (−1)^{n}q^{\binom{n}{2}} ∑_{k=0}^{n} \binom{n}{k}_{q}q^{−k(n−k)} = (−1)^{n}q^{\binom{n}{2}} ∑_{k=0}^{n} \binom{n}{k}_{q^{−1}}.

By the definition (45) of the Galois numbers, this implies identity (61).

Recall that the q-multiset coefficients are defined by

\begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix}_{q} = \begin{cases}\binom{n + k − 1}{k}_{q}, & if k ≥ 1; \\ 1, & if k = 0 \end{cases}

and that they have q-generating series

∑_{k≥0} \begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix}_{q}t^{k} = \frac{1}{(1 − t)(1 − qt)(1 − q^{2}t) ⋯ (1 − q^{n−1}t)} = \frac{1}{(t; q)_{n}} .  (62)

Theorem 21. For every m, n ∈ ℕ, we have the identity

∑_{k=0}^{n} \binom{n}{k}_{q}q^{mk} d_{k}(q) = [n]_{q}! ∑_{k=0}^{n} \begin{matrix}( \\ ( & {m \atop k} & ) \\ ) \end{matrix}_{q}(1 − q)^{k}q^{m(n−k)} .  (63)

Proof. We have the q-exponential series

L(q; t) = ∑_{n≥0} (∑_{k=0}^{n} \binom{n}{k}_{q}q^{mk} d_{k}(q)) \frac{t^{n}}{[n]_{q}!} = E_{q}(t)D_{q}(q^{m}t) = \frac{E_{q}(t)E_{q}(q^{m}t)^{−1}}{1 − q^{m}t} .

By identity (39), we have

L(q; t) = \frac{E_{q}(t)E_{q}(t)^{−1}}{(1 − q^{m}t)((1 − q)t; q)_{m}} = \frac{1}{1 − q^{m}t} · \frac{1}{((1 − q)t; q)_{m}}

= ∑_{n≥0} ([n]_{q}! ∑_{k=0}^{n} \begin{matrix}( \\ ( & {m \atop k} & ) \\ ) \end{matrix}_{q}(1 − q)^{k}q^{m(n−k)}) \frac{t^{n}}{[n]_{q}!}

from which we have at once identity (63).

We conclude this section proving the following elementary identity involving the q-Pochhammer symbol. Theorem 22. We have the identity

\frac{d_{n+2}(q)}{[n + 1]_{q}!} \frac{x^{n+1}}{(qx; q)_{n+1}} + ∑_{k=0}^{n} \frac{d_{k+1}(q) + d_{k}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k}} = ∑_{k=0}^{n} \frac{d_{k+1}(q) x^{k+1} + d_{k}(q) x^{k}}{[k]_{q}!(qx; q)_{k+1}} . (64)

Proof. By recurrence (6), we have

d_{k+2}(q) x = [k + 1]_{q} d_{k+1}(q) x + [k + 1]_{q} q^{k+1}x d_{k}(q)
= [k + 1]_{q} d_{k+1}(q) x + [k + 1]_{q} d_{k}(q) − [k + 1]_{q} (1 − q^{k+1}x) d_{k}(q),

and consequently

\frac{d_{k+2}(q)}{[k + 1]_{q}!} \frac{x^{k+1}}{(qx; q)_{k+1}} = \frac{d_{k+1}(q)}{[k]_{q}!} \frac{x^{k+1}}{(qx; q)_{k+1}} + \frac{d_{k}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k+1}} − \frac{d_{k}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k}} .

Then we have

∑_{k=0}^{n} \frac{d_{k+2}(q)}{[k + 1]_{q}!} \frac{x^{k+1}}{(qx; q)_{k+1}} = ∑_{k=0}^{n} \frac{d_{k+1}(q)}{[k]_{q}!} \frac{x^{k+1}}{(qx; q)_{k+1}} + ∑_{k=0}^{n} \frac{d_{k}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k+1}} − ∑_{k=0}^{n} \frac{d_{k}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k}} ,

which is

∑_{k=1}^{n+1} \frac{d_{k+1}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k}} + ∑_{k=0}^{n} \frac{d_{k}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k}} = ∑_{k=0}^{n} \frac{d_{k+1}(q)}{[k]_{q}!} \frac{x^{k+1}}{(qx; q)_{k+1}} + ∑_{k=0}^{n} \frac{d_{k}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k+1}} ,

or

\frac{d_{n+2}(q)}{[n + 1]_{q}!} \frac{x^{n+1}}{(qx; q)_{n+1}} + ∑_{k=0}^{n} \frac{d_{k+1}(q) + d_{k}(q)}{[k]_{q}!} \frac{x^{k}}{(qx; q)_{k}} = ∑_{k=0}^{n} \frac{d_{k+1}(q) x^{k+1} + d_{k}(q) x^{k}}{[k]_{q}!(qx; q)_{k+1}} .

This is the claimed identity.

6 Determinantal identities

Since the q-derangement numbers satisfy a three-term recurrence, they can be represented in terms of tridiagonal determinants (or continuants ([20, pp. 516–525], [31])).

Theorem 23. We have the identity

d_{n}(q) = |\begin{matrix}[0]_{q} & −q \\ [1]_{q} & [1]_{q} & −q^{2} \\ & [2]_{q} & [2]_{q} & −q^{3} \\ & & ... & ... & ... \\ & & & [n − 2]_{q} & [n − 2]_{q} & −q^{n−1} \\ & & & & [n − 1]_{q} & [n − 1]_{q} \end{matrix}|_{n×n} .  (65)

Proof. The tridiagonal determinants in formula (65) satisfy recurrence (6) with the appropriate initial values. This implies at once the claimed identity.

The q-derangement numbers can also be represented in terms of Hessenberg determinants [31, p. 90], as follows.

Theorem 24. Consider the n × n lower Hessenberg matrix

A_{n}(q) = [\begin{matrix}a_{00}(q) & −1 & 0 & 0 & ⋯ & 0 \\ a_{10}(q) & a_{11}(q) & −1 & 0 & ⋯ & 0 \\ a_{20}(q) & a_{21}(q) & a_{22}(q) & −1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ a_{n−2,1}(q) & a_{n−2,2}(q) & a_{n−2,3}(q) & a_{n−2,4}(q) & ⋯ & −1 \\ a_{n−1,1}(q) & a_{n−1,2}(q) & a_{n−1,3}(q) & a_{n−1,4}(q) & ⋯ & a_{n−1,n−1}(q) \end{matrix}]

where

a_{i,j}(q) = \begin{cases}\binom{i}{j}_{q}a_{i−j}(q), & if i ≥ j; \\ −1, & if i = j − 1; \\ 0, & otherwise \end{cases}

where

a_{k}(q) = \frac{q}{2q − 1} (q^{n} − (1 − q)^{n}) [n]_{q}! .  (66)

Then we have the identity

d_{n}(q) = det A_{n}(q) .  (67)

Proof. Let b_{n}(q) = det A_{n}(q). By expanding the determinant along the last column, we get the recurrence

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

with initial value b_{0}(q) = 1. Hence, considering the q-exponential generating series

a(q; t) = ∑_{n≥0} a_{n}(q)\frac{t^{n}}{[n]_{q}!} and b(q; t) = ∑_{n≥0} b_{n}(q)\frac{t^{n}}{[n]_{q}!} ,

we have the q-differential equation

𝔇_{q}b(q; t) = a(q; t) b(q; t) .

If b(q; t) = D_{q}(t), then b_{0}(q) = d_{0}(q) = 1, as requested, and

a(q; t) = \frac{𝔇_{q}b(q; t)}{b(q; t)} = \frac{𝔇_{q}D_{q}(t)}{D_{q}(t)} .

By series (43) and relation (38), we have

𝔇_{q}D_{q}(t) = \frac{D_{q}(qt) − D_{q}(t)}{(q − 1)t}

= \frac{1}{(q − 1)t} (\frac{E_{q}(qt)^{−1}}{1 − qt} − \frac{E_{q}(t)^{−1}}{1 − t} )

= \frac{1}{(q − 1)t} (\frac{E_{q}(t)^{−1}}{(1 − qt)(1 + (q − 1)t)} − \frac{E_{q}(t)^{−1}}{1 − t} )

= \frac{qt E_{q}(t)^{−1}}{(1 − t)(1 − qt)(1 + (q − 1)t)},

which is

𝔇_{q}D_{q}(t) = \frac{qt}{(1 − qt)(1 + (q − 1)t)} D_{q}(t) .

Therefore, we have

a(q; t) = \frac{qt}{(1 − qt)(1 + (q − 1)t)} = \frac{q}{2q − 1} \frac{1}{1 − qt} − \frac{q}{2q − 1} \frac{1}{1 − (1 − q)t} .

This decomposition yields identity (66), and, consequently, this proves identity (67).

7 Final remarks

In the literature, there are also other q-analogues for the derangement numbers. For instance, we have the q-derangement numbers [11]

D_{n}(q) = ∑_{k=0}^{n} \binom{n}{k}_{q}[n − k]_{q}! (−1)^{k}  (68)

satisfying the recurrences

D_{n+1}(q) = [n + 1]_{q} D_{n}(q) + (−1)^{n+1}  (69)
D_{n+2}(q) = q [n + 1]_{q} D_{n+1}(q) + [n + 1]_{q} D_{n}(q)  (70)

with initial conditions D_{0}(q) = 1 and D_{1}(q) = 0. Moreover, they have q-exponential generating series

∑_{n≥0} D_{n}(q)\frac{t^{n}}{[n]_{q}!} = \frac{E_{q}(−t)}{1 − t} .

The q-numbers d_{n}(q) and D_{n}(q) are not independent, as shown in the next theorem.

Theorem 25. For every n ∈ ℕ, we have the relation

d_{n}(q^{−1}) = q^{−\binom{n}{2}}D_{n}(q) .  (71)

Moreover, we have the formulas

d_{n}(q) = ∑_{k=0}^{n}(−1)^{n−k}q^{\binom{n−k}{2}} \frac{(q^{n−k+1}; q)_{k}}{(1 − q)^{k}}  (72)

D_{n}(q) = ∑_{k=0}^{n}(−1)^{n−k} \frac{(q^{n−k+1}; q)_{k}}{(1 − q)^{k}} .  (73)

Proof. By formula (4) and relations (8), we have

d_{n}(q^{−1}) = ∑_{k=0}^{n} \binom{n}{k}_{q^{−1}}[n − k]_{q^{−1}}! (−1)^{k}q^{−\binom{k}{2}}

= ∑_{k=0}^{n} \binom{n}{k}_{q}q^{−k(n−k)}[n − k]_{q}!q^{−\binom{n−k}{2}} (−1)^{k}q^{−\binom{k}{2}}

= q^{−\binom{n}{2}} ∑_{k=0}^{n} \binom{n}{k}_{q}[n − k]_{q}! (−1)^{k} .

By formula (68), this is relation (71).

Since [n]_{q}! = \frac{(q;q)_{n}}{(1−q)^{n}}, from definition (4) we have

d_{n}(q) = ∑_{k=0}^{n} \frac{[n]_{q}!}{[k]_{q}!} (−1)^{k}q^{\binom{k}{2}} = ∑_{k=0}^{n} \frac{(−1)^{k}q^{\binom{k}{2}}}{(1 − q)^{n−k}} \frac{(q; q)_{n}}{(q; q)_{k}} = ∑_{k=0}^{n} \frac{(−1)^{k}q^{\binom{k}{2}}}{(1 − q)^{n−k}} (q^{k+1}; q)_{n−k} .

This is equivalent to identity (72). Similarly, formula (68) can be rewritten as formula (73).

We also have the following result. Theorem 26. We have the ordinary generating series

d(q; t) = ∑_{n≥0} d_{n}(q) t^{n} = ∑_{k≥0} \frac{(−1)^{k}q^{\binom{k+1}{2}}}{(1 − q)^{k}} \frac{t^{k}Q(q; q^{k}t)}{(\frac{t}{1−q}; q)_{k+1}}  (74)
D(q; t) = ∑_{n≥0} D_{n}(q) t^{n} = ∑_{k≥0} \frac{(−1)^{k}q^{\binom{k+1}{2}}}{(1 − q)^{k}} \frac{t^{k}}{(1 + q^{k}t)(\frac{t}{1−q}; q)_{k+1}}  (75)

where

Q(q; t) = ∑_{n≥0}(−1)^{n}q^{\binom{n}{2}} t^{n} .

Proof. From recurrence (5), we have

∑_{n≥0} d_{n+1}(q) t^{n} = ∑_{n≥0} \frac{1 − q^{n+1}}{1 − q} d_{n}(q) t^{n} + ∑_{n≥0}(−1)^{n+1}q^{\binom{n+1}{2}} t^{n},

which is

\frac{d(q; t) − d_{0}(q)}{t} = \frac{1}{1 − q} (d(q; t) − qd(q; qt)) + \frac{Q(q; t) − 1}{t},

or

d(q; t) − 1 = \frac{t}{1 − q} d(q; t) − \frac{qt}{1 − q} d(q; qt) + Q(q; t) − 1,

or

(1 − \frac{t}{1 − q} ) d(q; t) = Q(q; t) − \frac{qt}{1 − q} d(q; qt),

which is

d(q; t) = \frac{Q(q; t)}{1 − \frac{t}{1−q}} − \frac{qt}{(1 − q)(1 − \frac{t}{1−q})} d(q; qt) .

By repeatedly applying this formula, we get

d(q; t) = ∑_{k=0}^{n} \frac{(−1)^{k}q^{\binom{k+1}{2}}}{(1 − q)^{k}} \frac{t^{k} Q(q; q^{k}t)}{(1 − \frac{t}{1−q})(1 − \frac{qt}{1−q}) ⋯ (1 − \frac{q^{k}t}{1−q})}

+ \frac{(−1)^{n+1}q^{\binom{n+2}{2}}}{(1 − q)^{n+1}} \frac{t^{n+1}}{(1 − \frac{t}{1−q})(1 − \frac{qt}{1−q}) ⋯ (1 − \frac{q^{n}t}{1−q})} d(q; q^{n+1}t)

= ∑_{k=0}^{n} \frac{(−1)^{k}q^{\binom{k+1}{2}}}{(1 − q)^{k}} \frac{t^{k} Q(q; q^{k}t)}{(\frac{t}{1−q}; q)_{k+1}} + \frac{(−1)^{n+1}q^{\binom{n+2}{2}}}{(1 − q)^{n+1}} \frac{t^{n+1}}{(\frac{t}{1−q}; q)_{n+1}} d(q; q^{n+1}t) .

Taking the limit for n tending to +∞, we obtain series (74).

Similarly, from recurrence (69), we have

∑_{n≥0} D_{n+1}(q) t^{n} = ∑_{n≥0} \frac{1 − q^{n+1}}{1 − q} D_{n}(q) t^{n} + ∑_{n≥0}(−1)^{n+1}t^{n},

which is

\frac{D(q; t) − D_{0}(q)}{t} = \frac{1}{1 − q} (D(q; t) − qD(q; qt)) − \frac{1}{1 + t},

or

(1 − \frac{t}{1 − q} ) D(q; t) = \frac{1}{1 + t} − \frac{qt}{1 − q} D(q; qt),

or

D(q; t) = \frac{1}{(1 + t)(1 − \frac{t}{1−q})} − \frac{qt}{(1 − q)(1 − \frac{t}{1−q})}D(q; qt).

By repeatedly applying this formula, we get

D(q; t) = ∑_{k=0}^{n} \frac{(−1)^{k}q^{\binom{k+1}{2}}}{(1 − q)^{k}} \frac{t^{k}}{(1 + q^{k}t)(1 − \frac{t}{1−q})(1 − \frac{qt}{1−q}) ⋯ (1 − \frac{q^{k}t}{1−q})}

+ \frac{(−1)^{n+1}q^{\binom{n+2}{2}}}{(1 − q)^{n+1}} \frac{t^{n+1}}{(1 − \frac{t}{1−q})(1 − \frac{qt}{1−q}) ⋯ (1 − \frac{q^{n}t}{1−q})} D(q; q^{n+1}t)

= ∑_{k=0}^{n} \frac{(−1)^{k}q^{\binom{k+1}{2}}}{(1 − q)^{k}} \frac{t^{k}}{(1 + q^{k}t)(\frac{t}{1−q}; q)_{k+1}}

+ \frac{(−1)^{n+1}q^{\binom{n+2}{2}}}{(1 − q)^{n+1}} \frac{t^{n+1}}{(\frac{t}{1−q}; q)_{n+1}} D(q; q^{n+1}t) .

Taking the limit for n tending to +∞, we obtain series (75).

References

[1] W. A. Al-Salam and L. Carlitz, A q-analog of a formula of Toscano, Boll. Un. Mat. Ital. (3) 12 (1957), 414–417.

[2] W. A. Al-Salam and L. Carlitz, Some orthogonal q-polynomials, Math. Nachr. 30 (1965), 47-61.

[3] S. Capparelli, M. M. Ferrari, E. Munarini, and N. Zagaglia Salvi, A generalization of the “Problème des Rencontres”, J. Integer Sequences 21 (2018), Article 18.2.8.

[4] L. Carlitz, Some polynomials related to the theta functions, Ann. Mat. Pura Appl. 41 (1955), 359–373.

[5] W. Y. C. Chen and G.-C. Rota, q-analogs of the inclusion-exclusion principle and permutations with restricted position, Discrete Math. 104 (1992), 7–22.

[6] W. Y. C. Chen, H. L. Saad, and L. H. Sun, An operator approach to the Al-Salam–Carlitz polynomials, J. Math. Phys. 51 (2010), Paper 043502.

[7] W. Y. C. Chen and E. X. W. Xia, The ratio monotonicity of the q-derangement numbers, Discrete Math. 311 (2011), 393–397.

[8] T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978.

[9] 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.

[10] M. M. Ferrari and E. Munarini, Decomposition of some Hankel matrices generated by the generalized rencontres polynomials, Linear Algebra Appl. 567 (2019), 180-–201.

[11] A. M. Garsia and J. Remmel, A combinatorial interpretation of q-derangement and q-Laguerre numbers, Europ. J. Combin. 1 (1980), 47–5.

[12] C. F. Gauss, Summatio quarumdam serierum singularium, Comm. soc. reg. sci. Gottingensis rec. 1 (1808), 147–186. Reprinted in Gauss’s Werke 2 (1863), 9–45.

[13] J. Goldman and G.-C. Rota, The number of subspaces of a vector space, Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968) Academic Press, 1969, pp. 75–83.

[14] J. Goldman and G.-C. Rota, On the foundations of combinatorial theory. IV. Finite vector spaces and Eulerian generating functions, Studies in Appl. Math. 49 (1970), 239–258.

[15] M. E. H. Ismail, Classical and Quantum Orthogonal Polynomials in One Variable, Cambridge University Press, 2005.

[16] F. H. Jackson, A basic-sine and cosine with symbolical solutions of certain differential equations, Proc. Edinburgh Math. Soc. 22 (1904), 28–39.

[17] F. H. Jackson, On q-functions and a certain difference operator, Trans. Roy. Soc. Edin. 46 (1908), 253–281.

[18] F. H. Jackson, q-Difference equations, Am. J. Math. 32 (1910), 305–314.

[19] D. Kim, On combinatorics of Al-Salam Carlitz polynomials, European J. Combin. 18 (1997), 295–302.

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

[21] E. Munarini, Shifting property for Riordan, Sheffer and connection constants matrices, J. Integer Sequencesf 20 (2017), Article 17.8.2.

[22] E. Munarini, Some q-binomial identities involving the generalized q-Fibonacci numbers, Integers 18 (2018), Paper No. A76.

[23] E. Munarini, Combinatorial identities for Appell polynomials, Appl. Anal. Discrete Math. 12 (2018), 362–388.

[24] E. Munarini, Callan-like identities, Online J. Anal. Comb. 14 (2019), Article #06.

[25] E. Munarini, An operational approach to the generalized rencontres polynomials, Kragujevac J. Math. 46 (2022), 461–469.

[26] A. Nijenhuis, A. E. Solow, and H. S. Wilf, Bijective methods in the theory of finite vector spaces, J. Combin. Theory Ser. A 37 (1984), 80–84.

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

[28] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2020. Available

    at https://oeis.org/.

[29] G. Szegő, Orthogonal Polynomials, Amer. Math. Soc. Colloquium Publication 23, Amer. Math. Soc., 1975.

[30] M. R. Ubriaco, Time evolution in quantum mechanics on the quantum line, Phys. Lett. A 163 (1992), 1–4.

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

[32] M. L. Wachs, On q-derangement numbers, Proc. Amer. Math. Soc. 106 (1989), 273–278.

[33] X.-D. Zhang, On the spiral property of the q-derangement numbers, Discrete Math. 159 (1996), 295–298.

2010 Mathematics Subject Classification: Primary 05A30; Secondary 11B65, 05A19, 11B73, 33B10, 39A13. Keywords: combinatorial sum, q-binomial sum, q-derangement number, q-Stirling number, q-Bell number, connection constant, q-exponential generating series.

(Concerned with sequences \underline{A000110} and \underline{A000166}.) Received October 27 2019; revised version received February 18 2020; March 11 2020. Published in Journal of Integer Sequences, March 17 2020. Return to Journal of Integer Sequences home page.