Cyclic and Linear Graph Partitions
and Normal Ordering
Ken Joffaniel Gonzales
Department of Physical Sciences and Mathematics
University of the Philippines Manila
Manila, Philippines
<EMAIL_ADDRESS>

###### Abstract

The Stirling number of a simple graph is the number of partitions of its
vertex set into a specific number of non-empty independent sets. In 2015,
Engbers et al. showed that the coefficients in the normal ordering of a word
$w$ in the alphabet $\\{x,D\\}$ subject to the relation $Dx=xD+1$ are equal to
the Stirling number of certain graphs constructed from $w$. In this paper, we
introduce graphical versions of the Stirling numbers of the first kind and the
Lah numbers and show how they occur as coefficients in other normal ordering
settings. Identities involving their $q$-analogues are also obtained.

##  1 Introduction

The _Weyl algebra_ is the noncommutative algebra generated by operators $x$
and $D$ satisfying $x(f(x))=xf(x)$ and $D(f(x))=\frac{d}{dx}f(x)$. This
algebra is also defined via the relation $Dx=xD+1$ without reference to any
specific representation of $x$ and $D$ as operators. The _normally ordered
form_ of a word $w$ in the Weyl algebra with $m$ $x$’s and $n$ $D$’s is the
unique expansion given by

$w=x^{m-n}\sum_{k=0}^{n}{w\brace k}x^{k}D^{k}\,.$

The coefficients $\displaystyle{w\brace k}$ have a well-known interpretation
in terms of rook placements [9, 10]. More recently, Engbers et al. [4] derived
another interpretation by showing that for some graph $G$ constructed from
$w$, the number of partitions of $V(G)$ into $k$ non-empty independent sets
are exactly the coefficients $\displaystyle{w\brace k}$. If $w=(xD)^{n}$, the
associated graph is the empty graph with $n$ vertices and the partitions
coincide with the usual interpretation for the Stirling numbers of the second
kind $S(n,k)$.

This paper seeks to extend the results of Engbers et al. [4] by introducing
graphical versions of the Stirling numbers of the first kind $c(n,k)$ and the
Lah numbers $L(n,k)$ that are inspired by their classical interpretations. We
then use these numbers to combinatorially interpret certain normal order
coefficients.

The paper is organized as follows. In Section 2, we recall the constructions
and main results of [4]. We then introduce rook placements associated with
graphs in Section 3. The graphical versions of $c(n,k)$ and $L(n,k)$ involve
cyclic and linear partitions, and these are discussed in Sections 4 and 5,
respectively.

##  2 Graphical Stirling numbers of the second kind

We begin by recalling some terminology and results from [4] relating the
coefficients $\displaystyle{w\brace k}$ and vertex partitions of some graphs
constructed from $w$.

######  Definition 1.

A word $w$ is a _Dyck word_ if the number of $x$’s is equal to the number of
$D$’s and for every $k$, every subword consisting of the first to the $k$-th
letter from the left of $w$ has a least as many $x$’s as $D$’s. A Dyck word is
_irreducible_ if either $w=xD$ or $w=xw^{\prime}D$ for some non-empty Dyck
word. Otherwise, the Dyck word is _reducible_.

Given a Dyck word $w$, we associate an unlabeled simple graph $G_{w}$
constructed as follows.

  1. 1.

If $w=xD$, then $G_{w}$ is a graph with one vertex.

  2. 2.

If $w$ is irreducible and $w=xw^{\prime}D$ for some non-empty Dyck word
$w^{\prime}$, then $G_{w}$ is the graph obtained by adding a single dominating
vertex to $G_{w^{\prime}}$.

  3. 3.

If $w$ is reducible, say $w=w_{1}w_{2}\cdots w_{m}$ where each $w_{i}$ is
irreducible, then $G_{w}$ is the disjoint union of the $G_{w_{i}}$’s.

Figure 1 shows the graph $G_{w}$ where $w=xxxDxDDDxxDD$. While we take $G_{w}$
to be an unlabeled graph, the figure shows a labeling of the vertices that
will be relevant in Section 3.

1234567 Figure 1: The graph $G_{w}$ associated with $w=xxxDxDDxDDxxDD$

######  Definition 2.

The $k$-th _Stirling number_ of a simple graph $G$, denoted by $S(G,k)$ is the
number of ways to partition $V(G)$ into $k$ non-empty independent sets.

Denote the length of a word $w$ by $|w|$. Using the representation of the Weyl
algebra in terms of differential operators, Engbers et al. [4] showed that if
$w$ is a Dyck word with $|w|/2=n$, then

$w=\sum_{k=0}^{n}S(G_{w},k)x^{k}D^{k}\,.$

That is, $\displaystyle{w\brace k}=S(G_{w},k)$. The authors also obtained an
interpretation for the normal order coefficients of arbitrary words by
adjoining appropriate powers of $x$ and $D$ to form a Dyck word [4, Corollary
2.5]. As we shall be eventually defining the first kind version of $S(G,k)$,
we shall call the number $S(G,k)$ as $k$-th _Stirling number of the second
kind of $G$_ from here onwards.

In addition, there is another graph $H_{w}$ for which $\displaystyle{w\brace
k}=S(H_{w},k)$. To construct $H_{w}$, we first draw the _Dyck path_
$\mathcal{P}(w)$ starting from the lower left corner of the $n\times n$
lattice, where $n=|w|/2$. The steps on $\mathcal{P}(w)$ are then obtained by
replacing $x$ with a unit up step and $D$ with a unit right step. Observe that
since $w$ is a Dyck word, its Dyck path $\mathcal{P}(w)$ ends in the upper
right corner and may touch but not cross the northeast diagonal of the
lattice. Next, we associate with $w$ the board $B(w)$ consisting of cells in
the lattice lying above $\mathcal{P}(w)$. Label the columns of the lattice
with $1,2,\ldots,n$ from right to left and its rows $1,2,\ldots,n$ from top to
bottom and denote the cell in column $i$ and row $j$ by $(i,j)$. We construct
an edge from $i$ to $j$ in $H_{w}$ for each $i>j$ if the cell $(i,j)$ lies
outside $B(w)$ and above the northeast diagonal. Figure 2 shows the Dyck path
and board with $w=xxxDxDDxDDxxDD$ while Figure 3 shows the corresponding graph
$H_{w}$. (Note that we will be using this $w$ in all the examples in the
succeeding sections.)

$1$$1$$2$$2$$3$$3$$4$$4$$5$$5$$6$$6$$7$$7$$(7,6)$$(7,5)$$(6,5)$$(6,4)$$(5,4)$$(4,3)$$(2,1)$
Figure 2: The Dyck path $\mathcal{P}(w)$ (thick lines) and board $B(w)$ (gray
cells) associated with $w=xxxDxDDxDDxxDD$. 1234567 Figure 3: The graph $H_{w}$
associated with $w=xxxDxDDxDDxxDD$

Engbers et al. [4] showed two proofs that $\displaystyle{w\brace
k}=S(H_{w},k)$. The first proof uses results involving rook placements by
Navon [9], Varvak [10] and Goldman et al. [5]. The second proof is direct and
proceeds by showing that $G_{w}$ and $H_{w}$ have the same chromatic
polynomials.

##  3 Boards associated with graphs

In this section, we introduce boards associated with graphs which will be used
in the succeeding sections. Additionally, they provide a visualization of why
the number of partitions of $H_{w}$ and $G_{w}$ both produce the normal order
coefficients.

######  Definition 3.

A _placement of non-attacking rooks_ on a board $B$ is a marking of the cells
of $B$ with rooks “$\times$” such that no two rooks lie in the same row or
column. The $k$-th _rook number_ of $B$, denoted by $r_{k}(B)$, is the number
of placements of $k$ non-attacking rooks on $B$. Furthermore, we say that two
boards $B_{1}$ and $B_{2}$ are _rook equivalent_ (or simply, _equivalent_) if
$r_{k}(B_{1})=r_{k}(B_{2})$ for every $k$.

Figure 4 shows a placement of $3$ non-attacking rooks.

$1$$1$$2$$2$$3$$3$$4$$4$$5$$5$$6$$6$$7$$7$$\times$$\times$$\times$$(7,5)$$(6,5)$$(7,3)$$(6,3)$$(5,3)$$(4,3)$$(2,1)$
Figure 4: A placement of $3$ non-attacking rooks on a board.

######  Definition 4.

Given a simple labeled graph $G$ with vertices labeled $1,2,\ldots,|G|$, the
_board associated with $G$_, denoted by $\mathcal{B}(G)$, is the board
consisting of cells $(i,j)$ if vertices $i$ and $j$ are not adjacent in $G$
and $i>j$.

By construction, the vertices of $H_{w}$ are labeled, with the edges added
later as determined by $B(w)$. We take this labeling as the prescribed
labeling for $H_{w}$. For $G_{w}$, we define its prescribed labeling as
follows. Recall that a pair of $x$ and $D$ in $w$ results into either an
additional isolated vertex or an additional dominating vertex so that we can
associate each $D$ in $w$ with its corresponding vertex in $G_{w}$. Label the
$D$’s in $w$ from right to left by $1,2,\ldots,|w|/2$. The label of the
vertices of $G_{w}$ are then the label of the corresponding $D$. Figure 1
shows a graph $G_{w}$ in this prescribed labeling.

For a simple graph $G$, the value of $S(G,k)$ is independent of its labeling.
However, two different labelings of $G$ do not always the result into
equivalent boards. We therefore assume from here onwards that $H_{w}$ and
$G_{w}$ are labeled in the prescribed manner. By construction of $H_{w}$, we
have that $\mathcal{B}(H_{w})=B(w)$, a property not satisfied by $G_{w}$ in
general. Figure 4, minus the rooks, shows $\mathcal{B}(G_{w})$ for
$w=xxxDxDDxDDxxDD$. Observe that flushing the rows of $\mathcal{B}(G_{w})$ in
the figure towards the top produces $\mathcal{B}(H_{w})$ and thus, the two
boards are equivalent. We prove that this is true for any Dyck word $w$ in the
theorem that follows.

######  Theorem 5.

Let $w$ be a Dyck word. Then,

  1. 1.

For every $i$, column $i$ of $\mathcal{B}(H_{w})$ and $\mathcal{B}(G_{w})$
have the same number of cells.

  2. 2.

For every $j$, row $j$ of $\mathcal{B}(H_{w})$ and the $j$-th non-empty row
from the top of $\mathcal{B}(G_{w})$ have the same number of cells.

  3. 3.

The boards $\mathcal{B}(H_{w})$ and $\mathcal{B}(G_{w})$ are equivalent.

###### Proof.

We begin by looking at $\mathcal{B}(H_{w})=B(w)$. The word $w$ determines the
shape of $B(w)$, and hence, the number of cells in each column. Specifically,
the number of cells in column $i$ is equal to the number $x$’s to the right of
the $i$-th $D$ from the right.

Next, we look at $\mathcal{B}(G_{w})$. If $w$ is a Dyck word, then the $x$’s
and $D$’s come in pairs, with each pair resulting into either a non-dominating
vertex if it occurs as $xD$ or a dominating vertex if it occurs as
$xw^{\prime}D$ for some non-empty word $w^{\prime}$. As before, label the
$D$’s $1,2,\ldots,|w|/2$ from right to left and label the $x$’s with the label
of the $D$ it is paired with. Then, for $i<j$, vertex $i$ dominates (and is
therefore adjacent to) vertex $j$ if and only if the $x$ and $D$ labeled $i$
sandwiches the $x$ and $D$ labeled $j$. This implies that if the $D$ labeled
$i$ occurs to the left of the $x$ labeled $j$, then the $x$ and $D$ labeled
$i$ do not sandwich the $x$ and $D$ labeled $j$, so that vertices $i$ and $j$
are non-adjacent. Hence, the number of $x$’s to the right of the $D$ labeled
$i$ counts the number of vertices not adjacent to vertex $i$ and therefore,
the number of cells in column $i$ of $\mathcal{B}(G_{w})$. This is exactly the
number of cells of column $i$ of $\mathcal{B}(H_{w})$, thereby proving the
first statement.

Given two boards $B_{1}$ and $B_{2}$, it is easy to see that if the cells of
both boards are flushed to the left, the second statement follows from the
first statement. Since $\mathcal{B}(H_{w})=B(w)$, the cells of
$\mathcal{B}(H_{w})$ are flushed to the left. As to $\mathcal{B}(G_{w})$,
suppose that for some $j<i_{1}<i_{2}$, $\mathcal{B}(G_{w})$ contains the cell
$(i_{1},j)$ but not the cell $(i_{2},j)$. This means that vertex $j$ dominates
vertex $i_{2}$ but not $i_{1}$. In terms of $w$, this implies that the $D$
labeled $j$ occurs to the left of the $D$ labeled $i_{1}$ and to the right of
the $D$ labeled $i_{2}$, which cannot happen since $j<i_{1}<i_{2}$.

Finally, the third statement follows from the first two. ∎

######  Corollary 6.

Let $w$ be a Dyck word. Then for any $k$, $S(G_{w},k)=S(H_{w},k)$.

###### Proof.

If $w$ is a Dyck word with $|w|/2=n$, then a bijection between the partitions
of the vertex set of $G_{w}$ into $k$ non-empty independent sets and the
placements of $n-k$ non-attacking rooks on $\mathcal{B}(G_{w})$ is as follows.
Two elements $i$ and $j$ belong to the same subset in the partition if and
only if there is a rook in cell $(i,j)$. This shows that
$S(G_{w},k)=r_{n-k}(\mathcal{B}(G_{w}))$. For example, the rook placement
associated with the partition $\\{1,5\\}\\{2,4\\}\\{3\\}\\{6,7\\}$ of the
graph $G_{w}$ in Figure 1 is shown in Figure 4. (This bijection was originally
defined in [2, Section 1.3] to be between the placement of $n-k$ rooks in the
staircase board $B((xD)^{n})$ and the partitions of the set
$\\{1,2,\ldots,n\\}$ into $k$ subsets.)

The same rule gives a bijection between the partitions of the vertex set of
$H_{w}$ into $k$ non-empty independent sets and the placements of $n-k$ non-
attacking rooks on $\mathcal{B}(H_{w})$. Hence,
$S(H_{w},k)=r_{n-k}(\mathcal{B}(H_{w}))$. The result then follows since
$\mathcal{B}(G_{w})$ and $\mathcal{B}(H_{w})$ are equivalent boards by the
third statement in Theorem 5. ∎

##  4 Cyclic partitions

In this section, we consider words in the alphabet $\\{V,U\\}$ subject to the
relation $UV=VU+V$. We write the normally ordered form of a word $w$ with $m$
$V$’s and $n$ $U$’s by

$w=V^{m}\sum_{k=0}^{n}{w\brack k}U^{k}\,.$

Both the relations $UV=VU+V$ and $Dx=xD+1$ are special cases of the relation
$UV=VU+hV^{s}$ studied by Mansour et al. [8], where the authors also showed
that the normally ordered form of $(VU)^{n}$ is given by

$(VU)^{n}=V^{n}\sum_{k=0}^{n}c(n,k)U^{k}\,.$

The coefficients $\begin{bmatrix}w\\\ k\end{bmatrix}$ may therefore be viewed
as a kind of generalization of the Stirling numbers of the first kind.

A $q$-analogue of the relation $UV=VU+V$ is given by $UV=qVU+V$. We write the
normally ordered form of a word $w$ with $m$ $V$’s and $n$ $U$’s under this
relation by

$w=V^{m}\sum_{k=0}^{n}{w;q\brack k}U^{k}\,.$

Given a board $B$, we denote by $f_{k}(B)$ the number of placements of $k$
rooks on $B$ such that no two rooks lie in the same column. We call rook
placements with this restriction _file placements_. For a file placement
$\phi$ of rooks, the _weight_ of $\phi$, denoted by $\mathrm{wt}(\phi)$, is
the number of cells not lying above a rook. The $k$-th $q$-_file number_ of
$B$ is then given by

$f_{n;q}(B)=\sum_{\phi}q^{\mathrm{wt}(\phi)}\,,$

where the sum runs over all file placements $\phi$ of $n$ rooks on $B$.

If a word $w$ has $n$ $U$’s, a result by Celeste et al. [3, Identity 3], in
terms of the notation in this paper, implies that

$\displaystyle{w\brack k}$ $\displaystyle=f_{n-k}(B(w))$ (1)
$\displaystyle{w;q\brack k}$ $\displaystyle=f_{n-k;q}(B(w))\,.$ (2)

We now define our graphical version of the Stirling number of the first kind.

######  Definition 7.

Given a permutation $\sigma$, let $\sigma^{(i)}$ be the partial permutation
obtained by keeping only elements $j\leq i$ in the cycle structure of
$\sigma$. A $k$-_cyclic partition_ of a labeled graph $G$ is a permutation
$\sigma$ of $V(G)$ into $k$ cycles such that for every vertex $i$,
$\sigma^{(i)}(i)=j$ only if there is no directed edge from $i$ to $j$. The
_$k$ -th Stirling number of the first kind of $G$_, denoted by $c(G,k)$, is
number of its $k$-cyclic partitions.

If $G$ is the empty graph with $n$ vertices, then $c(G,k)=c(n,k)$.

In order to state our interpretation for $\begin{bmatrix}w\\\ k\end{bmatrix}$,
we extend the definition of a Dyck word in $\\{V,U\\}$, as well as the graphs
$H_{w}$ and $G_{w}$ by adapting their definitions in terms of $\\{x,D\\}$,
with $V,U$ replacing $x,D$, respectively. For a Dyck word $w$, we denote by
$H^{d}_{w}$ the labeled digraph obtained from $H_{w}$ by replacing every edge
connecting $i$ to $j$, $i<j$, with a directed edge from $j$ to $i$. The graph
$G^{d}_{w}$ is defined similarly. The directed versions of the graphs in
Figures 3 and 1 are shown in Figure 5.

1234567

1234567

Figure 5: The labeled directed graphs $H^{d}_{w}$ (top) and $G^{d}_{w}$
(bottom) associated with $w=xxxDxDDxDDxxDD$.

We also introduce the following map, which is a slight modification of a map
in [2, Section 1.3]. Let $G$ be either $H^{d}_{w}$ or $G^{d}_{w}$ for some
Dyck word $w$ such that $|w|/2=n$. Given a cyclic partition $\sigma$ of $G$,
let $\Phi(\sigma)$ be the file placement of rooks on $\mathcal{B}(G)$ obtained
as follows. For $i=1,2,\ldots,n$:

  1. 1.

If $i$ is a minimal element, place no rook in column $i$ of $\mathcal{B}(G)$ .

  2. 2.

If $i$ is not a minimal element, then place a rook in cell
$(i,\sigma^{(i)}(i))$.

As illustration, consider the graphs $H^{d}_{w}$ and $G^{d}_{w}$ shown in
Figure 5. A $3$-cyclic partition of $H^{d}_{w}$ is given by
$\sigma=(1534)(26)(7)$. Columns $1$, $2$ and $7$ of $\mathcal{B}(H_{w})$ do
not contain a rook since these are the minimal elements of $\sigma$. In
addition, $\sigma^{(3)}(3)=1$, $\sigma^{(4)}(4)=1$, $\sigma^{(5)}(5)=3$ and
$\sigma^{(6)}(6)=2$, so that the associated rook placement has a rook in cells
$(3,1)$, $(4,1)$, $(5,3)$ and $(6,2)$. On the other hand, a $3$-cyclic
partition of $G^{d}_{w}$ is given by $\sigma^{\prime}=(1354)(26)(7)$. The rook
placements associated with $\sigma$ and $\sigma^{\prime}$ are shown in Figure
6.

We can now state our main result for this section.

######  Theorem 8.

Let $w$ be a Dyck word in $\\{V,U\\}$ subject to $UV=VU+V$. Then
$\begin{bmatrix}w\\\ k\end{bmatrix}=c(H^{d}_{w},k)=c(G^{d}_{w},k)$.

###### Proof.

First, we show that $\Phi$ is bijection between $k$-cyclic partitions of
$H^{d}_{w}$ with $|w|/2=n$ and the file placement of $n-k$ rooks on
$\mathcal{B}(H_{w})=B(w)$. The result $\begin{bmatrix}w\\\
k\end{bmatrix}=c(H^{d}_{w},k)$ then follows from Equation (1).

Let $\sigma$ be a $k$-cyclic partition of $H^{d}_{w}$. Suppose $i$ is not a
minimal element of $\sigma$ and that column $i$ of $B(w)$ has $j$ cells. Then,
there is an edge from $i$ to each of $i-1,i-2,\ldots,j+1$ and
$\sigma^{(i)}(i)$ cannot be equal to any of these by the definition of a
cyclic partition. Instead, $\sigma^{(i)}(i)$ is equal to one of $1,2\ldots,j$,
each of which corresponds to a placement of a rook in one of these $j$ cells,
specifically at cell $(i,\sigma^{(i)}(i))$, $\sigma^{(i)}(i)=1,2,\ldots,j$.
Moreover, since $\sigma$ has $k$ minimal elements, $\Phi(\sigma)$ contains $k$
columns without rooks, so that $\Phi(\sigma)$ contains $n-k$ rooks.

Next, we establish $c(H_{w},k)=c(G_{w},k)$ by giving a bijection between the
$k$-cyclic partitions of $H^{d}_{w}$ and the $k$-cyclic partitions of
$G^{d}_{w}$. List the rows of $\mathcal{B}(G_{w})$ by
$t_{1}<t_{2}<\ldots<t_{m_{1}},t_{m_{1}+1}<t_{m_{1}+2}<\ldots<t_{n}$, where
rows $t_{1},t_{2},\ldots,t_{m_{1}}$ have nonzero length and rows
$t_{m_{1}+1},t_{m_{1}+2},\ldots,t_{n}$ have zero length. Let $\sigma$ be a
$k$-cyclic partition of $H^{d}_{w}$ and $\sigma^{\prime}$ be the cyclic
partition having the same minimal elements as $\sigma$ and satisfying
$\sigma^{\prime(i)}(i)=t_{\sigma^{(i)}(i)}$ for every non-minimal element $i$.
This construction combined with the second statement of Theorem 5 shows that
the rook placements associated with $\sigma$ and $\sigma^{\prime}$ are
identical up to a reordering of the rows. More precisely, for every $j$, the
configuration of row $j$ of $\mathcal{B}(H_{w})$ is the same as the
configuration of row $t_{j}$ of $\mathcal{B}(G_{w})$. Thus, $\sigma^{\prime}$
is a $k$-cyclic partition of $G^{d}_{w}$ and priming gives the desired
bijection. For example, the listing of the rows of the board
$\mathcal{B}(G_{w})$ shown in Figure 4 in the order just described is given by
$1<2<4<6,3<5<7$. If $\sigma=(1534)(26)(7)$, then
$\sigma^{\prime}=(1354)(26)(7)$. ∎

$1$$1$$2$$2$$3$$3$$4$$4$$5$$5$$6$$6$$7$$7$$\times$$\times$$\times$$\times$$\Phi(\sigma)$

$1$$1$$2$$2$$3$$3$$4$$4$$5$$5$$6$$6$$7$$7$$\times$$\times$$\times$$\times$$\Phi(\sigma^{\prime})$

Figure 6: The file placement of rooks $\Phi(\sigma)$ associated with the
cyclic partition $\sigma=(1534)(26)(7)$ of $H^{d}_{w}$ and the file placement
of rooks $\Phi(\sigma^{\prime})$ associated with the cyclic partition
$\sigma^{\prime}=(1354)(26)(7)$ of $G^{d}_{w}$, with $w=xxxDxDDxDDxxDD$.

The next theorem gives a recurrence formula for $c(H^{d}_{w},k)$.

######  Corollary 9.

Let $w$ be a Dyck word in $\\{V,U\\}$ such that $n=|w|/2$, subject to
$UV=VU+V$. Suppose that the column lengths of $B(w)$ are
$b_{1},b_{2},\ldots,b_{n}$. Let $w_{i}$ be a subword of $w$ such that the
board $B(w_{i})$ consists of columns $1,2,\ldots,i$ of $B(w)$. Then for $k\leq
m\leq n$,

$c(H^{d}_{w_{m}},k)=c(H^{d}_{w_{m-1}},k-1)+b_{m}c(H^{d}_{w_{m-1}},k)\,.$

###### Proof.

By Theorem 8 and Equation (1),

$f_{m-k}(B(w))=c(H^{d}_{w_{m}},k)\,.$

The number of file placements of $m-k$ rooks on $B(w_{m})$ without a rook in
the $m$-th column is equal to the number of file placements of $m-k$ rooks on
$B(w_{m-1})$, which is given by

$f_{m-k}(B(w_{m-1}))=c(H^{d}_{w_{m-1}},k-1)\,.$

Meanwhile, the number of file placements of $m-k-1$ rooks on $B(w_{m})$
without a rook in the $m$-th column is equal to

$f_{m-k-1}(B(w_{m-1}))=c(H^{d}_{w_{m-1}},k)\,.$

An additional rook in the $m$-th column can then be added in $b_{m}$ ways to
form a file placement of $m-k$ rooks on $B(w_{m})$. ∎

Our interpretation for the $q$-normal order coefficients
$\begin{bmatrix}w;q\\\ k\end{bmatrix}$ involves the definitions that follow.

######  Definition 10.

Let $G$ be a labeled digraph and let $\sigma$ be a cyclic partition of $G$.

  1. 1.

The _outdegree_ of a vertex $i$, denoted by $\mathrm{deg}^{+}(i)$, is the
number of vertices $j$ such that there is a directed edge from $i$ to $j$.

  2. 2.

The _weight_ of $i$ is defined as

$\mathrm{wt}^{G}_{\sigma}(i)=\begin{cases}i-1-\mathrm{deg}^{+}(i),&\mbox{if
$i$ is a minimal element;}\\\
i-1-\mathrm{deg}^{+}(i)-\sigma^{(i)}(i),&\mbox{otherwise}\,.\end{cases}$

  3. 3.

The _weight_ of $\sigma$ is given by

$\mathrm{wt}^{G}(\sigma)=\sum_{i\in V(G)}\mathrm{wt}^{G}_{\sigma}(i)\,.$

  4. 4.

The $q$-analogue of $c(G,k)$ is defined by

$c(G,k;q)=\sum_{\sigma}q^{\mathrm{wt}^{G}(\sigma)}\,.$

where the sum runs over all $k$-cyclic partitions $\sigma$ of $G$.

######  Theorem 11.

Let $w$ be a Dyck word in $\\{V,U\\}$ subject to $UV=qVU+V$. Then
$\begin{bmatrix}w;q\\\ k\end{bmatrix}=c(H^{d}_{w},k;q)=c(G^{d}_{w},k;q)$.

###### Proof.

Let $\sigma$ be a $k$-cyclic partition of $H^{d}_{w}$. We first show that for
every $i$, $\mathrm{wt}^{H^{d}_{w}}_{\sigma}(i)$ is equal to the number of
cells not lying above a rook in column $i$ of $\Phi(\sigma)$. This establishes
that $\mathrm{wt}^{H_{w}}(\sigma)=\mathrm{wt}\left(\Phi(\sigma)\right)$ and
together with Equation (2), proves that $\begin{bmatrix}w;q\\\
k\end{bmatrix}=c(H^{d}_{w},k;q)$.

If $i$ is a minimal element of $\sigma$, then column $i$ of $\Phi(\sigma)$
does not contain a rook. The length of this row is equal to the number of
vertices $j<i$ not adjacent to $i$. If $\mathrm{deg}^{+}(i)=d$, then the $d$
vertices adjacent to $i$ are $i-1,i-2,\ldots,i-d$. Equivalently, the vertices
not adjacent to $i$ are $1,2,\ldots,i-d-1$, of which there are
$i-1-d=\mathrm{wt}^{H^{d}_{w}}_{\sigma}(i)$.

Next, if $i$ is not a minimal element of $\sigma$, then there is a rook in
cell $(i,\sigma^{(i)}(i))$ of $\Phi(\sigma)$. As before, let
$\mathrm{deg}^{+}(i)=d$. Since column $i$ has length $i-1-d$ by the argument
in the previous paragraph, the number of cells below the rook is
$i-1-d-\sigma^{(i)}(i)=\mathrm{wt}^{H^{d}_{w}}_{\sigma}(i)$. Thus,
$\mathrm{wt}^{H^{d}_{w}}(\sigma)=\mathrm{wt}(\Phi(\sigma))$, as desired.

Now, given a cyclic partition $\sigma$ of $H^{d}_{w}$ and its associated
cyclic partition $\sigma^{\prime}$ of $G^{d}_{w}$ as in the proof of Theorem
8, the rook placements $\Phi(\sigma)$ and $\Phi(\sigma^{\prime})$ have the
same configuration up to a rearrangement of the rows, and thus, have the same
weights, leading to
$\mathrm{wt}^{H^{d}_{w}}{(\sigma)}=\mathrm{wt}^{G^{d}_{w}}{(\sigma^{\prime})}$.
This proves that $c(H^{d}_{w},k;q)=c(G^{d}_{w},k;q)$. ∎

The following corollary gives a recurrence relation for $c(H^{d}_{w},k;q)$.
Here, the $q$-analogue of a natural number $n$ is given by

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

######  Corollary 12.

Let $w$ be a Dyck word in $\\{V,U\\}$ such that $|w|/2=n$, subject to
$UV=qVU+V$. With $b_{i}$ and $w_{i}$ defined as in Corollary 9, for $k\leq
m\leq n$,

$c(H^{d}_{w_{m}},k;q)=c(H^{d}_{w_{m-1}},k-1;q)+[b_{m}]_{q}\,c(H^{d}_{w_{m-1}},k;q)\,.$

###### Proof.

The proof is similar to that of Corollary 9. We simply note that the sum of
the weights of all file placements of a rook in a column of length $b_{m}$ is
equal to $[b_{m}]_{q}$. ∎

##  5 Linear partitions

The _Lah numbers_ $L(n,k)$ count the number of partitions of the set
$\\{1,2,\ldots,n\\}$ into $k$ non-empty linearly-ordered subsets or lists. For
example, the partitions of the set $\\{1,2,3\\}$ into two lists are
$[1][2,3]$, $[1][3,2]$, $[2][1,3]$, $[2][3,1]$, $[3][1,2]$ and $[3][2,1]$ and
thus, $L(3,2)=6$.

The Lah numbers satisfy the recurrence relation

$L(m,k)=L(m-1,k-1)+(m+k-1)L(m-1,k)\,,$

with initial conditions $L(m,0)=L(0,m)=\delta_{n,0}$, where
$\delta_{\cdot,\cdot}$ denotes the Kronecker delta. These numbers also satisfy
a simple explicit formula given by

$L(m,k)=\frac{m!}{k!}\binom{m-1}{k-1}\,.$

Goldman et al. [2, page 15] showed that $L(n,k)$ also counts the number of
ways to place $n-k$ non-attacking rooks in a rectangular board with $n$
columns of height $n-1$. Other properties, combinatorial interpretations and
$q$-analogues are discussed in [6, 7].

In analogy with the interpretation of the Lah numbers, we define the following
partition of a graph.

######  Definition 13.

Let $G$ be a simple graph. A _$k$ -linear partition of $G$_ is a partition of
$V(G)$ into $k$ non-empty lists such that two elements $i$ and $j$ occur as
consecutive elements in the same list only if vertices $i$ and $j$ are not
adjacent in $G$. The Lah number of a graph $G$, denoted by $L(G,k)$, is the
number of $k$-linear partitions of $G$.

For example, if $w=xxxDxDDxDDxxDD$, then a $3$-linear partition of the graph
$H_{w}$ in Figure 3 is $[315][247][6]$ and a $3$-linear partition of the graph
$G_{w}$ in Figure 1 is $[31][254][67]$. In addition, if $G$ is the empty graph
with $n$ vertices, that is, $G=G_{w}=H_{w}$ with $w=(xD)^{n}$, then
$L(n,k)=L(G,k)$. We can therefore think of $L(G,k)$ as a kind of
generalization of the Lah numbers.

Let $w$ be a Dyck word in $\\{x,D\\}$ subject to $Dx=xD+1$ and
$\mathcal{X}(w)$ be the word obtained by replacing every $x$ in $w$ with
$x^{2}$. If $|w|/2=n$, we write the normally ordered form of $\mathcal{X}(w)$
by

$\mathcal{X}(w)=x^{n}\sum_{k=0}^{n}\left\lfloor\begin{matrix}w\\\
k\end{matrix}\right\rfloor x^{k}D^{k}\,.$

A $q$-analog of the relation $Dx=xD+1$ is given by $Dx=qxD+1$. Two operators
satisfying this relation are $x(f(x))=xf(x)$ and $D(x^{m})=[m]_{q}x^{m-1}$.
Given a Dyck word $w$ in $\\{x,D\\}$ with $|w|/2=n$, we write the normally
ordered form of the word $\mathcal{X}(w)$ by

$\mathcal{X}(w)=x^{n}\sum_{k=0}^{n}\left\lfloor\begin{matrix}w;q\\\
k\end{matrix}\right\rfloor x^{k}D^{k}\,.$

Now, let $\psi$ be a placement of non-attacking rooks on a board $B$. The
_weight_ of $\psi$, denoted by $\mathrm{wt}^{*}(\psi)$, is the number of cells
not lying above or to the left of a rook. The $k$-th $q$-_rook number_ of $B$
is given by

$r_{k;q}(B)=\sum_{\psi}q^{\mathrm{wt}^{*}(\psi)}\,,$

where the sum runs over all placements $\psi$ of $k$ non-attacking rooks on
$B$.

Using [3, Identity 3], we have

$\displaystyle\left\lfloor\begin{matrix}w\\\ k\end{matrix}\right\rfloor$
$\displaystyle=r_{n-k}(B(\mathcal{X}(w)))\,.$ (3)
$\displaystyle\left\lfloor\begin{matrix}w;q\\\ k\end{matrix}\right\rfloor$
$\displaystyle=r_{n-k;q}(B(\mathcal{X}(w)))\,.$ (4)

Our main result for this section relates $\left\lfloor\begin{matrix}w\\\
k\end{matrix}\right\rfloor$ to the $k$-linear partitions of $H_{w}$ and
$G_{w}$. First, we define the following map. Let $G$ be either $H_{w}$ or
$G_{w}$ for some Dyck word $w$. Given a linear partition $\pi$ of $G$, define
$\Psi(\pi)$ as the placement of non-attacking rooks on $B(\mathcal{X}(x))$
obtained as follows. For $i=1,2,\ldots,n$:

  1. 1.

If $i$ is a minimal element, place no rook in column $i$.

  2. 2.

Let $\pi^{(i)}$ be the partial linear partition obtained by keeping only
elements $j\leq i$. A position is _allowable_ if inserting $i$ into
$\pi^{(i-1)}$ in that position does not result into $i$ occurring immediately
before or immediately after a vertex adjacent to $i$. If $i$ is not a minimal
element and $i$ is in the $t$-th position, that is, $\pi^{(i)}$ is obtained by
inserting $i$ in the $t$-th allowable position of $\pi^{(i-1)}$ from the left,
then place a rook in the $t$-th uncancelled cell from the bottom of column
$i$.

In addition, for a simple graph $G$ with vertices labeled $1,2,\ldots,|V|$,
let $\mathrm{deg}^{<}_{G}(i)$ be the number of vertices $j<i$ adjacent to
vertex $i$.

######  Lemma 14.

Let $w$ be a Dyck word in $\\{x,D\\}$ with $|w|/2=n$. Then, the map $\Psi$ is
a bijection between the $k$-linear partitions of $H_{w}$ (respectively,
$G_{w}$) and the placements of $n-k$ non-attacking rooks on
$B(\mathcal{X}(w))$. In other words,

$\displaystyle L(H_{w},k)$ $\displaystyle=r_{n-k}(B(\mathcal{X}(w)))$
$\displaystyle L(G_{w},k)$ $\displaystyle=r_{n-k}(B(\mathcal{X}(w)))\,.$

###### Proof.

We start by proving the first equation by showing that for a $k$-linear
partition $\pi$ of $H_{w}$, the number of allowable positions to insert a non-
minimal element $i$ in $\pi^{(i-1)}$ is equal to the number of uncancelled
cells in column $i$ of $B(\mathcal{X}(w))$.

Suppose that column $i$ of $B(w)$ has length $j$. Then, there is an edge
between vertex $i$ and each of vertices $t=i-1,i-2,\ldots,j+1$. If
$\mathrm{deg}^{<}_{H_{w}}(i)=d$, then there are $d=i-j-1$ such values of $t$
and $i$ cannot occur immediately before or immediately after each $t$. Suppose
that $\pi^{(i-1)}$ contains $r$ minimal elements. Then, there are
$(i-1+r)-2d=r-i+2j+1$ allowable positions to insert $i$ into $\pi^{(i-1)}$.

Meanwhile, since column $i$ of $B(w)$ has length $j$, column $i$ of
$B(\mathcal{X}(w))$ has length $2j$. If $\pi^{(i-1)}$ has $r$ minimal
elements, the first $i-1$ columns of $B(\mathcal{X}(w))$ contain $i-1-r$ non-
attacking rooks. Therefore, column $i$ of $B(\mathcal{X}(w))$ has
$2j-(i-1-r)=r-i+2j+1$ uncancelled cells, as desired.

Lastly, if $\pi$ is a $k$-linear partition, then $\pi$ has $k$ minimal
elements, so that $\Psi(\pi)$ contains $n-k$ rooks. This show that $\Psi$ is
indeed a bijection, thereby establishing the first equation.

Next, we prove the second equation. Observe by the previous argument that the
number of allowable positions to insert an element $i$ in $\pi^{(i-1)}$
depends completely on $\mathrm{deg}^{<}_{H_{w}}(i)=d$ and the number of
minimal elements of $\pi^{(i-1)}$. This also holds for $G_{w}$. We now claim
that for every $i$, $\mathrm{deg}^{<}_{H_{w}}(i)=\mathrm{deg}^{<}_{G_{w}}(i)$.
It follows that given a partial linear partition $\pi_{1}^{(i-1)}$ of $H_{w}$
and a partial linear partition $\pi_{2}^{(i-1)}$ of $G_{w}$ having the same
minimal elements, the number of allowable positions of inserting $i$ into
$\pi_{1}^{(i-1)}$ equals the number of allowable positions of inserting $i$
into $\pi_{2}^{(i-1)}$. Thus, if $\pi_{1}$ and $\pi_{2}$ have the same minimal
elements and $i$ is in the same position in both $\pi_{1}^{(i)}$ and
$\pi_{2}^{(i)}$ for every $i$, then $\Psi(\pi_{1})=\Psi(\pi_{2})$. For
example, if $w=xxxDxDDxDDxxDD$, the linear partitions $\pi_{1}=[315][247][6]$
and $\pi_{2}=[31][254][67]$ correspond to the same rook placement shown in
Figure 7. The second equation now follows from the first.

Finally, the claim is proved as follows. Observe that
$\mathrm{deg}^{<}_{H_{w}}(i)$ is equal to the number of cells of column $i$ of
$\mathcal{B}(H_{w})$ and $\mathrm{deg}^{<}_{G_{w}}(i)$ is equal to the number
of cells of column $i$ of $\mathcal{B}(G_{w})$. By the first statement of
Theorem 5, $\mathrm{deg}^{<}_{H_{w}}(i)=\mathrm{deg}^{<}_{G_{w}}(i)$. ∎

$1$$2$$3$$4$$5$$6$$7$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$\times$$\times$$\times$$\times$
Figure 7: The rook placement associated with both $\pi_{1}=[315][247][6]$ and
$\pi_{2}=[31][254][67]$ as $3$-linear partitions of $H_{w}$ and $G_{w}$,
respectively, with $w=xxxDxDDxDDxxDD$.

The next theorem states the main result for this section, which is a
combinatorial interpretation for the normal order coefficients
$\left\lfloor\begin{matrix}w\\\ k\end{matrix}\right\rfloor$ of
$\mathcal{X}(w)$ in terms of linear partitions of $H_{w}$ and $G_{w}$.

######  Theorem 15.

Let $w$ be a Dyck word in $\\{x,D\\}$ subject to $Dx=xD+1$. Then,
$\left\lfloor\begin{matrix}w\\\
k\end{matrix}\right\rfloor=L(H_{w},k)=L(G_{w},k)$

###### Proof.

The result follows from Lemma 14 and Equation (3). ∎

The next corollary gives a recurrence relation for $L(H_{w_{n}},k)$. As with
the previous recurrence relations, the proof is similar to that of Corollary
9. Observe that if $w=(xD)^{n}$, then $b_{m}=m-1$ and we recover the
recurrence relation for the classical Lah numbers.

######  Corollary 16.

Let $w$ be a Dyck word in $\\{x,D\\}$ such that $|w|/2=n$, subject to
$Dx=xD+1$. Suppose that the column lengths of $B(w)$ are
$b_{1},b_{2},\ldots,b_{n}$. Let $w_{i}$ be a subword of $w$ such that the
board $B(w_{i})$ consists of columns $1,2,\ldots,i$ of $B(w)$. Then for $k\leq
m\leq n$,

$L(H^{d}_{w_{m}},k)=L(H^{d}_{w_{m-1}},k-1)+\left[2b_{m}-(m-k-1)\right]L(H^{d}_{w_{m-1}},k)\,.$

Before stating our combinatorial interpretation for
$\left\lfloor\begin{matrix}w;q\\\ k\end{matrix}\right\rfloor$, we will need
the following definitions.

######  Definition 17.

Let $\pi$ be a linear partition of a simple graph $G$ with vertices labeled
$1,2,\ldots,|G|$.

  1. 1.

The _weight_ of a vertex $i$ is defined by

$\mathrm{wt}_{\pi}^{*G}(i)=\begin{cases}2\bigl{(}i-1-\mathrm{deg}^{<}_{G}(i)\bigr{)}-|\\{j\mbox{
non-minimal},j<i\\}|,&\mbox{$i$ is a minimal element}\,;\\\ t-1,$\mbox{ $i$ is
in position $t$ in $\pi^{(i)}$}$,&\mbox{otherwise}\,.\end{cases}$

  2. 2.

The _weight_ of $\pi$ is defined by

$\mathrm{wt}^{*G}(\pi)=\sum_{i\in V(G)}\mathrm{wt}_{\pi}^{*G}(i)\,.$

  3. 3.

The $q$-analogue of $L(G,k)$ is given by

$L(G,k;q)=\sum_{\pi}q^{\mathrm{wt}^{*G}(\pi)}\,,$

where the sum runs over all $k$-linear $\pi$ partitions of $G$.

######  Theorem 18.

Let $w$ be a Dyck word in $\\{x,D\\}$ subject to $Dx=qxD+1$. Then
$\left\lfloor\begin{matrix}w;q\\\
k\end{matrix}\right\rfloor=L(H_{w},k;q)=L(G_{w},k;q)$.

###### Proof.

To prove $\left\lfloor\begin{matrix}w;q\\\
k\end{matrix}\right\rfloor=r_{n-k;q}(B(\mathcal{X}(w)))$, we show that given a
linear partition $\pi$ of $H_{w}$, the number of uncancelled cells of column
$i$ of $\Psi(\pi)$ is equal to $\mathrm{wt}^{*H_{w}}_{\pi}(i)$. If $i$ is a
minimal element, then column $i$ of $B(\mathcal{X}(w))$ has
$2\bigl{(}i-1-\mathrm{deg}^{<}_{G}(i)\bigr{)}$ cells. The number of rooks to
the right of this column is equal to the number of non-minimal elements $j<i$.
Meanwhile, if $i$ is not a minimal element that is in position $t$ in
$\pi^{(i)}$, then there is a rook in the $t$-th uncancelled cell from the
bottom of column $i$. Below such rook are $t-1$ uncanceled cells. In
combination with Equation 4, this proves $\left\lfloor\begin{matrix}w;q\\\
k\end{matrix}\right\rfloor=L(H_{w},k;q)$.

Lemma 14 shows that given a $k$-linear partition $\pi_{1}$ of $H_{w}$, there
exists a unique $k$-linear partition $\pi_{2}$ of $G_{w}$ such that
$\Psi(\pi_{1})=\Psi(\pi_{2})$. This, together with
$\left\lfloor\begin{matrix}w;q\\\ k\end{matrix}\right\rfloor=L(H_{w},k;q)$,
establishes $L(H_{w},k;q)=L(G_{w},k;q)$ ∎

The corollary that follows gives a recurrence relation for
$L(H^{d}_{w_{m}},k)$.

######  Corollary 19.

Let $w$ be a Dyck word in $\\{x,D\\}$ such that $|w|/2=n$, subject to
$Dx=qxD+1$. With $b_{i}$ and $w_{i}$ defined as in Corollary 16, for $k\leq
m\leq n$,

$L(H_{w_{m}},k)=L(H_{w_{m-1}},k-1)+\left[2b_{m}-(m-k-1)\right]_{q}L(H_{w_{m-1}},k)\,.$

We note that setting $w=(xD)^{n}$ yields a $q$-analogue of the Lah numbers
with recurrence relation

$L_{q}[n,k]=L_{q}[n-1,k-1]+([n+k-1]_{q})L_{q}[n-1,k]\,.$

This $q$-analogue is slightly different from the one studied by Lindsay et al.
[7] and Gonzales [6], where the $q$-Lah numbers satisfy

$L^{*}_{q}[n,k]=L^{*}_{q}[n-1,k-1]+([n-1]_{q}+[k_{q}])L^{*}_{q}[n-1,k]\,.$

##  6 Some Remarks

  1. 1.

The results in this paper assume that $w$ is a Dyck word. Using the
construction used by Engbers et al. [4, Definition 2.4], we can generalize our
results to arbitrary words. This is done by rewriting $w$ into
$w^{\prime}=x^{a}wD^{b}$ (or $V^{a}wU^{b}$), where $a$ and $b$ are the
smallest integers such that $w^{\prime}$ is a Dyck word. We then have

$\displaystyle\begin{bmatrix}w\\\ k\end{bmatrix}$
$\displaystyle=c(H^{d}_{w^{\prime}},k+b)$
$\displaystyle\left\lfloor\begin{matrix}w\\\ k\end{matrix}\right\rfloor$
$\displaystyle=L(H_{w^{\prime}},k+b)\,.$

The same modification applies to the $q$-analogues.

  2. 2.

A different graphical Stirling number of the first kind $c^{*}(G,k)$ was
studied by Barghi [1], where $c^{*}(G,k)$ counts the number of permutations
$\sigma$ of $V(G)$ into $k$ cycles such that $v\sigma(v)$ is an edge in the
graph obtained by adding a loop at each vertex of $G$. This number seems to be
less restrictive than $c(G,k)$, and it would be interesting to find an
interpretation for $c^{*}(G,k)$ as normal order coefficients.

  3. 3.

It follows from Theorem 5 that other graphs $G$ for which
$\displaystyle{w\brace k}=S(G,k)$ can be constructed by rearranging the rows
of $B(w)$ as long as the cells remain above the northeast diagonal of the
lattice. In addition, the rook equivalence of boards having different column
and row lengths [2, Section 1.6] leads to still other graphs. It would be
interesting to determine the rules for constructing such graphs from a Dyck
word $w$ and derive necessary and sufficient conditions to determine graphs
$G_{1}$ and $G_{2}$ such that $S(G_{1},k)=S(G_{2},k)$. How many isomorphism
classes satisfy $S(G_{1},k)=S(G_{2},k)$ are there given $w$?

## References

  * [1] A. Barghi, Stirling numbers of the first kind for graphs, _Australas. J. Combin._ 70(2) (2018), 253–268.
  * [2] F. Butler, M. Can, J. Haglund and J. Remmel, Rook Theory Notes. Unpublished lecture notes, available at www.math.ucsd.edu/~remmel/files/Book.pdf. Retrieved 13 May 2021.
  * [3] R. Celeste, K. Gonzales and R. Corcino, Two approaches to normal order coefficients, _J. Integer Seq._ 20 (2017), Article 17.3.5.
  * [4] J. Engbers, D. Galvin and J. Hilyard, Combinatorially interpreting generalized Stirling numbers, _Europ. J. Combin._ 43 (2015), 32–54.
  * [5] J. Goldman, J. Joichi and D. White, Rook Theory III. Rook polynomials and the chromatic structure of graphs, _J. Combin. Theory Ser. B_ 25 (1978), 135–142.
  * [6] K. Gonzales, $q$-Lah numbers, Laguerre configurations and rook placements, _Matimyas Matematika_ 42(2) (2019), 29–41.
  * [7] J. Lindsay, T. Mansour and M. Shattuck, A new combinatorial interpretation of a $q$-analogue of the Lah numbers, _J. Comb._ 2(2) (2011), 245–264.
  * [8] T. Mansour, M. Schork and M. Shattuck, On a new family of generalized Stirling and Bell numbers, _Electron. J. Combin._ 18 (2011), #P77.
  * [9] A. Navon, Combinatorics and fermion algebra, _Nuovo Cimento_ 16 (1973), 324–330.
  * [10] A. Varvak, Rook numbers and the normal ordering problem, _J. Combin. Theory Ser. A_ 112 (2005), 292–307.