\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\usepackage{tikz}
\usepackage{mathtools}
\usetikzlibrary{decorations.markings}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Cyclic and Linear Graph Partitions \\
\vskip .1in
and Normal Ordering
}
\vskip 1cm
\large
Ken Joffaniel Gonzales\\
Department of Physical Sciences and Mathematics\\
University of the Philippines Manila\\
Manila 1000 \\
Philippines\\
\href{mailto:kmgonzales1@up.edu.ph}{\tt kmgonzales1@up.edu.ph} \\
\end{center}
\vskip .2in
\begin{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.
\end{abstract}
\section{Introduction}\label{sec:intro}
The \emph{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 \emph{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
\displaystyle \begin{Bmatrix} w \\ k \end{Bmatrix} x^k D^k\,.
\]
The coefficients $\displaystyle \begin{Bmatrix} w \\ k \end{Bmatrix}$ have a well-known interpretation in terms of rook placements~\cite{Nav,Var}. More recently, Engbers et al.~\cite{Engetal} 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 \begin{Bmatrix} w \\ k \end{Bmatrix}$. 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.~\cite{Engetal} 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~\ref{sec:revisit}, we recall the constructions and main results of~\cite{Engetal}. We then introduce rook placements associated with graphs in Section~\ref{sec:rook}. The graphical versions of $c(n,k)$ and $L(n,k)$ involve cyclic and linear partitions, and these are discussed in Sections~\ref{sec:cycle} and~\ref{sec:line}, respectively.
\section{Graphical Stirling numbers of the second kind} \label{sec:revisit}
We begin by recalling some terminology and results from~\cite{Engetal} relating the coefficients $\displaystyle \begin{Bmatrix} w \\ k \end{Bmatrix}$ and vertex partitions of some graphs constructed from $w$.
\begin{definition}
A word $w$ is a \emph{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 \emph{irreducible} if either $w=xD$ or $w=xw'D$ for some non-empty Dyck word. Otherwise, the Dyck word is \emph{reducible}.
\end{definition}
Given a Dyck word $w$, we associate an unlabeled simple graph $G_w$ constructed as follows.
\begin{enumerate}
\item If $w=x D$, then $G_w$ is a graph with one vertex.
\item 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'}$.
\item If $w$ is reducible, say $w=w_1w_2\cdots w_m$ where each $w_{i}$ is irreducible, then $G_w$ is the disjoint union of the $G_{w_i}$'s.
\end{enumerate}
Figure~\ref{fig:gw} 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~\ref{sec:rook}.
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8, transform shape]
\begin{scope}[yscale=1,xscale=-1,xshift=-12cm]
\node (n1) at (0,0) [circle,draw=black] {};
\node (n2) at (2,0) [circle,draw=black] {};
\node (n3) at (4,0) [circle,draw=black] {};
\node (n4) at (6,0) [circle,draw=black] {};
\node (n5) at (8,0) [circle,draw=black] {};
\node (n6) at (10,0) [circle,draw=black] {};
\node (n7) at (12,0) [circle,draw=black] {};
\draw (n1) .. controls (1,1.5) and (3,1.5) .. (n3);
\draw (n2) -- (n3);
\draw (n1) .. controls (2,3.5) and (6,3.5) .. (n5);
\draw (n2) .. controls (3.4,2.3) and (6.6,2.3) .. (n5);
\draw (n3) .. controls (5,1.5) and (7,1.5) .. (n5);
\draw (n4) -- (n5);
\draw (n6) -- (n7);
\end{scope}
\node at (0,-0.75) {\small 1};
\node at (2,-0.75) {\small 2};
\node at (4,-0.75) {\small 3};
\node at (6,-0.75) {\small 4};
\node at (8,-0.75) {\small 5};
\node at (10,-0.75) {\small 6};
\node at (12,-0.75) {\small 7};
\end{tikzpicture}
\caption{The graph $G_w$ associated with $w=xxxDxDDxDDxxDD$.} \label{fig:gw}
\end{center}
\end{figure}
\begin{definition}
The $k$-th \emph{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.
\end{definition}
Denote the length of a word $w$ by $|w|$. Using the representation of the Weyl algebra in terms of differential operators, Engbers et al.~\cite{Engetal} 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 \begin{Bmatrix} w \\ k \end{Bmatrix}= 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~\cite[Corollary 2.5]{Engetal}. 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 \emph{Stirling number of the second kind of $G$} from here onwards.
In addition, there is another graph $H_w$ for which $\displaystyle \begin{Bmatrix} w \\ k \end{Bmatrix}=S(H_w,k)$. To construct $H_w$, we first draw the \emph{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~\ref{fig:bw} shows the Dyck path and board with $w=xxxDxDDxDDxxDD$ while Figure~\ref{fig:hw} shows the corresponding graph $H_w$. (Note that we will be using this $w$ in all the examples in the succeeding sections.)
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8, transform shape]
\filldraw[color=gray!50, fill=gray!50] (0,3) rectangle (1,7);
\filldraw[color=gray!50, fill=gray!50] (1,4) rectangle (3,7);
\filldraw[color=gray!50, fill=gray!50] (3,5) rectangle (5,7);
\foreach \i in {0,...,7}{
\draw (0,\i) -- (7,\i);
\draw (\i,0) -- (\i,7);
}
\draw[ultra thick] (0.025,0) -- (0.025,3) -- (1,3) -- (1,4) -- (3,4) -- (3,5) -- (5,5) -- (5,6) -- (5,6.975) -- (7,6.975);
\draw[dotted] (0,0) -- (7,7);
\foreach \i in {1,...,7}{
\node at (-0.3,7.5-\i) {\scriptsize $\i$};
\node at (7.5-\i,7.3) {\scriptsize $\i$};
}
\draw[dashed] (0,0) -- (7,7);
\node at (0.5,1.5) {\scriptsize $(7,6)$};
\node at (0.5,2.5) {\scriptsize $(7,5)$};
\node at (1.5,2.5) {\scriptsize $(6,5)$};
\node at (1.5,3.5) {\scriptsize $(6,4)$};
\node at (2.5,3.5) {\scriptsize $(5,4)$};
\node at (3.5,4.5) {\scriptsize $(4,3)$};
\node at (5.5,6.5) {\scriptsize $(2,1)$};
\end{tikzpicture}
\caption{The Dyck path $\mathcal P(w)$ (thick lines) and board $B(w)$ (gray cells) associated with {$w=xxxDxDDxDDxxDD$.}} \label{fig:bw}
\end{center}
\end{figure}
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8, transform shape]
\begin{scope}[yscale=1,xscale=-1,xshift=-12cm]
\node (n1) at (0,0) [circle,draw=black] {};
\node (n2) at (2,0) [circle,draw=black] {};
\node (n3) at (4,0) [circle,draw=black] {};
\node (n4) at (6,0) [circle,draw=black] {};
\node (n5) at (8,0) [circle,draw=black] {};
\node (n6) at (10,0) [circle,draw=black] {};
\node (n7) at (12,0) [circle,draw=black] {};
\draw (n1) -- (n2);
\draw (n2) -- (n3);
\draw (n3) -- (n4);
\draw (n4) -- (n5);
\draw (n6) -- (n7);
\draw (n1) .. controls (1,1.5) and (3,1.5) .. (n3);
\draw (n2) .. controls (3,1.5) and (5,1.5) .. (n4);
\end{scope}
\node at (0,-0.75) {\small 1};
\node at (2,-0.75) {\small 2};
\node at (4,-0.75) {\small 3};
\node at (6,-0.75) {\small 4};
\node at (8,-0.75) {\small 5};
\node at (10,-0.75) {\small 6};
\node at (12,-0.75) {\small 7};
\end{tikzpicture}
\caption{The graph $H_w$ associated with $w=xxxDxDDxDDxxDD$.} \label{fig:hw}
\end{center}
\end{figure}
Engbers et al.~\cite{Engetal} gave two proofs that $\displaystyle \begin{Bmatrix} w \\ k \end{Bmatrix}=S(H_w,k)$. The first proof uses results involving rook placements by Navon~\cite{Nav}, Varvak~\cite{Var} and Goldman et al.~\cite{Goletal}. The second proof is direct and proceeds by showing that $G_w$ and $H_w$ have the same chromatic polynomials.
\section{Boards associated with graphs} \label{sec:rook}
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.
\begin{definition} A \emph{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 \emph{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 \emph{rook equivalent} (or simply, \emph{equivalent}) if $r_k(B_1)=r_k(B_2)$ for every $k$.
\end{definition}
Figure~\ref{fig:rookboard} shows a placement of $3$ non-attacking rooks.
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8]
\filldraw[color=gray!50, fill=gray!50] (0,1) rectangle (1,2);
\filldraw[color=gray!50, fill=gray!50] (0,3) rectangle (3,4);
\filldraw[color=gray!50, fill=gray!50] (0,5) rectangle (5,7);
\foreach \i in {0,...,7}{
\draw (0,\i) -- (7,\i);
\draw (\i,0) -- (\i,7);
}
\foreach \i in {1,...,7}{
\node at (-0.3,7.5-\i) {\scriptsize $\i$};
\node at (7.5-\i,7.3) {\scriptsize $\i$};
}
\draw[dashed] (0,0) -- (7,7);
\node at (0.5,1.5) {\Large $\times$};
\node at (2.5,6.5) {\Large $\times$};
\node at (3.5,5.5) {\Large $\times$};
\node at (0.5,2.5) {\scriptsize $(7,5)$};
\node at (1.5,2.5) {\scriptsize $(6,5)$};
\node at (0.5,4.5) {\scriptsize $(7,3)$};
\node at (1.5,4.5) {\scriptsize $(6,3)$};
\node at (2.5,4.5) {\scriptsize $(5,3)$};
\node at (3.5,4.5) {\scriptsize $(4,3)$};
\node at (5.5,6.5) {\scriptsize $(2,1)$};
\end{tikzpicture}
\caption{A placement of $3$ non-attacking rooks on a board.} \label{fig:rookboard}
\end{center}
\end{figure}
\begin{definition} Given a simple labeled graph $G$ with vertices labeled $1,2,\ldots,|G|$, the \emph{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$.
\end{definition}
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~\ref{fig:gw} 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 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~\ref{fig:rookboard}, 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.
\begin{theorem} \label{thm:alt} Let $w$ be a Dyck word. Then,
\begin{enumerate}
\item For every $i$, column $i$ of $\mathcal B(H_w)$ and $\mathcal B(G_w)$ have the same number of cells.
\item 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.
\item The boards $\mathcal B(H_w)$ and $\mathcal B(G_w)$ are equivalent.
\end{enumerate}
\begin{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'D$ for some non-empty word $w'$. 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