#  $q$-Stirling numbers in type $B$

Bruce E. Sagan
Department of Mathematics, Michigan State University,
East Lansing, MI 48824, USA<EMAIL_ADDRESS>
and
Joshua P. Swanson
Department of Mathematics, Univesity of Southern California,
Los Angeles, CA 90007, USA<EMAIL_ADDRESS>
(
Key Words: Artin basis, Coxeter group of type $B$, super coinvariant algebra,
generating function, Hilbert series, ordered set partition, $q$-analogue,
signed permutation, signed set partition, Stirling number, symmetric
polynomial
AMS subject classification (2020): 05A05, 05A18 (Primary) 05A15, 05A30, 05E05,
05E16 (Secondary) )

###### Abstract

Stirling numbers, which count partitions of a set and permutations in the
symmetric group, have found extensive application in combinatorics, geometry,
and algebra. We study analogues and $q$-analogues of these numbers
corresponding to the Coxeter group of type $B$. In particular, we show how
they are related to complete homogeneous and elementary symmetric polynomials;
demonstrate how they $q$-count signed partitions and permutations; compute
their ordinary, exponential, and $q$-exponential generating functions; and
prove various identities about them. Ordered analogues of the $q$-Stirling
numbers of the second kind have recently appeared in conjectures of Zabrocki
and of Swanson–Wallach concerning the Hilbert series of certain super
coinvariant algebras. We provide conjectural bases for these algebras and show
that they have the correct Hilbert series.

###### Contents

  1. 1 Introduction
    1. 1.1 Classical $q$-Stirling numbers
    2. 1.2 Existing $q$-Stirling literature
    3. 1.3 Stirling numbers in type $B$ and their $q$-analogues
    4. 1.4 Summary of results
  2. 2 Symmetric polynomials
    1. 2.1 Ordinary generating functions
    2. 2.2 Falling factorials
    3. 2.3 Inverse matrices
  3. 3 Combinatorial interpretations
    1. 3.1 Signed partitions
    2. 3.2 Signed permutations
    3. 3.3 The lattice of signed partitions
  4. 4 Exponential and $q$-exponential generating functions
    1. 4.1 Exponential generating functions
    2. 4.2 $q$-exponential generating functions
  5. 5 Ordered analogues and identities
    1. 5.1 Alternating sums
    2. 5.2 Divisibility
  6. 6 Coinvariant algebras
    1. 6.1 Type $A$ coinvariants
    2. 6.2 Type $A$ super coinvariants
    3. 6.3 Type $B$ super coinvariants
  7. 7 Comments and open questions
    1. 7.1 Complex reflection groups
    2. 7.2 Major index for signed permutations and super coinvariant bases
    3. 7.3 $q$-difference equations
    4. 7.4 Sign-reversing involutions
    5. 7.5 Log concavity
    6. 7.6 Asymptotics
    7. 7.7 Graded Euler characteristics

##  1 Introduction

Let ${\mathbb{Z}}$ and ${\mathbb{N}}$ be the integers and nonnegative
integers, respectively. If $n\in{\mathbb{N}}$. then we will be interested in
two intervals of integers, namely

$[n]=\\{1,2,\ldots,n\\}\quad\mbox{and}\quad\langle{n}\rangle=\\{-n,-n+1,\ldots,n-1,n\\}.$

If $n\in{\mathbb{Z}}$ and $q$ is a variable then we let

$\displaystyle[n]_{q}$ $\displaystyle=\frac{1-q^{n}}{1-q},$
$\displaystyle[n]_{q}!$ $\displaystyle=[n]_{q}[n-1]_{q}\cdots[1]_{q},$
$\displaystyle[n]_{q}!!$ $\displaystyle=[n]_{q}[n-2]_{q}[n-4]_{q}\cdots,$

where the double factorial ends at $[1]_{q}$ or $[2]_{q}$ depending on whether
$n$ is odd or even, respectively. Note that if $n<0$ then
$[n]_{q}!=[n]_{q}!!=1$ because both are the empty product. Note also that if
$n\geq 0$ then

$[n]_{q}=1+q+q^{2}+\cdots+q^{n-1}.$

We will often drop the subscript $q$ in such notation if there can be no
confusion about whether $[n]$ denotes the polynomial or the set.

###  1.1 Classical $q$-Stirling numbers

The purpose of the present work is to give a comprehensive treatment of the
Stirling numbers in type $B$ and their $q$-analogues. We begin by defining the
various classical Stirling numbers in type $A$ and their $q$-analogues
recursively. Each recursion in this paper will always have $n\in{\mathbb{N}}$
and $k\in{\mathbb{Z}}$ with the same boundary condition when $n=0$. We start
with the Stirling numbers of the second kind, which arise more frequently in
the context of $q$-analogues.

######  Definition 1.1.

The (type $A$) Stirling numbers of the second kind are $S(n,k)$ for
$n\in{\mathbb{N}}$ and $k\in{\mathbb{Z}}$ defined by the initial condition
$S(0,k)=\delta_{0,k}$ (Kronecker delta) and for $n\geq 1$,

$S(n,k)=S(n-1,k-1)+kS(n-1,k).$ (1)

It is well known that $S(n,k)$ is the number of partitions of the set $[n]$
into $k$ non-empty subsets called blocks. These partitions are in bijection
with subspaces of dimension $n-k$ in the intersection lattice of the type
$A_{n-1}$ Coxeter group.

We will be primarily interested in $q$-analogues of Stirling numbers. There
are in fact two standard $q$-analogues of the Stirling numbers of the second
kind, which differ by a $q$-shift. We will call the (type $A$) $q$-Stirling
numbers of the second kind the polynomials $S[n,k]$ in the variable $q$
obtained by replacing (1) with

$S[n,k]=S[n-1,k-1]+[k]S[n-1,k].$ (2)

Sometimes $\overline{S}[n,k]=q^{\binom{k}{2}}S[n,k]$ is also encountered,
which replaces (1) with

$\overline{S}[n,k]=q^{k-1}\overline{S}[n-1,k-1]+[k]\overline{S}[n-1,k].$ (3)

Some of the work related to $q$-Stirling numbers concerns the following
ordered analogue.

######  Definition 1.2.

The (type $A$) ordered $q$-Stirling numbers of the second kind are

$S^{o}[n,k]=[k]!S[n,k],$

and $\overline{S}^{o}[n,k]=[k]!\overline{S}[n,k]$.

When $q=1$, $S^{o}(n,k)$ counts the number of ordered set partitions of $[n]$
with $k$ blocks.

We now recall the Stirling numbers of the first kind and their $q$-analogue.

######  Definition 1.3.

The (signless, type $A$) Stirling numbers of the first kind are $c(n,k)$ for
$n\in{\mathbb{N}}$ and $k\in{\mathbb{Z}}$ defined by the initial condition
$c(0,k)=\delta_{0,k}$ and for $n\geq 1$,

$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k).$ (4)

Their signed counterparts are

$s(n,k)=(-1)^{n-k}c(n,k).$

Combinatorially, $c(n,k)$ counts the number of elements in the symmetric group
of permutations of $[n]$ which have $k$ cycles in their disjoint cycle
decomposition. The (signless, type $A$) $q$-Stirling numbers of the first kind
are the polynomials $c[n,k]$ obtained by replacing (4) with

$c[n,k]=c[n-1,k-1]+[n-1]c[n-1,k].$ (5)

Their signed counterparts are $s[n,k]=(-1)^{n-k}c[n,k]$.

Stirling numbers of both kinds have been extensively studied in combinatorics
and have interesting applications in algebra and geometry. See the texts of
Sagan [Sag20] or Stanley [Sta97] for more information. We next review the
literature on $q$-Stirling numbers.

###  1.2 Existing $q$-Stirling literature

The $q$-analogues above have been frequently studied, especially those of the
second kind. In the history which follows, we will sometimes make no
distinction between the two different variants of the $S[n,k]$. The second
kind $q$-Stirlings first appeared in the work of Carlitz on abelian fields
[Car33] and $q$-Bernoulli polynomials [Car48]. Then Gould [Gou61] studied
$q$-Stirling numbers of the first and second kinds, defining them in terms of
elementary and complete homogeneous symmetric polynomials. The $q$-Stirling
numbers of the first kind also appeared in the work of Gessel [Ges82] on a
$q$-analogue of the exponential formula.

By weighting the blocks of a partition, Garsia [Gar80] was the first to show
that $\overline{S}[n,k]$ can be considered as the generating function for a
statistic on set partitions, and Rawlings [Raw81] generalized this approach.
Milne [Mil82] showed that restricted growth functions (which are equinumerous
with set partitions) could be used to give two statistics, one for each
version of $S[n,k]$, both of which are similar to the inversion statistic on
permutations. Wachs and White [WW91] built on Milne’s work, giving two more
inversion-like statistics on restricted growth functions with the same
distribution. There is also an analogue of the major index for these Stirling
numbers as shown by Sagan [Sag91].

Ehrenborg and Readdy [ER96] interpreted the $\overline{S}[n,k]$ in terms of
juggling sequences and then Ehrenborg [Ehr03] used this interpretation to
evaluate various determinants whose entries are these polynomials. Other work
on $q$-Stirling numbers of the second kind has been done by Garsia and Remmel
[GR86] and by Leroux [Ler90].

In fact, in Carlitz’s original paper [Car33], the sum which arises in the
context of Stirling numbers is actually for $\overline{S}^{o}[n,k]$ and he has
to divide by $2^{\binom{k}{2}}[k]!$ to get the quantity in which he is
interested. Zeng and Zhang [ZZ94] used analytic means to prove a formula
relating the $\overline{S}^{o}[n,k]$ and a $q$-analogue of the $q$-exponential
numbers. A connection between the ordered polynomials and ordered set
partitions was obtained by Steingrímsson in a 2001 preprint which was finally
published in 2020 [Ste20]. There he gave eight statistics analogous to the
ones of Wachs and White. He also made a number of conjectures and posed an
open problem (to find a combinatorial proof of Zeng and Zhang’s identity)
which spurred a number of other authors to work on ordered set partitions
[IKZ06, IKZ08b, KZ09, KZ02, RW15, Wil16]. See Ishikawa, Kasraoui, and Zeng
[IKZ08a] for a survey.

Haglund, Rhoades, and Shimozono [HRS18] showed that there is a connection
between ordered set partitions, generalized coinvariant algebras, and the
Delta Conjecture (see the recent proof of the rise version [DM21]). In related
work, Zabrocki [Zab19] conjectured that the tri-graded Hilbert series of the
type $A$ superdiagonal coinvariant algebra has coefficients which are the
$S^{o}[n,k]$. Swanson and Wallach [SW21] made a corresponding conjecture in
type $B$. This led them to conjecture that an alternating sum involving these
ordered Stirling numbers equals one. We prove this as 5.5.

###  1.3 Stirling numbers in type $B$ and their $q$-analogues

The Stirling numbers in type $B$ have appeared sporadically in the literature
over the last several decades. They can be defined as follows.

######  Definition 1.4.

The type $B$ Stirling numbers of the second kind are defined by replacing (1)
with

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

The ordered version of $S_{B}(n,k)$ is

$S_{B}^{o}(n,k)=(2k)!!S_{B}(n,k).$

The (signless) type $B$ Stirling numbers of the first kind are defined by
replacing (4) with

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

with the signed version being

$s_{B}(n,k)=(-1)^{n-k}c_{B}(n,k).$

The reason for calling these “type $B$” is because the $S_{B}(n,k)$ and
$s_{B}(n,k)$ are the Whitney numbers of the second and first kind for the
intersection lattice ${\cal L}_{B_{n}}$ of the hyperplane arrangement of the
Coxeter group $B_{n}$, as follows from the work of Zaslavsky [Zas81]. See also
Section 3.3.

The $S_{B}(n,k)$ appear implicitly in the work of Dowling [Dow73] on certain
lattices and, as already mentioned, in that of Zaslavsky [Zas81] concerning
signed graphs. They were defined explicitly by Dolgachev and Lunts when
studying representations of Weyl groups [DL94] and Reiner [Rei97] in his work
on noncrossing partitions for classical reflection groups. An analogue of the
$s_{B}(n,k)$ appears implicitly in a formula of Shephard and Todd [ST54] for
the characteristic polynomial of the intersection lattice of an arbitrary
finite complex reflection group. Neither they, nor their $q$-analogue defined
below, have been explicitly defined elsewhere to our knowledge. See Section 3
for combinatorial interpretations of $S_{B}(n,k)$ and $c_{B}(n,k)$ involving
signed set partitions and signed permutations.

Our primary interest lies in the following $q$-analogues of the preceding type
$B$ Stirling numbers.

######  Definition 1.5.

The type $B$ $q$-Stirling numbers of the second kind are defined by replacing
(1) with

$S_{B}[n,k]=S_{B}[n-1,k-1]+[2k+1]S_{B}[n-1,k].$ (8)

The ordered version of $S_{B}[n,k]$ is

$S_{B}^{o}[n,k]=[2k]!!S_{B}[n,k].$

The (signless) type $B$ Stirling numbers of the first kind are defined by
replacing (4) with

$c_{B}[n,k]=c_{B}[n-1,k-1]+[2n-1]c_{B}[n-1,k],$ (9)

with the signed version being

$s_{B}[n,k]=(-1)^{n-k}c_{B}[n,k].$

As far as we know, the $S_{B}[n,k]$ have only appeared once before (in their
ordered form) in the previously cited paper of Swanson and Wallach. We will
have more to say about this in Sections 5 and 6. As we were preparing this
article, we became aware that Bagno, Garber, and Komatsu [BGK] were also
studying type $B$ analogues of the Stirling numbers. Their primary tool is the
use of signed analogues of restricted growth functions (RGFs) as opposed to
working with signed partitions and permutations as we do here. Interestingly,
their type $B$ analogue of the $s(n,k)$ differs significantly. They also use a
statistic on RGFs for $S_{B}[n,k]$ which, when translated into the language of
signed partitions, is different from ours although the two can be related by a
simple bijection. They also consider a variant where the elements of the
interval $[r]$ appear in different blocks or cycles for some fixed $r$. The
overlapping results between our two papers are 2.1 (b) and (d), as well as 4.1
(a).

###  1.4 Summary of results

Here we summarize some of our main results. See the following sections for
more details, references, and additional results. In Section 2, we show

  * •

$S_{B}[n,k]=h_{n-k}([1],[3],\ldots,[2k+1])$ and

$t^{n}=\sum_{k=0}^{n}S_{B}[n,k](t-[1])(t-[3])\cdots(t-[2k-1]),$

  * •

$c_{B}[n,k]=e_{n-k}([1],[3],\ldots,[2n-1])$ and

$\sum_{k=0}^{n}c_{B}[n,k]t^{k}=(t+[1])(t+[3])\cdots(t+[2n-1]),$

where $h$ and $e$ are complete homogeneous and elementary symmetric
polynomials. Along the way, we prove a new identity, 2.2, for the $h$
polynomials.

In Section 3, we provide combinatorial interpretations of the $S_{B}[n,k]$ and
$c_{B}[n,k]$ (and hence also the case $q=1$) in terms of certain statistics on
signed partitions and signed permutations, respectively; see Theorems 3.7,
3.10, and 3.17. In particular, we show that $c_{B}(n,k)$ counts the number of
signed permutations with $k$ pairs of “negative cycles.”

In Section 4, we prove a variety of additional generating function identities,
including the following:

$\displaystyle\sum_{n=0}^{\infty}S^{o}[n,k]\frac{x^{n}}{[n]!}$
$\displaystyle=\frac{1}{q^{\binom{k}{2}}}\sum_{i=0}^{k}(-1)^{k-i}q^{\binom{k-i}{2}}\left[\begin{array}[]{c}k\\\
i\end{array}\right]\exp_{q}([i]x),$
$\displaystyle\sum_{n=0}^{\infty}S_{B}^{o}(n,k)\frac{x^{n}}{n!}$
$\displaystyle=e^{x}(e^{2x}-1)^{k},$
$\displaystyle\sum_{n=0}^{\infty}S_{B}^{o}[n,k]\frac{x^{n}}{[n]!}$
$\displaystyle=\frac{1}{q^{k^{2}}}\sum_{i=0}^{k}(-1)^{k-i}q^{2\binom{k-i}{2}}\left[\begin{array}[]{c}k\\\
i\end{array}\right]_{q^{2}}\exp_{q}([2i+1]x).$

We also provide identities involving (bivariate) generating functions for
$c[n,k]$ and $c_{B}[n,k]$. In each case, they satisfy a first or second order
linear $q$-difference equation.

In Section 5, we prove the alternating sum identities

$\sum_{k=0}^{n}(-q)^{n-k}S^{o}[n,k]=1=\sum_{k=0}^{n}(-q)^{n-k}S_{B}^{o}[n,k],$

answering the conjecture in [SW21] in the affirmative. See 5.5 and 5.9. We
provide both algebraic demonstrations and combinatorial proofs based on sign-
reversing involutions. Replacing $-q$ with $-q^{m}$ in the above sums
conjecturally gives the graded Euler characteristic of certain generalized
exterior derivative complexes on super coinvariant algebras. Our sign-
reversing involutions more strongly give divisibility properties for these
conjectured graded Euler characteristics. Furthermore, we conjecture bases for
the type $A$ and $B$ super coinvariant algebras whose Hilbert series naturally
give rise to $S^{o}[n,k]$ and $S_{B}^{o}[n,k]$ with our inversion-style
statistics. See Section 6 for details. We end with a section of comments and
many questions and open problems.

##  2 Symmetric polynomials

Certain properties of the Stirling numbers follow from the fact that they can
be expressed in terms of elementary and complete homogeneous symmetric
polynomials. We will derive some of them, including their ordinary generating
functions, in this section. Further information about symmetric polynomials
can be found in the books of Macdonald [Mac15], Sagan [Sag01], or Stanley
[Sta99].

###  2.1 Ordinary generating functions

Let ${\bf x}=\\{x_{1},\ldots,x_{n}\\}$ be a set of commuting variables. The
degree $k$ elementary symmetric polynomial, denoted
$e_{k}(n)=e_{k}(x_{1},\ldots,x_{n})$, is the sum of all degree $k$ square-free
monomials in $x_{1},\ldots,x_{n}$. The degree $k$ complete homogeneous
symmetric polynomial $h_{k}(n)=h_{k}(x_{1},\ldots,x_{n})$ is the sum of all
degree $k$ monomials in these variables. For example

$e_{2}(3)=x_{1}x_{2}+x_{1}x_{3}+x_{2}x_{3}$

and

$h_{2}(3)=x_{1}x_{2}+x_{1}x_{3}+x_{2}x_{3}+x_{1}^{2}+x_{2}^{2}+x_{3}^{2}.$

By considering which monomials contain the variable $x_{n}$ and which do not,
it is easy to derive the following recursions for $n\geq 1$:

$e_{k}(n)=e_{k}(n-1)+x_{n}e_{k-1}(n-1)$ (10)

and

$h_{k}(n)=h_{k}(n-1)+x_{n}h_{k-1}(n).$ (11)

Let $t$ be a variable. The following generating functions are well known and
easy to prove directly from the definitions above:

$E_{n}(t):=\sum_{k=0}^{n}e_{k}(n)t^{k}=\prod_{i=1}^{n}(1+x_{i}t)$ (12)

and

$H_{n}(t):=\sum_{k\geq 0}h_{k}(n)t^{k}=\prod_{i=1}^{n}\frac{1}{1-x_{i}t}.$
(13)

The next result is a type $B$ analogue of the following facts from the
literature in type $A$:

  1. (a)

$c[n,k]=e_{n-k}([1],[2],\ldots,[n-1])$.

  2. (b)

$S[n,k]=h_{n-k}([1],[2],\ldots,[k])$.

  3. (c)

$\displaystyle\sum_{k=0}^{n}c[n,k]t^{k}=t(t+[1])(t+[2])\cdots(t+[n-1])$.

  4. (d)

$\displaystyle\sum_{n\geq
k}S[n,k]t^{n}=\frac{t^{k}}{(1-[1]t)(1-[2]t)\cdots(1-[k]t)}$.

######  Theorem 2.1.

Let $n\in{\mathbb{N}}$ and $k\in{\mathbb{Z}}$.

  1. (a)

$c_{B}[n,k]=e_{n-k}([1],[3],\ldots,[2n-1])$.

  2. (b)

$S_{B}[n,k]=h_{n-k}([1],[3],\ldots,[2k+1])$.

  3. (c)

$\displaystyle\sum_{k=0}^{n}c_{B}[n,k]t^{k}=(t+[1])(t+[3])\cdots(t+[2n-1])$.

  4. (d)

$\displaystyle\sum_{n\geq
k}S_{B}[n,k]t^{n}=\frac{t^{k}}{(1-[1]t)(1-[3]t)\cdots(1-[2k+1]t)}$.

###### Proof.

Parts (a) and (b) follow easily by comparing the recursions for the symmetric
polynomials with those for the Stirlings and using induction. Parts (c) and
(d) are obtained by combining the first two parts with the generating
functions (12) and (13). ∎

###  2.2 Falling factorials

We will need a result about symmetric polynomials which, while not difficult
to prove, we have not been able to find in the literature. Given a variable
$t$ and $k\in{\mathbb{N}}$ the corresponding (type $A$) falling factorial is

$t\downarrow_{k}=t(t-1)(t-2)\cdots(t-k+1).$

It is well known that for the type $A$ Stirling numbers we have

$t^{n}=\sum_{k=0}^{n}S(n,k)t\downarrow_{k}.$ (14)

To generalize this identity to symmetric polynomials in a set of variables
${\bf x}$, let

$t\downarrow_{k}^{\bf x}=(t-x_{1})(t-x_{2})\cdots(t-x_{k}).$

######  Theorem 2.2.

For $n\in{\mathbb{N}}$,

$t^{n}=\sum_{k=0}^{n}h_{n-k}(k+1)\ t\downarrow_{k}^{\bf x}.$

###### Proof.

Induct on $n$, where the base case is easy to verify. For the induction step
we use equation (11) and pull off a factor from the falling factorial to get

$\displaystyle\sum_{k}h_{n-k}(k+1)\ t\downarrow_{k}^{\bf x}$
$\displaystyle=\sum_{k}h_{n-k}(k)\ (t-x_{k})t\downarrow_{k-1}^{\bf
x}+\sum_{k}x_{k+1}h_{n-k-1}(k+1)\ t\downarrow_{k}^{\bf x}$
$\displaystyle=t\sum_{k}h_{n-k}(k)\ t\downarrow_{k-1}^{\bf
x}-\sum_{k}x_{k}h_{n-k}(k)\ \downarrow_{k-1}^{\bf x}$
$\displaystyle\rule{50.0pt}{0.0pt}+\sum_{k}x_{k}h_{n-k}(k)\
t\downarrow_{k-1}^{\bf x}$
$\displaystyle=t\sum_{k}h_{(n-1)-k}(k+1)t\downarrow_{k}^{\bf x}$
$\displaystyle=t\cdot t^{n-1}$

completing the proof. ∎

Clearly equation (14) follows from the previous theorem by setting $x_{i}=i-1$
for $1\leq i\leq n+1$. More generally, define the (type $A$) $q$-falling
factorial to be

$(t;q)\downarrow_{k}=t(t-[1])(t-[2])\cdots(t-[k-1]).$

Setting $x_{i}=[i-1]$ in the previous theorem gives:

######  Corollary 2.3.

For $n\in{\mathbb{N}}$

$t^{n}=\sum_{k=0}^{n}S[n,k](t;q)\downarrow_{k}.$

Now define the type $B$ $q$-falling factorial to be

$(t;q)\downarrow_{k}^{B}=(t-[1])(t-[3])\cdots(t-[2k-1]).$

Setting $x_{i}=[2i-1]$ for $1\leq i\leq k+1$ immediately gives an analogous
type $B$ result.

######  Corollary 2.4.

For $n\in{\mathbb{N}}$

$t^{n}=\sum_{k=0}^{n}S_{B}[n,k](t;q)\downarrow_{k}^{B},$

###  2.3 Inverse matrices

For our matrix identity, we need a new result about symmetric polynomials.
Given a generating function $f(t)=\sum_{n\geq 0}a_{n}t^{n}$ we define the
coefficient extraction function to be

$[t^{n}]f(t)=a_{n}.$

A special case of the following can be found in the book of Sturmfels [Stu08,
p. 12].

######  Theorem 2.5.

We have

$\sum_{a+b=N}(-1)^{a}e_{a}(n)h_{b}(m)=\begin{cases}(-1)^{N}e_{N}(x_{m+1},\ldots,x_{n})&n\geq
m,\\\ h_{N}(x_{n+1},\ldots,x_{m})&n\leq m.\end{cases}$

###### Proof.

From the generating functions in (12) and (13) we obtain

$\displaystyle\sum_{a+b=N}(-1)^{a}e_{a}(n)h_{b}(m)$
$\displaystyle=[t^{N}]E_{n}(-t)H_{m}(t)$
$\displaystyle=[t^{N}]\frac{(1-x_{1}t)(1-x_{2}t)\cdots(1-x_{n}t)}{(1-x_{1}t)(1-x_{2}t)\cdots(1-x_{m}t)}\rule{0.0pt}{15.0pt}.$

If $n\geq m$ then we are finding the coefficient of $t^{N}$ in
$(1-x_{m+1}t)(1-x_{m+2}t)\cdots(1-x_{n}t)$ which is the desired signed
elementary symmetric polynomial. The case $n\leq m$ is similar. ∎

Define two infinite matrices with rows and columns indexed by
$n\in{\mathbb{N}}$ and $k\in{\mathbb{N}}$, respectively, by

$E=[(-1)^{n-k}e_{n-k}(n)]_{n,k\geq 0}$

and

$H=[h_{n-k}(k+1)]_{n,k\geq 0}.$

Note that both $E$ and $H$ are lower uni-triangular. Let $I$ be the
${\mathbb{N}}\times{\mathbb{N}}$ identity matrix.

######  Theorem 2.6.

We have

$EH=I$

###### Proof.

Since $E$ and $H$ are both lower uni-triangular, so is their product.
Therefore we only need to evaluate the entry $(EH)_{n,k}$ when $n>k$. But

$(EH)_{n,k}=\sum_{i\geq 0}(-1)^{n-i}e_{n-i}(n)h_{i-k}(k+1)$

which is the sum in the previous theorem with $N=n-k$ and $m=k+1$. So we are
in the first case and the sum equals
$(-1)^{n-k}e_{n-k}(x_{k+2},\ldots,x_{n})=0$ since there are only $n-k-1$
variables in the elementary symmetric polynomial. ∎

Specialization of $x_{i}=[2i-1]$ immediately gives the following result.

######  Corollary 2.7.

If $s_{B}=[s_{B}[n,k]]_{n,k\geq 0}$ and $S_{B}=[S_{B}[n,k]]_{n,k\geq 0}$ then
$s_{B}S_{B}=I$. ∎

Note that setting $x_{i}=i-1$ in the previous theorem gives the well-known
result that $sS=I$ where $s=[s(n,k)]_{n,k\geq 0}$ and $S=[S(n,k)]_{n,k\geq
0}$.

##  3 Combinatorial interpretations

We will now give combinatorial interpretations of the $S_{B}[n,k]$ and
$c_{B}[n,k]$ (and hence also the case $q=1$) in terms of certain statistics on
signed partitions and permutations, respectively. The lattice of signed
partitions ordered by refinement is isomorphic to the intersection lattice
${\cal L}_{B_{n}}$ for the hyperplane arrangement of the Coxeter group
$B_{n}$. We will rederive the fact that $s_{B}(n,k)$ and $S_{B}(n,k)$ are the
Whitney numbers of the first and second kind, respectively, for ${\cal
L}_{B_{n}}$, as well as proving a new result expressing the Möbius function of
${\cal L}_{B_{n}}$ in terms signed permutations.

###  3.1 Signed partitions

######  Definition 3.1.

Let $S$ be a set and $\rho=\\{S_{1},\ldots,S_{k}\\}$ be a set partition of
$S$, so the $S_{i}$ are nonempty subsets whose disjoint union in $S$. We call
the $S_{i}$ blocks and write $\rho=S_{1}/\ldots/S_{k}\vdash S$, removing the
set braces from the $S_{i}$ themselves.

######  Definition 3.2.

A signed or type $B$ partition is a partition of the set $\langle{n}\rangle$
of the form

$\rho=S_{0}/S_{1}/S_{2}/\dots/S_{2k}$

satisfying

  1. 1.

$0\in S_{0}$ and if $i\in S_{0}$ then $-i\in S_{0}$, and

  2. 2.

for $i\geq 1$ we have $S_{2i}=-S_{2i-1}$,

where $-S=\\{-s\ :\ s\in S\\}$. Call the blocks $S_{2i}$ and $S_{2i-1}$
paired. We write $\rho\vdash_{B}\langle{n}\rangle$ and let
$S_{B}(\langle{n}\rangle,k)$ denote the set of all type $B$ partitions of
$\langle{n}\rangle$ with $2k+1$ blocks.

For readability, we will sometimes use an overline to represent a negative
sign and group the paired blocks together separated by a forward slash, while
vertical slashes separate pairs. Finally, set braces and commas may be
removed.

######  Example 3.3.

To illustrate, an element of $S_{B}(\langle{7}\rangle,2)$ is

$\rho=0\overline{1}1\overline{3}3\overline{6}6\mid\overline{4}/4\mid
2\overline{5}7/\overline{2}5\overline{7}.$

Note that we may write the elements of any block in any order, reverse the
order of any pair, and rearrange the pairs amongst themselves without changing
the type $B$ partition.

Let $|S|=\\{|s|\ :\ s\in S\\}$, so that $|S_{2i}|=|S_{2i-1}|$ for $i\geq 1$.
For all $i$ we let

$m_{i}=\min|S_{i}|.$

We will always write signed partitions in standard form which means that

  1. 1.

$m_{2i}\in S_{2i}$ for all $i$, and

  2. 2.

$0=m_{0}<m_{2}<m_{4}<\dots<m_{2k}$.

######  Example 3.4.

The standard form of our example type $B$ partition above is

$\rho=0\overline{1}1\overline{3}3\overline{6}6\mid\overline{2}5\overline{7}/2\overline{5}7\mid\overline{4}/4$

with $m_{0}=0$, $m_{1}=m_{2}=2$, and $m_{3}=m_{4}=4$.

######  Definition 3.5.

An inversion of $\rho\vdash_{B}\langle{n}\rangle$ written in standard form is
a pair $(s,S_{j})$ satisfying

  1. 1.

$s\in S_{i}$ for some $i<j$, and

  2. 2.

$s\geq m_{j}$.

Let $\operatorname{Inv}\rho$ be set of inversions of $\rho$ and
$\operatorname{inv}\rho=\\#\operatorname{Inv}\rho$ where the hash tag denotes
cardinality.

While we have not specified the order of elements within each block, this does
not affect which pairs form inversions. Note that the second condition implies
that any $s$ causing an inversion must be positive. Note also that in this
condition it is not actually possible for $s=m_{i}$ because of the partition
being in standard form. However, we include it because when considering
ordered set partitions equality will be possible and such cases will need to
be counted.

######  Example 3.6.

Continuing our example,

$\operatorname{Inv}\rho=\\{(3,S_{1}),(3,S_{2}),(6,S_{1}),(6,S_{2}),(6,S_{3}),(6,S_{4}),(5,S_{2}),(5,S_{3}),(5,S_{4}),(7,S_{3}),(7,S_{4})\\}$

so that $\operatorname{inv}\rho=11$.

The $S_{B}[n,k]$ count signed partitions by inversions. The next theorem is a
type $B$ analogue of the result of Milne [Mil82] cited in the introduction for
$S[n,k]$. See also Section 6.2 for a strongly related interpretation involving
the Hilbert series of a conjectural monomial basis.

######  Theorem 3.7.

We have

$S_{B}[n,k]=\sum_{\rho\in
S_{B}(\langle{n}\rangle,k)}q^{\operatorname{inv}\rho}.$

###### Proof.

We proceed by induction on $n$ where the base case is trivial. Given $\rho\in
S_{B}(\langle{n}\rangle,k)$ we can remove $n$ and $-n$ to obtain a new
partition $\rho^{\prime}$.

If $n$ (and thus $-n$) is in a singleton block then $\rho^{\prime}\in
S_{B}(\langle{n-1}\rangle,k-1)$ and there is only one way to construct $\rho$
from $\rho^{\prime}$. Furthermore, in this case the standardization condition
forces $S_{2k-1}=\\{-n\\}$ and $S_{2k}=\\{n\\}$ in $\rho$. It follows that
$\operatorname{inv}\rho=\operatorname{inv}\rho^{\prime}$. So, by induction,
such $\rho$ contribute $S_{B}[n-1,k-1]$ to the sum.

If $n$ (and thus $-n$) is in a block with other elements, then
$\rho^{\prime}\in S_{B}(\langle{n-1}\rangle,k)$. The possible $\rho$ giving
rise to a fixed $\rho^{\prime}$ are obtained by inserting $n$ in one of the
$2k+1$ blocks of $\rho^{\prime}$. And if $n$ is put in block $S_{i}$ then this
adds inversions of the form $(n,S_{j})$ for all $j>i$. Furthermore the
placement of $-n$, wherever it is forced by that of $n$, does not contribute
any inversions. So
$\operatorname{inv}\rho=2k-i+\operatorname{inv}\rho^{\prime}$ where $0\leq
i\leq 2k$. Thus the contribution of these $\rho$ is $[2k+1]S_{B}[n-1,k]$ and
we are done. ∎

######  Definition 3.8.

The descent set of $\rho\in S_{B}(\langle{n}\rangle,k)$ is the multiset

$\operatorname{Des}\rho=\\{\\!\\{1^{n_{1}},2^{n_{2}},\dots,(2k)^{n_{2k}}\\}\\!\\}$

where $n_{i}$ is the number of elements of $S_{i-1}$ which are greater than
$m_{i}$. Define the major index of $\rho$ to be

$\operatorname{maj}\rho=1\cdot n_{1}+2\cdot n_{2}+\cdots+2k\cdot n_{2k}.$

Note that this convention differs from the one for descents in a permutation
in the symmetric group since $i$ is the index of the block containing the
smaller integer. This could be fixed by renumbering the blocks, but then the
conventions above for $S_{0}$ would become less natural.

######  Example 3.9.

In our perennial example, descents are caused by the $3$ and $6$ in $S_{0}$,
the $5$ in $S_{1}$, and the $7$ in $S_{2}$. Hence
$\operatorname{Des}\rho=\\{\\!\\{1^{2},2^{1},3^{1}\\}\\!\\}$ and
$\operatorname{maj}\rho=1\cdot 2+2\cdot 1+3\cdot 1=7$.

Just as with permutations in the symmetric group, $\operatorname{inv}$ and
$\operatorname{maj}$ have the same distribution over signed partitions.

######  Theorem 3.10.

We have

$S_{B}[n,k]=\sum_{\rho\in
S_{B}(\langle{n}\rangle,k)}q^{\operatorname{maj}\rho}.$

###### Proof.

We proceed as in the previous proof, keeping the same notation. When $n$ and
$-n$ are in singleton blocks, the same reasoning applies to show
$\operatorname{maj}\rho=\operatorname{maj}\rho^{\prime}$. So, as before, such
$\rho$ contribute $S_{B}[n-1,k-1]$ to the sum. Now assume that $n$ is inserted
into a block of $\rho^{\prime}$ and $-n$ into the companion block. If $n$ is
in $S_{i}$ then

$\operatorname{maj}\rho=\left\\{\begin{array}[]{ll}\operatorname{maj}\rho^{\prime}&\mbox{if
$i=2k$,}\\\ i+1+\operatorname{maj}\rho^{\prime}&\mbox{if $0\leq
i<2k$.}\end{array}\right.$

Thus the contribution of these $\rho$ is $[2k+1]S_{B}[n-1,k]$ which finishes
the proof. ∎

It is possible to give a combinatorial proof of equation (14) by showing that
when $t$ is a positive integer both sides count the set of functions
$f:[n]\rightarrow[t]$. We will now give a combinatorial proof of 2.4 when
$q=1$ using similar ideas.

######  Definition 3.11.

A type $B$ function is any function
$f:\langle{n}\rangle\rightarrow\langle{p}\rangle$ satisfying

$f(-i)=-f(i)$ (15)

for all $i\in\langle{n}\rangle$. The kernel of $f$ is the partition $\ker f$
of $\langle{n}\rangle$ whose blocks are the nonempty fibers $f^{-1}(j)$ for
$j\in\langle{p}\rangle$.

In particular, a type $B$ function satisfies $f(0)=0$, and if $f(i)=0$, then
$f(-i)=0$. Hence the definition of a type $B$ function ensures that $\ker f$
is a type $B$ partition.

Define the type $B$ falling factorial to be

$t\downarrow_{k}^{B}=(t;1)\downarrow_{k}^{B}=(t-1)(t-3)\cdots(t-2k+1).$

The next result is the special case $q=1$ of 2.4. But here we give a
combinatorial proof rather than relying on symmetric functions. We note that
this result with essentially the same proof below was also given in a paper of
Bagno and Garber [BG22], but we include it for completeness.

######  Theorem 3.12.

For $n\in{\mathbb{N}}$,

$t^{n}=\sum_{k}S_{B}(n,k)t\downarrow^{B}_{k}.$

###### Proof.

Since this is a polynomial identity, it suffices show that it holds when $t$
is an odd positive integer, say $t=2p+1$. We claim that in this case both
sides of the identity count the number of type $B$ functions
$f:\langle{n}\rangle\rightarrow\langle{p}\rangle$.

On the one hand, we can determine $f$ by first choosing $f(1),\dots,f(n)$, in
which case $f(-1),\dots,f(-n)$ are determined by (15). And we know $f(0)=0$.
Since $\\#\langle{p}\rangle=t$, there are $t$ ways to choose each of the
necessary values, for a total count of $t^{n}$.

Alternatively, we can construct $f$ by first picking a type $B$ partition
$\rho=S_{0}/S_{1}/\dots/S_{2k}$ of $\langle{n}\rangle$ to be $\ker f$ and then
injectively mapping the blocks of $\rho$ into $\langle{p}\rangle$. Since $0\in
S_{0}$ we must have $f(S_{0})=0$. This leaves $t-1$ choices for $f(S_{1})$.
Now $f(S_{2})$ is determined by (15). There remains $t-3$ choices for
$f(S_{3})$, and so forth. ∎

###  3.2 Signed permutations

We now turn to the Stirling numbers of the first kind. A permutation of a
finite set $S$ is a bijection $\pi:S\rightarrow S$. As usual, $\pi$ can be
factored into cycles $c=(a_{1},a_{2},\ldots,a_{k})$ where $\pi(a_{i})=a_{i+1}$
with subscripts taken modulo $k$. Let
$\langle{n}\rangle^{\prime}=\langle{n}\rangle\setminus\\{0\\}$.

######  Definition 3.13.

A signed or type $B$ permutation is a permutation $\pi$ of
$\langle{n}\rangle^{\prime}$ satisfying

$\pi(-i)=-\pi(i)$ (16)

for all $i\in\langle{n}\rangle^{\prime}$.

This condition implies that any cycle $c$ of $\pi$ is of one of two types.

  1. 1.

If $c=(a_{1},a_{2},\ldots,a_{k})$ does not contain both $i$ and $-i$ for any
$i\in\langle{n}\rangle^{\prime}$ then $\pi$ also contains
$-c=(-a_{1},-a_{2},\ldots,-a_{k})$. We say that $c$ and $-c$ are paired.

  2. 2.

If $c$ contains both $i$ and $-i$ for some $i\in\langle{n}\rangle^{\prime}$
then $c$ must have the form

$c=(a_{1},a_{2},\ldots,a_{k},-a_{1},-a_{2},\ldots,-a_{k}).$

We call such a cycle unpaired.

Finally, let $c_{B}(\langle{n}\rangle^{\prime},k)$ be the set of all $B_{n}$
permutations with $2k$ paired cycles.

We use the same conventions when writing signed cycle decomposition as for
partitions, using bars instead of negative signs and keeping paired cycles
closer together than others.

######  Example 3.14.

In the permutation

$\pi=(1,\overline{3},\overline{1},3)\ (\overline{4})(4)\
(2,\overline{5},7)(\overline{2},5,\overline{7})\ (\overline{6},6)$

the four cycles $(\overline{4})$, $(4)$, $(2,\overline{5},7)$, and
$(\overline{2},5,\overline{7})$ are paired while the cycles
$(1,\overline{3},\overline{1},3)$ and $(\overline{6},6)$ are not. Since there
are $k=2$ cycle pairs, $\pi\in c_{B}(\langle{7}\rangle^{\prime},2)$.

We will use the absolute value and minimum notation for permutations exactly
as we did for partitions. Our standard form for a $B_{n}$ permutation
$\pi=c_{1}c_{2}\ldots c_{\ell}$ will be to list the cycles so that the minima
$m_{i}=\min|c_{i}|$ satisfy

  1. 1.

$m_{1}\leq m_{2}\leq\ldots\leq m_{\ell}$,

  2. 2.

if $m_{i}=m_{i+1}$ then $-m_{i}\in c_{i}$ and $m_{i+1}\in c_{i+1}$,

  3. 3.

each $c_{i}$ is listed with its $\pm m_{i}$ last, with unpaired cycles ending
in $-m_{i}$.

Putting our example permutation is standard form gives

$\pi=(3,1,\overline{3},\overline{1})\
(5,\overline{7},\overline{2})(\overline{5},7,2)\ (\overline{4})(4)\
(6,\overline{6}).$

######  Definition 3.15.

Given $\pi\in c_{B}(\langle{n}\rangle^{\prime},k)$ in standard form, we let
$w=w_{1}w_{2}\ldots w_{2n}$ be the word obtained by removing the parentheses
from $\pi$. Define the set of inversions of $\pi$ to be

$\operatorname{Inv}\pi=\\{(i,j)\ :\ \text{$i<j$ and $w_{i}>|w_{j}|$}\\}$

with corresponding inversion number

$\operatorname{inv}\pi=\\#\operatorname{Inv}\pi.$

######  Example 3.16.

For our running example permutation, we have

$w=3,1,\overline{3},\overline{1},5,\overline{7},\overline{2},\overline{5},7,2,\overline{4},4,6,\overline{6}.$

Hence $\operatorname{Inv}\pi$ is the set of pairs

$(1,2),(1,4),(1,7),(1,10),(5,7),(5,10),(5,11),(5,12),(9,10),(9,11),(9,12),(9,13),(9,14)$

and $\operatorname{inv}\pi=13$.

######  Theorem 3.17.

We have

$c_{B}[n,k]=\sum_{\pi\in
c_{B}(\langle{n}\rangle^{\prime},k)}q^{\operatorname{inv}\pi}.$

###### Proof.

As usual, we induct on $n$ and only give details for the induction step. Take
$\pi\in c_{B}(\langle{n}\rangle^{\prime},k)$ and remove $n$ and $-n$ to form
$\pi^{\prime}$.

If $n$ and $-n$ were both fixed points, then $\pi^{\prime}\in
c_{B}(\langle{n-1}\rangle^{\prime},k-1)$. Furthermore, standard form forces
the last two cycles of $\pi$ to be $(-n)(n)$ so that
$\operatorname{inv}\pi=\operatorname{inv}\pi^{\prime}$. Thus permutations in
this case give a contribution of $c_{B}[n-1,k-1]$ to the sum.

The other possibility is that $n$ and $-n$ are both in cycles of length at
least two. If these cycles are paired, then they remain paired cycles after
these elements are removed. If both elements are in the same unpaired cycle
then, even if that cycle contains no other elements, upon removal
$\pi^{\prime}$ still has the same number of paired cycles. So in either case
$\pi^{\prime}\in c_{B}(\langle{n-1}\rangle^{\prime},k)$.

Now consider all the ways $\pm n$ can be inserted in a given $\pi^{\prime}$ in
this case. Note that the position of $n$ determines the position of $-n$, and
that $-n$ can never cause any inversions. One possibility is to adjoin the
cycle $(n,-n)$ to $\pi$ which must be at the right end to be in standard form.
Now $n$ causes no inversions either so
$\operatorname{inv}\pi=\operatorname{inv}\pi^{\prime}$. The other possibility
is that $n$ is inserted just before, and in the same cycle as, any of the
$2n-2$ elements of $\pi^{\prime}$. (One must use the space before since using
the space after a final element in a cycle would make the result nonstandard.)
If this element is the $i$th from the right then
$\operatorname{inv}\pi=i+\operatorname{inv}\pi^{\prime}$ where $1\leq i\leq
2n-2$. It follows that the total contribution of this case is

$(q^{0}+q^{1}+\cdots+q^{2n-2})c_{B}[n-1,k]=[2n-1]c_{B}[n-1,k]$

which finishes the proof. ∎

Letting $q=1$ in the previous theorem gives the following result.

######  Corollary 3.18.

The number of $B_{n}$ permutations with $2k$ paired cycles is $c_{B}(n,k)$.

###  3.3 The lattice of signed partitions

We now connect the $S_{B}(n,k)$ and $s_{B}(n,k)$ with the intersection lattice
for the Coxeter group $B_{n}$.

######  Definition 3.19.

Let $P$ be a finite poset (partially ordered set) with a unique minimal
element $\hat{0}$. Call $P$ ranked if, for every $x\in P$, all maximal chains
from $\hat{0}$ to $x$ have the same length. This length is called the rank of
$x$ and denoted $\operatorname{rk}x$. The $k$th rank of $P$ is

$\operatorname{Rk}(P,k)=\\{x\in P\ :\ \operatorname{rk}x=k\\}$

with corresponding Whitney number of the second kind

$W(P,k)=\\#\operatorname{Rk}(P,k).$

The (one variable) Möbius function of $P$ is the function
$\mu:P\rightarrow{\mathbb{Z}}$ defined recursively by

$\sum_{x\leq y}\mu(x)=\delta_{\hat{0},y}.$

This is a far-reaching generalization of the Möbius function in number theory.
See [Sag20] or [Sta97] for more details. The Whitney numbers of the first kind
for $P$ are

$w(P,k)=\sum_{x\in\operatorname{Rk}(P,k)}\mu(x).$

If $P$ has a unique maximal element $\hat{1}$ then we will use the notation

$\mu(P)=\mu(\hat{1}).$

######  Definition 3.20.

For any finite set $S$ we denote by $\Pi_{S}$ the lattice of all set
partitions of $S$ ordered by refinement so that $\rho\leq\sigma$ if every
block of $\rho$ is contained in some block of $\sigma$. Let $\Pi_{B_{n}}$
denote the subposet of $\Pi_{\langle{n}\rangle}$ obtained by restricting the
partial order to the type $B$ partitions. We call $\Pi_{B_{n}}$ the $B_{n}$
partition lattice.

The Coxeter group $B_{n}$ has reflecting hyperplanes $x_{i}=0$ and $x_{i}=\pm
x_{j}$ where $i,j\in[n]$ and $x_{i}$ is the $i$th coordinate function. The
corresponding intersection lattice, ${\cal L}_{B_{n}}$, is the set of all
subspaces which are intersections of these hyperplanes ordered by reverse
inclusion. Zaslavsky [Zas81] showed that these subspaces are in bijective
correspondence with certain signed graphs which are clearly in bijection with
signed set partitions of $\langle{n}\rangle$. It easily follows that ${\cal
L}_{B_{n}}$ and $\Pi_{B_{n}}$ are isomorphic.

It will be useful to connect type $B$ partitions and permutations. Given a
signed permutation $\pi$, its underlying signed set partition is $\rho$
obtained by replacing every paired cycle by its underlying subset, and taking
the union of the sets underlying all paired cycles together with $\\{0\\}$ to
be the zero block. The reader can verify that our recurring example $\pi$ and
$\rho$ satisfy this relation. We let $B(\rho)$ be the set of type $B$
permutations with underlying set $\rho$. The first and third parts of the next
result also follow from [Zas81].

######  Theorem 3.21.

Fix $n\in{\mathbb{N}}$ and let $\mu$ be the Möbius function of $\Pi_{B_{n}}$.

  1. (a)

For $0\leq k\leq n$, we have $W(\Pi_{B_{n}},k)=S_{B}(n,n-k)$.

  2. (b)

If $\rho=S_{0}/S_{1}/S_{2}/\ldots/S_{2k}\in S_{B}(\langle{n}\rangle,k)$ then

$\displaystyle\\#B(\rho)$
$\displaystyle=(\\#S_{0}-2)!!\prod_{i=1}^{k}(\\#S_{2i}-1)!$
$\displaystyle=(-1)^{n-k}\mu(\rho).$

  3. (c)

For $0\leq k\leq n$ we have $w(\Pi_{B_{n}},k)=s_{B}(n,n-k)$.

###### Proof.

To prove (a), if $\rho$ is covered by $\sigma$ in $\Pi_{B_{n}}$, then there
are two possibilities. One is that there were two pairs of blocks
$S_{2i-1},S_{2i}$ and $S_{2j-1},S_{2j}$ in $\rho$ which were replaced in
$\sigma$ by a pair whose component blocks are unions of one block from each of
the given pairs. The other is that a pair $S_{2i-1},S_{2i}$ was absorbed into
the zero block. Note that in either case, the total number of blocks decreases
by two in passing from $\rho$ to $\sigma$. Using this fact, the desired result
now follows from an easy induction on $k$.

For the first equality in (b), note that, for $i\geq 1$, the number of ways to
turn $S_{2i}$ into a cycle is $(\\#S_{2i}-1)!$. And once a cycle is put on
$S_{2i}$, the cycle on $S_{2i-1}$ is fixed. So, letting $\\#S_{0}=2m+1$, it
suffices to show that the number of ways to decompose $S_{0}\setminus\\{0\\}$
into unpaired cycles is $(2m-1)!!$. But the count we seek is the number of
signed permutations of $\langle{m}\rangle^{\prime}$ which have no paired
cycles. By 3.18 and 2.1(a) with $q=1$, this is
$c_{B}(m,0)=e_{m}(1,3,\ldots,2m-1)=(2m-1)!!$.

We now prove (c) and the second equality in (b) simultaneously by induction on
$n$. From the description of the covering relations in part (a) we see that
the interval $[\hat{0},\rho]$ in $\Pi_{B_{n}}$ is isomorphic to a product of
posets, with one poset for $S_{0}$ and one for each pair $S_{2i-1},S_{2i}$ for
$1\leq i\leq k$. For $i\geq 1$, the partitions contained in $S_{2i}$ form the
lattice $\Pi_{S_{2i}}$. And once a partition $\sigma$ of $S_{2i}$ is chosen,
then $S_{2i-1}$ must be partitioned so that each block is the negative of some
block of $\sigma$. For the zero block, the partitions contained in $S_{0}$
contribute the lattice $\Pi_{B_{m}}$. Thus we have the isomorphism

$[\hat{0},\rho]\cong\Pi_{B_{m}}\times\Pi_{S_{2}}\times\Pi_{S_{4}}\times\cdots\times\Pi_{S_{2k}}$

and, since $\mu(P\times Q)=\mu(P)\mu(Q)$,

$\mu(\rho)=\mu(\Pi_{B_{m}})\prod_{i=1}^{k}\mu(\Pi_{S_{2i}}).$ (17)

It is well known that $\mu(\Pi_{S})=(-1)^{\\#S-1}(\\#S-1)!$. And we can assume
by induction that for $m<n$ we have $\mu(\Pi_{B_{m}})=(-1)^{m}(2m-1)!!$.
Plugging these values into (17) proves the second equality in (b) as long as
$\rho<\hat{1}$. Furthermore, from the proof of (a), the $\rho$ at rank $k$ of
$\Pi_{B_{n}}$ are exactly those signed partitions of $\langle{n}\rangle$ with
$2(n-k)+1$ blocks. It follows that for $\rho<\hat{1}$, the sum of the $\mu$
values of these partitions is exactly $(-1)^{k}c_{B}(n,n-k)=s_{B}(n,n-k)$.

To handle the case $\rho=\hat{1}$, we use the definition of $\mu$ and the
previous paragraph to give

$\mu(\hat{1})=-\sum_{\rho<\hat{1}}\mu(\rho)=-\sum_{k<n}s_{B}(n,n-k).$

On the other hand, plugging in $q=1$ and $t=-1$ to 2.1(c) and multiplying both
sides by $(-1)^{n}$ gives

$\sum_{k=0}^{n}s_{B}(n,k)=0.$

Comparing the last two displayed equations and using 2.1(a) when $q=1$ and
$k=0$ yields

$\mu(\hat{1})=s_{B}(n,0)=(-1)^{n}e_{n}(1,3,\ldots,2n-1)=(-1)^{n}(2n-1)!!$

which finishes this case and the proof. ∎

##  4 Exponential and $q$-exponential generating functions

We now derive exponential and $q$-exponential generating functions for the
Stirling numbers and $q$-Stirling numbers of types $A$ and $B$. We give
combinatorial proofs for the former using the theory of species. See the book
of Bergeron, Labelle, and Leroux [BLL98] or [Sag20, Chapter 4] for more
information. For the latter, we use the theory of $q$-difference equations.
Existence and uniqueness of solutions of linear $q$-difference equations with
constant coefficients is given explicitly in [AM12, Thm. 2.11]. A general
existence and uniqueness result for $q$-difference equations is given in
[AM12, Thm. 2.1]. Basic properties of $q$-derivatives such as their definition
and the $q$-product rule are summarized in [AM12, §1.3].

Our $q$-exponential generating function identities do not seem to be known for
the Stirling numbers even for $S[n,k]$ and $s[n,k]$. Consequently, we will
provide full proofs of these results in type $A$ and then just sketch whatever
changes are needed for type $B$.

###  4.1 Exponential generating functions

The following identities are well known; see e.g. [DLMF, §26.8(ii)], [OEI22,
A008275], and [OEI22, A008277].

$\displaystyle\displaystyle\sum_{n\geq 0}S(n,k)\frac{x^{n}}{n!}$
$\displaystyle=\frac{1}{k!}(e^{x}-1)^{k},$
$\displaystyle\displaystyle\sum_{n,k\geq 0}S(n,k)t^{k}\frac{x^{n}}{n!}$
$\displaystyle=e^{t(e^{x}-1)},$ $\displaystyle\displaystyle\sum_{n\geq
0}c(n,k)\frac{x^{n}}{n!}$
$\displaystyle=\frac{1}{k!}\left(\ln\frac{1}{1-x}\right)^{k},$
$\displaystyle\displaystyle\sum_{n,k\geq 0}c(n,k)t^{k}\frac{x^{n}}{n!}$
$\displaystyle=\frac{1}{(1-x)^{t}}.$

The type $B$ analogues are as follows. The first is stated (without proof) in
[OEI22, A039755]. The last two are stated (again, without proof) in [OEI22,
A028338], though effectively using 2.1(c) as a definition.

######  Theorem 4.1.

We have

  1. (a)

$\displaystyle\sum_{n\geq
0}S_{B}(n,k)\frac{x^{n}}{n!}=\frac{1}{2^{k}k!}e^{x}(e^{2x}-1)^{k}$.

  2. (b)

$\displaystyle\sum_{k,n\geq
0}S_{B}(n,k)t^{k}\frac{x^{n}}{n!}=e^{x}\sqrt{e^{t(e^{2x}-1)}}$.

  3. (c)

$\displaystyle\sum_{n\geq
0}c_{B}(n,k)\frac{x^{n}}{n!}=\frac{1}{k!\sqrt{1-2x}}\left(\log\frac{1}{\sqrt{1-2x}}\right)^{k}$.

  4. (d)

$\displaystyle\sum_{k,n\geq
0}c_{B}(n,k)t^{k}\frac{x^{n}}{n!}=\left(\frac{1}{\sqrt{1-2x}}\right)^{1+t}$.

###### Proof.

We will only prove (a) and (c) since then (b) and (d) follow by summing on
$k$.

For (a) note there is a bijection between type $B$ partitions
$S_{0}/\ldots/S_{2k}$ and ordered pairs of the form
$(T_{0},S_{2}/S_{4}/\ldots/S_{2k})$ where $T_{0}$ is the (possibly empty) set
of positive integers in $S_{0}$. This is because the other elements of $S_{0}$
are $-S_{0}\uplus\\{0\\}$ and $S_{2i-1}=-S_{2i}$ for all $i$.

By the conventions for the $S_{2i}$, its smallest element is positive and the
others can be signed arbitrarily. Consider the species ${\cal S}$ such that
${\cal S}(L)$ is all sets obtained from a set of nonempty integers $L$ by
arbitrarily signing every element of $L$ except the smallest. The number of
such sets is $2^{\\#L-1}$ with corresponding exponential generating function

$\sum_{n\geq 1}2^{n-1}\frac{x^{n}}{n!}=\frac{1}{2}(e^{2x}-1).$

So, by the Product Rule for exponential generating functions [Sag20, Theorem
4.4.2(b)], the exponential generating function for ordered $k$-tuples of such
sets is $(e^{2x}-1)^{k}/2^{k}$. We must divide by $k!$ to remove the order.
For $T_{0}$, we use the species ${\cal T}(L)=\\{L\\}$ which has exponential
generating function $e^{x}$ since $\\#{\cal T}(L)=1$ for all $L$. Now using
the Product Rule again completes the proof of (a).

To prove (c), consider a type $B$ permutation $\pi$ and its underlying
partition $\rho$. As in part (a), we can reconstruct $\rho$ from a pair
$(T_{0},S_{2}/S_{4}/\ldots/S_{2k})$. To recover the possible $\pi$ associated
with $\rho$ we must sign all but the smallest element of $S_{2i}$ and then put
a cycle on these elements, where the latter can be done in $(n-1)!$ ways if
$\\#S_{2i}=n$. This gives the exponential generating function

$\sum_{n\geq 1}(n-1)!2^{n-1}\frac{x^{n}}{n!}=\frac{1}{2}\sum_{n\geq
1}\frac{(2x)^{n}}{n}=\log\frac{1}{\sqrt{1-2x}}.$

On the other hand, if $\\#T_{0}=n$ then the elements in $T_{0}\uplus(-T_{0})$
need to be turned into unpaired cycles. By 2.1(a), this can be done in
$c_{B}(n,0)=(2n-1)!!$ ways which gives an exponential generating function of

$\sum_{n\geq 0}(2n-1)!!\frac{x^{n}}{n!}=\sum_{n\geq
0}(-1/2)\downarrow_{n}(-2)^{n}\frac{x^{n}}{n!}=\sum_{n\geq
0}\binom{-1/2}{n}(-2x)^{n}=\frac{1}{\sqrt{1-2x}}.$

Using the Product Rule and dividing by $k!$ to remove the order finishes the
proof. ∎

###  4.2 $q$-exponential generating functions

For our $q$-exponential generating functions, we will need the $q$-binomial
coefficients

$\left[\begin{array}[]{c}n\\\ k\end{array}\right]=\frac{[n]!}{[k]![n-k]!},$

the $q$-exponential function

$\exp_{q}(x)=\sum_{n\geq 0}\frac{x^{n}}{[n]!},$

the $q$-logarithm

$-\log_{q}(1-x)=\sum_{n=1}^{\infty}\frac{x^{n}}{[n]},$

as well as the $q$-derivative

$D_{q}f(x)=\frac{f(qx)-f(x)}{qx-x}.$

See [AM12, §1.3] for a summary of $q$-calculus. It will also be convenient to
find the $q$-exponential generating functions for the ordered versions of the
Stirling numbers of the second kind.

######  Theorem 4.2.

We have

$\sum_{n\geq
0}S^{o}[n,k]\frac{x^{n}}{[n]!}=\frac{1}{q^{\binom{k}{2}}}\sum_{i=0}^{k}(-1)^{k-i}q^{\binom{k-i}{2}}\left[\begin{array}[]{c}k\\\
i\end{array}\right]\exp_{q}([i]x),$ (18)

and

$\sum_{n,k\geq
0}S^{o}[n,k]t^{k}\frac{x^{n}}{[n]!}=\sum_{i=0}^{\infty}\frac{q^{i}t^{i}}{(1+t)(q+t)\cdots(q^{i}+t)}\exp_{q}([i]x).$

###### Proof.

To simplify the proof of the first equality, let

$E_{k}=\sum_{n\geq 0}S^{o}[n,k]\frac{x^{n}}{[n]!}=\sum_{n\geq
0}[k]!S[n,k]\frac{x^{n}}{[n]!}.$

From the recursion (2) we get that

$S^{o}[n,k]=[k](S^{o}[n-1,k-1]+S^{o}[n-1,k])$ (19)

for $n\geq 1$. Combining this with the $q$-derivative

$D_{q}x^{n}=[n]x^{n-1}$

implies that

$D_{q}E_{k}=[k](E_{k}+E_{k-1})$ (20)

for all $k\in{\mathbb{Z}}$ with $E_{k}=0$ for $k<0$. This equation and
induction on $k$ give

$\left(\prod_{i=0}^{k}(D_{q}-[i])\right)E_{k}=0.$

Since $D_{q}\exp_{q}([i]x)=[i]\exp_{q}([i]x)$, the theory of linear, constant-
coefficient $q$-difference equations now implies that

$E_{k}=\sum_{i=0}^{k}c_{i}^{k}\exp_{q}([i]x)$ (21)

for certain $c_{i}^{k}$ which are constant with respect to $x$. So it suffices
to show that

$c_{i}^{k}=\frac{(-1)^{k-i}q^{\binom{k-i}{2}}}{q^{\binom{k}{2}}}\left[\begin{array}[]{c}k\\\
i\end{array}\right].$ (22)

Substituting (21) into (20) and using the linear independence of
$\\{\exp_{q}([i]x)\\}_{i\in{\mathbb{N}}}$ gives

$c_{i}^{k}=\frac{-[k]}{q^{i}[k-i]}c_{i}^{k-1}$

for $0\leq i\leq k-1$ which, after iteration, results in

$c_{i}^{k}=\frac{(-1)^{k-i}}{q^{i(k-i)}}\left[\begin{array}[]{c}k\\\
k-i\end{array}\right]c_{i}^{i}.$ (23)

Comparing this with (22) and using the identity

$i(k-i)+\binom{k-i}{2}=\binom{k}{2}-\binom{i}{2},$ (24)

we see that we will be done if we can show $c_{i}^{i}=q^{-\binom{i}{2}}$ for
$i\geq 0$. Let us rewrite this as $c_{k}^{k}=q^{-\binom{k}{2}}$ and induct on
$k$. Since $E_{k}(0)=\delta_{0,k}$, we see from (21) that
$c_{0}^{0}=1=q^{-\binom{0}{2}}$ and, for $k\geq 1$,

$\sum_{i=0}^{k}c_{i}^{k}=0.$

This equation determines $c_{k}^{k}$ in terms of the $c_{i}^{k}$ for $i<k$.
And the latter are known to have the desired form by equation (23) and
induction. So it suffices to prove that

$0=\sum_{i=0}^{k}\frac{(-1)^{k-i}}{q^{i(k-i)+\binom{i}{2}}}\left[\begin{array}[]{c}k\\\
k-i\end{array}\right]=\frac{1}{q^{\binom{k}{2}}}\sum_{i=0}^{k}(-1)^{k-i}q^{\binom{k-i}{2}}\left[\begin{array}[]{c}k\\\
k-i\end{array}\right]=\frac{1}{q^{\binom{k}{2}}}\sum_{i=0}^{k}(-1)^{i}q^{\binom{i}{2}}\left[\begin{array}[]{c}k\\\
i\end{array}\right].$

But this last sum is seen to be zero by substituting $t=-1$ into the
$q$-Binomial Theorem

$\prod_{i=0}^{k-1}(1+q^{i}t)=\sum_{i=0}^{k}q^{\binom{i}{2}}\left[\begin{array}[]{c}k\\\
i\end{array}\right]t^{i}.$ (25)

For the second equality in the statement of the theorem, we multiply (18) by
$t^{k}$ and sum to get

$\displaystyle\sum_{n,k\geq 0}[k]!S[n,k]t^{k}\frac{x^{n}}{[n]!}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{t^{k}}{q^{\binom{k}{2}}}\sum_{i=0}^{k}(-1)^{k-i}q^{\binom{k-i}{2}}\left[\begin{array}[]{c}k\\\
i\end{array}\right]\exp_{q}([i]x)$
$\displaystyle=\sum_{i=0}^{\infty}\frac{1}{q^{\binom{i}{2}}}\left(\sum_{k=i}^{\infty}\frac{(-1)^{k-i}}{q^{i(k-i)}}\left[\begin{array}[]{c}k\\\
i\end{array}\right]t^{k}\right)\exp_{q}([i]x)$
$\displaystyle=\sum_{i=0}^{\infty}\frac{q^{i}t^{i}}{(1+t)(q+t)\cdots(q^{i}+t)}\exp_{q}([i]x),$

where the second equality uses equation (24), and the third is a form of the
Negative $q$-Binomial Theorem as in Exercise 8(b) from Chapter 3 of [Sag20]
substituting $-t$ for $t$ and $1/q$ for $q$. ∎

The proof of the next result is similar to the one just given. So we will only
mention the highlights.

######  Theorem 4.3.

We have

$\sum_{n\geq
0}S_{B}^{o}[n,k]\frac{x^{n}}{[n]!}=\frac{1}{q^{k^{2}}}\sum_{i=0}^{k}(-1)^{k-i}q^{2\binom{k-i}{2}}\left[\begin{array}[]{c}k\\\
i\end{array}\right]_{q^{2}}\exp_{q}([2i+1]x),$

and

$\sum_{n,k\geq
0}S_{B}^{o}[n,k]t^{k}\frac{x^{n}}{[n]!}=\sum_{i=0}^{\infty}\frac{q^{2i+1}t^{i}}{(q+t)(q^{3}+t)\cdots(q^{2i+1}+t)}\exp_{q}([2i+1]x).$

###### Proof.

Let $F_{k}$ be the first sum. Using the recursion (8) and the fact that
$S_{B}^{o}[n,k]=[2k]!!S_{B}[n,k]$ we see that

$S_{B}^{o}[n,k]=[2k]S_{B}^{o}[n-1,k-1]+[2k+1]S_{B}^{o}[n-1,k]$

for $n\geq 1$, This in turn implies that for $k\in{\mathbb{Z}}$

$D_{q}F_{k}=[2k+1]F_{k}+[2k]F_{k-1}$ (26)

and $F_{k}=0$ for $k<0$. Thus $F_{k}$ satisfies the linear $q$-difference
equation

$\left(\prod_{i=0}^{k}(D_{q}-[2i+1])\right)F_{k}=0.$

So we can write

$F_{k}=\sum_{i=0}^{k}d_{i}^{k}\exp_{q}([2i+1]x)$

for certain constants $d_{i}^{k}$. To show that the $d_{i}^{k}$ have the
correct form, one uses (26) and iteration to get

$d_{i}^{k}=\frac{(-1)^{k-i}}{q^{(2i+1)(k-i)}}\left[\begin{array}[]{c}k\\\
k-i\end{array}\right]_{q^{2}}d_{i}^{i}.$

The analogue of (24) is

$(2i+1)(k-i)+i^{2}=k^{2}-2\binom{k-i}{2},$ (27)

which implies that we must show $d_{k}^{k}=q^{-k^{2}}$. This is accomplished
recursively using the $q$-Binomial Theorem (25) as before with the
substitutions $t=-1$ and $q^{2}$ for $q$.

The bivariate generating function is now obtained by summing over $k$ and
using the previous version of the Negative $q$-Binomial Theorem with
substitutions $-t/q$ for $t$ and $1/q^{2}$ for $q$. ∎

For the $q$-Stirling numbers of the first kind we will need to use a version
of the chain rule. Unfortunately, no such analogue exists for $D_{q}(g(f))$.
But Gessel [Ges82] defined a $q$-analogue of composition which does obey a
$q$-chain rule. Given an $q$-exponential generating function $f(x)$ with
$f(0)=1$, define its $k$th symbolic power recursively by $f^{[0]}=1$ and

$D_{q}f^{[k]}=[k]f^{[k-1]}D_{q}f.$

Note that $x^{[k]}=x^{k}$, so that when $q=1$ we have $f^{[k]}=f^{k}$ for
$k\geq 0$. Given $g=\sum_{n\geq 0}g_{n}x^{n}/[n]!$, Gessel then defines a
$q$-analogue of functional composition to be

$g[f]=\sum_{n\geq 0}g_{n}\frac{f^{[n]}}{[n]!}.$

Again, when $q=1$ we have $g[f]=g(f)$. Gessel’s $q$-analogue of the chain rule
states that

$D_{q}(g[f])=(D_{q}g)[f]D_{q}f.$ (28)

The first result of the next theorem was also obtained by Johnson [Joh96,
(4.12)].

######  Theorem 4.4.

We have

$\sum_{n\geq 0}c[n,k]\frac{x^{n}}{[n]!}=\frac{(-\log_{q}(1-x))^{[k]}}{[k]!},$

and

$\sum_{n,k\geq 0}c[n,k]t^{k}\frac{x^{n}}{[n]!}=\exp_{q}[-t\log_{q}(1-x)].$

###### Proof.

Let $C_{k}=\sum_{n\geq 0}c[n,k]x^{n}/[n]!$. The usual manipulations and the
recursion (5) give the $q$-difference equation

$D_{q}C_{k}=\frac{C_{k-1}}{1-x}$

for $k\in{\mathbb{Z}}$ with $C_{k}=0$ for $k<0$. The formula for $C_{k}$ now
follows from a simple induction on $k$ using the definition of symbolic power.
And the bivariate generating function is a consequence of the definition of
$q$-composition. ∎

Unfortunately, for the $c_{B}[n,k]$ we were only able to derive a differential
equation for the desired $q$-exponential generating function. We will have
more to say about this in Section 7.3.

##  5 Ordered analogues and identities

In this section we will prove alternating sum identities as well as
divisiblity results for the ordered $q$-Stirling numbers of the second kind.
The former will prove two conjectures of Swanson and Wallach [SW21]. Our main
tools will be the use of sign-reversing involutions. These results and their
demonstrations are new even in type $A$ so, as in the previous section, the
type $B$ proofs will only be sketched.

###  5.1 Alternating sums

We first need a combinatorial interpretation for the $S^{o}[n,k]$. These
polynomials count ordered set partitions of $[n]$ into $k$ blocks which are
sequences of nonempty sets $\omega=(S_{1}/S_{2}/\ldots/S_{k})$ such that
$\uplus_{i}S_{i}=[n]$. Note the use of parentheses to denote a sequence rather
than a family of sets. The set of these sequences is denoted $S^{o}([n],k)$.
We define the inversion statistic exactly the same as for unordered signed
partitions using 3.5, letting

$\operatorname{Inv}\omega=\\{(s,S_{j})\ :\ \text{$s\in S_{i}$ for some $i<j$
and $s\geq\min S_{j}$}\\}$ (29)

and $\operatorname{inv}\omega=\\#\operatorname{Inv}\omega$. Using a similar
proof to that of Theorem 3.7, one can show the following.

######  Theorem 5.1.

For $n,k\geq 0$ we have

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle S^{o}[n,k]=\sum_{\omega\in
S^{o}([n],k)}q^{\operatorname{inv}\omega}.}\hfill\qed$

######  Definition 5.2.

We now define the maps which will make up our involution in type $A$. Given an
ordered partition $\omega=(S_{1}/S_{2}/\ldots/S_{k})$, suppose $M=\max S_{i}$.
Say that $\omega$ is splittable at $M$ if $\\#S_{i}\geq 2$. In that case the
splitting map $\sigma_{M}$ is defined by

$\sigma_{M}(\omega)=(S_{1}/\ldots/S_{i-1}/\\{M\\}/S_{i}-\\{M\\}/S_{i+1}/\ldots/S_{k}).$

We define $\omega$ to be mergeable at $M$ if

  1. 1.

$S_{i}=\\{M\\}$, and

  2. 2.

$M>\max S_{i+1}$.

If these conditions hold then one can apply the merging map $\mu_{M}$ where

$\mu_{M}(\omega)=(S_{i}/\ldots/S_{i-1}/S_{i}\uplus
S_{i+1}/S_{i+2}/\ldots/S_{k}).$

######  Example 5.3.

The ordered set partition $\omega=(246/8/35/1/7)$ is splittable for $M=6$ and
$5$, and

$\sigma_{6}(\omega)=(6/24/8/35/1/7).$

On the other hand, $\omega$ is only mergeable for $M=8$ and

$\mu_{8}(\omega)=(246/358/1/7).$

Note that if $\omega$ is splittable at $M$, then $\sigma_{M}(\omega)$ is
mergeable at $M$ and $\mu_{M}\sigma_{M}(\omega)=\omega$. The same statement
holds with the roles of $\sigma_{M}$ and $\mu_{M}$ reversed. Merge and split
maps have been useful in a number of areas, including the computation of
antipodes in Hopf algebras as shown by Benedetti and Sagan [BS17]. We can now
define the involution we will use for our first alternating sum.

######  Definition 5.4.

Define $\phi:\uplus_{k}S^{o}([n],k)\rightarrow\uplus_{k}S^{o}([n],k)$ as
follows. Given $\omega\in S^{o}([n],k)$, find the largest $M$ (if any) such
that $\omega$ is either splitable or mergeable at $M=\max S_{i}$. Note that,
because of the restriction on $\\#S_{i}$ for these two operations, it can not
be both. Let

$\phi(\omega)=\begin{cases}\sigma_{M}(\omega)&\text{if $\omega$ is splittable
at $M$,}\\\ \mu_{M}(\omega)&\text{if $\omega$ is mergeable at $M$,}\\\
\omega&\text{if no such $M$ exists.}\end{cases}$

We see that $\phi$ is an involution because of the remarks at the end of the
last paragraph and the fact that the largest splittable or mergeable $M$ is
preserved by splitting or merging at this value.

######  Theorem 5.5.

For $n\geq 0$, we have

$\sum_{k=0}^{n}(-q)^{n-k}S^{o}[n,k]=1.$

###### Proof.

Define the sign of $\omega\in S^{o}([n],k)$ to be

$\operatorname{sgn}\omega=(-1)^{n-k}.$ (30)

The involution $\phi$ is sign-reversing on partitions which are not fixed
since both $\sigma_{M}$ and $\mu_{M}$ change the number of blocks of $\omega$
by $1$.

By 5.1, we can write

$\sum_{k=0}^{n}(-q)^{n-k}S^{o}[n,k]=\sum_{\omega\in\uplus_{k}S^{o}([n],k)}(\operatorname{sgn}\omega)q^{n-k+\operatorname{inv}\omega}.$
(31)

We claim that the terms for $\omega$ and $\phi(\omega)$ in equation (31) will
cancel each other since splitting adds one inversion and one block whereas
merging removes one inversion and one block, hence $n-k+\operatorname{inv}$ is
preserved by $\phi$.

To see that the claim holds when $\phi$ applies $\sigma_{M}$, note that since
$M$ is not the minimum of its block all the inversions of $\omega$ will still
be inversions of $\phi(\omega)$. Furthermore, if $M=\max S_{i}$ then splitting
off $M$ will cause a new inversion $(M,S_{i}-\\{M\\})$. Thus
$\operatorname{inv}\phi(\omega)=\operatorname{inv}\omega+1$. Since $\phi$ is
an involution, it also follows that
$\operatorname{inv}\phi(\omega)=\operatorname{inv}\omega-1$.

To complete the proof, it suffices to show that $\omega_{0}=(1,2,\ldots,n)$ is
a fixed point of $\phi$ and the only one since its contribution to (31) is
$1$. Clearly $\omega_{0}$ is fixed since it has no blocks of size at least $2$
and its block maxima are in increasing order. Conversely, if $\omega$ is a
fixed point, then it can have no blocks of size $2$ since then one could apply
$\sigma_{M}$. So $\omega$ is a sequence of singleton blocks with increasing
elements since otherwise $\mu_{M}$ could be applied. The sequence $\omega_{0}$
is the only ordered partition with these two properties. This finishes the
proof. ∎

To prove the type $B$ analogue of the previous theorem, we proceed in a
similar manner. An ordered signed partition of $\langle{n}\rangle$ is a
sequence $\omega=(S_{0}/S_{1}/S_{2}/\ldots/S_{2k})$ satisfying conditions (1)
and (2) in 3.2. Note that no assumption is made about standard form. The set
of such partitions with $2k+1$ blocks is denoted
$S_{B}^{o}(\langle{n}\rangle,k)$.

The definition of inversion in 3.5 remains unchanged. But now it is possible
to have an inversion where $s=m_{j}$ if $m_{j}\in S_{j-1}$ and $-m_{j}\in
S_{j}$. The usual arguments give us the following result.

######  Theorem 5.6.

For $n,k\geq 0$ we have

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle S_{B}^{o}[n,k]=\sum_{\omega\in
S_{B}^{o}(\langle{n}\rangle,k)}q^{\operatorname{inv}\omega}.}\hfill\qed$

######  Definition 5.7.

The splitting and merging maps have two cases in type $B$. Consider
$\omega=(S_{0}/\ldots/S_{2k})$ and $M>0$ which is in a block with at least two
elements. If $M=\max S_{2i-1}$ for some $i$, then $\sigma_{M}(\omega)$ is the
ordered signed partition formed by removing $M$ and $-M$ from their blocks and
adding a block pair $-M/M$ immediately to the left of what remains of
$S_{2i-1}$. If $M=\max S_{2i}$ for some $i$, then $\sigma_{M}(\omega)$ is
obtained by removing $M$ and $-M$ from their blocks (which will be the same if
$i=0$) and adding a block pair $M/{-M}$ immediately to the right of the
remains of $S_{2i}$.

Now suppose that $M$ is in a singleton block, which implies that the same is
true of $-M$. If the block pair is $S_{2i-1}/S_{2i}=-M/M$ and
$M>\max|S_{2i+1}|$ then add $M$ to $S_{2i+1}$ and $-M$ to $S_{2i+2}$ to form
$\mu_{M}(\omega)$. If the block pair is $S_{2i-1}/S_{2i}=M/{-M}$ and
$M>\max|S_{2i-2}|$ then $\mu_{M}(\omega)$ is obtained by adding $M$ to
$S_{2i-2}$ and $-M$ to the same block if $2i-2=0$ or to the block to its left
otherwise.

######  Example 5.8.

Here are examples of splitting (the forward arrows) and merging (the reverse
arrows) to illustrate all of the possible cases.

$\displaystyle(\overline{4}\overline{1}014\mid 2\overline{3}/\overline{2}3)$
$\displaystyle\stackrel{{\scriptstyle
M=4}}{{\longleftrightarrow}}(\overline{1}01\mid 4/\overline{4}\mid
2\overline{3}/\overline{2}3),$
$\displaystyle(\overline{5}\overline{4}045\mid\overline{2}3\overline{6}/2\overline{3}6\mid
1/\overline{1})$ $\displaystyle\stackrel{{\scriptstyle
M=6}}{{\longleftrightarrow}}(\overline{5}\overline{4}045\mid\overline{2}3/2\overline{3}\mid
6/\overline{6}\mid 1/\overline{1}),$
$\displaystyle(\overline{5}\overline{4}045\mid\overline{2}36/2\overline{3}\overline{6}\mid
1/\overline{1})$ $\displaystyle\stackrel{{\scriptstyle
M=6}}{{\longleftrightarrow}}(\overline{5}\overline{4}045\mid\overline{6}/6\mid\overline{2}3/2\overline{3}\mid
1/\overline{1}).$

The map
$\phi:\uplus_{k}S_{B}^{o}(\langle{n}\rangle,k)\rightarrow\uplus_{k}S_{B}^{o}(\langle{n}\rangle,k)$
is defined exactly as in 5.4 for the type $A$ case, merely substituting the
signed splitting and merging maps. As in the previous case, it is easy to see
that $\phi$ is an involution.

######  Theorem 5.9.

For $n\geq 0$ we have

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle\sum_{k=0}^{n}(-q)^{n-k}S^{o}_{B}[n,k]=1.}\hfill\qed$

###### Proof.

A sign is assigned to $\omega\in S_{B}^{o}(\langle{n}\rangle,k)$ using (30)
again. Now the proof continues in much the same manner as that of 5.5 using
the previous theorem in place of Theorem 5.1 and with unique fixed point
$\omega_{0}=(0,\overline{1},1,\overline{2},2,\ldots,\overline{n},n)$. ∎

Note that Theorems 5.5 and 5.9 can be given algebraic proofs by setting $t=1$
and then substituting $x_{i}=-q[i-1]$ or $x_{i}=-q[2i-1]$, respectively, in
2.2.

###  5.2 Divisibility

The following two results are about divisibility in the ring
${\mathbb{Z}}[q]$. They are analogues of 5.5 and 5.9 for larger powers of $q$.
Algebraically, the results here follow immediately from the corresponding ones
in the previous subsection by using the fact that

$q^{m(n-k)}\equiv\ q^{n-k}\ (\operatorname{mod}q^{m}-q)$

for $m\geq 1$ and $n>k$. We will also show how they can be proved
combinatorially using the sign-reversing involutions already developed.

######  Theorem 5.10.

For $m\geq 1$ and $n\geq 0$ we have

$\sum_{k=0}^{n}(-1)^{n-k}q^{m(n-k)}S^{o}[n,k]\equiv 1\
(\operatorname{mod}q^{m}-q).$

###### Proof.

Let $\Sigma$ be the sum under consideration. Then clearly $\Sigma$ has
constant term $1$ so that $\Sigma-1$ is divisible by $q$. We must also show
that it is divisible by $q^{m-1}-1$.

By 5.1, we can write

$\Sigma=\sum_{\omega\in\uplus_{k}S^{o}([n],k)}(\operatorname{sgn}\omega)q^{m(n-k)+\operatorname{inv}\omega}$

where the sign is given by (30). Recall that $\omega=(1,2,\ldots,n)$ is the
only fixed point of the involution $\phi$ on $S^{o}([n],k)$ and that its
contribution to the previous sum is $1$. So we need only modify the
demonstration of 5.5 by showing that, for non-fixed points $\omega\in
S^{o}([n],k)$ of $\phi$, the sum of the contributions of $\omega$ and
$\phi(\omega)$ is divisible by $q^{m-1}-1$.

We will just give details when $\phi$ applies $\mu_{M}$. But then
$\phi(\omega)$ has $k-1$ blocks and, as proved in the proof of 5.5,
$\operatorname{inv}\phi(\omega)=\operatorname{inv}\omega-1$. So, up to sign,
the contribution of these two ordered set partitions is

$q^{m(n-k)+\operatorname{inv}\omega}-q^{m(n-k+1)+\operatorname{inv}\omega-1}=(1-q^{m-1})q^{m(n-k)+\operatorname{inv}\omega}$

as desired. ∎

The type $B$ analogue of the previous result is obtained by modifying the
proof of 5.9 similarly to how we just modified the demonstration of 5.5. So we
omit the details.

######  Theorem 5.11.

For $n\geq 0$ we have

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle\sum_{k=0}^{n}(-1)^{n-k}q^{m(n-k)}S^{o}_{B}[n,k]\equiv
1\ (\operatorname{mod}q^{m}-q).}\hfill\qed$

##  6 Coinvariant algebras

In this section we will propose analogues of the Artin basis for certain super
coinvariant algebras in types $A$ and $B$. If these sets can be shown to be
bases, then it will follow that the corresponding bigraded Hilbert series can
be expressed in terms of ordered $q$-Stirling numbers. Since our bases are new
even in type $A$, we will deal with that case first and then move on to type
$B$.

###  6.1 Type $A$ coinvariants

Consider the $k$th power sum symmetric polynomial

$p_{k}(n)=x_{1}^{k}+x_{2}^{k}+\cdots+x_{n}^{k}.$

######  Definition 6.1.

The type $A$ coinvariant algebra is the finite-dimensional commutative algebra

$\operatorname{R}_{n}=\frac{{\mathbb{Q}}[x_{1},\ldots,x_{n}]}{\langle{p_{k}(n)\
:\ k\in[n]}\rangle}$

where ${\mathbb{Q}}$ is the rational numbers. This algebra is graded by degree
and we let $(\operatorname{R}_{n})_{d}$ denote the $d$th graded piece. We will
not make a distinction in our notation between a polynomial in
${\mathbb{Q}}[x_{1},\ldots,x_{n}]$ and its representative in
$\operatorname{R}_{n}$.

There is a standard basis for $\operatorname{R}_{n}$. We will use it as a
model for our bases in the super coinvariant algebras we consider.

######  Definition 6.2.

The Artin basis for $\operatorname{R}_{n}$ is

${\cal A}_{n}=\\{x_{1}^{m_{1}}x_{2}^{m_{2}}\cdots x_{n}^{m_{n}}\ :\
\text{$0\leq m_{i}\leq i-1$ for $i\in[n]$}\\}.$

The next result follows immediately from the fact that ${\cal A}_{n}$ is a
basis for $\operatorname{R}_{n}$. See LABEL:SW:hdf for further history and
details.

######  Theorem 6.3.

The coinvariant algebra $\operatorname{R}_{n}$ has Hilbert series

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle\operatorname{Hilb}(\operatorname{R}_{n};q):=\sum_{d\geq
0}\dim(\operatorname{R}_{n})_{d}\ q^{d}=[n]!.}\hfill\qed$

There is an alternative description of ${\cal A}_{n}$ in terms of compositions
which will be useful in the sequel. A weak composition of $d$ with $n$ parts
is a sequence of nonnegative integers $\alpha=(\alpha_{1},\ldots,\alpha_{n})$
where $|\alpha|:=\sum_{i}\alpha_{i}=d$. The diagram of $\alpha$ consists of
$n$ columns lying on the same line with $\alpha_{i}$ boxes in column $i$ for
$i\in[n]$. See the diagram on the left in Figure 1 for an example. We will
also use the partial order on compositions with $n$ parts given by
$\alpha\leq\beta$ if $\alpha_{i}\leq\beta_{i}$ for all $i\in[n]$,
equivalently, if the diagram of $\alpha$ is contained in the diagram of
$\beta$. This relation is also illustrated in Figure 1. Every composition
$\alpha=(\alpha_{1},\ldots,\alpha_{n})$ has an associated monomial

${\bf x}^{\alpha}=x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots
x_{n}^{\alpha_{n}}$

of degree $d=|\alpha|$. The Artin basis can be described as

${\cal A}_{n}=\\{{\bf x}^{\alpha}\ :\ \alpha\leq(0,1,\ldots,n-1)\\}.$

We call $(0,1,\ldots,n-1)$ the staircase.

$\leq$

Figure 1: The diagram of $\alpha=(0,1,2,1,3)$ contained in the staircase
$(0,1,2,3,4)$

There is a third description of ${\cal A}_{n}$ involving permutations in the
symmetric group ${\mathfrak{S}}_{n}$. As usual, an inversion of a permutation
$\pi=\pi_{1}\ldots\pi_{n}$ written in one-line notation is a pair $(i,j)$ with
$i<j$ and $\pi_{i}>\pi_{j}$. Let

$\operatorname{inv}_{i}\pi=\\#\\{j\ :\ \text{$(i,j)$ is an inversion of
$\pi$}\\}.$

The inversion composition of $\pi\in{\mathfrak{S}}_{n}$ is

$I(\pi)=(\operatorname{inv}_{1}(\pi),\operatorname{inv}_{2}(\pi),\ldots,\operatorname{inv}_{n}(\pi)).$

Clearly $I(\pi)\leq(0,1,\ldots,n-1)$. In fact, it is well-known and easy to
prove that the map

$I:{\mathfrak{S}}_{n}\rightarrow\\{\alpha\ :\ \alpha\leq(0,1,\ldots,n-1)\\}$

is a bijection. It follows that

${\cal A}_{n}=\\{{\bf x}^{I(\pi)}\ :\ \pi\in{\mathfrak{S}}_{n}\\}.$

###  6.2 Type $A$ super coinvariants

We now turn our attention to super coinvariant algebras. Let
$\theta_{1},\ldots,\theta_{n}$ be anticommuting variables so that

$\theta_{i}\theta_{j}=-\theta_{j}\theta_{i}$

for all $i,j\in[n]$. Note that because of anticommutivity we have

$\theta_{i}^{2}=0$ (32)

for all $i\in[n]$. We also assume that the $\theta_{i}$ and $x_{j}$ commute
with each other. Define the $k$th super power sum polynomial to be

$sp_{k}(n)=x_{1}^{k}\theta_{1}+x_{2}^{k}\theta_{2}+\cdots+x_{n}^{k}\theta_{n}.$

######  Definition 6.4.

The type $A$ super coinvariant algebra is the finite-dimensional algebra

$\operatorname{SR}_{n}=\frac{{\mathbb{Q}}[x_{1},\ldots,x_{n},\theta_{1},\ldots,\theta_{n}]}{\langle{p_{k}(n),\
sp_{k-1}(n)\ :\ k\in[n]}\rangle}.$

This algebra is bi-graded where we let $(\operatorname{SR}_{n})_{d,e}$ denote
the graded piece with monomials which are of degree $d$ is the $x$’s and
degree $e$ in the $\theta$’s.

Zabrocki [Zab19] has conjectured a description for the tri-graded Frobenius
characteristic of the super-diagonal coinvariant algebra of
${\mathfrak{S}}_{n}$ involving two sets of commuting and one set of anti-
commuting variables. Specialized to $\operatorname{SR}_{n}$, it becomes the
following which explains our interest in this algebra.

######  Conjecture 6.5.

We have

$\operatorname{Hilb}(\operatorname{SR}_{n};q,t):=\sum_{d,e\geq
0}\dim(\operatorname{SR}_{n})_{d,e}\ q^{d}t^{e}=\sum_{k\geq
0}S^{o}[n,k]t^{n-k}.$

We will now propose an analogue of the Artin basis for
$\operatorname{SR}_{n}$. Note that by (32), nonzero $\theta$ monomials must
contain at most one copy of each $\theta_{i}$. So such monomials are indexed
by subsets $T\subseteq[n]$ and we let

$\theta_{T}=\theta_{t_{1}}\theta_{t_{2}}\cdots\theta_{t_{k}}$

where $T=\\{t_{1}<t_{2}<\cdots<t_{k}\\}$. Letting

$[a,b]=\\{a,a+1,\ldots,b\\}$

for $a,b\in{\mathbb{Z}}$, we will only need $T\subseteq[2,n]$ for our proposed
basis. Given such a subset we define the $\alpha$-sequence of $T$,
$\alpha(T)$, to be the composition constructed recursively by letting
$\alpha_{1}(T)=0$ and, for $i\in[2,n]$,

$\alpha_{i}(T)=\alpha_{i-1}(T)+\left\\{\begin{array}[]{ll}0&\mbox{if $i\in
T$,}\\\ 1&\mbox{if $i\not\in T$.}\end{array}\right.$

The diagram of an example of $\alpha(T)$ will be found in Figure 2.

$\alpha(T)=$$\epsilon(T)=$$(1,$$1,$$2,$$1)$$T=$$\\{2,$$4,$$6,$$7,$$9\\}$
Figure 2: The compositions $\alpha(T)$ and $\epsilon(T)$ when $n=9$ and
$T=\\{2,4,6,7,9\\}$

######  Definition 6.6.

The super Artin set for $\operatorname{SR}_{n}$ is

${\cal S}{\cal A}_{n}=\\{x^{\alpha}\theta_{T}\ :\ \text{$T\subseteq[2,n]$ and
$\alpha\leq\alpha(T)$}\\}.$

A different description of this set was independently discovered by a group of
mathematicians associated with the Fields Institute including Nantel Bergeron,
Shu Xiao Li, John Machachek, Robin Sulzgrüber, and Mike Zabrocki [Zab].

######  Conjecture 6.7.

The set ${\cal S}{\cal A}_{n}$ is a basis for $\operatorname{SR}_{n}$.

This conjecture has been verified using Macaulay2 [GS] for $n\leq 6$. While
the classical Artin basis is the standard monomial basis for any monomial
order with $x_{1}>x_{2}>\cdots>x_{n}$ (see [SW21, §5]), calculations by the
Fields Institute group have shown that under reasonable assumptions the same
cannot be true of ${\cal S}{\cal A}_{n}$.

It will be convenient to think of $\alpha(T)$ as an elongated version of the
staircase. For example, the composition in Figure 2 is the staircase
$(0,1,2,3)$ stretched out by adding a column of length $0$, a column of length
$1$, two columns of length $2$, and a column of length $3$. Formally, suppose
$T\subseteq[2,n]$ with $\\#T=n-k$. We then define the associated expansion
composition $\epsilon(T)=(\epsilon_{1}(T),\ldots,\epsilon_{k}(T))$ where

$\epsilon_{j}(T)=\\#\\{i\in T\ :\ \alpha_{i}(T)=j-1\\}.$

Returning to our example, we have $\epsilon(T)=(1,1,2,1)$ corresponding to the
bold line segments in the diagram for $\alpha(T)$. Note that
$|\epsilon(T)|=n-k$.

######  Proposition 6.8.

6.7 implies 6.5.

###### Proof.

Assume that ${\cal S}{\cal A}_{n}$ is a basis for $\operatorname{SR}_{n}$. For
fixed $T\subseteq[2,n]$ with $\\#T=n-k$, the description of the expansion
composition $\epsilon(T)=(\epsilon_{1},\epsilon_{2},\ldots,\epsilon_{k})$
shows that the monomials in ${\cal S}{\cal A}_{n}$ whose theta component is
$\theta_{T}$ contribute

$[1]^{\epsilon_{1}+1}[2]^{\epsilon_{2}+1}\cdots[k]^{\epsilon_{k}+1}=[k]![1]^{\epsilon_{1}}[2]^{\epsilon_{2}}\cdots[k]^{\epsilon_{k}}$

to the $q$-grading in $\operatorname{Hilb}(\operatorname{SR}_{n};q,t)$.
Summing over all such $T$ gives a contribution of

$[k]!h_{n-k}([1],[2],\ldots,[k])=S^{o}[n,k].$

Since $\theta_{T}$ has degree $t^{n-k}$ for these $T$, the proof is complete.
∎

There is also a way to express the elements of ${\cal S}{\cal A}_{n}$ by using
inversions in type $A$ ordered set partitions $\omega=(S_{1}/S_{2}/\ldots)$ of
$[n]$, for which we write $\omega\models[n]$. Given $s\in[n]$ we define

$\operatorname{inv}_{s}\omega=\\#\\{S_{j}\ :\
(s,S_{j})\in\operatorname{Inv}\omega\\}$ (33)

where $\operatorname{Inv}\omega$ is defined by (29). From this we get the
inversion composition

$\eta(\omega)=(\operatorname{inv}_{1}\omega,\operatorname{inv}_{2}\omega,\ldots,\operatorname{inv}_{n}\omega).$
(34)

We also need the set

$T(\omega)=\\{t\in[n]\ :\ \text{$t\in S_{i}$ for some $i$ and $t>m_{i}$}\\}$
(35)

where $m_{i}=\min|S_{i}|$. Note that the absolute value is not needed here
since all elements of $S_{i}$ are positive. Also, it is impossible for $1\in
T(\omega)$. But this description will permit us to use the exactly the same
definition in type $B$ where the absolute value is needed and $1\in T(\omega)$
is possible. For example, if $\omega=(S_{1}/S_{2}/S_{3})=(25/136/4)$ then
$\operatorname{inv}_{2}\omega=1$ because of $S_{2}$,
$\operatorname{inv}_{5}\omega=2$ because of $S_{2}$ and $S_{3}$,
$\operatorname{inv}_{6}\omega=1$ because of $S_{3}$, and
$\operatorname{inv}_{s}\omega=0$ for all other values of $s$, so that
$\eta(\omega)=(0,1,0,0,2,1)$. Furthermore, $T(\omega)=\\{3,5,6\\}$.

######  Proposition 6.9.

We have

${\cal S}{\cal A}_{n}=\\{{\bf x}^{\eta(\omega)}\theta_{T(\omega)}\ :\
\omega\models[n]\\}.$

###### Proof.

It suffices to define a weight-preserving bijection from the pairs
$(T,\alpha)$ appearing in 6.6 to the $\omega\models[n]$. Given $(T,\alpha)$ we
construct $\omega$ inductively as follows. We start with $\omega=(1)$ and
insert the numbers $2,3,\ldots,n$ in order according to the following rules
when it comes to inserting $k$.

  1. 1.

If $k\in T$ then put $k$ in the existing block of $\omega$ so that exactly
$\alpha_{k}$ new inversions result.

  2. 2.

If $k\not\in T$ then make $k$ a new block of $\omega$ so that exactly
$\alpha_{k}$ new inversions result.

It is routine to verify that this is a well defined map and to describe its
inverse, so those details are left to the reader. ∎

######  Example 6.10.

The reader will note how the proof just given mirrors the standard
combinatorial demonstration that

$\sum_{\pi\in{\mathfrak{S}}_{n}}q^{\operatorname{inv}\pi}=[q]!.$

To illustrate the construction in the proof of this result suppose that $n=5$,
$T=\\{3,5\\}$, and $\alpha=(0,1,0,2,1)$. The sequence of ordered partitions
constructed is

$(1),\ (2/1),\ (2/13),\ (4/2/13),\ (4/25/13).$

For example, when $4$ is inserted into $(2/13)$, then, since $4\not\in T$, it
will appear as a singleton block. And since $\alpha_{4}=2$ it must be the
first block to cause two inversions. Similarly, when $5$ is inserted then
$5\in T$ forces this element into one of the existing blocks. And if $5$ is to
cause one new inversion then it must be in the second block from the right.
The $\alpha$-sequence of $T$ is simply the sequence of the maximal number of
inversions one could possibly cause at each step.

Our $\operatorname{inv}$ statistic, or equivalently Steingrímsson’s
$\operatorname{ros}$ [Ste20], effectively numbers the possible insertion
positions “from right to left” starting at $0$. One may get equidistributed
variations on the $\operatorname{inv}$ statistic by changing this numbering
scheme. Using the left-to-right order yields Steingrímsson’s
$\operatorname{los}$ [Ste20], or equivalently (in the unordered case)
Cai–Readdy’s $\operatorname{wgt}$ [CR17] which is Wachs–White’s
$\operatorname{ls}$ up to a $q$-shift [WW91].

###  6.3 Type $B$ super coinvariants

We now consider coinvariant algebras in type $B$.

######  Definition 6.11.

The type $B$ coinvariant algebra is the finite-dimensional, graded,
commutative algebra

$\operatorname{RB}_{n}=\frac{{\mathbb{Q}}[x_{1},\ldots,x_{n}]}{\langle{p_{2k}(n)\
:\ k\in[n]}\rangle}.$

The analogue of the Artin basis in this context is as follows.

######  Definition 6.12.

The type $B$ Artin basis for $\operatorname{RB}_{n}$ is

${\cal B}_{n}=\\{{\bf x}^{\alpha}\ :\ \alpha\leq(1,3,\ldots,2n-1)\\}.$

Figure 3: The double staircase $(1,3,5,7)$

We call the composition $(1,3,\ldots,2n-1)$ the double staircase and it is
displayed in Figure 3 for $n=4$. Again, the Artin basis trivializes the
computation of the Hilbert series.

######  Theorem 6.13.

The coinvariant algebra $\operatorname{RB}_{n}$ has Hilbert series

$\rule{4.30554pt}{0.0pt}\hfill{\displaystyle\operatorname{Hilb}(\operatorname{RB}_{n};q)=[2n]!!.}\hfill\qed$

Swanson and Wallach [SW21] considered the type $B$ super coinvariant algebra
where one adds anticommuting variables $\theta_{1},\ldots,\theta_{n}$ which
again commute with the $x_{j}$’s.

######  Definition 6.14.

The type $B$ super coinvariant algebra is the finite-dimensional, bigraded,
algebra

$\operatorname{SRB}_{n}=\frac{{\mathbb{Q}}[x_{1},\ldots,x_{n}]}{\langle{p_{2k}(n),\
sp_{2k-1}(n)\ :\ k\in[n]}\rangle}.$

As for the super coinvariant algebra in type $A$, the Hilbert series is only
conjectural.

######  Conjecture 6.15 ([SW21]).

We have

$\operatorname{Hilb}(\operatorname{SRB}_{n};q,t)=\sum_{k\geq
0}S_{B}^{o}[n,k]t^{n-k}.$

$\beta(T)=$$\phi(T)=$$(1,$$2,$$1,$$0,$$1)$$T=$$\\{1,$$3,$$4,$$6,$$9\\}$ Figure
4: The compositions $\beta(T)$ and $\phi(T)$ when $n=9$ and
$T=\\{1,3,4,6,9\\}$

We have a set of elements of $\operatorname{SRB}_{n}$ which, if they form a
basis, will verify the previous conjecture. To define the analogue of the
$\alpha$-sequence, it will be convenient to use the notation $\chi({\cal S})$
which is $1$ if the statement ${\cal S}$ is true, or $0$ if it is false. Let
the $\beta$-sequence of $T\subseteq[n]$ to be the composition defined
recursively by $\beta_{1}(T)=\chi(1\not\in T)$ and

$\beta_{i}(T)=\beta_{i-1}(T)+\chi(i\not\in T)+\chi(i-1\not\in T)$

for $i\in[2,n]$. Figure 4 contains an example.

######  Definition 6.16.

The super Artin set for $\operatorname{SRB}_{n}$ is

${\cal S}{\cal A}{\cal B}_{n}=\\{x^{\alpha}\theta_{T}\ :\
\text{$T\subseteq[n]$ and $\alpha\leq\beta(T)$}\\}.$

We conjecture that ${\cal S}{\cal A}{\cal B}$ is, in fact, a basis.

######  Conjecture 6.17.

The set ${\cal S}{\cal A}{\cal B}_{n}$ is a basis for
$\operatorname{SRB}_{n}$.

Similar to type $A$, the composition $\beta(T)$ can be considered as an
expansion of the double staircase. Let $T\subseteq[n]$ with $\\#T=n-k$. The
type $B$ expansion composition is $\phi(T)=(\phi_{0}(T),\ldots,\phi_{k}(T))$
where

$\phi_{j}(T)=\\#\\{i\in T\ :\ \beta_{i}(T)=2j\\}.$

Figure 4 also lists the expansion composition for the given $n$ and $T$. So
$\phi_{j}(T)$ is just the number of columns of $\beta(T)$ of height $2j$. It
is not hard to see that removing all the even height columns from $\beta(T)$
leaves a copy of the double staircase $(1,3,\ldots,2k-1)$ and thus
$|\phi(T)|=n-k$.

######  Proposition 6.18.

6.17 implies 6.15.

###### Proof.

Suppose $T\subseteq[n]$ with $\\#T=n-k$. The discussion of
$\phi(T)=(\phi_{0},\ldots,\phi_{k})$ just given shows that the monomials in
${\cal S}{\cal A}{\cal B}_{n}$ whose theta component is $\theta_{T}$ have a
factor of $[2k]!!$ from the columns corresponding to the double staircase, and
a factor of $[1]^{\phi_{0}}[3]^{\phi_{1}}\cdots[2k+1]^{\phi_{k}}$ from the
column of even length. Summing over all such $T$ gives a contribution of

$[2k]!!h_{n-k}([1],[3],\ldots,[2k+1])=S_{B}^{o}[n,k].$

to the $q$-grading. Now the fact that $\theta_{T}$ has degree $t^{n-k}$ for
these $T$ completes the proof. ∎

For the description of ${\cal S}{\cal A}{\cal B}$ in terms of ordered set
partitions $\omega$ we will use the same notation as in type $A$. This will
cause no confusion because it will be clear from context whether the necessary
functions are being applied to a partition which is type $A$ or type $B$. We
write $\omega\models\langle{n}\rangle$ if $\omega=(S_{0}/S_{1}/S_{2}/\ldots)$
is an ordered set partition of $\langle{n}\rangle$. The definitions (33),
(34), and (35) carry over to type $B$ without change. For example, if we have
$\omega=(0\overline{1}1\mid 4/\overline{4}\mid\overline{2}3/2\overline{3})$
then $\eta(\omega)=(0,0,1,3)$ and $T(\omega)=\\{1,3\\}$.

######  Proposition 6.19.

We have

${\cal S}{\cal A}{\cal B}_{n}=\\{{\bf x}^{\eta(\omega)}\theta_{T(\omega)}\ :\
\omega\models\langle{n}\rangle\\}.$

###### Proof.

As in type $A$, it suffices to define a weight-preserving bijection from the
pairs $(T,\alpha)$ appearing in 6.16 to the $\omega\models\langle{n}\rangle$.
Given $(T,\alpha)$ we construct $\omega$ by starting with $\omega=(0)$ and
inserting the numbers $\pm 1,\pm 2,\ldots,\pm n$ in order according to the
following rules. Note that the position of $k$ forces the position of $-k$ so
that either both are in the zero block or $-k$ is in the block paired to the
one containing $k$.

  1. 1.

If $k\in T$ then put $k$ in the existing block of $\omega$ so that exactly
$\alpha_{k}$ new inversions result. (The forced insertion of $-k$ will not
cause any new inversions in this case.)

  2. 2.

If $k\not\in T$ then make $k$ and $-k$ a new pair of blocks of $\omega$ so
that exactly $\alpha_{k}$ new inversions result.

As before, details that this map is well defined and invertible are
straightforward and so omitted. ∎

######  Example 6.20.

Suppose that $n=3$, $T=\\{2,3\\}$, and $\alpha=(0,1,2)$. We start with
$\omega=(0)$. Since $1\not\in T$, we must add $1$ and $\overline{1}$ as
separate blocks. And $\alpha_{1}=0$ means that no inversions are to be created
so that now

$\omega=(0\mid\overline{1}/1).$

We have $2\in T$ so it must be placed in a block with other elements. And it
must create $\alpha_{2}=1$ new inversion. This forces $2$ into the block with
$\overline{1}$ and also $\overline{2}$ into the block with $1$ resulting in

$\omega=(0\mid\overline{1}2/1\overline{2}).$

Finally, $3\in T$ so $T$ will go into one of the existing blocks. It must
create $\alpha_{3}=2$ inversions and so must reside in the zero block. It
follows that $\overline{3}$ is also in $S_{0}$ and we finally have

$\omega=(0\overline{3}3\mid\overline{1}2/1\overline{2}).$

##  7 Comments and open questions

In this section we collect various comments and open questions raised by the
present work.

###  7.1 Complex reflection groups

If $G$ is any complex reflection group, then one can define Stirling numbers
of the first and second kind for $G$ using the Whitney numbers of the first
and second kind, respectively, for $G$’s intersection lattice analogous to
3.21 in type $B$. It follows from the work of Shephard and Todd [ST54] that
the Stirling numbers of the first kind can be expressed as elementary
symmetric polynomials in the coexponents of $G$. For the Stirling numbers of
the second kind, the situation is more complicated and this approach is
explored in [SS].

###  7.2 Major index for signed permutations and super coinvariant bases

We showed in 3.2 that $S_{B}[n,k]$ can be viewed as the generating function
for both an inversion and a major index statistic on signed partitions. By
contrast, only an inversion generating function was given for $c_{B}[n,k]$ in
3.17. It would be interesting to find a major index analogue for permutations
in type $B$.

In another direction, the Artin basis in type $A$ has a well-known “major
index analogue,” the Garsia–Stanton basis

$\left\\{\prod_{i\in\operatorname{Des}(\pi)}x_{\pi(1)}\cdots x_{\pi(i)}\ :\
\sigma\in S_{n}\right\\}.$

See [GS84]. Adin–Brenti–Roichman [ABR05] gave a type $B$ analogue of the
Garsia–Stanton basis using the flag-major index of Adin–Roichman [AR01]. It
would be interesting to give conjectured super coinvariant extensions of these
bases in types $A$ and $B$.

###  7.3 $q$-difference equations

The generating function

$C=\sum_{n,k\geq 0}c[n,k]t^{k}\frac{x^{n}}{[n]!}$

in 4.4 satisfies the first-order linear $q$-difference equation

$D_{q}C-\frac{tC}{1-x}=0$ (36)

where $C(0,t)=1$. The classical solution of $y^{\prime}+p(x)y=0$ given by
$y=\exp\left(-\int p(x)\,dx\right)$ generalizes to $q$-difference equations
using Gessel’s $q$-composition and $q$-chain rule. In particular, if
$D_{q}Y+P(x)Y=0$, then $Y=\exp\left[\int P(x)\,d_{q}x\right]$, where we have
used the $q$-antiderivative. From (36), $C=\exp[-y\log_{q}(1-x)]$.

Now consider

$C_{B}=\sum_{n,k\geq 0}c_{B}[n,k]t^{k}\frac{x^{n}}{[n]!}.$

Using manipulations similar to those in the proof of 4.4, one may show $C_{B}$
obeys the following second-order linear $q$-difference equation.

######  Lemma 7.1.

We have

$x^{2}q^{2}(1-q)D_{q}^{2}C_{B}+(1-q(1+q)x)D_{q}C_{B}-(1+t)C_{B}=0$ (37)

where $C_{B}(0,t)=1$.

When $q=1$, this becomes a first order differential equation with solution
$(1-2x)^{-(1+t)/2}$, giving an alternate proof of 4.1(d).

We are unaware of techniques which allow us to solve general second-order
linear q-differential equations in terms of well-known operations. However, we
may rewrite (37) as a first order equation using the $q$-pre-composition
operator $Q(F(x))=F(qx)$:

$D_{q}C_{B}-qxD_{q}(1+Q)C_{B}-(1+t)C_{B}=0.$

If we replace $Q$ with $q$ (i.e. post-multiply by $q$ rather than pre-multiply
by $q$), we may solve the resulting $q$-differential equation using the
methods of the previous paragraph, which may be considered as a “first
approximation” of $C_{B}$. More explicitly, we have

$(1-q(1+q)x)D_{q}\widetilde{C}_{B}-(1+t)\widetilde{C}_{B}=0$

where

$\widetilde{C}_{B}=\exp_{q}\left[-\frac{1+t}{q(1+q)}\log_{q}[1-q(1+q)x]\right].$

When $q=1$, we again recover 4.1(d). Since a wide variety of special functions
satisfy second order linear differential equations, solving (37) in a
recognizable way would be interesting.

###  7.4 Sign-reversing involutions

In Section 5.1 we gave combinatorial proofs of the alternating sums involving
$S^{o}[n,k]$ and $S_{B}^{o}[n,k]$ using sign-reversing involutions. We also
showed how these equations were special cases of the symmetric function
function identity in 2.2, where that result was demonstrated by algebraic
manipulation. Can 2.2 itself be proved by sign-reversing involution?

###  7.5 Log concavity

Partially order ${\mathbb{R}}[{\bf x}]$ by letting $f({\bf x})\leq g({\bf x})$
if $g({\bf x})-f({\bf x})\in{\mathbb{R}}^{+}[{\bf x}]$ where
${\mathbb{R}}^{+}$ is the nonnegative reals. A sequence of polynomials
$(f_{k}({\bf x}))_{k\geq 0}=f_{0}({\bf x}),f_{1}({\bf x}),f_{2}({\bf
x}),\ldots$ is said to be ${\bf x}$-log-concave if

$f_{k}({\bf x})^{2}\geq f_{k-1}({\bf x})f_{k+1}({\bf x})$

for all $k>0$. Call the sequence strongly ${\bf x}$-log-concave if

$f_{k}({\bf x})f_{l}({\bf x})\geq f_{k-1}({\bf x})f_{l+1}({\bf x})$

for all $l\geq k>0$. Clearly strong ${\bf x}$-log concavity implies ${\bf
x}$-log concavity. The converse is not true in general, although it is well
known that it does hold if the polynomials are all positive constants. And in
the case of a sequence of constants we say that it is just log-concave.

The following is a corollary of Theorem 2.6 in [Sag92].

######  Theorem 7.2.

If the sequence $x_{1},x_{2},x_{3},\dots$ is strongly ${\bf x}$-log-concave
then so are the following sequences

$(e_{k}(n))_{n\geq 0}\quad\mbox{and}\quad(h_{k}(n))_{n\geq 0}$

where $k$ is fixed, as well as

$(e_{k-j}(n+j))_{j\geq 0}\quad\mbox{and}\quad(e_{k-j}(n+j))_{j\geq 0}$

where both $k$ and $n$ are fixed. ∎

All the definitions in the previous paragraph apply when there is a single
variable $q$. It is easy to see that the sequence
$[1]_{q},[2]_{q},[3]_{q},\ldots$ is strongly $q$-log-concave. So any
subsequence will be as well. Combining this fact, the previous theorem, and
parts (a) and (b) of 2.1 give the following result.

######  Corollary 7.3.

For fixed $n$, the sequences $(S_{B}[n,k])_{k\geq 0}$ and $(c_{B}[n,k])_{k\geq
0}$ are strongly $q$-log-concave. ∎

A condition that is implied by log concavity for positive integer sequences
$a_{0},a_{1},\ldots,a_{n}$ is unimodality which means that there is some index
$m$ such that

$a_{0}\leq a_{1}\leq\ldots\leq a_{m}\geq a_{m+1}\geq\ldots\geq a_{n}.$

So, one may ask if the sequences of coefficients of the polynomials $S[n,k]$,
$S_{B}[n,k]$, $c[n,k]$, or $c_{B}[n,k]$ are unimodal or even log-concave for
each particular choice of $n,k$. Using a brute-force computation for $n,k\leq
50$, we have the following conjecture.

######  Conjecture 7.4.

For each $n,k$, the coefficients of $S[n,k]$ and $c[n,k]$ are log-concave and
positive, hence unimodal.

In type $B$, the coefficients are not necessarily even unimodal. The first
counterexamples are as follows:

$\displaystyle S_{B}[6,4]$
$\displaystyle=15+24q+34q^{2}+38q^{3}+43q^{4}+42q^{5}+43q^{6}+38q^{7}+35q^{8}$
$\displaystyle+26q^{9}+20q^{10}+14q^{11}+10q^{12}+6q^{13}+4q^{14}+2q^{15}+q^{16}$
$\displaystyle c_{B}[7,5]$
$\displaystyle=21+36q+51q^{2}+60q^{3}+70q^{4}+74q^{5}+79q^{6}+78q^{7}+79q^{8}$
$\displaystyle+74q^{9}+71q^{10}+62q^{11}+56q^{12}+44q^{13}+35q^{14}+26q^{15}+20q^{16}$
$\displaystyle+14q^{17}+10q^{18}+6q^{19}+4q^{20}+2q^{21}+q^{22}$

A sequence $a_{0},a_{1},a_{2},\ldots$ is parity-unimodal if
$a_{0},a_{2},a_{4},\ldots$ and $a_{1},a_{3},a_{5},\ldots$ are each unimodal.
See the article of Billey, Konvalinka, and Swanson [BKS20, §9] for additional
instances of this notion. Inspired by this definition, we say that such a
sequence is parity log-concave if $a_{0},a_{2},a_{4},\ldots$ and
$a_{1},a_{3},a_{5},\ldots$ are each log-concave and similarly for parity
unimodal.

######  Conjecture 7.5.

For each $n,k$, the coefficients of $S_{B}[n,k]$ and $c_{B}[n,k]$ are parity
log-concave and positive, hence parity unimodal.

Another common property of a sequence $a_{0},a_{1},a_{2},\ldots,a_{n}$ is that
it is symmetric meaning that $a_{k}=a_{n-k}$ for all $k\in[n]$. From the
examples above, it is clear that the Stirling polynomials do not have
symmetric coefficients, but there is a related condition that they seem to
enjoy. A sequence is bottom heavy if $a_{k}\geq a_{n-k}$ for $k<n/2$. See the
article of McConville, Sagan, and Smyth [MSS21] as well as the references
therein for more about the bottom heavy condition.

######  Conjecture 7.6.

For each $n,k$, the coefficients of $S[n,k]$, $c[n,k]$, $S_{B}[n,k]$, and
$c_{B}[n,k]$ are all bottom heavy.

Both of the previous conjectures have been verified by computer for $n,k\leq
50$. A property which implies both bottom heaviness and unimodality is being
bottom interlacing which means that

$a_{n}\leq a_{0}\leq a_{n-1}\leq a_{1}\leq\ldots\leq a_{\lfloor n/2\rfloor}$

where $\lfloor\cdot\rfloor$ is the floor function. Again, see [MSS21] for more
information about this property. The coefficients of $c[n,k]$, $S[n,k]$,
$c_{B}[n,k]$, and $S_{B}[n,k]$ are not in general bottom interlacing. For
example,

$S[4,3]=3+2q+q^{2}$

does not have this property.

###  7.6 Asymptotics

A sequence of real-valued random variables
$\mathcal{X}_{1},\mathcal{X}_{2},\ldots$ is asymptotically normal if the
sequence of standardized random variables
$\mathcal{X}_{1}^{*},\mathcal{X}_{2}^{*},\ldots$ converges in distribution to
the standard normal distribution $\mathcal{N}(0,1)$. More explicitly, this
means that for all $t\in\mathbb{R}$,

$\lim_{n\to\infty}\mathbb{P}\left[\frac{\mathcal{X}_{n}-\mu_{n}}{\sigma_{n}}\leq
t\right]=\int_{-\infty}^{t}\frac{1}{\sqrt{2\pi}}\exp(-x^{2}/2)\,dx.$

In order for $\mathcal{X}_{i}^{*}$ to be well-defined, we must assume
$\mathcal{X}_{i}$ does not have the degenerate distribution with variance $0$
supported at a single point. This is only a minor inconvenience, since
degenerate distributions are normal with variance $0$ and are “morally” if not
technically asymptotically normal.

We say that a sequence of non-zero polynomials $P_{1}(q),P_{2}(q),\ldots$ with
non-negative real coefficients $P_{n}(q)=\sum_{k\geq 0}a_{n}(k)q^{k}$ is
asymptotically normal if the sequence of random variables defined by
$\mathbb{P}[\mathcal{X}_{n}=k]=a_{n}(k)/P_{n}(1)$ is asymptotically normal.
Informally, plotting the list of coefficients of $P_{n}(q)$ for large $n$ must
give a bell-shaped curve. See e.g. [BKS20, §2.4, §4.1] for further discussion
and an example.

The polynomials $p_{n}(q)=\sum_{k\geq 0}c(n,k)q^{k}$ and $P_{n}(q)=\sum_{k\geq
0}S(n,k)q^{k}$ were shown to be asymptotically normal by Bender [Ben73] and by
Harper [Har67], respectively. It is natural to ask for asymptotic estimates of
the coefficients of $q$-Stirling numbers analogous to these classic results,
which we have been unable to find in the existing literature. We content
ourselves with the following simple case whose proof is an easy application of
Bender’s well-known result involving bivariate generating functions.

######  Theorem 7.7.

Fix $k\in\mathbb{Z}_{\geq 0}$. The coefficients of $S[n,k]$ when $k\geq 2$,
and of $S_{B}[n,k]$ when $k\geq 1$ are asymptotically normal as $n\to\infty$.

###### Proof.

As we saw in Section 2.1, the generating functions are

$\sum_{n\geq 0}S[n,k]x^{n}=\frac{x^{k}}{(1-[1]x)(1-[2]x)\cdots(1-[k]x)}$

and

$\sum_{n\geq
0}S_{B}[n,k]x^{n}=\frac{x^{k}}{(1-[1]x)(1-[3]x)\cdots(1-[2k+1]x)}.$

Each is of the form $g(x,q)/P(x,q)$ where

  1. 1.

$P(x,q)$ is a polynomial in $x$ with coefficients continuous in $q$,

  2. 2.

$P(x,1)$ has a simple root at $r=1/k$ or $r=1/(2k+1)$ with all other roots
having larger absolute value,

  3. 3.

$g(x,q)=x^{k}$ is entire, and

  4. 4.

$g(r,1)\neq 0$.

The distributions are non-degenerate for $n$ large when $k\geq 2$ in type $A$
and when $k\geq 1$ in type $B$. The result follows from [Ben73, Ex. 3.1, p.95]
(which inadvertently neglects the $\sigma\neq 0$ condition). ∎

A direct analogue of 7.7 for the $q$-Stirling numbers of the first kind would
require explicit expressions for $\sum_{n\geq 0}c[n,k]x^{n}/n!$ or
$\sum_{n\geq 0}c_{B}[n,k]x^{n}/n!$, which we do not have. In a complementary
direction, the distributions of the coefficients of $S[n,n-k]$,
$S_{B}[n,n-k]$, $c[n,n-k]$, and $c_{B}[n,n-k]$ for fixed $k$ as $n\to\infty$
appear to be non-normal, e.g. when $k=1$ the limiting standardized disribution
in each case is the triangle with density $(2\sqrt{2}-x)/9$ for $-\sqrt{2}\leq
x\leq 2\sqrt{2}$.

Based on computational data, the coefficients of the $q$-Stirling numbers of
both kinds and in both types all appear to be “generically asymptotically
normal.” The following conjecture is one way to make this intuition precise.

######  Conjecture 7.8.

Suppose $n,k\to\infty$ in such a way that $k/n\to\alpha$ for some
$0<\alpha<1$. Then the coefficients of $S[n,k]$, $S_{B}[n,k]$, $c[n,k]$, and
$c_{B}[n,k]$ are all asymptotically normal.

More strongly, the coefficients of $S[n,k],S_{B}[n,k],c[n,k],c_{B}[n,k]$
appear to tend towards a “limit shape.” See Figure 5 for an example with
$S[n,k]$. Note that the slices for fixed $k$ appear to be parabolic near their
maximum, consistent with asymptotic normality, at least for $k$ not close to
$0$ or $n$. It would be interesting to find the limit shape precisely in each
case. It would also be very interesting to develop tools for proving limit
shapes of the coefficients arising from recursions similar to (2), perhaps by
exploiting their $q$-difference equations.

Figure 5: Plots of $\log([q]^{j}S[n,k])$ as a function of $k$ and $j$ for
$n=25$ and $n=100$

###  7.7 Graded Euler characteristics

By [SW21], the alternating sums

$\left(\sum_{k=0}^{n}(-1)^{n-k}q^{m(n-k)}S^{o}[n,k]\right)-1\qquad\text{and}\qquad\left(\sum_{k=0}^{n}(-1)^{n-k}q^{m(n-k)}S^{o}_{B}[n,k]\right)-1$

are conjecturally graded Euler characteristics of chain complexes obtained by
applying generalized exterior derivatives to super coinvariant algebras in
types $A$ and $B$, respectively. When $m=1$, the complexes in question use
classical exterior differentiation and are an algebraic analogue of the de
Rham complex. One of the main results of [SW21] shows that the complex is
exact in this case, and correspondingly the $m=1$ alternating sums are $0$.

The following specific alternating sum appears to exhibit significant
structure.

######  Conjecture 7.9.

The polynomial

$\left(\sum_{k=0}^{n}(-1)^{n-k}q^{2(n-k)}S^{o}[n,k]\right)-1$ (38)

is palindromic ignoring signs, with the same number of positive and negative
coefficients, and where the lower-degree half of nonzero coefficients are
positive and the rest are negative.

The coefficients of (38) in fact appear to be slight variations on [OEI22,
A050176]. See Table 1 for examples.

$\sum_{k=0}^{n}(-1)^{n-k}q^{2(n-k)}S^{o}[n,k]-1$ |  $(n+1)$st row of A050176
---|---
$-6q^{7}-14q^{6}-14q^{5}+14q^{3}+14q^{2}+6q+1$ | $1,6,14,14,14,14,6,1$
$-7q^{8}-20q^{7}-28q^{6}-14q^{5}+14q^{4}+28q^{3}+20q^{2}+7q+1$ | $1,7,20,28,14,28,20,7,1$
Table 1: The $n=7$ and $n=8$ cases of (38) and the $8$th and $9$th rows of
[OEI22, A050176].

## References

  * [ABR05] Ron M. Adin, Francesco Brenti, and Yuval Roichman.  Descent representations and multivariate statistics.  Trans. Amer. Math. Soc., 357(8):3051–3082, 2005.
  * [AM12] Mahmoud H. Annaby and Zeinab S. Mansour.  $q$-fractional calculus and equations, volume 2056 of Lecture Notes in Mathematics.  Springer, Heidelberg, 2012.  With a foreword by Mourad Ismail.
  * [AR01] Ron M. Adin and Yuval Roichman.  The flag major index and group actions on polynomial rings.  European J. Combin., 22(4):431–446, 2001.
  * [Ben73] Edward A. Bender.  Central and local limit theorems applied to asymptotic enumeration.  J. Combinatorial Theory Ser. A, 15:91–111, 1973.
  * [BG22] Eli Bagno and David Garber.  Signed partitions—a ‘balls into urns’ approach.  Bull. Math. Soc. Sci. Math. Roumanie (N.S.), 65(113)(1):63–71, 2022\.
  * [BGK] Eli Bagno, David Garber, and Takao Komatsu.  A $q,r$-analogue for the stirling numbers of the second kind of type $b$.  Preprint.
  * [BKS20] Sara C. Billey, Matjaž Konvalinka, and Joshua P. Swanson.  Tableau posets and the fake degrees of coinvariant algebras.  Adv. Math., 371:107252, 46, 2020.
  * [BLL98] F. Bergeron, G. Labelle, and P. Leroux.  Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 1998.  Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota.
  * [BS17] Carolina Benedetti and Bruce E. Sagan.  Antipodes and involutions.  J. Combin. Theory Ser. A, 148:275–315, 2017.
  * [Car33] Leonard Carlitz.  On abelian fields.  Trans. Amer. Math. Soc., 35(1):122–136, 1933.
  * [Car48] L. Carlitz.  $q$-Bernoulli numbers and polynomials.  Duke Math. J., 15:987–1000, 1948.
  * [CR17] Yue Cai and Margaret A. Readdy.  $q$-Stirling numbers: a new view.  Adv. in Appl. Math., 86:50–80, 2017.
  * [DL94] Igor Dolgachev and Valery Lunts.  A character formula for the representation of a Weyl group in the cohomology of the associated toric variety.  J. Algebra, 168(3):741–772, 1994.
  * [DLMF] NIST Digital Library of Mathematical Functions.  http://dlmf.nist.gov/, Release 1.1.5 of 2022-03-15.  F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
  * [DM21] M. D’Adderio and A. Mellit.  A proof of the compositional Delta conjecture.  Preprint arXiv:2011.11467, 2021.
  * [Dow73] T. A. Dowling.  A class of geometric lattices based on finite groups.  J. Combinatorial Theory Ser. B, 14:61–86, 1973.
  * [Ehr03] Richard Ehrenborg.  Determinants involving $q$-Stirling numbers.  Adv. in Appl. Math., 31(4):630–642, 2003.
  * [ER96] Richard Ehrenborg and Margaret Readdy.  Juggling and applications to $q$-analogues.  In Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994), volume 157, pages 107–125, 1996.
  * [Gar80] Adriano M. Garsia.  On the “maj” and “inv” $q$-analogues of Eulerian polynomials.  Linear and Multilinear Algebra, 8(1):21–34, 1979/80.
  * [Ges82] Ira M. Gessel.  A $q$-analog of the exponential formula.  Discrete Math., 40(1):69–80, 1982.
  * [Gou61] H. W. Gould.  The $q$-Stirling numbers of first and second kinds.  Duke Math. J., 28:281–289, 1961.
  * [GR86] A. M. Garsia and J. B. Remmel.  $Q$-counting rook configurations and a formula of Frobenius.  J. Combin. Theory Ser. A, 41(2):246–275, 1986.
  * [GS] Daniel R. Grayson and Michael E. Stillman.  Macaulay2, a software system for research in algebraic geometry.  Available at http://www.math.uiuc.edu/Macaulay2/.
  * [GS84] A. M. Garsia and D. Stanton.  Group actions of Stanley-Reisner rings and invariants of permutation groups.  Adv. in Math., 51(2):107–201, 1984.
  * [Har67] L. H. Harper.  Stirling behavior is asymptotically normal.  Ann. Math. Statist., 38:410–414, 1967.
  * [HRS18] James Haglund, Brendon Rhoades, and Mark Shimozono.  Ordered set partitions, generalized coinvariant algebras, and the delta conjecture.  Adv. Math., 329:851–915, 2018.
  * [IKZ06] Masao Ishikawa, Anisse Kasraoui, and Jiang Zeng.  Computing generating functions of ordered partitions with the transfer-matrix method.  In Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Discrete Math. Theor. Comput. Sci. Proc., AG, pages 193–202. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2006.
  * [IKZ08a] Masao Ishikawa, Anisse Kasraoui, and Jiang Zeng.  Euler-Mahonian statistics on ordered partitions and Steingrímsson’s conjecture—a survey.  In Combinatorial representation theory and related topics, RIMS Kôkyûroku Bessatsu, B8, pages 99–113. Res. Inst. Math. Sci. (RIMS), Kyoto, 2008.
  * [IKZ08b] Masao Ishikawa, Anisse Kasraoui, and Jiang Zeng.  Euler-Mahonian statistics on ordered set partitions.  SIAM J. Discrete Math., 22(3):1105–1137, 2008.
  * [Joh96] Warren P. Johnson.  Some applications of the $q$-exponential formula.  In Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994), volume 157, pages 207–225, 1996.
  * [KZ02] Gérald Ksavrelof and Jiang Zeng.  Nouvelles statistiques de partitions pour les $q$-nombres de Stirling de seconde espèce.  Discrete Math., 256(3):743–758, 2002.  LaCIM 2000 Conference on Combinatorics, Computer Science and Applications (Montreal, QC).
  * [KZ09] Anisse Kasraoui and Jiang Zeng.  Euler-Mahonian statistics on ordered set partitions. II.  J. Combin. Theory Ser. A, 116(3):539–563, 2009.
  * [Ler90] Pierre Leroux.  Reduced matrices and $q$-log-concavity properties of $q$-Stirling numbers.  J. Combin. Theory Ser. A, 54(1):64–84, 1990.
  * [Mac15] I. G. Macdonald.  Symmetric functions and Hall polynomials.  Oxford Classic Texts in the Physical Sciences. The Clarendon Press, Oxford University Press, New York, second edition, 2015.  With contribution by A. V. Zelevinsky and a foreword by Richard Stanley, Reprint of the 2008 paperback edition [ MR1354144].
  * [Mil82] Stephen C. Milne.  Restricted growth functions, rank row matchings of partition lattices, and $q$-Stirling numbers.  Adv. in Math., 43(2):173–196, 1982.
  * [MSS21] Thomas McConville, Bruce E. Sagan, and Clifford Smyth.  On a rank-unimodality conjecture of Morier-Genoud and Ovsienko.  Discrete Math., 344(8):Paper No. 112483, 13, 2021.
  * [OEI22] OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences, 2022.  Published electronically at http://oeis.org.
  * [Raw81] Don Rawlings.  The $r$-major index.  J. Combin. Theory Ser. A, 31(2):175–183, 1981.
  * [Rei97] Victor Reiner.  Non-crossing partitions for classical reflection groups.  Discrete Math., 177(1-3):195–222, 1997.
  * [RW15] Jeffrey B. Remmel and Andrew Timothy Wilson.  An extension of MacMahon’s equidistribution theorem to ordered set partitions.  J. Combin. Theory Ser. A, 134:242–277, 2015.
  * [Sag91] Bruce E. Sagan.  A maj statistic for set partitions.  European J. Combin., 12(1):69–79, 1991.
  * [Sag92] Bruce E. Sagan.  Log concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinants.  Trans. Amer. Math. Soc., 329(2):795–811, 1992.
  * [Sag01] Bruce E. Sagan.  The symmetric group, volume 203 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 2001.  Representations, combinatorial algorithms, and symmetric functions.
  * [Sag20] Bruce E. Sagan.  Combinatorics: the art of counting, volume 210 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, [2020] ©2020.
  * [SS] Bruce Sagan and Joshua Swanson.  Stirling numbers for complex reflection groups.  In preparation.
  * [ST54] G. C. Shephard and J. A. Todd.  Finite unitary reflection groups.  Canad. J. Math., 6:274–304, 1954.
  * [Sta97] Richard P. Stanley.  Enumerative Combinatorics. Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1997.  With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original.
  * [Sta99] Richard P. Stanley.  Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1999.  With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
  * [Ste20] Einar Steingrímsson.  Statistics on ordered partitions of sets.  J. Comb., 11(3):557–574, 2020.
  * [Stu08] Bernd Sturmfels.  Algorithms in invariant theory.  Texts and Monographs in Symbolic Computation. SpringerWienNewYork, Vienna, second edition, 2008.
  * [SW21] Joshua P. Swanson and Nolan R. Wallach.  Harmonic differential forms for pseudo-reflection groups ii. bi-degree bounds.  Preprint arXiv:2109.03407, 2021.
  * [Wil16] Andrew Timothy Wilson.  An extension of MacMahon’s equidistribution theorem to ordered multiset partitions.  Electron. J. Combin., 23(1):Paper 1.5, 21, 2016.
  * [WW91] Michelle Wachs and Dennis White.  $p,q$-Stirling numbers and set partition statistics.  J. Combin. Theory Ser. A, 56(1):27–46, 1991.
  * [Zab] Mike Zabrocki.  Personal communication.
  * [Zab19] Mike Zabrocki.  A module for the delta conjecture.  Preprint arXiv:1902.08966, 2019.
  * [Zas81] Thomas Zaslavsky.  The geometry of root systems and signed graphs.  Amer. Math. Monthly, 88(2):88–105, 1981.
  * [ZZ94] Jiang Zeng and Changgui Zhang.  A $q$-analog of Newton’s series, Stirling functions and Eulerian functions.  Results Math., 25(3-4):370–391, 1994.