\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \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,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{wasysym} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\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} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{Observation}[theorem]{Observation} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Proper $n$-Cell Polycubes in $n-3$ Dimensions } \vskip 1cm \large Andrei Asinowski \\ Department of Mathematics \\ The Technion---Israel Institute of Technology \\ Haifa~32000 \\ Israel \\ \href{mailto:andrei@tx.technion.ac.il}{\texttt{andrei@tx.technion.ac.il}} \\ \ \\ Gill Barequet \\ Department of Computer Science\\ The Technion---Israel Institute of Technology \\ Haifa~32000 \\ Israel \\ \href{mailto:barequet@cs.technion.ac.il}{\texttt{barequet@cs.technion.ac.il}} \\ \ \\ Ronnie Barequet \\ Department of Computer Science \\ Tel Aviv University \\ Tel Aviv~69978 \\ Israel \\ \href{mailto:ronnieba@post.tau.ac.il}{\texttt{ronnieba@post.tau.ac.il}} \\ \ \\ G\"{u}nter Rote \\ Institut f\"{u}r Informatik \\ Freie Universit\"{a}t Berlin \\ Takustra{\ss}e~9 \\ D-14195 Berlin \\ Germany \\ \href{mailto:rote@inf.fu-berlin.de}{\texttt{rote@inf.fu-berlin.de}} \\ \end{center} \vskip .2 in \begin{abstract} A $d$-dimensional polycube of size $n$ is a connected set of $n$ cubes in $d$ dimensions, where connectivity is through $(d-1)$-dimensional faces. Enumeration of polycubes, and, in particular, specific types of polycubes, as well as computing the asymptotic growth rate of polycubes, is a popular problem in combinatorics and discrete geometry. This is also an important tool in statistical physics for computations and analysis of percolation processes and collapse of branched polymers. A polycube is said to be \emph{proper} in $d$ dimensions if the convex hull of the centers of its cubes is $d$-dimensional. In this paper we prove that the number of polycubes of size $n$ that are proper in $n-3$ dimensions is $2^{n-6} n^{n-7} (n-3) (12 n^5 - 104 n^4 + 360 n^3 - 679 n^2 + 1122 n - 1560) / 3$. \end{abstract} \newcommand{\DX}{\mathrm{DX}} \newcommand{\btwo}{\binom{n-3}{2}} %%% Structures \newcommand{\ya}{{A}} \newcommand{\yb}{{B}} \newcommand{\yc}{{C}} \newcommand{\yd}{{D}} \newcommand{\ye}{{E}} \newcommand{\yf}{{F}} \newcommand{\yg}{{G}} \newcommand{\yh}{{H}} \newcommand{\yi}{{I}} \newcommand{\yj}{{J}} \newcommand{\yk}{{K}} \newcommand{\yl}{{L}} \newcommand{\ym}{{M}} \newcommand{\yn}{{N}} \newcommand{\yo}{{O}} \newcommand{\yp}{{P}} \newcommand{\yq}{{Q}} \newcommand{\yr}{{R}} %%% Cardinalities of structures \newcommand{\za}{\mathbf{A}} \newcommand{\zb}{\mathbf{B}} \newcommand{\zc}{\mathbf{C}} \newcommand{\zd}{\mathbf{D}} \newcommand{\ze}{\mathbf{E}} \newcommand{\zf}{\mathbf{F}} \newcommand{\zg}{\mathbf{G}} \newcommand{\zh}{\mathbf{H}} \newcommand{\zi}{\mathbf{I}} \newcommand{\zj}{\mathbf{J}} \newcommand{\zk}{\mathbf{K}} \newcommand{\zl}{\mathbf{L}} \newcommand{\zm}{\mathbf{M}} \newcommand{\zn}{\mathbf{N}} \newcommand{\zo}{\mathbf{O}} \newcommand{\zp}{\mathbf{P}} \newcommand{\zq}{\mathbf{Q}} \newcommand{\zr}{\mathbf{R}} \newcommand{\zs}{\mathbf{S}} \newcommand{\zt}{\mathbf{T}} \newcommand{\zx}{\mathbf{X}} \newcommand{\zy}{\mathbf{Y}} \newcommand{\zz}{\mathbf{Z}} \section{Introduction} A $d$-dimensional \emph{polycube} of size $n$ is a connected set of $n$ cubical cells on the lattice $\mathbb{Z}^d$, where connectivity is through $(d-1)$-faces. Two \emph{fixed} polycubes are considered equivalent if one can be transformed into the other by a translation. A polycube is called \emph{proper} in $d$ dimensions if the convex hull of the centers of all its cubes is $d$-dimensional. While in the mathematical literature these objects are called polycubes (\emph{polyominoes} in two dimensions), they are usually referred to as (strongly-embedded) \emph{lattice animals} in the literature of statistical physics. Following Lunnon~\cite{Lu75}, we let $\DX(n,d)$ denote the number of $n$-cell fixed polycubes that are proper in $d$ dimensions. Counting polycubes (or animals) is a long-standing problem in discrete geometry, originating in statistical physics~\cite{BH57}. To-date, no formula is known for $A_d(n)$, the number of polycubes of size $n$ in $d$ dimensions, for any fixed value of $d$, not to mention the general case. Klarner~\cite{Kl67} showed that the limit $\lambda_2 = \lim_{n \to \infty} \sqrt[n]{A_2(n)}$ exists. Thirty two years have passed until Madras~\cite{Ma99} proved the convergence of the sequence $A_2(n+1) / A_2(n)$ to $\lambda_2$ (and, in fact, a similar claim in any fixed dimension $d$), as $n$ tends to infinity. Thus, $\lambda_2$ is the \emph{growth rate} limit (also known as the \emph{connective constant}) of polyominoes. Its exact value has remained elusive till these days. The currently best lower and upper bounds known on $\lambda_2$ are roughly~3.9801~\cite{BMRR06} and~4.6496~\cite{KR73}, respectively. Much less is known in higher dimensions, let alone in a general dimension $d$. Significant progress has been obtained along the years in the literature of statistical physics, although the computations usually relied on unproven assumptions or on formulae which were interpolated empirically from a few known values of $A_d(n)$. The expansion $$ \ln \lambda_d = \ln \sigma + 1 - \frac{2}{\sigma} - \frac{79}{24\sigma^2} - \frac{317}{24\sigma^3} - \frac{18321}{320\sigma^4} - \frac{123307}{240\sigma^5} + O(\frac{1}{\sigma^6}), $$ where $\sigma = 2d-1$ (one less than the \emph{coordination number} of the cubical lattice $\mathbb{Z}^d$), is provided by Gaunt and Peard~\cite{GP00}. This $1/d$-expansion (of the \emph{free energy} of animals, in their terminology) is partly based on so-called ``diagonal formulae,'' that is, formulae for $\DX(n,n-k)$, where $k>0$ is a small constant. It turned out that this expansion is consistent with the main result obtained by Barequet et al.~\cite{BBR10}, namely, that the growth-rate limit of the number of polycubes in $d$ dimensions is asymptotically $2ed-o(d)$, conjectured to asymptotically be $(2d-3)e-\frac{31e}{48d}+O(\frac{1}{d^2})$. In the literature of statistical physics~\cite{LM11,PG95}, formulae for $\DX(n,n-k)$ are interpolated for $1 \leq k \leq 7$. (See also a discussion by Barequet et al.~\cite[p.~265]{BBR10} about how to derive these formulae from more general formulae provided by Peard and Gaunt~\cite{PG95}.) It is rather easy to show, using Cayley trees, that $$ \DX(n,n-1) = 2^{n-1} n^{n-3} $$ (sequence \seqnum{A127670} in the On-Line Encyclopedia of Integer Sequences~\cite{oeis}). Barequet et al.~\cite{BBR10} proved rigorously, for the first time, that $$ \DX(n,n-2) = 2^{n-3} n^{n-5} (n-2) (2n^2-6n+9) $$ (sequence \seqnum{A171860} in the on-line encyclopedia of integer sequences). The proof uses a case analysis of the possible structures of spanning trees of the polycubes, and the various ways in which cycles can be formed in their cell-adjacency graphs. In this paper we find the explicit formula for $\DX(n, n-3)$, the number of $n$-cell polycubes that are proper in $d = n-3$ dimensions (sequence \seqnum{A191092} in the on-line encyclopedia of integer sequences), stated in the following theorem. \begin{theorem} \label{th:main} $$ \DX(n, n-3) = 2^{n-6} n^{n-7} (n-3) (12 n^5 - 104 n^4 + 360 n^3 - 679 n^2 + 1122 n - 1560) / 3. $$ \end{theorem} Similarly to our proof~\cite{BBR10} of the formula for $\DX(n,n-2)$, we prove the formula for $\DX(n,n-3)$ by counting spanning trees of polycubes, yet the reasoning and the calculations are significantly more involved. Indeed, we use the inclusion-exclusion principle in order to count correctly polycubes whose cell-adjacency graphs contain cycles. Spanning trees of such polycubes contain certain subgraphs, which we call ``distinguished structures.'' In comparison with the case $k=2$, the number of such structures is substantively higher, and the ways in which they can appear in spanning trees are much more varied. Therefore, the proof of Theorem~\ref{th:main} provides us with a better understanding of the difficulties that can be expected in applying this technique for higher values of $k$. In particular, we believe that it is not practical to achieve a similar proof manually for $k>3$. % ---------------------------------------------------------------------------- % Overview of the Method % ====================== \section{Overview of the Method} Denote by $\mathcal{P}_n$ the family of polycubes under consideration. Let $P \in \mathcal{P}_n$, and let $\gamma(P)$ denote the directed graph with labeled edges that is constructed as follows: The vertices of $\gamma(P)$ correspond to cells of $P$; two vertices of $\gamma(P)$ are connected by an edge if the corresponding cells of $P$ are adjacent; an edge has label $i$ ($1 \leq i \leq n-3$) if the corresponding cells have different $i$-coordinate (that is, their common $(d-1)$-dimensional face is perpendicular to the $x_i$ axis) and the direction of the edge is from the lower to the higher cell (with respect to the $x_i$ direction). See Figure~\ref{fig:tree_ex} \begin{figure} \begin{center} \begin{tabular}{ccc} \scalebox{0.50}{\input{tree_ex__1n.tex}} & \scalebox{0.50}{\input{tree_ex__2n.tex}} & \scalebox{0.50}{\input{tree_ex__3n.tex}} \\ (a) Polycube & (b) Adjacency graph & (c) Two spanning trees \end{tabular} \end{center} \caption{A polycube $P$, the corresponding graph $\gamma(P)$, and spanning trees of $\gamma(P)$.} \label{fig:tree_ex} \end{figure} for an example. It is clear that $P \mapsto \gamma(P)$ is an injection. Thus, it suffices to count the graphs obtained from the members of $\mathcal{P}_n$ in this way. We shall accomplish this task by counting their spanning trees. Consider a spanning tree of $\gamma(P)$. It has $n-1$ edges labeled by numbers from the set $\{1, 2, \ldots, n-3\}$; all these labels actually are present, otherwise the polycube is not proper. Thus, either there are two edge labels (say, $i$ and $j$) that appear twice, or there is one edge label (say, $i$) that appears three times. In the former case we distinguish members of such pairs by labeling them $i, i'$ and $j, j'$, while in the latter---by labeling them $i, i', i''$ (see Figure~\ref{fig:tree_ex}(c)). Whenever we consider a spanning tree of $\gamma(P)$, we assume that its repeated labels are distinguished this way. In contrast, when considering $\gamma(P)$, repeated labels are assumed not to be distinguished (as in Figure~\ref{fig:tree_ex}(b)). \begin{Observation} \label{the:even} Every label must occur an even number of times in any cycle of $\gamma(P)$. \end{Observation} In addition, the number of cycles in $\gamma(P)$, as well as the length of each such cycle, are limited due to the limited multiplicity of labels. Therefore, we must have the following: \begin{Observation} \label{the:three_cases} There are three possible cases concerning the structure of $\gamma(P)$: \begin{enumerate} \item $\gamma(P)$ is a tree itself. The number of such \emph{tree-like} polycubes in $\mathcal{P}_n$ will be denoted by~$\zx$. \item $\gamma(P)$ has exactly one cycle. The number of such polycubes in $\mathcal{P}_n$ will be denoted by~$\zy$. The length of this cycle in $\gamma(P)$ is either~4 or~6. \item $\gamma(P)$ has two 4-cycles. The number of such polycubes in $\mathcal{P}_n$ will be denoted by~$\zz$. In this case, the two cycles are either edge-disjoint or have exactly one common edge, thus forming a 6-cycle with a chord. \end{enumerate} \end{Observation} Indeed, all other possibilities (say, more than two 4-cycles, several 6-cycles, or an 8-cycle) are excluded: They would cause $\gamma(P)$ to have a spanning tree with too many repeated labels. Thus, $\DX(n, n-3) = \zx + \zy + \zz$. In order to find the formulae for $\zx, \zy, \zz$, we shall count those directed trees with $n-1$ labeled edges with two pairs of repeated labels or with one triple of repeated labels, which are actually spanning trees of $\gamma(P)$ for some polycube $P \in \mathcal{P}_n$. Note that: \begin{itemize} \item If a tree with two pairs of repeated labels, $i, i'$ and $j, j'$, is a spanning tree of $\gamma(P)$ for some polycube $P \in \mathcal{P}_n$, then the trees obtained by exchanging $i$ and $i'$ and/or $j$ and $j'$ are also spanning trees of $\gamma(P)$. Similarly, if a tree with a triple of repeated labels, $i, i', i''$, is a spanning tree of a $\gamma(P)$, then the trees obtained by permuting $i$, $i'$ and $i''$ are also spanning trees of $\gamma(P)$. \item In particular, if $\gamma(P)$ itself is a tree with two pairs of repeated labels, then it has four spanning trees.\footnote{ Recall that repeated labels are not distinguished in $\gamma(P)$, but they are distinguished in its spanning tree. } If $\gamma(P)$ is a tree with a triple of repeated labels, then it has six spanning trees. \item The situation may be more complicated when $\gamma(P)$ is not a tree at all. There are polycubes $P$ such that $\gamma(P)$ has both types of spanning trees: those with two pairs of repeated labels and those with a triple of repeated labels. (Such a polycube is shown in Figure~\ref{fig:tree_ex}.) \end{itemize} In the next section we characterize all substructures that are present in some trees with labeled edges due to the fact that the number of cells is greater than the number of dimensions. By analyzing this substructures, we will be able to compute how many of such trees actually represent polycubes. Then, in the following sections, we develop formulae for the numbers of all possible spanning trees of the polycubes, and then derive the actual number of polycubes. % ---------------------------------------------------------------------------- % Distinguished Subtrees % ====================== \section{Distinguished Structures} \label{sec:dist-structs} Our plan is to count polycubes by counting spanning trees of their adjacency graphs, taking into account possible multiplicities. In the reasoning below we shall consider several small structures, which may be contained in the spanning trees that we count. These structures are listed in Figure~\ref{fig:subgraphs}, \begin{figure} \begin{center} \scalebox{0.48}{\input{subgraphs_s-n.tex}} \end{center} \caption{Distinguished structures used in the counting.} \label{fig:subgraphs} \end{figure} and they are interesting for the following reason. For each labeled tree, we can attempt to build the corresponding polycube. Two things may happen: (a)~We may get coinciding cells, like in patterns $A$ or $I$ (shown by dotted frames around these points). Such a tree is invalid and does not correspond to a polycube. (b)~Two cells which are not connected by a tree edge may be adjacent, like in pattern $B$ or $C$ (indicated by dotted lines). Such a tree may correspond to a valid polycube, but it deserves special attention because the polycube has cycles in its cell-adjacency graph and, therefore, its spanning tree is not unique. A \emph{distinguished structure} is defined as a subtree that is responsible for the presence of two coinciding or adjacent cells, as explained above. More precisely, a structure is the union of all paths (edges plus incident vertices) that run between two coinciding or adjacent cells. Consider a distinguished structure that leads to coinciding cells. Similarly to Observation~\ref{the:even}, we see that for every label on the path between two vertices that correspond to such cells, repetitions of this label occur on this path an even number of times (which can be only~2). Moreover, in this case, these two edges are directed in opposite orientations. Due to the limited number of repeated labels, we get only two possibilities corresponding to a path of length~2 and a path of length~4 (see structures $A$ and $I$ in Figure~\ref{fig:subgraphs}). Consider now a structure that leads to a non-existing adjacency. This clearly results in an (even) cycle with one edge removed. By Observation~\ref{the:three_cases}, the length of such a cycle can be only either~4 or~6. A reasoning similar to that above leads us to two possibilities: structures $B$ and $C$ in Figure~\ref{fig:subgraphs}. Thus, the distinguished structures are $A, I, B, C$, and other structures that contain several occurrences of these ``basic'' structures.\footnote{ Notice that $I$ itself contains two occurrences of $B$. } The number of occurrences is limited, since each occurrence uses up some repeated labels. The enumeration of the distinguished structures is, thus, a finite task. Figure~\ref{fig:subgraphs} gives the complete list. It may happen that a distinguished structure is disconnected, like $D$, $E$, or $G$. We consider the components of a structure as edge-connected components; thus, it is permitted that the two parts in $D$, $E$, or $G$ share a vertex. The structures $\yc, \ldots, \yl$ occur only in trees with two pairs of repeated labels, while the structures $\ym, \ldots, \yr$ occur only in trees with one triple of repeated labels. In contrast, $\ya$ and $\yb$ occur in both kinds of trees. Next, we clarify the notation and conventions used in Figure~\ref{fig:subgraphs}. Each pattern in Figure~\ref{fig:subgraphs} stands actually for several substructures that may differ in edge directions or the precise choice of labels from $i, i', i''$ or $j, j'$. The edges labeled $i$ and $i'$ (respectively, $i$, $i'$, and $i''$) are all directed either according to black or to white arrows, and the same holds for $j$ and $j'$. The directions of $j, j'$ are independent of those of $i, i'$. The labels $a, b$ are assumed to be unrelated to any of the other labels $i, i', i'', j, j'$ appearing in each pattern. For example, $a$ in pattern $B$ is distinct from $i$ and $i'$ (but it could be another repeated label---say, $j$ or $j'$). Where $a$ or $b$ appear in patterns $C, \ldots, L$, they are automatically distinct from $i, i', j, j'$. Finally, in the remaining patterns $M, \ldots, R$, $a$ and $b$ are automatically distinct from $i, i', i''$. Variations of the same label, say, $i$ and $i'$, can be permuted, or replaced by other variations of the same label, like $i,i''$ or $i',i''$. In counting directed trees with $n-1$ labeled edges, which have subgraphs as in Figure~\ref{fig:subgraphs}, two lemmas will be used. Lemma~\ref{lem:rooted-trees} was proved earlier~\cite{BBR10}; we will here relate it to a result from the literature. \begin{lemma} \label{lem:rooted-trees} \cite[Lemma~4]{BBR10} The number of ordered sequences $T=(\tau_1, \ldots, \tau_k)$ of $k \geq 1$ rooted trees with a total of $n-k$ edges and distinct edge labels $1, \ldots, n-k$ is $n^{n-k-1}k$. \end{lemma} \begin{proof} Consider such a sequence $T$. It has a total of $n$ vertices. For $i=1, \ldots, k$, denote the root of the component $\tau_i$ by $n-k+i$. For any vertex $v$ which is not a root, set its label to be equal to the label of the first edge in the path from $v$ to the root. Now we have a forest $T'$ on $n$ labeled vertices, with roots labeled by $n-k+1, n-k+2, \dots, n$. The correspondence $T \leftrightarrow T'$ is clearly a bijection. The number of forests on $n$ labeled vertices with $k$ roots, whose labels belong to a specified set, is known to be $n^{n-k-1}k$, see Stanley~\cite[p.~25, Proposition~5.3.2]{St}. (Stanley provides two proofs of this, both of them differing from our proof~\cite{BBR10}.) \end{proof} The other lemma is a direct application of the previous lemma. \begin{lemma} \label{lem:rooted-trees-2-roots} The number of ordered sequences $\tilde{T}=(\tau_1, \ldots, \tau_k)$ of $k \geq 1$ trees, such that $\tau_1$ has two distinguished roots (which may coincide) and all other trees have one root, with a total of $n-k$ edges and distinct edge labels $1, \ldots, n-k$, is $n^{n-k}$. \end{lemma} \begin{proof} Consider a sequence $T$ as in Lemma~\ref{lem:rooted-trees}, and mark an arbitrary vertex as the extra root. In this way $n^{n-k}k$ sequences $\tilde{T}$ are obtained. The component of $\tilde{T}$ that has two roots is any of $\tau_1, \ldots, \tau_k$, with equal probability. Therefore, in order to get the number of sequences $\tilde{T}$ in which the component with two roots is $\tau_1$, we have to divide by $k$, obtaining $n^{n-k}$. \end{proof} We now introduce two functions that count ordered sequences of directed trees. Let $F_1(k)$ denote the number of ordered sequences $(\tau_1, \ldots, \tau_k)$ of $k \geq 1$ \emph{directed} rooted trees with a total of $n-k$ edges and distinct edge labels $1, \ldots, n-k$. Similarly, let $F_2(k)$ denote the number of ordered sequences $(\tau_1, \ldots, \tau_k)$ of $k \geq 1$ \emph{directed} trees, such that $\tau_1$ has two distinguished roots (which may coincide) and all other trees have one root, with a total of $n-k$ edges and distinct edge labels $1, \ldots, n-k$. By fixing directions to the edges of undirected trees, we obtain the following corollary of Lemmas~\ref{lem:rooted-trees} and~\ref{lem:rooted-trees-2-roots}. \begin{corollary} \label{the:lemmas} \mbox{} \begin{enumerate} \item $F_1(k) = 2^{n-k} n^{n-k-1} k$. \item $F_2(k) = 2^{n-k} n^{n-k}$. \end{enumerate} \end{corollary} Finally, we will use Corollary~\ref{the:t}, which follows directly from a previous result of ours~\cite{BBR10}. \begin{lemma} \label{the:old_lemma} \cite[Lemma~2]{BBR10} The number of \emph{directed} trees with $n$ vertices and $n-1$ distinct edge labels $1,\ldots,n-1$ is $2^{n-1} n^{n-3}$, for $n \geq 2$. \qed \end{lemma} Let $\zt_{22}$ denote the number of directed trees with $n$ vertices and labeled edges, with two pairs of repeated labels.\footnote{ Recall again that repeated labels in trees are distinguished. } Similarly, let $\zt_3$ denote the number of directed trees with $n$ vertices and labeled edges, with one triple of repeated labels. \begin{corollary} \label{the:t} \mbox{} \begin{enumerate} \item $\zt_{22} = \btwo 2^{n-1} n^{n-3}$. \item $\zt_3 = (n-3) 2^{n-1} n^{n-3}$. \end{enumerate} \end{corollary} Let us turn to the enumeration of occurrences of $\ya, \ldots, \yr$ from Figure~\ref{fig:subgraphs} in directed trees with $n$ vertices and edges labeled $1, 2, \ldots, n-3$, and with repeated labels as explained above. For $\yc, \yd, \ye, \ldots$, we let $\zc, \zd, \ze, \ldots$ denote the number of occurrences of these structures in such trees. Recall that the structures $\yc, \ldots, \yl$ occur only in trees with two pairs of repeated labels, while the structures $\ym, \ldots, \yr$ occur only in trees with one triple of repeated labels. In contrast, $\ya$ and $\yb$ occur in both kinds of trees. Therefore, for $\ya$ and $\yb$ we shall consider both cases (two pairs of repeated labels, and one triple of repeated labels), denoting the corresponding numbers by~$\za_{22}$, $\za_3$, and $\zb_{22}$, $\zb_3$. For some cases we shall explain in detail how the formula is obtained; all other calculations are based on a similar reasoning. We begin with counting \emph{occurrences} of $\ya_{22}, \yb_{22}, \yc, \ldots, \yl$ in directed trees with two pairs of repeated labels. By an \emph{occurrence} of a pattern $U$ in a tree $T$, we mean a pair $(S,T)$, where $S$ is a subset of edges of $T$ that form a the pattern~$U$. \newcounter{mycnt} \begin{enumerate} \item $\za_{22} = (n-3) \cdot (n-4) \cdot 2 \cdot F_1(3) = 6 (n-3) (n-4) 2^{n-3} n^{n-4}.$ \\ Here, we have the factors $(n-3)$ for choosing the repeated label ($i$, $i'$) that makes the configuration and $(n-4)$ for choosing the second repeated label in the tree, a factor~2 for directing the edges $i$ and $i'$ (i.e., both according to the black arrows or the white arrows), and $F_1(3)$ for sequences of three trees that can be attached to the vertices. At this stage, the three vertices are distinguishable from each other, and therefore we count \emph{sequences} of three trees. The same will be true for all other patterns. \item $\zb_{22} = (n-3) \cdot (n-4) \cdot 2 \cdot (n-3) \cdot 2 \cdot F_1(4) = (n-3)^2 (n-4) 2^n n^{n-5}$. \\ Here, the factors $(n-3)$, $(n-4)$, and~2 are the same as in the previous case, an additional factor $(n-3)$ is for choosing label $a$, an additional factor~2 is for directing the edge $a$, and $F_1(4)$ is for sequences of four trees that can be attached to the vertices. \item $\zc = \btwo \cdot (n-5) \cdot 4 \cdot 2 \cdot 4 \cdot F_1(6) = 3 (n-3) (n-4) (n-5) 2^{n-1} n^{n-7}$. \\ Here, the factor $\btwo$ is for choosing the repeated labels, $(n-5)$ is for choosing edge $a$, a factor~4 is for choosing which edge among $i$, $i'$, $j$, $j'$ is attached to the head of edge $a$, and, once this choice is made, a factor~2 is for choosing which of the complementary label is attached to the tail of $a$ (e.g., if the first choice is $i$, then the second choice can be only $j$ or $j'$), an additional factor~4 is for directing $i, i'$ and $j, j'$, and $F_1(6)$ is for sequences of six trees that can be attached to the vertices. \item $\zd = \btwo \cdot 4 \cdot F_2(5) \cdot 9 = 9 (n-3) (n-4) 2^{n-4} n^{n-5}$. \\ Here, the factors $\btwo$ and~4 are as in the previous case. The factor~$3\cdot 3=9$ stands for choosing the pair of vertices through which the components are connected: one vertex is chosen on each component. The factor $F_2(5)$ is for sequences of five trees that can be attached to the vertices (one of which connects the components of the configuration). \item $\ze = (n-3) \cdot (n-4) \cdot (n-5) \cdot 8 \cdot F_2(6) \cdot 12 = 3 (n-3) (n-4) (n-5) 2^{n-1} n^{n-6}$. \\ As above, we have the factors $(n-3)$, $(n-4)$, and $(n-5)$ for choosing the repeated labels and the edge $a$, a factor~8 for directing for directing $i,i'$, $j,j'$, and $a$. The factor~$3\cdot 4=12$ stands for choosing the pair of vertices through which the components are connected. The factor $F_2(6)$ stands for sequences of six trees that can be attached to the vertices (one of which connects the two components of the configuration). \item $\zf = (n-3) \cdot (n-4) \cdot 2 \cdot 2 \cdot 4 \cdot F_1(5) = 5 (n-3) (n-4) 2^{n-1} n^{n-6}$. \item $\zg = \btwo \cdot (n-5) \cdot (n-6) \cdot 16 \cdot F_2(7) \cdot 16 = (n-3) (n-4) (n-5) (n-6) 2^n n^{n-7}$. \item $\zh = \btwo \cdot (n-5) \cdot 4 \cdot 4 \cdot F_1(6) = 3 (n-3) (n-4) (n-5) 2^{n-2} n^{n-7}$. \item $\zi = \btwo \cdot 4 \cdot 4 \cdot F_1(5) = 5 (n-3) (n-4) 2^{n-2} n^{n-6}$. \item $\zj = (n-3) \cdot (n-4) \cdot (n-5) \cdot 2 \cdot 4 \cdot 4 \cdot F_1(6) = 3 (n-3) (n-4) (n-5) 2^n n^{n-7}$. \item $\zk = (n-3) \cdot (n-4) \cdot (n-5) \cdot 4 \cdot 4 \cdot F_1(6) = 3 (n-3) (n-4) (n-5) 2^{n-1} n^{n-7}$. \item $\zl = (n-3) \cdot (n-4) \cdot (n-5) \cdot 2 \cdot 4 \cdot 4 \cdot F_1(6) = 3 (n-3) (n-4) (n-5) 2^n \cdot n^{n-7}$. \setcounter{mycnt}{\value{enumi}} \end{enumerate} Next, we count occurrences of $\ya_3, \yb_3, \ym, \ldots, \yr$ in directed trees with one triple of repeated labels. \begin{enumerate} \setcounter{enumi}{\value{mycnt}} \item $\za_3 = (n-3) \cdot 3 \cdot 2 \cdot F_1(3) = 9 (n-3) 2^{n-2} n^{n-4}$. \\ Here, the factor $(n-3)$ is for choosing the repeated label ($i$, $i'$, and $i''$), the factor~3 is for choosing two labels from $\{i, i', i''\}$, the factor~2 is for directing these edges, and $F_1(3)$ is for sequences of three trees attached to the vertices. \item $\zb_3 = (n-3) \cdot 3 \cdot (n-4) \cdot 2 \cdot 2 \cdot F_1(4) = 3 (n-3)^2 2^n n^{n-5}$. \\ Here, we have the factors $(n-3)$ and~3 as in the previous case, an additional factor $(n-4)$ for choosing the edge $a$ (which is not a repetition of $i$), a factor~2 for directing the edges $i$ and $i'$, an additional factor~2 for choosing which edge with repeated label is attached to the head of edge $a$, and $F_1(4)$ for sequences of four trees attached to the vertices. \item $\zm = (n-3) \cdot 2 \cdot F_1(4) = (n-3) 2^{n-1} n^{n-5}$. \item $\zn = (n-3) \cdot 3 \cdot 2 \cdot F_1(4) = 3 (n-3) 2^{n-1} n^{n-5}$. \\ As above, the factor $(n-3)$ is for choosing the repeated label ($i$, $i'$, and $i''$), the factor~3 is for choosing which of these labels is found between the two others, the factor~2 is for directing these edges, and $F_1(4)$ is for sequences of four trees attached to the vertices. \item $\zo = (n-3) \cdot (n-4) \cdot 2 \cdot 3 \cdot 2 \cdot F_1(5) = 15 (n-3) (n-4) 2^{n-3} n^{n-6}$. \\ As in previous cases, the factor $(n-3)$ is for choosing the repeated label ($i$, $i'$, and $i''$), $(n-4)$ is for choosing the edge $a$, the factor~2 is for choosing whether one or two edges with repeated labels are attached to the head of $a$, the factor~3 is for choosing which edge (or edges, depending on the previous choice) among $i, i', i''$ is (resp., are) attached to the head of $a$, the factor~2 is for directing the edges $i, i', i''$, and $F_1(5)$ is for sequences of five trees attached to the vertices. \item $\zp = (n-3) \cdot (n-4) \cdot 2 \cdot 3 \cdot 2 \cdot 2 \cdot F_1(5) = 15 (n-3) (n-4) 2^{n-2} n^{n-6}$. \item $\zq = (n-3) \cdot 3 \cdot (n-4) \cdot (n-5) \cdot 2 \cdot 4 \cdot F_1(6) = 9 (n-3) (n-4) (n-5) 2^{n-2} n^{n-7}$. \item $\zr = (n-3) \cdot 3 \cdot (n-4) \cdot (n-5) \cdot 2 \cdot 4 \cdot F_1(6) = 9 (n-3) (n-4) (n-5) 2^{n-2} n^{n-7}$. \end{enumerate} Armed with these formulae, we can now count the various possible types of polycubes of size $n$ that are proper in $n-3$ dimensions. % ---------------------------------------------------------------------------- % Polycubes with a Tree Structure % =============================== \section{Polycubes with a Tree Structure} We split the counting according to the combinations of repeated labels in the tree. \paragraph{Two pairs of repeated labels.} Denote by~$\zx_{22}$ the number of polycubes $P \in \mathcal{P}_n$, such that $\gamma(P)$ is a tree that has two pairs of repeated labels. By Corollary~\ref{the:t}.1, the total number of directed trees with $n$ vertices and directed labeled edges, with two pairs of repeated labels, is $\zt_{22} = \btwo 2^{n-1} n^{n-3}$. Such a tree corresponds to a tree-like polycube in $\mathcal{P}_n$ unless it contains a subtree of type $\ya, \ldots, \yj$. Thus, subtrees of types $\ya$, $\yb$, or $\yc$ are all that we need to exclude. However, each of $\yd, \ldots, \yj$ includes \emph{two} subtrees of the type $\ya$, $\yb$, or $\yc$, and these are counted twice in the sum $\za_{22} + \zb_{22} + \zc$. Therefore, the number of trees which do not lead to tree-like polycubes is $$ \za_{22} + \zb_{22} + \zc - \zd - \ze - \zf - \zg - \zh - \zi - \zj $$ (Each of the patterns $\yk$ and $\yl$ contains exactly one subtree of type $\ya$, $\yb$, or $\yc$,\footnote{ In fact, the pattern $\yc$ is contained in no other distinguished structure. } and hence, they are correctly accounted for.) Dividing by 4 (since each such polycube is represented by four trees), we obtain that \begin{align} \nonumber \zx_{22} & = \left( \zt_{22} - \za_{22} - \zb_{22} - \zc + \zd + \ze + \zf + \zg + \zh + \zi + \zj \right) / 4 \\ \label{eq:x0-22} & = 2^{n-6} n^{n-7} (n-3) (n-4) (4 n^4 - 28 n^3 + 97 n^2 - 200 n + 300). \end{align} \paragraph{One triple of repeated labels.} Denote by~$\zx_3$ the number of polycubes $P \in \mathcal{P}_n$, such that $\gamma(P)$ is a tree that has one triple of repeated labels. By Corollary~\ref{the:t}.2, the total number of directed trees with $n$ vertices and directed labeled edges, with one triple of repeated labels, is $\zt_3 = (n-3) 2^{n-1} n^{n-3}$. Such a tree corresponds to a polycube in $\mathcal{P}_n$ unless it has a subtree of type either $\ya$ or $\yb$. In addition, all of $\ym, \ldots, \yr$ include (at least) two subtrees of the types $\ya$ or $\yb$. The types $\ym$ and $\yo$ even include three subtrees of the types $\ya$ or $\yb$. Therefore, by applying the inclusion-exclusion principle, and dividing by~6 (since each such polycube is represented by six trees), we obtain that \begin{align} \nonumber \zx_3 & = \left( \zt_3 - (\za_3 + \zb_3) + (3\zm + \zn + 3\zo + \zp + \zq + \zr) - (\zm + \zo) \right) / 6 \\ \label{eq:x0-3} & = 2^{n-3} n^{n-7} (n-3) (2 n^4 - 21 n^3 + 106 n^2 - 282 n + 360) / 3. \end{align} In total, we have $$ \zx = \zx_{22} + \zx_3. $$ % ---------------------------------------------------------------------------- % Polycubes with One Cycle % ======================== \section{Polycubes with One Cycle} As mentioned above, if $\gamma(P)$ has only one cycle, then the length of this cycle must be either~4 or~6. Assume first that $\gamma(P)$ has one 4-cycle whose edges are labeled $i, j, i, j$. Then, either $\gamma(P)$ has another edge with the label $i$ or $j$, or it has no such edge; in the latter case $\gamma(P)$ has another pair of edges with a repeated label which is distinct from $i$ and $j$. Denote, therefore, the number of polycubes of the former type by~$\zy_{23}$, and the latter type by~$\zy_{222}$. Each graph of the first type has two spanning trees with two pairs of repeated edge labels and two spanning trees with a triple of repeated edge labels. Each graph of the second type has four spanning trees with two pairs of repeated edge labels. Denote by $\zt^1_{22}$ the total number of spanning trees of these graphs (of both types), which have two pairs of repeated labels, and by $\zt^1_3$ the number of spanning trees of these graphs (necessarily of the first type), which have one triple of repeated labels. Then, we have \begin{equation} \label{eq:syst} \zt^1_{22} = 4 (2 \zy_{23} + 4 \zy_{222}) \quad \mathrm{and} \quad \zt^1_3 = 6 (2 \zy_{23}). \end{equation} \paragraph{Spanning trees with two pairs of repeated labels.} All these spanning trees have a single occurrence of $\yb$ as a subtree. Thus, the number of occurrences of $\yb$ in all such trees is $\zb_{22}$. From this number we have to subtract the number of occurrences of the forbidden subtrees $\ye$, $\yf$, and $\yi$; the number of spanning trees of graphs that have two edge-disjoint 4-cycles (that is, $\yg$); and also the number of spanning trees (with two pairs of repeated labels) of graphs that have two 4-cycles with a common edge (that is, $\yh$, $\yj$, $\yk$, and $\yl$). Notice that in $\zb_{22}$, trees with $\yi$, $\yg$, $\yh$, or $\yj$ are counted twice. Therefore, \begin{align} \nonumber \zt^1_{22} & = \zb_{22} - \ze - \zf - 2\zi - 2\zg - 2\zh - 2\zj - \zk - \zl \\ \label{eq:x1-22} & = 2^{n-1} n^{n-6} (n-3) (n-4) (2 n^2 - 13 n + 25). \end{align} \paragraph{Spanning trees with one triple of repeated labels.} In this case, possible spanning trees have a subtree $\yb$ (recall that $a$ is neither $i$, $i'$, nor $i''$). The number of occurrences of $\yb$ in all such trees is $\zb_3$. From this number we have to subtract the number of occurrences of the forbidden subtrees $\yo$ and $\yp$, and the number of spanning trees (with a triple of repeated labels) of graphs that have two 4-cycles with a common edge (that is, $\yq$ and $\yr$). Note that in $\zb_{3}$, trees with $\yo$, $\yq$, or $\yr$ are counted twice. Therefore, \begin{align} \nonumber \zt^1_3 & = \zb_3 - 2\zo - \zp - 2\zq - 2\zr \\ \label{eq:x1-3} & = 3 \cdot 2^{n-1} n^{n-7} (n-3) (n-4) (2 n^2 - 11 n + 30). \end{align} By solving the system~(\ref{eq:syst}--\ref{eq:x1-3}), we obtain \begin{align*} \zy_{23} & = 2^{n-3} n^{n-7} (n-3) (n-4) (2n^2 - 11n + 30), \\ \zy_{222}& = 2^{n-5} n^{n-7} (n-3) (n-4) (n-5) (2n^2 - 7n + 12). \end{align*} \paragraph{Polycubes with a 6-cycle.} Denote the number of polycubes in $\mathcal{P}_n$ that have only one cycle of length~6 by~$\zy_{\varhexagon}$. We have $$ \zy_{\varhexagon} = \binom{n-3}{3} \cdot 4 \cdot F_1(6) = 2^{n-4} n^{n-7} (n-3) (n-4) (n-5). $$ In order to establish this quantity, we do not need to consider spanning trees. Notice that the cells of a 6-cycle always form a $2 \times 2 \times 2$ cube with two opposite cells removed, as in $\includegraphics[width=10mm]{cube_rec_}$. Thus, $\binom{n-3}{3}$ counts the dimensions in which the cube lies, the factor~4 counts ways to remove two reciprocal cells, and $F_1(6)$ counts ways to attach six trees to the remaining six cells. In total, we have $\zy = \zy_{23} + \zy_{222} + \zy_{\varhexagon}.$ % ---------------------------------------------------------------------------- % Polycubes with Two Cycles % ========================= \section{Polycubes with Two Cycles} Again, we do not consider spanning trees. \paragraph{Two 4-cycles without a common edge.} The number of polycubes $P \in \mathcal{P}_n$, such that $\gamma(P)$ has two 4-cycles without a common edge, is $$ \zz_{\, \includegraphics[width=7mm]{two_cycles_1}} = \frac{1}{2} \cdot \binom{n-3}{2} \cdot \binom{n-5}{2} \cdot 16 \cdot F_2(7) = 2^{n-6} n^{n-7} (n-3) (n-4) (n-5) (n-6). $$ In this case, $\frac{1}{2} \binom{n-3}{2} \binom{n-5}{2}$ is the number of ways to choose the dimensions in which the ``squares'' lie (note that these pairs of dimensions are disjoint, otherwise $\gamma(P)$ would have a spanning tree with four repeated labels). The factor $4\cdot 4=16$ is the number of ways to choose a pair of vertices through which the squares will be connected, and $F_2(7)$ is the number of ways to connect them by trees. \paragraph{Two 4-cycles with a common edge.} The number of polycubes $P \in \mathcal{P}_n$, such that $\gamma(P)$ has two 4-cycles with a common edge, is $$ \zz_{\, \includegraphics[height=2.5mm]{two_cycles_2}} = \binom{n-3}{3} \cdot 12 \cdot F_1(6) = 3 \cdot 2^{n-4} n^{n-7} (n-3) (n-4) (n-5). $$ The cells of two 4-cycles with a common edge form a $2 \times 2 \times 2$ cube with two adjacent cells removed, as in $\includegraphics[width=10mm]{cube_adj}$. Thus, $\binom{n-3}{3}$ counts the dimensions in which the cube lies. There are 12 ways to remove two adjacent cells, and there are $F_1(6)$ ways to attach six trees to the remaining six cells. In total, we have $\zz = \zz_{\, \includegraphics[height=2.5mm]{two_cycles_1}} + \zz_{\, \includegraphics[height=2.5mm]{two_cycles_2}}.$ % ---------------------------------------------------------------------------- % Epilogue % ======== \section{Epilogue} Finally, we have {\small \begin{align*} \DX(n,n-3) & = \zx + \zy + \zz \\ & = \zx_{22} + \zx_{3} + \zy_{23} + \zy_{222} + \zy_{\varhexagon} + \zz_{\, \includegraphics[height=2.5mm]{two_cycles_1}} + \zz_{\, \includegraphics[height=2.5mm]{two_cycles_2}} \\ & = 2^{n-6} n^{n-7} (n-3) (n-4) (4n^4-28n^3+97n^2-200n+300) \\ & \qquad + 2^{n-3} n^{n-7} (n-3) (2n^4-21n^3+106n^2-282n+360)/3 \\ & \qquad + 2^{n-3} n^{n-7} (n-3) (n-4) (2n^2-11n+30) \\ & \qquad + 2^{n-5} n^{n-7} (n-3) (n-4) (n-5) (2n^2-7n+12) \\ & \qquad + 2^{n-4} n^{n-7} (n-3) (n-4) (n-5) \\ & \qquad + 2^{n-6} n^{n-7} (n-3) (n-4) (n-5) (n-6) \\ & \qquad + 3 \cdot 2^{n-4} n^{n-7} (n-3) (n-4) (n-5) \\ & = 2^{n-6} n^{n-7} (n-3) (12 n^5 - 104 n^4 + 360 n^3 - 679 n^2 + 1122 n - 1560) / 3, \end{align*} } which completes the proof of Theorem~\ref{th:main}. % ---------------------------------------------------------------------------- % Conclusion % ========== \section{Conclusion} In this paper we provide a rigorous proof of the formula enumerating $n$-cell polycubes proper in $n-3$ dimensions, that is, $\DX(n,n-3)$. The proof is based on the same method as in the proof of $\DX(n,n-2)$~\cite{BBR10}, but is significantly more involved. This reveals the difficulties expected with the general case, $\DX(n,n-k)$: The number of distinguished structures will grow rapidly, the inclusion relations between them will be much more complicated, and the ways in which they will be connected by forests will be much more varied. This will yield a large number of terms in the inclusion-exclusion analysis. Therefore, we believe that a complete manual analysis will not be feasible for the cases $k>3$. Peard and Gaunt~\cite[p.~6113, eq.~(2.15)]{PG95} predicted that the diagonal formula $\DX(n,n-k)$ has the pattern $2^{n-2k+1} \, n^{n-2k-1} \, g_k(n)$, where $g_k(n)$ is a polynomial in $n$. In fact, $k$ has to be a root of $g_k(n)$ since $\DX(n,0)=0$ for $n>1$. Therefore, the expected form is $2^{n-2k+1} n^{n-2k-1} (n-k) h_k(n)$, where $h_k(n)$ is a polynomial in $n$. Luther and Mertens~\cite{LM11} provide the explicit polynomials $h_k(n)$ for $1 \leq k \leq 7$. Careful inspection of these polynomials reveals that the leading coefficient of $h_k(n)$ has the form $2^{k-1} / (k-1)!$. In conclusion, our refined conjecture is that $$ \DX(n,n-k) = \frac{2^{n-k} n^{n-2k-1} (n-k)}{(k-1)!} P_k(n), $$ where $P_k(n)$ is a \emph{monic} polynomial in $n$. It has also been conjectured~\cite{BBR10,LM11} that the degree of $P_k(n)$ is $3k-4$. One can attempt to prove this pattern for the general case of $k$ without actually writing down all the expressions (respective of the cases in our method), but rather by showing that one of them (containing the dominant term, that is, having the highest degree of $n$) has the form $2^n n^{n-2k-1} (n-k)$ times a polynomial in $n$ of degree $3k-4$, and that all the other expressions have the same form multiplied by polynomials of at most the same degree. Then, the polynomial $P_k(n)$, and thus, $\DX(n,n-k)$, can be interpolated from any $3k-3$ known values of $\DX(n,n-k)$. Recently, Luther and Mertens~\cite{LM11} provided an argument supporting this hypothesis. They showed that the highest-degree term in $\DX(n,n-k)$ is of the order $2^n n^{n+k-4}$. They also demonstrated (using a ``physical argument'') that, in fact, only $k+1$ known values suffice for recovering the formulae of $P_k(n)$ and $\DX(n,n-k)$. We believe that the argument of Luther and Mertens can be refined as follows. The dominant term in $\DX(n,n-k)$ should correspond to the case in which $\gamma(P)$ is a tree (our $\zx$). More precisely, it should correspond to the subcase in which all the repeated labels appear in pairs (our $\zx_{22}$), that is, when there are $(n-1)-(n-k)=(k-1)$ pairs of repeated labels. Denote the corresponding term by $\zx_{22\dots2}$. In its turn, the dominant term of $\zx_{22\dots2}$ (denote it by $\zt_{22\dots 2}$) should correspond to our $\zt_{22}$: All the terms added or subtracted in the calculation of $\zx_{22\dots 2}$ will have lower order. Note that the use of Lemma~\ref{the:old_lemma} will remain unchanged. The statement corresponding to Corollary~\ref{the:t}.1 will then be $$ \zt_{22\dots 2} = \binom{n-k}{k-1} 2^{n-1} n^{n-3} = \frac{2^{n-1} n^{n-3}}{(k-1)!} (n^{k-1} + \cdots). $$ Finally, we need to divide this expression by $2^{k-1}$, the number of trees that represent each polycube in this case (cf.\ the factor $1/4$ in Eq.~\eqref{eq:x0-22}). Thus, the order of the dominant term is indeed $2^n n^{n+k-4}$, and the {constant} in this term is $\frac{1}{2^k (k-1)!}$. Our next attempt will, thus, be to implement a computer program which will automatically generate, for a given value of $k$, all the ``distinguished structures'' and all the ways they can be attached to form trees, and will compute the inclusion-exclusion formula for $\DX(n,n-k)$. % ---------------------------------------------------------------------------- % Bibliography % ============ \begin{thebibliography}{99} \bibitem{BMRR06} G. Barequet, M. Moffie, A. Rib\'{o}, and G. Rote, Counting polyominoes on twisted cylinders, \emph{Integers} \textbf{6}~(2006), \#A22, \newline \url{http://www.emis.de/journals/INTEGERS/papers/g22/g22.pdf}~. \bibitem{BBR10} R. Barequet, G. Barequet, and G. Rote, Formulae and growth rates of high-dimensional polycubes, \emph{Combinatorica} \textbf{30}~(2010), 257--275. \bibitem{BH57} S.~R. Broadbent and J.~M. Hammersley, Percolation processes: I. Crystals and mazes, \emph{Math.\ Proc.\ Cambridge Philos.\ Soc.} \textbf{53}~(1957), 629--641. \bibitem{GP00} D.~S. Gaunt and P.~J. Peard, $1/d$-expansions for the free energy of weakly embedded site animal models of branched polymers, \emph{J. Phys.\ A} \textbf{33}~(2000), 7515--7539. \bibitem{Kl67} D.~A. Klarner, Cell growth problems, \emph{Canad.\ J. Math.} \textbf{19}~(1967), 851--863. \bibitem{KR73} D.~A. Klarner and R.~L. Rivest, A procedure for improving the upper bound for the number of $n$-ominoes, \emph{Canad.\ J. Math.} \textbf{25}~(1973), 585--602. \bibitem{Lu75} W.~F. Lunnon, Counting multidimensional polyominoes, \emph{Computer J.} \textbf{18}~(1975), 366--367. \bibitem{LM11} S. Luther and S. Mertens, Counting lattice animals in high dimensions, \emph{J. Stat.\ Mech.\ Theory Exp.} \textbf{9}~(2011), 546--565. \bibitem{Ma99} N. Madras, A pattern theorem for lattice clusters, \emph{Ann.\ Comb.} \textbf{3}~(1999), 357--384. \bibitem{oeis} \emph{The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}~. \bibitem{PG95} P.~J. Peard and D.~S. Gaunt, $1/d$-expansions for the free energy of lattice animal models of a self-interacting branched polymer, \emph{J. Phys.\ A} \textbf{28}~(1995), 6109--6124. \bibitem{St} R. Stanley, \emph{Enumerative Combinatorics}, Vol.~2, Cambridge University Press, 1999. \end{thebibliography} % ---------------------------------------------------------------------------- % Paper data % ========== \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05B50; % Polyominoes Secondary 05A15, % Exact enumeration problems, generating functions 05A16, % Asymptotic enumeration 05C30. % Enumeration of graphs and maps \noindent \emph{Keywords:} Lattice animals, polyominoes, directed trees. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A127670}, \seqnum{A171860}, and \seqnum{A191092}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 6 2012; revised version received October 1 2012. Published in {\it Journal of Integer Sequences}, October 2 2012. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}