%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Submission to the Journal of Integer Sequences % % Bell and Stirling Numbers for Graphs % % by Bryce Duncan and Rhodes Peele % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Figures and Table employ the package 'tikz' % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{article} \usepackage{tikz,fullpage,amsmath,amsfonts,amsthm,epsf} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \usepackage[all]{hypcap} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \newtheorem{proposition}{Proposition}[section] \newtheorem{conjecture}{Conjecture}[section] \newtheorem{definition}{Definition}[section] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Title and Authors % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{center}\vskip 1cm {\LARGE \bf Bell and Stirling Numbers for Graphs} \\ \vspace*{+.1in} \end{center} \begin{center} {\large Bryce Duncan \\ Department of Mathematics \\ Auburn University \\ 221 Parker Hall \\ Auburn University, AL 36849 \\ USA \\ \href{mailto:duncabr@auburn.edu}{\tt duncabr@auburn.edu}} \\ \end{center} \begin{center} {\large Rhodes Peele \\ Department of Mathematics \\ Auburn University Montgomery\\ P. O. Box 244023 \\ Montgomery, AL 36124-4023 \\ USA \\ \href{mailto:rpeele@mail.aum.edu}{\tt rpeele@mail.aum.edu}} \\ \end{center} \medskip %%%%%%%%%%%%%%%%%%%%% % Abstract % %%%%%%%%%%%%%%%%%%%%% \begin{abstract} The {\it Bell number} $B(G)$ of a simple graph $G$ is the number of partitions of its vertex set whose blocks are independent sets of $G$. The number of these partitions with $k$ blocks is the (graphical) {\it Stirling number} $S(G,k)$ of $G$. We explore integer sequences of Bell numbers for various one-parameter families of graphs, generalizations of the relation $B(P_n)=B(E_{n-1})$ for path and edgeless graphs, one-parameter graph families whose Bell number sequences are quasigeometric, and relations among the polynomial $A(G,\alpha) = \sum S(G,k)\alpha^k$, the chromatic polynomial and the Tutte polynomial, and some implications of these relations. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Section 1. Introduction % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction.}\label{Sect1} For a simple graph $G = (V,E)$, a partition of the full vertex set of $G$ is called {\it stable} if each of its blocks is an independent set of $G$. The {\it (graphical) Bell number} $B(G)$ of $G$ is the {\it number} of such stable vertex partitions; this invariant for simple graphs generalizes the familiar Bell number sequence $(B_n)$ (sequence \seqnum{A000110} in \cite{OIS}) since $B(E_n) = B_n$ for the {\it edgeless graph} $E_n$ with $n$ vertices. Our aim is to develop the elementary theory of graphical Bell numbers in several different directions, and this we do in Sections~\ref{Sect2} through~\ref{Sect5}. This introduction establishes context, and summarizes what we will need from existing theory. Reference \cite{NB} develops most of the material in this section in fuller detail, and includes proofs. As a running example, and to fix ideas, suppose $G$ is the graph with $V = \{1,2,3,4,5\}$ and $E = \{12,23,34,45,51,25\}$ (shown on the left side of Figure~\ref{Fig1} at the end of this section). Then $B(G) = 8$, the list of stable partitions being: $$13 - 24 - 5 \qquad 14 - 2 - 35 \qquad 1 - 24 - 35$$ $$13 - 2 - 4 - 5 \qquad 14 - 2 - 3 - 5 \qquad 1 - 24 - 3 - 5 \qquad 1 - 2 - 35 - 4 \eqno{(1)}$$ $$1 - 2 - 3 - 4 - 5 $$ The deletion-contraction identity $B(G) = B(G - e) - B(G/e)$ does hold for graphical Bell numbers, but the multiplicative identity $B(G \, \dot \cup \, H) = B(G)\cdot B(H)$ always fails. In its place we have another identity that involves the {\it join} \footnote{In the referenced paragraph, $G$ and $H$ denote graphs with disjoint vertex sets. The operations deletion, contraction, disjoint union, and edge insertion (denoted here by $-$, $/$, $\dot \cup$ and $+$) are defined, for example, in \cite{BB}. The join $G \Join H$ (we have used the bowtie-shaped LaTex symbol $\Join$ - there is no standard notation) of graphs $G$ and $H$ is obtained from their disjoint union $G \, \dot \cup \, H$ by adding a new edge from every vertex of $G$ to every vertex of $H$.} of $G$ and $H$: $B(G \Join H) = B(G)\cdot B(H)$. For this reason it is sometimes useful to make a change in notation, and reformulate the deletion-contraction formula as an {\it insertion-contraction} identity, namely $B(G) = B(G+e) + B(G/e)$. Here, $e$ can be any edge (with endpoints in $V$) that $G$ lacks. As suggested by our running example and the lists (1) above, the stable partitions of $G$ can be enumerated by listing them in groups according to the number of blocks they contain. Accordingly, for any $k$ in the range $c(G) \le k \le |V|$, we define the {\it(graphical) Stirling number} $S(G,k)$ to be the number of stable partitions of $G$ consisting of exactly $k$ blocks. (Here $c(G)$ is the chromatic number of $G$.) For any fixed $k$, $S(G,k) = S(G+e,k) + S(G/e,k)$ holds, but $S(G \Join H,k) = S(G,k)\cdot S(H,k)$ is (usually) false. To recover a multiplicative indentity for these numbers $S(G,k)$, we define the {\it stable partition generating function} $A(G,\alpha) \dot= \sum_{k = c(G)}^{|V|} S(G,k) \alpha^k$. Then (\cite[Cor.\ 9.6, p.\ 60]{NB}) we have the convolution identity $A(G \Join H, \alpha) = A(G,\alpha)\cdot A(H,\alpha)$ . Moreover, the additive identity $A(G,\alpha) = A(G+e,\alpha) + A(G/e,\alpha)$ also holds. These two identities allow one to recursively find the polynomial $A(G,\alpha)$ for a given graph $G$ in much the same way as chromatic polynomials are calculated by hand for small graphs. The main difference is that we prefer to adjoin new edges (rather than delete old ones) in order to produce graphs that are joins of smaller graphs. Once we have found $A(G,\alpha)$, we can find the Bell number $B(G)$ by evaluating $A(G,\alpha)$ at $\alpha = 1$. Figure~\ref{Fig1} provides an example of this procedure. Finally (\cite[Prop.\ 9.2, p.\ 57]{NB}) the stable partition generating function $A(G,\alpha)$ determines the chromatic polynomial $\chi(G,\lambda)$ in the following way: For each term $c_i \alpha^i$ in $A(G,\alpha)$, replace $\alpha^i$ by the falling factorial $\lambda^{(i)} = \lambda (\lambda - 1) (\lambda - 2) \cdots (\lambda - i + 1)$. These substitutions transform $A(G,\alpha)$ into the chromatic polynomial of $G$. For instance, the graph in Figure~\ref{Fig1} has chromatic polynomial $$\chi(G,\lambda) = 3\lambda^{(3)} + 4\lambda^{(4)} + \lambda^{(5)} = 6\lambda - 15\lambda^2 + 14\lambda^3 - 6\lambda^4 + \lambda^5.$$ %%%%%%%%%%%%%%%%%%%%%%% % Figure 1 % %%%%%%%%%%%%%%%%%%%%%%% \begin{figure} \begin{center} \begin{tikzpicture}[scale=0.38] \draw[-, thick] (3,0) -- (4,2); \draw[-, thick] (3,0) -- (4,-2); \draw[-, thick] (4,2) -- (6,2); \draw[-, thick] (4,-2) -- (6,-2); \draw[-, thick] (4,2) -- (4,-2); \draw[-, thick] (6,2) -- (6,-2); \filldraw (3,0) circle (2.1pt) node[anchor=east] {$1$}; \filldraw (4,2) circle (2.1pt) node[anchor=east] {$2$}; \filldraw (6,2) circle (2.1pt) node[anchor=west] {$3$}; \filldraw (4,-2) circle (2.1pt) node[anchor=east] {$5$}; \filldraw (6,-2) circle (2.1pt) node[anchor=west] {$4$}; \draw[-, thick] (3+4,0+7) -- (4+4,2+7); \draw[-, thick] (3+4,0+7) -- (4+4,-2+7); \draw[-, thick] (4+4,2+7) -- (6+4,2+7); \draw[-, thick] (4+4,-2+7) -- (6+4,-2+7); \draw[-, thick] (4+4,2+7) -- (4+4,-2+7); \draw[-, thick] (6+4,2+7) -- (6+4,-2+7); \draw[-, thick] (4+4,-2+7) -- (6+4,2+7); \filldraw (3+4,0+7) circle (2.1pt) node[anchor=east] {$1$}; \filldraw (4+4,2+7) circle (2.1pt) node[anchor=east] {$2$}; \filldraw (6+4,2+7) circle (2.1pt) node[anchor=west] {$3$}; \filldraw (4+4,-2+7) circle (2.1pt) node[anchor=east] {$5$}; \filldraw (6+4,-2+7) circle (2.1pt) node[anchor=west] {$4$}; \draw[-, thick] (3+4,0-7) -- (4+4,2-7); \draw[-, thick] (3+4,0-7) -- (4+4,-2-7); \draw[-, thick] (4+4,-2-7) -- (6+4,-2-7); \draw[-, thick] (4+4,2-7) -- (4+4,-2-7); \filldraw (3+4,0-7) circle (2.1pt) node[anchor=east] {$1$}; \filldraw (4+4,2-7) circle (2.1pt) node[anchor=east] {$2$}; \filldraw (4+4,-2-7) circle (2.1pt) node[anchor=east] {$5$}; \filldraw (6+4,-2-7) circle (2.1pt) node[anchor=west] {$4$}; \draw[->, line width=5pt, red] (5,3) -- (6,5); \draw[->, line width=5pt, red] (5,-3) -- (6,-5); \draw[white] circle (0pt) (5,4) node[anchor=east] {\color{black} insert}; \draw[white] circle (0pt) (5,-4) node[anchor=east] {\color{black} contract}; \filldraw (14,8) circle (2.1pt) node[anchor=west] {$\Join P_4$}; \filldraw (14,8) circle (2.1pt) node[anchor=east] {$= 5$}; \filldraw (12.5,6) circle (0pt) node[anchor=west] {$\rightarrow \alpha(\alpha^2+ 3\alpha^3+\alpha^4)$}; \filldraw (14,-6) circle (2.1pt) node[anchor=east] {$= 5$}; \filldraw (14,-6) node[anchor=west] {$\Join$}; \filldraw (16.6,-5) circle (2.1pt) node[anchor=east] {$1$}; \filldraw (16.6,-7) circle (2.1pt) node[anchor=east] {$2$}; \draw[-, thick] (16.6,-5) -- (16.6,-7); \filldraw (18.2,-6) circle (2.1pt) node[anchor=west] {$4$}; \filldraw (12.5,-8.6) circle (0pt) node[anchor=west] {$\rightarrow \alpha(2\alpha^2+ \alpha^3)$}; \filldraw (12.5,-11) circle (0pt) node[anchor=west] {$A(G,\alpha)=3\alpha^3+4\alpha^4+\alpha^5$}; \draw circle (0pt) (16,0) node[anchor=east] {$\bf{+}$}; \end{tikzpicture} \end{center} \label{Fig1} \caption{Finding the stable partition generating function of a graph.} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Section 2. Bell Numbers for some One-Parameter Families of Graphs. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Bell Numbers for some One-Parameter Families of Graphs.}\label{Sect2} In this section we will comment on the entries in Table~\ref{Tab1}. It is well known that the number of subsets of $\{1,2,\ldots,n\}$ of cardinality $k$ that contain no pair of consecutive integers is $\binom{n-k+1}{k}$. The first entry of Table~\ref{Tab1} is the analog of this fact for set partitions. The earliest reference to it that we know of is \cite{AOM}; it also appears as an exercise in \cite{MA}. We will generalize it in two different ways in the next section. The second entry, giving the value of $B(C_n)$, follows from the first by induction and deletion-contraction. The sequence of alternating sums of Bell numbers occurs in other contexts in combinatorics; see sequence \seqnum{A000296}. The third entry, giving the Bell number of the star graphs $St_n$, although suggestive, is trivial to prove. One just observes that the hub vertex of the star must be a singleton block in any stable partiton of the vertex set, but apart from this one restriction, the vertices may be partitioned in any way whatsoever. The fourth entry, giving the Bell number for graphs that are complements of paths, is a slight variation on a well-known combinatorial exercise (\cite[p.\ 1]{ABJQ} for example) that asks for the number of ways to express a given positive integer integer $n$ as a sum of 1's and 2's if the order of the summands is significant. The answer also turns out to be $F_{n+1}$. For example, for $n = 3$ we have the three sums 1 + 1 + 1, 1 + 2 and 2 + 1. There is an obvious bijection between these sums (vaild for any $n$) and the stable partitons of $\overline{P_n}$ - in the present case, these partitions would be 1 - 2 - 3, 1 - 23 and 12 - 3. %%%%%%%%%%%%%%%%%%%%%%% % Table 1 % %%%%%%%%%%%%%%%%%%%%%%% \begin{table} \begin{center} \begin{tikzpicture}[scale=0.925] \draw (-8,-11) rectangle (7,11); \draw (-8,10) -- (7,10); \draw (-8,6.5) -- (7,6.3); \draw (-8,3) -- (7,3); \draw (-8,-0.5) -- (7,-0.5); \draw (-8,-4) -- (7,-4); \draw (-8,-7.5) -- (7,-7.5); \draw (-3,11) -- (-3,-11); \draw (2,11) -- (2,-11); \draw (-5.5,10.5) node {Example ($|V| = 6$)}; \draw (-0.5,10.5) node {Graph Sequence}; \draw (4.5,10.5) node {Graphical Bell Number}; \filldraw (-5.5 + 0.75,8.25 + 1.30) circle (2.1pt); \filldraw (-5.5 - 0.75,8.25 + 1.30) circle (2.1pt); \filldraw (-5.5 + 0.75,8.25 - 1.30) circle (2.1pt); \filldraw (-5.5 - 0.75,8.25 - 1.30) circle (2.1pt); \filldraw (-5.5 + 1.5,8.25) circle (2.1pt); \filldraw (-5.5 - 1.5,8.25) circle (2.1pt); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30) -- (-5.5 + 1.5,8.25); \draw[-, thick] (-5.5 + 1.5,8.25) -- (-5.5 + 0.75,8.25 - 1.30); \draw[-, thick] (-5.5 + 0.75,8.25 - 1.30) -- (-5.5 - 0.75,8.25 - 1.30); \draw[-, thick] (-5.5 - 0.75,8.25 - 1.30) -- (-5.5 - 1.5,8.25); \draw[-, thick] (-5.5 - 1.5,8.25) -- (-5.5 - 0.75,8.25 + 1.30); \draw (-0.5,8.25) node {Paths $P_n$}; \draw (4.5,8.5) node {$B(P_n) = B_{n-1}$}; \draw (4.5,8) node {(shifted Bell number)}; \filldraw (-5.5 + 0.75,8.25 + 1.30 - 3.5) circle (2.1pt); \filldraw (-5.5 - 0.75,8.25 + 1.30 - 3.5) circle (2.1pt); \filldraw (-5.5 + 0.75,8.25 - 1.30 - 3.5) circle (2.1pt); \filldraw (-5.5 - 0.75,8.25 - 1.30 - 3.5) circle (2.1pt); \filldraw (-5.5 + 1.5,8.25 - 3.5) circle (2.1pt); \filldraw (-5.5 - 1.5,8.25 - 3.5) circle (2.1pt); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30 - 3.5) -- (-5.5 + 1.5,8.25 - 3.5); \draw[-, thick] (-5.5 + 1.5,8.25 - 3.5) -- (-5.5 + 0.75,8.25 - 1.30 - 3.5); \draw[-, thick] (-5.5 + 0.75,8.25 - 1.30 - 3.5) -- (-5.5 - 0.75,8.25 - 1.30 - 3.5); \draw[-, thick] (-5.5 - 0.75,8.25 - 1.30 - 3.5) -- (-5.5 - 1.5,8.25 - 3.5); \draw[-, thick] (-5.5 - 1.5,8.25 - 3.5) -- (-5.5 - 0.75,8.25 + 1.30 - 3.5); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30 - 3.5) -- (-5.5 - 0.75,8.25 + 1.30 - 3.5); \draw (-0.5,8.25 - 3.5) node {Cycles $C_n$}; \draw (4.5,8.25 - 3.5) node {$\displaystyle {B(C_n)\! = \! \sum_{k=0}^{n-2} (-1)^k B_{n-k-1}}$}; \filldraw (-5.5,1.25) circle (2.1pt); \filldraw (-5.5,1.25 + 1.5) circle (2.1pt); \filldraw (-5.5 + 1.43,1.25 + 0.464) circle (2.1pt); \filldraw (-5.5 - 1.43,1.25 + 0.464) circle (2.1pt); \filldraw (-5.5 + 0.882,1.25 - 1.21) circle (2.1pt); \filldraw (-5.5 - 0.882,1.25 - 1.21) circle (2.1pt); \draw[-, thick] (-5.5,1.25) -- (-5.5,1.25 + 1.5); \draw[-, thick] (-5.5,1.25) -- (-5.5 + 1.43,1.25 + 0.464); \draw[-, thick] (-5.5,1.25) -- (-5.5 - 1.43,1.25 + 0.464); \draw[-, thick] (-5.5,1.25) -- (-5.5 + 0.882,1.25 - 1.21); \draw[-, thick] (-5.5,1.25) -- (-5.5 - 0.882,1.25 - 1.21); \draw (-0.5,1.25) node {Stars $St_n$}; \draw (4.5,1.25) node {$B(St_n) = B_{n-1}$}; \filldraw (-5.5 + 0.75,8.25 + 1.30 - 10.5) circle (2.1pt); \filldraw (-5.5 - 0.75,8.25 + 1.30 - 10.5) circle (2.1pt); \filldraw (-5.5 + 0.75,8.25 - 1.30 - 10.5) circle (2.1pt); \filldraw (-5.5 - 0.75,8.25 - 1.30 - 10.5) circle (2.1pt); \filldraw (-5.5 + 1.5,8.25 - 10.5) circle (2.1pt); \filldraw (-5.5 - 1.5,8.25 - 10.5) circle (2.1pt); \draw[-, thick] (-5.5 - 0.75,8.25 + 1.30 - 10.5) -- (-5.5 + 0.75,8.25 + 1.30 - 10.5); \draw[-, thick] (-5.5 - 0.75,8.25 + 1.30 - 10.5) -- (-5.5 + 1.5,8.25 - 10.5); \draw[-, thick] (-5.5 - 0.75,8.25 + 1.30 - 10.5)-- (-5.5 + 0.75,8.25 - 1.30 - 10.5); \draw[-, thick] (-5.5 - 0.75,8.25 + 1.30 - 10.5)-- (-5.5 - 0.75,8.25 - 1.30 - 10.5); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30 - 10.5)-- (-5.5 - 1.5,8.25 - 10.5); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30 - 10.5)-- (-5.5 + 0.75,8.25 - 1.30 - 10.5); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30 - 10.5)-- (-5.5 - 0.75,8.25 - 1.30 - 10.5); \draw[-, thick] (-5.5 - 0.75,8.25 - 1.30 - 10.5) -- (-5.5 + 1.5,8.25 - 10.5); \draw[-, thick] (-5.5 + 0.75,8.25 - 1.30 - 10.5) -- (-5.5 - 1.5,8.25 - 10.5); \draw[-, thick] (-5.5 - 1.5,8.25 - 10.5) -- (-5.5 + 1.5, 8.25 - 10.5); \draw (-0.5,8.25 - 10.5) node {Path Complements $\overline{P_n}$}; \draw (4.5,8.5 - 10.5) node {$B(\overline{P_n}) = F_{n+1}$}; \draw (4.5,8 - 10.5) node {(Fibonacci number)}; \filldraw (-5.5 + 0.75,8.25 + 1.30 - 14) circle (2.1pt); \filldraw (-5.5 - 0.75,8.25 + 1.30 - 14) circle (2.1pt); \filldraw (-5.5 + 0.75,8.25 - 1.30 - 14) circle (2.1pt); \filldraw (-5.5 - 0.75,8.25 - 1.30 - 14) circle (2.1pt); \filldraw (-5.5 + 1.5,8.25 - 14) circle (2.1pt); \filldraw (-5.5 - 1.5,8.25 - 14) circle (2.1pt); \draw[-, thick] (-5.5 - 0.75,8.25 + 1.30 - 14) -- (-5.5 + 1.5,8.25 - 14); \draw[-, thick] (-5.5 - 0.75,8.25 + 1.30 - 14)-- (-5.5 + 0.75,8.25 - 1.30 - 14); \draw[-, thick] (-5.5 - 0.75,8.25 + 1.30 - 14)-- (-5.5 - 0.75,8.25 - 1.30 - 14); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30 - 14)-- (-5.5 - 1.5,8.25 - 14); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30 - 14)-- (-5.5 + 0.75,8.25 - 1.30 - 14); \draw[-, thick] (-5.5 + 0.75,8.25 + 1.30 - 14)-- (-5.5 - 0.75,8.25 - 1.30 - 14); \draw[-, thick] (-5.5 - 0.75,8.25 - 1.30 - 14) -- (-5.5 + 1.5,8.25 - 14); \draw[-, thick] (-5.5 + 0.75,8.25 - 1.30 - 14) -- (-5.5 - 1.5,8.25 - 14); \draw[-, thick] (-5.5 - 1.5,8.25 - 14) -- (-5.5 + 1.5, 8.25 - 14); \draw (-0.5,8.25 - 14) node {Cycle Complements $\overline{C_n}$}; \draw (4.5,8.5 - 14) node {$B(\overline{C_n}) = L_n$ if $n > 3$}; \draw (4.5,8 - 14) node {(Lucas number)}; \filldraw (-5.5,1.25 - 10.5) circle (2.1pt); \filldraw (-5.5,1.25 + 1.5 - 10.5) circle (2.1pt); \filldraw (-5.5 + 1.43,1.25 + 0.464 - 10.5) circle (2.1pt); \filldraw (-5.5 - 1.43,1.25 + 0.464 - 10.5) circle (2.1pt); \filldraw (-5.5 + 0.882,1.25 - 1.21 - 10.5) circle (2.1pt); \filldraw (-5.5 - 0.882,1.25 - 1.21 - 10.5) circle (2.1pt); \draw[-,thick] (-5.5,1.25 + 1.5 - 10.5) -- (-5.5 + 1.43,1.25 + 0.464 - 10.5); \draw[-,thick] (-5.5 + 1.43,1.25 + 0.464 - 10.5) -- (-5.5 - 1.43,1.25 + 0.464 - 10.5); \draw[-,thick] (-5.5 - 1.43,1.25 + 0.464 - 10.5) -- (-5.5 + 0.882,1.25 - 1.21 - 10.5); \draw[-,thick] (-5.5 + 0.882,1.25 - 1.21 - 10.5) -- (-5.5 - 0.882,1.25 - 1.21 - 10.5); \draw[-,thick] (-5.5 - 0.882,1.25 - 1.21 - 10.5) -- (-5.5,1.25 + 1.5 - 10.5); \draw[-,thick] (-5.5,1.25 + 1.5 - 10.5) -- (-5.5 - 1.43,1.25 + 0.464 - 10.5); \draw[-,thick] (-5.5 - 1.43,1.25 + 0.464 - 10.5) -- (-5.5 - 0.882,1.25 - 1.21 - 10.5); \draw[-,thick] (-5.5 - 0.882,1.25 - 1.21 - 10.5) -- (-5.5 + 1.43,1.25 + 0.464 - 10.5); \draw[-,thick] (-5.5 + 1.43,1.25 + 0.464 - 10.5) -- (-5.5 + 0.882,1.25 - 1.21 - 10.5); \draw[-,thick] (-5.5 + 0.882,1.25 - 1.21 - 10.5) -- (-5.5,1.25 + 1.5 - 10.5); \draw (-0.5,1.25 - 10.25) node {Star Complements}; \draw (-0.5,1.25 - 10.75) node {$\overline{St_n} = K_{n-1}\, \dot \cup \, K_1$}; \draw (4.5,1.25 - 10.5) node {$B(\overline{St_n}) = n$}; \end{tikzpicture} \end{center} \caption{Bell Numbers for some One-Parameter Graph Families} \label{Tab1} \end{table} The fifth entry for the Bell number of complements of cycles, is similarly a variation of a well-known combinatorial exercise (see \cite[pp.\ 10--20]{ABJQ} for details). However, the correspondence between the two problems is not perfect in that it breaks down when $n = 2$ and 3. For these anomalous cases, we have $B(\overline{C_2}) = 2$, $B(\overline{C_3}) = 5$ while $L_2 = 3$ and $L_3 = 4$. In connection with the final entry, we recall the famous question posed by Herb Wilf in \cite{HW1}, and still unanswered to this day, namely, ``Which polynomials are chromatic?''. By contrast, we see at once by considering stable partitions of graphs that are star complements, that {\it all} positive integers are graphical Bell numbers. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Section 3. Bell Numbers for Generalizations of Path Graphs. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Bell Numbers for Generalizations of Path Graphs.} This section was inspired by the following striking observation, made (and proved) by A. O. Munagi: \medskip {\it The number of partitions of the set $\{1, 2, ... , n\}$ equals the number of of those partitions of $\{1, 2, ... , n+1\}$, with the property that no block contains a pair of consecutive integers.} \medskip We note that this is equivalent to our entry $B(P_n) = B_{n-1}$ in Table~\ref{Tab1}. Additionally, Munagi showed that the equality refines to one of Stirling Numbers: For $1 \le k \le n$, $S(P_n,k) = S_{n-1,k-1}$. We also noted in Table~\ref{Tab1} that $B(St_n) = B_{n-1}$. What is true for paths and stars ought to be true for trees also: \begin{proposition}Let $T_{n+1}$ be any rooted tree with $n+1$ vertices, and root $r$. Then: (i) There is a natural bijection between the stable partitions of $T_{n+1}$ and all partitions of the set $V - r$; (ii) For $1 \le k \le n$ there is a natural bijection between the stable partitions of $T_{n+1}$ with $k+1$ blocks and all partitions of $V - r$ with $k$ blocks.\end{proposition} \begin{proof} In the following discussion we will let $V = \{1,2, \ldots, n, n+1\}$ and choose root $r = n+1$. The same two bijections that appear in (i) will also serve for (ii) when restricted to the smaller collections of stable partitions with $k+1$ blocks and all partitions with $k$ blocks, as we shall see in a moment. The main problem is to describe the two bijections in (i) clearly, and we will rely on a suitable example for this purpose. Letting $n = 8$, consider the tree shown in Figure~\ref{Fig2}. First, we will describe how to associate with any partition of $\{1, 2, \ldots , 8\}$, a $T_9-$ stable partition of $\{1, 2, \ldots , 9\}$. %%%%%%%%%%%%%%%%%%%%%% % Figure 2 % %%%%%%%%%%%%%%%%%%%%%% \begin{figure} %\capstart \begin{center} \begin{tikzpicture} [scale=1] %\filldraw[white] circle (2.1pt) (0.0,10.5);% \filldraw (4.5 + 5.5,10.5) circle (2.1pt) node[anchor=south] {$6$}; \filldraw (4.5 + 5.5 - 1.2,10.5 + 1.6) circle (2.1pt) node[anchor=west] {$8$}; \filldraw (4.5 + 5.5,10.5 + 3.2) circle (2.1pt) node[anchor=south] {${\bf 9} = {\rm root}$}; \filldraw (4.5 + 5.5 + 2.0,10.5 + 3.2) circle (2.1pt) node[anchor=south] {$7$}; \filldraw (4.5 + 5.5 - 3.0 - 1.0,10.5) circle (2.1pt) node[anchor=east] {$4$}; \filldraw (4.5 + 5.5 - 1.2,10.5 - 1.6) circle (2.1pt) node[anchor=north] {$5$}; \filldraw (4.5 + 5.5 - 1.2 - 1.6,10.5 - 1.6 - 1.2) circle (2.1pt) node[anchor=north] {$2$}; \filldraw (4.5 + 5.5 + 1.6,10.5 - 1.2) circle (2.1pt) node[anchor=west] {$1$}; \filldraw (4.5 + 5.5 + 1.6,10.5 - 1.2 - 2.0) circle (2.1pt) node[anchor=north] {$3$}; \draw[-,ultra thick] (4.5 + 5.5,10.5) -- (4.5 + 5.5 - 1.2,10.5 + 1.6); \draw[-,-] (4.5 + 5.5 - 1.2,10.5 + 1.6) -- (4.5 + 5.5,10.5 + 3.2); \draw[-,-] (4.5 + 5.5,10.5 + 3.2) -- (4.5 + 5.5 + 2.0,10.5 + 3.2); \draw[-,ultra thick] (4.5 + 5.5 - 1.2,10.5 + 1.6) -- (4.5 + 5.5 - 3.0 - 1.0,10.5); \draw[-,-] (4.5 + 5.5,10.5) -- (4.5 + 5.5 - 1.2,10.5 - 1.6); \draw[-,ultra thick] (4.5 + 5.5 - 1.2,10.5 - 1.6) -- (4.5 + 5.5 - 1.2 - 1.6,10.5 - 1.6 - 1.2); \draw[-,-] (4.5 + 5.5,10.5) -- (4.5 + 5.5 + 1.6,10.5 - 1.2); \draw[-,ultra thick] (4.5 + 5.5 + 1.6,10.5 - 1.2) -- (4.5 + 5.5 + 1.6,10.5 - 1.2 - 2.0); \draw (4.5 + 5.5 + 1.8 + 1.0,10.5) arc (0:360:1.0cm and 4.0cm); \draw (4.5 + 5.5 + 1.2 - 0.8,10.5 - 0.6) arc (0:360:2.5cm and 3.5cm); \end{tikzpicture} \end{center} \caption{Finding a $T_9$-stable partition $\Sigma$ for $\Pi = 137-24568$} \label{Fig2} \end{figure} For illustration, consider the two-block partition $\Pi = 137-24568$ of $\{1,2, \ldots , 8\}$. We will associate it with a three-block $T_9$-stable partition. Begin by adjoining the singleton block 9 to get $137-24568-9$. Next, consider the (uniquely defined) paths in $T_9$ that connect the root 9 to the pendant vertices of $T_9$. In our example, these paths are $9 \rightarrow 7$, $9 \rightarrow 8 \rightarrow 4$, $9 \rightarrow 8 \rightarrow 6 \rightarrow 5 \rightarrow 2$, and $9 \rightarrow 8 \rightarrow 6 \rightarrow 1 \rightarrow 3$. We traverse each such path, marking certain vertices for transfer from their present block to the new block so far containing only the vertex 9. No vertices along the (very short) path $9 \rightarrow 7$ need to be marked for transfer because all the edges that appear in this path (there is only one of course) are stable edges for the partition $\Pi$. In the path $9 \rightarrow 8 \rightarrow 4$, the edge $8 \rightarrow 4$ is unstable for $\Pi$. We mark the vertex $4$ (the one the arrow $8 \rightarrow 4$ points to) for transfer to the new block containing the root vertex 9. The path $9 \rightarrow 8 \rightarrow 6 \rightarrow 5 \rightarrow 2$ has three $\Pi-$unstable edges. The first unstable edge, $8 \rightarrow 6$, requires that vertex 6 be marked for transfer. This transfer will move 6 out of its present block, so we do not mark vertex 5 for transfer. (Marked vertices are never adjacent vertices.) However, edge $5 \rightarrow 2$ is $\Pi-$unstable, and remains so even after vertex 6 is moved to the new block. Hence vertex $2$ needs to be marked for transfer. Finally, the path $9 \rightarrow 8 \rightarrow 6 \rightarrow 1 \rightarrow 3$ has two $\Pi-$unstable edges, with the arrows pointing to vertices $6$ and $3$. Since the transfer of vertex 6 does not make edge $1 \rightarrow 3$ $\Pi-$stable, both 6 and 3 must be marked for transfer. To sum up, we have marked vertices 4, 6, 2 and 3 for transfer to the new block containing 9. After this transfer is made, the partition $\Pi$ has been mapped to the $T_9-$stable partition $\Sigma = 17-58-23469$. Now, using $\Sigma = 17-58-23469$ for illustration, we will describe the (inverse) mapping that assigns to each $T_9-$ stable partition of $\{1, 2, \ldots , 9\}$ a partition of $\{1, 2, \ldots , 8\}$. This mapping is simpler to explain. One merely reverses all of the previous arrows so that they point away from the pendant vertices and toward the root vertex. Then, each element of the block of $\Sigma$ containing the root vertex, except for the root vertex itself, is (re)-assigned to the block containing the vertex that its arrow now points to. For example, the arrow out of vertex 2 now points to vertex 5, so 2 is reassigned to the block containing 5. The root vertex is simply erased. This procedure carries $\Sigma$ back to $\Pi$ as the reader will readily verify. \medskip Several comments about the two mappings $\Pi \rightarrow \Sigma$ and $\Sigma \rightarrow \Pi$ are in order. First, to show that we have a bijective correspondence, we need to see why compositions $\Pi \rightarrow \Sigma \rightarrow \Pi$ and $\Sigma \rightarrow \Pi \rightarrow \Sigma$ are both identity mappings. The reason for this is that the edges involving transfers of vertices for both $\Pi$ and $\Sigma$ are identical (apart from being oriented oppositely). In our example, these edges are $\{84, 86, 13, 52\}$ for $\Pi$, and $\{48, 68, 31, 25\}$ for $\Sigma$. Second, it is quite clear that the first mapping $\Pi \rightarrow \Sigma$ adds exactly one block to $\Pi$, and the second mapping $\Sigma \rightarrow \Pi$ removes exactly one block from $\Sigma$. Hence (ii) and (i) have essentially the same proof. $\square$\renewcommand{\qedsymbol}{}\end{proof} Third, the vertex set $\{1, 2, \ldots, n+1\}$ has the natural ordering inherited from the integers $\mathbb Z$, but this ordering plays practically no role in our development. The numbers $1, 2, \ldots, n+1$ could be arbitrary symbols. All that matters is that they can be told apart, and that one of them is designated to play a special role as the root of $T_{n+1}$. By contrast, Proposition~\ref{Prop32} below (and its proof) does exploit the natural ordering of the integers as vertex labels. Finally, there are easy ways to speed up the execution time of the algorithm we have described for the mapping $\Pi \rightarrow \Sigma$. For clarity of exposition, we described the algorithm as one that examines all paths starting at the root vertex and ending at a pendant vertex. It should be clear that once such a path is scanned, if there are other paths that branch off from it, one does not have to return all the way to the root vertex, but only to where the branching off occured. It should be possible to write computer code for the algorithm so that it runs in linear time. \bigskip For our second generalization of Munagi's observation, we define a two-parameter family of {\it generalized path graphs} as follows: For integers $m$ and $n$ with $0 \le m \le n$ and $n > 0$, the (undirected) graph $P_{n,m}$ has vertex set $\{1, 2, \ldots , n\}$, and edge set $E(P_{n,m}) = \{(i,j):0 < |i - j| \le m\}.$ Note that, in particular, $P_{n,0}$ is the edgeless graph $E_n$, and $P_{n,1}$ is the familiar path graph $P_n$ that appeared as one of our one-parameter families in Section~\ref{Sect2}. \begin{proposition}\label{Prop32} Let $P_{n,m}$ be any generalized path graph. Then: (i) For any positive integer $j$, we have $B(P_{n,m}) = B(P_{n+j,m+j})$; (ii) For $m < k \le n$, we have $S(P_{n,m},k) = S(P_{n+j,m+j},k+j)$. \end{proposition} \begin{proof} We have $S(P_{n,0},k) = S(E_n,k) = S(n,k)$ (classical Stirling number of the Second Kind). Proposition~\ref{Prop32} will be proved if we can show that $S(n,k) = S(P_{n+j,j},k+j)$ for all $j > 0$. One way to do this begins by recalling that the triangular integer array $(a_{n,k}) = (S(n,k))$ is fully defined by the Pascal Triangle-like boundary conditions $S(n,1) = S(n,n) = 1$ and recurrence relation $S(n+1,k) = S(n,k-1) + kS(n,k)$. It therefore suffices to show that for any fixed $j > 0$, the array $(b_{n,k}) = (S(P_{n+j,j},k+j))$ satisfies the same boundary conditions and recurrence relation. The boundary condition $b_{n,n} = S(P_{n+j,j},n+j) = 1$ is trivial, the only admissible partition being the one in which every block is a singleton. To see that $b_{n,1} = S(P_{n+j,j},j+1) = 1$, we will find the only stable partition $\Pi$ of $P_{n+j,j}$ that has exactly $j + 1$ blocks. (For example, for $P_{7,2}$, this partition would be $147 - 25 - 36$). Let the elements of the blocks of $\Pi$ be listed in ascending order: $\{a, b, c, \cdots\}$ with $a < b < c \cdots$; $\{d,e,\cdots\}$ with $d < e < \cdots$; etc. Since $\Pi$ is stable, the gaps between consecutive elements in its blocks must be at least $j+1$: $b - a \ge j+1$, $c - b \ge j+1$, $e - d \ge j+1$, etc., and these inequalities are in fact equalities. For, if there were a larger gap, say a block $\{\cdots f, g, \cdots\}$ of $\Pi$ with $g - f > j+1$, then the $j+1$ elements $f+1, f+2, \cdots, f+j+1$ would be in different blocks of $\Pi$, and these $j+1$ blocks, along with the one with the big gap, would contradict the fact that $\Pi$ has only $j+1$ blocks. This argument shows that there can be at most one stable partition $\Pi$ of $P_{n+j,j}$ with $j+1$ blocks. To see that there is such a partition, just take the integers $1,2,\cdots,j+1$ (noting that these are all vertices of $P_{n+j}$ since $n \ge 1$), and assign each to its separate block of $\Pi$ as follows: $\{1, 1 + (j+1), 1 + 2(j+1), \cdots\}$, $\{2, 2 + (j+1), 2 + 2(j+1), \cdots\}$, etc. Next we verify that for fixed $j$, we have $$S(P_{n+1+j,j},k+j) = S(P_{n+j,j},k-1+j) + kS(P_{n+j,j},k+j).$$ The argument is a simple extension of the familiar one (for example, (\cite[p.\ 22]{MA} for the classical Stirling numbers $S(n,k)$. Consider the collection of stable partitions of $P_{n+1+j,j}$ with $k+j$ blocks. Among these partitions, there are some in which the block containing the vertex $n+1+j$ is a singleton; by deleting this block we set up a bijection between this subcollection of stable partitions of $P_{n+1+j,j}$, and all stable partitions of $P_{n+j,j}$ with $k-1+j$ blocks. In the remaining subcollection of stable partitions of $P_{n+1+j,j}$ with $k+j$ blocks, the vertex $n+1+j$ shares a block with other vertices (or another vertex). If we delete this vertex $n+1+j$, the block it belong to still exists, so we get a stable partition of $P_{n+j,j}$ still with $k+j$ blocks. This is not a bijection but a many-one correspondence. For, if we take an arbitrary stable partition of $P_{n+j,j}$ with $k+j$ blocks, and try to insert the vertex $n+1+j$ into one of these blocks to get a stable partition of $P_{n+1+j,j}$, there are (only) $k$ blocks into which it can be inserted, since the blocks containing the vertices $n+j, n+j-1,n+j-2, \cdots, n+1$ are not available. This completes one proof of Proposition~\ref{Prop32}. We would prefer a proof that sets up a direct bijective correspondence between the stable partitions of $P_{n,m}$ with $k$ blocks and those of $P_{n+1,m+1}$ with $k+1$ blocks. $\square$\renewcommand{\qedsymbol}{}\end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Section 4. Graph Families whose Bell Numbers are Quasigeometric Sequences % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Graph Families whose Bell Numbers are Quasigeometric Sequences.} Recall from Section~\ref{Sect2} that $B(\overline{P_n}) = F_{n+1}$, shifted Fibonacci number. Using a well-known version of the Binet formula for Fibonacci numbers, we can write $B(\overline{P_n}) = \lfloor s \cdot \phi^n \rceil$, where $s = (5 + \sqrt{5})/10$, $\phi = (1 + \sqrt{5})/2$ (golden mean), and $\lfloor \cdot \rceil$ is the nearest integer function \footnote{Since all numbers that get rounded in this section are irrational, the issue of how to round half-integers will not arise.}. The Binet-like formula for the Lucas numbers, $L_n = \phi^n + (\phi^*)^n$, with $\phi^* = (1 - \sqrt{5})/2$, can also be recast with the nearest integer function: $L_n = \lfloor \phi^n \rceil$, but in this case, we must take $n > 1$. Recalling our discussion from Section~\ref{Sect2} about Bell numbers of cycle complement graphs, we then have $B(\overline{C_n}) = \lfloor \phi^n \rceil$, for $n > 3$.\footnote{To further clarify, beginning at $n = 1$, we have: $(L_n) = 1,3,4,7,11,\cdots$; $( \lfloor \phi^n \rceil ) = 2,3,4,7,11,\dots$; $(B(\overline{C_n})) = 1,2,5,7,11\cdots$. For $n > 3$ the three sequences are identical.} The aim in this section is to extend these results in a certain way. Our discussion will lead naturally to a conjecture that may lie at the heart of emerging graphical Bell number theory. \begin{definition} A sequence of integers $(a_n)$, $n = 1,2,\ldots$, is called {\rm quasigeometric} if there are constants $s$ and $r$ and an integer $N$ such that $a_n = \lfloor s \cdot r^n \rceil$ for $n \ge N$. If we can choose $N = 1$, we call $(a_n)$ {\rm strictly quasigeometric}. \end{definition} Thus $(B(\overline{C_n}))$ is a quasigeometric sequence, and $(B(\overline{P_n}))$ is a strictly quasigeometric sequence. For another combinatorial context in which such sequences occur, see \cite{HW2}. Our extension concerns the family $(\overline{P_{n,2}})$. The graph $\overline{P_{n,2}}$ has vertex set $\{1,2,\ldots,n\}$ and (undirected) edge set $\{e = (i,j): |i - j| > 2\}$. Each block in any stable partition of $\overline{P_{n,2}}$ must have one of these forms: singletons $\{ i \}$; consecutive doubletions $\{i, i+1\}$; doubletons of the form $\{ i,i+2\}$; and consecutive three-element sets $\{i,i+1,i+2\}$. In particular, when $n = 4$ we have this list of stable partitions: $$\begin{matrix} 1-2-3-4 & 12-3-4 & 1-23-4 & 1-2-34 & 13-2-4 \\ 1-24-3 & 12-34 & 13-24 & 1-234 & 123-4 \end{matrix}.$$ \begin{proposition}\label{Prop41} The sequence of graphical Bell numbers, $(B(\overline{P_{n,2}}))$, is strictly quasigeometric: $$B(\overline{P_{n,2}}) = \lfloor s \cdot r^n \rceil; \qquad s = 0.53979687305\ldots; \qquad r = 2.0659948920\ldots\,.$$ \end{proposition} \begin{proof} The proof of Proposition~\ref{Prop41} relies on standard technique. Setting $b_n = B(\overline{P_{n,2}})$ for $n \ge 1$, we have initial conditions $b_1 = 1$, $b_2 = 2$, $b_3 = 5$; and as we saw above, $b_4 = 10$. Further, for any fixed $n > 4$, the collection of stable partitions of $\overline{P_{n,2}}$ may be classified, according to the kind of block that contains the vertex $n$. (For example, in $b_{n-1}$ of these stable partitions, $n$ appears as a singleton block $\{ n \}$.) Doing so gives the following recurrence relation of order four: $$b_n = b_{n-1} + b_{n-2} + 2b_{n-3} + b_{n-4}.$$ The roots of the characteristic equation of this recurrence relation are shown on the right of Figure~\ref{Fig3}. This figure makes clear why both $B(\overline{P_n})$ and $B(\overline{P_{n,2}})$ are quasigeometric sequences. The key fact is that in both cases, all but the dominant root are within the unit circle (although in the case of $B(\overline{P_{n,2}})$, this is true only by a hair's breadth!) Hence, there are constants $r,a,b$ such that $b_n = r\cdot s^n + a \cdot q^n + b\cdot p^n + \overline{b} \cdot \overline{p}^n$, with all but the first term on the right damping to zero as $n$ gets large. Thus $B(\overline{P_{n,2}}) = \lfloor s \cdot r^n \rceil$ for sufficiently large $n$, and by examining the first few terms of $(s \cdot r^n)$ we find that the equality holds for $n \ge 1$. So Proposition~\ref{Prop41} is proved. $\square$\renewcommand{\qedsymbol}{}\end{proof} %%%%%%%%%%%%%%%%%%%%%%% % Figure 3 % %%%%%%%%%%%%%%%%%%%%%%% \begin{figure} %\capstart \begin{center} \begin{tikzpicture}[scale=0.9] \draw (-2.0,0) -- (5.5,0); \draw (1,-4.0) -- (1,4.0); \draw (1,0) circle (2.5cm); \draw (3.5,2.0) node {$|z| = 1$}; \filldraw (5.045,0.0) circle (1.5pt) node[anchor=north] {$\phi$}; \filldraw (-0.545,0.0) circle (1.5pt) node[anchor=north] {$\phi^{*}$}; \draw (7.0,0) -- (15.5,0); \draw (10,-4.0) -- (10,4.0); \draw (10,0) circle (2.5cm); \draw (12.5,2.0) node {$|z| = 1$}; \filldraw (8.682,0.0) circle (1.5pt) node[anchor=north] {$q$}; \filldraw (15.125,0.0) circle (1.5pt) node[anchor=north] {$r$}; \filldraw (9.326,-2.299) circle (1.5pt) node[anchor=south] {$\overline{p}$}; \filldraw (9.326,2.299) circle (1.5pt)node[anchor=north] {$p$}; \draw (1,-4.5) node {For $(B(\overline{P_n}))$}; \draw (10,-4.5) node {For $(B(\overline{P_{n,2}}))$}; \end{tikzpicture} \end{center} \caption{Characteristic roots for linear recurrences defining $(B(\overline{P_n}))$ and $(B(\overline{P_{n,2}}))$.} \label{Fig3} \end{figure} If we do not use the nearest integer function, and regard $B(\overline{P_n}) \approx (5 + \sqrt{5})/10 \cdot \phi^n$ and $B(\overline{P_{n,2}}) \approx s \cdot r^n$ as approximations, then the sign of the error term in the first of these formulas alternates, while in the second one the behavior of the sign of the error is very erratic. The impeccable behavior of the Bell number sequences $B(\overline{P_n})$ and $B(\overline{P_{n,2}})$ suggests to us the following: \begin{conjecture}For any fixed $k \ge 0$, the graphical Bell number sequence $B(\overline{P_{n,k}})$ is quasigeometric. \end{conjecture} Various strengthenings and analogs of this conjecture are possible. Since our evidence for it is based entirely on the cases $k = 1$ and $k = 2$, we have chosen a rather conservative formulation. We note that $(B(\overline{P_{n,2}}))$ is sequence \seqnum{A129847} in \cite{OIS}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Section 5. Relations Among Polynomial Invariants for Graphs % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Relations Among Polynomial Invariants for Graphs and Matroids.}\label{Sect5} In this section, $S(n,k)$ and $s(n,k)$ denote the classical Stirling numbers of the Second Kind, and (signed) First Kind, respectively. We reserve the notation $S(G,k)$ for graphical Stirling numbers, and set $|V(G)| = n$. At the end of Section~\ref{Sect1} it was mentioned that if $A(G,\alpha) = \sum_{k=c(G)}^n S(G,k) \alpha^k$ is the stable partition generating function of $G$, then $\chi(G,\lambda) = \sum_{k=c(G)}^n S(G,k) \lambda^{(k)}$ is the characteristic polynomial of $G$. In preparation for formulating this relationship as a matrix product, we will ``pad'' both $A(G,\alpha)$ and the falling factorials $\lambda^{(k)} = \sum_{j=1}^k s(k,j)\lambda^j$ with extra zero terms so that both of these polynomials have exactly $n$ terms with exponents $1, 2,\ldots, n$, but no constant term. Then \begin{align} \chi(G,\lambda) &= \sum_{k=c(G)}^n S(G,k) \cdot \sum_{j=1}^k s(k,j) \lambda^j \notag \\ &= \sum_{k=1}^n S(G,k) \cdot \sum_{j=1}^n s(k,j) \lambda^j \tag{2} \\ &= \sum_{j=1}^n \sum_{k=1}^n S(G,k) \cdot s(k,j) \lambda^j \notag. \end{align} Thus if we identify $A(G,\alpha)$ with the row vector ${\bf A} = [S(G,1), S(G,2), \ldots , S(G,n)]$, and let ${\bf s} = (s(i,j))_{n \times n}$ be the $n$ by $n$ lower triangular matrix of (signed) Stirling Numbers of the First Kind, then the matrix product ${\bf X} = {\bf A} \cdot {\bf s} = [c_1, c_2, \ldots , c_n]$ is the row vector whose entries are the coefficients in the chromatic polynomial $\chi(G,\lambda) = \sum_{i=1}^n c_i\lambda^i$ of $G$. Since the inverse of ${\bf s}$ is the $n$ by $n$ matrix of classical Stirling numbers of the Second Kind, ${\bf s}^{-1} = {\bf S} = (S(i,j))_{n \times n}$, we also have that ${\bf A} = {\bf X} \cdot {\bf S}$. This shows that the invariants $A(G,\alpha)$ and $\chi(G,\lambda)$ are {\it equivalent}; they contain exactly the same information about $G$, and that is computationally easy to pass from one to the other. \footnote{This equivalence of $A$ and $\chi$ seems to be part of mathematical folklore, but most graph theory textbooks and survey articles on chromatic polynomials do not mention it.} Since graphs are also matriods, $G$ has a {\it Tutte polynomial} $t(G;x,y) = \sum_{i=0}^p \sum_{j=0}^q a_{ij} x^j y^i$. (Some of the standard references for Tutte polynomial theory are \cite{MA, NB, BB, TB, TBJO, IGBS}.) Note that we must sum from 0 rather than 1 for this polynomial. There is no constant term, $a_{00} = 0$, but there are nonzero terms $a_{0j}$ and these (pure $x$) terms are the important ones in the present context. It is known (for example, \cite[Thm.\ 6, p. 346]{BB}) that the Tutte polynomial of a graph along with its number $k$ of connected components determine its chromatic polynomial: $\chi(G,\lambda) = (-1)^n \lambda^k t(1-\lambda,0)$. (The value of $n$ need not be specified since chromatic polynomials are monic; the highest power of $\lambda$ has coefficient 1.) We can also formulate the relationship between $t(G;x,y)$ and $\chi(G;\lambda)$ as a matrix product. Begin by identifying $t(G;x,y)$ with the $(p+1)\times (q+1)$ matrix ${\bf t} = (a_{ij})$. (Our running example $G$ from Section I has $t(G;x,y) = x + 2x^2 + 2x^3 + x^4 + y + 2xy + x^2y + y^2$ so that in this case ${\bf{t}}$ is a 3 by 5 matrix.) Now discard all but the top row ${\bf T}$ of ${\bf t}$: thus ${\bf T} = {\bf u \cdot t}$ where ${\bf u}$ is the standard unit vector $(1,0,0,\ldots, 0)$. The evaluation of $t$ at $x = \lambda - 1$ can be effected by right-multiplying by a matrix of signed binomial coefficients: ${\bf T \cdot C}$ with ${\bf C} = \left((-1)^{j}\binom{i}{j}\right)$. (This is proved by a calculation similar to (2) above.) Since the left entry of $\bf X$ is $c_1$ and not $c_0$, multiplying by $\lambda^k$ corresponds to inserting $k-1$ leading zeros; this can be effected by right-multiplying by the appropriate zero-one matrix ${\bf D}$ with ones on the $(k-1)$-st superdiagonal and zeros elsewhere (for connected graphs, ${\bf D}$ is just the identity matrix, so this step can be skipped). In summary: ${\bf X} = {\pm \, {\bf u} \cdot {\bf t} \cdot {\bf C} \cdot {\bf D}}$. The sign ambiguity is resolved by the requirement that the rightmost entry of ${\bf X}$ must be 1. We note that the equation ${\bf X} = {\pm \, {\bf u} \cdot {\bf t} \cdot {\bf C} \cdot {\bf D}}$ makes sense for an abritrary (not necessarily graphic) matroid $M$, provided that we assign it a {\it graphical connectivity number} $k$. We would suggest a default value $k = 1$. Right-multiplying ${\bf X}$ by ${\bf S}$ then gives us ${\bf A}$, and we can even define a matriodal Bell number by matrix multiplication (dot-product operation) : $B(M) = {\bf A} \cdot {\bf 1}$, where ${\bf 1}$ is the column vector of all ones. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Section 6. Acknowledgements. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Acknowledgements.} Professors William Nowell, Matthew Ragland, Richard Stanley, and Thomas Zaslavsky, Mr. Frank Jurjevich, and the anonymous referee helped in various ways to make this a better paper. Rhodes Peele owes his mathematical career to the late Professor Thomas Brylawski. We dedicate our work to his memory, and to Bruna and Professor Brylawski's extended family. %%%%%%%%%%%%%%%%%%%%%%%%%% % Bibliography % %%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{99} \bibitem{MA} M. Aigner, {\it A Course in Enumeration}, Springer, 2007. \bibitem{ABJQ} A. Benjamin and J. Quinn, {\it Proofs that Really Count: the Art of Combinatorial Proof}, Mathematical Association of America, 2003. \bibitem{NB} N. Biggs, {\it Algebraic Graph Theory}, Cambridge University Press, 1974. \bibitem{BB} B. B\'{o}llobas, {\it Modern Graph Theory}, Springer, 1998. \bibitem{TB} T. Brylawski, The Tutte polynomial, in {\it Matroid Theory and its Applications}, Liguori editore, Napoli, 1982, pp.\ 125--176. \bibitem{TBJO} T. Brylawski and J. Oxley, The Tutte polynomial and its applications, in N. White, ed., {\it Matroid Applications}, Cambridge University Press, 1992, pp.\ 123--225. \bibitem{IGBS} I. Gessel and B. Sagan, \htmladdnormallink{The Tutte polynomial of a graph, depth-first search, and simplicial} {http://www.combinatorics.org/Volume_3/Abstracts/v3i2r9.html} complex partitions, {\it Electronic J. Combin.}, {\bf 3(2)} (1996), Paper \#R9. \bibitem{AOM} A. Munagi, \htmladdnormallink{$k$-Complementing subsets of nonnegative integers}{http://www.emis.de/journals/HOA/IJMMS/2005/2215.pdf}, {\it Internat. Jour. Math.} {\bf 21} (2005), 215--224. \bibitem{RCWT} R. Read and W. Tutte, Chromatic polynomials, in L. Beineke and R. Wilson, eds., {\it Selected Topics in Graph Theory 3}, Academic Press, 1988, pp.\ 15--43. \bibitem{OIS} N. J. A. Sloane, \htmladdnormallink{\it The On-Line Encyclopedia of Integer Sequences}{http://www.research.att.com/~njas/sequences/}, published electronically at {\tt http://www.research.att.com/$\sim$njas/sequences}. \bibitem{HW1} H. Wilf, {Which polynomials are chromatic?}, in {\it Colloquio Internazionale sulle Teorie Combinatorie}, Accademia Nazionale dei Lincei, Tomo 1 (1973), pp.\ 247--257. \bibitem{HW2} H. Wilf, Strings, substrings, and the nearest integer function, {\it Amer. Math. Monthly}, {\bf 94} (1987) 855--861. \end{thebibliography} \bigskip \hrule \bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % AMS Subject Classification and Keywords % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \noindent{2000 {\it Mathematics Subject Classification:}} \noindent{\it Primary:} 05A18; {\it Secondary:} 05A15, 05B35, 05C05, 05C50, 05C85. \medskip \noindent {\it Keywords:} simple graph; stable partition; graphical Bell number; graphical Stirling number; chromatic polynomial; matroid; Tutte polynomial. \bigskip \hrule \bigskip \noindent{Concerned with sequences \seqnum{A000032}, \seqnum{A000045}, \seqnum{A000110}, \seqnum{A000296}, and \seqnum{A129847}.} \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 28 2009; revised version received October 8 2009. Published in {\it Journal of Integer Sequences}, October 13 2009. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}