Enumeration of Polycubes and Dirichlet Convolutions

C. Carré, N. Debroux, M. Deneufchâtel, J.-Ph. Dubernard,

C. Hillairet, J.-G. Luque, and O. Mallet

LITIS Université de Rouen

Faculté des Sciences et Techniques - Madrillet

Avenue de l’Université 76801 St Etienne du Rouvray CEDEX

France

christophe.carre@univ-rouen.fr
matthieu.deneufchatel@univ-rouen.fr
jean-philippe.dubernard@univ-rouen.fr
jean-gabriel.luque@univ-rouen.fr
 olivier.malle@univ-rouen.frt
 noemie.debroux@insa-rouen.fr
conrad.hillairet@insa-rouen.fr

Abstract

We present a new method for polycube enumeration, in connection with the multiindexed Dirichlet convolution, which we illustrate with the study of two families of polycubes, namely pyramids and espaliers.

1 Introduction

In the Cartesian plane ℤ^{2}, a polyomino is a finite edge-connected union of elementary cells (unit squares) without cut point and defined up to a translation. Even if they have been

Figure 1: A polycube

studied for a long time in combinatorics, no exact formula is known for counting general polyominoes, but many results have been found concerning certain classes of polyominoes [4,14].

Polyominoes have a 3-dimensional equivalent: the 3-dimensional polycubes (or polycubes for short) [19] (see Figure 1). Now if we consider that an elementary cell is a unit cube, then a polycube is a face-connected finite set of elementary cells defined up to a translation in ℤ^{3}. Like polyominoes, polycubes appear in statistical physics, more precisely in the phenomenon of percolation [6]. A lot of studies have tackled the problem of counting polycubes with respect to their number, n say, of cells. The first values were found in 1972 up to n = 6 [19] and the last one (to our knowledge) in 2006, up to n = 18 [1]. Thus, the number of polycubes composed of 18 cells is equal to 84384157287999.

The notion of polycube can be extended to dimension d, with d ≥ 3; d-dimensional polycubes (or d-polycubes for short) are used in an efficient model of real-time validation [17], as well as in the representation of finite geometrical languages [8]. Although polycubes are higher dimensional natural analogues of polyominoes, very little is known about their enumeration. The most well-known, for which there exists a rich literature, is the enumeration of plane partitions [3,5,11,27]. For instance, an expression of the generating function of planar partitions with respect to number of peaks has been given by MacMahon [21], Bender and Knuth [3] and Bressoud and Propp [5]; it is equal to

∑_{n} P L(n)q^{n} = ∏_{k≥0} \frac{1}{(1 − q^{k})^{k}}

We also can give another result of MacMahon [21], reshaped by MacDonald [20]. It determines the number of plane partitions that are included in a parallelepiped of dimensions a × b × c and is equal to

P L(a, b, c) = ∏_{i=1}^{a} ∏_{j=1}^{b} ∏_{k=1}^{c} \frac{i + j + k − 1}{i + j + k − 2}

Recently, a new method allowed the enumeration of several families of polycubes (in dimension 3 and greater than 3) as far as they can be split into strata [9]. For instance, using this method, one can find that the generating function of vertically-convex s-directed polycubes with respect to width and volume is given by

V CD(t, p) = \frac{tp(p − 1)(1 − 3p + p^{2})}{1 − 6p + 11p^{2} − 6p^{3} + p^{4} − t(p − 2p^{2} + 2p^{3})} [9].

In this paper, we propose to investigate two classes of polycubes (pyramids and espaliers) from which we deduce a new method of enumeration. The interest of these results lies in their connection with Lambert transform and Dirichlet generating series.

The paper is organized as follows. First, in Section 2, we define pyramids and espaliers in dimension d + 1 and investigate their first properties. In particular, espaliers of height h are used to describe a partial order on partitions of height h which corresponds to the classical divisibility order for h = 1. In Section 3, we extend the convolution product to multiindexed families and we give an interpretation in terms of ordinary and Dirichlet generating functions. Furthermore, we point out the connection with espaliers. In Section 4, we apply the properties of the convolution product to the enumeration of pyramids and espaliers. In particular, we show that the number n_{v}(d) of pyramids of volume v in dimension d + 1^{1} is a polynomial in d of degree ⌊log_{2}(v)⌋. Finally, in Section 5, we explain how to apply our method to other families of polycubes.

2 Some families of polycubes

2.1 What are polycubes?

A small number of families of polycubes have been investigated. The most well-known, for which there exists a rich literature, is that of plane partitions [3, 5, 11, 27]. Recently, a new method has made it possible to enumerate several families of polycubes (in dimension 3 and greater than 3) [9]. It is worthwhile noticing that it is the investigation of plateau and parallelogram polycubes that motivated the design of this method [7]. No other subclass of polycubes seems to have been examined. In the next section, we recall definitions about the extensions of classes of directed polyominoes to the (2 + 1)-dimensional case [7,9].

A polyomino is said to be row-convex (resp. column-convex) if its intersection with any horizontal (resp. vertical) strip is convex. It is said to be directed if each of its cells can be reached from a distinguished cell, called the root, by a path only made of East and North steps.

2.2 Definitions

We will consider polycubes as discrete objects which are embedded in the three-dimensional discrete lattice ℤ^{3}. Each point of ℤ^{3} will be represented by the triplet of its coordinates and lexicographically ordered. An atomic cell is a cube of volume 1 which will be identified with the smallest coordinates of its vertices. So, for our purpose and without loss of generality, we will consider a polycube as a finite and face-connected collection P of cells such that its smallest cell is (0, 0, 0). The volume of a polycube is the number of its atomic cells. The height of a polycube P refers to the first coordinate: it is one plus the difference between the first coordinate of a point taken on the top of P and the one of a point taken in the bottom of P, i.e., height(P) := max{x : (x, y, z) ∈ P } − min{x : (x, y, z) ∈ P } + 1. For instance, the height of the polycube in Figure 1 is 4.

1d is the dimension of the pedestal, that is the dimension of the ambient space minus 1.

A very particular convex polycube is the horizontal plateau: it is a horizontal parallelepiped of height 1. To simplify the notation, let us call it a plateau. The notion of plateau allows us to define two new families of polycubes. They appear in the study of two particular families of convex-directed polycubes [7]. The first family is a subclass of plane partitions [5,11,27].

A pyramid polycube (or pyramid for short) is obtained by gluing together horizontal plateaus in such a way that

• (0, 0, 0) belongs to the first plateau, and each cell with coordinates (0, b, c) belonging to the first plateau is such that b, c ≥ 0.

• If the cell with coordinates (a, b, c) belongs to the (a + 1)-th plateau (a > 0), then the cell with coordinates (a − 1, b, c) belongs to the a-th plateau.

Note that the plateau made of cells whose first coordinate is k is called (k + 1)-th plateau.

Figure 2: A pyramid

An espalier polycube is a special pyramid such that for all a, the (a + 1)-th plateau contains the cell (a, 0, 0).

2.3 Counting pyramids

The most natural statistic to count pyramids and espaliers is the volume. The number of pyramids and espaliers of a given volume are presented below up to volume 12:

1, 3, 7, 16, 33, 63, 117, 202, 344, 566, 908, 1419

and

1, 3, 5, 10, 14, 26, 34, 57, 76, 116, 150, 227.

They correspond respectively to the sequences \underline{A229914} and \underline{A229915} in the OEIS [25]. This statistic can be refined by the height (i.e., the number of plateaus) and the volume of each plateau. If ℙ is a pyramid of height h, let mv(ℙ) = (v_{1}, …, v_{h}) with v_{1} ≥ v_{2} ≥ ⋯ ≥ v_{h} > 0 denote the sequence of the volumes of its plateaus. Let λ = (λ_{1}, …, λ_{h}), such that λ_{1} ≥ ⋯ ≥ λ_{h} > 0, be a partition. We define E_{λ} as the set of espaliers 𝔼 such that mv(𝔼) = λ. We use the following notation where t = e if the corresponding quantity involves espalier polycubes and t = p if it involves pyramid polycubes:

• n_{v}^{t} denotes the number of objects of volume v and n_{v,h}^{t} the number of objects of given height h and volume v;

• there are n_{[v_{1},...,v_{h}]}^{t} objects such that each plateau has volume v_{i}, for i such that 1 ≤ i ≤ h, if v_{1} ≥ ⋯ ≥ v_{h}.

By convention, there is no espalier nor pyramid of volume 0: n_{0}^{t} = 0. The number n_{i,j,h,v}^{t} of considered polycubes (espaliers or pyramids) of volume v, height h and such that their largest plateau has dimensions i × j is given by the recurrence n_{i,j,h,v}^{t} = ∑_{a,b} α_{a,b}^{t}n_{i+a,j+b,h−1,v−ij}^{t} with

α_{a,b}^{e} = 1, α_{a,b}^{p} = (a + 1)(b + 1) and n_{i,j,1,v}^{t} = δ_{ij,v}^{2}.

Let E^{t}(x; h) := ∑_{v≥1} n_{v,h}^{t}x^{v} denote the generating function for the number of considered polycubes (espaliers or pyramids) of given height h; we also define E^{t}(x) := ∑_{v≥1} n_{v}^{t}x^{v} = ∑_{h} E^{t}(x; h). Taking into account the distribution of the volume among the levels, one gets

E^{t}(x_{1}, …, x_{h}; h) = ∑_{m_{1}≥···≥m_{h}} n_{[m_{1},...,m_{h}]}^{t}x_{1}^{m_{1}} ⋯ x_{h}^{m_{h}}.

We also present results about Dirichlet generating functions, which are defined by

E_{D}^{t}(s_{1}, …, s_{h}; h) = ∑_{m_{1}≥···≥m_{h}} \frac{n_{[m_{1},...,m_{h}]}^{t}}{m_{1}^{s_{1}} ⋯ m_{h}^{s_{h}}} .

It is interesting to note that the limit lim_{h→∞} x^{−h}E^{e}(x; h) exists. The corresponding series is in fact the generating function for a class of (2 + 1)-dimensional objects, which we call quasi-espaliers, counted by volume. Quasi-espaliers are espaliers from which all the cells with coordinates (a, 0, 0) were removed. Note that quasi-espaliers are not considered up to a translation (so they are not polycubes): they are the figures obtained when we remove the column (a, 0, 0) from an espalier based at (0, 0, 0) (see Figure 3 for an example). For instance {(0, 1, 0)} and {(0, 0, 1)} are different quasi-espaliers. The first values are

2, 4, 7, 12, 18, 29, 42, 61, 87, 122, 167, 229.

Figure 3: An espalier and its associated quasi-espalier

If we extend the notion of quasi-espalier to pyramids, we can also extend the previous result to pyramids. A quasi-pyramid is obtained from a pyramid of height h by choosing a cell (h, b, c) in the pyramid and deleting all the cells (a, b, c) with 1 ≤ a ≤ h. Let Q^{p}(x) be their generating function with respect to volume. Then lim_{h→∞} x^{−h}E^{p}(x, h) exists and

lim_{h→∞} x^{−h}E^{p}(x, h) = Q^{p}(x) + \frac{x}{1 − x}.  (1)

Indeed, the reasoning is almost the same as with quasi-espaliers: if you remove one of the highest columns of a pyramid, then you obtains a quasi-pyramid. But the quasi-pyramid consisting in only one column (a, 0, 0) with 0 ≤ a ≤ n is obtained twice: from a pyramid with only two columns {(a, 0, 0) : 0 ≤ a ≤ n} and {(a, 1, 0) : 0 ≤ a ≤ m} with m > n, and also from a pyramid with only two columns {(a, 0, 0) : 0 ≤ a ≤ n} and {(a, 0, 1) : 0 ≤ a ≤ m}. This explains why we add the series \frac{x}{1−x}. All the other quasi-pyramids are obtained exactly once by removing the highest column of a pyramid having only one highest column. So, we recover the formula (1).

2.4 The projection order

Figure 4: One-to-one correspondence between espaliers and pairs of partitions

Here we describe an order on integer partitions of the same height (i.e., number of parts) h. Note first that there is a one-to-one correspondence between espaliers of height h and pairs of partitions of the same height h. The partitions are obtained by projecting an espalier 𝔼 of height h as 𝔼_{x} := {(a, 0, c) : (a, b, c) ∈ 𝔼} and 𝔼_{y} := {(a, b, 0) : (a, b, c) ∈ 𝔼}. These two sets are obviously two Ferrers diagrams which represent two partitions λ_{x}(𝔼) and λ_{y}(𝔼) of height h (see Figure 4 for an example). Conversely, to each pair of Ferrers diagrams (λ, μ) of height h, we associate the (2 + 1)-dimensional figure 𝔼^{λ,μ} := {(a, b, c) : (a, b) ∈ λ, (a, c) ∈ μ}. It is easy to check that 𝔼^{λ,μ} is an espalier and

2The indices i + a and j + b means that the plateau at height h − 1 is bigger than the one at height h.

𝔼^{λ,μ} = {(a, b, c) : (a, b, 0) ∈ 𝔼_{y}^{λ,μ}, (a, 0, c) ∈ 𝔼_{x}^{λ,μ}}.

So, the bijection is straightforward from the construction.

We define the relation ⪯ on the set of partitions of the same height by λ ⪯ μ if there exists 𝔼 ∈ E_{μ} such that λ_{x}(𝔼) = λ. For instance, Figure 4 illustrates the relations (4, 3, 2, 2, 1) ⪯ (20, 9, 2, 2, 1) and (5, 3, 1, 1, 1) ⪯ (20, 9, 2, 2, 1).

Proposition 1. The relation ⪯ is a partial order which generalizes the division order on integers in the following sense: (d, …, d) ⪯ (n, …, n) if and only if d|n.

Although it is not the purpose of this article, we note that the Möbius function ^{3} μ^{(h)} of this order seems to have interesting properties. For instance, let us give several identities which hold for h = 2. The simplest one is straightforward from the definition:

μ^{(2)}((1, 1), (n, n)) = μ^{(2)}((1, 1), (n, 1)) = μ(n).  (2)

where μ denotes the “classical” Möbius function on integers [22] ^{4}.

One also has

μ^{(2)}((1, 1), (p, m)) = −1 for p prime and p > m.  (3)

Hence, we have

μ^{(2)}((1, 1), (pq, n)) = 2(n_{1} + 1) ⋯ (n_{k} + 1) − 1 when \begin{cases}p, q are prime; \\ n = p_{1}^{n_{1}} ⋯ p_{k}^{n_{k}}; \\ p, q > n. \end{cases}  (4)

Indeed,

\begin{matrix}μ^{(2)}((1, 1), (pq, n)) = \\ − ∑_{d|n} (\underbrace{μ^{(2)}((1, 1), (p, d))}_{−1} + \underbrace{μ^{(2)}((1, 1), (q, d))}_{−1}) − μ^{(2)}((1, 1), (1, 1)) \end{matrix}  (5)

3The Möbius function of a partial order is obtained by inverting its adjacency matrix. This notion encodes, in an algebraic setting, the inclusion-exclusion principle. Readers should refer to Rota [24] for definition and properties of the Möbius function of a poset.

4As mentioned by Hardy and Wright [16], the Möbius function occurs implicitly in the early writings of Euler.

and the divisors of n are obtained by choosing a multi-index (m_{1}, …, m_{k}) ≤ (n_{1}, … n_{k}). Now observe that the Dirichlet generating series of μ^{(2)}((1, 1), (n, k)) is

∑_{1≤k≤n} \frac{μ^{(2)}((1, 1), (n, k))}{n^{s_{1}}k^{s_{2}}} = ( ∑_{1≤k≤n} \frac{1}{n^{s_{1}}k^{s_{2}}} )^{−1} .

Setting s_{2} = 0 yields

∑_{1≤n} \frac{∑_{k=1}^{n} μ^{(2)}((1, 1), (n, k))}{n^{s_{1}}} = ∑_{1≤n} \frac{1}{n} (∑_{k=1}^{n} μ^{(2)}((1, 1), (n, k))) \frac{1}{n^{s_{1}−1}} .

Therefore,

∑_{k=1}^{n} μ^{(2)}((1, 1), (n, k)) = nμ(n).  (6)

Iterating this relation, one finds

∑_{n≥k_{1}≥k_{2}≥···≥k_{ℓ}} \frac{μ^{(ℓ+1)}((1, …, 1), (n, k_{1}, …, k_{ℓ}))}{k_{1} ⋯ k_{ℓ−1}} = nμ(n).  (7)

2.5 Higher dimensional polycubes

The (d+1)-polycubes^{5} are a natural extension of the notion of polyomino to dimension d+1, with d ≥ 2 [7, 9]. An atomic (d + 1)-cell is a cube of volume 1 identified with the smallest coordinates of its vertices in ℤ^{d+1}. A (d + 1)-polycube is then a (d + 1)-face-connected finite set of elementary cells, defined up to translation. The volume of a (d + 1)-polycube is the number of its elementary cells. A (d + 1)-parallelepiped is a (d + 1)-polycube P such that for some (n_{1}, ⋯, n_{d+1}) ∈ ℕ^{d+1}, any cell with coordinates (α_{1}, ⋯, α_{d+1}) satisfying 0 ≤ α_{k} ≤ n_{k}, 1 ≤ k ≤ d + 1, belongs to P. Then a (d + 1)-plateau is a (d + 1)-parallelepiped of height 1 (i.e., it is composed of cells of the form (a, n_{1}, ⋯, n_{d+1}) ∈ ℕ^{d+1} for a fixed a).

A (d + 1)-pyramid is a (d + 1)-polycube obtained by gluing together (d + 1)-plateaus in such a way that

• the cell (0, 0, …, 0) belongs to the first plateau and each cell with coordinates (0, n_{1}, …, n_{d+1}) belonging to the first plateau is such that n_{1}, …, n_{d+1} ≥ 0.

• if the cell with coordinates (n_{0}, n_{1}, …, n_{d+1}) belongs to the (n_{0}+1)-th plateau (n_{0} > 0), then the cell with coordinates (n_{0} − 1, n_{1}, …, n_{d+1})) belongs to the n_{0}-th plateau.

A (d + 1)-espalier is a (d + 1)-pyramid such that each plateau contains the cell (n_{0}, 0, …, 0). As with (2 + 1)-polycubes, we define the following notation:

5In our notation, we distinguish a special dimension for the height of the polycubes. For instance, a polyomino is a (1 + 1)-polycube and a polycube is a (2 + 1)-polycube.

• n_{v}^{t}(d) denotes the number of objects of type t (recall that t = p means that the objects are pyramids and t = e means that they are espaliers) of volume v and n_{v,h}^{t}(d) the number of objects of given height h and volume v;

• n_{[v_{1},...,v_{h}]}^{t}(d) denotes the number of objects of type t such that each plateau has volume v_{i}, for i such that 1 ≤ i ≤ h, if v_{1} ≥ ⋯ ≥ v_{h}.

By convention, there is no espalier nor pyramid of volume 0 in any dimension and only one object in dimension 0 and volume v > 0: n_{0}^{t}(d) = 0 and n_{v}^{t}(0) = 1. Let E^{t}(x; h, d) = ∑_{v≥1} n_{v}^{t}(d)x^{v} denote the generating function for the number of espaliers of given height h; we also define E^{t}(x; d) := ∑_{v≥1} n_{v}^{t}x^{v} = ∑_{h} E^{t}(x; h, d). Taking into account the distribution of the volume among the levels, one sets

E^{t}(x_{1}, …, x_{h}; h, d) := ∑_{m_{1}≥···≥m_{h}} n_{[m_{1},...,m_{h}]}^{t}(d)x_{1}^{m_{1}} ⋯ x_{h}^{m_{h}},

and

E_{D}^{t} := ∑_{m_{1}≥···≥m_{h}≥1} \frac{n_{[m_{1},...,m_{h}]}^{t}(d)}{m_{1}^{s_{1}} ⋯ m_{h}^{s_{h}}}.

3 Multivariate versions of the Lambert transform

3.1 Convolution and multivariate series

We consider a natural multidimensional generalization of the Dirichlet convolution. For each h ∈ ℕ, we consider the set multi-indexed families: M_{h} := {(a_{n_{1},...,n_{h}})_{n_{1},...,n_{h}≥1} : a_{n_{1},...,n_{h}} ∈ ℂ}. If A = (a_{n_{1},...,n_{h}}) and B = (b_{n_{1},...,n_{h}}) are two families in M_{h} then let C = A ⋆ B = (c_{n_{1},...,n_{h}})_{n_{1},...,n_{h}} ∈ M_{h} denote the multivariate convolution of A and B defined by

c_{n_{1},...,n_{h}} = ∑_{n_{i}=m_{i}p_{i}, i=1,...h} a_{m_{1},...,m_{h}}b_{p_{1},...,p_{h}}.

Proposition 2. For any h ∈ ℕ, the product ⋆ is distributive and 1 = (δ_{1,n_{1}} ⋯ δ_{1,n_{h}})_{n_{1},...,n_{h}} is its identity. Hence, this endows M_{h} with a structure of commutative algebra.

Denoting by S_{A}(x_{1}, …, x_{h}) := ∑_{n_{1},...,n_{h}≥1} a_{n_{1},...,n_{h}}x^{n_{1}} ⋯ x^{n_{h}} the ordinary generating function of A and by S_{A}^{D}(s_{1}, …, s_{h}) := ∑_{n_{1},...,n_{h}≥1} \frac{a_{n_{1},...,n_{h}}}{n_{1}^{s_{1}}···n_{h}^{s_{h}}} its Dirichlet generating function, we observe the following fact.

Proposition 3. Let A, B ∈ M_{h}. The three following assertions are equivalent:

1. C = A ⋆ B;

2. S_{C}(x_{1}, …, x_{h}) = ∑_{n_{1},...,n_{h}} a_{n_{1},...,n_{h}}S_{B}(x_{1}^{n_{1}}, …, x_{h}^{n_{h}});

3. S_{C}^{D}(s_{1}, …, s_{h}) = S_{A}^{D}(s_{1}, …, s_{h}) S_{B}^{D}(s_{1}, …, s_{h}).

Indeed, via the map A ↦ S_{A}, the ideal x_{1} ⋯ x_{h}ℂ[x_{1}, …, x_{h}] can be embedded with a structure of commutative algebra (x_{1} ⋯ x_{h}ℂ[x_{1}, …, x_{h}], +, ⋆) isomorphic to M_{h}. With this notation, we have S_{A⋆B} = S_{A} ⋆ S_{B}. The formal substitution

D : x_{i}^{n} → \frac{1}{n^{s_{i}}}

is an isomorphism from (x_{1} ⋯ x_{h}ℂ[x_{1}, …, x_{h}], +, ⋆) to the algebra of multivariate Dirichlet formal series in the variables {s_{1}, …, s_{h}}. Note that the isomorphism above can be realized through an iteration of Mellin transforms [15, Appendix B, Section B.7]:

D[f] = \frac{1}{∏_{i=1}^{h} Γ(s_{i})} ∫_{0}^{∞}⋯ ∫_{0}^{∞} f (e^{−x_{1}}, …, e^{−x_{h}}) x_{1}^{s_{1}−1} ⋯ x_{h}^{s_{h}−1}dx_{1} ⋯ dx_{h}

where Γ(s) = ∫_{0}^{∞} e^{−x}x^{s−1}dx is the Euler Gamma function.

Let T_{h} := {(a_{n_{1},...,n_{h}})_{n_{1},...,n_{h}≥1} ∈ M_{h} : a_{n_{1},...,n_{h}} ≠ 0 ⇒ n_{1} ≥ ⋯ ≥ n_{h}}. As T_{h} is stable under convolution, it is a subalgebra of M_{h}. In the rest of the paper, let (a_{n_{1},...,n_{h}})_{n_{1}≥···≥n_{h}≥1} denote the elements of T_{h}.

3.2 Multivariate Lambert transform

Let △ = (1)_{m_{1}≥···≥m_{h}≥1}. We call multivariate Lambert transform of A = (a_{n_{1},...,n_{h}})_{n_{1}≥···≥n_{h}≥1} the convolution of A with △: T_{L}(A) := A ⋆ △. Remark that the (ordinary) generating function of △ is S_{△} = \frac{x_{1}···x_{h}}{(1−x_{1})(1−x_{1}x_{2})···(1−x_{1}···x_{h})} and its Dirichlet generating function is S_{△}^{D} = Z(s_{1}, …, s_{h}), where Z denotes the large multizeta function Z(s_{1}, …, s_{h}) := ∑_{n_{1}≥···≥n_{h}≥1} \frac{1}{n_{1}^{s_{1}}···n_{h}^{s_{h}}} [12,13].

The generating function of (â_{n_{1},...,n_{h}})_{n_{1},...,n_{h}} := T_{L}(A) is

S_{T_{L}(A)} = S_{△} ⋆ S_{A}

= ∑_{n_{1}≥···≥n_{h}≥1} a_{n_{1},...,n_{h}} \frac{x_{1}^{n_{1}} ⋯ x_{h}^{n_{h}}}{(1 − x_{1}^{n_{1}})(1 − x_{1}^{n_{1}}x_{2}^{n_{2}}) ⋯ (1 − x_{1}^{n_{1}} ⋯ x_{h}^{n_{h}})}

and its Dirichlet generating function is given by

S_{T_{L}(A)}^{D}(s_{1}, …, s_{h}) = Z(s_{1}, …, s_{h})S_{A}^{D}(s_{1}, …, s_{h}).

The multivariate Lambert transform is related to the order defined in Section 2.4 by the following formula.

Proposition 4. If A = (a_{n_{1},...,n_{h}})_{n_{1},...,n_{h}} then we have

â_{n_{1},...,n_{h}} = ∑_{(m_{1},...,m_{h})⪯(n_{1},...,n_{h})} a_{m_{1},...,m_{h}}.

As a consequence, the Dirichlet generating function of μ^{h}((1, …, 1), λ) is the inverse of Z:

Corollary 5.

Z(s_{1}, …, s_{h})^{−1} = ∑_{(1,...,1)⪯(n_{1},...,n_{h})} \frac{μ^{h}((1, …, 1), (n_{1}, …, n_{h}))}{n_{1}^{s_{1}} ⋯ n_{h}^{s_{h}}}.

Note that when h = 1, Z(s) = ζ(s) is the Riemann zeta function and Corollary 5 is the classical identity ζ(s)^{−1} = ∑_{n>0} \frac{μ(n)}{n^{s}}.

3.3 Another transform

Let ▲ = ((n_{1} − n_{2} + 1) ⋯ (n_{h−1} − n_{h} + 1))_{n_{1}≥···≥n_{h}≥1}. Using ▲ and the convolution product

defined above, we construct a new transformation:

T_{▲}(A) = ▲ ⋆ A = (a_{n_{1},··· ,n_{h}}^{▲})_{n_{1}≥···≥n_{h}≥1}.

Lemma 6. The generating function of ▲ is given by the following formula

\begin{matrix}S_{▲} := & ∑_{n_{1}≥···≥n_{h}≥1}(n_{1} − n_{2} + 1) ⋯ (n_{h−1} − n_{h} + 1)x_{1}^{n_{1}} ⋯ x_{h}^{n_{h}} \\ = & \frac{x_{1} ⋯ x_{h}}{(1 − x_{1})^{2}(1 − x_{1}x_{2})^{2} ⋯ (1 − x_{1} ⋯ x_{h−1})^{2}(1 − x_{1} ⋯ x_{h})}. \end{matrix}  (8)

Proof. First, note that \frac{x}{1 − x^{2}} = \frac{d}{dx} (\frac{1}{1 − x}). Hence, we have \frac{x}{1 − x^{2}} = ∑_{n>0} nx^{n}. Now

assume that one has two variables x and y. Then

\frac{xy}{(1 − x)^{2}(1 − xy)} = (∑_{n>0} nx^{n}) y (∑_{m≥0}(xy)^{m})

= ∑_{n>0,m≥0} nx^{n+m}y^{m+1}

= ∑_{n>0,m>0} nx^{n+m−1}y^{m}

= ∑_{n≥m>0}(n − m + 1)x^{n}y^{m}.

Now assume that the formula holds with h variables. Then

\frac{x_{1} ⋯ x_{h+1}}{(1 − x_{1})^{2}(1 − x_{1}x_{2})^{2} ⋯ (1 − x_{1} ⋯ x_{h})^{2}(1 − x_{1} ⋯ x_{h+1})} =

\frac{1}{(1 − x_{1})^{2}} ∑_{n_{1}≥···≥n_{h}≥1}(n_{1} − n_{2} + 1) ⋯ (n_{h−1} − n_{h} + 1)(x_{1}x_{2})^{n_{1}} ⋯ x_{h}^{n_{h}} =

∑_{n>0} nx^{n−1} ∑_{n_{1}≥···≥n_{h}≥1}(n_{1} − n_{2} + 1) ⋯ (n_{h−1} − n_{h} + 1)(x_{1}x_{2})^{n_{1}} ⋯ x_{h}^{n_{h}} =

∑_{n>0,n_{1}≥···≥n_{h}≥1} n(n_{1} − n_{2} + 1) ⋯ (n_{h−1} − n_{h} + 1)x_{1}^{n+n_{1}−1}x_{2}^{n_{1}} ⋯ x_{h}^{n_{h}} =

∑_{n_{1}≥0,n_{2}≥···≥n_{h_{+}1}≥1}(n_{1} + 1)(n_{2} − n_{3} + 1) ⋯ (n_{h} − n_{h+1} + 1)x_{1}^{n_{1}+n_{2}}x_{2}^{n_{2}} ⋯ x_{h}^{n_{h+1}}.

A last change of variables proves the formula for h + 1 variables and the result follows by induction.

Lemma 6 implies that the generating function of T_{▲}(A) is

S_{▲} ⋆ S_{A} = ∑_{n_{1}≥···≥n_{h}≥1} a_{n_{1},...,n_{h}} \frac{x_{1}^{n_{1}}···x_{h}^{n_{h}}}{(1−x_{1}^{n_{1}})^{2}(1−x_{1}^{n_{1}}x_{2}^{n_{2}})^{2}···(1−x_{1}^{n_{1}}···x_{h−1}^{n_{h−1}})^{2}(1−x_{1}^{n_{1}}···x_{h}^{n_{h}})}

and its Dirichlet generating function is given by

S_{T_{▲}(A)}^{D} = Z^{▲}(s_{1}, …, s_{h}) S_{A}^{D}(s_{1}, …, s_{h}),

where

Z^{▲}(s_{1}, …, s_{h}) = ∑_{n_{1}≥···≥n_{h}≥1} \frac{(n_{1} − n_{2} + 1) ⋯ (n_{h−1} − n_{h} + 1)}{n_{1}^{s_{1}} ⋯ n_{h}^{s_{h}}}.

As a consequence, we have a_{n_{1},...,n_{h}}^{▲} = ∑_{(m_{1},...,m_{h})⪯(n_{1},...,n_{h})} α_{m_{1},...,m_{h}}^{n_{1},...,n_{h}}a_{m_{1},...,m_{h}} where α_{m_{1},...,m_{h}}^{n_{1},...,n_{h}} =

(\frac{n_{1}}{m_{1}} − \frac{n_{2}}{m_{2}} + 1) ⋯ (\frac{n_{h−1}}{m_{h−1}} − \frac{n_{h}}{m_{h}} + 1) are non-negative integers. These coefficients have a simple interpretation. Assume that a plateau of volume n_{1} with one of its sides of length m_{1} lies under a plateau of volume n_{2} and length m_{2} in the same direction (see Figure 5). Then \frac{n_{1}}{m_{1}} − \frac{n_{2}}{m_{2}} + 1 gives the number of translations of the above plateau over the other one which yield a pyramid. Hence, α_{m_{1},...,m_{h}}^{n_{1},...,n_{h}} gives the number of pyramids obtained with translations of the plateaus in one direction only.

4 Application to the enumeration of pyramids

4.1 Counting pyramids and espaliers by volume

The one-to-one correspondence described in Section 2.4 allows us to construct an espalier 𝔼_{λ,λ′} ∈ E_{(λ_{1}λ′_{1},...,λ_{h}λ′_{h})} for each pair of partitions λ = (λ_{1}, …, λ_{h}) and λ′ = (λ′_{1}, …, λ′_{h}). Hence, we deduce

m_{1} \frac{n_{1}}{m_{1}} m_{2} \frac{n_{2}}{m_{2}}

Figure 5: Translations of plateaus

Lemma 7.

△^{⋆2} = (n_{[m_{1},...,m_{h}]}^{e})_{m_{1}≥···≥m_{h}≥1} .

A similar method can be used to compute the number of pyramids. We consider pyramids in dimension 1 + 1. These objects are obtained from partitions (which are espaliers in dimension 1 + 1) by shifting each (1 + 1)-plateau. A (1 + 1)-pyramid ℙ will be of type λ = (λ_{1}, …, λ_{h}) if the first plateau is of size λ_{1}, …, the h-th plateau is of size λ_{h}; we will write mv(ℙ) = λ as with pyramids in dimension 2 + 1. The number of (1 + 1)-pyramids of type λ equals (λ_{1} − λ_{2} + 1) ⋯ (λ_{h−1} − λ_{h} + 1) (see Figure 6 for an example).

Figure 6: The 3 (1 + 1)-pyramids of type (5, 3)

The pyramids of height h are in one-to-one correspondence with the pairs of (1 + 1)- pyramids of height h (see Figure 7 for an example). Furthermore, the pyramid ℙ corresponding to a pair (ℙ′, ℙ′′) is such that mv(ℙ) = (λ′_{1}λ′′_{1}, …, λ′_{h}λ′′_{h}) if mv(ℙ′) = λ′ and mv(ℙ′′) = λ′′.

Figure 7: A (2 + 1)-pyramid and its two (1 + 1) associated pyramids

We deduce Lemma 8.

▲^{⋆2} = (n_{[m_{1},...,m_{h}]}^{p})_{m_{1}≥···≥m_{h}≥1} .

Hence, we are now able to compute the generating function.

Theorem 9. The Dirichlet generating functions of espaliers and pyramids are respectively

E_{D}^{e}(s_{1}, …, s_{h}; h) = Z(s_{1}, …, s_{h})^{2}, E_{D}^{p}(s_{1}, …, s_{h}; h) = Z^{▲}(s_{1}, …, s_{h})^{2}.  (9)

The ordinary generating functions of the espaliers and the pyramids are respectively

\begin{matrix}E^{e}(x_{1}, …, x_{h}; h) = S_{△}^{⋆2} = \\ ∑_{n_{1}≥···≥n_{h}≥1} \frac{x_{1}^{n_{1}} ⋯ x_{h}^{n_{h}}}{(1 − x_{1}^{n_{1}})(1 − x_{1}^{n_{1}}x_{2}^{n_{2}}) ⋯ (1 − x_{1}^{n_{1}} ⋯ x_{h}^{n_{h}})}, \end{matrix}  (10)

\begin{matrix}E^{p}(x_{1}, …, x_{h}; h) = S_{▲}^{⋆2} = \\ ∑_{n_{1}≥···≥n_{h}≥1} \frac{(n_{1} − n_{2} + 1) ⋯ (n_{h−1} − n_{h} + 1)x_{1}^{n_{1}} ⋯ x_{h}^{n_{h}}}{(1 − x_{1}^{n_{1}})^{2}(1 − x_{1}^{n_{1}}x_{2}^{n_{2}})^{2} ⋯ (1 − x_{1}^{n_{1}} ⋯ x_{h−1}^{n_{h−1}})^{2}(1 − x_{1}^{n_{1}} ⋯ x_{h}^{n_{h}})}. \end{matrix}  (11)

So we deduce

Corollary 10.

E^{e}(x; h) = ∑_{n_{1}≥···≥n_{h}≥1} \frac{x^{n_{1}+···+n_{h}}}{(1 − x^{n_{1}})(1 − x^{n_{1}+n_{2}}) ⋯ (1 − x^{n_{1}+···+n_{h}})},

E^{p}(x; h) =

∑_{n_{1}≥···≥n_{h}≥1} \frac{(n_{1} − n_{2} + 1) ⋯ (n_{h−1} − n_{h} + 1)x^{n_{1}+···+n_{h}}}{(1 − x^{n_{1}})^{2}(1 − x^{n_{1}+n_{2}})^{2} ⋯ (1 − x^{n_{1}+···+n_{h−1}})^{2}(1 − x^{n_{1}+···+n_{h}})}.

4.2 Higher dimensions

In this section, we investigate the coefficients n_{v}^{t}(d) (t ∈ {e, p}). The iteration of the transformations presented above gives the generating functions of the same objects in higher dimension. Hence, the generating function of the number of espaliers (resp. pyramids) whose plateaus have volume v_{1}, …, v_{h} in dimension d + 1 is given by △^{⋆d} (resp. ▲^{⋆d}).

Therefore the Dirichlet generating function of n_{[m_{1},...,m_{n}]}^{t}(d) is

E_{D}^{t}(s_{1}, …, s_{h}) = Z^{t}(s_{1}, …, s_{h})^{d},  (12)

with Z^{e} = Z and Z^{p} = Z^{▲}. We now consider d as a formal parameter. We have

\frac{∂^{k}}{∂d^{k}} E_{D}^{t}(s_{1}, …, s_{h}) = Z^{t}(s_{1}, …, s_{h})^{d} log (Z^{t}(s_{1}, …, s_{h}))^{k} .

We observe that Z^{t}(s_{1}, …, s_{h}) = 1+Z̃^{t}(s_{1}, …, s_{h}) where Z̃^{t}(s_{1}, …, s_{h}) = ∑_{\begin{matrix}n_{1}≥2 \\ n_{1}≥···≥n_{h}≥1 \end{matrix}} \frac{(∗)}{n_{1}^{s_{1}} ⋯ n_{h}^{s_{h}}};

here (∗) denotes coefficients depending on n_{1}, …, n_{h} and the type t of the objects. It follows that

\frac{∂^{k}}{∂d^{k}} E_{D}^{t}(s_{1}, …, s_{h}) = ∑_{\begin{matrix}n_{1}≥2^{k} \\ n_{1}≥···≥n_{h}≥1 \end{matrix}} \frac{(□)}{n_{1}^{s_{1}} ⋯ n_{h}^{s_{h}}};  (13)

(□) also denotes coefficients. We deduce from (13) that n_{[v_{1},...,v_{h}]}^{t}(d) is a polynomial in d whose degree is at most log_{2}(v_{1}). Furthermore,

deg (n_{[2^{k},1,...,1]}^{t}(d)) = k.  (14)

Hence, we have

Theorem 11. The number n_{v}^{e}(d) of (d + 1)-espaliers of volume v and the number n_{v}^{p}(d) of (d + 1)-pyramids of volume v are both polynomials in d of degree ⌊log_{2}(v)⌋.

Proof. Since

n_{v}^{t}(d) = ∑_{h≥1} ∑_{v_{1}≥···≥v_{h}≥1} n_{[v_{1},...,v_{h}]}^{t}(d),

(13) implies that deg(n_{v}^{t}(d)) ≤ ⌊log_{2}(v)⌋. From (14), the inverse inequality holds if

E_{( 2^{⌊log_{2} v⌋}, \underbrace{1, …, 1}_{(v−2^{⌊log_{2} v⌋})×})} ≠ ∅.

This is obviously the case since it suffices to consider an espalier such that the volume of the first plateau is 2^{⌊log_{2} v⌋} and with v − 2^{⌊log_{2} v⌋} other plateaus consisting of one cell.

5 General construction

A (1 + 1)-dimensional object is a finite set of cells (x, y) such that x ∈ ℕ and y ∈ ℤ. If O is a (1+1)-dimensional object, its i-th stratum will be the set L_{i}(O) := {(i, y) ∈ O}. From a pair of (1+1)-dimensional objects (O_{1}, O_{2}), we construct a (2+1)-dimensional object that is a set of cells (x, y, z) with x ∈ ℕ and y, z ∈ ℤ: G(O_{1}, O_{2}) := {(x, y, z) : (x, y) ∈ O_{1}, (x, z) ∈ O_{2}). The i-th stratum of a (2 + 1)-dimensional object will be defined by L_{i}(O) := {(i, y, z) ∈ O}. The height of such an object is h(O) = max{i : L_{i}(O) ≠ ∅}. The multivolume mv(O) of a (1 + 1)- or (2 + 1)-dimensional object O is the sequence of the cardinals of its strata.

Note that if mv(O_{1}) = [v_{1}, ⋯, v_{h}] and mv(O_{2}) = [v′_{1}, ⋯, v′_{h′}] then

mv(G(O_{1}, O_{2})) = [v_{1}v′_{1}, …, v_{min(h,h′)}v′_{min(h,h′)}].

This property is obtained easily by examining the construction of each stratum (see Figure 8 for an example). An object O is said to be plain if for any 1 ≤ i ≤ h(O), the stratum L_{i}(O) is not empty. Let A = ⋃_{u} A_{u} and B = ⋃_{v} B_{v} be two families of (1+1)-dimensional plain objects of height h graded by multivolume and such that A_{u} and B_{v} are finite for any multivolume u and v. Let also set A = (a_{v_{1},...,v_{h}})_{v_{1},...,v_{h}} and B = (b_{v_{1},...,v_{h}})_{v_{1},...,v_{h}} with a_{v_{1},...,v_{h}} = #A_{[v_{1},...,v_{h}]} and b_{[v_{1},...,v_{h}]} = #B_{[v_{1},...,v_{h}]}. The set G(A, B) = G(O_{1}, O_{2}) : {O_{1} ∈ A_{u}, O_{2} ∈ B_{u}} contains only plain objects of size h. Furthermore, it is graded by multivolume (G(A, B) = ⋃_{v} G_{v}) and the sequence G = (#G_{[v_{1},...,v_{h}]})_{v_{1},...,v_{h}≥1} is given by G = A ⋆ B.

Figure 8: Construction of a stratum

Let us recall the operation of extrusion that appears in a geometric model for the validation of real-time applications [10,18]. It is defined in the following way:

\begin{aligned}Extr : & ℝ^{m} & × & ℝ & → & ℝ^{m+1} \\ & (x − 1, ⋯, x_{m}) & , & y & → & (x − 1, ⋯, x_{m}, y) \end{aligned}

The extrusion generates a volume from its base according a direction of construction. Thus, the classes of polycubes on which we can apply our method are obtained (as in the

geometric model of real-time validation [10,18]) from two polyominoes that we extrude and intersect. However, not all the families of polyominoes can be considered.

Nevertheless it suffices that each polyomino be horizontally connected. Consider first the family of directed^{6} plateau polycubes [7, 9]. The generating function of the number P_{v,h} of directed plateau polycubes of height h and volume v is

∑_{v,h} P_{v,h}p^{v}t^{h} = \frac{tτ(p)}{1 − tpτ′(p)}  (15)

where τ(x) = ∑_{k≥1} \frac{x^{k}}{1−x^{k}} denotes the generating function of the number τ(n) of divisors of an integer n [7, 9]. Formula 15 can be generalized in dimension d + 1. If P_{v,h}^{(d+1)} denotes the number of directed plateau (d + 1)-polycubes of height h and volume v, we have

∑_{v,h} P_{v,h}^{(d+1)}p^{v}t^{h} = \frac{tτ^{(d+1)}(p)}{1 − tpτ^{(d+1)}′(p)}

where τ^{(d+1)}(x) = (\frac{x}{1−x})^{∗d}.

6A polycube is said to be directed if each of its cells can be reached from a distinguished cell, called the root, by a path only made of East, North and Ahead steps.

Figure 9: A plateau polycube from two horizontally convex directed polyominoes

Let us show how to recover (15) with our method. First we remark that each directed plateau polycube is obtained from two horizontally convex (i.e., each horizontal line meets the polyomino in a single line segment) directed (i.e., each cell can be reached from (0, 0) by moves up or right one cell, without leaving the polyomino) polyominoes. The generating function of horizontally convex directed polyominoes of multivolume [v_{1}, …, v_{h}] is

∑_{v_{1},...,v_{h}≥1} v_{1} ⋯ v_{h−1}x_{1}^{v_{1}} ⋯ x_{h}^{v_{h}} = \frac{x_{1} ⋯ x_{h}}{(1 − x_{1})^{2} ⋯ (1 − x_{h−1})^{2}(1 − x_{h})}

and the convolution yields

∑_{v_{1},...,v_{h}≥1} v_{1} ⋯ v_{h−1} \frac{x_{1}^{v_{1}} ⋯ x_{h}^{v_{h}}}{(1 − x^{v_{1}})^{2} ⋯ (1 − x_{h−1}^{v_{h−1}})^{2}(1 − x_{h}^{v_{h}})}.

Setting x_{1} = ⋯ = x_{h−1} = p and x_{h} = pω, we obtain the generating function with respect to the volume (p) and the volume of the highest stratum (ω):

∑_{v_{1},...,v_{h}≥1} v_{1} ⋯ v_{h−1} \frac{p^{v_{1}+···+v_{h−1}+v_{h}} ω^{v_{h}}}{(1 − p^{v_{1}})^{2} ⋯ (1 − p^{v_{h−1}})^{2}(1 − (pω)^{v_{h}})} = (pτ′(p))^{h−1} τ(pω).

We recover (15) by summing over h and setting ω = 1 in

∑_{h≥1} t^{h} (pτ′(p))^{h−1} τ(pω) = \frac{tτ(pω)}{1 − tpτ′(p)} [7].  (16)

By a similar reasoning, (15) can be generalized in dimension d + 1. If P_{v,h}^{(d+1)} denotes the number of directed plateau (d + 1)-polycubes of height h and volume v, we have

Proposition 12.

∑_{v,h} P_{v,h}^{(d+1)}p^{v}t^{h} = \frac{tτ^{(d+1)}(p)}{1 − tpτ^{(d+1)}′(p)}

where τ^{(d+1)}(x) = (\frac{x}{1−x})^{∗d}.

The Dirichlet generating function of directed plateau polycubes of height h is Ξ(s_{1} −

1, …, s_{h−1} − 1, s_{h})^{2} with Ξ(s_{1}, …, s_{h}) = ∑_{v_{1},...,v_{h}≥1} \frac{1}{v_{1}^{s_{1}} ⋯ v_{h}^{s_{h}}}.

We give briefly a second example by computing the generating function of the number of all plateau polycubes (without constraint). Plateau polycubes of height h are in one-to-one correspondence with pairs of horizontally convex polyominoes of height h. The generating function of horizontally convex polyominoes of height h is

∑_{v_{1},...,v_{h}≥1}(v_{1} + v_{2} − 1) ⋯ (v_{h−1} + v_{h} − 1)x_{1}^{v_{1}} ⋯ x_{h}^{v_{h}}

= α_{h} (x_{1}, \frac{x_{2}}{x_{1}} , …, \frac{x_{h}x_{h−2} ⋯}{x_{h−1}x_{h−3} ⋯})

with

α_{h}(t_{1}, …, t_{h}) = t_{1}^{2} ⋯ t_{h−1}^{2} \frac{d}{dt_{1}} ⋯ \frac{d}{dt_{h−1}} \frac{t_{1}···t_{h}}{(1−t_{1})(1−t_{1}t_{2})(1−t_{2}t_{3})···(1−t_{h−1}t_{h})}.

Using the same method as above, we obtain the following formula for the generating function of the number of plateau polycubes counted by height and volume:

\begin{matrix}∑_{h≥1} t^{h} ∑_{n_{1},...,n_{h}}(n_{1} + n_{2} − 1) ⋯ (n_{h−1} + n_{h} − 1)α_{h}(p^{n_{1}}, p^{n_{2}−n_{1}}, …, p^{n_{h}−n_{h−1}+n_{h−2}−···}) = \\ t ( ∑_{n_{1},m_{1}≥1} p^{n_{1}m_{1}} (1 + t ∑_{n_{2},m_{2}≥1}(n_{1} + n_{2} − 1)(m_{1} + m_{2} − 1)p^{n_{2}m_{2}} (1 + t ∑ ⋯))) . \end{matrix}

6 Conclusion

In this paper, we have presented a new enumeration method for polycubes in connection with the Lambert transform. Complementary to the single one known so far [9], it has permitted to investigate two new classes of polycubes, espaliers and pyramids. With this method, one can also recover known results. In particular, we gave two expressions for the generating function of the plateau polycubes. Although these expressions are not closed, they can be used to enumerate this family far enough. Nevertheless, the underlying combinatorics remains to be understood. For instance, a straightforward examination of the generating function of the horizontally convex polyominoes [28, p. 153], ∑_{h} t^{h}α_{h}(p, 1, p, 1, …) =

\frac{pt(1 − p)^{3}}{(1 − p)^{4} − pt(1 − p − p^{2} + p^{3} + p^{2}t)}, reveals interesting connections with Delannoy numbers

D_{n−k,k}, which count the number of lattice paths from (0, 0) to (n, k) using steps (1, 0), (0, 1), (1, 1) (see sequence \underline{A008288} from the OEIS [25]) and whose generating function is

∑_{n,k} D_{n,k}x^{n}y^{k} = (1−x−y−xy)^{−1}. More precisely, α_{h}(p, 1, p, 1, …) = \frac{p^{h}}{(1 − p)^{2h−1}} ∑_{k=0}^{h−1} D_{h−k−1,k}p^{k}.

It is natural to ask the question of analogous connections for higher dimensions.

One of the tricks allowing one to enumerate polyominoes is to consider the statistic of the area of the highest stratum. For instance, the generating function of parallelogram polyominoes is deduced from functional equations involving the variable associated with this statistic [15, Example IX.14, p. 660]. Formula (16) shows that this strategy is compatible with our method at least in certain cases. It should be interesting to see if one can adapt the “adding a slice” method for computing functional equations to the generating functions of some families of polycubes obtained from two polyominoes. Perhaps this method could be adapted by introducing new variables for the width and the length of the highest plateau as suggested by Equation (16).

Finally, note that numerical investigations lead us to the promising conjecture below. We define a new family of objects called canyons as follows: A polycube P is a canyon polycube if the following conditions are satisfied:

• if the cell with coordinates (a, b, c) belongs to P, then (a − 1, b, c) ∈ P (for a > 1);

• for all (a, b, c) ∈ P such that a = max {a′, (a′, b, c) ∈ P }, either a = max {a′, (a′, b′, c) ∈ P } or a = max {a′, (a′, b, c′) ∈ P }.

An example of canyon is given in Figure 10.

Figure 10: A canyon polycube

Let n_{v}^{c} denote the number of canyons of volume v (sequence \underline{A239257} from the OEIS [25]). Then we have

Conjecture 13.

n_{v}^{c} ∼_{+∞} 2^{v} + \frac{10 − 2\sqrt{5}}{5}ϕ^{v} + αβ^{v}

where ϕ = \frac{1+\sqrt{5}}{2} is the golden ratio, β = 1.51287 … is the unique positive real zero of the polynomial x^{4} − x^{3} − x^{2} + x − 1 and α = 0.94695 . . ..

This conjecture follows from numerical evidence obtained by computing the number of canyons up to volume 510 and using Simon Plouffe’s inverse symbolic calculator [23].

References

[1] G. Aleksandrowicz and G. Barequet, Counting d-dimensional polycubes and nonrectangular planar polyominoes, Internat. J. Comput. Geom. Appl. 19 (2009), 215–229.

[2] M. Baake and U. Grimm, Combinatorial problems of (quasi-)crystallography, in H.- R. Trebin, ed., Quasicrystals — Structure and Physical Properties, Wiley-VCH, 2002, pp. 160–171.

[3] E. A. Bender and D. E. Knuth, Enumeration of plane partitions, J. Combin. Theory Ser. A 13 (1972), 40–54.

[4] M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996), 4–25.

[5] D. M. Bressoud, Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, Cambridge University Press, 1999.

[6] S. R. Broadbent and J. M. Hammersley, Percolation processes; I. Crystals and mazes, Proc. Cambridge Philos. Soc. 53 (1957), 629–641.

[7] J.-M. Champarnaud, Q. Cohen-Solal, J.-Ph. Dubernard, and H. Jeanne, Enumeration of specific classes of polycubes, Electron. J. Combin. 20 (4) (2013), Paper P26.

[8] J.-M. Champarnaud, J.-Ph. Dubernard, and H. Jeanne, An efficient algorithm to test whether a binary and prolongeable language is geometrical, Internat. J. Found. Comput. Sci. 20 (2009), 763–774.

[9] J.-M. Champarnaud, J.-Ph. Dubernard, and H. Jeanne, A generic method for the enumeration of various classes of directed polycubes, Discrete Math. Theor. Comput. Sci. 15 (2013), 183–200.

[10] A. Choquet-Geniet and G. Largeteau, Real-time scheduling using regularity criteria and a geometrical approach, Int. J. Critical Computer-Based Systems, 2 (2011), 266–287.

[11] H. Cohn, M. Larsen, and J. Propp, The shape of a typical boxed plane partition, New York J. Math. 4 (1998), 137–165.

[12] C. Costermans and V. Hoang Ngoc Minh, Noncommutative algebra, multiple harmonic sums and applications in discrete probability, J. Symbolic Comput. 44 (2009), 801–817.

[13] J.  Cresson,  S.  Fischler,  and  T.  Rivoal,  Séries  hy-
pergéométriques  multiples  et  polyzêtas,  preprint,  available  at

    http://hal.archives-ouvertes.fr/hal-00101376/PDF/CFRalgo-HAL.pdf.

[14] S. Feretic, A q-enumeration of convex polyominoes by the festoon approach, Theoret. Comput. Sci. 319 (2004), 333–356.

[15] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[16] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford University Press, 1980.

[17] G. Largeteau and D. Geniet, Quantification du taux d’invalidité d’applications tempsréel à contraintes strictes, Technique et Science Informatiques 27 (2008), 589–625.

[18] G. Largeteau, D. Geniet, and E. Andres, Discrete geometry applied in hard real-time systems validation, in Discrete Geometry for Computer Imagery, Lect. Notes in Comp. Sci., Vol. 3429, Springer, 2005, pp. 23–33.

[19] W. F. Lunnon, Counting multidimensional polyominoes, Computer J. 18 (1975), 366– 367.

[20] I. G. MacDonald, Symmetric Functions and Hall Polynomials, Oxford Mathematical Monographs, Oxford University Press, 1995.

[21] P. A. MacMahon, Combinatory Analysis, Cambridge University Press, 1915–1916.

[22] A. F. Möbius, Über eine besondere Art von Umkehrung der Reihen, J. Reine Angew. Math., 9 (1832), 105–123.

[23] ISC, Inverse Symbolic Calculator, http://isc.carma.newcastle.edu.au/.

[24] G.-C. Rota, On the foundations of combinatorial theory I: theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368.

[25] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences,

    http://oeis.org.

[26] H. N. V. Temperley, Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules, Phys. Rev. 103 (1956), 1–16.

[27] R. P. Stanley, Enumerative Combinatorics 2, Chapter 7, Cambridge Studies in Advanced Math, Wadsworth & Brooks/Cole Advanced Books & Software, 2001.

[28] H. S. Wilf, Generatingfunctionology, Academic Press, 1994.

2010 Mathematics Subject Classification: Primary 05B50; Secondary 05A15. Keywords: polycube, Dirichlet convolution, Dirichlet generating function, Lambert transform.

(Concerned with sequences \underline{A008288}, \underline{A229914}, \underline{A229915}, \underline{A239257}.)

Received June 19 2015; revised version received August 12 2015; October 8 2015; October 20 2015. Published in Journal of Integer Sequences, November 25 2015.

Return to Journal of Integer Sequences home page.