L’arborification de Matula

David W. Matula, professeur émérite à la Southern Methodist University, a découvert en 1968 une remarquable bijection entre les entiers naturels (non nuls) et les arbres enracinés finis. Plusieurs auteurs (D. F. Göbel, P. Cappello, J. Sousselier,…) l’ont redécouverte dans les dernières décennies du siècle dernier. La représentation des nombres ainsi obtenue est fascinante : elle est indépendante de tout choix de base, décimale, binaire ou autre, et le produit s’effectue simplement en fusionnant les racines des arbres correspondant à chaque facteur. La somme en revanche est impénétrable, rendant la représentation de Matula impropre à tout calcul faisant intervenir les deux opérations de base de l’arithmétique. 
 
Décrivons la bijection (notée A, son inverse étant noté N) en détail, en considérant les forêts plutôt que les arbres. Une forêt est une collection (éventuellement vide) d’arbres enracinés, avec répétitions possibles. Les forêts, qui forment un monoïde commutatif via la réunion disjointe, sont en bijection avec les arbres via l’opération B+, qui greffe tous les arbres d’une forêt sur une racine commune. La forêt vide est associée au nombre 1, soit A(1)=ø et N(ø)=1. Tout arbre s’écrit de manière unique T=B+(F) où F=T_1…T_n est une forêt dont les T_j sont les branches issues de la racine. On choisit alors pour N(T) le nombre premier de rang N(F), où N(F) est le produit des N(T_j). Cette procédure définit bien la correspondance N par récurrence sur le nombre de sommets de l’arbre ou de la forêt. C’est un morphisme bijectif de monoïdes commutatifs. Pour se familiariser avec, voir le site de Zh. Chen qui fournit A(n) – plus exactement B+ (A(n)) avec nos conventions – pour tout n inférieur à un milliard.
 
Simple curiosité ? Peut-être pas. Je reviens sur cette bijection dans un article sur HAL et sur arXiv. Lorsqu’on coupe une branche issue de la racine d’un arbre T, on obtient une forêt F constituée de deux arbres : la branche coupée et le tronc restant. Il se trouve qu’on a toujours N(F) <N(T) sauf dans les deux cas N(T)=3 et N(T)=5, qui donnent respectivement N(F)=4 et N(F)=6. Lorsqu’on fusionne les racines de deux arbres T et T’, on obtient un arbre U, et on a toujours N(U)<N(T)N(T’) sauf si N(T)=N(T’)=7, ou encore si N(T)=5 et N(T’)=7 (ou vice-versa). Ces deux exceptions fournissent N(U)=53 et N(U)=37 respectivement, à comparer avec 49 et 35. Hormis ces exceptions, ces coupes et fusions associent donc à tout nombre n un nombre n’ plus petit que lui, ayant un facteur de plus ou de moins que lui. On peut espérer que cette propriété s’avère très utile pour l’étude des fonctions sommatoires des fonctions de Liouville ou de Möbius.