\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}