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)