Animaux, empilements de dominos, �quations fonctionnelles

Ce travail s'inscrit dans la grande traque des animaux sur r�seau 2D : comment fabriquer des classes d'animaux, aussi grandes que possible, qui aient suffisamment de structure pour �tre �num�rables exactement ? Rappelons qu'un animal est un ensemble fini et connexe de sommets d'un r�seau (le r�seau carr� par exemple), d�fini � translation pr�s, et qu'on ne conna�t pas le comportement asymptotique du nombre d'animaux � n sommets.

Notre point de d�part est la correspondance, due � Viennot, entre animaux dirig�s et pyramides de dominos. Nous d�finissons une classe (bien) plus grande d'animaux, en bijection avec certains empilements de dominos, dits connexes, et nous nous attachons � l'�num�ration de ceux-ci.

Cette �num�ration passe par la r�solution d'une �quation fonctionnelle, dont une variante r�git la s�rie g�n�ratrice des animaux dirig�s. Mais la diff�rence entre les deux mod�les est de taille : les animaux dirig�s ont une s�rie g�n�ratrice alg�brique, et une constante de croissance �gale � 3, tandis que notre nouvelle classe d'animaux a une s�rie g�n�ratrice non-holonome, et une constante de croissance �gale � 3.58...

Autant dire que nous avons fait, d'un seul coup d'un seul, la moiti� du chemin jusqu'au Graal animalier : leur constante de croissance est estim�e � 4.06... :)

(travail en commun avec A. Rechnitzer)