Cyclic and Linear Graph Partitions and Normal Ordering

Ken Joffaniel Gonzales Department of Physical Sciences and Mathematics University of the Philippines Manila Manila 1000 Philippines

                 kmgonzales1@up.edu.ph

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. 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. We also obtain identities involving their q-analogues.

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} ∑_{k=0}^{n} \begin{cases}w \\ k \end{cases}\} x^{k}D^{k} .

The coefficients \begin{cases}w \\ k \end{cases}\} 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 \begin{cases}w \\ k \end{cases}\}. 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 \begin{cases}w \\ k \end{cases}\}

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′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. If w = xD, then G_{w} is a graph with one vertex.

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

3. If w is reducible, say w = w_{1}w_{2} ⋯ 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.

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 = ∑_{k=0}^{n} S(G_{w}, k)x^{k}D^{k} .

1 2 3 4 5 6 7

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

That is, \begin{cases}w \\ k \end{cases}\} = 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 \begin{cases}w \\ k \end{cases}\} = S(H_{w}, k). To construct H_{w}, we

first draw the Dyck path P(w) starting from the lower left corner of the n × n lattice, where n = |w|/2. The steps on 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 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 P(w). Label the columns of the lattice with 1, 2, …, n from right to left and its rows 1, 2, …, 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.)

Engbers et al. [4] gave two proofs that \begin{cases}w \\ k \end{cases}\} = 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

\begin{matrix}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) \end{matrix}

Figure 2: The Dyck path P(w) (thick lines) and board B(w) (gray cells) associated with w = xxxDxDDxDDxxDD.

1 2 3 4 5 6 7

Figure 3: The graph H_{w} associated with w = xxxDxDDxDDxxDD.

of B with rooks “×” 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.

Definition 4. Given a simple labeled graph G with vertices labeled 1, 2, …, |G|, the board associated with G, denoted by 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, …, |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.

\begin{matrix}1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 7 \\ 7 \\ × \\ × \\ × \\ (7, 5) \\ (6, 5) \\ (7, 3) \\ (6, 3) \\ (5, 3) \\ (4, 3) \\ (2, 1) \end{matrix}

Figure 4: A placement of 3 non-attacking rooks on a board.

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 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 B(H_{w}) = B(w), a property not satisfied by G_{w} in general. Figure 4, minus the rooks, shows B(G_{w}) for w = xxxDxDDxDDxxDD. Observe that flushing the rows of B(G_{w}) in the figure towards the top produces 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. For every i, column i of B(H_{w}) and B(G_{w}) have the same number of cells.

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

3. The boards B(H_{w}) and B(G_{w}) are equivalent.

Proof. We begin by looking at 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 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′D for some non-empty word w′. As before, label the D’s 1, 2, …, |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 B(G_{w}). This is exactly the number of cells of column i of 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 B(H_{w}) = B(w), the cells of B(H_{w}) are flushed to the left. As to B(G_{w}), suppose that for some j < i_{1} < i_{2}, 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 S(G_{w}, k) = S(H_{w}, k) for all 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 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}(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, …, n} into k subsets.)

The same rule gives a bijection between the partitions of the vertex set of H_{w} into k nonempty independent sets and the placements of n − k non-attacking rooks on B(H_{w}). Hence, S(H_{w}, k) = r_{n−k}(B(H_{w})). The result then follows since B(G_{w}) and 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 = V U + V. We write the normally ordered form of a word w with m V ’s and n U’s by

w = V^{m} ∑_{k=0}^{n} [\begin{matrix}w \\ k \end{matrix}] U^{k} .

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

(V U)^{n} = V^{n} ∑_{k=0}^{n} c(n, k)U^{k} .

The coefficients [\begin{matrix}w \\ k \end{matrix}] may therefore be viewed as a kind of generalization of the Stirling

numbers of the first kind.

A q-analogue of the relation UV = V U + V is given by UV = qV U + 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} ∑_{k=0}^{n} [\begin{matrix}w; q \\ k \end{matrix}] 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 ϕ of rooks, the weight of ϕ, denoted by wt(ϕ), 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) = ∑_{ϕ} q^{wt(ϕ)} ,

where the sum runs over all file placements ϕ 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

[\begin{matrix}w \\ k \end{matrix}] = f_{n−k}(B(w))  (1)
[\begin{matrix}w; q \\ k \end{matrix}] = 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 σ, let σ^{(i)} be the partial permutation obtained by keeping only elements j ≤ i in the cycle structure of σ. A k-cyclic partition of a labeled graph G is a permutation σ of V (G) into k cycles such that for every vertex i, σ^{(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 the number of k-cyclic partitions of G is equal to the number of permutations of {1, 2, …, n} into k disjoint cycles. Hence, c(G, k) = c(n, k) and we can think of c(G, k) as a kind of generalization of c(n, k).

In order to state our interpretation for [\begin{matrix}w \\ k \end{matrix}], 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_{w}^{d} 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_{w}^{d} is defined similarly. The directed versions of the graphs in Figures 3 and 1 are shown in Figure 5.

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

1 2 3 4 5 6 7

1 2 3 4 5 6 7

Figure 5: The labeled directed graphs H_{w}^{d} (top) and G_{w}^{d} (bottom) associated with w = xxxDxDDxDDxxDD.

1. If i is a minimal element, place no rook in column i of B(G) .

2. If i is not a minimal element, then place a rook in cell (i, σ^{(i)}(i)).

As illustration, consider the graphs H_{w}^{d} and G_{w}^{d} shown in Figure 5. A 3-cyclic partition of H_{w}^{d} is given by σ = (1534)(26)(7). Columns 1, 2 and 7 of B(H_{w}) do not contain a rook since these are the minimal elements of σ. In addition, σ^{(3)}(3) = 1, σ^{(4)}(4) = 1, σ^{(5)}(5) = 3 and σ^{(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_{w}^{d} is given by σ′ = (1354)(26)(7). The rook placements associated with σ and σ′ 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 = V U + V. Then [\begin{matrix}w \\ k \end{matrix}] =

c(H_{w}^{d}, k) = c(G_{w}^{d}, k).

Proof. First, we show that Φ is bijection between k-cyclic partitions of H_{w}^{d} with |w|/2 = n

and the file placement of n − k rooks on B(H_{w}) = B(w). The result [\begin{matrix}w \\ k \end{matrix}] = c(H_{w}^{d}, k) then

follows from Equation (1).

Let σ be a k-cyclic partition of H_{w}^{d}. Suppose i is not a minimal element of σ and that column i of B(w) has j cells. Then, there is an edge from i to each of i − 1, i − 2, …, j + 1 and σ^{(i)}(i) cannot be equal to any of these by the definition of a cyclic partition. Instead, σ^{(i)}(i) is equal to one of 1, 2 …, j, each of which corresponds to a placement of a rook in one of these j cells, specifically at cell (i, σ^{(i)}(i)), σ^{(i)}(i) = 1, 2, …, j. Moreover, since σ has k minimal elements, Φ(σ) contains k columns without rooks, so that Φ(σ) 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_{w}^{d} and the k-cyclic partitions of G_{w}^{d}. List the rows of B(G_{w}) by t_{1} < t_{2} < ⋯ < t_{m_{1}}, t_{m_{1}+1} < t_{m_{1}+2} < ⋯ < t_{n}, where rows t_{1}, t_{2}, …, t_{m_{1}} have nonzero length and rows t_{m_{1}+1}, t_{m_{1}+2}, …, t_{n} have zero length. Let σ be a k-cyclic partition of H_{w}^{d} and σ′ be the cyclic partition having the same minimal elements as σ and satisfying σ^{′(i)}(i) = t_{σ^{(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 σ and σ′ are identical up to a reordering of the rows. More precisely, for every j, the configuration of row j of B(H_{w}) is the same as the configuration of row t_{j} of B(G_{w}). Thus, σ′ is a k-cyclic partition of G_{w}^{d} and is the image of σ under the desired bijection. For example, the listing of the rows of the board B(G_{w}) shown in Figure 4 in the order just described is given by 1 < 2 < 4 < 6, 3 < 5 < 7. If σ = (1534)(26)(7), then σ′ = (1354)(26)(7).

\begin{matrix}1 \\ 1 \\ 2 \\ 2 \\ 3 \\ 3 \\ 4 \\ 4 \\ 5 \\ 5 \\ 6 \\ 6 \\ 7 \\ 7 \\ × \\ × \\ × \\ × \\ Φ(σ) \end{matrix}  ^{1}^{1}^{2}^{2}^{3}^{3}^{4}^{4}^{5}^{5}^{6}^{6}^{7}^{7}× × × ×^{Φ(σ′)}

Figure 6: The file placement of rooks Φ(σ) associated with the cyclic partition σ = (1534)(26)(7) of H_{w}^{d} and the file placement of rooks Φ(σ′) associated with the cyclic partition σ′ = (1354)(26)(7) of G_{w}^{d}, with w = xxxDxDDxDDxxDD.

The next corollary gives a recurrence formula for c(H_{w}^{d}, k).

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

c(H_{w_{m}}^{d}, k) = c(H_{w_{m−1}}^{d}, k − 1) + b_{m}c(H_{w_{m−1}}^{d}, k) .

Proof. By Theorem 8 and Equation (1),

f_{m−k}(B(w)) = c(H_{w_{m}}^{d}, 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_{w_{m−1}}^{d}, 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_{w_{m−1}}^{d}, 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{matrix}w; q \\ k \end{matrix}] involves the definitions that

follow.

Definition 10. Let G be a labeled digraph and let σ be a cyclic partition of G.

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

2. The weight of i is defined as

wt_{σ}^{G}(i) = \begin{cases}i − 1 − deg^{+}(i), & if i is a minimal element; \\ i − 1 − deg^{+}(i) − σ^{(i)}(i), & otherwise . \end{cases}

3. The weight of σ is given by

wt^{G}(σ) = ∑_{i∈V (G)} wt_{σ}^{G}(i) .

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

c(G, k; q) = ∑_{σ} q^{wt^{G}(σ)} .

where the sum runs over all k-cyclic partitions σ of G.

Theorem 11. Let w be a Dyck word in \{V, U\} subject to UV = qV U + V. Then [\begin{matrix}w; q \\ k \end{matrix}] =

c(H_{w}^{d}, k; q) = c(G_{w}^{d}, k; q).

Proof. Let σ be a k-cyclic partition of H_{w}^{d}. We first show that for every i, wt_{σ}^{H_{w}^{d}}(i) is equal to the number of cells not lying above a rook in column i of Φ(σ). This establishes that

wt^{H_{w}}(σ) = wt (Φ(σ)) and together with Equation (2), proves that [\begin{matrix}w; q \\ k \end{matrix}] = c(H_{w}^{d}, k; q).

If i is a minimal element of σ, then column i of Φ(σ) does not contain a rook. The length of this row is equal to the number of vertices j < i not adjacent to i. If deg^{+}(i) = d, then the d vertices adjacent to i are i − 1, i − 2, …, i − d. Equivalently, the vertices not adjacent to i are 1, 2, …, i − d − 1, of which there are i − 1 − d = wt_{σ}^{H_{w}^{d}}(i).

Next, if i is not a minimal element of σ, then there is a rook in cell (i, σ^{(i)}(i)) of Φ(σ). As before, let 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−σ^{(i)}(i) = wt_{σ}^{H_{w}^{d}}(i). Thus, wt^{H_{w}^{d}}(σ) = wt(Φ(σ)), as desired.

Now, given a cyclic partition σ of H_{w}^{d} and its associated cyclic partition σ′ of G_{w}^{d} as in the proof of Theorem 8, the rook placements Φ(σ) and Φ(σ′) have the same configuration up to a rearrangement of the rows, and thus, have the same weights, leading to wt^{H_{w}^{d}}(σ) = wt^{G_{w}^{d}}(σ′). This proves that c(H_{w}^{d}, k; q) = c(G_{w}^{d}, k; q).

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

[n]_{q} = 1 + q + q^{2} + ⋯ + q^{n−1} .

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

c(H_{w_{m}}^{d}, k; q) = c(H_{w_{m−1}}^{d}, k − 1; q) + [b_{m}]_{q} c(H_{w_{m−1}}^{d}, 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, …, n} into k nonempty 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) = δ_{n,0}, where δ_{·,·} 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.

As an example, let w = xxxDxDDxDDxxDD. A 3-linear partition of the graph H_{w} shown in Figure 3 is [315][247][6] while a 3-linear partition of the graph G_{w} shown 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 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 X (w) by

X (w) = x^{n} ∑_{k=0}^{n} ⌊\begin{matrix}w \\ k \end{matrix}⌋ 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 X (w) by

X (w) = x^{n} ∑_{k=0}^{n} ⌊\begin{matrix}w; q \\ k \end{matrix}⌋ x^{k}D^{k} .

Now, let ψ be a placement of non-attacking rooks on a board B. The weight of ψ, denoted by wt^{∗}(ψ), 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) = ∑_{ψ} q^{wt^{∗}(ψ)} ,

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

Using [3, Identity 3], we have

⌊\begin{matrix}w \\ k \end{matrix}⌋ = r_{n−k}(B(X (w))) .  (3)
⌊\begin{matrix}w; q \\ k \end{matrix}⌋ = r_{n−k;q}(B(X (w))) .  (4)

Our main result for this section relates ⌊\begin{matrix}w \\ k \end{matrix}⌋ 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 π of G, define Ψ(π) as the placement of non-attacking rooks on B(X (x)) obtained as follows. For i = 1, 2, …, n:

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

2. Let π^{(i)} be the partial linear partition obtained by keeping only elements j ≤ i. A position is allowable if inserting i into π^{(i−1)} in that position does not result into i occurring immediately before or immediately after a vertex adjacent to i. A cell in B(X (x)) is canceled if it lies above in the same column or to the right in the same row of a rook. Otherwise, a cell is uncanceled. If i is not a minimal element and i is in the t-th position, that is, π^{(i)} is obtained by inserting i in the t-th allowable position of π^{(i−1)} from the left, then place a rook in the t-th uncanceled cell from the bottom of column i in B(X (x)).

As an illustration, let w = xxxDxDDxDDxxDD and consider the 3-linear partition of H_{w} given by π = [315][247][6]. To construct Ψ(π), we place no rook in columns 1, 2 and 6 of B(X (x)) since these are the minimal elements of π. The allowable positions of π^{(2)} = [1][2], marked by ∗, are [∗1∗][∗2∗]. Since π^{(3)} = [31][2] is obtained by inserting 3 into the first allowable position of π^{(2)}, we place a rook in the first cell from the bottom of column 3. Next, the allowable positions of π^{(3)} = [31][2] are [31∗][∗2∗]. Note that [∗3 ∗ 1][2] are not allowable positions since there is an edge between vertices 3 and 4 in H_{w}. Since π^{(4)} = [31][24] is obtained by inserting 4 into the third allowable position of π^{(3)}, we place a rook in the third uncanceled cell from the bottom of column 4. Continuing this with the other non-minimal elements, we obtain the rook placement in Figure 7

For a simple graph G with vertices labeled 1, 2, …, |V |, let 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 Ψ 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(X (w)). In other words,

L(H_{w}, k) = r_{n−k}(B(X (w)))
L(G_{w}, k) = r_{n−k}(B(X (w))) .

Proof. We start by proving the first equation by showing that for a k-linear partition π of H_{w}, the number of allowable positions to insert a non-minimal element i in π^{(i−1)} is equal to the number of uncanceled cells in column i of B(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, …, j + 1. If 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 π^{(i−1)} contains r minimal elements. Then, there are (i − 1 + r) − 2d = r − i + 2j + 1 allowable positions to insert i into π^{(i−1)}.

Meanwhile, since column i of B(w) has length j, column i of B(X (w)) has length 2j. If π^{(i−1)} has r minimal elements, the first i − 1 columns of B(X (w)) contain i − 1 − r nonattacking rooks. Therefore, column i of B(X (w)) has 2j − (i − 1 − r) = r − i + 2j + 1 uncanceled cells, as desired.

Lastly, if π is a k-linear partition, then π has k minimal elements, so that Ψ(π) contains n − k rooks. This show that Ψ 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 π^{(i−1)} depends completely on deg_{H_{w}}^{<}(i) = d and the number of minimal elements of π^{(i−1)}. This also holds for G_{w}. We now claim that for every i, deg_{H_{w}}^{<}(i) = deg_{G_{w}}^{<}(i). It follows that given a partial linear partition π_{1}^{(i−1)} of H_{w} and a partial linear partition π_{2}^{(i−1)} of G_{w} having the same minimal elements, the number of allowable positions of inserting i into π_{1}^{(i−1)} equals the number of allowable positions of inserting i into π_{2}^{(i−1)}. Thus, if π_{1} and π_{2} have the same minimal elements and i is in the same position in both π_{1}^{(i)} and π_{2}^{(i)} for every i, then Ψ(π_{1}) = Ψ(π_{2}). For example, if w = xxxDxDDxDDxxDD, the linear partitions π_{1} = [315][247][6] and π_{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 deg_{H_{w}}^{<}(i) is equal to the number of cells of column i of B(H_{w}) and deg_{G_{w}}^{<}(i) is equal to the number of cells of column i of B(G_{w}). By the first statement of Theorem 5, deg_{H_{w}}^{<}(i) = deg_{G_{w}}^{<}(i).

The next theorem states the main result for this section, which is a combinatorial inter-

pretation for the normal order coefficients ⌊\begin{matrix}w \\ k \end{matrix}⌋ of 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, ⌊\begin{matrix}w \\ k \end{matrix}⌋ =

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}, …, b_{n}. Let w_{i} be a subword of w such that the board B(w_{i}) consists of columns 1, 2, …, i of B(w). Then for k ≤ m ≤ n we have

L(H_{w_{m}}^{d}, k) = L(H_{w_{m−1}}^{d}, k − 1) + [2b_{m} − (m − k − 1)] L(H_{w_{m−1}}^{d}, k) .

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ × \\ × \\ × \\ × \end{matrix}

Figure 7: The rook placement associated with both π_{1} = [315][247][6] and π_{2} = [31][254][67] as 3-linear partitions of H_{w} and G_{w}, respectively, with w = xxxDxDDxDDxxDD.

Before stating our combinatorial interpretation for ⌊\begin{matrix}w; q \\ k \end{matrix}⌋, we will need the following definitions. Definition 17. Let π be a linear partition of a simple graph G with vertices labeled 1, 2, …, |G|.

1. The weight of a vertex i is defined by

wt_{π}^{∗G}(i) = \begin{cases}2(i − 1 − deg_{G}^{<}(i)) − |\{j non-minimal, j < i\}|, & i is a minimal element ; \\ t − 1, i is in position t in π^{(i)}, & otherwise . \end{cases}

2. The weight of π is defined by

wt^{∗G}(π) = ∑_{i∈V (G)} wt_{π}^{∗G}(i) .

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

L(G, k; q) = ∑_{π} q^{wt^{∗G}(π)} ,

where the sum runs over all k-linear π partitions of G.

Theorem 18. Let w be a Dyck word in \{x, D\} subject to Dx = qxD + 1. Then ⌊\begin{matrix}w; q \\ k \end{matrix}⌋ =

L(H_{w}, k; q) = L(G_{w}, k; q).

Proof. To prove ⌊\begin{matrix}w; q \\ k \end{matrix}⌋ = r_{n−k;q}(B(X (w))), we show that given a linear partition π of H_{w},

the number of uncanceled cells of column i of Ψ(π) is equal to wt_{π}^{∗H_{w}}(i). If i is a minimal element, then column i of B(X (w)) has 2(i − 1 − deg_{G}^{<}(i)) 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 π^{(i)}, then there is a rook in the t-th uncanceled cell from the bottom of column i. Below such rook are t − 1 uncanceled cells. In

combination with Equation 4, this proves ⌊\begin{matrix}w; q \\ k \end{matrix}⌋ = L(H_{w}, k; q).

Lemma 14 shows that given a k-linear partition π_{1} of H_{w}, there exists a unique k-linear

partition π_{2} of G_{w} such that Ψ(π_{1}) = Ψ(π_{2}). This, together with ⌊\begin{matrix}w; q \\ k \end{matrix}⌋ = 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_{w_{m}}^{d}, 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 ≤ m ≤ n,

L(H_{w_{m}}, k) = L(H_{w_{m−1}}, k − 1) + [2b_{m} − (m − k − 1)]_{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. 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′ = x^{a}wD^{b} (or V^{a}wU^{b}), where a and b are the smallest integers such that w′ is a Dyck word. We then have

[\begin{matrix}w \\ k \end{matrix}] = c(H_{w′}^{d}, k + b)
⌊\begin{matrix}w \\ k \end{matrix}⌋ = L(H_{w′}, k + b) .

The same modification applies to the q-analogues.

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 σ of V (G) into k cycles such that vσ(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. It follows from Theorem 5 that other graphs G for which \begin{cases}w \\ k \end{cases}\} = 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 (2018), 253–268.

[2] F. Butler, M. Can, J. Haglund and J. Remmel, Rook theory notes. Unpublished lecture

notes, available at https://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 Sequences 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 (2019), 29–41.

[7] J. Lindsay, T. Mansour and M. Shattuck, A new combinatorial interpretation of a qanalogue of the Lah numbers, J. Comb. 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.

2010 Mathematics Subject Classification: Primary 05A15. Secondary 05A10, 05A18, 05A19, 05A30.

Keywords: Stirling number, Lah number, rook placement, Weyl algebra, normal ordering.

(Concerned with sequences \underline{A132393} and \underline{A111596}.)

Received June 15 2021; revised version received November 1 2021. Published in Journal of Integer Sequences, December 28 2021.

Return to Journal of Integer Sequences home page.