# Analytic aspects of $q,r$-analogue of poly-Stirling numbers of both kinds

Takao Komatsu
Department of Mathematical Sciences, School of Science
Zhejiang Sci-Tech University
Hangzhou 310018 China
<EMAIL_ADDRESS>

Eli Bagno
Jerusalem College of Technology
21 HaVaad HaLeumi St.
Jerusalem, Israel
<EMAIL_ADDRESS>

David Garber
Holon Institute of Technology
52 Golomb St., P.O.Box 305
5810201 Holon, Israel
<EMAIL_ADDRESS>
###### Abstract

This paper deals with analytical aspects of several generalizations of
Stirling number of both kinds. We generalize the Comtet and Lancaster
theorems, which present conditions that are equivalent to the definition of
ordinary Stirling numbers of both kinds, to the case of the $q,r$-poly
Stirling numbers (which are $q$-analogues of the restricted Stirling numbers
defined by Broder and having a polynomial values appearing in their defining
recursion).

Keywords: $q,r$-poly-Stirling numbers, $q$-calculus, $r$-Stirling numbers,
Comtet Theorem, Lancaster Theorem, Coxeter groups of type $B$, set partitions
of type $B$

MR Subject Classifications: Primary: 05A15; Secondary: 05A18, 05A19, 05A30,
11B73

##  1 Introduction

The Stirling number of the second kind, denoted $S_{n,k}$, counts the number
of partitions of the set $[n]:=\\{1,\dots,n\\}$ into $k$ non-empty subsets
(see [22, page 81]). Stirling numbers of the second kind arise in a variety of
problems in enumerative combinatorics; they have many combinatorial
interpretations, and have been generalized in various contexts and in
different ways.

Stirling numbers also have a vast algebraic background and the connection
between the algebraic and the combinatorial aspects is via the well-known
recursion of these numbers:

$S_{n,k}=S_{n-1,k-1}+kS_{n-1,k}.$ (1)

###  1.1 The Comtet and Lancaster approaches to Stirling numbers

Comtet [6] showed that the Stirling numbers of the second kind can be
presented in several equivalent algebraic ways. We provide here the content of
Comtet’s theorem, following the presentation of Wagner [24, Section 7.2,
Theorem 7.2.1]:

######  Theorem 1.1.

Let $(b_{n})_{n\geq 0}$ be a sequence of complex numbers. The following are
equivalent characterizations for an array of numbers $(A_{n,k})_{n,k\geq 0}$:

  1. (1)

Defining equation: For each $n\geq 0$:

$x^{n}=\sum\limits_{k\geq 0}A_{n,k}\cdot(x-b_{0})(x-b_{1})\cdots(x-b_{k-1}).$

  2. (2)

Recursion: For each $n\geq k>0$:

$A_{n,k}=A_{n-1,k-1}+b_{k}A_{n-1,k}$

with the boundary conditions: $A_{n,0}=b_{0}^{n}$ and $A_{0,k}=\delta_{0k}$
for each $n\geq k\geq 0$.

  3. (3)

Complete recursion: For $n\geq k>0$:

$A_{n,k}=\sum\limits_{j=k}^{n}A_{j-1,k-1}b_{k}^{n-j},$

subject to the same boundary conditions as in Condition (2).

  4. (4)

Ordinary generating function: For each $k\geq 0$:

$\sum\limits_{n\geq 0}A_{n,k}x^{n}=\frac{x^{k}}{(1-b_{0}x)\cdots(1-b_{k}x)}.$

  5. (5)

Explicit formula: For each $n\geq k\geq 0$:

$A_{n,k}=\sum\limits_{d_{0}+d_{1}+\cdots+d_{k}=n-k\atop d_{i}\geq
0}b_{0}^{d_{0}}\cdots b_{k}^{d_{k}}.$

Note that if $b_{k}=1$ for all $k$, the numbers $A_{n,k}$ are the binomial
coefficients $n\choose k$, and if $b_{k}=k$ for all $k$, then the numbers
$A_{n,k}$ are the Stirling numbers of the second kind.

The (unsigned) Stirling number of the first kind, denoted $c_{n,k}$, counts
the number of permutations of the set $[n]$ having $k$ cycles (see [22, page
32]).

The recursion satisfied by the these numbers is:

$c_{n,k}=c_{n-1,k-1}+(n-1)c_{n-1,k}.$ (2)

The (signed) Stirling number of the first kind, denoted $s_{n,k}$, is defined
by the recursion:

$s_{n,k}=s_{n-1,k-1}-(n-1)s_{n-1,k}.$ (3)

The signed Stirling numbers of the first kind satisfy some orthogonality
relations with the Stirling numbers of the second kind (see e.g. [10, p.
264]).

Back to the unsigned Stirling numbers of the first kind, an analogue of
Comtet’s theorem for these numbers was given by Lancaster [12], see also [13]
and Wagner’s book [24, Section 7.2] (we fix $b_{i}=0$ in the original
formulation of Lancaster):

######  Theorem 1.2 (Lancaster).

Let $(a_{n})_{n\geq 0}$ be a sequence of complex numbers. The following are
equivalent characterizations for $(c_{n,k})_{n,k\geq 0}$:

  1. (1)

Defining equation/generating function:

$(x+a_{0})(x+a_{1})\cdots(x+a_{n-1}){=}\sum\limits_{k=0}^{n}c_{n,k}\cdot
x^{k}.$

  2. (2)

Recursion: For each $n\geq k\geq 0$:

$c_{n,k}=c_{n-1,k-1}+a_{n-1}c_{n-1,k}$

with the boundary conditions: $c_{n,0}=a_{0}a_{1}\cdots a_{n-1}$ and
$c_{0,k}=\delta_{0k}$.

  3. (3)

Complete recursion: For $n\geq k\geq 0$:

$c_{n,k}=\sum\limits_{j=k}^{n}c_{j-1,k-1}\prod\limits_{i=j}^{n-1}a_{i},$

subject to the same boundary conditions as in Condition (2).

###  1.2 Broder’s restricted Stirling numbers

Broder [4] defined an $r$-version to both kinds of Stirling numbers, which
counts set partitions such that the first $r$ elements are placed in $r$
distinguished parts of the partition in the case of the second kind platform,
and the permutations of $[n]$ which are decomposed in $k$ cycles such that the
elements $1,\dots,r$ are in distinguished cycles in the case of the first kind
platform.

The ordinary Stirling numbers of the second kind can also be interpreted as
the number of elements of a constant rank in the intersection lattice of
hyperplane arrangements of Coxeter type $A$. Dolgachev-Lunts [7, p. 755] and
Reiner [19, Section 2] generalized this idea to hyperplane arrangements of
Coxeter type $B$ (in [7], the partitions of type $B$ are counted by
$\tilde{S}(n,k)_{0}$ in their notation). However, the concept of set
partitions of type $B$ has already appeared implicitly in Dowling [8] and also
in Zaslavsky [27] in the form of signed graphs. The Stirling numbers of the
second kind of type $B$ enumerate the set partitions of type $B$; the exact
definitions will be recalled in Section 3.1.

The Stirling numbers were further generalized in various ways, see for example
[1, 3, 5, 9, 14, 15, 17] and many more.

###  1.3 Poly-Stirling numbers

One type of a generalization of the Stirling numbers is obtained by exchanging
$k$ in Equation (1) or $n-1$ in Equation (2) for a value $p(k)$ or $p(n-1)$
(respectively) of a given polynomial $p(x)\in\mathbb{Z}[x]$. In this way, we
get the poly-Stirling numbers (actually one might define the polynomial $p(x)$
also over $\mathbb{C}$ at the expense of losing the nice combinatorial
meaning).

We cite here the definitions of poly-Stirling numbers, as they appear in
Miceli [17]:

######  Definition 1.3.

Given any nonzero polynomial $p(x)\in\mathbb{Z}[x]$, define the (unsigned)
poly-Stirling numbers of the first kind with respect to $p(x)$, denoted by
$c_{n,k}^{p(x)}$, by the recursion:

$c_{n,k}^{p(x)}=c_{n-1,k-1}^{p(x)}+p(n-1)c_{n-1,k}^{p(x)},$

where $c_{0,0}^{p(x)}=1$ and $c_{n,k}^{p(x)}=0$ if either $k>n$ or $k<0$.

In a similar manner, the poly-Stirling numbers of the second kind with respect
to $p(x)$, denoted by $S_{n,k}^{p(x)}$, are defined by the recursion:

$S_{n,k}^{p(x)}=S_{n-1,k-1}^{p(x)}+p(k)S_{n-1,k}^{p(x)},$

where $S_{0,0}^{p(x)}=1$ and $S_{n,k}^{p(x)}=0$ if either $k>n$ or $k<0$.

In the current paper, we follow the work of Miceli [17], who defined two
natural types of $q$-analogues of poly-Stirling numbers, namely taking the
$q$-analogue of $p(x)$ to be either $[p(x)]_{q}$ (type II $q$-poly-Stirling)
or $p([x]_{q})$ (type I $q$-poly-Stirling), where
$[n]_{q}=1+q+\cdots+q^{n-1}=\frac{q^{n}-1}{q-1}$ is the $q$-analogue of the
number $n$.

We further generalize both Miceli’s types $q$-poly-Stirling numbers to
$q,r$-poly Stirling numbers, where the additional $r$ stands for the Broder
generalization [4] mentioned above. Actually, we provide a comprehensive
analysis of these numbers by generalizing the theorems of Comtet and Lancaster
to the $q,r$-poly-Stirling numbers of both kinds (see Theorem 2.2 and Theorem
4.2, respectively).

Furthermore, we present orthogonality relations between the first and the
second kinds $q,r$-poly-Stirling numbers of both types I and II.

We also provide some identities pertaining to sum of powers:
$\displaystyle\sum_{j=r}^{n}\left([p(j)]_{q}\right)^{k}$ and
$\displaystyle\sum_{j=r}^{n}\bigl{(}p([j]_{q})\bigr{)}^{k}$ (see Theorem 5.3
and Theorem 6.4 below), which generalize several results regarding the
ordinary sum of powers $\displaystyle\sum_{j=1}^{n}j^{k}$, see [11, 15, 21,
26].

###  1.4 Organization of the paper

The paper is organized as follows. Section 2 deals with the generalization of
Comtet’s theorem. Section 3 deals with an exponential generating function for
$S_{n,k,r}^{B}$ and we use it to present these numbers as connection constants
between two bases of $\mathbb{R}[x]$.

Section 4 deals with the generalization of Lancaster’s theorem for the
unsigned $q,r$-poly-Stirling numbers of the first kind. In Section 5, we
present the generalization of Lancaster’s theorem for the signed $q,r$-poly-
Stirling numbers of the first kind, and we prove two applications of this
generalization: sum of powers and orthogonality relations. Section 6 deals
with some mixed relations between the two types of $q,r$-poly-Stirling
numbers.

In the appendix, we supply a comprehensive proof of the generalization of
Comtet’s theorem presented in Section 2.

##  2 Type II $q,r$-poly-Stirling numbers of the second kind

In this section, we present a generalization of Comtet’s theorem (Theorem 1.1
above) to the case of type II $q,r$-poly-Stirling numbers of the second kind,
mentioned in the introduction (based on Miceli’s type II $q$-poly-Stirling
number of the second kind [17]).

######  Definition 2.1.

Let $p(x)\in\mathbb{Z}[x]$. The type II $q,r$-poly-Stirling numbers of the
second kind are defined by the recurrence relation:

$S_{n,k,r}^{p(x)}(q)=S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\quad(r\leq
k\leq n,~{}n\geq 1)$ (4)

with $S_{r,r,r}^{p(x)}(q)=1$ and $S_{n,k,r}^{p(x)}(q)=0$ for $k<r$, $k>n$ or
$n<r$.

We present here the generalization of Comtet’s theorem for type II $q,r$-poly-
Stirling numbers of the second kind. For the sake of completeness, the
detailed but routine proof can be found in the Appendix.

######  Theorem 2.2 (Generalization of Comtet’s theorem for type II).

Let $p(n)$ be a polynomial with non-negative integer coefficients and let
$\varphi_{k}(x),\ k\geq r$, be defined by

$\varphi_{r}(x)=1\mbox{ and
}\varphi_{k}(x)=(x-[p(r)]_{q})(x-[p(r+1)]_{q})\cdots(x-[p(k-1)]_{q})\mbox{ \rm
for }k>r.$

The following are equivalent characterizations for
$(S^{p(x)}_{n,k,r}(q))_{n,k,r\mid 0\leq r\leq k\leq n}$ (where for all other
values of the triple $(r,k,n)$, we assume $S^{p(x)}_{n,k,r}(q)=0$):

  1. (1)

Defining equation/Change of bases: For each $n\geq r$:

$x^{n-r}{=}\sum\limits_{k=r}^{n}S^{p(x)}_{n,k,r}(q)\cdot\varphi_{k}(x).$

  2. (2)

Recursion: For each $n\geq k>r$:

$S^{p(x)}_{n,k,r}(q)=S^{p(x)}_{n-1,k-1,r}(q)+[p(k)]_{q}S^{p(x)}_{n-1,k,r}(q)$

with the boundary conditions: $S^{p(x)}_{r,r,r}(q)=1$ and
$S_{n,k,r}^{p(x)}(q)=0$ for $k<r$, $k>n$ or $n<r$.

  3. (3)

Complete recursion: For $n\geq k>r$:

$S^{p(x)}_{n,k,r}(q)=\sum\limits_{j=k}^{n}S^{p(x)}_{j-1,k-1,r}(q)\left([p(k)]_{q}\right)^{n-j},$

subject to the same boundary conditions as in Condition (2).

  4. (4)

Ordinary generating function: For each $k\geq r$:

$\sum\limits_{n=k}^{\infty}S^{p(x)}_{n,k,r}(q)x^{n}=\frac{x^{k}}{(1-[p(r)]_{q}x)\cdots(1-[p(k)]_{q}x)}.$

  5. (5)

Explicit formula: For $r\leq k\leq n$:

$S_{n,k,r}^{p(x)}(q)=\sum\limits_{i_{r}+i_{r+1}+\cdots+i_{k}=n-k\atop
i_{l}\geq
0}\left([p(r)]_{q}\right)^{i_{r}}\cdots\left([p(k)]_{q}\right)^{i_{k}}.$

Condition (5) of Theorem 2.2 can be written in an equivalent form, as follows:

######  Corollary 2.3.

For $r\leq k\leq n$, we have:

$\displaystyle S_{n,k,r}^{p(x)}(q)$
$\displaystyle=\sum_{j_{k-1}=0}^{n-k}\bigl{(}[p(k)]_{q}\bigr{)}^{n-k-
j_{k-1}}\sum_{j_{k-2}=0}^{j_{k-1}}\bigl{(}[p(k-1)]_{q}\bigr{)}^{j_{k-1}-j_{k-2}}$
$\displaystyle\qquad\qquad\cdots\sum_{j_{r+1}=0}^{j_{r+2}}\bigl{(}[p(r+2)]_{q}\bigr{)}^{j_{r+2}-j_{r+1}}\sum_{j_{r}=0}^{j_{r+1}}\bigl{(}[p(r+1)]_{q}\bigr{)}^{j_{r+1}-j_{r}}\bigl{(}[p(r)]_{q}\bigr{)}^{j_{r}}.$

###### Proof.

The right hand side is equivalent to the right hand side of the equation in
Condition (5) of Theorem 2.2 by the following substitutions: $j_{r}=i_{r}$
and$j_{m}=i_{r}+i_{r+1}+\cdots+i_{m}$ for $r<m<k$. ∎

In the next theorem, we present a new way to write $S_{n,k,r}^{p(x)}(q)$,
based on its generating function. We start with a lemma:

######  Lemma 2.4.

For $n\geq k$ and $\ell\geq 2$, we have:

$\frac{d^{n}}{dx^{n}}\left[\frac{x^{k}}{(1-a_{1}x)\cdots(1-a_{\ell}x)}\right]=n!\sum_{j=1}^{\ell}\frac{a_{j}^{n-k+\ell-1}}{\left[\prod_{i=1,\
i\neq j}^{\ell}(a_{i}-a_{j})\right](1-a_{j}x)^{n+1}}.$

###### Proof.

We prove this identity by induction on $n$. The base case is $n=1$, in which
one has to show that:

$\frac{d}{dx}\left[\frac{x^{k}}{(1-a_{1}x)\cdots(1-a_{\ell}x)}\right]=\sum_{j=1}^{\ell}\frac{a_{j}^{\ell-k}}{\left[\prod_{i=1,\
i\neq j}^{\ell}(a_{i}-a_{j})\right](1-a_{j}x)^{2}}.$

This equality can be achieved by performing a second induction on $\ell$ and
using partial fractions.

The induction step on $n$ follows due to a simple derivation argument. ∎

######  Theorem 2.5.

For $r\leq k\leq n$, we have

$S_{n,k,r}^{p(x)}(q)=\sum_{j=r}^{k}\frac{\bigl{(}[p(j)]_{q}\bigr{)}^{n-r}}{\prod_{i=r,i\neq
j}^{k}\bigl{(}[p(i)]_{q}-[p(j)]_{q}\bigr{)}}\,.$

Here, the empty product equals $1$ as usual.

###### Proof.

The generating function appearing in Condition (4) of Theorem 2.2 is:

$\sum\limits_{n=k}^{\infty}S^{p(x)}_{n,k,r}(q)x^{n}=\frac{x^{k}}{(1-[p(r)]_{q}x)\cdots(1-[p(k)]_{q}x)}.$

Then, we get by Lemma 2.4 for $\ell=k-r+1$ and substituting $[p(i)]_{q}$ for
$a_{i}$:

$\displaystyle S_{n,k,r}^{p(x)}(q)$ $\displaystyle=$
$\displaystyle\frac{1}{n!}\cdot\left.\frac{d^{n}}{dx^{n}}\left[\frac{x^{k}}{\prod_{j=r}^{k}\bigl{(}1-[p(j)]_{q}\cdot
x\bigr{)}}\right]\right|_{x=0}=$ $\displaystyle=$
$\displaystyle\sum_{j=r}^{k}\frac{\bigl{(}[p(j)]_{q}\bigr{)}^{n-r}}{\prod_{i=r,i\neq
j}^{k}\bigl{(}[p(i)]_{q}-[p(j)]_{q}\bigr{)}}.$

∎

##  3 Exponential generating functions for Stirling numbers of type $B$

If we focus on the polynomial $p(k)=2k-1$ and $q=1$ in Equation (4), we
actually deal with the Stirling numbers (of the second kind) of type $B$:
$S_{n,k}^{B}$ and $S_{n,k,r}^{B}$. In this section, we elaborate on these
numbers, both from combinatorial and analytical aspects. Explicitly, we deal
with the exponential generating functions of $S_{n,k}^{B}$ and $S_{n,k,r}^{B}$
(Sections 3.2 and 3.3 respectively). In Section 3.4, we introduce an
application of the exponential generating function of $S_{n,k,r}^{B}$ to
connection constants between bases of $\mathbb{R}[x]$.

###  3.1 Set partitions for type $B$

We now recall the definition of set partitions for type $B$, which are
enumerated by these Stirling numbers (see Dolgachev-Lunts [7, p. 755] and
Reiner [19, Section 2]; implicitly in Dowling [8] and Zaslavsky [27] in the
form of signed graphs):

######  Definition 3.1.

A set partition of $[\pm n]=\\{\pm 1,\dots,\pm n\\}$ of type $B$ is a set
partition of the set $[\pm n]$ such that the following conditions are
satisfied:

  * •

If $B$ appears as a block in the partition, then $-B$ (which is obtained by
negating all the elements of $B$) also appears in that partition.

  * •

There exists at most one block satisfying $-B=B$. This block is called the
zero block (if it exists, it is a subset of $[\pm n]$ of the form $\\{\pm
i\mid i\in C\\}$ for some $C\subseteq[n]$).

For example, the following is a set partition of $[\pm 6]$ of type $B$:

$\\{\\{1,-1,4,-4\\},\\{2,3,-5\\},\\{-2,-3,5\\},\\{6\\},\\{-6\\}\\}.$

Note that every non-zero block $B$ has a corresponding block $-B$ attached to
it. For the sake of convenience, we write for the pair of blocks $B,-B$, only
the representative block containing the minimal positive number appearing in
$B\cup-B$. For example, the pair of blocks $B=\\{-2,-3,5\\},-B=\\{2,3,-5\\}$
will be represented by the single block $\\{2,3,-5\\}$.

######  Definition 3.2.

Let $S_{n,k}^{B}$ be the number of set partitions of type $B$ having $k$
representative non-zero blocks. This is known as the Stirling number of the
second kind of type $B$ (see sequence A085483 in OEIS [18]).

It is easy to see that $S_{n,n}^{B}=S_{n,0}^{B}=1$ for each $n\geq 0$. The
following recursion for $S_{n,k}^{B}$ is well-known ([8, Theorem 7; see the
Erratum], [2, Corollary 3], for $m=2$, and [25, Equation (1)], for $m=2,c=1$):

######  Proposition 3.3.

For each $1\leq k<n$,

$S_{n,k}^{B}=S_{n-1,k-1}^{B}+(2k+1)S_{n-1,k}^{B}.$ (5)

We present here a new generalization of the Stirling number of the second kind
of type $B$, based on the work of Broder [4] for type $A$. Define the
$r$-Stirling number of the second kind of type $B$ as follows:

######  Definition 3.4.

Let $S_{n,k,r}^{B}$ be the number of set partitions of type $B$ of the set
$[\pm n]$ into $k$ non-zero blocks such that the numbers $1,\dots,r$ are in
distinct non-zero blocks. The numbers $1,\dots,r$ will be called special
elements.

For example, the following is an element of $S_{7,3,2}^{B}$:

$\\{\\{4,-4\\},\\{\mathbf{1},3,-5\\},\\{-1,-3,5\\},\\{\mathbf{2},6\\},\\{-2,-6\\},\\{7\\},\\{-7\\}\\}.$

Note that the case $r=0$ brings us back to the definition of the Stirling
number of type $B$ given in Definition 3.2.

The recursion for the $r$-Stirling numbers of type $B$ is identical to the one
given in Proposition 3.3, where the only differences are the initial
conditions, as the following proposition claims:

######  Proposition 3.5.

If $n<r$, then $S_{n,k,r}^{B}=0$. If $n=r$, then $S_{n,k,r}^{B}=\delta_{kr}$.
If $n>r$, then:

$S_{n,k,r}^{B}=S_{n-1,k-1,r}^{B}+(2k+1)S_{n-1,k,r}^{B}.$

###  3.2 An exponential generating function of $S_{n,k}^{B}$

In this subsection, we deal with the exponential generating function of
$S_{n,k}^{B}$.

######  Proposition 3.6.

For $k\geq 0$,

$\sum\limits_{n=k}^{\infty}S_{n,k}^{B}\frac{t^{n}}{n!}=\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}.$
(6)

Here we propose an analytic proof of Theorem 3.6, while a generalization of
this result for $S_{n,k,r}^{B}$ will be proved in a combinatorial way in
Theorem 3.8.

###### Proof of Proposition 3.6.

Denote: $S^{B}_{k}(t):=\sum\limits_{n=k}^{\infty}S_{n,k}^{B}\frac{t^{n}}{n!}$
for all $k\geq 0$. By the recursion (5), we have:

$\displaystyle\frac{d}{dt}S^{B}_{k}(t)$ $\displaystyle=$
$\displaystyle\frac{d}{dt}\left[\sum\limits_{n=k}^{\infty}S_{n,k}^{B}\frac{t^{n}}{n!}\right]=$
$\displaystyle\stackrel{{\scriptstyle(\ref{recursion_second_kind_type_b})}}{{=}}$
$\displaystyle\frac{d}{dt}\left[\sum\limits_{n=k}^{\infty}S_{n-1,k-1}^{B}\frac{t^{n}}{n!}\right]+(2k+1)\frac{d}{dt}\left[\sum\limits_{n=k}^{\infty}S_{n-1,k}^{B}\frac{t^{n}}{n!}\right]=$
$\displaystyle=$
$\displaystyle\sum\limits_{n=k}^{\infty}S_{n-1,k-1}^{B}\frac{t^{n-1}}{(n-1)!}+(2k+1)\sum\limits_{n=k}^{\infty}S_{n-1,k}^{B}\frac{t^{n-1}}{(n-1)!}=$
$\displaystyle=$
$\displaystyle-\underbrace{S_{k-2,k-1}^{B}}_{=0}\frac{t^{n-1}}{(n-1)!}+\sum\limits_{n=k-1}^{\infty}S_{n-1,k-1}^{B}\frac{t^{n-1}}{(n-1)!}+(2k+1)\sum\limits_{n=k}^{\infty}S_{n-1,k}^{B}\frac{t^{n-1}}{(n-1)!}=$
$\displaystyle\stackrel{{\scriptstyle n-1\rightarrow n}}{{=}}$
$\displaystyle\sum\limits_{n=k-2}^{\infty}S_{n,k-1}^{B}\frac{t^{n}}{n!}+(2k+1)\sum\limits_{n=k-1}^{\infty}S_{n,k}^{B}\frac{t^{n}}{n!}=$
$\displaystyle=$
$\displaystyle\sum\limits_{n=k-1}^{\infty}S_{n,k-1}^{B}\frac{t^{n}}{n!}-\underbrace{S_{k-2,k-1}^{B}}_{=0}\frac{t^{n}}{n!}+(2k+1)\sum\limits_{n=k}^{\infty}S_{n,k}^{B}\frac{t^{n}}{n!}-\underbrace{S_{k-1,k}^{B}}_{=0}\frac{t^{n}}{n!}=$
$\displaystyle=$ $\displaystyle S^{B}_{k-1}(t)+(2k+1)S^{B}_{k}(t),$

so we get:

$\frac{d}{dt}S^{B}_{k}(t)=S^{B}_{k-1}(t)+(2k+1)S^{B}_{k}(t).$ (7)

Directly from the boundary condition, one computes:

$S^{B}_{0}(t)=\sum\limits_{n=0}^{\infty}S_{n,0}^{B}\frac{t^{n}}{n!}=\sum\limits_{n=0}^{\infty}1\cdot\frac{t^{n}}{n!}=e^{t}.$

For proving the proposition, we check that the right hand side of Equation
(6), $\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}$, satisfies Equation (7) and the
boundary condition $S^{B}_{0}(t)=e^{t}$. Indeed, substituting $0$ for $k$ in
the right hand side yields: $\frac{1}{0!2^{0}}e^{t}(e^{2t}-1)^{0}=e^{t}$ as
needed. Now we check that it satisfies Equation (7):

$\displaystyle\frac{d}{dt}\left[\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}+\frac{1}{k!2^{k}}e^{t}\cdot
k(e^{2t}-1)^{k-1}\cdot 2e^{2t}=$ $\displaystyle=$
$\displaystyle\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}+\frac{1}{(k-1)!2^{k-1}}e^{t}e^{2t}(e^{2t}-1)^{k-1}=$
$\displaystyle=$
$\displaystyle\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}+\frac{1}{(k-1)!2^{k-1}}(e^{2t}-1)^{k-1}\left[e^{t}+e^{t}(e^{2t}-1)\right]=$
$\displaystyle=$
$\displaystyle\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}+\frac{1}{(k-1)!2^{k-1}}e^{t}(e^{2t}-1)^{k-1}+\frac{1}{(k-1)!2^{k-1}}e^{t}(e^{2t}-1)^{k}=$
$\displaystyle=$
$\displaystyle\frac{1}{(k-1)!2^{k-1}}e^{t}(e^{2t}-1)^{k-1}+(2k+1)\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}$

as required. ∎

Sagan and Swanson [20, Theorem 4.3] provided a $q$-analogue of Proposition 3.6
using $q$-exponentials.

###  3.3 An exponential generating function of $S_{n,k,r}^{B}$

In this subsection, we present the exponential generating function for
$S_{n,k,r}^{B}$. We generalize an approach appearing in Mező’s book [16,
Section 8.2].

We start by proving the following nice combinatorial identity:

######  Lemma 3.7.

Let $n,k,r\in\mathbb{N}$ and let $0\leq p\leq r$. Then

$S_{n,k,r}^{B}=\sum\limits_{m=0}^{n-r}{{n-r}\choose m}\cdot
S^{B}_{n-p-m,k-p,r-p}\cdot(2p)^{m}.$ (8)

###### Proof.

Given $p\leq r$, we call the first $p$ elements $\\{1,\dots,p\\}$ out of the
first $r$ special elements (see Definition 3.4) - most special elements. For
each one of them, its positive value will serve as the minimal element of a
distinct block. These $p$ blocks will be called the most special blocks.

In the first step, we choose the number $m$ of additional elements that will
occupy the $p$ most special blocks (in addition to the most special elements
$1,\dots,p$). Obviously, the absolute value of each of these $m$ elements is
greater than $r$. The number ${n-r\choose m}$ counts the ways to choose $m$
such elements.

Then, we insert the remaining $n-p-m$ elements in $k-p$ blocks, such that the
$r-p$ elements $p+1,\dots,r$ are special, i.e. $p+1,\dots,r$ are in distinct
blocks, in $S^{B}_{n-p-m,k-p,r-p}$ possibilities. Next, we fill the $p$ most
special blocks with $p+m$ elements in $S^{B}_{p+m,p,p}$ ways. Note, however,
that $S^{B}_{p+m,p,p}=(2p)^{m}$, since each one of the additional $m$ elements
can be located in one of the $p$ most special blocks, and can be either
positive or negative. This gives us the required equality. ∎

From here, one can easily deduce an expression for the exponential generating
function of $S_{n+r,k+r,r}^{B}$ as follows:

######  Theorem 3.8.

Let $k,r\in\mathbb{N}$. Then:

$\displaystyle\sum\limits_{n=k}^{\infty}S_{n+r,k+r,r}^{B}\frac{t^{n}}{n!}=\frac{1}{k!2^{k}}e^{(2r+1)t}(e^{2t}-1)^{k}.$

###### Proof.

By substituting in Equation (8) $n+r$, $k+r$ and $r$ for $n$, $k$ and $p$
respectively, we get:

$S_{n+r,k+r,r}^{B}=\sum\limits_{m=0}^{n}{n\choose
m}S^{B}_{(n+r)-r-m,(k+r)-r,r-r}\cdot(2r)^{m}\stackrel{{\scriptstyle
m\leftarrow n-m}}{{=}}\sum\limits_{m=0}^{n}{n\choose m}\cdot(2r)^{n-m}\cdot
S_{m,k}^{B}.$

Since the exponential generating function of the (ordinary) Stirling numbers
for type $B$ is:
$\displaystyle\sum\limits_{n=k}^{\infty}S_{n,k}^{B}\frac{t^{n}}{n!}=\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}$
(see Sagan and Swanson [20], who proved it using the theory of species), we
conclude from the rule of product of exponential generating functions (see
e.g. [23, Prop. 5.1.1]) that

$\sum\limits_{n=k}^{\infty}S_{n+r,k+r,r}^{B}\frac{t^{n}}{n!}=e^{2rt}\cdot\frac{1}{k!2^{k}}e^{t}(e^{2t}-1)^{k}=\frac{1}{k!2^{k}}e^{(2r+1)t}(e^{2t}-1)^{k}$

as required. ∎

Note that by substituting $r=0$ in Theorem 3.8, we get again Proposition 3.6.

###  3.4 An application to connection constants

Given $n,r\in\mathbb{N}$, let $\\{(x+2r)^{n}\\}_{n\in\mathbb{N}}$ and
$\\{(x-1)(x-3)\cdots(x-2n+1)\\}_{n\in\mathbb{N}}$ be two sequences of
polynomials, forming two different bases of $\mathbb{R}[x]$. The following
result presents the numbers $S_{n+r,k+r,r}^{B}$ as connection constants
between these two bases of $\mathbb{R}[x]$:

######  Theorem 3.9.

Let $n,r\in\mathbb{N}$. Then we have:

$(x+2r)^{n}=\sum\limits_{k=0}^{n}S_{n+r,k+r,r}^{B}\cdot(x-1)(x-3)\cdots(x-2k+1).$

###### Proof.

We calculate:

$\displaystyle\sum\limits_{n=0}^{\infty}(2x+2r)^{n}\frac{t^{n}}{n!}$
$\displaystyle=$ $\displaystyle
e^{2(x+r)t}=e^{(2r+1)t}e^{2(x-\frac{1}{2})t}=e^{(2r+1)t}(1+(e^{2t}-1))^{(x-\frac{1}{2})}=$
$\displaystyle=$
$\displaystyle\sum\limits_{k=0}^{\infty}e^{(2r+1)t}(e^{2t}-1)^{k}\cdot\frac{2^{k}\left(x-\frac{1}{2}\right)\left(x-\frac{3}{2}\right)\cdots\left(x-k+\frac{1}{2}\right)}{2^{k}k!}=$
$\displaystyle\stackrel{{\scriptstyle{\rm Thm.}\ \ref{thm_exponential}}}{{=}}$
$\displaystyle\sum\limits_{k=0}^{\infty}\left(\sum\limits_{n=0}^{\infty}S_{n+r,k+r,r}^{B}\frac{t^{n}}{n!}\right)(2x-1)(2x-3)\cdots(2x-2k+1)=$
$\displaystyle=$
$\displaystyle\sum\limits_{n=0}^{\infty}\left(\sum\limits_{k=0}^{n}S_{n+r,k+r,r}^{B}\cdot(2x-1)(2x-3)\cdots(2x-2k+1)\right)\frac{t^{n}}{n!}$

By comparing the coefficients of $t^{n}$, we have:

$(2x+2r)^{n}=\sum\limits_{k=0}^{n}S_{n+r,k+r,r}^{B}\cdot(2x-1)(2x-3)\cdots(2x-2k+1).$

By substituting $x$ for $2x$, the result follows. ∎

Note that Corollary 2.4 of Sagan and Swanson [20] is a $q$-analogue for the
$r=0$ case.

##  4 The type II $q,r$-poly-Stirling numbers of the first kind

In this section, we move to the Stirling numbers of the first kind, and
present a generalization of Lancaster’s theorem (Theorem 1.2 above) to the
case of unsigned type II $q,r$-poly-Stirling numbers of the first kind,
mentioned in the introduction (based on Miceli’s type II $q$-poly-Stirling
number of the first kind [17]).

######  Definition 4.1.

Let $p(x)\in\mathbb{Z}[x]$. The (unsigned) type II $q,r$-poly-Stirling numbers
of the first kind, denoted $c_{n,k,r}^{p(x)}(q)$, are defined by the
recurrence relation:

$c_{n,k,r}^{p(x)}(q)=c_{n-1,k-1,r}^{p(x)}(q)+[p(n-1)]_{q}c_{n-1,k,r}^{p(x)}(q)\quad(r\leq
k\leq n,~{}n\geq 1)$ (9)

with $c_{r,r,r}^{p(x)}(q)=1$ and $c_{n,k,r}^{p(x)}(q)=0$ (for $k<r$, $k>n$ or
$n<r$).

When $r=0$, the recurrence (9) is reduced to that in Miceli [17, Eqn. (39)].
Moreover, the boundary conditions for $r=0$: $c_{0,0,0}^{p(x)}(q)=1$ and
$c_{n,k,0}^{p(x)}(q)=0$ (for $k<0$, $k>n$ or $n<0$) are compatible with those
of Miceli.

Next, we extend and generalize Lancaster’s result to the case of type II
unsigned $q,r$-poly-Stirling numbers of the first kind:

######  Theorem 4.2 (Generalized Lancaster’s theorem for $q,r$-poly-Stirling
numbers).

Let $p(n)$ be a polynomial with non-negative integer coefficients. The
following are equivalent characterizations for
$(c^{p(x)}_{n,k,r}(q))_{n,k,r\mid 0\leq r\leq k\leq n}$ (where for all other
values of the triple $(n,k,r)$, we assume $c^{p(x)}_{n,k,r}(q)=0$).

  1. (1)

Defining equation/generating function:

$(x+[p(r)]_{q})(x+[p(r+1)]_{q})\cdots(x+[p(n-1)]_{q})=\sum\limits_{k=r}^{n}c_{n,k,r}^{p(x)}(q)\cdot
x^{k-r}.$

  2. (2)

Recursion: For each $n\geq k>r$:

$c^{p(x)}_{n,k,r}=c_{n-1,k-1,r}^{p(x)}(q)+[p(n-1)]_{q}\ c_{n-1,k,r}^{p(x)}(q)$

with the boundary conditions:
$c_{n,r,r}^{p(x)}(q)=[p(r)]_{q}[p(r+1)]_{q}\cdots[p(n-1)]_{q}$ and
$c_{r,k,r}^{p(x)}(q)=\delta_{kr}$.

  3. (3)

Complete Recursion: For $n\geq k>r$:

$c_{n,k,r}^{p(x)}(q)=\sum\limits_{j=k}^{n}c_{j-1,k-1,r}^{p(x)}(q)\prod\limits_{i=j}^{n-1}[p(i)]_{q},$

subject to the same boundary conditions as in Condition (2).

  4. (4)

Explicit formula: For $n\geq k\geq r$:

$c_{n,k,r}^{p(x)}(q)=\prod_{j=r}^{n-1}[p(j)]_{q}\sum_{r\leq
i_{r+1}<\dots<i_{k}\leq n-1}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k})]_{q}}.$

###### Proof.

We prove only the implications [(2)$\Longrightarrow$(4)] and
[(4)$\Longrightarrow$(2)], since the other implications can be easily deduced
from the proof of the original theorem of Lancaster.

[(2)$\Longrightarrow$(4)]: We prove the identity by induction on $n$. The base
case is: $n=k=r$. Indeed,

$c_{r,r,r}^{p(x)}(q)=\prod_{j=r}^{r-1}[p(j)]_{q}=1$

as required.

Assume correctness for $n-1$, and we prove the correctness for $n$: by the
recursion (9), we have:

$\displaystyle c_{n,k,r}^{p(x)}(q)$
$\displaystyle\stackrel{{\scriptstyle(\ref{2st1})}}{{=}}$ $\displaystyle
c_{n-1,k-1,r}^{p(x)}(q)+[p(n-1)]_{q}\ c_{n-1,k,r}^{p(x)}(q)=$
$\displaystyle\stackrel{{\scriptstyle\rm Assumption}}{{=}}$
$\displaystyle\left[\prod_{j=r}^{n-2}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k-1}\leq
n-2}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k-1})]_{q}}+$
$\displaystyle\qquad+[p(n-1)]_{q}\left[\prod_{j=r}^{n-2}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k}\leq n-2}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k})]_{q}}=$
$\displaystyle=$
$\displaystyle\left[\prod_{j=r}^{n-1}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k-1}\leq
n-2}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k-1})]_{q}[p(n-1)]_{q}}+$
$\displaystyle\qquad+\left[\prod_{j=r}^{n-1}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k}\leq n-2}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k})]_{q}}=$
$\displaystyle=$
$\displaystyle\left[\prod_{j=r}^{n-1}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k}\leq n-1}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k})]_{q}}\,.$

[(4)$\Longrightarrow$(2)]: Assume that we have Condition (4):

$c_{n,k,r}^{p(x)}(q)=\prod_{j=r}^{n-1}[p(j)]_{q}\sum_{r\leq
i_{r+1}<\dots<i_{k}\leq n-1}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k})]_{q}},$

then it is immediate that
$c_{n,r,r}^{p(x)}(q)=[p(r)]_{q}[p(r+1)]_{q}\cdots[p(n-1)]_{q}$ and
$c_{r,k,r}^{p(x)}(q)=\delta_{kr}$, and therefore the boundary conditions are
satisfied.

Now we show the recurrence relation in Condition (2):

$\displaystyle c_{n,k,r}^{p(x)}(q)$ $\displaystyle\stackrel{{\scriptstyle{\rm
Cond.}\ (4)}}{{=}}$
$\displaystyle\left[\prod_{j=r}^{n-1}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k}\leq n-1}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k})]_{q}}=$
$\displaystyle=$
$\displaystyle\left[\prod_{j=r}^{n-2}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k-1}\leq
n-2}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k-1})]_{q}}+$
$\displaystyle\qquad+[p(n-1)]_{q}\left(\left[\prod_{j=r}^{n-2}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k}\leq
n-2}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k})]_{q}}\right)=$
$\displaystyle\stackrel{{\scriptstyle{\rm Cond.}\ (4)}}{{=}}$ $\displaystyle
c_{n-1,k-1,r}^{p(x)}(q)+[p(n-1)]_{q}\ c_{n-1,k,r}^{p(x)}(q),$

as required. ∎

##  5 Orthogonality relations between poly-Stirling numbers of both kinds

In the previous section, we focused on the unsigned version of the $q,r$-poly-
Stirling number of the first kind $c_{n,k,r}^{p(x)}$. In the current section,
we discuss its signed version, in order to present two of its applications: an
identity related to a sum of powers (Section 5.1) and the orthogonality
relations between the Stirling numbers of first and second kinds (Section
5.2).

######  Definition 5.1.

Let $p(x)\in\mathbb{Z}[x]$. The type II (signed) $q,r$-poly-Stirling numbers
of the first kind, denoted $s_{n,k,r}^{p(x)}(q)$, are defined by the
recurrence relation:

$s_{n,k,r}^{p(x)}(q)=s_{n-1,k-1,r}^{p(x)}(q)-[p(n-1)]_{q}\
s_{n-1,k,r}^{p(x)}(q)\quad(r\leq k\leq n,~{}n\geq 1)$ (10)

with $s_{r,r,r}^{p(x)}(q)=1$ and $s_{n,k,r}^{p(x)}(q)=0$ (for $k<r$, $k>n$ or
$n<r$).

We present here the generalization of Lancaster’s theorem for the signed case,
the correctness of which is evident by substituting $x\to-x$ in the
formulation of the unsigned case (Theorem 4.2).

######  Theorem 5.2 (Generalized Lancaster’s theorem for signed type II
$q,r$-poly-Stirling numbers of the first kind).

Let $p(x)\in\mathbb{Z}[x]$. The following are equivalent characterizations for
$(s^{p(x)}_{n,k,r}(q))_{n,k,r\mid 0\leq r\leq k\leq n}$ (where for all other
values of the triple $(n,k,r)$, we assume $s^{p(x)}_{n,k,r}(q)=0$):

  1. (1)

Defining equation/generating function:

$(x-[p(r)]_{q})(x-[p(r+1)]_{q})\cdots(x-[p(n-1)]_{q}){=}\sum\limits_{k=r}^{n}s_{n,k,r}^{p(x)}(q)\cdot
x^{k-r}.$

  2. (2)

Recursion: For each $n\geq k>r$:

$s^{p(x)}_{n,k,r}=s_{n-1,k-1,r}^{p(x)}(q)-[p(n-1)]_{q}\
s_{n-1,k,r}^{p(x)}(q),$

with the boundary conditions:

$s_{n,r,r}^{p(x)}(q)=(-1)^{n-r}[p(r)]_{q}[p(r+1)]_{q}\cdots[p(n-1)]_{q}$

and $s_{r,k,r}^{p(x)}(q)=\delta_{kr}$.

  3. (3)

Complete recursion: For $n\geq k>r$:

$s_{n,k,r}^{p(x)}(q)=\sum\limits_{j=k}^{n}(-1)^{n-j}s_{j-1,k-1,r}^{p(x)}(q)\prod\limits_{i=j}^{n-1}[p(i)]_{q},$

subject to the same boundary conditions as in Condition (2).

  4. (4)

Explicit formula: For $n\geq k\geq r$:

$s_{n,k,r}^{p(x)}(q)=(-1)^{n-k}\left[\prod_{j=r}^{n-1}[p(j)]_{q}\right]\sum_{r\leq
i_{r+1}<\dots<i_{k}\leq n-1}\frac{1}{[p(i_{r+1})]_{q}\cdots[p(i_{k})]_{q}}.$

###  5.1 An application to sum of powers

In this subsection, we provide an application of Theorem 5.2 to the sum of
powers of the expressions $[p(j)]_{q}$:

######  Theorem 5.3.

For integers $n,k$ and $r$ with $n\geq r$ and $k\geq 1$, we have:

$\sum_{j=r}^{n}\bigl{(}[p(j)]_{q}\bigr{)}^{k}=-\sum_{\ell=1}^{n-r+1}\ell
s_{n+1,n+1-\ell,r}^{p(x)}(q)S_{n+k-\ell,n,r}^{p(x)}(q)\,.$

###### Proof.

By Condition (1) of Theorem 5.2 for $n+1$ instead of $n$ we have:

$x^{r}\prod_{j=r}^{n}\bigl{(}x-[p(j)]_{q}\bigr{)}=\sum_{k=r}^{n+1}s_{n+1,k,r}^{p(x)}(q)x^{k}.$
(11)

Next, we substitute $\frac{1}{t}$ for $x$:

$\left(\frac{1}{t}\right)^{r}\prod_{j=r}^{n}\left(\frac{1}{t}-[p(j)]_{q}\right)=\sum_{k=r}^{n+1}s_{n+1,k,r}^{p(x)}(q)\left(\frac{1}{t}\right)^{k}.$

Multiplying this by $t^{n+1}$, yields:

$F_{1}(t):=\prod_{j=r}^{n}\bigl{(}1-t[p(j)]_{q}\bigr{)}=\sum_{k=r}^{n+1}s_{n+1,k,r}^{p(x)}(q)\
t^{n-k+1}\stackrel{{\scriptstyle
n-k+1\rightarrow\ell}}{{=}}\sum_{\ell=0}^{n-r+1}s_{n+1,n+1-\ell,r}^{p(x)}\
t^{\ell}\,.$ (12)

Recall from Theorem 2.2(4) that

$\sum\limits_{n=k}^{\infty}S^{p(x)}_{n,k,r}(q)x^{n}=\frac{x^{k}}{(1-x[p(r)]_{q})\cdots(1-x[p(k)]_{q})}.$

By the substitutions (in this order): $n\rightarrow n+\nu$, $k\rightarrow n$
and $x\rightarrow t$, and dividing both sides by $t^{n}$, we get:

$\sum\limits_{\nu=0}^{\infty}S^{p(x)}_{n+\nu,n,r}(q)\
t^{\nu}=\frac{1}{(1-t[p(r)]_{q})\cdots(1-t[p(n)]_{q})}=\prod_{j=r}^{n}\bigl{(}1-t[p(j)]_{q}\bigr{)}^{-1}=:F_{2}(t).$

Note that $F_{1}(t)F_{2}(t)=1$. Now, we have:

$\frac{d}{dt}\log
F_{2}(t)=\frac{d}{dt}\left[\sum_{j=r}^{n}-\log\left(1-t[p(j)]_{q}\right)\right]=\sum_{j=r}^{n}\frac{[p(j)]_{q}}{1-t[p(j)]_{q}}=\sum_{j=r}^{n}\sum_{k=1}^{\infty}\bigl{(}[p(j)]_{q}\bigr{)}^{k}t^{k-1}.$
(13)

Note that:

$\frac{d}{dt}F_{1}(t)=\frac{d}{dt}\left[\prod_{j=r}^{n}\bigl{(}1-t[p(j)]_{q}\bigr{)}\right]=\sum_{m=r}^{n}-[p(m)]_{q}\prod_{j=r,j\neq
m}^{n}\bigl{(}1-t[p(j)]_{q}\bigr{)}.$

Therefore, we have

$-\left(\frac{d}{dt}F_{1}(t)\right)F_{2}(t)=\sum_{m=r}^{n}\frac{[p(m)]_{q}}{1-t[p(m)]_{q}}\stackrel{{\scriptstyle(\ref{eq:221})}}{{=}}\frac{d}{dt}\log
F_{2}(t).$ (14)

On the other hand, by Equation (12), we also have:

$\frac{d}{dt}F_{1}(t)=\sum_{\ell=1}^{n-r+1}\ell
s_{n+1,n+1-\ell,r}^{p(x)}(q)t^{\ell-1}\,.$

Combining Equations (13) and (14), we have:

$-\left(\sum_{\ell=1}^{n+1}\ell
s_{n+1,n+1-\ell,r}^{p(x)}(q)t^{\ell-1}\right)\left(\sum_{\nu=0}^{\infty}S_{n+\nu,n,r}^{p(x)}(q)t^{\nu}\right)=\sum_{k=1}^{\infty}\sum_{j=r}^{n}\bigl{(}[p(j)]_{q}\bigr{)}^{k}t^{k-1},$

which can be also written as:

$-\sum_{\ell=1}^{n+1}\sum_{\nu=0}^{\infty}\ell
s_{n+1,n+1-\ell,r}^{p(x)}(q)S_{n+\nu,n,r}^{p(x)}(q)t^{\ell-1+\nu}=\sum_{k=1}^{\infty}\sum_{j=r}^{n}\bigl{(}[p(j)]_{q}\bigr{)}^{k}t^{k-1}.$

Comparing the coefficients of $t^{k-1}$ in both sides (imposing that
$\nu=k-\ell$), yields the requested formula. ∎

Note that Theorem 1.1 of Merca [15] is a special case of Theorem 5.3 where
$r=0$ and $p(x)=x$.

###  5.2 An application to orthogonality relations

As a consequence of Theorems 2.2 and 5.2, we get the orthogonality relations
between the type II $q,r$-poly-Stirling numbers of the first and second kinds:

######  Theorem 5.4.

For $r\leq\ell\leq n$ and $r<n$, we have:

$\sum_{k=\ell}^{n}S_{n,k,r}^{p(x)}(q)s_{k,\ell,r}^{p(x)}(q)=\delta_{n\ell}$
$\sum_{k=\ell}^{n}s_{n,k,r}^{p(x)}(q)S_{k,\ell,r}^{p(x)}(q)=\delta_{n\ell}.$

###### Proof.

By Theorem 2.2(1), we have:

$x^{n-r}=\sum_{k=r}^{n}S_{n,k,r}^{p(x)}(q)\prod_{j=r+1}^{k}\bigl{(}x-[p(j-1)]_{q}\bigr{)}.$

On the other hand, by Theorem 5.2(1) we have:

$\prod_{j=r}^{n-1}\left(x-[p(j)]_{q}\right)=\sum\limits_{k=r}^{n}s_{n,k,r}^{p(x)}(q)\cdot
x^{k-r}.$

By substituting either one of these equations into the other and changing the
order of summations, we readily obtain the orthogonality relations. ∎

##  6 Type I $q,r$-poly-Stirling numbers of both kinds and mixed relations
between both types

In this section, we present another version of $q,r$-poly-Stirling numbers of
the first and second kinds. Based on this version, we present some mixed
relations between both types of these numbers.

###  6.1 Type I $q,r$-poly-Stirling numbers of both kinds

Here we present the generalization of Miceli’s Type I $q$-poly-Stirling
numbers of the first and second kind (see [17]):

######  Definition 6.1.

The type I $q,r$-poly-Stirling numbers of the second kind are defined by the
recurrence:

$\overline{S}_{n,k,r}^{p(x)}(q)=\overline{S}_{n-1,k-1,r}^{p(x)}(q)+p([k]_{q})\overline{S}_{n-1,k,r}^{p(x)}(q)\quad(r\leq
k\leq n,~{}n\geq 1),$ (15)

with $\overline{S}_{r,r,r}^{p(x)}(q)=1$ and $\overline{S}_{n,k,r}^{p(x)}(q)=0$
for $k<r$, $k>n$ or $n<r$.

######  Definition 6.2.

The type I signed $q,r$-poly-Stirling numbers of the first kind are defined by
the recurrence:

$\overline{s}_{n,k,r}^{p(x)}(q)=\overline{s}_{n-1,k-1,r}^{p(x)}(q)-p([n-1]_{q})\overline{s}_{n-1,k,r}^{p(x)}(q)\quad(r\leq
k\leq n,~{}n\geq 1)$ (16)

with $\overline{s}_{r,r,r}^{p(x)}(q)=1$ and $\overline{s}_{n,k,r}^{p(x)}(q)=0$
for $k<0$, $k>n$ or $n<r$.

######  Definition 6.3.

The type I unsigned $q,r$-poly-Stirling numbers of the first kind are defined
by the recurrence:

$\overline{c}_{n,k,r}^{p(x)}(q)=\overline{c}_{n-1,k-1,r}^{p(x)}(q)+p([n-1]_{q})\overline{c}_{n-1,k,r}^{p(x)}(q)\quad(r\leq
k\leq n,~{}n\geq 1)$ (17)

with $\overline{c}_{r,r,r}^{p(x)}(q)=1$ and $\overline{c}_{n,k,r}^{p(x)}(q)=0$
for $k<0$, $k>n$ or $n<r$.

All the results of Sections 2, 4 and 5 and their proofs can be transferred
verbatim to type I as well (the only change is the location of the squared
brackets); nevertheless, we provide here the formulation of the result
parallel to Theorem 5.3, for our use in the next subsection:

######  Theorem 6.4.

For integers $n$ and $k$ with $n\geq r$ and $k\geq 1$, we have

$\sum_{j=r}^{n}\bigl{(}p([j]_{q})\bigr{)}^{k}=-\sum_{\ell=1}^{n-r+1}\ell\overline{s}_{n+1,n+1-\ell,r}^{p(x)}(q)\overline{S}_{n+k-\ell,n,r}^{p(x)}(q)\,.$

###  6.2 Mixed relations

We can obtain a mixed relation of both types of $q,r$-poly-Stirling numbers:

######  Theorem 6.5.

Let $u\geq 1$ be a positive integer. For $n\geq r$, we have

$\sum_{\ell=1}^{n-r+1}\ell
s_{n+1,n+1-\ell,r}^{x}(q)S_{n+ku-\ell,n,r}^{x}(q)=\sum_{\ell=1}^{n-r+1}\ell\overline{s}_{n+1,n+1-\ell,r}^{x^{u}}(q)\overline{S}_{n+k-\ell,n,r}^{x^{u}}(q)\,.$

###### Proof.

If we put $p(x)=x$ in Theorem 5.3, we get:

$\sum_{j=r}^{n}\bigl{(}[j]_{q}\bigr{)}^{k}=-\sum_{\ell=1}^{n-r+1}\ell
s_{n+1,n+1-\ell,r}^{x}(q)S_{n+k-\ell,n,r}^{x}(q).$

Substituting $ku$ for $k$, we get:

$\sum_{j=r}^{n}\bigl{(}[j]_{q}\bigr{)}^{ku}=-\sum_{\ell=1}^{n-r+1}\ell
s_{n+1,n+1-\ell,r}^{x}(q)S_{n+ku-\ell,n,r}^{x}(q).$ (18)

On the other hand, if we put $p(x)=x^{u}$ in Theorem 6.4, we get:

$\sum_{j=r}^{n}\bigl{(}([j]_{q})^{u}\bigr{)}^{k}=-\sum_{\ell=1}^{n-r+1}\ell\overline{s}_{n+1,n+1-\ell,r}^{x^{u}}(q)\overline{S}_{n+k-\ell,n,r}^{x^{u}}(q).$
(19)

Comparing Equations (18) and (19) yields the requested equality. ∎

## Acknowledgements

We thank Bruce Sagan and Josh Swanson for many fruitful discussions, including
correcting our formula in Theorem 3.8.

## References

  * [1] P. Bala, A 3-parameter family of generalized Stirling numbers (2015). Electronic version: https://oeis.org/A143395/a143395.pdf
  * [2] M. Benoumhani, On Whitney numbers of Dowling lattices, Discrete Math. 159 (1996), 13–33.
  * [3] B. Bényi, M. Méndez, J. L. Ramírez and T. Wakhare, Restricted $r$-Stirling numbers and their combinatorial applications, Appl. Math. Comput. 348 (2019), 186–205.
  * [4] A. Z. Broder, The $r$-Stirling numbers, Discrete Math. 49 (1984), 241–259.
  * [5] Ch.A. Charalambides, Non-central generalized $q$-factorial coefficients and $q$-Stirling numbers, Discrete Math. 275 (2004), 67–85.
  * [6] L. Comtet, Nombres de Stirling généraux et fonctions symmetriques, C. R. Acad. Sc. Paris, Série A, 275 (1972), 747–750.
  * [7] I. Dolgachev and V. Lunts, A character formula for the representation of a Weyl group in the cohomology of the associated toric variety, J. Algebra 168(3) (1994), 741–772.
  * [8] T. A. Dowling, A class of geometric lattices based on finite groups, J. Combin. Theory, Ser. B 14 (1973), 61–86. Erratum: J. Combin. Theory, Ser. B 15 (1973), 211.
  * [9] B.S. El-Desouky and F.A. Shiha, A $q$-analogue of $\bar{\alpha}$-Whitney numbers, Appl. Anal. Discrete Math. 12 (2018), 178–191.
  * [10] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, second edition, Addison-Wesley, Reading, Mass., 1994.
  * [11] V. J. W. Guo and J. Zeng, A $q$-analogue of Faulhaber’s formula for sums of powers, Electron. J. Combin. 11 (2004/2006), #R19, 19 pp.
  * [12] M. Lancaster, Generalizations of the Stirling, Lah, and cycle numbers of the first and second kinds, M.Sc. Thesis, University of Tennessee, 1996.
  * [13] M. Lancaster, T. Mansour, S. Mulay and M. Shattuck, A general two-term recurrence and its solution, European J. Combin. 33 (2012), 20–26; Corrigendum, European J. Combin. 71 (2018), 268.
  * [14] R.S. Maier, Triangular recurrences, generalized Eulerian numbers, and related number triangles, submitted. [arXiv: 2207.10224]
  * [15] M. Merca, A $q$-analogue for sums of powers, Acta Arith. 183.2 (2018), 185–189.
  * [16] I. Mező, Combinatorics and Number Theory of Counting Sequences, CRC Press. Taylor & Francis Group. Boca Raton (FL), 2020.
  * [17] B. K. Miceli, Two $q$-analogues of poly-Stirling numbers, J. Integer Seq. 14 (2011), Article 11.9.6, 33 pp.
  * [18] OEIS Foundation Inc. (2022), The On-Line Encyclopedia of Integer Sequences, http://oeis.org
  * [19] V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177(1–3) (1997), 195–222.
  * [20] B. Sagan and J. Swanson, $q$-Stirling numbers in type $B$, submitted [arXiv:2205.14078].
  * [21] M. Schlosser, A $q$-analogue of consecutive integers, squares, cubes, quarts and quints, Electron. J. Combin. 11 (2004), #R71, 12 pp.
  * [22] R.P. Stanley, Enumerative Combinatorics, Vol. 1, Second edition, Cambridge University Press, 2012.
  * [23] R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.
  * [24] C. G. Wagner, A First Course in Enumerative Combinatorics, Pure and Applied Undergraduate Texts, vol. 49, Amer. Math. Soc., 2020.
  * [25] D. G. L. Wang, On colored set partitions of type $B_{n}$, Cent. Eur. J. Math. 12(9) (2014), 1372–1381.
  * [26] S. O. Warnaar, On the $q$-analogue of the sums of cubes, Electron. J. Combin. 11 (2004), #N14, 2 pp.
  * [27] T. Zaslavsky, The geometry of root systems and signed graphs, Amer. Math. Monthly 88(2) (1981), 88–105.

##  7 Appendix - Proof of Theorem 2.2

######  Lemma 7.1.

  1. (1)

$S_{n,n,r}^{p(x)}(q)=1$

  2. (2)

$S_{n,n-1,r}^{p(x)}(q)=\sum\limits_{i=r}^{n-1}[p(i)]_{q}$

  3. (3)

$S_{n,r,r}^{p(x)}(q)=\bigl{(}[p(r)]_{q}\bigr{)}^{n-r}$

Hence, in general, if $p(r)\neq 0$, then $S_{n,r,r}^{p(x)}(q)\neq 0$ even if
$r=0$.

###### Proof.

By the recurrence relation (4), we get:

  1. (1)

$S_{n,n,r}^{p(x)}(q)=S_{n-1,n-1,r}^{p(x)}(q)+[p(n)]_{q}\underbrace{S_{n-1,n,r}^{p(x)}(q)}_{=0}=S_{n-1,n-1,r}^{p(x)}(q)=\cdots=S_{r,r,r}^{p(x)}(q)=1$

  2. (2)

$\displaystyle S_{n,n-1,r}^{p(x)}(q)$ $\displaystyle=$ $\displaystyle
S_{n-1,n-2,r}^{p(x)}(q)+[p(n-1)]_{q}\cdot\underbrace{S_{n-1,n-1,r}^{p(x)}(q)}_{=1}=\cdots=$
$\displaystyle=$
$\displaystyle\underbrace{S_{r,r-1,r}^{p(x)}(q)}_{=0}+[p(r)]_{q}+\cdots+[p(n-2)]_{q}+[p(n-1)]_{q}=\sum\limits_{i=r}^{n-1}[p(i)]_{q}$

  3. (3)

$S_{n,r,r}^{p(x)}(q)=\underbrace{S_{n-1,r-1,r}^{p(x)}(q)}_{=0}+[p(r)]_{q}S_{n-1,r,r}^{p(x)}(q)=\cdots=\bigl{(}[p(r)]_{q}\bigr{)}^{n-r}\underbrace{S_{r,r,r}^{p(x)}(q)}_{=1}=\bigl{(}[p(r)]_{q}\bigr{)}^{n-r}$

∎

######  Lemma 7.2.

For $n\geq r+2$:

$S_{n,r+1,r}^{p(x)}(q)=\sum_{i_{r}+i_{r+1}=n-r-1\atop i_{r},i_{r+1}\geq
0}\bigl{(}[p(r)]_{q}\bigr{)}^{i_{r}}\bigl{(}[p(r+1)]_{q}\bigr{)}^{i_{r+1}}$

###### Proof.

We prove this lemma by induction on $n$. For the base case, substitute $n=r+2$
in Lemma 7.1(2):

$S_{r+2,r+1,r}^{p(x)}(q)=[p(r)]_{q}+[p(r+1)]_{q}.$

Assume correctness for $n-1$ and we prove for $n>r+2$ using the recurrence
relation in Equation (4):

$\displaystyle S_{n,r+1,r}^{p(x)}(q)$
$\displaystyle\stackrel{{\scriptstyle(\ref{2st2})}}{{=}}$ $\displaystyle
S_{n-1,r,r}^{p(x)}(q)+[p(r+1)]_{q}S_{n-1,r+1,r}^{p(x)}(q)=$
$\displaystyle\stackrel{{\scriptstyle\ref{second kind special cases}(3)+{\rm
Assumption}}}{{=}}$
$\displaystyle\bigl{(}[p(r)]_{q}\bigr{)}^{n-r-1}+[p(r+1)]_{q}\sum_{i_{r}+i_{r+1}=n-r-2\atop
i_{r},i_{r+1}\geq
0}\bigl{(}[p(r)]_{q}\bigr{)}^{i_{r}}\bigl{(}[p(r+1)]_{q}\bigr{)}^{i_{r+1}}=$
$\displaystyle=$ $\displaystyle\sum_{i_{r}+i_{r+1}=n-r-1\atop
i_{r},i_{r+1}\geq
0}\bigl{(}[p(r)]_{q}\bigr{)}^{i_{r}}\bigl{(}[p(r+1)]_{q}\bigr{)}^{i_{r+1}}$

∎

When $r=0$, the recurrence relation (4) is reduced to the one appearing in
Miceli [17, Equation (37)]. Moreover, the boundary conditions for $r=0$,
namely $S_{0,0,0}^{p(x)}(q)=1$ and $S_{n,k,0}^{p(x)}(q)=0$ (for $k<0$, $k>n$
or $n<0$), are compatible with those of Miceli.

Before proving the theorem, we need one more lemma:

######  Lemma 7.3.

Using the notations of Theorem 2.2, we have for $r\leq n$:

$x\sum_{k=r}^{n-1}S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=\sum_{k=r}^{n}\left(S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\right)\varphi_{k}(x)$

###### Proof.

It is easy to check that for $n=r$ both sides are $0$. We compute for $n>r$:

$\displaystyle x\sum_{k=r}^{n-1}S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)$
$\displaystyle=$
$\displaystyle\sum_{k=r}^{n-1}\left(x-[p(k)]_{q}+[p(k)]_{q}\right)S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=$
$\displaystyle=$
$\displaystyle\sum_{k=r}^{n-1}S_{n-1,k,r}^{p(x)}(q)\cdot\left(x-[p(k)]_{q}\right)\varphi_{k}(x)+\sum_{k=r}^{n-1}[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=$
$\displaystyle=$
$\displaystyle\sum_{k=r}^{n-1}S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k+1}(x)+\sum_{k=r}^{n-1}[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=$
$\displaystyle\stackrel{{\scriptstyle k+1\to k\ {\rm in\ left\ sum}}}{{=}}$
$\displaystyle\sum_{k=r+1}^{n}S_{n-1,k-1,r}^{p(x)}(q)\cdot\varphi_{k}(x)+\sum_{k=r}^{n-1}[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=$
$\displaystyle=$
$\displaystyle\sum_{k=r}^{n}\left(S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\right)\varphi_{k}(x)$
$\displaystyle-\underbrace{S_{n-1,r-1,r}^{p(x)}(q)}_{=0}\varphi_{r}(x)-\underbrace{S_{n-1,n,r}^{p(x)}(q)}_{=0}[p(n)]_{q}\varphi_{n}(x)=$
$\displaystyle=$
$\displaystyle\sum_{k=r}^{n}\left(S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\right)\varphi_{k}(x)$

as requested. ∎

###### Proof of Theorem 2.2.

The proof consists of the following eight parts.

[(1)$\Longrightarrow$(2)]: We first prove the boundary condition:

$1=x^{r-r}\stackrel{{\scriptstyle\rm Cond.\
(1)}}{{=}}\sum\limits_{k=r}^{r}{S^{p(x)}_{r,k,r}(q)\varphi_{k}(x)}=S^{p(x)}_{r,r,r}(q)\underbrace{\varphi_{r}(x)}_{=1}=S^{p(x)}_{r,r,r}(q),$

so we get: $S^{p(x)}_{r,r,r}(q)=1$ as needed.

Now, we prove the recurrence relation. We have:

$\sum_{k=r}^{n}S_{n,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)\stackrel{{\scriptstyle\rm
Cond.\ (1)}}{{=}}x^{n-r}=x\cdot x^{n-1-r}\stackrel{{\scriptstyle\rm Cond.\
(1)}}{{=}}x\sum_{k=r}^{n-1}S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k}(x).$

By Lemma 7.3, we can replace the right-hand-side of the above equation by the
right-hand-side of the equation in the lemma, in order to get:

$\sum_{k=r}^{n}S_{n,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=\sum_{k=r}^{n}\left(S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\right)\varphi_{k}(x).$

Comparing the coefficients of the basis elements $\\{\varphi_{k}(x)\\}$ on
both sides, we obtain:

$S_{n,k,r}^{p(x)}(q)=S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q).$

[(2)$\Longrightarrow$(1)]: Expand the recurrence relation appearing in
Condition (2) and use Lemma 7.3 $n-r$ times. Explicitly:

$\displaystyle\sum\limits_{k=r}^{n}S_{n,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)$
$\displaystyle\stackrel{{\scriptstyle\rm Cond.\ (2)}}{{=}}$
$\displaystyle\sum\limits_{k=r}^{n}\left(S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\right)\cdot\varphi_{k}(x)=$
$\displaystyle\stackrel{{\scriptstyle\rm Lemma\ \ref{long calc}}}{{=}}$
$\displaystyle
x\sum\limits_{k=r}^{n-1}S_{n-1,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=$
$\displaystyle\stackrel{{\scriptstyle{\rm Cond.}\ (2)+\ref{long calc}}}{{=}}$
$\displaystyle
x^{2}\sum\limits_{k=r}^{n-2}S_{n-2,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=\cdots\stackrel{{\scriptstyle{\rm
Cond.}\ (2)+\ref{long calc}}}{{=}}$ $\displaystyle=$ $\displaystyle
x^{n-r}\sum\limits_{k=r}^{r}S_{r,k,r}^{p(x)}(q)\cdot\varphi_{k}(x)=$
$\displaystyle=$ $\displaystyle
x^{n-r}\underbrace{S_{r,r,r}^{p(x)}(q)\cdot\varphi_{r}(x)}_{=1}\stackrel{{\scriptstyle\rm
Bound.\ Cond.\ (2)}}{{=}}x^{n-r}.$

[(2)$\Longrightarrow$(3)]: Expand the recurrence relation appearing in
Condition (2) $n-k$ times. Explicitly:

$\displaystyle S_{n,k,r}^{p(x)}(q)$ $\displaystyle=$ $\displaystyle
S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)=$ $\displaystyle=$
$\displaystyle
S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}\bigl{(}S_{n-2,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-2,k,r}^{p(x)}(q)\bigr{)}=$
$\displaystyle=$ $\displaystyle
S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-2,k-1,r}^{p(x)}(q)+$ $\displaystyle\
+\bigl{(}[p(k)]_{q}\bigr{)}^{2}(S_{n-3,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-3,k,r}^{p(x)}(q)\bigr{)}=\cdots=$
$\displaystyle=$ $\displaystyle
S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-2,k-1,r}^{p(x)}(q)+\bigl{(}[p(k)]_{q}\bigr{)}^{2}S_{n-3,k-1,r}^{p(x)}(q)+$
$\displaystyle\
+\cdots+\bigl{(}[p(k)]_{q}\bigr{)}^{n-k}S_{k-1,k-1,r}^{p(x)}(q)=\sum\limits_{j=k}^{n}S^{p(x)}_{j-1,k-1,r}(q)\left([p(k)]_{q}\right)^{n-j}.$

[(3)$\Longrightarrow$(2)]: We check for $n=r+1$ separately: in this case, the
only possible value of $k$ is $r+1$. By Condition (3), we have:

$\displaystyle S_{r+1,r+1,r}^{p(x)}(q)$ $\displaystyle=$
$\displaystyle\sum_{j=r+1}^{r+1}S_{j-1,r,r}^{p(x)}(q)\bigl{(}[p(k)]_{q}\bigr{)}^{r+1-j}=S_{r,r,r}^{p(x)}(q)=1,$

while the recursion in Condition (2), achieves the same value:

$\displaystyle S_{r+1,r+1,r}^{p(x)}(q)$ $\displaystyle=$
$\displaystyle\underbrace{S_{r,r,r}^{p(x)}(q)}_{=1}+[p(r)]_{q}\underbrace{S_{r,r+1,r}^{p(x)}(q)}_{=0}=1.$

For $n>r+1$, apply Condition (3) for both $n,n-1>r$:

$S_{n,k,r}^{p(x)}(q)=\sum_{j=k}^{n}S_{j-1,k-1,r}^{p(x)}(q)\bigl{(}[p(k)]_{q}\bigr{)}^{n-j}\,,$
(20)
$S_{n-1,k,r}^{p(x)}(q)=\sum_{j=k}^{n-1}S_{j-1,k-1,r}^{p(x)}(q)\bigl{(}[p(k)]_{q}\bigr{)}^{n-j-1}\,.$
(21)

Hence,

$\displaystyle S_{n,k,r}^{p(x)}(q)$
$\displaystyle\stackrel{{\scriptstyle(\ref{cond3-n})}}{{=}}$
$\displaystyle\sum_{j=k}^{n}S_{j-1,k-1,r}^{p(x)}(q)\bigl{(}[p(k)]_{q}\bigr{)}^{n-j}=$
$\displaystyle=$ $\displaystyle
S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}\sum_{j=k}^{n-1}S_{j-1,k-1,r}^{p(x)}(q)\bigl{(}[p(k)]_{q}\bigr{)}^{n-j-1}=$
$\displaystyle\stackrel{{\scriptstyle(\ref{cond3n-1})}}{{=}}$ $\displaystyle
S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q),$

which is the recurrence relation in Condition (2).

[(2)$\Longrightarrow$(4)]: We assume that the recurrence relation in Condition
(2) holds. Denote $\displaystyle
f_{k}:=\sum\limits_{n=k}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n}$ for each $k\geq r$.
Then, for $k>r$, we have:

$\displaystyle f_{k}$ $\displaystyle=$
$\displaystyle\sum_{n=k}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n}=$
$\displaystyle\stackrel{{\scriptstyle{\rm Cond.}\ (2)}}{{=}}$
$\displaystyle\sum_{n=k}^{\infty}\left(S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\right)x^{n}=$
$\displaystyle=$
$\displaystyle\sum_{n=k}^{\infty}S_{n-1,k-1,r}^{p(x)}(q)x^{n}+\sum_{n=k}^{\infty}[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)x^{n}=$
$\displaystyle\stackrel{{\scriptstyle n\leftarrow n-1}}{{=}}$ $\displaystyle
x\sum_{n=k-1}^{\infty}S_{n,k-1,r}^{p(x)}(q)x^{n}+[p(k)]_{q}\cdot
x\sum_{n=k-1}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n}=$
$\displaystyle\stackrel{{\scriptstyle\left(S_{k-1,k,r}^{p(x)}(q)=0\right)}}{{=}}$
$\displaystyle
x\sum_{n=k-1}^{\infty}S_{n,k-1,r}^{p(x)}(q)x^{n}+[p(k)]_{q}\cdot
x\sum_{n=k}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n}=$ $\displaystyle=$ $\displaystyle
xf_{k-1}+[p(k)]_{q}\cdot xf_{k}.$

This implies:

$f_{k}=\frac{x}{1-[p(k)]_{q}\cdot x}\cdot f_{k-1}.$ (22)

For $k=r$, we have:

$f_{r}=\sum_{n=r}^{\infty}S_{n,r,r}^{p(x)}(q)x^{n}\stackrel{{\scriptstyle{\rm
Lemma}\ \ref{second kind special
cases}(3)}}{{=}}\sum_{n=r}^{\infty}\bigl{(}[p(r)]_{q}\bigr{)}^{n-r}x^{n}=x^{r}\sum_{n=r}^{\infty}\bigl{(}[p(r)]_{q}\cdot
x\bigr{)}^{n-r}=\frac{x^{r}}{1-[p(r)]_{q}\cdot x}.$

In summary, using Equation (22), we get for $k\geq r$:

$\sum_{n=k}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n}=f_{k}=\frac{x^{k}}{\bigl{(}1-[p(r)]_{q}\cdot
x\bigr{)}\bigl{(}1-[p(r+1)]_{q}\cdot x\bigr{)}\cdots\bigl{(}1-[p(k)]_{q}\cdot
x\bigr{)}}\,.$

[(4)$\Longrightarrow$(2)]: Denote for $k\geq r$:

$g_{k}:=\frac{x^{k}}{\bigl{(}1-[p(r)]_{q}\cdot
x\bigr{)}\bigl{(}1-[p(r+1)]_{q}\cdot x\bigr{)}\cdots\bigl{(}1-[p(k)]_{q}\cdot
x\bigr{)}}=\sum_{n=k}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n}\,.$

As $g_{r}=\frac{x^{r}}{1-[p(r)]_{q}\cdot x}$, we get:
$g_{k}=\frac{x}{1-[p(k)]_{q}\cdot x}\cdot g_{k-1}$. Thus for $k\geq r$:

$\displaystyle\sum_{n=k}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n}$ $\displaystyle=$
$\displaystyle g_{k}=xg_{k-1}+[p(k)]_{q}xg_{k}=$ $\displaystyle=$
$\displaystyle
x\sum_{n=k-1}^{\infty}S_{n,k-1,r}^{p(x)}(q)x^{n}+[p(k)]_{q}x\sum_{n=k}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n}=$
$\displaystyle\stackrel{{\scriptstyle S_{k-1,k,r}^{p(x)}(q)=0}}{{=}}$
$\displaystyle\sum_{n=k-1}^{\infty}S_{n,k-1,r}^{p(x)}(q)x^{n+1}+[p(k)]_{q}\sum_{n=k-1}^{\infty}S_{n,k,r}^{p(x)}(q)x^{n+1}=$
$\displaystyle\stackrel{{\scriptstyle n+1\rightarrow n}}{{=}}$
$\displaystyle\sum_{n=k}^{\infty}\left(S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\right)x^{n}.$

Comparing the coefficients on both sides, we obtain:

$S_{n,k,r}^{p(x)}(q)=S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)\,.$

[(2)$\Longrightarrow$(5)]: Before proving the general case, we have to verify
some specific cases. For $r\leq k=n$, we have by the boundary condition in
Condition (2) and Lemma 7.1(1):

$S_{n,n,r}^{p(x)}(q)=1=\sum\limits_{i_{r}+i_{r+1}+\cdots+i_{k}=0\atop
i_{l}\geq
0}\left([p(r)]_{q}\right)^{i_{r}}\cdots\left([p(k)]_{q}\right)^{i_{k}}$

as required.

For $r=k<n$, we have by Lemma 7.1(3):

$S_{n,r,r}^{p(x)}(q)=\left([p(r)]_{q}\right)^{n-r}$

again as required.

Now, we pass to the general case, where $r<k<n$. We start by induction on $n$.
The base case is $n=r+2$. Since $r<k<n$, it means that $k=r+1$, and this is
the case $n=r+2$ of Lemma 7.2 .

Now assume its correctness for $n-1\geq r+2$ and we prove it for $n$. This
will be done by a proof for all values of $k$ in the range
$\\{r+1,\dots,n-1\\}$. The first case is $k=r+1$, which was proved in Lemma
7.2. For $k>r+1$, we prove it using the recurrence in Condition (2):

$\displaystyle S_{n,k,r}^{p(x)}(q)$ $\displaystyle\stackrel{{\scriptstyle{\rm
Cond.}\ (2)}}{{=}}$ $\displaystyle
S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q)=$
$\displaystyle\stackrel{{\scriptstyle\rm Assumption}}{{=}}$
$\displaystyle\sum_{i_{r}+i_{r+1}+\cdots+i_{k-1}=n-k\atop
i_{r},i_{r+1},\dots,i_{k-1}\geq
0}\bigl{(}[p(r)]_{q}\bigr{)}^{i_{r}}\bigl{(}[p(r+1)]_{q}\bigr{)}^{i_{r+1}}\cdots\bigl{(}[p(k-1)]_{q}\bigr{)}^{i_{k-1}}+$
$\displaystyle+[p(k)]_{q}\sum_{i_{r}+i_{r+1}+\cdots+i_{k}=n-1-k\atop
i_{r},i_{r+1},\dots,i_{k}\geq
0}\bigl{(}[p(r)]_{q}\bigr{)}^{i_{r}}\bigl{(}[p(r+1)]_{q}\bigr{)}^{i_{r+1}}\cdots\bigl{(}[p(k)]_{q}\bigr{)}^{i_{k}}=$
$\displaystyle=$ $\displaystyle\sum_{i_{r}+i_{r+1}+\cdots+i_{k}=n-k\atop
i_{r},i_{r+1},\dots,i_{k}\geq
0}\bigl{(}[p(r)]_{q}\bigr{)}^{i_{r}}\bigl{(}[p(r+1)]_{q}\bigr{)}^{i_{r+1}}\cdots\bigl{(}[p(k)]_{q}\bigr{)}^{i_{k}}.$

[(5)$\Longrightarrow$(2)]: Assume that Condition (5) is satisfied:

$S_{n,k,r}^{p(x)}(q)=\sum\limits_{i_{r}+i_{r+1}+\cdots+i_{k}=n-k\atop
i_{l}\geq
0}\left([p(r)]_{q}\right)^{i_{r}}\cdots\left([p(k)]_{q}\right)^{i_{k}}.$

Then it is immediate that $S^{p(x)}_{r,r,r}(q)=1$ and $S_{n,k,r}^{p(x)}(q)=0$
for $k<r$, $k>n$ or $n<r$, and therefore the boundary conditions are
satisfied.

Now we have to show the recurrence relation in Condition (2):

$\displaystyle S_{n,k,r}^{p(x)}(q)$ $\displaystyle\stackrel{{\scriptstyle{\rm
Cond.}\ (5)}}{{=}}$
$\displaystyle\sum\limits_{i_{r}+i_{r+1}+\cdots+i_{k}=n-k\atop i_{l}\geq
0}\left([p(r)]_{q}\right)^{i_{r}}\cdots\left([p(k)]_{q}\right)^{i_{k}}=$
$\displaystyle=$
$\displaystyle\sum\limits_{i_{r}+i_{r+1}+\cdots+i_{k-1}=n-k\atop i_{l}\geq
0}\left([p(r)]_{q}\right)^{i_{r}}\cdots\left([p(k-1)]_{q}\right)^{i_{k-1}}+$
$\displaystyle\qquad+[p(k)]_{q}\sum\limits_{i_{r}+i_{r+1}+\cdots+i_{k}=n-k-1\atop
i_{l}\geq
0}\left([p(r)]_{q}\right)^{i_{r}}\cdots\left([p(k)]_{q}\right)^{i_{k}}=$
$\displaystyle\stackrel{{\scriptstyle{\rm Cond.}\ (5)}}{{=}}$ $\displaystyle
S_{n-1,k-1,r}^{p(x)}(q)+[p(k)]_{q}S_{n-1,k,r}^{p(x)}(q),$

which is the requested recurrence relation. ∎