% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\usepackage[english]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{graphics}
\usepackage{amsfonts, amssymb}
\usepackage{vmargin}
%Styles de chapitres
%\usepackage[Lenny]{fncychap}
%Bibliographie
%\usepackage{cite}
%\bibliographystyle{alpha}
%Tikz
\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,plothandlers,positioning,calc}

%Somme et Produit
\newcommand{\bigsum}{\displaystyle\sum\limits}
\newcommand{\bigprod}{\displaystyle\prod\limits}


%Cellule
\newcommand{\cellule}[2]{
			\fill[rounded corners, color=black!50] (#1,#2) +(.02,.02) -- +(.02,.98) -- +(.98,.98) -- +(.98,.02) -- cycle;
		}
		
%Cube
\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);
}

%Cube bleu
\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);
}



% plateau
\newcommand{\plateau}[2]{
	\foreach \y in {0,...,#1}{
		\foreach \z in {0,...,#2}{
			\cube{0}{\y}{\z}
		}
	}
}


% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{Enumeration of Specific Classes of Polycubes}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Jean-Marc Champarnaud\\
\small LITIS\\[-0.8ex]
\small Universit\'e de Rouen\\[-0.8ex] 
\small France\\
\small\tt jean-marc.champarnaud@univ-rouen.fr\\ 
\and
Quentin Cohen-Solal\\
\small LITIS\\[-0.8ex]
\small INSA Rouen\\[-0.8ex]
\small France\\
\small\tt quentin.cohensolal@insa-rouen.fr
\and
Jean-Philippe Dubernard\\
\small LITIS\\[-0.8ex]
\small Universit\'e de Rouen\\[-0.8ex]
\small France\\
\small\tt jean-philippe.dubernard@univ-rouen.fr
\and
Hadrien Jeanne\\
\small LITIS\\[-0.8ex]
\small Universit\'e de Rouen\\[-0.8ex]
\small France\\
\small\tt hadrien.jeanne@univ-rouen.fr
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jul 6, 2013}{}\\
\small Mathematics Subject Classifications: 05A15, 05A16}

\begin{document}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract}
The aim of this paper is to gather several new results concerning the enumeration of specific classes of polycubes. We first consider two classes of $3$-dimensional vertically-convex directed polycubes: the plateau polycubes and the parallelogram polycubes. An expression of the generating function is provided for the former class, as well as an asymptotic result for the number of polycubes of each class with respect to volume and width. We also consider three classes of $d$-dimensional polycubes ($d\geq 3$) and we state asymptotic results for the number of polycubes of each class with respect to volume and width.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	
% Intro et preliminaires
%!TEX root = polycubes.tex
\section{Introduction}

\ \indent In the cartesian plane $\mathbb{N}^2$, a polyomino is a
finite connected union of elementary cells (unit squares) without cut
points and defined up to a translation. Even though polyominoes have been studied for a long time in
combinatorics, no exact formula is known for general polyominoes but many
results have been found concerning some classes of 
polyominoes, see for instance \cite{Bo96} or \cite{Fer04}.


\indent Polyominoes also have a 3-dimensional equivalent: the
 polycubes \cite{Lu71}.  
If we consider, now, 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 $\mathbb{N}^3$. As with polyominoes, polycubes appear in statistical physics, more 
precisely in the phenomenon of percolation (see \cite{BH57} for example). A lot 
of studies have led to count polycubes according to the number $n$ of 
cells composing them. The first values were found in 1972 up to $n=6$ 
\cite{Lu71} and the last one (to our knowledge) in 2006, up to $n=18$ \cite{AB06}.
If we extend the notion of polycube to $d$-dimensions, where $d\geq 3$, these objects are also used in an efficient model of real-time validation \cite{LG08}, as well as in the representation of finite geometrical languages \cite{CDJ09,Jea10,Dub11}. 

\indent However a small number of families of polycubes have been investigated. The most well-known, for which there exists a rich literature, is the one of plane partitions (see \cite{BK72,CLP98,Bres99,Stan01} for instance). Recently, a new method has allowed us to enumerate several families of polycubes (in dimension $3$ and greater than $3$) as far as they can be split into strata \cite{CDJ13,Jea10, Dub11}. It is worthwhile noticing that  it is the investigation of the families of plateau and parallelogram polycubes (as reported in \cite{Sienne}) that motivated the design of this method.
%The main study that we present below is the preliminary one that led to this new method. 

\indent In the next section, following the model of polyominoes, we define several classes of polycubes and we recall a method, 
due to M. Bousquet-M\'elou \cite{Bo96}, for the enumeration of classes of 
column-convex polyominoes, that we will use to enumerate plateaus. Then, in Section 3, we present the results obtained for the enumeration of a particular class of vertically-convex polycubes (the  plateau ones). Partial results for one subclass (parallelogram polycubes) of the class of plateau polycubes are reported in Section 4. The last section contains asymptotic results concerning $d$-dimensional polycubes ($d\geq 3$) that can be deduced from results of Sections $3$ and $4$ and that complete those found in \cite{CDJ13}.


\section{Preliminaries}
\subsection{Polycubes}

\ \indent 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.

\indent Let $(0,\vec{i},\vec{j},\vec{k})$ be an orthonormal coordinate system
where  $\vec{i}$ and $\vec{k}$ are horizontal vectors and $\vec{j}$ the only vertical vector. 

\indent As for polyominoes, several parameters can be defined for a 
polycube. The \emph{volume} is the number of elementary cells, the
\emph{width} (resp. \emph{height, depth}) is the difference between the
greatest and the 
smallest indices of the polycube according to $\vec{i}$ (resp. $\vec{j}$, $\vec{k}$).
A polycube is said to be \emph{horizontally-convex} if its intersection with any horizontal plane $(\vec{i},\vec{k})$ is a row-convex polyomino;
it is said to be \emph{vertically-convex} if its intersection with any vertical plane $(\vec{i},\vec{j})$ is a column-convex polyomino. 
An example of horizontally-convex polycube is given in Figure~\ref{convexhori}.
Similarly, 
a polycube is said to be \emph{antihorizontally-convex} if its intersection with any horizontal plane $(\vec{i},\vec{k})$ is a column-convex polyomino;
it is said to be \emph{antivertically-convex} if its intersection with any vertical plane $(\vec{j},\vec{k})$ is a column-convex polyomino.



	\begin{figure}[ht]
	\begin{center}
		\begin{tikzpicture}[scale=.5,rotate=0]
			%polycube		
				\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,3/2/-1,3/2/0,4/2/-1,4/2/0,5/2/-1,1/0/1,-1/1/1,0/1/1,1/1/1,2/1/1,3/1/1,4/1/1,2/1/2,3/1/2}{
					\cube{\x}{\y}{\z}
				}
				
				
			%fleche	
			\begin{scope}[xshift = 5.1cm,yshift = 1.5cm]
				\fill[color = black!50, draw=black] (0,0,1) -- (0,0,-1) -- (3,0,-1) -- (3,0,-1.5) -- (4,0,0) -- (3,0,1.5) -- (3,0,1) -- cycle;
			\end{scope}

				\begin{scope}[xshift = 13cm]
					\draw[help lines] (0,0) grid (6,4);
					\foreach \x/\y in {3/0,4/0,0/1,1/1,2/1,3/1,4/1,5/1,2/2,3/2,4/2,5/2,2/3,3/3}{
						\cellule{\x}{\y};
					}
				\end{scope}
				
				
		\end{tikzpicture}
	\caption{A horizontally-convex polycube.}
	\label{convexhori}
	\end{center}
	\end{figure}


\indent A polycube is said to be \emph{convex} if it is both horizontally, antihorizontally, vertically and antivertically convex. The 2-dimensional notion of step is extended as follows. An \emph{East}
(resp.  \emph{North},  \emph{Ahead}) step is a move of one unit in the $\vec{i}$-direction 
(resp. $\vec{j}$-direction, $\vec{k}$-direction). So, 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.

\indent The 2-dimensional notion of column is extended as follows. 
A \emph{stratum} is a polycube of width 1.
Hence a stratum can be directed or horizontally (resp. vertically, antihorizontally, antivertically) convex.
Two examples of strata are given in Figure~\ref{strate}.
The notion of stratum allows us to define two new families of polycubes. 

\indent A polycube is said to be \emph{s-directed} if
the two following conditions are satisfied:\\
$(1)$ its strata are directed,\\
$(2)$ its strata are glued together so that the polycube is directed.

\indent A polycube is said to be \emph{vertically convex s-directed} if the two following conditions are satisfied:\\
$(1)$ its strata are vertically convex directed,\\
$(2)$ its strata are glued together so that the polycube is directed.

	\begin{figure}[h]
	\begin{center}
		\begin{tikzpicture}[scale=.6,rotate=0]
		\begin{scope}
			\foreach \y/\z in {0/1,0/3,1/0,1/1,1/2,1/3,1/4,2/0,2/4,3/0,3/2,3/4,4/0,4/1,4/2,4/3,4/4,5/0,5/1,5/3}{
				\cube{0}{\y}{\z}
			}
			\node at (0,-2) {$(1)$};
		\end{scope}
					
		\begin{scope}[xshift=6cm]
			\foreach \y/\z in {0/1,0/2,0/3,0/4,1/0,1/1,1/2,1/4,2/0,2/4,3/0,3/2,3/3,3/4,4/0,4/1,4/2,4/3,5/1,5/2}{
				\cube{0}{\y}{\z}
			}
			\node at (0,-2) {$(2)$};
		\end{scope}
		\end{tikzpicture}
	\end{center}
	\caption{An ordinary stratum $(1)$ and a directed stratum $(2)$.}
	\label{strate}
	\end{figure}

\indent A particular vertically convex s-directed polycube is the \emph{plateau polycube} that can be obtained
by gluing together vertical plateaus.

	\begin{figure}[ht!]
		\begin{center}
		\begin{tikzpicture}[scale = .5]
			\begin{scope}[xshift=0cm]
				\plateau{4}{5}
			\end{scope}
			\begin{scope}[xshift=1cm]
				\plateau{4}{4}
			\end{scope}
			\begin{scope}[xshift=2cm,yshift = 1cm]
				\plateau{4}{3}
			\end{scope}
			\begin{scope}[xshift=12cm, yshift = 1cm]
				\plateau{4}{4}
			\end{scope}
			
		\end{tikzpicture}
	\end{center}
	\caption{A plateau polycube of width $3$ and volume $75$ and a plateau of volume $25$.}
	\label{polyplateau}
	\end{figure}
		

\indent Intuitively, we define the  \emph{front} (resp. the  \emph{back}) of a polycube as
 the closest (resp. the furthest) side of the plane $(O,\vec{i},\vec{j})$.
The bottoms and the tops of a polycube are defined similarly as for a polyomino. 
A \emph{parallelogram polycube} is a plateau polycube such that each vertical plateau
 has no vertical plateau to its right and behind it that gets a cell under its bottom neither to its left and in front of it that gets a cell above its top.
Note that this definition implies that the projection of  a parallelogram 
polycube w.r.t. $(O,\vec{i},\vec{j})$ (resp.  w.r.t. $(O,\vec{j},\vec{k})$) gives a 
parallelogram polyomino.



\subsection{Enumeration}

\ \indent Let ${\cal R} = \mathbb{R} [[s,x,q]]$ be the algebra of formal power series in the variables
$s,x,q$ and with real coefficients and let ${\cal A}$ be a sub-algebra of ${\cal R}$ such that the series are convergent for $s=1$. If $X(s,x,q)$ is such a series, we will often denote it $X(s)$. Its derivative, with respect to $s$ will be denoted $X'(s)$. 

\indent In \cite{Bo96}, Bousquet-M\'elou uses the decomposition of column-convex polyominoes to express functional equations that have the same form for any class of convex polyominoes. She also proves the following
lemma to solve this type of equation:

\begin{lemma} \cite{Bo96} 
\label{lemmemireille}
Let $X(s)$ be a formal power series lying in $\cal A$.
Suppose that:
\[X(s)=xe(s)+x f(s)X(1)+x g(s)X(sq), 
\label{X.eq} 
\]
where $e(s)$, $f(s)$ 
and 
$g(s)$ 
are some given power series in $\cal
A$. Then
\[
X(1)=\frac{E(1)
}{
1-F(1)
}\ ,
\]
\noindent where 
\[
E(s)={\sum_{n\geq 0} x^{n+1}g(s)g(sq)\ldots
g(sq^{n-1})e(sq^n)}
\]
\noindent and 
\[
F(s)=\sum_{n\geq 0} x^{n+1}g(s)g(sq)\ldots g(sq^{n-1})f(sq^n).
\]
\end{lemma}



% Enum pvcd
%!TEX root = polycubes.tex
\section{Enumeration of plateau polycubes}

\ \indent 
A plateau polycube can be split into plateaus that are glued together. So, we need, at first, to find an 
expression of the generating function of plateaus with respect to height, volume and area of the rightmost face. Next, we use this result to enumerate plateau polycubes. 

\subsection{Case of plateaus}
 
\ \indent
Let $P(s,p,q)$ be the  generating function of vertical plateaus with respect to height (coded by $s$), volume (coded by $p$) and surface of the rightmost face (coded by $q$). Notice that the volume of a plateau is equal to the area of its rightmost face. However, as we need the area later, we simultaneously
consider the two parameters. Let us remark that our method is inspired by the one described in \cite{Bo96} to enumerate various classes of column-convex polygons. 

\indent
To enumerate vertical plateaus, we have to consider two different cases (see 
Figure~\ref{figpvcd}):
\begin{itemize}
\item the columns (vertical plateaus of depth 1): their generating function is
$\displaystyle{
\dfrac{spq}{1-spq}.
}$

\item the plateaus of depth $>1$: such plateaus are obtained by gluing a new column behind a plateau of depth $\geq 1$; they are enumerated by
$\displaystyle{
P(spq,p,q).
}$
\end{itemize}
\begin{figure}
\hspace*{17mm}
\begin{minipage}[t]{.3\linewidth}

		\begin{tikzpicture}[scale = .4]
			
			\begin{scope}[xshift = 0cm]
				\plateau{3}{3}
			\end{scope}
		
			\begin{scope}[xshift = 2cm]
				\node at (0,0) {=};
			\end{scope}
			
			\begin{scope}[xshift = 4cm]
				\cube{0}{0}{1}
				\bluecube{0}{1}{1}
				\bluecube{0}{2}{1}
				\bluecube{0}{3}{1}
			\end{scope}
			
			\begin{scope}[xshift = 6cm]
				\node at (0,0) {+};
			\end{scope}				
			
			\begin{scope}[xshift = 8cm]
				\bluecube{0}{0}{-1}
				\bluecube{0}{1}{-1}
				\bluecube{0}{2}{-1}
				\bluecube{0}{3}{-1}
				\plateau{3}{3}
			\end{scope}
			
%			\node at (0,-2) {$P(s,p,q)$};
%			\node at (2,-2) {=};
%			\node[state,minimum size = .1cm] at (4,-2) {1};
%			\node at (6,-2) {+};
%			\node[state,minimum size = .1cm] at (8,-2) {2};
		\end{tikzpicture}
	
\end{minipage}
\hspace*{4mm}
\begin{minipage}[t]{.45\linewidth}
		\begin{tikzpicture}[scale = .3]
				\begin{scope}[xshift = 0cm,yshift = 0cm]
					\plateau{3}{3}
				\end{scope}
				\begin{scope}[xshift = 1cm,yshift = 0cm]
					\plateau{3}{2}
				\end{scope}
				\begin{scope}[xshift = 2cm,yshift = 0cm]
					\plateau{3}{2}
				\end{scope}
				\begin{scope}[xshift = 3cm,yshift = 1cm]
					\plateau{3}{2}
				\end{scope}
				
				\begin{scope}[xshift=5.5cm,yshift=1cm]
					\node at (0,0) {$=$};
				\end{scope}
				
				\begin{scope}[xshift = 8cm,yshift = 0cm]
					\plateau{4}{4}
				\end{scope}
				
				
				\begin{scope}[xshift=11cm,yshift=1cm]
					\node at (0,0) {$+$};
				\end{scope}
				
				
				\begin{scope}[xshift = 14cm,yshift = 0cm]
					\plateau{4}{4}
				\end{scope}
				
				
				\begin{scope}[xshift = 15cm,yshift = 2cm]
					\plateau{3}{3}
				\end{scope}
				\begin{scope}[xshift = 16cm,yshift = 2cm]
					\plateau{3}{2}
				\end{scope}
				\begin{scope}[xshift = 17cm,yshift = 2cm]
					\plateau{3}{2}
				\end{scope}
				\begin{scope}[xshift = 18cm,yshift = 3cm]
					\plateau{3}{2}
				\end{scope}
				
%				
%				\begin{scope}[xshift = 0cm,yshift=-3cm]
%					\node at (2,0) {$G(t,p)$};
%					\node at (5.5,0) {$=$};
%					\node[state] at (8,0) {$1$};
%					\node at (11,0) {$+$};
%					\node[state] at (16,0) {$2$};					
%				\end{scope}
				
			\end{tikzpicture}
\end{minipage}
\caption{Decomposition of plateaus and plateau polycubes.}
\label{figpvcd}
\end{figure}

\indent Hence the following proposition:
\begin{proposition}
\label{fgplateaux}
The generating function $P(s,p,q)$ of plateaus satisfies the functional 
equation:
\[
P(s,p,q) = \dfrac{spq}{1-spq} + P(spq,p,q).
\]
\end{proposition}
\indent Using the Lemma \ref{lemmemireille}, we obtain the following
proposition: 

\begin{proposition}
\label{thpl}
The generating function $P(s,p,q)$ of plateaus satisfies:
\[
P(1,p,q) = \sum \limits_{n \geq 1} \dfrac{(pq)^n}{1-(pq)^n}.
\]
\end{proposition}
\indent Let $\displaystyle{P(1,p,1) = \sum \limits_{n \geq 1}f_n p^n}$;
we can remark that $f_n=\tau(n)$ is the number of divisors of $n$ 
\cite{www}. 
Finding a bijection  between these two families is trivial. For
instance, we just have to consider that a divisor $d$ of $n$ is in
bijection with the plateau of volume $n$ and height $d$. Notice also
that there is no explicit formula for $\tau(n)$. 

\subsection{Case of plateau polycubes}

\ \indent The idea is to decompose these polycubes in vertical plateaus. Let
G(t,p) be their generating function with respect to width and volume. We have to consider two cases to enumerate them:

\begin{itemize}
\item the plateau polycubes are plateaus: using proposition \ref{fgplateaux}, we immediately find that their generating function is $\displaystyle{t P(1,p,1)}$;
\item they can be split into a plateau on which we glue a plateau polycube: notice that the South-West corner of the polycube must be glued on a cell of the right face of the plateau; their generating function is \  $\displaystyle{t (\dfrac{\partial P}{\partial q})(1,p,1) G(t,p)}.$
\end{itemize}

\indent Finally, we obtain the following equation:
\[
G(t,p) = t P(1,p,1) + t(\dfrac{\partial P}{\partial q})(1,p,1)  G(t,p)
\]
\noindent and the following proposition:
\begin{proposition}
\label{fgpvcd}
\[
G(t,p) = \dfrac{t \sum \limits_{k\geq 1} \dfrac{p^k}{1-p^k}}{1- 
                              \sum \limits_{k \geq 1} \dfrac{ktp^k}{(1-p^k)^2}}.
\]
\end{proposition}

\begin{table}[hbt]
\caption{The first values of $g_{n,m}$.}
\label{tab_pvcd}
	\begin{small}
	\begin{tabular}{l | cccccccccccc}
		p$\backslash$t & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\
		\hline
		1 & 1 \\
		2 & 2 & 1 \\
		3 & 2 & 6 & 1 \\
		4 & 3 & 16 & 10 & 1 \\
		5 & 2 & 35 & 46 & 14 & 1 \\
		6 & 4 & 60 & 147 & 92 & 18 & 1 \\
		7 & 2 & 98 & 378 & 403 & 154 & 22 & 1 \\
		8 & 4 & 148 & 824 & 1372 & 867 & 232 & 26 & 1 \\
		9 & 3 & 198 & 1638 & 3894 & 3714 & 1603 & 326 & 30 & 1\\
		10 & 4 & 290 & 2948 & 9680 & 13068 & 8332 & 2675 & 436 & 34 & 1\\
		11 & 2 & 352 & 5029 & 21726 & 39594 & 35178 & 16410 & 4147 & 562 & 38 & 1\\
		12 & 6 & 480 & 8100 & 44836 & 106740 & 126540 & 81152 & 29388 & 6083 & 704 & 42 & 1\\
	\end{tabular}\\
	\end{small}
\end{table}

\indent From Proposition \ref{fgpvcd}, it is easy to obtain the first values of 
$G(t,p)$. They are given in Table~\ref{tab_pvcd}. 
From these values, it has 
been possible to find some properties about $G(t,p)$. Let us set 
$G(t,p) = \sum \limits_{n,m} g_{n,m}t^n p^m$ where $g_{n,m}$ is
the number of plateau polycubes of width $n$ and volume $m$.

\begin{proposition}\ \\
\label{proppp}
\hspace*{3.5cm}
\begin{tabular}{l}
  $\displaystyle{1.\hbox{\ \ } g_{1,n}=\tau(n)}$;\\
  $\displaystyle{2.\hbox{\ \ }g_{n,n}=1}$;\\
  $\displaystyle{3.\hbox{\ \ }g_{n-1,n}=4n-6}$;\\
  $\displaystyle{4.\hbox{\ \ }g_{n-2,n} =  8n^2-42n+56}$;\\
  $\displaystyle{5.\hbox{\ \ }g_{n-3,n}=\frac{32}{3}n^3 -120n^2 +\frac{1384}{3}n-605}.$
\end{tabular}

\end{proposition}

\begin{proof}
 The proofs of these formulas are based on a unique principle.  We
 start from the plateau of height 1, depth 1 and width $n-i,i\leq 3$ (and  
volume $n-i$). Next, we build all the polycubes of width $n-i$ and
volume $n$ from this plateau by adding $i$ cells, cutting and gluing
it. Thus, we only detail the proof of the value of $g_{n-2,n}$.
Let us consider the polycube of volume $n-2$ and width $n-2$ and let us
enumerate all  the ways to inject two cells to obtain a plateau
polycube. There are two main cases :

\begin{itemize}
\item the two cells are inserted on the same plateau:
  \begin{itemize}
  \item if we insert the cells on the last plateau, as in Figure
    \ref{inser1}, we have two possibilites, vertically or
    horizontally;
\begin{figure}[hbt]
				\begin{center}
					\begin{tikzpicture}[scale = .5]
						\begin{scope}
							\foreach \x in {0,1,2,3,4}{
								\cube{\x}{0}{0}
							}
						\bluecube{4}{1}{0}
						\bluecube{4}{2}{0}
						\end{scope}
				
						\begin{scope}[xshift = 10cm]
							\bluecube{4}{0}{-2}
							\bluecube{4}{0}{-1}
							\foreach \x in {0,1,2,3,4}{
								\cube{\x}{0}{0}
							}
						\end{scope}
					\end{tikzpicture}
				\end{center}
\caption{Insertion on the last plateau.}
\label{inser1}	
\end{figure}	
  \item otherwise, for a given column, there are six ways to insert two
    cells : three vertical insertions (see Figure \ref{inser2}) and
    three horizontal ones. As we can choose any of the $n-3$ columns, we obtain
    $6(n-3)$ possibilities.

\begin{figure}[hbt]    
    			\begin{center}
				\begin{tikzpicture}[scale = .5]
					\begin{scope}
						\foreach \x/\y/\z in {0/0/0,1/0/0,2/0/0,3/0/0,4/0/0}{
							\cube{\x}{\y}{\z}
						}
						\bluecube{2}{1}{0}
						\bluecube{2}{2}{0}
					\end{scope}
					\begin{scope}[xshift=7cm]
						\foreach \x/\y/\z in {0/0/0,1/0/0,2/0/0}{
							\cube{\x}{\y}{\z}
						}
						\bluecube{2}{1}{0}
						\bluecube{2}{2}{0}
						\cube{3}{1}{0}
						\cube{4}{1}{0}
					\end{scope}
					\begin{scope}[xshift=14cm]
						\foreach \x/\y/\z in {0/0/0,1/0/0,2/0/0}{
							\cube{\x}{\y}{\z}
						}
						\bluecube{2}{1}{0}
						\bluecube{2}{2}{0}
						\cube{3}{2}{0}
						\cube{4}{2}{0}
					\end{scope}
				\end{tikzpicture}
				\end{center}
\caption{Insertion on a plateau different of the last one.}
\label{inser2}	
\end{figure}
  \end{itemize}
\item the cells are inserted on two different plateaus, as in Figure
  \ref{inser3}:
  \begin{itemize}
  \item one of the two cells is on the last plateau and there are two different ways to glue it. The second cell is then  added to one of the
    $n-3$ other plateaus. Since we have four different ways to inject the cell,
    we obtain $8(n-3)$ possibilities;
 \begin{figure}[hbt]   		
			\begin{center}
					\begin{tikzpicture}[scale = .5]
						\begin{scope}
							\foreach \x in {0,1,2,3,4}{
								\cube{\x}{0}{0}
							}
							\bluecube{2}{1}{0}
							\bluecube{4}{1}{0}
						\end{scope}
						
						\begin{scope}[xshift = 6cm]
							\foreach \x in {0,1,2}{
								\cube{\x}{0}{0}
							}
							\bluecube{2}{1}{0}
							\cube{3}{1}{0}
							\cube{4}{1}{0}
							\bluecube{4}{2}{0}
						\end{scope}
						
						\begin{scope}[xshift = 12cm]
							\bluecube{2}{0}{-1}
							\foreach \x in {0,1,2,3,4}{
								\cube{\x}{0}{0}
							}
							\bluecube{4}{1}{0}
						\end{scope}
						
						\begin{scope}[xshift = 18cm]
							\bluecube{2}{0}{-1}
							\foreach \x in {0,1,2}{
								\cube{\x}{0}{0}
							}
							\cube{3}{0}{-1}
							\cube{4}{0}{-1}
							\bluecube{4}{1}{-1}
						\end{scope}
					\end{tikzpicture}
					\end{center}
  \caption{Insertion on two different plateaus.}
\label{inser3}	
\end{figure}  
  \item in the case where no cell is added to the last plateau, we
    have to choose 2 plateaus among $n-3$, what gives
    $\binom{n-3}{2}$ possibilities. Moreover, we have already
    established that there are 4 different ways to add a cell to a
    plateau. Since this operation must be applied on two different
    plateaus, we  obtain $4^2 \binom{n-3}{2}$ possibilities. 
  \end{itemize}
\end{itemize}
\ \indent When we add all the possibilities we finally find:
$\displaystyle{\hbox{\ \ }g_{n-2,n} =  8n^2-42n+56}$.


\end{proof}

\indent Notice that this proof is similar as the ones established  in \cite{CDJ13} in the case of the enumeration concerning families of $3$-dimensional polycubes. Moreover, it is not possible to find a formula in the general case because it depends on the $\tau(k)$ coefficients that do not have explicit formula. However, it is possible to state the following proposition: 

\begin{proposition}
\label{asymptplp}
 $\displaystyle{g_{n-i,n}}$ is a polynomial in $\mathbb{Q}[n]$ whose
  highest-degree-term is equal to $\displaystyle{\frac {4^i}{i!} n^{i}}.$
\end{proposition}

\begin{proof}
The proof is based on the same principle as in Proposition \ref{proppp}.
Let us consider the plateau of height 1, depth 1 and width $n-i$ and let us 
add to it $i$ cells on $i$ different columns (except for the last one).
We have $\binom {n-i-1}{i}$ different choices of columns. Then, for each 
selected column, we have $2*2$ possible constructions to obtain a polycube. As
we perform this construction on $i$ columns, we finally obtain 
$4^i \binom {n-i-1}{i}$ possibilities. 

\indent In all the other cases, we only have  $\binom {n-i-1}{i-j}$, $j>1$, 
possibilities to choose columns, leading to a term of degree
$i-j$. Since $j>1$, the highest-degree-term is in $O(n^{i-j})$, which is
unimportant in front of $O(n^{i})$.
So, the highest degree term in $n$ is $\frac{4^i}{i!} n^{i}$.
\end{proof}

\indent Computing a polynomial interpolation of $G(t,p)$ leads to the following results:

\begin{corollary}
		\begin{align*}
			g_{n-3,n} &= \dfrac{32}{3} n^3 - 120 n^2 + \dfrac{1384}{3} n - 605\\
			g_{n-4,n} &= \dfrac{32}{3} n^4 - 208 n^3 + \dfrac{4678}{3} n^2 -5324 n + 6972\\
			g_{n-5,n} &= \dfrac{128}{15} n^5 - 256 n^4 + 3144 n^3 - 19756 n^2 + \dfrac{951742}{15} n - 83160\\
			g_{n-6,n} &= \dfrac{256}{45} n^6 - \dfrac{1216}{5} n^5 + \dfrac{39824}{9} n^4 - \dfrac{131572}{3} n^3 + \dfrac{11231344}{45} n^2 - \dfrac{11583502}{15} n\\ &+ 1013028\\
			g_{n-7,n} &= \dfrac{1024}{315} n^7 - \dfrac{2816}{15} n^6 + \dfrac{213184}{45} n^5 - \dfrac{203152}{3} n^4 + \dfrac{26635408}{45} n^3 - \dfrac{47411774}{15} n^2\\  &+ \dfrac{333749548}{35} n - 12517020\\
			g_{n-8,n} &= \dfrac{512}{315} n^8 - \dfrac{2560}{21} n^7 + \dfrac{183232}{45} n^6 - \dfrac{237344}{3} n^5 + \dfrac{43996894}{45} n^4 - 7864440 n^3\\ &+ \dfrac{12654017396}{315} n^2 - \dfrac{832930465}{7} n + 156257400
		\end{align*}
\end{corollary}

\section{Some propositions about  parallelogram polycubes}

\ \indent Let us establish a functional equation satisfied by the
 generating function of parallelogram polycubes with respect to several
 parameters. We first introduce the following variables:
\begin{itemize}
\item $p$ that encodes the volume of the polycube;
\item $t$, its width;
\item $q$, the area of the rightmost face of the polycube;
\item $h$, the heigth of the last plateau;
\item $r$, the depth of the last plateau.
\end{itemize}

\indent Let us note $H(t,h,r,p,q) = \sum \limits_{n,m}h_{n,m}t^n
p^m$, the generating function of parallelogram polycubes with respect to
the above-mentioned parameters. Let us notice that these
polycubes appear in the modelling of real-time applications
composed of two periodic tasks \cite{Lar04}.

\begin{figure}[h!]
	\begin{tabular}{ccc}
		%Pp
		\begin{tikzpicture} [scale = .8]
			\draw (0,0,0) -- (3,1,0) -- (3,3,0) -- (0,2,0) -- cycle;
			\draw (0,2,0) -- (0,2,-2) -- (3,3,-2) -- (3,3,0);
			\draw (3,1,0) -- (3,1,-2) -- (3,3,-2);
			
			\node at (1.5,1.5) {1};
			
			
			\node at (4.5,1) {\huge{=}};
		\end{tikzpicture}
		
		&
		
		%plateau
		\begin{tikzpicture} [scale = .8]
			\draw (0,0,0) rectangle +(.5,2);
			\draw (0,2,0) -- (0,2,-2) -- (.5,2,-2) -- (.5,2,0);
			\draw (.5,0,0) -- (.5,0,-2) -- (.5,2,-2);
			
			\node at (.5,1,-1) {2};
			
			\node at (3.5,1) {\huge{+}};
		\end{tikzpicture}
		
		&
		
		\begin{tikzpicture} [scale = .8]
			\draw (0,0,0) -- (3,1,0) -- (3,3,0) -- (0,2,0) -- cycle;
			\draw (0,2,0) -- (0,2,-2) -- (3,3,-2) -- (3,3,0);
			\draw (3,1,0) -- (3,1,-2) -- (3,3,-2);
			
			\node at (1.5,1.5) {3};
			
			\draw [thick,->] (3.25,2.5,-1.75) -- (3.25,2,-1.75);
			\draw [thick,->] (3.25,2.75,-2) -- (3.25,2.75,-3.25);
			
			
			\fill[color = black!30] (3,2.5,-1.5) -- (3,3,-1.5) -- (3,3,-2) -- (3.5,3,-2) -- (3.5,2.5,-2) -- (3.5,2.5,-1.5) -- cycle;
			\draw (3,2.5,-1.5) rectangle +(.5,.5);
			\draw (3.5,2.5,-1.5) -- (3.5,2.5,-2) -- (3.5,3,-2) -- (3,3,-2);
			\draw (3.5,3,-2) -- (3.5,3,-1.5);
			\draw (3,3,-1.5) -- (3,3,-2);
			
			\draw [thick,->] (3.25,3,-1.75) -- (3.25,3.5,-1.75);
			\draw [thick,->] (3.25,2.75,-1.5) -- (3.25,2.75,-.5);
			
		\end{tikzpicture}
		
		\\
		
		&
		
		\begin{tikzpicture} [scale = .8]
			\node at (-1,1) {\huge{-}};
			
			\node at (1.5,1.5) {4};
			
			\draw (0,0,0) -- (3,1,0) -- (3,3,0) -- (0,2,0) -- cycle;
			\draw (0,2,0) -- (0,2,-2) -- (3,3,-2) -- (3,3,0);
			\draw (3,1,0) -- (3,1,-2) -- (3,3,-2);
			
			\draw [thick,->] (3.25,.5,-1.75) -- (3.25,0,-1.75);
			\draw [thick,->] (3.25,1.75,-2) -- (3.25,1.75,-3.25);
			
			
			\fill[color = black!30] (3,3,-1.5) -- (3,3,-2) -- (3.5,3,-2) -- (3.5,.5,-2) -- (3.5,.5,-1.5) -- (3,.5,-1.5) -- cycle;
			\fill[color = black!70] (3,1,-1.5) -- (3.5,1,-1.5) -- (3.5,1,-2) -- (3.5,.5,-2) -- (3.5,.5,-1.5) -- (3,.5,-1.5) -- cycle;
			\draw (3,3,-1.5) rectangle +(.5,-2.5);
			\draw (3,3,-1.5) -- (3,3,-2) -- (3.5,3,-2) -- (3.5,.5,-2) -- (3.5,.5,-1.5);
			\draw (3.5,3,-1.5) -- (3.5,3,-2);
			
			\draw [thick,->] (3.25,3,-1.75) -- (3.25,3.5,-1.75);
			\draw [thick,->] (3.25,1.75,-1.5) -- (3.25,1.75,-.5);
			
		\end{tikzpicture}
		
		&
		
		\begin{tikzpicture} [scale = .8]
			\node at (-1,1) {\huge{-}};
			
			\node at (1.5,1.5) {5};
			
			\draw (0,0,0) -- (3,1,0) -- (3,3,0) -- (0,2,0) -- cycle;
			\draw (0,2,0) -- (0,2,-2) -- (3,3,-2) -- (3,3,0);
			\draw (3,1,0) -- (3,1,-2) -- (3,3,-2);
			
			\draw [thick,->] (3.25,2.5,-.75) -- (3.25,2,-.75);
			\draw [thick,->] (3.25,2.75,-2) -- (3.25,2.75,-3.25);
			
			
			\fill[color = black!30] (3,2.5,.5) -- (3,3,.5) -- (3,3,-2) -- (3.5,3,-2) -- (3.5,2.5,-2) -- (3.5,2.5,.5) -- cycle;
			\fill[color = black!70] (3,3,0) -- (3.5,3,0) -- (3.5,2.5,0) -- (3.5,2.5,.5) -- (3,2.5,.5) -- (3,3,.5) -- cycle;
			\draw (3,2.5,.5) rectangle +(.5,.5);
			\draw (3,3,.5) -- (3,3,-2) -- (3.5,3,-2) -- (3.5,3,.5);
			\draw (3.5,2.5,.5) -- (3.5,2.5,-2) -- (3.5,3,-2);
			
			\draw [thick,->] (3.25,3,-.75) -- (3.25,3.5,-.75);
			\draw [thick,->] (3.25,2.75,.5) -- (3.25,2.75,1.5);
			
		\end{tikzpicture}
		
		
		\\
		
		&
		
		\begin{tikzpicture} [scale = .8]
			\node at (-1,1) {\huge{+}};
			
			\node at (1.5,1.5) {6};
		
			\draw (0,0,0) -- (3,1,0) -- (3,3,0) -- (0,2,0) -- cycle;
			\draw (0,2,0) -- (0,2,-2) -- (3,3,-2) -- (3,3,0);
			\draw (3,1,0) -- (3,1,-2) -- (3,3,-2);
			
			\draw [thick,->] (3.25,.5,-.75) -- (3.25,0,-.75);
			\draw [thick,->] (3.25,1.75,-2) -- (3.25,1.75,-3.25);
			
			
			\fill[color = black!30] (3,3,.5) -- (3,3,-2) -- (3.5,3,-2) -- (3.5,.5,-2) -- (3.5,.5,.5) -- (3,.5,.5) -- cycle;
			\fill[color = black!70] (3,3,0) -- (3.5,3,0) -- (3.5,1,0) -- (3.5,1,-2) -- (3.5,.5,-2) -- (3.5,.5,.5) -- (3,.5,.5) -- (3,3,.5) -- cycle;
			\draw (3,3,.5) rectangle +(.5,-2.5);
			\draw (3,3,.5) -- (3,3,-2) -- (3.5,3,-2) -- (3.5,3,.5);
			\draw (3.5,3,-2) -- (3.5,.5,-2) -- (3.5,.5,.5);
			
			\draw [thick,->] (3.25,3,-.75) -- (3.25,3.5,-.75);
			\draw [thick,->] (3.25,1.75,.5) -- (3.25,1.75,1.5);
			
		\end{tikzpicture}
		
	\end{tabular}
	\caption{Decomposition of the construction of a parallelogram polycube.}
	\label{fig_Pp}
	\end{figure}		

\indent Let us consider a parallelogram polycube. Then, several cases can appear:
\begin{itemize}
\item The first case (decomposition 2 in Figure \ref{fig_Pp}) is the
  one where it is reduced to a plateau. Thus, it is  enumerated by
  $Pl(t,h,r,p,q)$. 
\item Otherwise, the parallelogram polycube can be built from a
  smaller polycube, adding to it a new plateau. We start by gluing a
  cell at   the top and at the bottom of the rightmost plateau
  (decomposition 3 in Figure \ref{fig_Pp}). We add as many cells as we
  want on   the top and under the bottom. Then, we duplicate
  this column upward   and downward to build the last plateau. 
	
	Let us translate this construction into a generating function. All the possibilities are enumerated by	$H(t,h,r,p,q)$.

	We begin by gluing a cell at  the top and at the bottom of the rightmost plateau. Adding a new cell leads to the creation of a new plateau and the new cell is coded by $pqrh$. 
	The constructions that we obtain are enumerated by
		$H(t,1,1,p,1)pqrth$.
	
	Then, we make the cell grow up and down. Adding a cell amounts to an increase of $1$ of the area, the volume and the height of the rightmost plateau, which leads to a factor $pqh$.
	Adding as many cells as possible upward is enumerated by: 
\begin{center}	
	$1+pqh+(pqh)^2+\ldots+(pqh)^n = \dfrac{1}{1-pqh}$.
\end{center}
	
	A similar reasoning for downward growth leads to a factor $\dfrac{1}{(1-pqh)^2}$.
	Therefore we get the following generating function:
	\begin{center}
		$H(t,1,1,p,1)\dfrac{pqrth}{(1-pqh)^2}$.
	\end{center}
	
	Finally, we must make grow simultaneously and identically all the lines of the newly created column, to obtain any plateau. Let us notice that there are  $n+1$ different ways to add $n$ cells to make a line from a cell.
	It means that, for the last plateau, we substitute $p$ by $p^{n+1}$, $q$ by $q^{n+1}$ and $r$ by $r^{n+1}$, for all $n\geq 0$.	
	Then, the generating function of the second case is: 
	\begin{center}
		$\bigsum_{n\geq 0} (n+1) H(t,1,1,p,1) \dfrac{p^{n+1}q^{n+1}r^{n+1}th}{(1-p^{n+1}q^{n+1}h)^2}$.
	\end{center}
	
\item The previous growth creates polycubes that are not   parallelograms, in particular when the last plateau has a too low bottom (decomposition 4 in  Figure~\ref{fig_Pp}). 
  
	To begin, let us consider a parallelogram polycube. %, enumerated by $H(t,h,r,p,q)$.
	We stick at the back a column of height equal to the height of the last plateau, what means we add a new plateau. This is translated by substituting $h$ by $hpq$. Next, we add a unique cell under this column. This is translated by $H(t,hpq,1,p,1)pqrth$.	 
	 Then, we make the column grow upward and downward, what leads, as previously, to a factor $\dfrac{1}{(1-pqh)^2}$. 
	 
	 Finally, the simultaneous and identical growth of all the lines of the created column is generated by the substitution, for the last plateau, of  $p$ by $p^{n+1}$, $q$ by $q^{n+1}$ and $r$ of $r^{n+1}$, for all $n\geq 0$.	 
	This case is enumerated by:
	\begin{center}
		$\sum \limits_{n \geq 0} (n+1)  H(t,hp^{n+1}q^{n+1},1,p,1)  \dfrac{p^{n+1}  q^{n+1}   r^{n+1} t  h}{(1-p^{n+1}q^{n+1}h)^{2}}$.
	\end{center}

\item We also have to remove polycubes such that last plateau has
  a too much forward front face (decomposition 5 in Figure \ref{fig_Pp}). 

We can notice that, compared wtih the case of upward growth, we simply have to invert the role of $r$ and $h$, what allows us to conclude that this case is enumerated by:
  	\begin{center}
		$\sum \limits_{n \geq 0} (n+1)  H(t,1,rp^{n+1}q^{n+1},p,1)  \dfrac{p^{n+1}  q^{n+1}   r t  h^{n+1}}{(1-rp^{n+1}q^{n+1})^{2}}$.
	\end{center}
	
\item  Computing the above expression, we have removed twice the polycubes
 such that their last plateau has a bottom too low and a front face
 too  much forward (decomposition 6 in Figure \ref{fig_Pp}). So, we
 have to add their generating function.
	
\indent One more time, let us consider a parallelogram polycube, enumerated by  $H(t,h,r,p,q)$. First, we duplicate the last plateau, what is expressed by $H(t, hpq, rpq, p, 1)t$. Second, we add a line and a column to this plateau, what is enumerated by $H(t,(h+1)pq,(r+1)pq,p,1) pqrth$.
Then, we make grow upward and backward the plateau, which leads, for the last plateau, to substitute $p$ by $p^{n+1}$, $q$ by $q^{n+1}$ and $r$ by $r^{n+1}$, for all $n\geq 0$:
	\begin{center}
		$\bigsum_{n\geq 0} (n+1) H(t,(h^{n+1}+1)p^{n+1}q^{n+1},(r+1)pq,p,1) p^{n+1}q^{n+1}rth^{n+1}$.
	\end{center}
	
	Thus, the upward and backward growth allows us to find the following generating function:
	\begin{align*}
		\bigsum_{m\geq 0} \bigsum_{n\geq 0}  & (m+1)  (n+1) t r^{m+1} h^{n+1} (pq)^{n+m+1}\\
		& \times H(t,(h^{n+1}+1)p^{n+1}q^{n+1}, (r^{m+1}+1)p^{m+1}q^{m+1},p,1).
	\end{align*}
\end{itemize}	


\begin{proposition}
The generating function of the parallelogram polycubes with respect to volume, width, area of the rightmost face, heigth of the last plateau and depth satisfies:

\begin{tabular}{lcl}
			$H(t,h,r,p,q)$ & $=$ & $Pl(t,h,r,p,q)$ \\
			&$+$ &$ \bigsum_{n\geq 0} (n+1) H(t,1,1,p,1) \dfrac{p^{n+1}q^{n+1}r^{n+1}th}{(1-p^{n+1}q^{n+1}h)^2} $\\
			&$-$ & $ \sum \limits_{n \geq 0} (n+1)  H(t,hp^{n+1}q^{n+1},1,p,1)  \dfrac{p^{n+1}  q^{n+1}   r^{n+1} t  h}{(1-p^{n+1}q^{n+1}h)^{2}}$\\
			&$-$&$ \sum \limits_{n \geq 0} (n+1)  H(t,1,rp^{n+1}q^{n+1},p,1)  \dfrac{p^{n+1}  q^{n+1}   r t  h^{n+1}}{(1-rp^{n+1}q^{n+1})^{2}} $\\
			&$+$&$ \bigsum_{m\geq 0} \bigsum_{n\geq 0}  (m+1)  (n+1) t r^{m+1} h^{n+1} (pq)^{n+m+1}$\\
		 &$\times$& $H(t,(h^{n+1}+1)p^{n+1}q^{n+1}, (r^{m+1}+1)p^{m+1}q^{m+1},p,1)$
		\end{tabular}

\end{proposition}


\indent Unfortunately, we did not succeed in solving the previous functional equation.  
As far as we know, there is, at the moment, no method allowing us to find an expression of $H(t,p)$. However, it has been possible to extend some properties of $P(t,p,)$ to $H(t,p)$. Their characterization is summed up in the following proposition: 


\begin{proposition}\ \\
\hspace*{3.5cm}
\begin{tabular}{l}
  $\displaystyle{1.\hbox{\ \ } h_{n,n} = 1}$;\\
  $\displaystyle{2.\hbox{\ \ } h_{1,n} = \tau(n)}$;\\
  $\displaystyle{3.\hbox{\ \ } h_{n-1,n} = 2(n-1)}$;\\
  $\displaystyle{4.\hbox{\ \ } h_{n-2,n} = 2n^2-6n+2}$;\\
  $\displaystyle{4.\hbox{\ \ } h_{n-3,n} = \frac{4}{3}n^3- 8n^2+\frac{23}{3}n+13}$.
  \end{tabular}
\end{proposition}

\indent The proof is similar as the one of Proposition \ref{proppp}. Since the values of $h_{n-i,n}$ depend on the values of $\tau(i)$ it is not possible to find a general formula. However, with a similar proof as for Proposition \ref{asymptplp} it is possible to find the asymptotic value of the polynomial:

\begin{proposition}
 $\displaystyle{h_{n-i,n}}$ is a polynomial in $\mathbb{Q}[n]$ whose highest-degree-term is equal to $\frac{2^i}{i!} n^{i}$.
\end{proposition}


% Asymptotiques
\section{Asymptotic $d$-dimensional results}

\ \indent We first generalize some parameters and definitions from $3$-dimensional polycubes to $d$-dimensional ones, with $d\geq 4$.
Then we give some asymptotic results concerning three new families of $d$-dimensional polycubes. Let us remark that these results extend the ones established  in \cite{CDJ13} in the case of specific $d$-dimensional polycubes.


\subsection{The extension to $d$-dimensional polycubes}
\ \indent 
Let us now consider $\mathbb{N}^d$, with 
$d\geq 3$.
An elementary cell is a unitary $d$-cube.
A $d$-polycube
is then a $d$-face connected finite set of elementary cells, defined up to a translation.
The volume of a $d$-polycube is the number of its elementary cells.

\indent Let $(0,\vec{i_1},\ldots,\vec{i_d})$ be an orthonormal coordinate system.   
The \emph{width} (resp. \emph{height}) of a $d$-polycube is the difference
between its greatest index and its smallest index according to $\vec{i_1}$ (resp. $\vec{i_2}$).
A $d$-polycube is said to be \emph{vertically-convex}
if its intersection with any hyperplane
$(\vec{i_2},\ldots,\vec{i_d})$
is a vertically-convex $(d-1)$-polycube. It is said \emph{horizontally-convex} if its intersection with any hyperplane $(\vec{i_1},\vec{i_3},\vec{i_4},\ldots,\vec{i_d})$ is a  horizontally-convex $(d-1)$-polycube.
Other convexities can be defined, but they are not useful here.

\indent The notion of \emph{step} is extended as follows.
A \emph{step in direction j} is a positive move of one unit along the axis $\vec{i_j}$.
Then a \emph{directed} $d$-polycube is such that each cell can be reached from a distinguished one, the root,
by a path only made of steps in direction $j$, with $1 \leq j \leq d$.

\indent A \emph{d-stratum} of a $d$-polycube is a $d$-polycube of width 1.
We will say stratum instead of $d$-stratum if there is no ambiguity.
For $d\geq 3$, the \emph{rightmost face} of the $i$th stratum
is the $d$-face of this stratum on which is glued the $(i+1)^{th}$ stratum
and its surface is the number of its cells.
The $(i+1)^{th}$ stratum is called the \emph{rightmost stratum} of the $i^{th}$ one.

\indent A \emph{s-d-polycube} is a $d$-polycube that can be split into strata. 
A \emph{pseudo-directed d-polycube} is a $s$-$d$-polycube such that each of its strata has to be glued to the previous one using a distinguished cell that must coincide with any cell of the previous stratum.
The distinguished cell of a stratum can be, for instance, the lowest cell of the first column.
In fact, the distinguished cell plays the same role as the root in the case of directed polycubes.
Even if the considered strata are not directed, they are glued according to a similar rule.
 
\subsection{Asymptotic results}
 
\ \indent Let $d\geq 3$ and  let
$\displaystyle{R^d (t,p)=\sum_{n,m\geq 0} R^d_{n,m} t^ n p^m}$ 
the generating function of directed s-$d$-polycubes with respect to width and volume.
\begin{proposition} 
\label{asymptspd}
The expresssion $\displaystyle{r^d_{n-i,n}}$ is a polynomial in $\mathbb{Q}[n]$ whose highest-degree-term is equal to
$\displaystyle{\frac {2^i(d-1)^i}{i!} n^{i}}$.  
\end{proposition}

\begin{proof} The proof is
essentially based on the fact that adding a cell to a stratum of a directed s-$d$-polycube is equivalent to inject a cell into a directed s-$(d-1)$-polycube.
As a consequence, there is a unique possibility to add a cell to a $d$-stratum of volume 1 with respect to each of the $d-1$ directions.
Then, the rightmost stratum initially glued to the modified stratum can be glued again 
in two different ways in order to satisfy the property of direction of directed s-$d$-polycubes.
Note that the last stratum is not concerned by this construction since it has no rightmost stratum.
So, there are $2(d-1)$ possible constructions for the $i$ selected strata,
which leads to $(2(d-1))^i \binom {n-i-1}{i}$ possibilities to realize this operation.
If the last stratum belongs to the set of selected strata, there are only $2^i \times (d-1)^{i-1} \binom {n-i-2}{i}$ possibilities.
In all the other cases, there are $\binom {n-i-1}{i-j}$ or $\binom {n-i-2}{i-j}$ (and $j>1$)
possibilities to choose strata, leading to a term of degree $i-j$.
Since $j>1$, the highest-degree-term in $O(n^{i-j})$ is unimportant with respect to  $n^{i}$.
Finally, the highest-degree-term of $\displaystyle{r^d_{n-i,n}}$
is equal to $\displaystyle{\frac {2^i(d-1)^i}{i!} n^{i}}$. 
\end{proof}

\indent Let $\displaystyle{U^d (t,p)=\sum_{n,m\geq 0} u^d_{n,m} t^ n p^m}$ the generating function of directed s-polycubes with respect to width and volume. With a similar reasoning, it is also possible to prove the following result:

\begin{proposition} 
\label{asymptpdp}
The expresssion $\displaystyle{u^d_{n-i,n}}$ is a polynomial in $\mathbb{Q}[n]$ whose highest-degree-term is equal to
$\displaystyle{\frac {2^i(d-1)^i}{i!} n^{i}}$.  
\end{proposition}
    
\indent Note that, in \cite{CDJ13}, the same asymptotic result appears for another class of polycubes, the 
rs-directed $d$-polycubes. Moreover, the Propositions  \ref{asymptspd} and \ref{asymptpdp} generalize known results in dimension $3$ \cite{CDJ13}.

\indent Let us now adress the case of s-$d$-polycubes. Let $V^d (t,p)=\sum_{n,m\geq 0} v^d_{n,m} t^ n p^m$ their generating function with respect to width and volume.

\begin{proposition}
\label{asympt2}
The expresssion $\displaystyle{v^d_{n-i,n}}$ is a polynomial in $\mathbb{Q}[n]$ whose highest-degree-term is of the form
$\displaystyle{\frac {\alpha 2^i(d-1)^i}{i!} n^{i}}$ where $\alpha$ is a power of $2$ such that $1\leq\alpha\leq 2^i$.  
\end{proposition}

\begin{proof}
The difference with proofs of Propositions \ref{asymptspd} and \ref{asympt2} results from the gluing of modified strata. As the considered $d$-polycube is no more directed, there are not necessarily two different ways to glue again the rightmost stratum initially glued to the modified stratum. If the rightmost stratum contains only one cell, there are effectively two ways. But if it contains two cells, there are four ways of gluing, which leads to the proposition. 
\end{proof}
    


%Conclu
%!TEX root = polycubes.tex
\section{Conclusion}

\ \indent After introducing criteria to easily characterize classes of polycubes, we have defined a new directed family, the plateau polycubes, that we have enumerated with respect to volume and width. We also have exhibited a subclass: the parallelogram polycubes. Even though we did not find an expression of their generating
function, it has been possible to extend to these polycubes the main properties found for the plateau polycubes. Moreover, this work has also allowed us to extend to any dimension two asymptotic results valid for some classes of $3$-dimensional polycubes and to find another one concerning the enumeration of $d$-dimensional polycubes ($d\geq 3$) that can be split into strata. We currently work on how to refine the study of parallelogram polycubes and, more precisely, we expect to find a general expression for their generating function. We also expect to find formulae for new families of s-$d$-polycubes.


%Biblio
%!TEX root = polycubes.tex

\begin{thebibliography}{8}

\bibitem{AS64}{M. Abramowitz, I. A. Stegun, eds.}, Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55 (1964),
840. 
\bibitem{AB06}{ G. Aleksandrowicz, G. Barequet}, Counting $d$-dimensional 
polycubes and nonrectangular planar polyominoes, in Proc: 12th Ann. Int. 
Computing Combinatorics Conf., Taipei, Taiwan in: Lecture Notes in Computer 
Science, vol. 4112, Spinger-Verlag (2006), 418-427.

\bibitem{BK72}{E.A. Bender, D.E. Knuth}, Enumeration of Plane Partitions,
 J. Combin. Theory Ser. A. 13 (1972), 40-54.

\bibitem{Bres99}{Bressoud, D.M.}, Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, Spectrum Series, Cambridge University Press (1999).
 
\bibitem{BH57}{ S.R. Broadbent, J.M. Hammersley}, Percolation processes; I. 
Crystals and mazes, Proc. Camb. Philos. Soc. 53 (1957),629-641.

\bibitem{Bo96}{ M. Bousquet-M\'elou}, A method for the enumeration of
various classes of column-convex polygons, Discrete Mathematics, vol 154
(1996), 4-25.

\bibitem{BCD07}{B. Blanpain, J.-M. Champarnaud, J.-Ph. Dubernard},
    Geometrical Languages, LATA 2007, Report 35/07, GRLMC Universitat Rovira I Virgili 52007, 127-138.

\bibitem{CDJ09}{J.-M. Champarnaud, J.-Ph. Dubernard, H. Jeanne}, An efficient algorithm to test whether a binary and prolongeable language is geometrical, 
Int. J. Found. Comput. Sci.Vol. 20(4) (2009), 763-774.

\bibitem{Sienne}{J.-M. Champarnaud, J.-Ph. Dubernard, H. Jeanne}, Enumeration of specific classes of polycubes, Lattice Path Combinatorics and Applications, Siena, Italy (2010), 79-87.

\bibitem{CDJ13}{J.-M. Champarnaud, J.-Ph. Dubernard, H. Jeanne}, A generic method for the enumeration of
various classes of directed polycubes, 
Discrete Mathematics {\&} Theoretical Computer Science 15:1 (2013), 183-200.


\bibitem{CLP98}{H. Cohn, M. Larsen, J. Propp}, The Shape of a Typical Boxed Plane Partition, New York J. Math. 4 (1998), 137-166.

\bibitem{Dub11}{J.-Ph. Dubernard}, {\'E}num{\'e}rations, Automates et Langages G{\'e}om{\'e}triques, M{\'e}moire d’ha\-bi\-li\-ta\-tion \`a diriger des recherches, Universit\'e de Rouen, 25 Novembre 2011.

\bibitem{Fer04}{S. Feretic}, A $q$-enumeration of convex polyominoes by festoon approach, Theoret. Comput. Sci., 319(1-3) (2004), 333-356.

\bibitem{Jea10}{H. Jeanne}, Langages g{\'e}om{\'e}triques et polycubes, PhD thesis, Universit\'e de Rouen (2010).

\bibitem{Lar04}{G. Largeteau}, Quantification du taux d'invalidit\'e d'applications temps-r\'eel \`a contraintes strictes, PhD Thesis, Universit\'e de Poitiers, 2004.

\bibitem{LG08}{G. Largeteau, D. Geniet}, Quantification du taux d'invalidit\'e d'applications temps-r\'eel \`a contraintes strictes, Tech. et Sci. Inf. 27(5) (2008), 589-625

\bibitem{Lu71}{ W.F. Lunnon}, Counting polyominoes, in: A.O.L. Atkin B.J. 
Birch (Eds), Computers in Number Theory, Academic Press, London (1971), 347-372. 

\bibitem{Lu72}{ W.F. Lunnon}, Symmetry of cubical and general polyominoes, in:
 R.C. Read (Eds), Graph Theory and Computing,  Academic Press, London (1972),
101-109 

\bibitem{Stan01}{Stanley, R.P.}, Enumerative combinatorics. 2, chapter 7, Cambridge Studies in Advanced Math, Wadsworth \& Brooks/Cole Advanced Books \& Software (2001).


\bibitem{www}The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com, sequence A000005.
\end{thebibliography}




\end{document}
