The Perimeter of Proper Polycubes

Sebastian Luther Institut für Theoretische Physik

Otto-von-Guericke Universität Magdeburg

Postfach 4120 39016 Magdeburg Germany

  SebastianLuther@gmx.de

Stephan Mertens Institut für Theoretische Physik

Otto-von-Guericke Universität Magdeburg

Postfach 4120 39016 Magdeburg Germany and Santa Fe Institute 1399 Hyde Park Rd. Santa Fe, NM 87501 USA

      mertens@ovgu.de

Abstract

We derive formulas for the number of polycubes of size n and perimeter t that are proper in n − 1 and n − 2 dimensions. These formulas complement computer based enumerations of perimeter polynomials in percolation problems. We demonstrate this by computing the perimeter polynomial for n = 12 in arbitrary dimension d.

1 Introduction

A d-dimensional polycube of size n is a set of face-connected cells in the lattice ℤ^{d}. Two fixed polycubes are considered equivalent if one can be transformed into the other by translation. Figure 1 shows all 3-dimensional fixed polycubes of size 4. Polycubes are a classical topic in recreational mathematics and combinatorics [10]. In statistical physics and percolation theory, polycubes are called lattice animals [11, 19].

\begin{matrix}t = 18(2) \\ t = 17(9) \\ t = 16(8) \\ t = 16(8) \\ t = 16(8) \\ t = 15(15) \\ t = 16(16) \end{matrix}

Figure 1: Polycubes of size n = 4 in d = 3 dimensions and their perimeter t. The leftmost polycube is proper in 1 dimension, the two rightmost polycubes are proper in 3 dimensions. All other polycubes are proper in 2 dimensions. Numbers in parentheses denote the perimeter of the polycube embedded in its proper dimension.

Let A_{d}(n) denote the number of fixed polycubes of size n in dimension d. The On-Line Encyclopedia of Integer Sequences [18] contains several sequences A_{d}(n), like A_{3}(n) \underline{A001931}, A_{4}(n) \underline{A151830}, A_{5}(n) \underline{A151831}, …, A_{9}(n) \underline{A151835}.

Some polycubes that contribute to A_{d}(n) span less than d dimensions. A polycube that spans i dimensions is called proper in i dimensions. See Figure 1 for examples. Following Lunnon [13], we denote the number of fixed polycubes of size n that are proper in dimension i by DX(n, i). A polycube of size n can span at most n − 1 dimensions. The sequences DX(n, n − 1) \underline{A127670}, DX(n, n − 2) \underline{A171860} and DX(n, n − 3) \underline{A191092} are also part of the On-Line Encyclopedia of Integer Sequences [18].

Since each polycube that lives in ℤ^{d} is proper in some dimension ≤ d, we have

A_{d}(n) = ∑_{i=1}^{n−1} \binom{d}{i} DX(n, i) ,  (1)

a classical formula due to Lunnon [13]. The binomial factor reflects the fact that we can choose the i dimensions of a proper polycube from the d dimensions of the host lattice. Note that for given n, (1) allows us to easily compute A_{d}(n) for any value of d provided we know the numbers DX(n, i) for all i < n.

In percolation theory [19] we are interested in counting fixed polycubes of a given size n according to their perimeter t, i.e., to the number of adjacent cells that are empty (see again Figure 1). If each cell of the lattice is occupied independently with probability p, the average number of occupied clusters of size n per lattice site reads

∑_{t} g_{n,t}^{(d)}p^{n}(1 − p)^{t} ,  (2)

where g_{n,t}^{(d)} denotes the number of fixed d-dimensional polycubes of size n and perimeter t. The g’s define the perimeter polynomials

P_{n}^{(d)}(q) = ∑_{t} g_{n,t}^{(d)}q^{t} .  (3)

The perimeter polynomials comprise a considerable amount of information about the percolation problem in ℤ^{d}. The total number of fixed polycubes of size n can be computed from the perimeter polynomial as A_{d}(n) = P_{n}^{(d)}(1). In fact, one can compute A_{d}(n + 1) from the perimeter polynomials up to size n [14, Eq. (7)]. Hence, in terms of enumerations it is more efficient to enumerate the perimeter polynomials even if one is only interested in the total number of poycubes A_{d}(n). Note also that in two and three dimensions, one can derive explicit formulas for g_{n,2n+2−k}^{(2)} [2] and g_{n,4n+2−k}^{(3)} [3] for k = 0, 1, 2, 3, i.e., for lattice animals for which the perimeter deviates by k from the maximum possible value.

Again, we can distinguish between general and proper polycubes. Let G_{n,t}^{(i)} denote the number of fixed polycubes of size n and that are proper in dimension i and that have perimeter t in ℤ^{i}. We then have

g_{n,t}^{(d)} = ∑_{i=1}^{n−1} \binom{d}{i} G_{n,t−2(d−i)n}^{(i)} ,  (4)

as an analogy to Lunnon’s formula (1). We also have

DX(n, i) = ∑_{t} G_{n,t}^{(i)} .  (5)

Equation (4) tells us that for given n and t, g_{n,t}^{(d)} is a polynomial in d of degree n − 1. We can compute this polynomial if we know the numbers G_{n,t}^{(1)}, …, G_{n,t}^{(n−1)}. For n = 4, for example, one can enumerate the proper polycubes with pencil and paper to get

G_{4,2}^{(1)} = 1 G_{4,8}^{(2)} = 9 G_{4,9}^{(2)} = 8 G_{4,15}^{(3)} = 8 G_{4,16}^{(3)} = 24 ,

and G_{4,t}^{(i)} = 0 for all other values of i and t. With these numbers, (4) then yields

g_{4,t}^{(d)} = dδ_{t,8d−6} + \frac{d(d − 1)}{2} [9δ_{t,8d−8} + 8δ_{t,8d−7}] + \frac{d(d − 1)(d − 2)}{3} [9δ_{t,8d−9} + 8δ_{t,8d−8}] ,

where δ_{x,y} is the usual Kronecker delta.

The numbers G_{n,t}^{(i)} can be found by enumerating polycubes on a computer. Computer based enumerations of polycubes have a long tradition in computer science and in statistical physics, see Luther and Mertens [14] and references therein. This approach, however, is limited by the exponential growth of the number of proper polycubes with n. The hardest problems in terms of exhaustive enumeration are the “diagonal” and “sub-diagonal” numbers G_{n,t}^{(n−1)} and G_{n,t}^{(n−2)}, but it turns out that one can compute these numbers using combinatorial arguments instead of exhaustive enumerations. This is the main result of this paper.

We start by reviewing the link between proper polycubes and edge-labeled trees. In Section 3 we demonstrate how this link can be explored to compute the numbers G_{n,t}^{(n−1)}. The computation of G_{n,t}^{(n−2)} is more involved and requires some preparation. We start by deriving formulas for the perimeter of polycubes that correspond to certain classes of edgelabeled trees in Section 4. Then we introduce a sort of Prüfer code for edge-labeled trees (Section 5) that finally allows us to compute the number of edge-labeled trees that enter the computation of G_{n,t}^{(n−2)}. In Section 7 we demonstrate how the combinatorial arguments complement exhaustive enumerations by computing the perimeter polynomial P_{12}^{(d)}(q) for arbitrary dimension d.

2 Proper polycubes and tainted trees

A polycube of size n can barely span n − 1 dimensions. In particular, in a polycube that contributes to DX(n, n − 1), every pair of adjacent cells must span a new dimension. There can not be any loops. Apparently, the computation of DX(n, n−1) is an exercise in counting trees. Let us work out that exercise.

Consider the adjacency graph of a polycube, i.e, the graph in which each vertex represents a cell of the polycube and two vertices are connected if the corresponding cells are neighbors in the polycube. The edges of this graph are labeled with the dimension along which the two cells touch each other.

In the case DX(n, n − 1) every edge in the adjacency graph has a unique label that corresponds to one of the n − 1 dimensions. Hence, the adjacency graph has exactly n − 1 edges, i.e., it is an edge labeled tree. And since there are two possible directions for each dimension, we get

DX(n, n − 1) = 2^{n−1} · number of edge-labeled trees of size n.

The number of vertex labeled trees of size n is given by n^{n−2}, the famous formula published by Cayley in 1889 [8]. The number of edge labeled trees is smaller by a factor n, i.e., it is n^{n−3}. The earliest reference for a proof we could find is from 1995 [7], but the formula seems to have been known for much longer. We will give another proof in Section 5. Anyway, the number of proper polycubes of size n in dimension n − 1 reads

DX(n, n − 1) = 2^{n−1} n^{n−3} .  (6)

This formula has been known and used in the statistical physics community for a long time[9], but a formal proof has been published only recently [5].

The computation of DX(n, n − k) for k > 1 is more complicated because the correspondence between proper polycubes and edge-labeled trees gets more involved. For k > 1, the adjacency graph of a proper polycube can have loops, i.e., it is represented by more than one spanning tree. On the other hand, some labeled spanning trees represent impossible polycubes with overlapping cells. Yet a careful consideration of all these cases has yielded the formulas for DX(n, n − 2) [5] and DX(n, n − 3) [1]. Recently, Barequet and Shalah [4] proved the formulas for DX(n, n−4) and DX(n, n−5). Using non-rigorous arguments, DX(n, n−k) has been computed up to k = 7 [14]. In this contribution we will show how combinatorial arguments can be used to compute G_{n,t}^{(n−1)} and G_{n,t}^{(n−2)}.

3 Computation of G_{n,t}^{(n−1)}

For G_{n,t}^{(n−1)} we need to know the perimeter of a polycube represented by a given tree. It turns out that the perimeter is determined by the degree sequence δ = (δ_{1}, …, δ_{n}) of the tree, not to be mixed up with the double indexed Kronecker delta δ_{x,y}:

Theorem 1. Let δ = (δ_{1}, …, δ_{n}) denote the degree sequence of the adjacency graph of a proper n-cell polycube in (n − 1) dimensions. The perimeter t_{1} of the polycube depends only on n and δ and it is given by

t_{1}(δ) = (2n − 1)(n − 1) − \frac{1}{2} ∑_{i=1}^{n} δ_{i}^{2} .  (7)

Proof. If we ignore the fact that some perimeter sites can be shared by several cells of the polycube, the perimeter of an n-cell polycube in d dimensions would be

t_{n,d}^{⋆} = ∑_{i=1}^{n}(2d − δ_{i}) = 2dn − 2(n − 1) .  (8)

Now consider a cell of the polycube with degree δ_{i} > 1. If the polycube is proper in (n − 1) dimensions, each pair of adjacent cells spans a fresh two dimensional plane. The perimeter site that sits in the corner of that plane is shared by two cells of the polycube, and these are the only perimeter sites have been over counted in t_{n,n−1}^{⋆}. The true perimeter then reads

t_{1}(δ) = t_{n,n−1}^{⋆} − ∑_{i=1}^{n} \binom{δ_{i}}{2} = (2n − 1)(n − 1) − \frac{1}{2} ∑_{i=1}^{n} δ_{i}^{2} .

We also need the number of edge-labeled trees with a given degree sequence. This number is given by

T (δ) = \frac{1}{n} · (α_{1}(δ), …, α_{n−1}(δ))! · (δ_{1} − 1, …, δ_{n} − 1)!  (9)

where δ represents an ordered degree sequence and α_{k}(δ) denotes the number of vertices with degree k. The notation (n_{1}, …, n_{k})! refers to the multinomial coefficient

(n_{1}, n_{2}, …, n_{k})! = \frac{(n_{1} + n_{2} + ⋯ + n_{k})!}{n_{1}! n_{2}! ⋯ n_{k}!} for all n_{i} ≥ 0.  (10)

For later convenience, we define (n_{1}, …, n_{k})! to be zero if any of the n_{i}’s is negative. Eq. (9) is a well known result (see Cameron [7], for example). We will re-derive it in Section 5.

Equipped with (7) and (9) we can easily compute G_{n,t}^{(n−1)} for all possible values of t by summing over all ordered degree sequences δ = (δ_{1}, …, δ_{n}) of trees of size n:

G_{n,t}^{(n−1)} = ∑_{δ} T (δ) δ_{t,t_{1}(δ)} .  (11)

This leaves us with the problem of how many ordered degree sequences δ there are and how to generate them. The identity ∑ δ_{i} = 2|E| = 2(n − 1) (valid on trees) tells us that the sequences δ − 1 = (δ_{1} − 1, …, δ_{n} − 1) correspond to the integer partitions of n − 2. There is no closed formula for the number of partitions \underline{A000041}, but asymptotically the number of partitions of n scales like [12]

∼ \frac{1}{4n\sqrt{3}} e^{π\sqrt{2n/3}} .  (12)

Despite this (sub-)exponential growth, the number of summands in (11) is much smaller than the number of proper animals. For n = 12, for example, there are only 42 ordered degree sequences, compared to DX(12, 11) = 2^{11} 12^{9} = 10567230160896 proper animals. There are many algorithms to generate all partitions of an integer, see Zoghbi and Stojmenović [20] for a review. The fastest algorithms generate each partition in constant time, simpler algorithms have time complexity O(n) per partition.

In summary, the evaluation of (11) ist much faster than the exhaustive enumeration of proper animals. For example, the computation of G_{12,t}^{(11)} takes only a tiny fraction of a second on a laptop. The equivalent explicit enumeration of lattice animals would take about 25 years of CPU time, see Section 7. A simple Python script that computes G_{n,t}^{(n−1)} can be found on the project webpage [16].

4 Perimeter formulas for G_{n,t}^{(n−2)}

Computing the perimeter values for G_{n,t}^{(n−2)} is a bit more complicated. Again, we represent a polycube by an edge-labeled tree with n nodes and, in this case, n − 2 distinct edge labels. In such a polycube all but one connection between two adjacent cells span a new dimension.

Type Pattern Perimeter and Description

Count

xx \begin{matrix}x \\ x \end{matrix}

t_{xx}(δ) = t_{2}(δ) + 1

Antiparallel orientation of x does not correspond to a legal polycube.

2^{n−3} T_{xx}(δ)

xyx
x yx

t_{xyx}(δ, δ_{a}, δ_{b}) = t_{2}(δ)−(δ_{a}−1)−(δ_{b}−1) Corresponding polycubes have 4 spanning trees.

2^{n−3} T_{xyx}(δ)

xyzx x x yz  t_{xyzx}(δ) = t_{2}(δ) − 1  2^{n−3} T_{xyzx}(δ)

Table 1: Counting polycubes of size n that are proper in n−2 dimensions. The three patterns that lead to over counting and/or a perimeter value that is different form t_{2}(δ). T_{xx}, T_{xyx} and T_{xyzx} denote the number of undirected, edge-labeled trees with the corresponding error patterns. Every tree that does not contain any of these patterns represents exactly 2^{n−2} polycubes with perimeter t_{2}(δ). Note that flipping the direction of both edges with the same label x at the same time yields a polycube that must not be counted since it is only the mirror image in the x-dimension. Hence, the factor 2^{n−2} for the error free case. The factor 2^{n−3} in the error classes arises from the fact that an antiparallel orientation of the x-edge does not correspond to a legal polycube (case xx), and a parallel orientation of the x-edge induces no correction to the default perimeter t_{2}(δ) (cases xyz and xyzx).

In contrast to the previous case there is no longer a one-to-one map between polycubes and edge-labeled trees. We need to take care of the three “error patterns” shown in Table 1.

Consider the case where two adjacent edges of the tree share the same label. We call this configuration xx. If the directions of these edges are antiparallel, the corresponding polycube will have overlapping cells. If their directions are parallel, the polycube is valid but has a larger perimeter than the error-free case.

An n-cell polycube that is proper in n − 2 dimensions can have a loop, in which case it is represented by more than one spanning tree. The loopy polycubes all contain a quadrilateral. The corresponding tree then contains the pattern xyx of adjacent edge labels. Only one fourth of those trees contribute to the number of polycubes, and their perimeter is also special.

Taking into account the patterns xx and xyx is enough to correctly compute DX(n, n−2), but to compute G_{n,t}^{(n−2)} an additional pattern has to be considered: a pattern xyzx of adjacent edges represents exactly one polycube, but its perimeter is different from the perimeter of other trees with the same degree sequence. But let’s start with the most simple, error free case:

Theorem 2. Let δ = (δ_{1}, …, δ_{n}) denote the degree sequence of a directed edge labeled tree with n − 2 distinct edge labels not containing any of the error patterns in Table 1. Then the perimeter of the corresponding polycube is

t_{2}(δ) = (2n^{2} − 5n + 1) − \frac{1}{2} ∑_{i=1}^{n} δ_{i}^{2} .  (13)

Proof. As with t_{1} we start with t_{n,d}^{⋆} and subtract the number of those perimeter cells that are shared by two cells. Since we excluded all error patterns, the two equally-labeled edges are far apart from each other. This means that the tree locally looks like a tree with n − 1 distinct edge labels. Consequently all pairs of cells that are adjacent to a common cell span a fresh two dimensional plane and hence share a perimeter cell:

t_{2}(δ) = t_{n,n−2}^{⋆} − ∑_{i=1}^{n} \binom{δ_{i}}{2} = (2n^{2} − 5n + 1) − \frac{1}{2} ∑_{i=1}^{n} δ_{i}^{2} .

Theorem 3. Let δ = (δ_{1}, …, δ_{n}) denote the degree sequence of a directed edge labeled tree with n − 2 distinct edge labels containing the pattern xx. Then the perimeter of the corresponding polycube is

t_{xx}(δ) = t_{2}(δ) + 1 .  (14)

Proof. The same argument as in Theorem 2 applies to all pairs of edges that are adjacent to a common cell, except the two equally-labeled edges. They do not span a plane but form a one dimensional line, hence we have to add back the perimeter cell that has been inaccurately subtracted in t_{2}(δ).

Theorem 4. Let δ = (δ_{1}, …, δ_{n}) denote the degree sequence of a directed edge labeled tree with n − 2 distinct edge labels containing the pattern xyx. Let δ_{a} and δ_{b} be the degrees of the two vertices that lie at the ends of the path formed by the two equally-labeled edges and the edge separating them. Then the perimeter of the corresponding polycube is

t_{xyx}(δ) = t_{2}(δ) − (δ_{a} − 1) − (δ_{b} − 1) .  (15)

Proof. Polycubes containing a quadrilateral have four spanning trees. To construct a spanning tree for a given polycube, one of the four edges of the quadrilateral has to be removed. The missing edge would connect the cells a and b. Since the edge is missing from the tree there are more pairs of cells that are neighbours than we count in t_{2}. In t_{2} we subtract

\binom{δ_{a}}{2} + \binom{δ_{b}}{2}

pairs of cells, but if the edge were present we would have subtracted

\binom{δ_{a} + 1}{2} + \binom{δ_{b} + 1}{2} .

Unfortunately, this is still not correct, because two of those pairs span the plane of the quadrilateral and must not be subtracted. The correct count isare

\begin{aligned}t_{xyx}(δ) & = t_{2}(δ) + \binom{δ_{a}}{2} + \binom{δ_{b}}{2} − [\binom{δ_{a} + 1}{2} + \binom{δ_{b} + 1}{2} − 2] \\ & = t_{2}(δ) − (δ_{a} − 1) − (δ_{b} − 1) . \end{aligned}

Theorem 5. Let δ = (δ_{1}, …, δ_{n}) denote the degree sequence of a directed edge labeled tree with n − 2 distinct edge labels containing the pattern xyzx. Then the perimeter of the corresponding polycube is

t_{xyzx}(δ) = t_{2}(δ) − 1 .  (16)

Proof. The two end vertices of the path connecting the two equally-labeled, antiparallel edges have two common neighbouring perimeter cells. One of them is accounted for correctly. It is adjacent to the two end points and to another point in the polycube and those are counted three times. On the other hand, it lies in two planes formed by the cells of the pattern xyzx, which means it is subtracted twice. Only the double counting of the other perimeter cell is missed and must be corrected.

5 Prüfer-like bijection for edge-labeled trees

In order to characterize and count the edge-labeled trees with the patterns listed in Table 1, we will use a bijection between edge-labeled trees of size n and sequences of integers 0, …, n− 1 of length n−3, which is very similar to the Prüfer code for vertex labeled trees. En passant we will prove equations (6) and (9). Our exposition of the Prüfer code follows Pikhurko [17]. We explain it here in detail to establish the connection between Prüfer code and error patterns in the next section.

24130 L = (0, 2, 3)  _{v253410 S = (4, 1)}  _{v341025 S = S + (5)}  _{v402513 S = S + (1)}

Figure 2: An example for the Prüfer code for edge-labeled trees. The code for this tree reads C = (1, 5, 1).

Let T be a tree with n vertices and edge labels 0, 1, …, n − 2, and let L be the sorted list of labeled edges that are incident to a leaf. We subdivide the edge n − 2 into two edges by adding a new vertex v. The new edge which lies on the unique path from v to the smallest element in L inherits the old label n − 2. The other new edge gets the new label n − 1. See Fig. 2 for an illustration of this step and the rest of the procedure.

We now construct a sequence S = (s_{1}, s_{2} …) of edge labels. Starting from the empty sequence, repeat the following procedure for each i ∈ L in increasing order. Let i, e_{1}, e_{2}, … denote the path from i to v. Move along this path and stop when you encounter an edge e_{i} ∈ {n − 1, n − 2, s_{1}, s_{2} …}. Append the sequence (e_{i}, e_{i−1}, …, e_{1}) to S.

Note that S always starts with n − 2 and has length n − 2. We form the sequence C(T) from S by removing the first entry n − 2. This is the code for the edge-labeled tree T.

For the reverse construction consider a sequence C of length n − 3 consisting of integers from the set {0, …, n − 1}. We obtain a new sequence S from C by adding a leading n − 2. We define L = (ℓ_{1}, ℓ_{2}, …) as the list of all labels not contained in S, sorted in increasing order ℓ_{1} < ℓ_{2} < . . .. Note that L contains at least two elements. Obviously, an element of S equals n − 2, n − 1 or some previously occurring element of S exactly |L| times. Cutting S before each such element gets us subsequences S_{1}, …, S_{|L|}. Note that each S_{i} begins with n − 1, n − 2 or a label contained in some previous S_{j}, j < i.

We append ℓ_{i} to S_{i} to create the sequence P_{i}. Each P_{i} represents a path from the interior of the tree to one of its leafs, and we will use these paths to assemble the tree.

We start with T being the path consisting of n − 1 and n − 2 adjacent to the vertex v. For i = 1, …, |L| we append the path P_{i} to T along its unique common edge e. Of the two possible ways for doing this, we choose the one for which the path connecting v and ℓ_{i} uses the edge e.

Finally, we remove the vertex v and merge the two edges n − 1 and n − 2 to a single edge with label n − 2.

This concludes the proof that there is a one-to-one correspondence between edge-labeled trees of size n and sequences of length n − 3 in which each element is a number between 0 and n − 1. In particular this proves that the number of edge-labeled trees is n^{n−3} and hence (6).

The connection between the degree sequence δ and the code C is given by the following theorem:

Theorem 6. Let T be an edge-labeled tree of size n with code C and degree sequence δ = (δ_{1}, …, δ_{n}). Then for i = 1, …, n the sequence S = (n − 2, C) contains a label l_{i} exactly δ_{i} − 1 times and vice versa.

Proof. Let v_{i} be a vertex with degree δ_{i}. One of its δ_{i} edges lies in the unique path from v_{i} to the extra vertex v. Let l_{i} be the label of that edge. Then there are exactly δ_{i} − 1 paths that go through v_{i} and l_{i} to reach v. Hence, S contains the label l_{i} exactly δ_{i} − 1 times.

Theorem 6 allows us to derive the number of edge labeled trees with a given degree sequence, i.e., equation (9). See Figure 3 for an example. Note that the numbers in S come in groups of size δ_{i} − 1, and there are (δ_{1} − 1, …, δ_{n} − 1)! different ways to arrange these group elements. This gives the second multinomial coefficient in (9). Next we have to count the number of ways to assign labels to the different groups in S. Note that codes like S = (a, a, b, b, b, c, c, c) and S = (a, a, c, c, c, b, b, b) correspond to the same set of edge-labeled trees. Therefore we must count the number of maps from {1, …, n} to (a, b, c) with b and c being indistinguishable. In general, the number of groups in S of the size d is given by α_{d}. Hence, the number of different label assignments reads (α_{1}, …, α_{n−1})!, which is the first multinomial coefficient in (9). Finally, the factor 1/n takes into account the fact that the first entry in S is fixed to the value n − 2.

\begin{aligned}δ & = (1, 1, 1, 1, 1, 1, 1, 3, 4, 4) \\ α & = (7, 0, 1, 2, 0, 0, 0, 0, 0) \end{aligned}

According to Theorem 6 , the code S must be of the form

S = (a, a, b, b, b, c, c, c) or permutations.

There are (2, 3, 3)! = 560 such arrangements. Assignment of labels: {1, …, 10} ↦ (a, b, c) with b, c indistinguishable. There are (7, 1, 2)! = 10 · 9 · 8/2 = 360 possible assignments.

Figure 3: Example for counting the number of edge-labeled trees with a given degree sequence using the Prüfer code. According to Equation (9) there are 560·360/10 = 20160 edge labeled trees with the given degree sequence δ.

6 Computing G_{n,t}^{(n−2)}

We are now ready to compute the number of edge-labeled trees containing one of the patterns in Table 1 according to their degree sequence. The idea is to express the patterns as restrictions on the Prüfer code C.

First, note that two edges now carry the same label. We still use 0, …, n − 2 for the labels, but with the convention that the label n − 2 is identified with one of the other labels. By taking into account a factor n − 2, we can fix this shared label to be 0.

Let’s start with the pattern xx, i.e., with trees in which two adjacent edges carry the same label. What are the codes C that correspond to trees in which the labels 0 and n − 2 are assigned to adjacent edges? Recall that C contains paths from leaf edges to the edges n − 2 or n − 1 (which also represents the edge n − 2 in the original tree) or to edges already present in C. Hence, 0 and n − 2 are incident if the first appearance of 0 in C is of the form (…, n − 2, 0, …) or (…, n − 1, 0, …). If 0 lies on the very first path (from the smallest leaf to n − 2), the ending edge n − 2 is removed from S, so another possibility is C = (0, …). If 0 is a leaf edge, i.e., 0 ∉ C), then it is the smallest leaf edge and hence the origin of the very first path in C. If 0 and n − 2 are incident, there are no edges for the second path to terminate other than n−2 or n−1. Hence, C = (n−2, …) or C = (n−1, …). In summary, the pattern xx is represented by these five classes of C:

1. C = (n − 2, …), 0 ∉ C,

2. C = (n − 1, …), 0 ∉ C,

3. C = (0, …),

4. C = (…, n − 2, 0, …) for the first occurrence of 0 in C,

5. C = (…, n − 1, 0, …) for the first occurrence of 0 in C.

Let T_{xx,1}(δ) denote the number of edge-labeled trees in class 1. We illustrate the computation of T_{xx,1}(δ) using the example from Figure 3. The first two entries of S must be equal, hence S must be of the form

S = \{ \begin{matrix}(a, a; b, b, b, c, c, c) & with (3, 3)! = 20 arrangements, or \\ (b, b; a, a, b, c, c, c) & with (1, 2, 3)! = 60 arrangements. \end{matrix}

Note that the part left of the semicolon is not to be rearranged and that the vertex in which the edges 0 and n−2 meet has either degree 3 or degree 4. In general, it can have any degree d ≥ 3, and the corresponding number of arrangements is given by

(δ_{1} − 1, …, δ_{n} − 1)! \frac{(d − 2)(d − 1)}{(n − 2)(n − 3)} ,  (17)

where the factor (d − 2)(d − 1)/((n − 2)(n − 3)) takes care of the fact that two edges of some vertex with degree d are no longer taking part in the rearrangements in S.

We also need to count the number of ways to assign labels to the elements of S. The value of the first two entries of S is fixed to n − 2, and the value 0 is not allowed in S. This leaves us with n − 2 possible values to be assigned to the other entries of S. In our example we have

S = \{ \begin{matrix}(a, a; b, b, b, c, c, c) & with 8 · 7/2 = 28 label assignments, \\ (b, b; a, a, b, c, c, c) & with 8 · 7 = 56 assignments. \end{matrix}

In general, the number of label assignments for the class xx, 1 is given by

(α_{1} − 1, α_{2}, …, α_{d} − 1, …, α_{n−1})! = (α_{1}, …, α_{n−1})! \frac{α_{1}α_{d}}{n(n − 1)}  (18)

if d ≥ 3 is the degree of the vertex incident to the two edges with the same label. Combining (17), (18) and (9) and taking into account the factor n − 2 from fixing the shared label to be 0 provides us with

\begin{aligned}T_{xx,1}(δ) & = \frac{(δ_{1} − 1, …, δ_{n} − 1)!}{n − 3} ∑_{d=3}^{n−1}(d − 2)(d − 1) (α_{1} − 1, α_{2}, …, α_{d} − 1, …, α_{n−1})! \\ & = T (δ) \frac{α_{1}}{(n − 1)(n − 3)} ∑_{d=3}^{n−1}(d − 2)(d − 1) α_{d} . \end{aligned} (19)

The second case is similar except for the fact that we need to consider two degrees d and d′. As above, d denotes the degree of the vertex that joins edges 0 and n − 2. The degree d′ denotes the degree of the vertex that connects the edge n − 1 to its first path in S. The number of arrangements of labels in S that is compatible with S = (n − 2, n − 1, …) then reads

(δ_{1} − 1, …, δ_{n} − 1)! · \frac{(d − 1)(d′ − 1)}{(n − 2)(n − 3)} ,  (20)

and the number of label assignments is given by

(α_{1}, …, α_{n−1})! · \frac{α_{1}}{n(n − 1)(n − 2)} · \{ \begin{matrix}α_{d}α_{d′} & if d ≠ d′, \\ α_{d}(α_{d} − 1) & if d = d′. \end{matrix}  (21)

Combining (20) and (21) and using the identity

∑_{d=1}^{n−1}(d − 1)α_{d} = n − 2  (22)

provides us with

T_{xx,2}(δ) = T (δ) \frac{α_{1}}{(n − 1)(n − 2)(n − 3)} [(n − 2)^{2} − ∑_{d=2}^{n−1}(d − 1)^{2}α_{d}] .  (23)

For the third case S = (n − 2, 0, …) we need to consider the two degrees d and d′ of the vertices incident to the edge 0. The number of arrangements in S is again given by (20). We no longer have the constraint 0 ∉ S, hence the number of label assignments is

(α_{1}, …, α_{n−1})! · \frac{1}{n(n − 1)} · \{ \begin{matrix}α_{d}α_{d′} & if d ≠ d′, \\ α_{d}(α_{d} − 1) & if d = d′, \end{matrix}  (24)

which gets us

T_{xx,3}(δ) = T (δ) \frac{1}{(n − 1)(n − 3)} [(n − 2)^{2} − ∑_{d=2}^{n−1}(d − 1)^{2}α_{d}] .  (25)

For the fourth class of xx-patterns we again consider the degrees d and d′ of the vertices incident to the edge with label 0. Let d′ denote the degree of the vertex that is not incident to the edge n − 2. Then 0 appears d′ − 1 times in S. If j denotes the position of the first 0 in S there are

\binom{n − 2 − j}{d′ − 2}

ways to distribute the other 0’s to the right of position j. Now j ≥ 3 (the case j = 2 corresponds to the previous class xx, 3) and the total number of arrangements of the 0’s in S reads

∑_{j=3}^{n−2} \binom{n − 2 − j}{d′ − 2} = ∑_{k=0}^{n−5} \binom{k}{d′ − 2} = \binom{n − 4}{d′ − 1} .  (26)

Besides all the 0’s, we have also two entries n − 2 in S with fixed positions, both with degree d. Hence, the total number of arrangements in S is

(δ_{1} − 1, …, δ_{n} − 1)! · \frac{(d − 1)(d − 2)}{(n − 2)(n − 3)} · \underbrace{\frac{(d′ − 1)! (n − 4 − (d′ − 1))!}{(n − 4)!} · \binom{n − 4}{d′ − 1}}_{=1} .  (27)

The number of label assignments is again given by (24), and combining these counts we get

T_{xx,4}(δ) = T (δ) \frac{n − 1 − α_{1}}{(n − 1)(n − 3)} ∑_{d=3}^{n−1}(d − 1)(d − 2) α_{d} .  (28)

The fifth and final class of the error pattern xx is characterized by the degrees d and d′ of the endpoints of edge 0 and d′′, the degree of the endpoint of edge n − 2 that is not incident to edge n − 2. The argument with the first position of the 0 entry in S works exactly as above and leaves us with

(δ_{1} − 1, …, δ_{n} − 1)! · \frac{(d − 1)(d′′ − 1)}{(n − 2)(n − 3)}  (29)

for the number of arrangements in S. The number of label assignments reads

\frac{(α_{1}, …, α_{n−1})!}{n(n − 1)(n − 2)} · \{ \begin{matrix}α_{d}α_{d′}α_{d′′} & if d, d′, d′′ are pairwise different, \\ α_{d}(α_{d} − 1)α_{d′} & if d = d′′ and d ≠ d′, \\ α_{d}(α_{d} − 1)α_{d′′} & if d = d′ and d ≠ d′′, \\ α_{d′}(α_{d′} − 1)α_{d} & if d′ = d′′ and d′ ≠ d, \\ α_{d}(α_{d} − 1)(α_{d} − 2) & if d = d′ = d′′. \end{matrix}  (30)

Combining these counts provides us with

T_{xx,5}(δ) = T (δ) \frac{n − 2 − α_{1}}{(n − 1)(n − 2)(n − 3)} [(n − 2)^{2} − ∑_{d=2}^{n−1}(d − 1)^{2} α_{d}] .  (31)

Now the total number of edge-labeled trees in this error class is the sum T_{xx} = T_{xx,1} + ⋯ + T_{xx,5}, which yields the surprisingly simple expression

T_{xx}(δ) = (n − 2)T (δ) \frac{∑_{d} \binom{d}{2}α_{d}}{\binom{n−1}{2}} ,  (32)

With the benefit of hindsight, this formula could have been written down without going through all the combinatorial arguments above: (n − 2)T (δ) is the number of edge-labeled trees with n − 2 distinguishable labels, and the other factor is the fraction of all pairs of edges that are incident to a common vertex (with degree d, sum over d).

The reason we went through all the combinatorics to arrive at the simple formula (32) is to demonstrate the principle. It turns out that for T_{xyx} and T_{xyzx}, there are no such simple formulas, and going through the various classes of constraints on C seems to be the only way to compute T_{xyx} and T_{xyzx}. The actual computation is similar in spirit to the computation of T_{xx}, but the number of classes is larger and the corresponding formulas are more complicated. We present the results in Appendices A and B. The corresponding formulas have been implemented in a Python script that computes G_{n,t}^{(n−2)} for given n. This script (and the script for G_{n,t}^{(n−1)}) can be found on the project webpage [16].

7 Application

To compute the perimeter polynomial P_{n}^{(d)}(q) for arbitrary dimension d, it suffices to know the numbers G_{n,t}^{(i)} for i = 1, …, n − 1. Since it is more efficient to enumerate lattice animals without keeping track of their spanning dimension, computer enumerations usually yield g rather than G. But we can compute G from g because (4) can be inverted [6]:

G_{n,t}^{(i)} = ∑_{d=1}^{i}(−1)^{i−d}\binom{i}{d} g_{n,t+2(d−i)n}^{(d)} .  (33)

\begin{matrix}d = & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ n ≤ & 22 & 18 & 15 & 14 & 14 & 13 & 11 & 11 & 11 \end{matrix}

Table 2: Parameters for which enumeration data for g_{n,t}^{(d)} are available [14, 15].

The available enumeration data (Table 2) suffices to compute P_{n}^{(d)}(q) for n ≤ 11. For n = 12, we need additional data for the number of lattice animals of size 12 in dimensions 8, 9, 10 and 11, but thanks to our combinatorial results we need to run exhaustive enumerations only in dimensions 8 and 9. How much computation time does this save us?

For fixed value of n, the number of polycubes to be enumerated grows only polynomially with d, but we are talking about large numbers here. Let

A_{d}(n) = ∑_{t} g_{n,t}^{(d)}  (34)

be the total number of polycubes of size n in dimension d. These numbers are known for all values of d and n ≤ 14 [14]. In particular,

\begin{aligned}\frac{A_{10}(12)}{A_{9}(12)} & = \frac{7 412 808 050 184 625}{2 001 985 304 489 169} ≃ 3.7 \\ \frac{A_{11}(12)}{A_{9}(12)} & = \frac{23 882 895 566 952 721}{2 001 985 304 489 169} ≃ 11.9 . \end{aligned}

Our combinatorial method saves us about 15.6 times the CPU time of the largest enumeration task n = 12 and d = 9. The enumeration algorithm takes about 100 clock cycles to generate a polycube [14], which implies a counting rate of roughly 3 · 10^{7} polycubes per second on a 3 GHz CPU. The enumeration for n = 12 and d = 9 takes 2.12 years on a single CPU, and our combinatorics saves us 33 years of CPU time. In practice, the enumeration is of course parallelized and run on hundreds of CPUs, reducing the wallclock time from “years” to “days.” In this setup, our combinatorics still saves us about one months of computation.

The new (and the previous) data for g_{12,t}^{(d)} and G_{12.t}^{(d)} for d = 8, 9, 10, 11 are available on the project website [16].

What about the perimeter polynomials for n = 13 and arbitrary d? The combinatorics provide the data for d = 12 and d = 11, but we would still need to explicitly enumerate

A_{8}(13) = 13 228 272 325 440 164 (14 years)
A_{9}(13) = 67 341 781 440 810 531 (71 years)
A_{10}(13) = 282 338 750 889 253 800 (298 years)

polycubes. The corresponding estimates of single CPU times are given in parentheses. Note that our combinatorial results here save us about 1073 years (for A_{11}(13)) and 3416 years (for A_{12}(13)) of CPU time, but the remaining enumeration task is still out of reach unless one is willing to devote a substantial number of CPUs and time to accomplish it.

8 Conclusions

We have derived combinatorial methods to compute G_{n,t}^{(n−1)} and G_{n,t}^{(n−2)}, the number of lattice animals of size n and perimeter t that are proper in dimension n−1 or n−2. These methods complement data from exhaustive enumerations. In particular, they replace the hardest enumeration tasks by an evaluation of these formulas, which is much faster. The approach outlined in this paper can be extended to derive formulas for G_{n,t}^{(n−k)} for k > 2, but the complexity increases considerably with k since more and more “error patterns” need to be identified and analysed.

A The case T_{xyz}

For the xyx case we have:

1. C = (1)(n − 2) …, 0 ∉ C, free variables: d_{n−1}

2. C = (1)(n − 1) …, 0 ∉ C, free variables: d_{n−1}

3. C = (1)(1) …, 0 ∉ C, free variables: d_{n−1}

4. C = (1)(0) …, free variables: d_{0}, d_{n−1}

5. C = (1) … (1)(0) …, first 0 at position j, no 0 in the first …, free variables: d_{0}, d_{n−1}

6. C = … (n − 2)(1)(0) …, first 0 at position j, no 0 and 1 in the first …, free variables: d_{0}, d_{n−1}

7. C = … (n − 1)(1)(0) …, first 0 at position j, no 0 and 1 in the first …, free variables: d_{0}, d_{n−2}

8. C = … (n − 2)(1) … (1)(0) …, first 1 at position k, first 0 at position j, no 0 and 1 in the first …, no 0 in the second …, free variables: d_{0}, d_{n−1}

9. C = … (n − 1)(1) … (1)(0) …, first 1 at position k, first 0 at position j, no 0 and 1 in the first …, no 0 in the second …, free variables: d_{0}, d_{n−2}

One thing that is special about the xyx case is that we have to specify the degrees of the two vertices at the end of the path that connects the equally-labeled edges. One of these two vertices is always 0 and the other one is either n − 1 or n − 2. This means we must not sum over the degree of these nodes, but leave their degree as a free argument in the T_{xyx,i} formulas. This is necessary because the perimeter of the corresponding polycube depends on these two degrees, as explained earlier.

To shorten the formulas we introduce the following variables

X_{k}(δ) = ∑_{d=1}^{n−1} d^{k}α_{d} ,  (35)

and we will omit the dependence on δ and just write X_{2}, X_{3}, etc.

\begin{matrix}T_{xyx,1}(δ, d_{n−1}) = & T_{xyx,3}(δ, d_{n−1}) = \frac{T (δ) α_{1}}{(n − 1)(n − 2)(n − 3)(n − 4)}× \\ (4n^{2} − 6n + 2 − X_{2}(n + 2) + X_{3} + [2d_{n−1}^{3} − X_{2}(d_{n−1} − n − 3) \\ − 6d_{n−1}^{2} − d_{n−1}^{2}n + 7d_{n−1}n − 4n^{2} − X_{3} − 2d_{n−1} + 4]α_{d_{n−1}}) , \end{matrix} (36)
T_{xyx,2}(δ, d_{n−1}) = T (δ) α_{1} α_{d_{n−1}}(d_{n−1} − 1) \frac{n^{2} + (1 − 2d_{n−1})n − 2 + 2d_{n−1}^{2} − X_{2}}{(n − 1)(n − 2)(n − 3)(n − 4)} ,  (37)

where 1 ≤ d_{n−1} ≤ n − 1.

\begin{matrix}T_{xyx,4}( & δ, d_{0}, d_{n−1}) + T_{xyx,5}(δ, d_{0}, d_{n−1}) = \frac{T (δ) α_{d_{0}}}{(n − 1)(n − 2)(n − 3)(n − 4)}× \\ ( − 12d_{0}^{3} − (d_{0} − 5)n^{2} + X_{2}(3d_{0} − n − 5) + 30d_{0}^{2} + 3(2d_{0}^{2} − 7d_{0} + 3)n \\ + [4d_{0}^{3} + 3d_{0}^{2}d_{n−1} + 3d_{0}d_{n−1}^{2} + 2d_{n−1}^{3} + (d_{0} − 5)n^{2} − X_{2}(2d_{0} + d_{n−1} − n − 5) \\ − 11d_{0}^{2} − 10d_{0}d_{n−1} − 9d_{n−1}^{2} − (3d_{0}^{2} + 2d_{0}d_{n−1} + d_{n−1}^{2} − 12d_{0} − 9d_{n−1} + 9)n \\ − X_{3} + 3d_{0} + 5d_{n−1} + 8]α_{d_{n−1}} + X_{3} − 8d_{0} − 8) , \end{matrix} (38)

\begin{matrix}T_{xyx,6}(δ, d_{0}, d_{n−1}) + T_{xyx,8}(δ, d_{0}, d_{n−1}) = \frac{T (δ) α_{d_{0}}}{(n − 1)(n − 2)(n − 3)(n − 4)}× \\ ( − 6d_{0}^{3} + X_{2}(2d_{0} − n − 4) + 20d_{0}^{2} + 2(d_{0}^{2} − 7d_{0} + 3)n + 4n^{2} + X_{3} − 6d_{0} − 6 \\ + [2d_{0}^{3} + d_{0}^{2}d_{n−1} + d_{0}d_{n−1}^{2} + 2d_{n−1}^{3} − X_{2}(d_{0} + d_{n−1} − n − 4) − 7d_{0}^{2} − 6d_{0}d_{n−1} \\ − 7d_{n−1}^{2} − (d_{0}^{2} + d_{n−1}^{2} − 7d_{0} − 7d_{n−1} + 6)n − 4n^{2} − X_{3} + 3d_{0} + 3d_{n−1} + 6]α_{d_{n−1}}) , \end{matrix} (39)

where 2 ≤ d_{0} ≤ n − 1 and 1 ≤ d_{n−1} ≤ n − 1.

\begin{matrix}T_{xyx,7}(δ, d_{0}, d_{n−2}) + T_{xyx,9}(δ, d_{0}, d_{n−2}) = \frac{T (δ) α_{d_{0}}}{(n − 1)(n − 2)(n − 3)(n − 4)}× \\ ( − 6d_{0}^{3} − (d_{0} − 1)n^{2} + X_{2}(d_{0} − 1) + 10d_{0}^{2} + (4d_{0}^{2} − 7d_{0} + 3)n \\ + [2d_{0}^{2}d_{n−2} + 2d_{0}d_{n−2}^{2} + 2d_{n−2}^{3} + (d_{n−2} − 1)n^{2} − 2d_{0}^{2} − X_{2}(d_{n−2} − 1) − 4d_{0}d_{n−2} \\ − 4d_{n−2}^{2} − (2d_{0}d_{n−2} + 2d_{n−2}^{2} − 2d_{0} − 5d_{n−2} + 3)n + 2d_{0} + 2]α_{d_{n−2}} − 2d_{0} − 2) , \end{matrix} (40)

where 2 ≤ d_{0} ≤ n − 1 and 2 ≤ d_{n−2} ≤ n − 1.

Combining the above equations yields for all d, d_{0} ≥ 1:

\begin{aligned}T_{xyx}(δ, d_{0}, d) = & \frac{T (δ) α_{d_{0}}(α_{d} − δ_{d_{0},d})}{(n − 1)(n − 2)(n − 3)(n − 4)} (6 d^{3} + 2 (3 d − 10)d_{0}^{2} + 6 d_{0}^{3} + 16 \\ & + (d + d_{0} − 10)n^{2} − (3 X_{2} − 8)d − 20 d^{2} + (6 d^{2} − 3 X_{2} − 20 d + 8)d_{0} \\ & − [4 d^{2} + (4 d − 21)d_{0} + 4 d_{0}^{2} − 2 X_{2} − 21 d + 18]n + 10 X_{2} − 2 X_{3}). \end{aligned} (41)

Since we need the number of all edge-labeled trees in the class xyx to compute the number of error-free trees, we compute this formula as well. Combining the above formulas after summing over the free variables results in

T_{xyx}(δ) = T (δ) \frac{−6n^{2} + 10n − 4 + 2X_{2}(n + 1) − 2X_{3}}{(n − 1)(n − 2)} .  (42)

B The case T_{xyzx}

For the xyzx case we have the following restrictions 1. C = (1)(2)(n − 2) …, 0 ∉ C

2. C = (1)(2)(n − 1) …, 0 ∉ C

3. C = (1)(2)(1) …, 0 ∉ C

4. C = (1)(2)(2) …, 0 ∉ C

5. C = (1)(2)(0) …

6. C = (1) … (1)(2)(0) …

7. C = (1)(2) … (2)(0) …

8. C = (1) … (1)(2) … (2)(0) …

9. C = … (n − 2)(1)(2)(0) …

10. C = … (n − 2)(1) … (1)(2)(0) …

11. C = … (n − 2)(1)(2) … (2)(0) …

12. C = … (n − 2)(1) … (1)(2) … (2)(0) …

13. C = … (n − 1)(1)(2)(0) …

14. C = … (n − 1)(1) … (1)(2)(0) … 15. C = … (n − 1)(1)(2) … (2)(0) …

16. C = … (n − 1)(1) … (1)(2) … (2)(0) …

The first four restrictions are quite similar to the case xx_{1}, except that there are two more fixed positions. Like label 0, these labels could be any label except the one chosen for 0. To correct for this, we have to multiply all counts by (n − 3)(n − 4) like we did with (n − 2) for label 0.

\begin{matrix}T_{xyzx,1}(δ) & = T_{xyzx,3}(δ) = T_{xyzx,4}(δ) = \\ T (δ) α_{1} \frac{−4 n^{3} − 6 n^{2} + 22 n − 12 + X_{2}(n^{2} + 11 n − 4) − 2 X_{3}(n + 3) + 2 X_{4}}{(n − 1)(n − 2)(n − 3)(n − 5)} . \end{matrix} (43)

\begin{matrix}T_{xyzx,2}(δ) = \\ T (δ) α_{1} \frac{n^{4} + 10 n^{3} − 5 n^{2} − 22 n + 16 − 6 X_{2}(n^{2} + 3 n − 2) + 8 X_{3}(n + 1) − 6 X_{4}}{(n − 1)(n − 2)(n − 3)(n − 4)(n − 5)} . \end{matrix} (44)

\begin{matrix}T_{xyzx,5}(δ) & + T_{xyzx,6}(δ) + T_{xyzx,7}(δ) + T_{xyzx,8}(δ) = \frac{T (δ)}{(n − 1)(n − 2)(n − 3)(n − 5)}× \\ ( − 7 n^{4} + 22 n^{3} + 75 n^{2} + 4 (2 n^{3} + 3 n^{2} − 11 n + 6)α_{1} − 178 n + 88 \\ + 2 (n^{3} + 5 n^{2} − (n^{2} + 11 n − 4)α_{1} − 46 n + 18)X_{2} \\ − 4 (n^{2} − (n + 3)α_{1} − 2 n − 11)X_{3} + 2 X_{4}(2 n − 2 α_{1} − 9)). \end{matrix} (45)

T_{xyzx,9}(δ) + T_{xyzx,10}(δ) + T_{xyzx,11}(δ) + T_{xyzx,12}(δ) = \frac{T (δ)}{(n − 1)(n − 2)(n − 3)(n − 4)(n − 5)}×
( − 2 (2 n^{3} + 3 n^{2} − 11 n + 6)(n − 3) + 2 (2 n^{3} + 3 n^{2} − 11 n + 6)α_{1}
+ ((n^{2} + 11 n − 4)(n − 3) − (n^{2} + 11 n − 4)α_{1})X_{2}
− 2 ((n + 3)(n − 3) − (n + 3)α_{1})X_{3} + 2 X_{4}(n − α_{1} − 3)).

(46)

\begin{matrix}T_{xyzx,13}(δ) & + T_{xyzx,14}(δ) + T_{xyzx,15}(δ) + T_{xyzx,16}(δ) = \frac{T (δ)}{(n − 1)(n − 2)(n − 3)(n − 5)}× \\ (n^{4} + 10 n^{3} − 5 n^{2} − 22 n + 16)(n − 4) − (n^{4} + 10 n^{3} − 5 n^{2} − 22 n + 16)α_{1} \\ − 6 ((n^{2} + 3 n − 2)(n − 4) − (n^{2} + 3 n − 2)α_{1})X_{2} \\ + 8 ((n + 1)(n − 4) − (n + 1)α_{1})X_{3} − 6 X_{4}(n − α_{1} − 4)). \end{matrix} (47)

Combining the above formulas results in

\begin{aligned}T_{xyzx}(δ) = \frac{T (δ)}{(n − 1)(n − 2)(n − 3)}( & − 10 n^{3} − 12 n^{2} + 50 n − 28 \\ & + 3 (n^{2} + 9 n − 4)X_{2} − 2 X_{3}(3 n + 7) + 6 X_{4}). \end{aligned} (48)

References

[1] Andrei Asinowski, Gill Barequet, Ronnie Barequet, and Günther Rote, Proper n-cell polycubes in n − 3 dimensions, J. Integer Sequences 15 (2012), Article 12.8.4.

[2] Andrei Asinowski, Gill Barequet, and Yufei Zheng, Enumerating polyominoes with fixed perimeter defect, Electron. Notes Discrete Math. 61 (Supplement C) (2017), 61–67.

[3] Andrei Asinowski, Gill Barequet, and Yufei Zheng, Polycubes with small perimeter defect, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (2018), to appear.

[4] Gill Barequet and Mira Shalah, Counting n-cell polycubes proper in n − k, European J. Combin. 63 (2017), 146–163.

[5] Ronnie Barequet, Gill Barequet, and Günther Rote, Formulae and growth rates of highdimensional polycubes, Combinatorica 30 (2010), 257–275.

[6] Gregory S. Call and Daniel J. Velleman, Pascal’s matrices, Amer. Math. Monthly 100 (1993), 372–376.

[7] Peter J. Cameron, Counting two-graphs related to trees, Electron. J. Combin. 2 (1995), Paper R4.

[8] Arthur Cayley, A theorem on trees, Quart. J. Pure Applied Math. 23 (1889), 376–378.

[9] Michael E. Fisher and John W. Essam, Some cluster size and percolation problems, J. Math. Phys. 2 (1961), 609–619.

[10] Solomon W. Golomb, Polyominoes, Princeton University Press, 2nd edition, 1994.

[11] Anthony J. Guttmann, ed., Polygons, Polyominoes and Polycubes, Lecture Notes in Phys., Vol. 775, Springer-Verlag, 2009.

[12] Godfrey Harold Hardy and Srinivasa Ramanujan, Asymptotic formulae in combinatory analysis, Proc. Lond. Math. Soc. 17 (1918), 75–115.

[13] William Frederick Lunnon, Counting multidimensional polyominoes, Comput. J. 18 (1975), 366–367.

[14] Sebastian Luther and Stephan Mertens, Counting lattice animals in high dimensions, J. Stat. Mech. Theory Exp. (2011), P09026.

[15] Stephan Mertens, Lattice animals: A fast enumeration algorithm and new perimeter polynomials, J. Stat. Phys. 58 (1990), 1095–1108.

[16] Stephan  Mertens,  Lattice  animals  website.  Available  at

    http://www.ovgu.de/mertens/research/animals, 2017.

[17] Oleg Pikhurko, Generating edge-labeled trees, Amer. Math. Monthly 112 (2005), 919– 921.

[18] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences. Available elec-

    tronically at http://oeis.org.

[19] Dietrich Stauffer and Amnon Aharony, Introduction to Percolation Theory, Taylor & Francis, 2nd revised edition, 1994.

[20] Antoine Zoghbi and Ivan Stojmenović, Fast algorithms for generating integer partitions, Internat. J. Comput. Math. 70 (1998), 319–332.

2010 Mathematics Subject Classification: Primary 05B50; Secondary 05A15, 05A16, 05C30, 82B43. Keywords: Lattice animal, polyomino, perimeter polynomial, percolation.

(Concerned with sequences \underline{A000041}, \underline{A001931}, \underline{A127670}, \underline{A151830}, \underline{A151831}, \underline{A151832}, \underline{A151833}, \underline{A151834}, \underline{A151835}, \underline{A171860}, and \underline{A191092}.)

Received July 7 2017; revised versions received October 22 2017; October 25 2017. Published in Journal of Integer Sequences, October 27 2017.

Return to Journal of Integer Sequences home page.