Séminaire Lotharingien de Combinatoire, B13a (1986), 19 pp. [Formerly : Publ. I.R.M.A. Strasbourg, 1986, 316/S-13, p. 27–44.]

PICS DE CYCLE ET DÉRIVÉES PARTIELLES

PAR

Dominique Dumont

R^{}ÉSUM^{}É. — Nous introduisons quatre suites de polynômes en trois variables présentant de fortes analogies. Chacune de ces suites est définie par une récurrence faisant intervenir des dérivées partielles, chacune peut également se définir à partir du dénombrement des pics de cycle pairs et impairs dans une certaine classe de permutations. En outre, lorsqu’on annule une variable adéquate, les quatre suites de polynômes en deux variables qu’on obtient ont des fonctions génératrices ordinaires pouvant s’écrire comme fractions continues, lesquelles sont des extensions de celles relatives aux nombres d’Euler et de Genocchi. Enfin, lorsqu’on identifie deux variables, les polynômes dégénérés qu’on obtient ont pour fonctions génératrices ordinaires des séries de fractions rationnelles qui, elles aussi, ont toutes la même forme. Ici nos preuves sont purement combinatoires, et le problème est posé d’une version analytique de ces résultats, d’autant que nous ne connaissons pas les fonctions génératrices exponentielles des quatre suites étudiées, sauf pour la première qui est une fonction elliptique.

ABSTRACT. — We introduce four sequences of polynomials in three variables that present strong analogies. Each of those sequences is defined by a recurrence involving partial derivatives, each of them can also be defined in a counting permutation context involving even and odd cycle peaks. Furthermore, when one variable vanishes, the ordinary generating functions for the four sequences of polynomials in two variables thereby derived have continued fraction expansions, that appear to be extensions of the continued fraction expansions for the Euler and Genocchi numbers. Finally, when two variables are identified, the polynomials thereby obtained have ordinary generating functions that can be expressed as series of rational fractions having the same form. The proofs derived here are purely combinatorial. This rises the problem of getting an analytical proof. No exponential generating function is known for those four sequences, except for the first one that is an elliptic function.

1. Deux exemples simples. — Considérons les involutions sans point fixe de l’ensemble [2n] = {1, 2, …, 2n}, c’est-à-dire la classe des permutations ne comportant que des cycles de longueur 2, par exemple l’involution :

σ = (1 6)(2 4)(3 7)(5 8).

Les points maximaux des cycles de cette involution, qu’on peut aussi appeler pics de cycle, sont les quatre entiers 4, 6, 7, 8. Comme il y en a un impair et trois pairs, nous lui faisons correspondre le monôme xy^{3}.

D. DUMONT

Nous posons :

M_{n}(x, y) = ∑_{σ} x^{i(σ)}y^{p(σ)} (σ ∈ Inv(2n)),

où la somme est étendue à toutes les involutions sans pointfixe de [2n], et où p(σ) et i(σ) sont respectivement le nombre de pics de cycle pairs et impairs de σ. Le polynôme M_{n} est donc homogène de degré n, et comme nous nous posons le problème de le calculer par récurrence, nous aboutissons à la proposition suivante :

Proposition 1. — On a :

\begin{aligned}M_{1}(x, y) & = x, \\ M_{n}(x, y) & = 2xy (\frac{∂}{∂x} + \frac{∂}{∂y} ) M_{n−1}(x, y) + yM_{n−1}(x, y). \end{aligned}

Démonstration. — Etant donnée σ une involution sans point fixe de [2n], définissons sa restriction ρ, involution de [2n − 2], comme suit :

si (2n − 1, 2n) est un cycle de σ, alors ρ est la restriction triviale ; sinon, on a deux cycles (a, 2n − 1) et (b, 2n) qu’on remplace par (a, b),

sans changer le reste.

Réciproquement, toute ρ se prolonge en une σ de 2n − 1 manières différentes : soit on choisit l’un des n−1 cycles (a, b) de ρ et on le remplace soit par (a, 2n − 1) et (b, 2n), soit par (a, 2n) et (b, 2n − 1), soit on ajoute simplement (2n − 1, 2n). Dans le premier cas, on aura remplacé l’une des lettres x ou y du monôme x^{i(ρ)}y^{p(ρ)} par 2xy, dans le second cas on aura simplement multiplié le monôme par y. Ceci achève la démonstration.

Voici les premières valeurs de ces polynomes :

\begin{aligned}M_{1}(x, y) & = y, \\ M_{2}(x, y) & = y^{2} + 2xy, \\ M_{3}(x, y) & = y^{3} + 10xy^{2} + 4x^{2}y etc. \end{aligned}

dont nous mentionnerons pour mémoire la fonction génératrice exponentielle :

\frac{1}{\sqrt{1 − \frac{y}{x−y} e^{2(x−y)t} − 1}} = 1 + yt + (y^{2} + 2xy)\frac{t^{2}}{2!} + ⋯ + M_{n}(x, y)\frac{t^{n}}{n!} + ⋯

PICS DE CYCLE ET DÉRIVÉES PARTIELLES

Intéressons-nous à présent à un deuxième exemple bien proche, puisqu’il s’agit de considérer les involutions bipartites de [2n], c’est-à-dire de se restreindre à celles qui satisfont la condition supplémentaire que dans chaque cycle les deux termes sont deux entiers de parités différentes. Exemple :

σ = (8 1)(7 2)(6 5)(4 3) est bipartite.

Par convention, nous ajouterons le cycle supplémentaire (0, 2n + 1) ou, ce qui revient au même, nous compterons un pic de cycle impair en plus. Ainsi à cette involution bipartite σ nous associons le monôme x^{2}y^{3}. Et nous introduisons le polynôme énumérateur analogue :

A_{n}(x, y) = ∑_{σ} x^{i(σ)}y^{p(σ)} (σ ∈ Invbip(2n)).

Proposition 2. — Les polynômes A_{n} sont les polynômes eulériens :

\begin{aligned}A_{1}(x, y) & = xy, \\ A_{n}(x, y) & = xy (\frac{∂}{∂x} + \frac{∂}{∂y} ) A_{n−1}(x, y). \end{aligned}

Démonstration. — La preuve est calquée sur celle de la proposition 1, il convient simplement de respecter le caractère bipartite dans le prolongement de ρ à σ. Si dans le cycle (a, b) choisi pour le prolongement a est pair et b impair, on remplace (a, b) par (a, 2n − 1) et (b, 2n), ce qui se traduit par le remplacement de x ou de y par xy. Le cas du prolongement trivial correspond au choix de (0, 2n − 1) comme cycle (a, b). On obtient ainsi les polynômes eulériens.

2. Les permutations. Les polynômes de Schett. — Nous considérons à présent l’ensemble S_{n} de toutes les permutations de {1, 2, …, n}. Nous décomposons chaque permutation σ en cycles et appelons pic de cycle un entier p strictement supérieur à son antécédent et à son image par la permutation :

σ^{−1}(p) < p > σ(p).

Exemple : σ = (1 2 4)(3 7 6)(5) a un pic de cycle pair (4) et un pic de cycle impair (7).

Mais au lieu de lui faire correspondre le monôme xy comme dans l’étude précédente, nous préférons introduire un monôme en trois variables en considérant les arêtes de cycle. Une arête de cycle est un couple (k, σ(k)) que nous noterons k → σ(k) pour distinguer du cycle de longueur 2. Nous distinguerons :

- les arêtes de cycle incidentes à un pic de cycle impair, c’est-à-dire dont l’origine k ou l’extrémité σ(k) est un pic de cycle impair, que nous appellerons arêtes de type x ;

- les arêtes de cycle incidentes à un pic de cycle pair, ou arêtes de type y ;

- les autres arêtes de cycle, appelées basses ou de type z. En particulier toute boucle k → k est une arête de type z.

En outre, nous convenons d’ajouter une arête 0 → n + 1, de type x ou de type y selon que n + 1 est impair ou pair. Nous posons :

X_{n}(x, y, z) = ∑_{σ} x^{i(σ)}y^{p(σ)}z^{b(σ)} (σ ∈ S_{n}),

où i(σ), p(σ) et b(σ) sont respectivement le nombre d’arêtes de type x, y ou z de la permutation σ.

Exemple : à la permutation ci-dessus correspond le monôme x^{2}y^{3}z^{3}. Nous proposons à présent une nouvelle démonstration (cf. [4]) pour la proposition suivante :

Proposition 3. — Les polynomes X_{n} sont les polynomes de Schett, donnés par la relation de récurrence :

\begin{aligned}X_{0} & = x, \\ X_{1} & = yz, \\ X_{n} & = (yz \frac{∂}{∂x} + zx\frac{∂}{∂y} + xy \frac{∂}{∂z})X_{n−1}. \end{aligned}

Démonstration. — Pour restreindre une permutation σ de S_{n} à une permutation ρ de S_{n−1}, on supprime simplement n de son cycle. Réciproquement, pour prolonger ρ sur S_{n−1} en une permutation σ sur S_{n}, on choisit une arête de cycle a → b de ρ. Si a → b et 0 → n sont deux arêtes distinctes, on les remplace par a → n, n → b et 0 → n + 1. Si au contraire l’arête choisie est 0 → n, alors on la remplace par n → n et 0 → n + 1. Supposons n pair et envisageons les trois cas :

- Cas où a → b est une arête de type x. On la remplace par a → n et n → b qui sont deux arêtes de type y, on convertit l’autre arête incidente à l’ancien pic de cycle impair, elle aussi de type x, en une arête de type z, enfin on change 0 → n en 0 → n + 1. D’où, sur le monôme, l’opération y^{2}(z/x)(x/y)\frac{∂}{∂x} = yz \frac{∂}{∂x}

- Cas où a → b est une arête de type y. Si elle est distincte de 0 → n, on la remplace par a → n et n → b qui sont deux arêtes de type y, on convertit l’autre arête incidente à l’ancien pic de cycle pair, elle aussi de type y, en une arête de type z, enfin on change 0 → n en 0 → n + 1. D’où y^{2}(z/y)(x/y)\frac{∂}{∂y} = zx\frac{∂}{∂y}. Si l’arête de type y choisie est 0 → n, on la remplace par n → n de type z et par 0 → n + 1 de type x, ce qui redonne la même chose.

- Cas où a → b est de type z. On la remplace par a → n et n → b qui sont de type y et on change 0 → n en 0 → n + 1, d’où l’opération y^{2}(x/y)\frac{∂}{∂z} = xy \frac{∂}{∂z}.

La démonstration est tout-à-fait analogue dans le cas où n est impair.

Voici les premières valeurs des polynômes de Schett, étudiés en [4] pour leur lien avec les fonctions elliptiques de Jacobi :

\begin{aligned}X_{0} & = x, \\ X_{1} & = yz, \\ X_{2} & = xy^{2} + xz^{2}, \\ X_{3} & = y^{3}z + yz^{3} + 4x^{2}yz, \\ X_{4} & = xy^{4} + 14xy^{2}z^{2} + xz^{4} + 4x^{3}y^{2} + 4x^{3}z^{2}. \end{aligned}

3. Les permutations circulaires et les polynômes T_{n}. — Reprenant une idée de Désiré André [2], nous restreignons à présent le même dénombrement à l’ensemble C_{n} des permutations circulaires de {1, 2, …, n}, et posons

T_{n}(x, y, z) = ∑_{σ} x^{i(σ)}y^{p(σ)}z^{b(σ)} (σ ∈ C_{n}),

avec cette différence que nous n’ajoutons plus une arête 0 → n + 1 à celles du cycle unique de la permutation.

Proposition 4. — Les polynômes T_{n} satisfont la relation de récurrence :

\begin{aligned}T_{1} & = z, \\ T_{2n} & = y^{2}(\frac{z}{x} \frac{∂}{∂x} + \frac{z}{y} \frac{∂}{∂y} + \frac{∂}{∂z})T_{2n−1}, \\ T_{2n+1} & = x^{2}(\frac{z}{x} \frac{∂}{∂x} + \frac{z}{y} \frac{∂}{∂y} + \frac{∂}{∂z})T_{2n}. \end{aligned}

Démonstration. — En effet la dérivation est la même que dans le cas de la proposition précédente, à ceci près que nous n’avons plus à remplacer 0 → n par 0 → n + 1, ce qui supprime le facteur \frac{x}{y} dans le cas n pair, le facteur \frac{y}{x} dans le cas n impair. Autrement dit, si nous notons en abrégé “Sch” l’opérateur de dérivation définissant les polynômes de Schett : X_{n} = Sch(X_{n−1}), la récurrence sur les polynômes T_{n} est :

\begin{aligned}T_{2n} & = \frac{y}{x} Sch(T_{2n−1}), \\ T_{2n+1} & = \frac{x}{y} Sch(T_{2n}). \end{aligned}

Voici les premières valeurs des polynômes T_{n} :

\begin{aligned}T_{1} & = z, \\ T_{2} & = y^{2}, \\ T_{3} & = 2x^{2}z, \\ T_{4} & = 2x^{2}y^{2} + 4y^{2}z^{2}, \\ T_{5} & = 4x^{4}z + 12x^{2}y^{2}z + 8x^{2}z^{3}, \\ T_{6} & = 4x^{4}y^{2} + 12x^{2}y^{4} + 64x^{2}y^{2}z^{2} + 24y^{4}z^{2} + 16y^{2}z^{4}. \end{aligned}

4. Les permutations bipartites et les polynômes G_{n}. — Une permutation σ de [2n] est dite bipartite si, pour tout k ∈ [2n], k et σ(k) sont deux entiers de parités opposées. Par commodité pour les dénombrements on convient d’ajouter un cycle (0, 2n + 1). Par exemple, 2n = 8 ; σ = (1 4 5 6 3 8)(2 7)(0 9).

Une permutation σ de [2n + 1] est dite bipartite si la même condition est vérifiée pour tout k ∈ [2n], et si σ(2n+1) est impair et constitue donc, de ce fait, la seule entorse au caractère bipartite. Par exemple, 2n+1 = 9 ; τ = (1 4 5 6 9 3 8)(2 7).

Nous définissons à présent la suite G_{n}(x, y, z) comme suit :

\begin{aligned}G_{2n}(x, y, z) & = ∑_{σ} x^{i(σ)}y^{p(σ)}z^{n+1−i(σ)−p(σ)}  (σ ∈ Bip(2n)), \\ G_{2n+1}(x, y, z) & = ∑_{σ} x^{i(σ)}y^{p(σ)}z^{n+1−i(σ)−p(σ)},  (σ ∈ Bip(2n + 1)), \end{aligned}

où i(σ) et p(σ) désignent, comme dans le cas des involutions sans point fixe, le nombre de pics de cycle impairs et pairs de σ. Pour les permutations de Bip(2n), l’entier 2n+1 figure donc toujours parmi les pics de cycle, tandis que pour les permutations de Bip(2n + 1), il n’y figure qu’à condition de ne pas être point fixe.

Proposition 5. — Les polynômes G_{n}(x, y, z) satisfont la récurrence :

G_{1} = z,
G_{2n} = xy (\frac{∂}{∂x} + \frac{∂}{∂y} + \frac{∂}{∂z} ) G_{2n−1}, G_{2n+1} = z (\frac{∂}{∂x} + \frac{∂}{∂y} + \frac{∂}{∂z} ) G_{2n}

Démonstration. — On restreint une permutation τ de [2n + 1] en supprimant 2n + 1 de son cycle et en créant (0, 2n + 1). Dans les exemples ci-dessus σ est la restreinte de τ. Inversement, pour prolonger une permutation σ bipartite sur [2n] en une τ sur [2n + 1], on choisit une arête “pair →impair” p → i de σ qu’on remplace par p → 2n + 1 et 2n + 1 → i, et on supprime (0, 2n + 1). Si l’arête p → i choisie était 0 → 2n + 1 on la remplace simplement par le point fixe (2n + 1).

Remarquons que le polynôme G_{2n}(x, y, z) défini plus haut comme polynôme énumérateur des pics de cycles est également polynôme énumérateur sur les permutations σ des arêtes pair→impair selon leur type x, y ou z, et en ce sens nous dirons que les arêtes p → i repèrent les pics de cycle. Examinons ce qui se passe dans le dénombrement de ces arêtes quand on prolonge σ en τ. A part la dérivation de l’arête p → i choisie et quel que soit son type, rien n’est changé puisque p → 2n + 1 remplace 0 → 2n+1 en tant qu’arête de type x. En fait, τ a une arête pair→ impair de moins que σ et la dérivation n’a pas créé de nouveau pic de cycle, mais par convention G_{2n+1} doit avoir le même degré que G_{2n}, par conséquent il faut multiplier par z. D’où z (\frac{∂}{∂x} + \frac{∂}{∂y} + \frac{∂}{∂z} ).

Exemples ci-dessus : le monôme de σ est x^{2}y^{2}z, l’arête choisie pour le prolongement est 6 → 3,de type y. On supprime cet y et on multiplie par z, d’où le monôme de τ : x^{2}yz^{2}.

A présent pour restreindre une permutation σ sur [2n] en une ρ sur [2n − 1] on procède comme suit : on pose i = σ^{−1}(2n), i′ = σ(2n), p′ = σ(2n − 1), et on remplace les arêtes i → 2n, 2n → i′ et 2n − 1 → p′ par 2n − 1 → i′ et i → p′, cela sauf si σ(2n − 1) = 2n auquel cas on supprime simplement 2n. On supprime également le cycle (0, 2n + 1). Par exemple, la restreinte de σ = (1 4 5 6 3 8)(2 7)(0 9) est ρ = (1 4 5 6 3 2 7).

Inversement on prolonge une permutation bipartite ρ sur [2n − 1] en une σ de la manière suivante :

- soit on choisit une arête impair→pair notée i → p′ qu’on supprime ainsi que 2n − 1 → i′ pour créer les arêtes i → 2n, 2n − 1 → p′ et 2n → i′ sans oublier les deux arêtes du cycle (0, 2n + 1) ;

- soit on choisit l’arête impair→impair 2n − 1 → i′ qu’on remplace par 2n − 1 → 2n et 2n → i′, et on ajoute encore le cycle (0, 2n + 1).

Remarquons que les arêtes impair→pair ne repèrent pas, au sens précisé plus haut, tous les pics de cycle de ρ puisque 2n − 1 est repéré par 2n − 1 → i′, que nous décompterons donc comme arête de type x. En revanche dans σ les arêtes impair→pair suffisent à repérer tous les pics de cycle. Dans le prolongement de ρ à σ, on dérive donc une arête repérante quelconque i → p′ ou 2n − 1 → i′, et on crée deux nouvelles arêtes impair→pair , l’une, i → 2n ou 2n − 1 → 2n, de type y, et l’autre, 2n + 1 → 0, de type x, l’autre arête de type x 2n − 1 → p′ remplaçant 2n − 1 → i′ dans le décompte si on a dérivé une arête i → p′. D’où xy (\frac{∂}{∂x} + \frac{∂}{∂y} + \frac{∂}{∂z} ).

Exemples ci-dessus. — ρ a pour monôme xyz^{2}, on dérive l’arête 3 → 2 de type z et on obtient σ, dont le monôme s’obtient en remplaçant une occurence de z par xy, d’où x^{2}y^{2}z.

Voici les premières valeurs des polynômes G_{n} :

\begin{aligned}G_{1} & = z, \\ G_{2} & = xy, \\ G_{3} & = xz + yz, \\ G_{4} & = x^{2}y + xy^{2} + 2xyz, \\ G_{5} & = x^{2}z + 6xyz + y^{2}z + 2xz^{2} + 2yz^{2}, \\ G_{6} & = x^{3}y + 6x^{2}y^{2} + xy^{3} + 12x^{2}yz + 12xy^{2}z + 4xyz^{2}. \end{aligned}

5. Les permutations bipartites circulaires et les polynômes H_{n}. Une permutation bipartite circulaire est à peu près une permutation bipartite ne comportant qu’un seul cycle. En fait, dans le cas [2n] on convient de lui adjoindre le cycle (0, 2n + 1), et dans le cas [2n + 1] on accepte non seulement l’arête 2n + 1 → i′ dans le cycle mais aussi la possibilité d’un point fixe (2n + 1).

Exemples : sur [10], σ = (1 10 3 8 5 2 9 4 7 6)(0 11) ; sur [7], σ′ = (1 4 5 2 3 6)(7) ou σ′′ = (1 4 7 5 2 3 6).

Nous définissons les polynômes H_{n}(x, y, z) pour n ≥ 2 comme suit :

\begin{aligned}H_{2n}(x, y, z) & = ∑_{σ} x^{i(σ)}y^{p(σ)}z^{n+1−i(σ)−p(σ)}  (σ ∈ Bipcirc(2n)), \\ H_{2n+1}(x, y, z) & = ∑_{σ} x^{i(σ)}y^{p(σ)}z^{n−i(σ)−p(σ)}  (σ ∈ Bipcirc(2n + 1)). \end{aligned}

où i(σ) et p(σ) désignent le nombre de pics de cycle impairs et pairs de σ avec les conventions ci-dessus. Remarquons que les arêtes pair→impair de σ repèrent ses pics de cycle, par conséquent les polynômes H_{n} sont également énumérateurs de ces arêtes selon leurs types. Dans les exemples ci-dessus, σ a pour monôme x^{3}y^{2}z, σ′ et σ′′ ont le même monôme xyz.

Proposition 6. — Les polynômes H_{n} satisfont la récurrence :

\begin{aligned}H_{2}(x, y, z) & = xy, \\ H_{2n+1}(x, y, z) & = (\frac{∂}{∂x} + \frac{∂}{∂y} + \frac{∂}{∂z} ) H_{2n}(x, y, z)  (2n + 1 ≥ 3), \\ H_{2n}(x, y, z) & = xyz (\frac{∂}{∂x} + \frac{∂}{∂y} + \frac{∂}{∂z} ) H_{2n−1}(x, y, z)  (2n ≥ 4). \end{aligned}

De ce fait les polynômes H_{n} sont symétriques dans les trois variables à partir de n = 4.

Démonstration. — On restreint une permutation bipartite circulaire σ sur [2n+1] en une ρ sur [2n] par suppression de 2n+1 et création du cycle (0, 2n+1). Inversement on prolonge ρ en choisissant une arête pair→impair quelconque. Si cette arête est 0 → 2n + 1 on la remplace simplement par la boucle (2n + 1). Sinon, on remplace cette arête p → i et 0 → 2n + 1 par p → 2n + 1 et 2n + 1 → i. Dans les deux cas il n’y a eu aucune création de pic de cycle et le résultat sur le monôme est (\frac{∂}{∂x} + \frac{∂}{∂y} + \frac{∂}{∂z} ).

Nous définissons à présent la restriction ρ d’une permutation bipartite circulaire σ sur [2n] de la manière suivante : nous posons i = σ^{−1}(2n), i′ = σ(2n), p = σ^{−1}(2n − 1), p′ = σ(2n − 1).

- Si i ≠ 2n − 1 et i′ ≠ 2n − 1, nous supprimons les arêtes i → 2n, 2n → i′, p → 2n − 1, 2n − 1 → p′, ainsi que le cycle (0, 2n + 1), puis créons les arêtes p → i, p′ → 2n − 1 et 2n − 1 → i′, enfin renversons le sens de la séquence d’arêtes (p′ → ⋯ → i) en séquence (i → ⋯ → p′), en ne laissant finalement inchangée que la séquence (i′ → ⋯ → p). Exemple : la restriction de σ = (1 10 3 8 5 2 9 4 7 6)(0 11) est ρ = (9 3 8 5 2 1 6 7 4).

- Si i′ = 2n − 1, nous supprimons les arêtes 2n → 2n − 1, i → 2n et 2n − 1 → p′, créons p′ → i et la boucle (2n − 1), enfin renversons le sens de la séquence (p′ → ⋯ → i) en séquence (i → ⋯ → p′) ;

- Si i = 2n − 1, nous supprimons simplement 2n du cycle.

Réciproquement, pour prolonger ρ, il suffit de choisir une arête p → i de ρ, de la supprimer ainsi que 2n − 1 → i′, de renverser le sens de la séquence (i → ⋯ → 2n − 1), de créer i → 2n, 2n → i′, ainsi que le cycle (0, 2n + 1), autrement dit de créer exactement deux nouveaux pics de cycle, 2n et 2n + 1, l’un de type x et l’autre de type y. Exactement, car d’une part le pic de cycle 2n − 1, quand il existe ailleurs que sur l’arête p → i, est conservé, d’autre part le fait d’avoir inversé le sens de la séquence (i → ⋯ → p′) n’a en rien modifié sa contribution en pics de cycle. Il reste que le polynome H_{2n} étant de degré n + 1 et H_{2n−1} de degré n − 1, il convient encore de multiplier par z. Du point de vue des arêtes pair→impair , la prolongée σ en a deux de plus que ρ, et même trois après suppression de l’arête p → i qui définit le prolongement, création de l’arête de type x 0 → 2n + 1, de l’arête de type y 2n → i′, et d’une arête de type z. D’où, sur le monôme, la dérivation xyz (\frac{∂}{∂x} + \frac{∂}{∂y} + \frac{∂}{∂z} ).

Voici les premières valeurs des polynômes H_{n} :

H_{2} = xy,
H_{3} = x + y,
H_{4} = 2xyz,

H_{5} = 2xy + 2xz + 2yz,
H_{6} = 4x^{2}yz + 4xy^{2}z + 4xyz^{2},
H_{7} = 4x^{2}y + 4x^{2}z + 4xy^{2} + 24xyz + 4xz^{2} + 4y^{2}z + 4yz^{2},
H_{8} = 8x^{3}yz + 40x^{2}y^{2}z + 40x^{2}yz^{2} + 8xy^{3}z + 40xy^{2}z^{2} + 8xyz^{3},

6. Quelques fractions continues. — On montre assez facilement, suivant Touchard (cf. [6] et [8]), la formule suivante. Si (c_{n})_{n≥1} est une suite quelconque, que nous appellerons valuation , alors on a :

\frac{1}{1 − \frac{c_{1}u}{1 − \frac{c_{2}u}{1 − \frac{c_{3}u}{…}}}} = 1 + c_{1}u + (c_{1}c_{1} + c_{1}c_{2})u^{2} + (c_{1}c_{1}c_{1} + c_{1}c_{1}c_{2} + c_{1}c_{2}c_{1} ; +c_{1}c_{2}c_{2} + c_{1}c_{2}c_{3})u^{3} + ⋯ + (∑_{d} c_{d_{1}}c_{d_{2}} … c_{d_{n}})u^{n} ; + ⋯

la sommation pour chaque n s’effectuant sur les suites ou mots de Dyck d = (d_{1}, d_{2}, …, d_{n}) que l’on définit par la condition (δ) suivante

\begin{matrix}d_{1} & = 1, \\ 1 ≤ & d_{i} ≤ d_{i−1} + 1 (1 ≤ i ≤ n). \end{matrix}

Le produit c_{d_{1}}c_{d_{2}} … c_{d_{n}} est appelé poids de la suite de Dyck d relativement à la valuation (c_{n}).

En fait, nous aurons surtout affaire à la présentation suivante de la formule de Touchard :

\frac{1}{1 − \frac{c_{1}yu}{1 − \frac{c_{2}xu}{1 − \frac{c_{3}yu}{\begin{aligned}. & . & . \\ & & & 1 − \frac{c_{2n}xu}{1 − \frac{c_{2n+1}yu}{…}} \end{aligned}}}}} = 1 + c_{1}yu + (c_{1}c_{1}y^{2} + c_{1}c_{2}xy)u^{2} ; + (c_{1}c_{1}c_{1}y^{3} ; + (c_{1}c_{1}c_{2} + c_{1}c_{2}c_{1} + c_{1}c_{2}c_{3})xy^{2} ; + c_{1}c_{2}c_{2}x^{2}y)u^{3} + ⋯; + (∑_{d} c_{d_{1}}c_{d_{2}} … c_{d_{n}}x^{p(d)}y^{i(d)})u^{n}, ; + ⋯,

où p(d) et i(d) désignent respectivement le nombre d’entiers d_{i} pairs et impairs de la suite de Dyck d.

Nous allons à présent nous restreindre, dans chacune des classes de permutations considérées précédemment, à la sous-classe de celles qui ont le maximum de pics de cycle. Dans le cas des involutions il ne s’agira pas à proprement parler d’une restriction, mais dans le cas des permutations, dans celui des permutations circulaires et dans celui des permutations bipartites, nous nous restreindrons à celles qui, opérant sur [2n], ont n pics de cycle (dans le cas des permutations bipartites circulaires sur [2n], ce nombre maximum tombe à n − 1).

Convenons donc de ranger ces n pics de cycle par ordre décroissant :

2n = p_{1} > p_{2} > p_{3} > … > p_{n}.

La suite p = (p_{i}) vérifie en outre la condition (π) :

p_{i} ≥ 2(n − i + 1) (1 ≤ i ≤ n)

qui exprime le fait que p_{i}, p_{i+1}, … p_{n} et leurs (n − i + 1) images par la permutation sont des entiers distincts et tous inférieurs ou égaux à p_{i}. Posons alors :

d_{i} = p_{i} − 2(n − i) − 1

La suite d = (d_{i}) ainsi définie est une suite de Dyck. Les conditions (δ) et (π) sont équivalentes et réciproquement la donnée d’une suite de Dyck définit un ensemble de n pics de cycle.

Exemple : σ = (8 5 6 1)(7 3)(4 2), permutation sur [8], a 4 pics de cycle 8, 7, 6, 4 auxquels correspond la suite de Dyck d = (1, 2, 3, 3).

Nous allons montrer que pour chacune des classes de permutations considérées, le nombre de celles qui ont une suite de pics de cycle p donnée est égal au poids c_{d_{1}}c_{d_{2}} … c_{d_{n}} de la suite de Dyck d correspondant à p relativement à une certaine valuation dépendant de la classe considérée. En outre, p_{i} et d_{i} sont toujours de parités opposées d’où

p(σ) = i(d) et i(σ) = p(d).

Dans chaque cas, on obtiendra donc une fraction continue comme fonction génératrice ordinaire des polynômes P_{n}(x, y, 0), P_{n} étant une notation générique des différentes suites de polynômes introduites ici, et l’annulation de la variable z traduisant le fait qu’on s’est restreint à la sous-classe des permutations ayant un nombre maximum de pics de cycle donc sans arêtes de type z (on pourrait, par analogie avec les permutations alternantes d’André [1], les appeler cyclalternantes ).

Proposition 7. — Les six suites de polynômes introduites vérifient

D. DUMONT

les identités suivantes :

\frac{1}{1 − \frac{yu}{1 − \frac{2xu}{1 − \frac{3yu}{\begin{aligned}. & . & . \\ & & & 1 − \frac{(2n)xu}{1 − \frac{(2n + 1)yu}{…}} \end{aligned}}}}} = 1 + ∑_{n≥1} M_{n}(x, y)u^{n}

\frac{x}{1 − \frac{yu}{1 − \frac{xu}{1 − \frac{2yu}{1 − \frac{2xu}{\begin{aligned}. & . & . \\ & & & 1 − \frac{nyu}{1 − \frac{nxu}{…}} \end{aligned}}}}}} = x + ∑_{n≥1} A_{n}(x, y)u^{n}

\frac{x}{1 − \frac{y^{2}u}{1 − \frac{4x^{2}u}{1 − \frac{9y^{2}u}{\begin{aligned}. & . & . \\ & & & 1 − \frac{(2n)^{2}x^{2}u}{1 − \frac{(2n + 1)^{2}y^{2}u}{…}} \end{aligned}}}}} = ∑_{n≥0} X_{2n}(x, y, 0)u^{n}

\frac{x}{1 − \frac{yu}{1 − \frac{xu}{1 − \frac{4yu}{1 − \frac{4xu}{\begin{aligned}. & . & . \\ & & & 1 − \frac{n^{2}yu}{1 − \frac{n^{2}xu}{…}} \end{aligned}}}}}} = ∑_{n≥0} G_{2n}(x, y, 0)u^{n}

\frac{y^{2}}{1 − \frac{2x^{2}u}{1 − \frac{6y^{2}u}{1 − \frac{12x^{2}u}{\begin{aligned}. & . & . \\ & & & 1 − \frac{(2n − 1)(2n)x^{2}u}{1 − \frac{(2n)(2n + 1)y^{2}u}{…}} \end{aligned}}}}} = ∑_{n≥0} T_{2n+2}(x, y, 0)u^{n}

\frac{x}{1 − \frac{2yu}{1 − \frac{2xu}{1 − \frac{6yu}{1 − \frac{6xu}{\begin{aligned}. & . & . \\ & & & 1 − \frac{n(n + 1)yu}{1 − \frac{n(n + 1)xu}{…}} \end{aligned}}}}}} = x + ∑_{n≥1} \overline{H}_{2n+2}(x, y, 0)u^{n},

où \overline{H}_{2n+2}(x, y, z) = (1/z)H_{2n+2}(x, y, z).

Remarque. — Il manque à cette liste la formule suivante, pour la démonstration de laquelle nous aurions besoin d’un autre modèle combinatoire, celui des pistolets ([5], [9]) :

\frac{z}{1 − \frac{yu}{1 − \frac{2zu}{1 − \frac{4yu}{\begin{aligned}. & . & . \\ & & & 1 − \frac{n(n − 1)zu}{1 − \frac{n^{2}yu}{…}} \end{aligned}}}}} = ∑_{n≥0} G_{2n+1}(0, y, z)u^{n}.

Démonstration. — Pour établir la première formule, nous devons dénombrer les involutions sans point fixe de la forme

(p_{1}, q_{1})(p_{2}, q_{2}) … (p_{n}, q_{n}),

où la suite des pics (p_{i}) a été donnée, décroissante et satisfaisant (π). Dans ces conditions il y a

\begin{aligned}p_{n} − 1 & = d_{n} choix possibles pour q_{n}, \\ p_{n−1} − 3 & = d_{n−1} choix possibles pour q_{n−1}, \\ p_{i} − 2(n − i) − 1 & = d_{i} choix possibles pour q_{i} etc. \end{aligned}

Le nombre d’involutions répondant à la question est donc égal à d_{1}d_{2} ⋯ d_{n}, la valuation correspondante est c_{n} = n, et on raffine en pics pairs et impairs en remplaçant alternativement c_{2n−1} par (2n − 1)y et c_{2n} par (2n)x. Notons qu’on trouve une preuve analytique de cette formule à partir de la fonction génératrice mentionnée plus haut dans [10].

Pour établir la deuxième formule, nous considérons les involutions bipartites. Fixons donc à nouveau une suite de pics (p_{i}) à laquelle correspond la suite de Dyck d_{i}). Le nombre de choix pour q_{n} n’est plus p_{n} − 1, mais le nombre d’entiers inférieurs à p_{n} et de parité opposée , or ce nombre est la partie entière

E (\frac{p_{n}}{2} ) = E (\frac{d_{n} + 1}{2}) .

Plus généralement, pour choisir q_{i}, il faut exclure parmi les entiers inférieurs à p_{i} tous ceux déjà occupés par p_{i+1}, q_{i+1}, p_{i+2}, q_{i+2}, …, p_{n}, q_{n} qui sont au nombre de 2n−2i et comportent autant de pairs que d’impairs, et parmi les entiers restants en choisir un de parité opposée à p_{i}, soit

E (\frac{p_{i} − 2(n − i)}{2}) = E (\frac{d_{i} + 1}{2}) choix.

On doit donc prendre pour valuation c_{n} = E((n + 1)/2), ce qui donne la fraction continue d’Euler, raffinée en celle des polynomes eulériens.

On passe aux deux formules suivantes en observant qu’à une permutation σ de [2n] ayant n pics de cycle p_{i} on fait correspondre bijectivement un couple ordonné de deux involutions sans point fixe ayant les mêmes pics que σ, la première appliquant ces pics sur leurs images par σ, la seconde appliquant de même les antécédents des pics sur les pics. Cette correspondance bijective établit que la valuation pour les permutations n’est autre que le carré de la valuation pour les involutions. En outre la permutation sera bipartite si et seulement si les deux involutions le sont également. Cela suffit à établir les deux formules. La première concerne en fait le cosinus elliptique cn(u) (à ce sujet, voir [6] et [10]), fonction génératrice exponentielle des polynomes X_{2n}(x, y, 0) qui dégénère en sec(u) pour x = y = 1, la seconde constitue un analogue Genocchi puisque les coefficients G_{2n}(1, 1, 0) sont, de manière similaire, les nombres de Genocchi de deuxième espèce ou “médians”(à ce sujet, cf. [3], [5] et [9]). Quant à la première des deux dernières formules, il s’agit d’un analogue tangent , car les T_{2n}(1, 1, 0) sont les nombres tangents [9], mais nous ignorons si, comme dans le cas sécant, l’extension proposée ici est en relation avec une fonction elliptique.

Pour établir les deux dernières formules il faut simplement, dans le choix de l’antécédent q_{i} et de l’image q′_{i} du pic de cycle p_{i}, tenir compte du fait que la permutation finale σ doit être circulaire, et qu’on doit donc éviter de boucler un cycle avant l’étape finale. Plaçons-nous donc dans le cas des permutations circulaires sur [2n] ayant n pics de cycle donnés (p_{i})_{1≤i≤n}. Pour l’antécédent q_{n} de p_{n} il y a p_{n} − 1 choix, pour son image q′_{n} il reste p_{n}−2 choix, d’où, à ce stade, d_{n}(d_{n}−1) choix. A présent supposons choisis les antécédents et images de p_{i+1}, p_{i+2}, …, p_{n}. Comme certaines images de pic peuvent avoir été choisies comme antécédents d’un autre pic, il s’est formé des chaînes de pics , chacune commençant par un antécédent et aboutissant à une image, et aucune chaîne ne s’étant fermée puisque nous supposons que le choix a été correct. Pour choisir l’antécédent q_{i} de p_{i} il suffit de choisir un entier inférieur à p_{i}, différent des n − i pics p_{i+1}, p_{i+2}, …, p_{n} et de leurs n − i antécédents (mais pouvant être une de leurs images), ce qui représente

p_{i} − 2(n − i) − 1 = d_{i} choix pour q_{i}.

Pour choisir ensuite l’image q′_{i} de p_{i}, il faut un entier inférieur à p_{i}, différent des n − i pics et de leurs n − i images, mais aussi différent d’un élément supplémentaire qui est, soit l’antécédent q_{i} si celui-ci n’a pas été choisi parmi les images des pics antérieurs, soit, dans le cas inverse, l’antécédent de pic qui inaugure la chaîne aboutissant à q_{i}, cela pour, dans un cas comme dans l’autre, éviter de boucler un cycle. Ainsi il y a

d_{i} − 1 choix pour q′_{i}.

A l’étape finale, il n’y a que d_{1} = 1 choix possible pour l’antécédent comme pour l’image de p_{1} pour boucler le cycle unique de la permutation. D’où une valuation c_{n} = n(n − 1) pour n ≥ 2 et c_{1} = 1.

Le cas des permutations bipartites circulaires est tout-à-fait analogue, à ceci près qu’une telle permutation sur [2n+2] comporte au maximum n, et non pas n + 1, pics de cycle, donc comporte toujours des arêtes de type z. D’où la nécessité de diviser préalablement par z le polynome avant de porter z = 0. Il faut également choisir images et antécédents de manière bipartite, ce qui conduit à la valuation

c_{n} = E(\frac{n + 1}{2}) (E(\frac{n + 1}{2}) − 1) (n ≥ 2) et c_{1} = 1.

7. Quelques séries de fractions rationnelles.

Proposition 8. — Les polynômes étudiés dans les sections précédentes satisfont les identités suivantes :

∑_{n≥1} \frac{1.3.5 … (2n − 1) t^{n}}{(1 − 2(x − 1)t)(1 − 4(x − 1)t) ⋯ (1 − 2n(x − 1)t)} = ∑_{n≥1} M_{n}(x, 1)t^{n}

D. DUMONT

∑_{n≥1} \frac{n! t^{n}}{(1 − (x − 1)t)(1 − 2(x − 1)t) ⋯ (1 − n(x − 1)t)} = ∑_{n≥1} \frac{1}{x}A_{n}(x, 1)t^{n}

∑_{n≥1} \frac{(2n − 1)! t^{n}}{(1 − 4(x^{2} − 1)t) ⋯ (1 − 4n^{2}(x^{2} − 1)t)} = ∑_{n≥1} X_{2n−1}(x, 1, 1)t^{n}

∑_{n≥1} \frac{(2n)! t^{n}}{(1 − 4(x^{2} − 1)t) ⋯ (1 − 4n^{2}(x^{2} − 1)t)} = ∑_{n≥1} \frac{1}{x}X_{2n}(x, 1, 1)t^{n}

∑_{n≥1} \frac{(2n − 1)! t^{n}}{(1 − (z^{2} − 1)t) ⋯ (1 − (2n − 1)^{2}(z^{2} − 1)t)} = ∑_{n≥1} \frac{1}{z}X_{2n−1}(1, 1, z)t^{n}

∑_{n≥1} \frac{(2n)! t^{n}}{(1 − (z^{2} − 1)t) ⋯ (1 − (2n − 1)^{2}(z^{2} − 1)t)} = ∑_{n≥0} X_{2n}(1, 1, z)t^{n+1}

∑_{n≥1} \frac{(n − 1)! n! t^{n}}{(1 − (x − 1)t)(1 − 4(x − 1)t) ⋯ (1 − n^{2}(x − 1)t)}

= ∑_{n≥1} G_{2n−1}(x, 1, 1)t^{n}

∑_{n≥1} \frac{(n!)^{2}t^{n}}{(1 − (x − 1)t)(1 − 4(x − 1)t) ⋯ (1 − n^{2}(x − 1)t)}

= ∑_{n≥1} \frac{1}{x}G_{2n}(x, 1, 1)t^{n}

∑_{n≥1} \frac{(n!)^{2}t^{n}}{(1 − 2(z − 1)t)(1 − 6(z − 1)t) ⋯ (1 − n(n + 1)(z − 1)t)}

= ∑_{n≥1} G_{2n}(1, 1, z)t^{n}

∑_{n≥1} \frac{(n − 1)! n! t^{n}}{(1 − 2(z − 1)t)(1 − 6(z − 1)t) ⋯ (1 − n(n + 1)(z − 1)t)}

= ∑_{n≥1} H_{2n}(1, 1, z)t^{n}

∑_{n≥1} \frac{(n − 1)! (n + 1)! t^{n}}{(1 − 2(z − 1)t)(1 − 6(z − 1)t) ⋯ (1 − n(n + 1)(z − 1)t)}

= ∑_{n≥1} H_{2n+1}(1, 1, z)t^{n}

En outre, si on substitue z à x dans X_{n}(x, 1, 1) on obtient T_{n+1}(1, 1, z), d’où une réécriture des troisième et quatrième identités. De même, on a

G_{2n−1}(1, 1, z) = H_{2n}(1, 1, z)

Démonstration. — Nous nous bornerons à résumer les démonstrations combinatoires de ces identités, toutes calquées sur le même modèle. Dans chaque cas, le membre de gauche est de la forme :

∑_{n} \frac{u_{n}t^{n}}{(1 − a_{1}(x − 1)t) ⋯ (1 − a_{n}(x − 1)t)}.

Dans ce développement, le coefficient de t^{n} est

∑_{k=0}^{k=n−1} u_{n−k}S_{k}(a_{1}, …, a_{n−k+1})(x − 1)^{k},

où S_{k} désigne la fonction symétrique homogène de degré k dans les (a_{i})_{1≤i≤n−k+1}. Quand a_{i} = i, ces fonctions symétriques sont les nombres de Stirling de deuxième espèce, quand a_{i} = i^{2} ce sont les nombres dits factoriels centraux etc.

On se propose de calculer par inclusion-exclusion le nombre de permutations d’une classe donnée ayant un nombre déterminé de pics de cycle d’une parité déterminée. A cet effet nous dénombrons d’abord les couples (C_{k}, σ), où C_{k} désigne un choix de k pics de cycle et σ une permutation possédant ces pics de cycle, plus d’autres éventuellement. On montre (cas par cas…) que S_{k}(a_{i}) est le nombre de ces choix C_{k} et que u_{n−k} est le nombre de manières de compléter chaque choix en une permutation σ. La variable (x−1)^{k} indique qu’on en déduit le nombre de permutations ayant exactement un certain nombre de pics de cycle par inclusion-exclusion.

Remarquons pour conclure qu’on peut sans grande difficulté démontrer les six premières formules par des calculs sur les fonctions génératrices, ou par d’autres considérations combinatoires. La seconde notamment est une identité bien connue liant les nombres eulériens aux nombres de Stirling [7]. Quant aux cinq dernières formules, elles ont été établies par des calculs analytiques dans le cas x = z = 0 (pour une démonstration globale, cf. [3]).

Appendice (D. Dumont, Novembre 1994)

Lors de mon exposé à Bologne en 1985, j’ai énoncé une conjecture prolongeant les résultats de cet article, conjecture qui a été démontrée récemment par Benjamin Randrianirina.

Il s’agit de faire le même dénombrement sur l’ensemble des permutations σ de [n] dont tous les cycles sont de longueurs impaires, ensemble que nous notons ℑ_{n}.

La notation Sch désignant toujours l’opérateur différentiel de Schett défini au § 3 ci-dessus, on considère les polynômes I_{n}(x, y, z) définis comme suit :

I_{1} = y, I_{2n} = z Sch(I_{2n−1}), I_{2n+1} = \frac{1}{z} Sch(I_{2n}).

Les paramètres i(σ), p(σ) et b(σ) ont été définis au § 2 ci-dessus. On a alors le résultat suivant :

Théorème (Randrianirina [A5]).

\begin{aligned}I_{2n}(x, y, z) & = x ∑_{σ∈ℑ_{2n}} x^{i(σ)}y^{p(σ)}z^{b(σ)}, \\ zI_{2n+1}(x, y, z) & = y ∑_{σ∈ℑ_{2n+1}} x^{i(σ)}y^{p(σ)}z^{b(σ)}. \end{aligned}

On trouvera une démonstration dans [A5]. Cette démonstration n’est pas apparentée à celles qui sont mises en oeuvre dans le présent article , elle est plus complexe et utilise d’autres méthodes développées dans [4] à propos du dénombrement analogue sur les permutations dont les cycles sont de longueurs paires.

Le problème du calcul des fonctions génératrices exponentielles des polynômes T_{n}(x, y, z), G_{n}(x, y, z), H_{n}(x, y, z), I_{n}(x, y, z), qui sont peutêtre des fonctions elliptiques, ou des fonctions apparentées, reste ouvert.

Par ailleurs, on trouvera dans d’autres contributions parues entretemps, ou à paraître prochainement, des développements en fractions continues et en séries de fractions rationnelles qui sont liés à ceux du présent article ([A1], [A2], [A3], [A4]).

BIBLIOGRAPHIE

[1] D. ANDR^{}É. — Sur les permutations alternées, J. Math. Pures Appl., t. 7, 1881, p. 167–184.

[2] D. ANDR^{}É. — Mémoire sur les séquences des permutations circulaires, Bull. Soc. Math. France, t. 23, 1895, p. 122–184.

[3] D. BARSKY. — Congruences pour les nombres de Genocchi de deuxième espèce, Séminaire d’Analyse Ultramétrique, t. 34, 1980, p. 1–13.

[4] D. DUMONT. — Une approche combinatoire des fonctions elliptiques de Jacobi, Adv. in Math., t. 41, 1981, p. 1–39.

[5] D. DUMONT, G. VIENNOT. — The Seidel generation of Genocchi numbers, Ann. Disc. Math., t. 6, 1980, p. 77–87.

[6] P. FLAJOLET. — Combinatorial aspects of continued fractions, Disc. Math., t. 32, 1980, p. 125–161.

[7] I. GESSEL. — Generating functions and enumeration of sequences. — M.I.T. 1973.

[8] J. TOUCHARD. — Sur un problème de configurations et sur les fractions continues, Canad. J. of Math., t. 4, 1952, p. 2–25.

[9] G. VIENNOT. — Interprétations combinatoires des nombres d’Euler et de Genocchi. — Séminaire Th. des Nombres, Bordeaux 1981.

[10] H.S. WALL. — Analytic Theory of continued fractions. — Chelsea, London 1973.

BIBLIOGRAPHIE APPENDICE

[A1] D. DUMONT, A. RANDRIANARIVONY. — Dérangements et nombres de Genocchi, Disc. Math., t. 132, 1994, p. 37–49.

[A2] D. DUMONT, J. ZENG. — Further results on the Euler and Genocchi numbers , Aequat. Math., t. 47, 1994, p. 31–42.

[A3] A. RANDRIANARIVONY. — Fractions continues, q-nombres de Catalan et qpolynômes de Genocchi, in Thèse math., Univ. Louis-Pasteur, Strasbourg, 1994.

[A4] A. RANDRIANARIVONY, J. ZENG. — Une famille de polynômes qui interpole plusieurs suites classiques de nombres, Actes 31^{e} Séminaire Lotharingien, p. 103-126. — Publ. I.R.M.A. Strasbourg, 1994/021.

[A5] B. RANDRIANIRINA. — Dérangements, successions et pics de cycle dans les permutations, Mémoire de D.E.A., Université de Fianarantsoa 1993.

Dominique DUMONT,

Département de mathématique, Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg.