Proprités combinatoires de l’alg`ebre deFa´ a di Bruno non commutative

Propriétés combinatoires de l’algèbre deFa´ a di Bruno non commutative

L’algèbre de Hopf HNC des difféomorphismes formels non commutatifs 

La formule d’inversion de Lagrange non commutative Comme on l’a vu dans le chapitre précédent, la formule d’inversion de Lagrange classique pour l’inversion des séries formelles au sens de la composition peut être interprétée en termes de fonctions symétriques classiques (pour plus de détails, on pourra consulter. Section 2.4 et [23]). De même, pour beaucoup d’analogues non commutatifs de l’inversion de Lagrange (voir [11], [29] et [2]), Novelli et Thibon donnent dans [28] des interprétations en terme de fonctions symétriques non commutatives. Brouder, Frabetti et Krattenthaler obtiennent dans [2] une forme de l’inversion de Lagrange non commutative qui est une formule explicite pour l’antipode de l’algèbre de Hopf HNC des difféomorphismes formels non commutatifs, également appelée algèbre de Fa´a di Bruno non commutative. Les éléments de HNC peuvent être identifiés à des fonctions symétriques non commutatives par la correspondance an (de [2]) = Sn (de Sym) qui identifie HNC à Sym en tant qu’algèbre associative. Le coproduit ∆ de HNC prend alors la forme ∆Sn(A) = Xn k=0 Sk(A) ⊗ Sn−k((k + 1)A). (5–350) On désigne par s : F 7→ F ⋆ l’antipode de HNC. On définit les coefficients αI , βI et δI par S ⋆ n = X In βIRI = X In αIS I = X In δIΛ I . (5–351) 69 Propriés combinatoires de l’algèbre deFa´ a di Bruno non commutative 5.1.1. La formule d’inversion de Lagrange non commutative 70 De même, on définit les coefficients ˆαI , βˆ I et ˆδI par S ⋆ n (−A) = X In βˆ IRI = X In αˆIS I = X In ˆδIΛ I . (5–352) Nous aurons également besoin de la définition suivante. Définition 5.1.1. Pour tout n, on appelle An l’ensemble des suites finies a = (a1, a2, . . .) de longueur n o`u les ai sont des entiers positifs tels que    a1 + . . . + . . . + an = n − 1 a2 + . . . + an ≤ n − 2 . . . . . . an ≤ 0 (5–353) En retranchant chaque ligne à la première, on peut réécrire le système (5–353) sous la forme    an + . . . + . . . + a1 = n − 1 an−1 + . . . + a1 ≥ n − 1 . . . . . . a1 ≥ 1 (5–354) La valeur du coefficient αI est donné dans [2] par αI = (−1)l(I) X a∈Al(I) l( Y I)−1 k=1  ik + 1 ak  . (5–355) La raison pour laquelle on a donné deux formes équivalentes du système d’inéquations de la définition 5.1.1 est que l’on utilisera plutˆot (5–353) dans ce document, bien que ce soit (5–354) qui soit utilisé dans [28]. Gessel [11] et Pak-Postnikov-Retakh [29] donnent une autre version de la formule d’inversion de Lagrange non commutative. Novelli et Thibon montrent dans [28] que cette formule peut aussi être interprétée en termes de fonctions symétriques non commutatives, et qu’elle est de plus équivalente à la formule de Brouder-Frabetti-Krattenthaler. Plus précisément, la formule de Gessel et Pak-Postnikov-Retakh correspond à l’évaluation du coefficient ˆαI , et peut s’écrire αˆI = X a∈Al(I) l( Y I)−1 k=1  ik ak  . 

Interprétation combinatoire en termes d’arbres

Novelli et Thibon donnent dans [28] l’interprétation combinatoire suivante pour le coefficient αI . On a ∆(σ1(A)) = X n≥0 Xn k=0 Sk(A) ⊗ Sn−k((k + 1)A) = X k≥0 Sk(A) ⊗ σ1((k + 1)A) = X k≥0 Sk ⊗ σ1(A) k+1 , (5–357) c’est-à-dire 1 = X k≥0 Sk(S ⋆ 0 + S ⋆ 1 + S ⋆ 2 + . . .) k+1 . (5–358) On peut réécrire cette formule sous la forme σ ⋆ 1 −1 = S0 + S1σ ⋆ 1 + S2σ ⋆ 1 2 + . . . (5–359) En posant c = S −1 0 et dn = −S −1 0 Sn, on obtient σ ⋆ 1 = c + d1σ ⋆ 1 2 + d2σ ⋆ 1 3 + . . . (5–360) Cette formule permet de calculer récursivement S ⋆ 0 , S ⋆ 1 , … S ⋆ 0 = c, S⋆ 1 = d1cc, S⋆ 2 = d1cd1cc + d1d1ccc + d2ccc, . . . (5–361) Chaque di peut être interprété comme le symbole d’une opération (i + 1)-aire en notation polonaise de la fa¸con suivante. S ⋆ 0 = c, S⋆ 1 = d1(c, c), S⋆ 2 = d1(c, d1(c, c)) + (d1(d1(c, c), c) + d2(c, c, c), . . . . (5–362) Ainsi, σ ⋆ 1 correspond à la somme d’arbres ordonnés de la figure 5.1. f = + + + + + . . . c c c c c c c c c c c c 2 2 2 2 2 3 Figure 5.1 – Les termes S ⋆ 0 , S ⋆ 1 et S ⋆ 2 exprimés comme une somme d’arbres ordonnés. Cette interprétation permet de voir S ⋆ n comme la somme de tous les codes polonais des arbres ordonnés à n + 1 feuilles sans sommet d’arité 1. Etant donné un arbre T vérifiant ces conditions, on définit son squelette comme étant l’arbre obtenu à partir de T en supprimant ses feuilles et en étiquetant ses sommets internes avec leurs arités.

Fonctions de parking croissantes 

Figure 5.2 – Un arbre et son squelette. Etant donné un squelette S, on définit sa 1-composition I1(S) comme étant la suite (j1 − 1, j2 − 1, . . .), o`u les jk sont les étiquettes des sommets donnés dans l’ordre préfixe. Novelli and Thibon montrent que le nombre d’arbres de squelette S est Y p k=1  ik + 1 ak  , (5–363) o`u (i1, . . . , ip) = I1(S) et o`u ak est l’arité du k-ième sommet de S dans l’ordre préfixe. Soit I = (i1, . . . , ip) une composition de n. La valeur absolue |αI | = (−1)l(I)αI du coefficient αI de S I dans S ⋆ n est alors égale au nombre d’arbres ordonnés à n + 1 feuilles dont la suite des arités non nulles moins un dans l’ordre préfixe est I. C’est de cette interprétation combinatoire que Novelli et Thibon déduisent la formule (5–355), dans laquelle l’ensemble des (a1, . . . , ap−1) correspond à l’ensemble des squelettes de ces arbres. 

Fonctions de parking croissantes

Une fonction de parking croissante de taille n est une suite croissante F = (f1 . . . fn), fi ≤ i de n entiers positifs majorée terme à terme par (123 . . . n). Le terme de fonction subexcédente est également employé pour désigner une telle suite d’entiers. On notera NDP F(n) l’ensemble des fonctions de parking croissantes de taille n. Pour toute composition I  n, on notera p(I) la fonction de parking F de taille n telle que mk(F) = ik pour tout k. Par exemple, on aura p(321) = (111223). Pour toute fonction de parking croissante F de taille n, on notera ev(F) la composition obtenue en enlevant toutes les parts égales à zéro dans (m1(F), m2(F), . . .), et on dira que cette composition est l’évaluation de F. Ainsi, on aura par exemple ev(1224) = (121). Comme on peut le constater, ev est surjective mais pas injective, et on a pour tout I ev(p(I)) = I. (5–364) S’il existe une composition I telle que F = p(I), alors on dira que F est une fonction de parking croissante tassée. Enfin, on notera F ≤ G pour dire que F est inférieure terme à terme à G, o`u F et G sont deux fonctions de parking croissantes de même taille. Par exemple, (112234) ≤ (122345).