We give a purely combinatorial proof of a formula derived by Riordan from a result of Touchard. This proof involves a sequence of bijections starting with involutions, passing through words, trees .... and ending with polynominoes satisfying the required property.
Resum/~
Une preuve bijective d'une formule tir6e par Riordan d'un papier de Touchard est pr6sent6e. Cette preuve proc6de par un encha~nement de bijections allant des involutions aux polyominos, en passant par les histoires de fichiers, les mots, les arbres fi deux types de sommets, les couples de suites d'entiers jusqu'fi l'object final off la propri6t6 devient 6vidente.
1. La formule de Touchard-Riordan
I1 est classique de repr6senter une involution sans point fixe sur les entiers de I/t 2n (ensemble que l'on note [1..2n]) par un diagramme compos6 de n cordes joignant deux 5. deux 2n points distincts r6partis sur un cercle. Le lecteur trouvera dans un autre article de Dulucq et l'auteur un apergu des relations entre cordes, arbres et permutations . La Fig. ci-dessous montre la configuration de cordes associbe 5. l'involution c~ =(1,4)(2, 6)(3, 5)(7, 8).
Les questions qui viennent alors naturellement sont celles relatives aux points de croisement des cordes, c'est-5.-dire, en termes d'involution sur [1,2n], aux quadruplets (i, j, k, I) tels que 1 ~< i < j < k < l-%< 2n et que (i, k) et (j, l) soient des cycles de l'involution.
--Quel est le nombre de configurations de cordes qui ne se coupent pas? --Quel est le nombre de configurations ayant un nombre de croisements donne?