\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} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \restylefloat{figure} \usepackage{cite} \usepackage{lipsum} \usepackage{pgf} \usepackage{tikz} \usetikzlibrary{arrows,automata,plothandlers,positioning,calc} %\usepackage[normalem]{ulem} \newcommand{\bigsum}{\displaystyle\sum\limits} \newcommand{\bigprod}{\displaystyle\prod\limits} \def\N{{\mathbb N}} \def\indentit{\,\mbox{l\hspace{-0.55em}1}} \newcommand{\cellule}[2]{ \fill[rounded corners, color=black!50] (#1,#2) +(.02,.02 ) -- +(.02,.98) -- +(.98,.98) -- +(.98,.02) -- cycle; } \newcommand{\rcellule}[2]{ \fill[rounded corners, color=red] (#1,#2) +(.02,.02 ) -- +(.02,.98) -- +(.98,.98) -- +(.98,.02) -- cycle; } \newcommand{\gcellule}[2]{ \fill[rounded corners, color=green] (#1,#2) +(.02,.02 ) -- +(.02,.98) -- +(.98,.98) -- +(.98,.02) -- cycle; } \newcommand{\Mcube}[3]{ \fill[color = black!20] (#1,#2,#3) +(0,1,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,1,0) -- cycle; \fill[color = black!30] (#1,#2,#3) -- +(0,1,0) -- +(1,1, 0) -- +(1,0,0) -- cycle; \fill[color = black!50] (#1,#2,#3) +(1,0,0) -- +(1,1,0) -- +(1,1,-1) -- +(1,0,-1) -- cycle; \draw[color = black!80] (#1,#2,#3) -- +(0,1) -- +(1,1) - - +(1,0) -- cycle; \draw[rounded corners,color = black!80] (#1,#2,#3) + (0 .025,.94,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,0,-1) -- +(1,0,0); \draw[color = black!80] (#1,#2,#3) + (0,1,0) -- +(0,1,-1 ) -- +(1,1,-1) -- +(1,0,-1) -- +(1,0,0); \draw[color = black!80] (#1,#2,#3) +(1,1,0) -- +(1,1,-1) ; } \newcommand{\cube}[3]{ \fill[color = black!20] (#1,#2,#3) +(0,1,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,1,0) -- cycle; \fill[color = black!30] (#1,#2,#3) -- +(0,1,0) -- +(1,1, 0) -- +(1,0,0) -- cycle; \fill[color = black!50] (#1,#2,#3) +(1,0,0) -- +(1,1,0) -- +(1,1,-1) -- +(1,0,-1) -- cycle; \draw[color = black!80] (#1,#2,#3) -- +(0,1) -- +(1,1) - - +(1,0) -- cycle; \draw[rounded corners,color = black!80] (#1,#2,#3) + (0 .025,.94,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,0,-1) -- +(1,0,0); \draw[color = black!80] (#1,#2,#3) + (0,1,0) -- +(0,1,-1 ) -- +(1,1,-1) -- +(1,0,-1) -- +(1,0,0); \draw[color = black!80] (#1,#2,#3) +(1,1,0) -- +(1,1,-1) ; } \newcommand{\tcube}[3]{ \draw[color = black!20] (#1,#2,#3) +(0,1,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,1,0) -- cycle; \draw[color = black!30] (#1,#2,#3) -- +(0,1,0) -- +(1,1, 0) -- +(1,0,0) -- cycle; \draw[color = black!50] (#1,#2,#3) +(1,0,0) -- +(1,1,0) -- +(1,1,-1) -- +(1,0,-1) -- cycle; \draw[color = black!80] (#1,#2,#3) -- +(0,1) -- +(1,1) - - +(1,0) -- cycle; \draw[rounded corners,color = black!80] (#1,#2,#3) + (0 .025,.94,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,0,-1) -- +(1,0,0); \draw[color = black!80] (#1,#2,#3) + (0,1,0) -- +(0,1,-1 ) -- +(1,1,-1) -- +(1,0,-1) -- +(1,0,0); \draw[color = black!80] (#1,#2,#3) +(1,1,0) -- +(1,1,-1) ; \draw[color = black!80] (#1,#2,#3-1) -- +(0,1) -- +(1,1) - - +(1,0) -- cycle; \draw[color = black!80] (#1,#2,#3) +(0,0,0) -- +(0,1,0) -- +(0,1,-1) -- +(0,0,-1) -- cycle; } \newcommand{\bcube}[3]{ \fill[color = red] (#1,#2,#3-1) -- +(0,1) -- +(1,1) - - +(1,0) -- cycle; } \newcommand{\lcube}[3]{ \fill[color = green] (#1,#2,#3) +(0,0,0) -- +(0,1,0) -- +(0,1,-1) -- +(0,0,-1) -- cycle; } \newcommand{\bluecube}[3]{ \fill[color = blue!20] (#1,#2,#3) +(0,1,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,1,0) -- cycle; \fill[color = blue!30] (#1,#2,#3) -- +(0,1,0) -- +(1,1,0 ) -- +(1,0,0) -- cycle; \fill[color = blue!50] (#1,#2,#3) +(1,0,0) -- +(1,1,0) - - +(1,1,-1) -- +(1,0,-1) -- cycle; \draw[color = blue!80] (#1,#2,#3) -- +(0,1) -- +(1,1) -- +(1,0) -- cycle; \draw[rounded corners,color = black!80] (#1,#2,#3) + (0 .025,.94,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,0,-1) -- +(1,0,0); \draw[color = blue!80] (#1,#2,#3) + (0,1,0) -- +(0,1,-1) -- +(1,1,-1) -- +(1,0,-1) -- +(1,0,0); \draw[color = blue!80] (#1,#2,#3) +(1,1,0) -- +(1,1,-1); } \def\R{{\mathbb R}} \def\C{{\mathbb C}} \def\Z{{\mathbb Z}} \def\N{{\mathbb N}} \def\Y{{\mathbb Y}} \def\P{{\mathbb P}} \def\E{{\mathbb E}} \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} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \vskip .2 in %\usepackage[latin1]{inputenc} %\usepackage[english]{babel} %\usepackage[T1]{fontenc} \begin{center} \vskip 1cm{\LARGE\bf Enumeration of Polycubes \\ \vskip .1in and Dirichlet Convolutions } \vskip 1cm \large C. Carr\'e, N. Debroux, M. Deneufch\^atel, J.-Ph. Dubernard, \\ C. Hillairet, J.-G. Luque, and O. Mallet\\ LITIS \\ Universit\'e de Rouen\\ Facult\'e des Sciences et Techniques - Madrillet\\ Avenue de l'Universit\'e \\ 76801 St Etienne du Rouvray CEDEX \\ France \\ \href{mailto:christophe.carre@univ-rouen.fr}{\tt christophe.carre@univ-rouen.fr}\\ \href{mailto:matthieu.deneufchatel@univ-rouen.fr}{\tt matthieu.deneufchatel@univ-rouen.fr}\\ \href{mailto:jean-philippe.dubernard@univ-rouen.fr}{\tt jean-philippe.dubernard@univ-rouen.fr}\\ \href{mailto:jean-gabriel.luque@univ-rouen.fr}{\tt jean-gabriel.luque@univ-rouen.fr}\\ \href{mailto:olivier.mallet@univ-rouen.fr}{\tt olivier.malle@univ-rouen.frt}\\ \href{mailto:noemie.debroux@insa-rouen.fr}{\tt noemie.debroux@insa-rouen.fr}\\ \href{mailto:conrad.hillairet@insa-rouen.fr}{\tt conrad.hillairet@insa-rouen.fr} \end{center} \vskip .2 in \begin{abstract} We present a new method for polycube enumeration, in connection with the multi-indexed Dirichlet convolution, which we illustrate with the study of two families of polycubes, namely pyramids and espaliers. \end{abstract} \section{Introduction} \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.7] \begin{scope}[xshift = 0cm] \foreach \x/\y/\z in {0/0/0,1/0/0,2/0/0,3/0/0,1/1/0,2/1/-1,2/1/0,3/1/0,4/1/0,0/2/0,1/2/0,2/2/-1,2/2/0,4/2/-1,4/2/0,0/3/0,5/2/-1,1/0/1,3/1/1,4/1/1}{ \cube{\x}{\y}{\z} } \end{scope} \end{tikzpicture} \caption{A polycube} \label{polycube1} \end{figure} In the Cartesian plane $\mathbb{Z}^2$, a \emph{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 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\cite{Bo96,Fer04}. Polyominoes have a 3-dimensional equivalent: the 3-dimensional polycubes (or polycubes for short) \cite{Lu75} (see Figure \ref{polycube1}). Now if we consider that an elementary cell is a unit cube, then a \emph{polycube} is a face-connected finite set of elementary cells defined up to a translation in $\mathbb{Z}^3$. Like polyominoes, polycubes appear in statistical physics, more precisely in the phenomenon of percolation \cite{BH57}. 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$ \cite{Lu75} and the last one (to our knowledge) in 2006, up to $n=18$ \cite{AB06}. 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\geq 3$; $d$-dimensional polycubes (or $d$-polycubes for short) are used in an efficient model of real-time validation \cite{LG08}, as well as in the representation of finite geometrical languages \cite{CDJ09}. 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 \cite{BK72,CLP98,Bres99,Stan01}. For instance, an expression of the generating function of planar partitions with respect to number of peaks has been given by MacMahon \cite{MacMahon}, Bender and Knuth \cite{BK72} and Bressoud and Propp \cite{Bres99}; it is equal to \begin{center} $\bigsum_{n} PL(n) q^n = \bigprod_{k \geq 0} \dfrac{1}{(1-q^k)^k}$ \end{center} We also can give another result of MacMahon \cite{MacMahon}, reshaped by MacDonald \cite{Macdonald}. It determines the number of plane partitions that are included in a parallelepiped of dimensions $a \times b \times c$ and is equal to \begin{center} $PL(a,b,c) = \bigprod_{i=1}^a \bigprod_{j=1}^b \bigprod_{k=1}^c \dfrac{i+j+k-1}{i+j+k-2}$ \end{center} 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 \cite{ChamparnaudDJ13}. 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 $$VCD(t,p) = \dfrac{tp (p-1) (1-3p+p^2)}{1-6p+11p^2-6p^3+p^4-t (p-2p^2+2p^3)}\mbox{\cite{ChamparnaudDJ13}}.$$ 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 \ref{families}, 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 \ref{convolution}, we extend the convolution product to multi-indexed families and we give an interpretation in terms of ordinary and Dirichlet generating functions. Furthermore, we point out the connection with espaliers. In Section \ref{counting}, 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$\footnote{$d$ is the dimension of the pedestal, that is the dimension of the ambient space minus $1$.} is a polynomial in $d$ of degree $\lfloor \log_2(v)\rfloor$. Finally, in Section \ref{general}, we explain how to apply our method to other families of polycubes. \section{Some families of polycubes}\label{families} \subsection{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 \cite{BK72,CLP98,Bres99,Stan01}. Recently, a new method has made it possible to enumerate several families of polycubes (in dimension $3$ and greater than $3$) \cite{ChamparnaudDJ13}. It is worthwhile noticing that it is the investigation of plateau and parallelogram polycubes that motivated the design of this method \cite{CohenSolal}. 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 \cite{CohenSolal,ChamparnaudDJ13}. A polyomino is said to be \emph{row-convex} (resp.~\emph{column-convex}) if its intersection with any horizontal (resp.\ vertical) strip is convex. It is said to be \emph{directed} if each of its cells can be reached from a distinguished cell, called the \emph{root}, by a path only made of East and North steps. \subsection{Definitions} We will consider polycubes as discrete objects which are embedded in the three-dimensional discrete lattice $\Z^3$. Each point of $\Z^3$ will be represented by the triplet of its coordinates and lexicographically ordered. An atomic \emph{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 $\mathcal P$ of cells such that its smallest cell is $(0,0,0)$. The \emph{volume} of a polycube is the number of its atomic cells. The \emph{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$, \emph{i.e.}, $\mathrm{height}(P):=\max\{x:(x,y,z)\in P\}-\min\{x:(x,y,z)\in P\}+1$. For instance, the height of the polycube in Figure \ref{polycube1} is $4$. A very particular convex polycube is the \emph{horizontal plateau}: it is a horizontal parallelepiped of height 1. To simplify the notation, let us call it a \emph{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 \cite{CohenSolal}. The first family is a subclass of plane partitions\cite{CLP98,Bres99,Stan01}. A \emph{pyramid} polycube (or \emph{pyramid} for short) is obtained by gluing together horizontal plateaus in such a way that \begin{itemize} \item $(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\geq 0$. \item 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. \end{itemize} Note that the plateau made of cells whose first coordinate is $k$ is called $(k+1)$-th plateau. \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.6] \begin{scope}[xshift = 0cm] \foreach \x in {0,1,2,3}{ \foreach \z in {0,1,2,3,4}{ \cube{\x}{0}{\z} } } \foreach \x in {1,2,3}{ \foreach \z in {1,2,3}{ \cube{\x}{1}{\z} } } \foreach \x in {1,2}{ \foreach \z in {2}{ \cube{\x}{2}{\z} } } \foreach \x in {1,2}{ \foreach \z in {2}{ \cube{\x}{3}{\z} } } \cube{2}{4}{2} \end{scope} \end{tikzpicture} \caption{A pyramid} \label{pyramid1} \end{figure} An \emph{espalier} polycube is a special pyramid such that for all $a$, the $(a+1)$-th plateau contains the cell $(a,0,0)$. \subsection{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 \seqnum{A229914} and \seqnum{A229915} in the OEIS \cite{Sloane}. This statistic can be refined by the height (i.e., the number of plateaus) and the volume of each plateau. If $\mathbb P$ is a pyramid of height $h$, let $mv(\mathbb P)=(v_1,\ldots,v_h)$ with $v_1\geq v_2\geq\cdots \geq v_h>0$ denote the sequence of the volumes of its plateaus. Let $\lambda=(\lambda_1,\ldots,\lambda_h)$, such that $\lambda_1 \geq \cdots \geq \lambda_h>0$, be a partition. We define $E_\lambda$ as the set of espaliers $\E$ such that $mv(\E)=\lambda$. We use the following notation where $t=e$ if the corresponding quantity involves espalier polycubes and $t=p$ if it involves pyramid polycubes: \begin{itemize} \item $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$; \item there are $n^t_{\left[ v_1 , \ldots , v_h \right]}$ objects such that each plateau has volume $v_i$, for $i$ such that $1 \leq i \leq h$, if $v_1 \geq \cdots \geq v_h$. \end{itemize} By convention, there is no espalier nor pyramid of volume $0$: $n^{t}_0= 0$. The number $n^t_{i,j,h,v}$ of considered polycubes (espaliers or pyramids) of volume $v$, height $h$ and such that their largest plateau has dimensions $i\times j$ is given by the recurrence $ \displaystyle n_{i,j,h,v}^t= \sum_{a,b}\alpha^t_{a,b}n_{i+a,j+b,h-1,v-ij}^t $ with $\alpha^e_{a,b}=1,\alpha^p_{a,b}=(a+1)(b+1)$ and $n^t_{i,j,1,v}=\delta_{ij,v}$\footnote{The indices $i+a$ and $j+b$ means that the plateau at height $h-1$ is bigger than the one at height $h$.}. Let ${\cal E}^t(x;h) := \sum_{v \geq 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 ${\cal E}^t(x) := \sum_{v \geq 1} n_{v}^t x^v=\sum_h {\cal E}^t(x;h)$. Taking into account the distribution of the volume among the levels, one gets \[\displaystyle{\cal E}^t (x_1 , \ldots , x_h ; h) = \sum_{m_1 \geq \cdots \geq m_h} n^t_{\left[ m_1 , \ldots , m_h \right]} x_1^{m_1} \cdots x_h^{m_h}. \] We also present results about Dirichlet generating functions, which are defined by \[ {\cal E}_{\cal D}^t (s_1 , \ldots , s_h ; h) = \sum_{m_1 \geq \cdots \geq m_h} \frac{n^t_{[m_1,\ldots,m_h]}} {m_1^{s_1} \cdots m_h^{s_h}}. \] It is interesting to note that the limit $\lim\limits_{h \to \infty} x^{-h} {\cal 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 \emph{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 \ref{espalier1} 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.\] \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.5] \begin{scope}[xshift = 0cm] \foreach \x in {0,1,2,3}{ \foreach \z in {0,1,2,3,4}{ \cube{\x}{0}{\z} } } \foreach \x in {0,1,2}{ \foreach \z in {0,1,2}{ \cube{\x}{1}{\z} } } \foreach \x in {0,1}{ \foreach \z in {0}{ \cube{\x}{2}{\z} } } \foreach \x in {0,1}{ \foreach \z in {0}{ \cube{\x}{3}{\z} } } \cube{0}{4}{0} \end{scope} \end{tikzpicture} \begin{tikzpicture}[scale=0.5] \begin{scope}[xshift = 0cm] \foreach \x in {0,1,2,3}{ \foreach \z in {0,1,2,3,4}{ \cube{\x}{0}{\z} } } \cube{0}{1}{1} \cube{0}{1}{2} \foreach \x in {1,2}{ \foreach \z in {0,1,2}{ \cube{\x}{1}{\z} } } \foreach \x in {1}{ \foreach \z in {0}{ \cube{\x}{2}{\z} } } \foreach \x in {1}{ \foreach \z in {0}{ \cube{\x}{3}{\z} } } \end{scope} \end{tikzpicture} \caption{An espalier and its associated quasi-espalier} \label{espalier1} \end{figure} If we extend the notion of quasi-espalier to pyramids, we can also extend the previous result to pyramids. A \emph{ 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\leq a\leq h$. Let $Q^p(x)$ be their generating function with respect to volume. Then $\lim_{h\rightarrow \infty}x^{-h}\mathcal E^p(x,h)$ exists and \begin{equation}\label{pyr2quasipyr}\lim_{h\rightarrow \infty}x^{-h}\mathcal E^p(x,h)=Q^p(x)+\frac{x}{1-x}.\end{equation} 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\leq a\leq n$ is obtained twice: from a pyramid with only two columns $\{(a,0,0):0\leq a\leq n\}$ and $\{(a,1,0):0\leq a\leq m\}$ with $m>n$, and also from a pyramid with only two columns $\{(a,0,0):0\leq a\leq n\}$ and $\{(a,0,1):0\leq a\leq 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 (\ref{pyr2quasipyr}). \subsection{The projection order}\label{order} \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.6] \begin{scope}[xshift = 0cm] \lcube{0}{0}{0}\lcube{0}{0}{1}\lcube{0}{0}{2}\lcube{0}{0}{3}\lcube{0}{0}{4} \lcube{0}{1}{0}\lcube{0}{1}{1}\lcube{0}{1}{2} \lcube{0}{2}{0} \lcube{0}{3}{0} \lcube{0}{4}{0} \foreach \x in {0,1,2,3}{ \bcube{\x}{0}{0} \foreach \z in {0,1,2,3,4}{ \tcube{\x}{0}{\z} } } \foreach \x in {0,1,2}{ \bcube{\x}{1}{0} \foreach \z in {0,1,2}{ \tcube{\x}{1}{\z} } } \foreach \x in {0,1}{ \bcube{\x}{2}{0} \foreach \z in {0}{ \tcube{\x}{2}{\z} } } \foreach \x in {0,1}{ \bcube{\x}{3}{0} \foreach \z in {0}{ \tcube{\x}{3}{\z} } } \bcube{0}{4}{0}\tcube{0}{4}{0} \end{scope} \end{tikzpicture} \caption{One-to-one correspondence between espaliers and pairs of partitions} \label{bijection1} \end{figure} 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 $\mathbb E$ of height $h$ as $\mathbb E_x:=\{(a,0,c):(a,b,c)\in\mathbb E\}$ and $\mathbb E_y:=\{(a,b,0):(a,b,c)\in\mathbb E\}$. These two sets are obviously two Ferrers diagrams which represent two partitions $\lambda_x(\mathbb E)$ and $\lambda_y(\mathbb E)$ of height $h$ (see Figure \ref{bijection1} for an example). Conversely, to each pair of Ferrers diagrams $(\lambda,\mu)$ of height $h$, we associate the $(2+1)$-dimensional figure $\mathbb E^{\lambda,\mu}:=\{(a,b,c):(a,b)\in\lambda, (a,c)\in \mu\}$. It is easy to check that $\mathbb E^{\lambda,\mu}$ is an espalier and \[ \mathbb E^{\lambda,\mu}=\{(a,b,c):(a,b,0)\in \mathbb E^{\lambda,\mu}_y, (a,0,c)\in\mathbb E^{\lambda,\mu}_x\}. \] So, the bijection is straightforward from the construction. We define the relation $\preceq$ on the set of partitions of the same height by $\lambda\preceq\mu$ if there exists $\E\in E_\mu$ such that $\lambda_x(\E)=\lambda$. For instance, Figure \ref{bijection1} illustrates the relations $(4,3,2,2,1) \preceq (20,9,2,2,1)$ and $(5,3,1,1,1)\preceq (20,9,2,2,1)$. \begin{proposition} The relation $\preceq$ is a partial order which generalizes the division order on integers in the following sense: $(d,\ldots,d)\preceq (n,\ldots,n)$ if and only if $d|n$. \end{proposition} Although it is not the purpose of this article, we note that the M\"obius function \footnote{The M\"obius 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 \cite{Rota} for definition and properties of the M\"obius function of a poset.} $\mu^{(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: \begin{equation} \label{a} \mu^{(2)}((1,1),(n,n))=\mu^{(2)}((1,1),(n,1))=\mu(n). \end{equation} where $\mu$ denotes the ``classical'' M\"obius function on integers \cite{Mobius} \footnote{As mentioned by Hardy and Wright\cite{HW}, the M\"obius function occurs implicitly in the early writings of Euler.}. One also has \begin{equation} \mu^{(2)}((1,1),(p,m))=-1 \mbox{ for }p\mbox{ prime and }p>m. \end{equation} Hence, we have \begin{equation} \mu^{(2)}((1,1),(pq,n))=2(n_1+1) \cdots (n_k+1)-1 \text{ when } \begin{cases} p, q\text{ are prime; }\\ n = p_1^{n_1} \cdots p_k^{n_k}; \\ p,q>n. \end{cases} \end{equation} Indeed, \begin{equation} \begin{array}{l} \mu^{(2)}((1,1),(pq,n)) = \\ \hspace*{.3cm}- \sum_{d|n} \left( \underbrace{\mu^{(2)}((1,1),(p,d))}_{-1} + \underbrace{\mu^{(2)}((1,1),(q,d))}_{-1} \right) - \mu^{(2)}((1,1),(1,1)) \end{array} \end{equation} and the divisors of $n$ are obtained by choosing a multi-index $(m_1 , \ldots , m_k) \leq (n_1 , \ldots n_k)$. Now observe that the Dirichlet generating series of $\mu^{(2)}((1,1),(n,k))$ is \[ \sum_{1\leq k\leq n}\frac{\mu^{(2)}((1,1),(n,k))}{ n^{s_1}k^{s_2}}=\left(\sum_{1\leq k\leq n}\frac1{n^{s_1}k^{s_2}}\right)^{-1}.\] Setting $s_2 = 0$ yields \[ \sum_{1\leq n}\frac{\sum_{k=1}^n\mu^{(2)}((1,1),(n,k))}{n^{s_1}}= \sum_{1\leq n}\frac1n\left(\sum_{k=1}^n\mu^{(2)}((1,1),(n,k))\right)\frac1{n^{s_1-1}}. \] Therefore, \begin{equation} \label{b} \sum_{k=1}^n\mu^{(2)}((1,1),(n,k))=n\mu(n). \end{equation} Iterating this relation, one finds \begin{equation} \sum_{n \geq k_1 \geq k_2\geq \cdots \geq k_\ell} \frac{\mu^{(\ell+1)}((1 , \ldots , 1),(n,k_1,\ldots,k_\ell))}{k_1\cdots k_{\ell-1}} = n \mu(n). \end{equation} \subsection{Higher dimensional polycubes} The $(d+1$)-polycubes\footnote{In 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.} are a natural extension of the notion of polyomino to dimension $d+1$, with $d\geq 2$ \cite{CohenSolal,ChamparnaudDJ13}. An atomic \emph{$(d+1)$-cell} is a cube of volume $1$ identified with the smallest coordinates of its vertices in $\Z^{d+1}$. A \emph{$(d+1)$-polycube} is then a $(d+1)$-face-connected finite set of elementary cells, defined up to translation. The \emph{volume} of a $(d+1)$-polycube is the number of its elementary cells. A \emph{$(d+1)$-parallelepiped} is a $(d+1)$-polycube $P$ such that for some $(n_1,\cdots , n_{d+1})\in \mathbb{N}^{d+1}$, any cell with coordinates $(\alpha_1,\cdots , \alpha_{d+1})$ satisfying $0\leq\alpha_k\leq n_k$, $1\leq k\leq d+1$, belongs to $P$. Then a \emph{$(d+1)$-plateau} is a $(d+1)$-parallelepiped of height $1$ (i.e., it is composed of cells of the form $(a,n_1,\cdots , n_{d+1})\in \mathbb{N}^{d+1}$ for a fixed $a$). A \emph{$(d+1)$-pyramid} is a $(d+1)$-polycube obtained by gluing together $(d+1)$-plateaus in such a way that \begin{itemize} \item the cell $(0,0,\ldots,0)$ belongs to the first plateau and each cell with coordinates $(0,n_1,\ldots,n_{d+1})$ belonging to the first plateau is such that $n_1,\ldots,n_{d+1}\geq 0$. \item if the cell with coordinates $(n_0,n_1,\ldots,n_{d+1})$ belongs to the $(n_0+1)$-th plateau ($n_0>0$), then the cell with coordinates $(n_0-1, n_1,\ldots,n_{d+1})$) belongs to the $n_0$-th plateau. \end{itemize} A \emph{$(d+1)$-espalier} is a $(d+1)$-pyramid such that each plateau contains the cell $(n_0,0,\ldots,0)$. As with $(2+1)$-polycubes, we define the following notation: \begin{itemize} \item $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$; \item $n^t_{\left[ v_1 , \ldots , v_h \right]}(d)$ denotes the number of objects of type $t$ such that each plateau has volume $v_i$, for $i$ such that $1 \leq i \leq h$, if $v_1 \geq \cdots \geq v_h$. \end{itemize} 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^t_0(d)=0$ and $n^t_v(0)=1$. Let ${\cal E}^t(x;h,d) = \sum_{v \geq 1} n_v^t(d) x^v$ denote the generating function for the number of espaliers of given height $h$; we also define ${\cal E}^t(x;d) := \sum_{v \geq 1} n_{v}^t x^v=\sum_h {\cal E}^t(x;h,d)$. Taking into account the distribution of the volume among the levels, one sets $${\cal E}^t (x_1 , \ldots , x_h ;h, d) := \sum_{m_1 \geq \cdots \geq m_h} n^t_{\left[ m_1 , \ldots , m_h \right]}(d) x_1^{m_1} \cdots x_h^{m_h},$$ and $$\mathcal E^t_{\mathcal D}:=\sum_{m_1\geq \cdots\geq m_h\geq 1}\frac{n^t_{[m_1,\ldots,m_h]}(d)}{m_1^{s_1}\cdots m_h^{s_h}}.$$ \section{Multivariate versions of the Lambert transform}\label{convolution} \subsection{Convolution and multivariate series} We consider a natural multidimensional generalization of the Dirichlet convolution. For each $h \in \N$, we consider the set multi-indexed families: $\mathcal M_h:=\{(a_{n_1 , \ldots , n_h})_{n_1 , \ldots , n_h\geq 1}: a_{n_1 , \ldots , n_h}\in\C\}$. If $A=(a_{n_1 , \ldots , n_h})$ and $B=(b_{n_1 , \ldots , n_h})$ are two families in $\mathcal M_h$ then let $C = A \star B = \left( c_{n_1 , \ldots , n_h} \right)_{n_1, \ldots, n_h}\in\mathcal M_h$ denote the \emph{multivariate convolution} of $A$ and $B$ defined by \[ c_{n_1 , \ldots , n_h} = \sum_{n_i = m_i p_i,\, i=1,\ldots h} a_{m_1 , \ldots , m_h} b_{p_1 , \ldots , p_h}. \] \begin{proposition} For any $h\in\N$, the product $\star$ is distributive and $\mathbf 1=\left(\delta_{1,n_1}\cdots \delta_{1,n_h}\right)_{n_1 , \ldots , n_h}$ is its identity. Hence, this endows $\mathcal M_h$ with a structure of commutative algebra. \end{proposition} Denoting by $S_{A}(x_1,\ldots,x_h):=\sum_{n_1 , \ldots , n_h\geq1}{a_{n_1,\ldots,n_h}}x^{n_1}\cdots x^{n_h}$ the ordinary generating function of $A$ and by $S_{A}^{\cal D}(s_1,\ldots,s_h):=\sum_{n_1 , \ldots , n_h\geq1}\frac{a_{n_1,\ldots,n_h}}{n_1^{s_1}\cdots n_h^{s_h}}$ its Dirichlet generating function, we observe the following fact. \begin{proposition} Let $A, B\in\mathcal M_h$. The three following assertions are equivalent: \begin{enumerate} \item $C=A\star B$; \item $\displaystyle S_{C} ( x_1 , \ldots , x_h) = \sum_{n_1 , \ldots , n_h} a_{n_1 , \ldots , n_h} S_B (x_1^{n_1} , \ldots , x_h^{n_h})$; \item $ \displaystyle S^{{\cal D}}_{C} ( s_1 , \ldots , s_h) = S^{{\cal D}}_{A} ( s_1 , \ldots , s_h) \, S^{{\cal D}}_{B} ( s_1 , \ldots , s_h)$. \end{enumerate} \end{proposition} Indeed, via the map $A \mapsto S_A$, the ideal $x_1\cdots x_h \C[x_1,\ldots,x_h]$ can be embedded with a structure of commutative algebra $(x_1\cdots x_h\C[x_1,\ldots,x_h],+,\star)$ isomorphic to $\mathcal M_h$. With this notation, we have $S_{A\star B}=S_A\star S_B$. The formal substitution \[\mathcal D:x_i^n\rightarrow \frac1{n^{s_i}}\] is an isomorphism from $(x_1\cdots x_h\C[x_1,\ldots,x_h],+,\star)$ to the algebra of multivariate Dirichlet formal series in the variables $\{s_1,\ldots,s_h\}$. Note that the isomorphism above can be realized through an iteration of Mellin transforms \cite[Appendix B, Section B.7]{Fla}: % \[ % \mathcal D[f]=\frac1{\Gamma(s_1)\cdots\Gamma(s_h)}\int_0^\infty\dotsi\int_0^\infty f\left(e^{-x_1},\ldots,e^{-x_h}\right)x_1^{s_1-1}\cdots x_h^{s_h-1}dx_1\cdots dx_h % \] \[ \mathcal D[f]=\frac1{\prod_{i=1}^h\Gamma(s_i)}\int_0^\infty\dotsi\int_0^\infty f\left(e^{-x_1},\ldots,e^{-x_h}\right)x_1^{s_1-1}\cdots x_h^{s_h-1}dx_1\cdots dx_h \] where $\Gamma(s)=\int_0^\infty e^{-x}x^{s-1}dx$ is the Euler Gamma function. Let $\mathcal T_h:=\left\{\left( a_{n_1 , \ldots , n_h} \right)_{n_1, \ldots,n_h \geq 1}\in\mathcal M_h: a_{n_1,\ldots,n_h}\neq 0\Rightarrow n_1\geq\cdots\geq n_h\right\}$. As $\mathcal T_h$ is stable under convolution, it is a subalgebra of $\mathcal M_h$. In the rest of the paper, let $\left( a_{n_1 , \ldots , n_h} \right)_{n_1\geq \cdots\geq n_h \geq 1}$ denote the elements of $\mathcal T_h$. \subsection{Multivariate Lambert transform} Let $\triangle = (1)_{m_1 \geq \cdots \geq m_h \geq 1}$. We call \emph{multivariate Lambert transform} of $A = \left( a_{n_1 , \ldots , n_h} \right)_{n_1 \geq \cdots \geq n_h\geq1}$ the convolution of $A$ with $\triangle$: $ {\rm T}_L(A) := A \star \triangle$. Remark that the (ordinary) generating function of $\triangle$ is $\mathcal S_{\triangle}=\frac{x_1 \cdots x_h}{(1 - x_1)(1 - x_1 x_2) \cdots (1-x_1 \cdots x_h)}$ and its Dirichlet generating function is $\mathcal S_{\triangle}^{\mathcal D}= \mathcal Z(s_1,\ldots,s_h)$, where ${\cal Z}$ denotes the \emph{large multizeta} function ${\cal Z}(s_1,\ldots,s_h):=\sum_{n_1 \geq \cdots \geq n_h\geq1}\frac{1}{n_1^{s_1}\cdots n_h^{s_h}}$ \cite{cresson,Costermans:2009:NAM}. The generating function of $(\hat a_{n_1,\ldots,n_h})_{n_1,\ldots,n_h}:=T_L(A)$ is \begin{align*} S_{{\rm T}_L(A)} &= S_\triangle\star S_A\\ &=\sum_{n_1 \geq \cdots \geq n_h \geq 1} a_{n_1 , \ldots , n_h} \frac{x_1^{n_1} \cdots x_h^{n_h}}{(1-x_1^{n_1})(1-x_1^{n_1}x_2^{n_2}) \cdots (1 - x_1^{n_1} \cdots x_h^{n_h})} \end{align*} and its Dirichlet generating function is given by \[ S^{{\cal D}}_{{\rm T}_L(A)}(s_1,\ldots,s_h) = {\cal Z}(s_1,\ldots,s_h) S^{{\cal D}}_{A} ( s_1 , \ldots , s_h). \] The multivariate Lambert transform is related to the order defined in Section \ref{order} by the following formula. \begin{proposition} If $A=\left({a}_{n_1 , \ldots , n_h}\right)_{n_1 , \ldots , n_h}$ then we have \[ \hat{a}_{n_1 , \ldots , n_h} = \sum_{(m_1 , \ldots , m_h) \preceq (n_1 , \ldots , n_h)} a_{m_1 , \ldots , m_h}. \] \end{proposition} As a consequence, the Dirichlet generating function of $\mu^h((1,\ldots,1),\lambda)$ is the inverse of $\cal Z$: \begin{corollary}\label{Mob} \[ {\cal Z} (s_1 , \ldots , s_h)^{-1} = \sum_{(1 , \ldots , 1) \preceq (n_1 , \ldots , n_h)} \frac{\mu^h((1 , \ldots , 1),(n_1 , \ldots , n_h))}{n_1^{s_1} \cdots n_h^{s_h}}. \] \end{corollary} Note that when $h=1$, ${\cal Z}(s)=\zeta(s)$ is the Riemann zeta function and Corollary \ref{Mob} is the classical identity $\zeta(s)^{-1}=\sum_{n>0}\frac{\mu(n)}{n^s}$. \subsection{Another transform} Let $\blacktriangle = \Big( (n_1 - n_2 + 1) \cdots (n_{h-1} - n_{h} +1 ) \Big)_{n_1 \geq \cdots \geq n_h \geq 1}$. Using $\blacktriangle$ and the convolution product defined above, we construct a new transformation: $$ {\rm T}_\blacktriangle(A) = \blacktriangle \star A = (a^\blacktriangle_{n_1 , \cdots , n_h})_{n_1 \geq \cdots \geq n_h \geq 1}. $$ \begin{lemma} \label{lemgenfunc} The generating function of $\blacktriangle$ is given by the following formula \begin{equation} \begin{array}{rl} S_\blacktriangle:= & \displaystyle \sum_{n_1 \geq \cdots \geq n_h \geq 1} (n_1 - n_2 + 1) \cdots ( n_{h-1} - n_{h} + 1 ) x_1^{n_1} \cdots x_{h}^{n_h} \\ = & \displaystyle \frac{x_1 \cdots x_h}{(1 - x_1)^2 (1 - x_1 x_2)^2 \cdots ( 1 - x_1 \cdots x_{h-1})^2 ( 1 - x_1 \cdots x_h)}. \end{array} \end{equation} \end{lemma} \begin{proof} First, note that $\displaystyle \frac{x}{1-x^2} = \frac{d}{dx} \left( \frac{1}{1-x} \right)$. Hence, we have $\displaystyle \frac{x}{1-x^2} = \sum_{n > 0} n x^n$. Now assume that one has two variables $x$ and $y$. Then \begin{equation*} \begin{aligned} \frac{xy}{(1-x)^2(1-xy)} & = \left( \sum_{n > 0} n x^n \right) \, y \, \left( \sum_{m \geq 0} (xy)^m \right) \\ & = \sum_{n>0 , m \geq 0} n x^{n+m} y^{m+1} \\ & = \sum_{n>0 , m > 0} n x^{n+m-1} y^{m} \\ & = \sum_{n \geq m > 0} (n-m+1) x^n y^m. \end{aligned} \end{equation*} Now assume that the formula holds with $h$ variables. Then \begin{equation*} \begin{split} & \frac{x_1 \cdots x_{h+1}}{(1 - x_1)^2 (1 - x_1 x_2)^2 \cdots ( 1 - x_1 \cdots x_{h})^2 ( 1 - x_1 \cdots x_{h+1})} = \\ & \frac{1}{(1-x_1)^2} \sum_{n_1 \geq \cdots \geq n_h \geq 1} (n_1 - n_2 + 1) \cdots ( n_{h-1} - n_{h} + 1 ) (x_1 x_2)^{n_1} \cdots x_{h}^{n_h} =\\ & \sum_{n > 0} n x^{n-1} \sum_{n_1 \geq \cdots \geq n_h \geq 1} (n_1 - n_2 + 1) \cdots ( n_{h-1} - n_{h} + 1 ) (x_1 x_2)^{n_1} \cdots x_{h}^{n_h} =\\ & \sum_{n > 0 , n_1 \geq \cdots \geq n_h \geq 1} n(n_1 - n_2 + 1) \cdots ( n_{h-1} - n_{h} + 1 ) x_1^{n+n_1-1} x_2^{n_1} \cdots x_{h}^{n_h} =\\ & \sum_{n_1 \geq 0 , n_2 \geq \cdots \geq n_{h_+1} \geq 1} (n_1+1)(n_2 - n_3 + 1) \cdots ( n_{h} - n_{h+1} + 1 ) x_1^{n_1 + n_2} x_2^{n_2} \cdots x_{h}^{n_{h+1}}. \end{split} \end{equation*} A last change of variables proves the formula for $h+1$ variables and the result follows by induction. \end{proof} Lemma \ref{lemgenfunc} implies that the generating function of ${\rm T}_\blacktriangle(A)$ is \[ \begin{array}{c} S_\blacktriangle\star S_A= \sum_{n_1 \geq \cdots \geq n_h \geq 1} a_{n_1 , \ldots , n_h} \frac{x_1^{n_1} \cdots x_h^{n_h}}{(1-x_1^{n_1})^2 (1-x_1^{n_1}x_2^{n_2})^2 \cdots (1-x_1^{n_1} \cdots x_{h-1}^{n_{h-1}})^2 (1-x_1^{n_1} \cdots x_h^{n_h}) } \end{array} \] and its Dirichlet generating function is given by \[ S^{\cal D}_{{\rm T}_\blacktriangle(A)} = {\cal Z}^\blacktriangle(s_1 , \ldots , s_h) \, S^{\cal D}_{A} (s_1 , \ldots , s_h) ,\] where $$ {\cal Z}^\blacktriangle(s_1 , \ldots , s_h) = \sum_{n_1 \geq \cdots \geq n_h \geq 1} \frac{(n_1 - n_2 + 1) \cdots (n_{h-1} - n_{h}+1)}{n_1^{s_1} \cdots n_h^{s_h}}. $$ As a consequence, we have $ {a}^\blacktriangle_{n_1 , \ldots , n_h} = \displaystyle \sum_{(m_1 , \ldots , m_h) \preceq (n_1 , \ldots , n_h)} \alpha_{m_1 , \ldots , m_h}^{n_1 , \ldots , n_h} a_{m_1 , \ldots , m_h} $ where $\alpha_{m_1 , \ldots , m_h}^{n_1 , \ldots , n_h}=\left(\frac{n_1}{m_1}- \frac{n_2}{m_2}+1\right)\cdots\left(\frac{n_{h-1}}{m_{h-1}}- \frac{n_h}{m_h}+1\right)$ 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 \ref{trans}). 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, $\alpha_{m_1 , \ldots , m_h}^{n_1 , \ldots , n_h}$ gives the number of pyramids obtained with translations of the plateaus in one direction only. \begin{figure}[ht] \begin{center} \scalebox{0.8}{ \begin{tikzpicture} \draw [red] (0,0) -- (0,1); \draw [red] (0,0) -- (5,0); \draw [red] (5,0) -- (5,1); \draw [red] (0,1) -- (5,1); \draw [red] (0,1) -- (2,4); \draw [red] (5,1) -- (7,4); \draw [red] (2,4) -- (7,4); \draw [red] (7,3) -- (7,4); \draw [red] (5,0) -- (7,3); \draw [blue] (2,1.5) -- (4,1.5); \draw [blue] (2,2.5) -- (4,2.5); \draw [blue] (2,2.5) -- (2,1.5); \draw [blue] (4,1.5) -- (4,2.5); \draw [blue] (2,2.5) -- (3,4); \draw [blue] (4,2.5) -- (5,4); \draw [blue] (5,4) -- (5,3); \draw [blue] (5,3) -- (4,1.5); \draw [blue] (3,4) -- (5,4); \draw [<->,gray] (2,4.05) -- (7,4.05); \draw [<->,gray] (-0.05,1) -- (1.95,4); \draw [<->,gray] (5.05,3) -- (4.05,1.5); \draw [<->,gray] (2,1.45) -- (4,1.45); \node at (0.7,3){{{$m_1$}}}; \node at (4.5,4.5){{{$\displaystyle\frac{n_1}{m_1}$}}}; \node at (4.8,2){{{$m_2$}}}; \node at (3.2,2){{{$\displaystyle\frac{n_2}{m_2}$}}}; \end{tikzpicture}} \end{center} \caption{Translations of plateaus} \label{trans} \end{figure} \section{Application to the enumeration of pyramids}\label{counting} \subsection{Counting pyramids and espaliers by volume} The one-to-one correspondence described in Section \ref{order} allows us to construct an espalier $\mathbb E_{\lambda,\lambda'}\in E_{(\lambda_1\lambda'_1,\ldots,\lambda_h\lambda'_h)}$ for each pair of partitions $\lambda=(\lambda_1,\ldots,\lambda_h)$ and $\lambda'=(\lambda'_1,\ldots,\lambda'_h)$. Hence, we deduce \begin{lemma} \[ \triangle^{\star 2}=\left(n^e_{[m_1,\ldots,m_h]}\right)_{m_1\geq\cdots\geq m_h\geq 1}. \] \end{lemma} 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 $\P$ will be of type $\lambda=(\lambda_1,\ldots,\lambda_h)$ if the first plateau is of size $\lambda_1$, $\ldots$, the $h$-th plateau is of size $\lambda_h$; we will write $mv(\P)=\lambda$ as with pyramids in dimension $2+1$. The number of $(1+1)$-pyramids of type $\lambda$ equals $({\lambda_1}-{\lambda_2}+1)\cdots ({\lambda_{h-1}}-{\lambda_h}+1)$ (see Figure \ref{(1+1)-pyramids} for an example). \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.3] \foreach \x in {0,1,2,3,4} {\cellule {\x}{0}} \foreach \x in {0,1,2,3,4} {\cellule {\x+6}{0}} \foreach \x in {0,1,2,3,4} {\cellule {\x+12}{0}} \foreach \x in {0,1,2} {\cellule {\x}{1}} \foreach \x in {0,1,2} {\cellule {\x+7}{1}} \foreach \x in {0,1,2} {\cellule {\x+14}{1}} \end{tikzpicture} \caption{The $3$ $(1+1)$-pyramids of type $(5,3)$} \label{(1+1)-pyramids} \end{figure} The pyramids of height $h$ are in one-to-one correspondence with the pairs of $(1+1)$-pyramids of height $h$ (see Figure \ref{(1+1)-pyramid1} for an example). Furthermore, the pyramid $\P$ corresponding to a pair $(\P',\P'')$ is such that $mv(\P)=(\lambda'_1\lambda''_1,\ldots,\lambda'_h\lambda''_h)$ if $mv(\P')=\lambda'$ and $mv(\P'')=\lambda''$. \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.6] \lcube{0}{0}{0}\lcube{0}{0}{1}\lcube{0}{0}{2}\lcube{0}{0}{3}\lcube{0}{0}{4} \lcube{0}{1}{1}\lcube{0}{1}{2}\lcube{0}{1}{3} \lcube{0}{2}{2} \lcube{0}{3}{2} \lcube{0}{4}{2} \bcube{0}{0}{0}\bcube{1}{0}{0}\bcube{2}{0}{0}\bcube{3}{0}{0} \bcube{1}{1}{0}\bcube{2}{1}{0}\bcube{3}{1}{0} \bcube{1}{2}{0}\bcube{2}{2}{0} \bcube{1}{3}{0}\bcube{2}{3}{0} \bcube{2}{4}{0} \begin{scope}[xshift = 0cm] \foreach \x in {0,1,2,3}{ \foreach \z in {0,1,2,3,4}{ \tcube{\x}{0}{\z} } } \foreach \x in {1,2,3}{ \foreach \z in {1,2,3}{ \tcube{\x}{1}{\z} } } \foreach \x in {1,2}{ \foreach \z in {2}{ \tcube{\x}{2}{\z} } } \foreach \x in {1,2}{ \foreach \z in {2}{ \tcube{\x}{3}{\z} } } \tcube{2}{4}{2} \end{scope} \end{tikzpicture} \caption{A $(2+1)$-pyramid and its two $(1+1)$ associated pyramids} \label{(1+1)-pyramid1} \end{figure} We deduce \begin{lemma} \[ \blacktriangle^{\star 2}=\left(n^p_{[m_1,\ldots,m_h]}\right)_{m_1\geq\cdots\geq m_h\geq 1}. \] \end{lemma} Hence, we are now able to compute the generating function. \begin{theorem} The Dirichlet generating functions of espaliers and pyramids are respectively \begin{equation}\label{EPDir} {\mathcal E}_{\mathcal D}^e(s_1,\ldots,s_h;h)={\cal Z}(s_1,\ldots,s_h)^2,\, {\mathcal E}_{\mathcal D}^p(s_1,\ldots,s_h;h)={\cal Z}^\blacktriangle(s_1,\ldots,s_h)^2. \end{equation} The ordinary generating functions of the espaliers and the pyramids are respectively \begin{equation} \begin{array}{l} \displaystyle {\mathcal E}^e(x_1,\ldots,x_h;h)=S_\triangle^{\star2} =\\ \displaystyle \sum_{n_1\geq\cdots\geq n_h\geq 1}\frac{x_1^{n_1}\cdots x_h^{n_h}}{ (1-x_1^{n_1})(1-x_1^{n_1}x_2^{n_2})\cdots(1-x_1^{n_1}\cdots x_{h}^{n_h})}, \label{EOrd} \end{array} \end{equation} \begin{equation} \begin{array}{l} {\mathcal E}^p(x_1,\ldots,x_h;h)=S_\blacktriangle^{\star2}=\\ \displaystyle \hspace*{-.9cm} \sum_{n_1\geq\cdots\geq n_h\geq 1}\frac{(n_1-n_2+1)\cdots (n_{h-1}-n_{h}+1)x_1^{n_1}\cdots x_h^{n_h}}{ (1-x_1^{n_1})^2(1-x_1^{n_1}x_2^{n_2})^2\cdots(1-x_1^{n_1}\cdots x_{h-1}^{n_{h-1}})^2(1-x_1^{n_1}\cdots x_{h}^{n_h})}. \label{POrd} \end{array} \end{equation} \end{theorem} So we deduce \begin{corollary} \[ \begin{array}{l} \displaystyle {\mathcal E}^e(x;h)=\sum_{n_1\geq\cdots\geq n_h\geq 1}\frac{x^{n_1+\cdots+n_h}}{ (1-x^{n_1})(1-x^{n_1+n_2})\cdots(1-x^{n_1+\cdots+n_h})},\\ \mathcal E^p(x;h)=\\ \displaystyle \sum_{n_1\geq\cdots\geq n_h\geq 1}\frac{(n_1-n_2+1)\cdots (n_{h-1}-n_{h}+1)x^{n_1+\cdots+n_h}}{ (1-x^{n_1})^2(1-x^{n_1+n_2})^2\cdots(1-x^{n_1+\cdots+n_{h-1}})^2(1-x^{n_1+\cdots+n_h})}. \end{array} \] \end{corollary} \subsection{Higher dimensions} In this section, we investigate the coefficients $n_v^t(d)$ ($t \in \{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 , \ldots , v_h$ in dimension $d+1$ is given by $\triangle^{\star d}$ (resp.\ $\blacktriangle^{\star d}$). Therefore the Dirichlet generating function of $n_{[m_1,\ldots,m_n]}^t(d)$ is \begin{equation} \mathcal E^t_{\mathcal D}(s_1,\ldots,s_h)={\cal Z}^t(s_1,\ldots,s_h)^d, \end{equation} with ${\cal Z}^e={\cal Z}$ and ${\cal Z}^p={\cal Z}^\blacktriangle$. We now consider $d$ as a formal parameter. We have \[ \frac{\partial^k}{\partial d^k}\mathcal E^t_{\mathcal D}(s_1,\ldots,s_h)= {\cal Z}^t(s_1,\ldots,s_h)^d\log\left({\cal Z}^t(s_1,\ldots,s_h)\right)^k. \] We observe that ${\cal Z}^t(s_1,\ldots,s_h)=1+\widetilde{\cal Z}^t(s_1,\ldots,s_h)$ where $\displaystyle\widetilde{\cal Z}^t(s_1,\ldots,s_h)=\sum_{\substack{n_1\geq 2\\n_1\geq\cdots\geq n_h\geq 1}} \frac{(*)}{n_1^{s_1}\cdots n_h^{s_h}}$; here $(*)$ denotes coefficients depending on $n_1,\ldots,n_h$ and the type $t$ of the objects. It follows that \begin{equation} \label{eqdif} \frac{\partial^k}{\partial d^k}\mathcal E^t_{\mathcal D}(s_1,\ldots,s_h)= \sum_{\substack{n_1\geq 2^k\\n_1\geq\cdots\geq n_h\geq 1}}\frac{(\Box)}{n_1^{s_1}\cdots n_h^{s_h}}; \end{equation} $(\Box)$ also denotes coefficients. We deduce from (\ref{eqdif}) that $n^t_{[v_1,\ldots,v_h]}(d)$ is a polynomial in $d$ whose degree is at most $\log_2(v_1)$. Furthermore, \begin{equation} \label{degn}\deg\left(n^t_{[2^k,1,\ldots,1]}(d)\right)=k. \end{equation} Hence, we have \begin{theorem} 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 $\lfloor \log_2(v)\rfloor$. \end{theorem} \begin{proof} Since \[n_v^t(d)=\sum_{h\geq 1}\sum_{v_1\geq\cdots\geq v_h\geq 1}n^t_{[v_1,\ldots,v_h]}(d), \] (\ref{eqdif}) implies that $\deg(n_v^t(d))\leq\lfloor \log_2(v)\rfloor$. From (\ref{degn}), the inverse inequality holds if $$\displaystyle E_{(\ 2^{\lfloor\log_2v\rfloor},\underbrace{1,\ldots,1}_{(v-2^{\lfloor\log_2v\rfloor})\times})}\neq\emptyset.$$ This is obviously the case since it suffices to consider an espalier such that the volume of the first plateau is $2^{\lfloor\log_2v\rfloor}$ and with $v-2^{\lfloor\log_2v\rfloor}$ other plateaus consisting of one cell. \end{proof} \section{General construction}\label{general} A \emph{$(1+1)$-dimensional object} is a finite set of cells $(x,y)$ such that $x\in\N$ and $y\in \Z$. If $\cal O$ is a $(1+1)$-dimensional object, its $i$-th stratum will be the set $L_i({\cal O}):= \{(i,y)\in{\cal O}\}$. From a pair of $(1+1)$-dimensional objects $({\cal O}_1,{\cal O}_2)$, we construct a $(2+1)$-dimensional object that is a set of cells $(x,y,z)$ with $x\in\N$ and $y,z\in\Z$: ${\cal G}({\cal O}_1,{\cal O}_2):=\{(x,y,z):(x,y)\in{\cal O}_1, (x,z)\in{\cal O}_2)$. The $i$-th \emph{stratum} of a $(2+1)$-dimensional object will be defined by $L_i({\cal O}):= \{(i,y,z)\in{\cal O}\}$. The \emph{height} of such an object is $h({\cal O})=\max\{i:L_i({\cal O})\neq \emptyset\}$. The \emph{multivolume} $mv({\cal O})$ of a $(1+1)$- or $(2+1)$-dimensional object ${\cal O}$ is the sequence of the cardinals of its strata. Note that if $mv({\cal O}_1)=[v_1,\cdots,v_{h}]$ and $mv({\cal O}_2)=[v'_1,\cdots,v'_{h'}]$ then $$mv({\cal G}({\cal O}_1,{\cal O}_2))= [v_1v'_1,\ldots, v_{\min(h,h')}v'_{\min(h,h')}].$$ This property is obtained easily by examining the construction of each stratum (see Figure \ref{Level} for an example). An object $\cal O$ is said to be \emph{plain} if for any $1\leq i\leq h({\cal O})$, the stratum $L_i({\cal O})$ is not empty. Let $\mathcal A=\bigcup_{u}\mathcal A_u$ and $\mathcal B=\bigcup_{v}\mathcal B_v$ be two families of $(1+1)$-dimensional plain objects of height $h$ graded by multivolume and such that $\mathcal A_u$ and $\mathcal B_v$ are finite for any multivolume $u$ and $v$. Let also set $A=\left(a_{v_1,\ldots,v_h}\right)_{v_1,\ldots,v_h}$ and $B=\left(b_{v_1,\ldots,v_h}\right)_{v_1,\ldots,v_h}$ with $a_{v_1,\ldots,v_h}=\#A_{[v_1,\ldots,v_h]}$ and $b_{[v_1,\ldots,v_h]}=\#B_{[v_1,\ldots,v_h]}$. The set ${\mathcal G}({\mathcal A},{\mathcal B})={\cal G}({\cal O}_1,{\cal O}_2): \{{\cal O}_1\in {\mathcal A}_u, {\cal O}_2\in {\mathcal B}_u\}$ contains only plain objects of size $h$. Furthermore, it is graded by multivolume (${\mathcal G}({\mathcal A},{\mathcal B})=\bigcup_v{\mathcal G}_v$) and the sequence $G=\left(\#G_{[v_1,\ldots,v_h]}\right)_{v_1,\ldots,v_h\geq 1}$ is given by $ G=A\star B. $ \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.2] \foreach \x in {0,1,2,3,4} {\gcellule {\x}{9}} \foreach \x in {7,8} {\gcellule {\x}{9}} \foreach \y in {0,1,2} {\rcellule {-1}{\y}} \foreach \y in {5,8} {\rcellule {-1}{\y}} \foreach \x in {0,1,2,3,4,7,8} {\foreach \y in{0,1,2,5,8}{\cellule {\x}{\y}}} \end{tikzpicture} \caption{Construction of a stratum} \label{Level} \end{figure} Let us recall the operation of \emph{extrusion} that appears in a geometric model for the validation of real-time applications \cite{LG05,CGL11}. It is defined in the following way: $$ \begin{array}{cccccc} Extr: & \mathbb{R}^m & \times & \mathbb{R} & \rightarrow & \mathbb{R}^{m+1}\\ & (x-1 , \cdots , x_m ) & , & y & \rightarrow & (x-1 , \cdots , x_m ,y) \end{array} $$ 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 \cite{LG05,CGL11}) 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\footnote{A polycube is said to be \emph{directed} if each of its cells can be reached from a distinguished cell, called the \emph{root}, by a path only made of East, North and Ahead steps.} plateau polycubes \cite{CohenSolal,ChamparnaudDJ13}. The generating function of the number $P_{v,h}$ of directed plateau polycubes of height $h$ and volume $v$ is \begin{equation}\label{plateau} \displaystyle\sum_{v,h} P_{v,h} p^v t^h = \displaystyle \frac{t \tau(p)}{1 - t p \tau'(p)} \end{equation} where $\tau(x) = \sum_{k \geq 1} \frac{x^k}{1-x^k}$ denotes the generating function of the number $\tau(n)$ of divisors of an integer $n$ \cite{CohenSolal,ChamparnaudDJ13}. Formula \ref{plateau} 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 $$\displaystyle{ \sum_{v,h} P_{v,h}^{(d+1)} p^v t^h = \frac{t \tau^{(d+1)}(p)}{1 - t p {\tau^{(d+1)}}'(p)} }$$ where $\tau^{(d+1)}(x) = \left(\frac{x}{1-x}\right)^{*d}$. \begin{figure}[ht] \centering \begin{tikzpicture}[scale=0.5] \cube{0}{0}{0}\cube{1}{0}{0} \cube{0}{0}{1}\cube{1}{0}{1} \cube{0}{0}{2}\cube{1}{0}{2} \cube{1}{1}{1}\cube{2}{1}{1}\cube{3}{1}{1} \cube{1}{1}{2}\cube{2}{1}{2}\cube{3}{1}{2} \cube{2}{2}{1}\cube{3}{2}{1} \end{tikzpicture} \begin{tikzpicture}[scale=0.5] \lcube{0}{0}{0}\lcube{0}{0}{1}\lcube{0}{0}{2} \lcube{0}{1}{1}\lcube{0}{1}{2} \lcube{0}{2}{1} \bcube{0}{0}{0}\bcube{1}{0}{0}\bcube{1}{1}{0}\bcube{2}{1}{0} \bcube{3}{1}{0} \bcube{2}{2}{0}\bcube{3}{2}{0} \tcube{0}{0}{0}\tcube{1}{0}{0} \tcube{0}{0}{1}\tcube{1}{0}{1} \tcube{0}{0}{2}\tcube{1}{0}{2} \tcube{1}{1}{1}\tcube{2}{1}{1}\tcube{3}{1}{1} \tcube{1}{1}{2}\tcube{2}{1}{2}\tcube{3}{1}{2} \tcube{2}{2}{1}\tcube{3}{2}{1} \end{tikzpicture} \caption{A plateau polycube from two horizontally convex directed polyominoes} \label{plapol} \end{figure} Let us show how to recover (\ref{plateau}) 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,\ldots, v_h]$ is \[ \sum_{v_1,\ldots,v_h\geq 1}v_1\cdots v_{h-1}x_1^{v_1}\cdots x_h^{v_h}=\frac{x_1\cdots x_h}{(1-x_1)^2\cdots(1-x_{h-1})^2(1-x_h)} \] and the convolution yields \[ \sum_{v_1 , \ldots, v_h \geq 1} v_1 \cdots v_{h-1} \frac{x_1^{v_1}\cdots x_{h}^{v_h}}{(1-x^{v_1})^2\cdots (1-x_{h-1}^{v_{h-1}})^2 (1-x_h^{v_h})}. \] Setting $x_1=\cdots=x_{h-1}=p$ and $x_h=p\omega$, we obtain the generating function with respect to the volume ($p$) and the volume of the highest stratum ($\omega$): \[ \sum_{v_1 , \ldots, v_h \geq 1} v_1 \cdots v_{h-1} \frac{p^{v_1+\cdots+v_{h-1}+v_h} \, \omega^{v_h}}{(1-p^{v_1})^2\cdots (1-p^{v_{h-1}})^2 (1-(p\omega)^{v_h})} = \left( p\tau'(p) \right)^{h-1} \tau(p\omega). \] We recover (\ref{plateau}) by summing over $h$ and setting $\omega=1$ in \begin{equation}\label{platomeg} \sum_{h\geq1}t^h\left( p\tau'(p) \right)^{h-1} \tau(p\omega)=\frac{t\tau(p\omega)}{1-tp\tau'(p)} \hbox{\cite{CohenSolal}}. \end{equation} By a similar reasoning, (\ref{plateau}) 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 \begin{proposition} $$\displaystyle{ \sum_{v,h} P_{v,h}^{(d+1)} p^v t^h = \frac{t \tau^{(d+1)}(p)}{1 - t p {\tau^{(d+1)}}'(p)} }$$ where $\tau^{(d+1)}(x) = \left(\frac{x}{1-x}\right)^{*d}$. \end{proposition} The Dirichlet generating function of directed plateau polycubes of height $h$ is $\Xi(s_1-1,\ldots,s_{h-1}-1,s_h)^2$ with $\displaystyle \Xi(s_1,\ldots,s_h)=\sum_{v_1,\ldots,v_h\geq 1}\frac{1}{v_1^{s_1}\cdots 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 \begin{align*} &\displaystyle\sum_{v_1,\ldots,v_h\geq1}(v_1+v_2-1)\cdots(v_{h-1}+v_h-1)x_1^{v_1}\cdots x_h^{v_h}\\ =\quad &\alpha_h\left(x_1,\frac{x_2}{x_1},\ldots,\frac{x_hx_{h-2}\cdots}{x_{h-1}x_{h-3}\cdots}\right) \end{align*} with \begin{center} $ \alpha_h(t_1,\ldots,t_h)=t_1^2\cdots t_{h-1}^2\frac{d}{dt_1}\cdots \frac{d}{dt_{h-1}}\frac{t_1\cdots t_h}{(1-t_1)(1-t_1t_2)(1-t_2t_3)\cdots(1-t_{h-1}t_h)}. $ \end{center} 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: {\footnotesize \[ \begin{array}{l} \displaystyle \sum_{h\geq 1}t^h\sum_{n_1,\ldots,n_h}(n_1+n_2-1)\cdots(n_{h-1}+n_h-1)\alpha_h(p^{n_1},p^{n_2-n_1},\ldots,p^{n_h-n_{h-1}+n_{h-2}-\cdots})=\\ \scriptstyle \displaystyle t \left( \sum_{n_1,m_1\geq 1} p^{n_1 m_1} \left( 1 + t \sum_{n_2,m_2 \geq 1} (n_1+n_2-1)(m_1+m_2-1) p^{n_2m_2} \left( 1 + t \sum_{} \cdots \right) \right) \right). \end{array} \] } \section{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 \cite{ChamparnaudDJ13}, 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 \cite[p.\ 153]{Wilf}, $\displaystyle \sum_h t^h\alpha_h(p,1,p,1,\ldots) = \frac{pt(1-p)^3}{(1-p)^4-pt(1-p-p^2+p^3+p^2t)} $, 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 \seqnum{A008288} from the OEIS \cite{Sloane}) and whose generating function is $\displaystyle \sum_{n,k}D_{n,k}x^ny^k=(1-x-y-xy)^{-1}$. More precisely, $\displaystyle \alpha_h(p,1,p,1,\ldots)=\frac{p^h}{(1-p)^{2h-1}} \sum_{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 \cite[Example IX.14, p.\ 660]{Fla}. Formula (\ref{platomeg}) 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 (\ref{platomeg}). Finally, note that numerical investigations lead us to the promising conjecture below. We define a new family of objects called \emph{canyons} as follows: A polycube $P$ is a canyon polycube if the following conditions are satisfied: \begin{itemize} \item if the cell with coordinates $(a,b,c)$ belongs to $P$, then $(a-1,b,c) \in P$ (for $a>1$); \item for all $(a,b,c) \in P$ such that $a = \max \left\{ a' , (a',b,c) \in P \right\}$, either $a = \max \left\{ a' , (a',b',c) \in P \right\}$ or $a = \max \left\{ a' , (a',b,c') \in P \right\}$. \end{itemize} An example of canyon is given in Figure \ref{canyon}. \begin{figure}[ht] \begin{center} \begin{tikzpicture}[scale=0.6] \Mcube{0}{0}{0}\Mcube{1}{0}{0}\Mcube{2}{0}{0}\Mcube{3}{0}{0} \Mcube{0}{0}{1}\Mcube{1}{0}{1}\Mcube{2}{0}{1}\Mcube{3}{0}{1} \Mcube{0}{0}{2}\Mcube{1}{0}{2}\Mcube{2}{0}{2}\Mcube{3}{0}{2} \Mcube{0}{0}{3}\Mcube{1}{0}{3}\Mcube{2}{0}{3}\Mcube{3}{0}{3} \Mcube{0}{0}{4}\Mcube{1}{0}{4}\Mcube{2}{0}{4}\Mcube{3}{0}{4} \Mcube{0}{1}{0}\Mcube{2}{1}{0}\Mcube{3}{1}{0} \Mcube{0}{2}{0}\Mcube{2}{2}{0}\Mcube{3}{2}{0} \Mcube{0}{3}{0}\Mcube{2}{3}{0}\Mcube{3}{2}{0} \Mcube{2}{4}{0} \Mcube{0}{1}{1}\Mcube{2}{1}{1}\Mcube{3}{1}{1} \Mcube{0}{1}{2}\Mcube{2}{1}{2}\Mcube{3}{1}{2} \Mcube{0}{2}{2}\Mcube{2}{2}{2}\Mcube{3}{2}{2} \Mcube{0}{1}{4}\Mcube{2}{1}{4}\Mcube{3}{1}{4} \end{tikzpicture} \end{center} \caption{A canyon polycube} \label{canyon} \end{figure} Let $n^c_{v}$ denote the number of canyons of volume $v$ (sequence \seqnum{A239257} from the OEIS \cite{Sloane}). Then we have \begin{conjecture} \[n_v^c \underset{+\infty}{\sim} 2^v+\frac{10-2\sqrt{5}}{5} \phi^v + \alpha\beta^v\] where $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio, $\beta=1.51287\ldots$ is the unique positive real zero of the polynomial $x^4-x^3-x^2+x-1$ and $\alpha=0.94695\ldots$. \end{conjecture} 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 \cite{Plouffe}. \begin{thebibliography}{99} \bibitem{AB06} G. Aleksandrowicz and G. Barequet, Counting $d$-dimensional polycubes and nonrectangular planar polyominoes, {\it Internat. J. Comput. Geom. Appl.} {\bf 19} (2009), 215--229. \bibitem{oai:arXiv.org:math-ph/0212015} M. Baake and U. Grimm, Combinatorial problems of (quasi-)crys\-tallography, in H.-R. Trebin, ed., {\it Quasicrystals --- Structure and Physical Properties}, Wiley-VCH, 2002, pp.~160--171. \bibitem{BK72} E. A. Bender and D. E. Knuth, Enumeration of plane partitions, {\it J. Combin. Theory Ser. A} {\bf 13} (1972), 40--54. \bibitem{Bo96} M. Bousquet-M\'elou, A method for the enumeration of various classes of column-convex polygons, {\it Discrete Math.} {\bf 154} (1996), 4--25. \bibitem{Bres99} D. M. Bressoud, {\it Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture}, Cambridge University Press, 1999. \bibitem{BH57} S. R. Broadbent and J. M. Hammersley, Percolation processes; I. Crystals and mazes, {\it Proc. Cambridge Philos. Soc.} \textbf{53} (1957), 629--641. \bibitem{CohenSolal} J.-M. Champarnaud, Q. Cohen-Solal, J.-Ph. Dubernard, and H. Jeanne, Enumeration of specific classes of polycubes, {\it Electron. J. Combin.} {\bf 20} (4) (2013), \href{http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p26}{Paper P26}. \bibitem{CDJ09} J.-M. Champarnaud, J.-Ph. Dubernard, and H. Jeanne, An efficient algorithm to test whether a binary and prolongeable language is geometrical, {\it Internat. J. Found. Comput. Sci.} {\bf 20} (2009), 763--774. \bibitem{ChamparnaudDJ13} J.-M. Champarnaud, J.-Ph. Dubernard, and H. Jeanne, A generic method for the enumeration of various classes of directed polycubes, {\it Discrete Math. Theor. Comput. Sci.} {\bf 15} (2013), 183--200. \bibitem{CGL11} A. Choquet-Geniet and G. Largeteau, Real-time scheduling using regularity criteria and a geometrical approach, {\it Int. J. Critical Computer-Based Systems}, {\bf 2} (2011), 266--287. \bibitem{CLP98} H. Cohn, M. Larsen, and J. Propp, The shape of a typical boxed plane partition, {\it New York J. Math.} {\bf 4} (1998), 137--165. \bibitem{Costermans:2009:NAM} C. Costermans and V. Hoang Ngoc Minh, Noncommutative algebra, multiple harmonic sums and applications in discrete probability, {\it J. Symbolic Comput.} {\bf 44} (2009), 801--817. \bibitem{cresson} J. Cresson, S. Fischler, and T. Rivoal, S\'eries hyperg\'eom\'etriques multiples et polyz\^etas, preprint, available at \url{http://hal.archives-ouvertes.fr/hal-00101376/PDF/CFRalgo-HAL.pdf}. \bibitem{Fer04} S. Feretic, A $q$-enumeration of convex polyominoes by the festoon approach, {\it Theoret. Comput. Sci.} {\bf 319} (2004), 333--356. \bibitem{Fla} P. Flajolet and R. Sedgewick, {\it Analytic Combinatorics}, Cambridge University Press, 2009. \bibitem{HW} G. H. Hardy and E. M. Wright, {\it An Introduction to the Theory of Numbers}, 5th ed., Oxford University Press, 1980. \bibitem{LG08} G. Largeteau and D. Geniet, Quantification du taux d'invalidit\'e d'ap\-pli\-ca\-tions temps-r\'eel \`a contraintes strictes, {\it Technique et Science Informatiques} {\bf 27} (2008), 589--625. \bibitem{LG05} G. Largeteau, D. Geniet, and E. Andres, Discrete geometry applied in hard real-time systems validation, in {\it Discrete Geometry for Computer Imagery}, Lect. Notes in Comp. Sci., Vol.~3429, Springer, 2005, pp.~23--33. \bibitem{Lu75} W. F. Lunnon, Counting multidimensional polyominoes, {\it Computer J.} {\bf 18} (1975), 366--367. \bibitem{Macdonald} I. G. MacDonald, Symmetric Functions and Hall Polynomials, {\it Oxford Mathematical Monographs}, Oxford University Press, 1995. \bibitem{MacMahon} P. A. MacMahon, \textit{Combinatory Analysis}, Cambridge University Press, 1915--1916. \bibitem{Mobius} A. F. M\"obius, \"Uber eine besondere Art von Umkehrung der Reihen, {\it J. Reine Angew. Math.}, {\bf 9} (1832), 105--123. \bibitem{Plouffe} {ISC}, Inverse Symbolic Calculator, \url{http://isc.carma.newcastle.edu.au/}. \bibitem{Rota} G.-C. Rota, On the foundations of combinatorial theory I: theory of M\"obius functions, {\it Z. Wahrscheinlichkeitstheorie und Verw. Gebiete} {\bf 2} (1964), 340--368. \bibitem{Sloane} OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, \url{http://oeis.org}. \bibitem{Temp56} H. N. V. Temperley, Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules, {\it Phys. Rev.} {\bf 103} (1956), 1--16. \bibitem{Stan01} R. P. Stanley, {\it Enumerative Combinatorics 2}, Chapter 7, Cambridge Studies in Advanced Math, Wadsworth \& Brooks/Cole Advanced Books \& Software, 2001. \bibitem{Wilf} H. S. Wilf, {\it Generatingfunctionology}, Academic Press, 1994. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05B50; Secondary 05A15. \noindent \emph{Keywords: } polycube, Dirichlet convolution, Dirichlet generating function, Lambert transform. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A008288}, \seqnum{A229914}, \seqnum{A229915}, \seqnum{A239257}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 19 2015; revised versions received August 12 2015; October 8 2015; October 20 2015. Published in {\it Journal of Integer Sequences}, November 25 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}