\documentclass[12pt]{article}
\textwidth 16.5cm
\textheight 23cm
\topmargin  -1cm
\oddsidemargin -0.5cm
\newcommand{\dimos}{{\bf Preuve.} }
\newcommand{\finedimos}{\hfill \fbox{} \\}
\newtheorem{teor}{Th\'eor\`eme}[section]
\newtheorem{defi}[teor]{D\'efinition}
\newtheorem{prop}[teor]{Proposition}
\newtheorem{cor}[teor]{Corollaire}
\newtheorem{conge}[teor]{Conjecture}
\def\theequation{\thesection.\arabic{equation}}
\begin{document}
\setlength{\unitlength}{0.5cm}
\title{La hauteur des polyominos dirig\'es verticalement convexes}
\author{Elena Barcucci, Alberto Del Lungo, Renzo Pinzani, Renzo Sprugnoli\\
\\ Dipartimento di Sistemi e Informatica\\
Via Lombroso 6/17- Firenze - Italy\\
}
\date{}
\maketitle
%%%%%%%%%%%%%%
%INTRODUZIONE%
%%%%%%%%%%%%%%
\normalsize
\section{Introduction}
Les polyominos (et les animaux qui sont des structures \'equivalentes) ont
\'et\'e \'etudi\'es aussi bien par les math\'ematiciens, car ils constituent
des objects combinatoires qui ont des propri\'et\'es tr\`es int\'eressantes
\cite{Vi1}, que par les physiciens car ils repr\'esentent des mod\`eles pour
plusieurs ph\'enom\`enes physiques \cite{Vi}.\newline
Si nous consid\'erons le plan ${\bf R}\times {\bf R}$ nous pouvons d\'efinir
une {\em cellule} comme un carr\'e unitaire $[i,i+1]\times [j,j+1]$
($i,j\in {\bf N})$ et un {\em polyomino} comme un ensemble connexe de cellules
qui sont deux \`a deux adjacentes par un c\^ot\'e. Les polyominos sont d\'efinis
\`a une translation pr\`es. Pour obtenir un animal d'un polyomino il suffit
consid\'erer les centres des cellules qui le composent. Les d\'efinitions des
param\`etres caract\'erisant les polyominos sont tr\`es intuitives:
\begin{quote}
  - l'{\em aire} d'un polyomino est le nombre de cellules qui le composent,

  - le {\em p\'erim\`etre} est la longueur de son contour,

  - une {\em colonne} (resp. {\em ligne}) est l'intersection du polyomino avec
  une bande verticale (resp. horizontale) infinie $[i,i+1]\times {\bf R}$ (resp.
  ${\bf R} \times[j,j+1] $).
\end{quote}
Tant pour les polyominos que pour les animaux on peut introduire les notions
de {\em direction privil\'egi\'ee} et de {\em convexit\'e}. Un polyomino
dirig\'e est un polyomino qui peut \^etre obtenu \`a partir d'une cellule
appel\'ee source en ajoutant des cellules dans deux directions (par exemple
Nord et Est, c'est-\`a-dire au-dessus et \`a droite des cellules d\'ej\`a
pr\'esentes). De cette fa\c con le polyomino se d\'eveloppe dans une direction
(par exemple Nord-Est) qui est appel\'ee direction privil\'egi\'ee. Un polyomino est
{\em verticalement convexe} (resp. {\em horizontalement convexe, convexe}) si
ses colonnes (resp. lignes, lignes et colonnes) sont connexes.\newline
M\^eme si les polyominos sont des structures apparemment simples les
propri\'et\'es combinatoires qui les concernent ne sont pas faciles \`a \'etudier.
Le probl\`eme de l'\'enum\'eration selon l'aire, par exemple, a \'et\'e r\'esolu
il y a cinq ans seulement par Gouyou-Beauchamps et Viennot \cite{GB-Vi} et ensuite
d'une fa\c con plus simple, par Penaud \cite{Pe}. Plusieurs probl\`emes ont
\'et\'e r\'esolus en utilisant des bijections \cite{De-Vi} entre les objects
\'etudi\'es et les mots d'un langage alg\'ebrique et en appliquant la
m\'ethodologie DSV \cite{Sc} qui permet d'obtenir des fonctions
g\'en\'eratrices \`a partir d'une grammaire non ambig\" ue. Diff\'erentes
classes de polyominos ont \'et\'e \'enum\'er\'ees selon l'aire, ou le
p\'erim\`etre ou la largeur etc., ou une combinaison de ces param\`etres
\cite{Bo}.
\newline
Toutefois il y a encore plusieurs probl\`emes ouverts, par exemple
l'\'enum\'eration des polyominos dirig\'es selon le p\'erim\`etre et la
d\'etermination de leur hauteur moyenne. Il faut remarquer que dans ce cas
la hauteur d'un polyomino n'est pas le nombre de ses lignes mais le nombre de
droites d'\'equation $y=-x+k$ ($ k\in {\bf N}$) qui passent par les centres des
cellules du polyomino.
\begin{figure}[htb]
\begin{center}
\setlength{\unitlength}{0.0125in}%
\begin{picture}(200,240)(60,480)
\put( 60,540){\line( 1,-1){ 60}}
\put( 60,560){\line( 1,-1){ 80}}
\put( 60,600){\line( 1,-1){100}}
\put( 60,580){\line( 1,-1){ 80}}
\put( 60,620){\line( 1,-1){120}}
\put( 80,620){\line( 1,-1){100}}
\put( 80,640){\line( 1,-1){100}}
\put( 80,660){\line( 1,-1){100}}
\put(140,640){\line( 1,-1){ 80}}
\put(140,660){\line( 1,-1){100}}
\put(140,680){\line( 1,-1){100}}
\put(160,680){\line( 1,-1){100}}
\put(160,700){\line( 1,-1){100}}
\put(160,720){\line( 1,-1){100}}
\put(120,640){\line( 1,-1){ 80}}
\put(200,700){\line( 1,-1){ 60}}
\thicklines
\put( 80,500){\framebox(20,100){}}
\put(100,600){\line( 0, 1){ 40}}
\put(100,640){\line( 1, 0){ 20}}
\put(120,640){\line( 0,-1){140}}
\put(120,500){\line(-1, 0){ 20}}
\put(120,580){\line( 1, 0){ 20}}
\put(140,580){\line( 0,-1){ 60}}
\put(140,520){\line(-1, 0){ 20}}
\put(140,580){\line( 0, 1){ 40}}
\put(140,620){\line( 1, 0){ 20}}
\put(160,620){\line( 0,-1){100}}
\put(160,520){\line(-1, 0){ 20}}
\put(160,620){\line( 0, 1){ 40}}
\put(160,660){\line( 1, 0){ 20}}
\put(180,660){\line( 0,-1){ 80}}
\put(180,580){\line(-1, 0){ 20}}
\put(180,660){\line( 0, 1){ 40}}
\put(180,700){\line( 1, 0){ 20}}
\put(200,700){\line( 0,-1){120}}
\put(200,580){\line(-1, 0){ 20}}
\put(200,620){\line( 1, 0){ 20}}
\put(220,620){\line( 0,-1){ 40}}
\put(220,580){\line(-1, 0){ 20}}
\put(220,620){\line( 0, 1){ 60}}
\put(220,680){\line( 1, 0){ 20}}
\put(240,680){\line( 0,-1){ 80}}
\put(240,600){\line(-1, 0){ 20}}
\put( 80,520){\line( 1, 0){ 40}}
\put( 80,540){\line( 1, 0){ 80}}
\put( 80,560){\line( 1, 0){ 80}}
\put( 80,580){\line( 1, 0){ 40}}
\put(140,580){\line( 1, 0){ 20}}
\put(100,600){\line( 1, 0){ 20}}
\put(100,620){\line( 1, 0){ 20}}
\put(140,600){\line( 1, 0){ 80}}
\put(160,620){\line( 1, 0){ 40}}
\put(220,620){\line( 1, 0){ 20}}
\put(160,640){\line( 1, 0){ 40}}
\put(220,640){\line( 1, 0){ 20}}
\put(180,660){\line( 1, 0){ 20}}
\put(220,660){\line( 1, 0){ 20}}
\put(180,680){\line( 1, 0){ 20}}
\end{picture}
\caption{\label{figura2} Polyomino dirig\'e verticalement convexe d'aire 36 et
de hauteur 16}
\end{center}
\end{figure}
Cette d\'efinition s'accorde avec la d\'efinition standard de hauteur pour les
arbres binaires et d'autres structures utilis\'ees en l'informatique. Pour
ce qui concerne la hauteur moyenne des polyominos dirig\'es il y a une conjecture
formul\'ee par les physiciens \cite{De-Na-Va} qui a \'et\'e confirm\'ee par des
r\'esultats de simulation \cite{Ba-Pi-Sp}.\newline
Dans ce papier nous \'etudions la classe des polyominos dirig\'es verticalement
convexes et en utilisant des relations de r\'ecurrence, nous les \'enum\'erons
selon l'aire et la hauteur et nous d\'eterminons leur hauteur moyenne.
L'\'evaluation th\'eorique s'accorde parfaitement avec les r\'esultats
exp\'erimentaux que nous avons obtenus par la g\'en\'eration al\'eatoire qui
utilise l'algorithme pr\'esent\'e en \cite{Ba-Pi-Sp1}. Ce r\'esultat concerne une classe
particuli\`ere de polyominos mais, \`a la connaissance des auteurs, c'est le
premier r\'esultat exact sur la hauteur des polyominos dirig\'es.
%%%%%%%%%%%%%%
% Ricorrenza %
%%%%%%%%%%%%%%
\section{D\'enombrement des polyominos dirig\'es verticalement convexes selon
les param\`etres aire et hauteur}
\setcounter{equation}{0}
\begin{prop}
Le nombre $V_{n,k}$ de polyominos dirig\'es verticalement convexes d'aire $n$
et de hauteur $k$ satisfait la relation de r\'ecurrence suivante:
\begin{equation}
 V_{n,k}= V_{n-1,k-1}+\sum \limits^{k-1} \limits_{j=1} V_{n-k,j}+
 \sum \limits^{k-1} \limits_{j=1} V_{n-j,k-1}, \hspace{1.5cm} n>1, k>1.
\label{dvc}
\end{equation}
\label{prop1}
\end{prop}
\dimos
Soit $P$ un polyomino dirig\'e verticalement convexe d'aire $n$ et de
hauteur $k$. Si $P$ ne contient pas la cellule $L$ adjacente au c\^ot\'e droit
de la source $S$, en \'eliminant $S$ de $P$ on obtient un polyomino
$P^{'}$, d'aire $n-1$ et de hauteur $k-1$ (voir fig.~\ref{figura3}).
\begin{figure}[htb]
\begin{center}
\begin{picture}(7,7)(-1,0)
\put(0,0){\framebox(1,1)}
\put(-1,0){$S$}
\put(1,0){\dashbox{0.25}(1,1)}
\put(2.2,0){$L$}
\put(0,1){\framebox(6,6){$P^{'}$}}
\end{picture}
\caption{\label{figura3} Polyomino $P$}
\end{center}
\end{figure}
Si la cellule $L$ appartient \`a $P$, alors $P$ est obtenu attachant un polyomino
$P^{''}$ \`a une colonne $C$ de hauteur $j$, avec $1\leq j \leq k$, de fa\c con
que la source $S_{1}$ de $P^{''}$ soit adjacente \`a la premi\`ere cellule
de la colonne $C$.
Si $j=k$ alors le polyomino $P^{''}$ est d'aire $n-k$ et de hauteur $i$, avec
$1\leq i\leq k-1$ (voir fig.~\ref{figura4}).
\begin{figure}[htb]
\begin{center}
\begin{picture}(6,8)(-1,0)
\put(0,0){\framebox(1,8)}
\put(0.3,3.8){$k$}
\put(0.5,4.5){\vector(0,1){3.5}}
\put(0.5,3.5){\vector(0,-1){3.5}}
\put(-1,3){$C$}
\put(1,0){\framebox(1,1)}
\put(2.2,0.2){$S_{1}$}
\put(1,0){\framebox(5,5){$P^{''}$}}
\end{picture}
\caption{\label{figura4} Polyomino $P$ ayant la premi\`ere colonne de
hauteur $k$}
\end{center}
\end{figure}
Si $1\leq j \leq k-1$, le polyomino $P^{''}$ est d'aire $n-j$ et de hauteur
$k-1$ (voir fig.~\ref{figura5}).
\begin{figure}[htb]
\begin{center}
\begin{picture}(8,7)(-1,0)
\put(0,0){\framebox(1,4)}
\put(0.4,1.8){$j$}
\put(0.5,2.5){\vector(0,1){1.5}}
\put(0.5,1.5){\vector(0,-1){1.5}}
\put(-1,2){$C$}
\put(1,0){\framebox(1,1)}
\put(2.2,0.2){$S_{1}$}
\put(1,0){\framebox(7,7){$P^{''}$}}
\end{picture}
\caption{\label{figura5} Polyomino $P$ ayant la premi\`ere colonne de hauteur
$j<k$}
\end{center}
\end{figure}
Ainsi on obtient:
\[ V_{n,k}= V_{n-1,k-1}+\sum \limits^{k-1} \limits_{j=1} V_{n-k,j}+
 \sum \limits^{k-1} \limits_{j=1} V_{n-j,k-1}. \]
\finedimos
\newline
On a $V_{n,k}=0$ pour $n\leq 0$ $k\leq 0$, et $V_{1,1}=1$. Donc l'\'equation
(\ref{dvc}) est modifi\'ee de la fa\c con suivante:
\[ V_{n,k}= V_{n-1,k-1}+\sum \limits^{k-1} \limits_{j=1} V_{n-k,j}+
 \sum \limits^{k-1} \limits_{j=1} V_{n-j,k-1}+[n=1, k=1]. \]
En posant:
\[  V_{k}(t)= \sum \limits_{n} V_{n,k} t^n, \]
de la r\'ecurrence (\ref{dvc}) on obtient:
\begin{equation}
 V_{k}(t)= t\: V_{k-1}(t)+t^k\: \sum \limits^{k-1} \limits_{j=1} V_{j}(t)+
 \frac {t-t^k}{1-t}\: V_{k-1}(t)+[k=1]\:t.
\label{dvc1}
\end{equation}
Si on d\'efinit:
\begin{equation}
  V(t,z)= \sum \limits_{n,k} V_{n,k}\: t^n z^k,
\label{dvc2}
\end{equation}
on a:
\[  V(t,z)= \sum \limits_{k} V_{k}(t)\: z^k, \]
et donc d'apr\`es (\ref{dvc1}):
\begin{teor}
La fonction g\'en\'eratrice $V(t,z)$ des polyominos dirig\'es verticalement
convexes compt\'es suivant l'aire et la hauteur par $t$ et $z$ respectivement,
satisfait l'\'equation \mbox{suivante}:
\begin{equation}
 V(t,z)= \frac {zt(1-t)}{1-t-2zt+zt^2}+\frac{zt^2 (z-1)}{(1-t-2zt+zt^2)(1-zt)}
 V(t,tz).
\label{dvc3}
\end{equation}
\end{teor}
{\bf Remarque.}  En posant $z=1$ on retrouve la fonction g\'en\'eratrice $F(t)$
des polyominos dirig\'es verticalement convexes compt\'es selon l'aire:
\[ F(t)=V(t,1)=\frac {t(1-t)}{1-3t+t^2} \]
(voir \cite{Ba-Pi-Ro-Sp,De-Du}).
\section{Hauteur moyenne des polyominos dirig\'es verticalement convexes}
\setcounter{equation}{0}
Pour obtenir la hauteur moyenne on d\'etermine une estimation de la somme des
hauteurs des polyominos dirig\'es verticalement convexes d'aire fix\'ee.
\begin{prop}
Soit $S_{n}$ la somme des hauteurs des polyominos dirig\'es verticalement
convexes d'aire $n$. La fonction g\'en\'eratrice $S(t)=\sum \limits_{n}
S_{n}\: t^n$ est:
\begin{equation}
 S(t)= \frac{t(1-t)^2}{(1-3t+t^2)^2}+\frac{t^2}{(1-t)(1-3t+t^2)}\: V(t,t).
\label{dvc4}
\end{equation}
\label{prop2}
\end{prop}
\dimos
Puisque $V_{n,k}$ est le nombre des polyominos dirig\'es d'aire $n$ et de
hauteur $k$ on a:
\[ S_{n}=\sum \limits_{k} k\: V_{n,k}, \]
et donc d'apr\`es (\ref{dvc2}):
\[ S(t)=\frac {\partial}{\partial z} V(t,z)_{\bigm\vert z=1}. \]
En utilisant l'\'equation (\ref{dvc3}) on a:
\[ (1-t-2zt+zt^2)\: V(t,z)= zt(1-t)+\frac{zt^2 (z-1)}{1-zt} V(t,tz), \]
d'o\`u en d\'erivant par rapport \`a $z$ et en posant $z=1$, on d\'eduit:
\[ S(t)= \frac{t(1-t)^2}{(1-3t+t^2)^2}+\frac{t^2}{(1-t)(1-3t+t^2)}\: V(t,t).\]
\finedimos
\newline
Maintenant nous calculons une estimation de la somme des hauteurs des polyominos
dirig\'es verticalement convexes d'aire $n$, c'est-\`a-dire la valeur $S_{n}$.
De la proposition~\ref{prop2} on a:
\[ S(t)= f(t)+g(t)\: V(t,t), \]
o\`u,
\[ f(t)=\frac{t(1-t)^2}{(1-3t+t^2)^2}, \hspace{1cm}
g(t)=\frac{t^2}{(1-t)(1-3t+t^2)}, \hspace{1cm} V(t,t)= \sum \limits_{k} V_{k}(t)
\: t^k. \]
La fonction $f(t)$ a deux p\^oles du second ordre, un dans $t_{0}=\frac{1}
{\phi^2}$ et l'autre dans $t_{1}=\frac{1}{\hat{\phi^2}}$, o\`u $\phi=\frac
{1+\sqrt{5}}{2}$ et $\hat {\phi}=1-\phi$. Le point singulier dominant de
la $f(t)$ est $t_{0}$ et donc:
\[ f_{n}=[t^n]\:f(t)\approx (a_{0}\:n+a_{1})\:\phi^{2n},\]
o\`u
\begin{eqnarray}
 a_{0} & = & \lim_{t \rightarrow \frac{1}{\phi^2}} (1-\phi^2\:t)^2 \:f(t),
 \label{dvc7} \\
 a_{1} & = & -\frac{1}{\phi^2}\: \lim_{t \rightarrow \frac{1}{\phi^2}}
 \frac {d}{dt}\left( (1-\phi^2\:t)^2 \:f(t) \right).
\label{dvc8}
\end{eqnarray}
Mais $f(t)=\frac{t(1-t)^2}{(1-\phi^2\:t)^2\:(1-\hat {\phi}^2\:t)^2}$
et $\hat {\phi}^2=\frac {1}{\phi^2}$, et ainsi d'apr\`es (\ref{dvc7}):
\[ a_{0}=\frac {\frac {1}{\phi^2}\:(1-\frac {1}{\phi^2})^2}
{(1-\frac {1}{\phi^4})^2}=\frac {1}{5}. \]
Puisque:
\[ \frac {d}{dt}\left( (1-\phi^2\:t)^2 \:f(t) \right)=
\frac {(1-4t+3t^2)(1-\hat {\phi}^2\:t)+2 \hat {\phi}^2\:t(1-t)^2}
{(1-\hat {\phi}^2\:t)^3}, \]
d'apr\`es (\ref{dvc8}):
\[ a_{1}=-\frac{5-2\sqrt{5}}{25}, \]
et par cons\'equent:
\[ f_{n}=[t^n]\:f(t)\approx \frac{1}{5}(n-\frac{5-2\sqrt{5}}{5})\:\phi^{2n}. \]
Maintenant on consid\`ere le deuxi\`eme terme de $S(t)$, c'est-\`a-dire
$g(t)\:V(t,t)=\sum \limits_{n} c_{n}\:t^n$.
En utilisant la r\'ecurrence (\ref{dvc1}) on obtient:
\begin{equation}
 V_{k+1}(t)= \frac{2t-t^2}{1-t}\: V_{k}(t)+ \frac{t^{k+2}}{1-t}\: V_{k}(t)+
t^{k+1}\: \sum \limits^{k-1} \limits_{j=1} V_{j}(t).
\label{dvc9}
\end{equation}
En posant $\delta_{k}=V_{k}(\frac{1}{2})$ on a:
\[ \delta_{k+1}=\frac{3}{2}\:\delta_{k}-\frac{1}{2^{k+1}}\:\delta_{k}+
\frac{1}{2^{k+1}}\:\sum \limits^{k-1} \limits_{j=1} \delta_{j}, \]
d'o\`u
\[ \frac{\delta_{k+1}}{\delta{k}}=\frac{3}{2}-\frac{1}{2^{k+1}}+
\frac{1}{2^{k+1}}\:\frac{1}{\delta_{k}}\:\sum \limits^{k-1} \limits_{j=1}
\delta_{j}. \]
Mais:
\[ V(\frac{1}{2},\frac{1}{2})=\sum \limits_{k} V_{k}(\frac{1}{2})\:\frac{1}{2^k}
=\sum \limits_{k} \frac{\delta_{k}}{2^k}, \]
donc
\[ \lim_{k \rightarrow +\infty} \frac{\frac{\delta_{k+1}}{2^{k+1}}}
{\frac{\delta_{k}}{2^{k}}}=\frac{3}{4}<1, \]
et ainsi d'apr\`es le crit\`ere de D'Alembert la s\'erie $V(t,t)$ converge dans
$t=\frac{1}{2}$. Par cons\'equent, d'apr\`es le th\'eor\`eme d'Abel, le rayon
de convergence $\rho$ de $V(t,t)$ est tel que $\rho \geq \frac{1}{2}$.\newline
La fonction $g(t)$ a rayon de convergence $\rho^{'}=\frac{1}{\phi^2}$, et donc:
\begin{equation}
 \rho>\rho^{'}>0 .
\label{dvc10}
\end{equation}
Le point singulier dominant de $g(t)$ est $t_{0}=\frac{1}{\phi^2}$ et ainsi:
\[ g_{n}=[t^n]\:g(t)\approx b_{0}\:\phi^{2n},\]
o\`u
\[b_{0} = \lim_{t \rightarrow \frac{1}{\phi^2}} (1-\phi^2\:t) \:g(t)=
 \frac{5-\sqrt{5}}{10}. \]
Donc:
\begin{equation}
 \lim_{n \rightarrow +\infty} \frac{g_{n+1}}{g_{n}}=\frac{1}{\phi^2}.
\label{dvc11}
\end{equation}
Maintenant nous prouvons que $V(\frac{1}{\phi^2},\frac{1}{\phi^2})\neq 0$.
Puisque $V_{k}(t)= \sum \limits_{n\geq k} V_{n,k}\: t^n$, et $V_{n,k}\geq 0$ on
a:
\[ t^k\:V_{k}(t) > V_{k}(t^2), \hspace{1.5cm}  t<1,\]
et:
\[  V(t,t) > \sum \limits_{k} V_{k}(t^2),\hspace{1.5cm} t<1.\]
Mais:
\[ V(t^2,1)=\sum \limits_{k} V_{k}(t^2)=\frac {t^2(1-t^2)}{1-3t^2+t^4},\]
donc on obtient:
\begin{equation}
 V(\frac{1}{\phi^2},\frac{1}{\phi^2}) > V(\frac{1}{\phi^4},1)>0.
\label{dvc12}
\end{equation}
En utilisant les conditions (\ref{dvc10}), (\ref{dvc11}) et (\ref{dvc12})
on peut appliquer le th\'eor\`eme 2 de Bender \cite{Be}, d'o\`u on d\'eduit
que le coefficient $c_{n}$ de $t^n$ dans $g(t)\:V(t,t)$ est tel que:
\[ c_{n}\approx g_{n}\:V(\frac{1}{\phi^2},\frac{1}{\phi^2}), \]
et ainsi:
\[  c_{n}\approx \frac{5-\sqrt{5}}{10}\:V(\frac{1}{\phi^2},\frac{1}{\phi^2})
  \:\phi^{2n}. \]
En posant $\alpha_{k}=V_{k}(\frac{1}{\phi^2})$ on a:
\[ V(\frac{1}{\phi^2},\frac{1}{\phi^2})=\sum \limits^{\infty}\limits_{k=1}
 \frac{\alpha_{k}}{\phi^{2k}}.\]
D'apr\`es (\ref{dvc9}):
\begin{equation}
 \alpha_{k+1}=\left(1-\frac{1}{\phi^{2k+3}}\right)\:\alpha_{k}+
\frac{1}{\phi^{2k+2}}\: \sum \limits^{k-1} \limits_{j=1} \alpha_{j}.
\label{ric}
\end{equation}
En utilisant cette r\'ecurrence, on d\'etermine exp\'erimentalement que la
valeur de la somme est:
\[ V(\frac{1}{\phi^2},\frac{1}{\phi^2})\approx 0.229265982292, \]
et donc:
\[ c_{n}\approx 0.6336757901\: \phi^{2n}.\]
Puisque $S_{n}=f_{n}+c_{n}$ d'apr\`es ce qui pr\'ec\`ede on d\'eduit:
\begin{prop}
La somme $S_{n}$ des hauteurs des polyominos dirig\'es verticalement convexes
d'aire $n$ est:
\begin{equation}
S_{n}\approx \frac{n}{5}\: {\phi^{2n}}\left(1+\frac{1.21126498605}{n}\right) .
\label{som}
\end{equation}
\end{prop}
Le nombre $V_{n}$ de polyominos dirig\'es verticalement convexes d'aire $n$
est le nombre de Fibonacci $F_{2n-1}$ \cite{Ba-Pi-Ro-Sp,De-Du}, donc:
\[ V_{n}=F_{2n-1}\approx \frac {1}{\sqrt{5}}\: {\phi^{2n-1}}, \]
et par cons\'equent, de la proposition (\ref{som}) on d\'eduit:
\begin{teor}
La hauteur moyenne des polyominos dirig\'es verticalement convexes d'aire
$n$ est:
\begin{equation}
 \xi_{\parallel}(n)\approx \frac{\phi}{\sqrt{5}}\:n+0.87647957778 .
\end{equation}
\end{teor}
{\bf Remarque.} \newline
On peut d\'eterminer le rayon de convergence $\rho^{''}$ de
$V(t,t)=\sum \limits_{k} V_{k}(t)\:t^k= \sum \limits_{i} v_{i}\:t^i$.
Posons $\beta_{k}=V_{k}(\alpha)$, avec $\alpha \in \Re$. Alors d'apr\`es
(\ref{dvc9}):
\begin{equation}
 \beta_{k+1}=\frac{2\alpha-\alpha^{2}}{1-\alpha}\:\beta_{k}-\frac{\alpha^{k+2}}
{1-\alpha}\:\beta_{k}+\alpha^{k+1}\:\sum \limits^{k-1} \limits_{j=1}
\beta_{j},
\label{dvc13}
\end{equation}
et donc on a:
\[ \lim_{k \rightarrow +\infty} \frac{\beta_{k+1}}{\beta_{k}}=
\frac{2\alpha-\alpha^2}{1-\alpha}.\]
On d\'eduit, d'apr\`es le crit\`ere de D'Alembert, que la s\'erie
$V(\alpha,\alpha)=\sum \limits_{k} \beta_{k}\:\alpha^k$ converge si
\[\frac{2\alpha^2-\alpha^3}{1-\alpha}<1.\]
Donc la s\'erie $V(t,t)$ a rayon de convergence $\rho^{''}=\lambda$ o\`u:
\[ \lambda={2 \over 3}-{{\sqrt{7}} \over 3}\:\cos\left({1 \over 3}
\arctan\left(3\sqrt{3}\right)\right)
+\sqrt{7 \over 3}\:\sin\left({1 \over 3} \arctan\left(3\sqrt{3}\right)\right)
\approx 0.554958132088.\]
Par cons\'equent:
\begin{prop}
Le nombre $v_{i}$ de polyominos dirig\'es verticalement convexes d'aire $n$ et
de hauteur $k$ tels que $i=n+k$ est:
\[ v_{i}\:=\:O\left({1 \over \lambda^i}\right) .\]
\end{prop}
\section{D\'enombrement des polyominos dirig\'es verticalement convexes selon
la hauteur}
\setcounter{equation}{0}
\begin{prop}
Le nombre $W_{k}$ de polyominos dirig\'es verticalement convexes de hauteur
$k$ satisfait la relation de r\'ecurrence suivante:
\begin{equation}
W_{k+2}-(k+4)\:W_{k+1}+(k+1)\:W_{k}=0,
\label{a1}
\end{equation}
o\`u $W_{0}=1$ et $W_{1}=1$.
\end{prop}
\dimos
Le nombre $W_{k}$ est tel que:
\[ W_{k}= \sum \limits^{\infty} \limits_{n=1} V_{n,k}, \]
donc
\[ W_{k}=V_{k}(1).\]
En utilisant la relation (\ref{dvc1}) on d\'eduit:
\[ V_{k+1}(t)= t\: V_{k}(t)+ \sum \limits^{k} \limits_{j=1} t^j\: V_{k}(t)+
t^{k+1}\: \sum \limits^{k} \limits_{j=1} V_{j}(t)+ [k=0]\:t, \]
ainsi on a:
\[ W_{k+1}= (k+1)\: W_{k}+\sum \limits^{k} \limits_{j=1} W_{j}, \]
et par cons\'equent:
\[ W_{k+2}=(k+4)\:W_{k+1}-(k+1)\:W_{k} .\]
\finedimos
La fonction $X_{k}=k!\:k$ est une solution de l'\'equation (\ref{a1}).
En utilisant la transformation $W_{k}=X_{k}\:Y_{k}$ dans l'\'equation (\ref{a1})
on a:
\[ (k+2)^2\:(Y_{k+2}-Y_{k+1})-k\:(Y_{k+1}-Y_{k})=0. \]
En posant $Z_{k}=Y_{k+1}-Y_{k}$, on obtient:
\[ Z_{k+1}=\frac {k}{(k+2)^2} Z_{k}, \]
d'o\`u
\[ Z_{k}=\frac {C_{1}}{k\:(k+1)\:(k+1)!}, \]
et ainsi:
\[Y_{k}=\sum \limits^{k-1}\limits_{j=1}\frac {C_{1}}{j\:(j+1)\:(j+1)!}+C_{2} ,\]
o\`u $C_{1}$ et $C_{2}$ sont deux constantes.
Mais $W_{1}=1$ et $W_{2}=3$, et d'apr\`es ce qui pr\'ec\`ede, on a le
r\'esultat suivant:
\begin{teor}
Le nombre $W_{k}$ de polyominos dirig\'es verticalement convexes ayant la
hauteur $k$ est:
\begin{equation}
 W_{k}=k!\:k\:\left( 1-\sum \limits^{k-1}\limits_{j=1}\frac {1}{j\:(j+1)\:(j+1)!}
 \right) .
\end{equation}
\end{teor}
{\bf Remarque.}\\
\[ \sum \limits^{\infty}\limits_{j=0}\frac {1}{(j+1)\:(j+1)!}=\int_{0}^{1}
\frac {e^t-1}{t}\: dt ,\]
\[ \sum \limits^{\infty}\limits_{j=1}\frac {1}{j\:(j+1)!}=\int_{0}^{1}
\frac {e^t-t-1}{t^2}\: dt ,\]
\[ \sum \limits^{\infty}\limits_{j=1}\frac {1}{j\:(j+1)\:(j+1)!}=\int_{0}^{1}
\frac {te^t-t-1}{t^2}\: dt\:=\:3-e,\]
donc on a:
\[ W_{k}\approx (e-2)\:k!\:k .\]
Observons que pour $k=6$ en approchant
$1-\sum \limits^{k-1}\limits_{j=1}\frac {1}{j\:(j+1)\:(j+1)!}$ avec $e-2$
on commet une erreur de l'ordre de $10^{-6}$.
%%%%%%%%%%%%%%
%Bibliografia%
%%%%%%%%%%%%%%
\begin{thebibliography}{99}
\bibitem{Ba-Pi-Ro-Sp}
E. Barcucci, R. Pinzani, E. Rodella et R. Sprugnoli, A Characterization of
Binary Search Networks, Fundamentals of Computation Theory, ed. Budach,
{\it Lecture Notes in Computer Science}, 529 (1991) 126-135.
\bibitem{Ba-Pi-Sp}
E. Barcucci, R. Pinzani et R. Sprugnoli, G\'en\'eration al\'eatoire des animaux
dirig\'es, {\it Atelier de Combinatoire franco-qu\'ebecois}, eds. J.~Labelle et
J.~G.~Penaud, Publications du LACIM, $n^{\circ}$ 10, Universit\'e Bordeaux 1,
(1991) 17-25.
\bibitem{Ba-Pi-Sp1}
E. Barcucci, R. Pinzani et R. Sprugnoli, Directed Column-Convex Polyominoes
by Recurrence Relations, TAPSOFT'93, eds. M. C. Gaudel, J. P. Jouannaud,
{\it Lecture Notes in Computer Science 668} (1993) 282-298.
\bibitem{Be}
E. A. Bender, Asymptotic methods in enumeration, {\it SIAM Rev.}, 16 (1974)
485-514.
\bibitem{Bo}
M. Bousquet-M\'elou, q-\'Enum\'eration de polyominos convexes, {\it Publications
du LACIM, $n^{\circ}$ 9}, Universit\'e du Qu\'ebec  \`a Montreal,
(Th\`ese de doctorat, Universit\'e Bordeaux 1, (1991)).
\bibitem{De}
M. Delest, Polyominoes and animals: Some recent results, Proc.
Math/Chem/Comp 90, Dubrovnik, Croatie, {\it J. of Computer and Chemistry},
8 (1991) 3-18.
\bibitem{De-Du}
M. Delest et S. Dulucq, Enumeration of Directed Column-Convex Animals with
given Perimeter and Area, {\it rapport LaBRI $n^{\circ}$ 86-15}, Universit\'e
Bordeaux 1, (1987).
\bibitem{De-Vi}
M. Delest et X. G. Viennot, Algebraic languages and polyominoes enumeration,
{\it Theor. Comp. Sci.}, 34 (1984) 169-206.
\bibitem{De-Na-Va}
B. Derrida, J. P. Nadal et J. Vannimenus, Directed lattice animals in 2
dimensions: Numerical and exact results, {\it J. Physique} 43, (1982) 1561.
\bibitem{GB-Vi}
D. Gouyou-Beauchamps et X. G. Viennot, Equivalence of the two-dimensional
directed animal problem to a one-dimensional path problem, {\it Advances in
Applied Mathematics} 9, (1988) 334-357.
\bibitem{Pe}
J. G. Penaud, Une nouvelle bijection pour les animaux dirig\'es, {\it Act\'es
du 22\`eme S\'eminaire Lotharingien de combinatoire}, Publi. IRMA, Universit\'e
Strasbourg I (1989).
\bibitem{Sc}
M. P. Sch\"utzenberger, Context-free langages and pushdown automata, {\it
Information and Control} 6, (1963) 246-264.
\bibitem{Vi}
X. G. Viennot, Probl\`emes combinatoires pos\'es par la physique statistique,
{\it S\'eminaire Bourbaki $n^{\circ}$ 626, 36\`eme ann\'ee}, in Ast\'erisque
$n^{\circ}$ 121-122, (1985) 225-246, Soc. Math. France.
\bibitem{Vi1}
X. G. Viennot, A Survey of Polyomino enumeration, {\it Proc. S\'eries formelles
et combinatoire alg\'ebrique}, Montr\'eal, Juin 1992, eds. P.~Leroux et
C.~Reutenauer, Publications du LACIM, $n^{\circ}$ 11, Universit\'e du Qu\'ebec
\`a Montr\'eal (1992).
\end{thebibliography}
\end{document}