Variations sur le thème E+\overline{E} = XY

Bodo LASS

Département de mathématique, Université Louis Pasteur, 7, rue René-Descartes F-67084 Strasbourg, France Courriel: lass@math.u-strasbg.fr

Soit G=(X,Y;E) un graphe biparti et \overline{G}=(X,Y;\overline{E}) le graphe biparti complémentaire. Notons p(G,r) le nombre des r-couplages de G. Il est classique que le vecteur [p(\overline{G},r)]_{r=1,2,...} est déterminé par [p(G,r)]_{r=1,2,...}. Nous explicitons ce fait en démontrant des théorèmes de dualité nouveaux, généralisant et globalisant notamment les résultats de Chow, Foata, Gessel, Joni, Rota et Zeilberger. Pour des graphes orientés on obtient ainsi une preuve rapide de l’identité fondamentale de Berge entre des chemins et des circuits hamiltoniens. Exprimée dans le langage des fonctions d’ensembles, celle-ci implique immédiatement la conjecture de Chung et Graham (établie d’abord par Chow et Gessel) ainsi que les théorèmes de parité de Rédei sur les tournois, de Lovász sur les graphes non-orientés et de Camion et Rao sur les graphes auto-complémentaires. Finalement, nous étudions les relations entre les fonctions d’ensembles et les fonctions symétriques. Le théorème principal de la thèse de Chow devient ainsi une conséquence directe de l’identité de Berge.

Let G=(X,Y;E) be a bipartite graph with bipartite complement \overline{G}=(X,Y;\overline{E}). The number of r-matchings of G is denoted by p(G,r). It is classical that the vector [p(\overline{G},r)]_{r=1,2,...} is determined by [p(G,r)]_{r=1,2,...}. We make this statement more explicit by proving new duality theorems, generalizing and globalizing the results of Chow, Foata, Gessel, Joni, Rota and Zeilberger, in particular. For oriented graphs this provides a short proof of Berge’s fundamental identity between Hamiltonian paths and circuits. Expressed in terms of set functions, the identity immediately implies the Chung-Graham conjecture (first derived by Chow and Gessel) as well as Rédei’s, Lovász’, and Camion’s and Rao’s parity results for tournaments, non-oriented and self-complementary graphs, respectively. Finally, we study the relations between set functions and symmetric functions and show that the main theorem in Chow’s Ph.D. Thesis becomes a direct consequence of Berge’s identity.

1. Introduction

Soient X et Y deux ensembles disjoints de cardinalité n et m, respectivement. Un graphe biparti G = (X, Y; E) est dit simple si et seulement si l’ensemble de ses arêtes E est un sous-ensemble de X × Y. Pour de tels graphes on définit le graphe biparti complémentaire par \overline{G} := (X, Y; \overline{E}) avec \overline{E} := (X × Y)\E. On appelle r-couplage de G un ensemble de r arêtes tel que deux quelconques des arêtes du couplage sont non-adjacentes. Notons p(G, r) le nombre des r-couplages de G et posons p(G, 0) := 1. Traditionellement, on interprète X (resp. Y) comme

BODO LASS

Key words: graph, rook polynomial, complementary graph, Hamiltonian circuit, Hamiltonian path, cover polynomial, tournament, Rédei’s theorem, selfcomplementary graph, symmetric functions un ensemble de lignes (resp. colonnes) d’un échiquier rectangulaire de sorte qu’un couplage devient un ensemble de tours non-attaquantes. C’est pourquoi on appelle

ρ(G, x) := ∑_{r=0}^{min(n,m)}(−1)^{r}p(G, r) · x^{n−r}

le polynôme des tours. Il est classique (voir le livre [28] de Riordan, chapitre 7.7) que ρ(\overline{G}, x) est complètement déterminé par ρ(G, x). Toutefois, aucune relation simple reliant ρ(\overline{G}, x) et ρ(G, x) n’a été imaginée jusqu’à présent. D’autre part, inspirés par la définition visionnaire du polynôme de recouvrement de Chung et Graham [12], Chow (et Gessel) [9] ont introduit le polynôme factoriel des tours comme étant

ρ!(G, z) := ∑_{r=0}^{min(n,m)} p(G, r) · z\underline{m−r},

où z\underline{k} := z(z−1) ⋯ (z−k+1). Nous l’appellerons, ci-après, polynôme de Chow. Il a déjà fait ses preuves dans l’étude des diagrammes de Ferrers (voir [15]), parce qu’il se factorise naturellement (voir [19] et [31], théorème 2.4.1). De plus, il satisfait une relation de dualité tout à fait remarquable

ρ!(\overline{G}, z) = (−1)^{m}ρ!(G, m − n − 1 − z),

imaginée par Chow (et Gessel) [9] dans le cas n = m. Outre cette généralisation, nous établissons la nouvelle formule

ρ!(\overline{G}, z) = \frac{1}{Γ(z + 1 + n − m)} ∫_{0}^{∞} x^{z} · e^{−x}ρ(G, x) · dx,

dont la spécialisation n = m et z = 0 fut trouvée par Joni, Rota et Zeilberger [21], puisque ρ!(\overline{G}, 0) compte le nombre des couplages parfaits de \overline{G} lorsque n = m. Ce résultat permet notamment d’interpréter des intégrales de produits de polynômes de Laguerre généralisés comme nombre de dérangements (voir [3], [4], [5], [14], [16], [18], [20], [29], [34]).

Suivant Godsil ([17], page 157), on peut, en effet, définir les polynômes de Laguerre comme des polynômes des tours des graphes bipartis complets K_{n,m} := (X, Y; X × Y) avec |X| = n et |Y | = m. Autrement dit, pour tout a ∈ ℕ, nous posons

Le_{n}^{(a)}(x) := ρ(K_{n,n+a}, x).

Comme ρ(K_{n,n+a} ⊎ K_{m+a,m}, x) = x^{a} · Le_{n}^{(a)}(x) · Le_{m}^{(a)}(x), l’identité de Joni, Rota et Zeilberger implique alors

ρ!(\overline{K_{n,n+a} ⊎ K_{m+a,m}}, 0) = ∫_{0}^{∞} Le_{n}^{(a)}(x) · Le_{m}^{(a)}(x) · x^{a}e^{−x}dx

E + \overline{E} = XY

(voir [18]), ce qui fournit notamment l’orthogonalité de nos polynômes Le_{n}^{(a)}(x) par rapport à x^{a}e^{−x}dx. Voilà pourquoi notre définition des polynômes de Laguerre Le_{n}^{(a)}(x) correspond bien à la définition classique. Notre normalisation, cependant, est choisie de façon que le premier coefficient, i. e. le coefficient de x^{n}, vaille 1.

Il nous semble également utile d’introduire les polynômes des tours symétriques (par rapport à la bipartition) en deux variables

\begin{aligned}ρ(G, x, y) & := ∑_{r=0}^{min(n,m)}(−1)^{r}p(G, r) · x^{n−r}y^{m−r} = y^{m−n} · ρ(G, xy), \\ \overline{ρ}(G, x, y) & := ∑_{r=0}^{min(n,m)} p(G, r) · x^{n−r}y^{m−r} = (−1)^{n}y^{m−n} · ρ(G, −xy), \end{aligned}

si G = (X, Y; E) est biparti avec |X| = n et |Y | = m. Pour ces polynômes, nous démontrons plusieurs théorèmes de dualité qui font intervenir des opérateurs différentiels. En particulier, nos identités nouvelles

ρ(\overline{G}, x, y) = e^{xy} · \overline{ρ}(G, −\frac{d}{dy} , −\frac{d}{dx}) · e^{−xy}
= (x/y)^{n−m} · ρ(\overline{G}, y, x)
= (x/y)^{n−m} · e^{xy} · \overline{ρ}(G, −\frac{d}{dx}, −\frac{d}{dy}) · e^{−xy}

impliquent

Le_{n}^{(m−n)}(x) = ρ(K_{n,m}, x, 1) = [e^{xy} · (−\frac{d}{dx})^{m}(−\frac{d}{dy})^{n} · e^{−xy}]_{y=1}
= e^{x} · (−\frac{d}{dx})^{m}[x^{n}e^{−x}]
= x^{n−m} · e^{x} · (−\frac{d}{dx})^{n}[x^{m}e^{−x}],

où la toute dernière identité est la formule de Rodrigues pour les polynômes de Laguerre généralisés. Dans le cas n = m, nous établissons également le théorème de dualité suivant pour le polynôme des tours lui-même :

\begin{aligned}ρ(\overline{G}, −x) & = (−1)^{n} · exp[\frac{d}{dx}x\frac{d}{dx}]ρ(G, x), \\ ρ(\overline{G}, x) & = (−1)^{n} · exp[−\frac{d}{dx}x\frac{d}{dx}]ρ(G, −x). \end{aligned}

Nous démontrons tous nos résultats à l’aide des fonctions génératrices pour les fonctions d’ensembles. Cette méthode algébrique permet, par excellence, d’automatiser l’utilisation de plusieurs méthodes classiques de la combinatoire énumérative et algébrique, et notamment l’utilisation du principe d’inclusion-exclusion et de l’inversion de Möbius sur l’ensemble partiellement ordonné des partitions d’un ensemble. L’algèbre des fonctions d’ensembles est introduite dans le paragraphe 2.

Dans le paragraphe 3, elle est appliquée pour le traitement du polynôme des tours et de sa parenté. Ceci fournit des démonstrations particulièrement courtes et explicatives et permet même de prolonger tous nos résultats à l’étude des permanents des matrices quelconques.

Pour des matrices carrées on obtient ainsi une preuve rapide d’une généralisation pondérée d’une identité fondamentale de Berge entre les chemins et les circuits hamiltoniens d’un graphe orienté simple G = (V, E), E ⊆ V × V, et ceux de son complément \overline{G} = (V, \overline{E}), \overline{E} = (V × V)\E. Appelons bi-chemin hamiltonien une partition de V en deux chemins hamiltoniens non-vides. Si cyc(G) désigne le nombre de circuits hamiltoniens de G, lin(G) le nombre de chemins hamiltoniens et bilin(G) le nombre de bi-chemins hamiltoniens, alors Berge a imaginé le théorème de dualité suivant :

lin(\overline{G}) ≡ lin(G) (mod 2), bilin(\overline{G}) ≡ bilin(G) (mod 2),
lin(\overline{G}) + bilin(\overline{G}) ≡ lin(G) + bilin(G) ≡ cyc(\overline{G}) + cyc(G) (mod 2)

(voir [7] ainsi que [6], chapitre 10, théorème 1 et exercice 9). La démonstration de Berge, cependant, contient un résultat nettement plus puissant que nous appelons identité de Berge. Exprimée dans le langage des fonctions d’ensembles, cette identité fondamentale prend toute sa force et implique immédiatement tous les résultats des paragraphes 4 et 5, et notamment la conjecture de Chung et Graham (établie d’abord par Chow et Gessel), l’identité de Foata et Zeilberger sur les polynômes de Laguerre, les théorèmes de parité de Rédei sur les tournois, de Lovász sur les graphes non-orientés et de Camion et Rao sur les graphes autocomplémentaires. Les démonstrations de ces résultats données par Berge, Camion, Chow, Foata, Gessel, Lovász, Moon, Rao, Szele et Zeilberger s’étendent parfois sur plusieurs pages (voir [8], [10], [16], [27], [33], [24], 5.19-20, [26], p. 21-23).

Dans le paragraphe 6, nous étudions les relations les plus importantes entre les fonctions d’ensembles et les fonctions symétriques. Nous généralisons plusieurs théorèmes de Stanley [30] et simplifions ses démonstrations. Finalement, nous montrons que le théorème principal de la thèse de Chow [11] est une conséquence directe de l’identité de Berge.

2. Outils algébriques

Soit V un ensemble fini et

\begin{matrix}f : 2^{V} & → A \\ V′ ⊆ V & ↦ f(V′) ∈ A \end{matrix}

une fonction d’ensembles, où A est un anneau commutatif (avec 1). Considérons la fonction génératrice

F_{f}(ν) := ∑_{V′⊆V} f(V′) · ν^{V′}, ν^{∅} := 1,

à joindre aux règles de calcul suivantes (V′, V′′ ⊆ V) :

ν^{V′} · ν^{V′′} := ν^{V′+V′′}, où

V′ + V′′ := \{ \begin{matrix}V′ ∪ V′′, & si V′ ∩ V′′ = ∅, \\ †, & si V′ ∩ V′′ ≠ ∅, où \end{matrix}

† + V′ := †, † + † := †,  et  ν† := 0.

L’algèbre A[V] de ces fonctions génératrices n’est pas une inconnue. En effet, on a l’isomorphisme

A[V] ≃ A[v_{1}, …, v_{n}]/⟨v_{1}^{2}, …, v_{n}^{2}⟩,

si V contient n éléments.

Exemple 2.1. Le produit fg de deux fonctions d’ensembles f, g est défini, pour tout V′ ⊆ V, par

(fg)(V′) := ∑_{V′=V′′⊎V′′′} f(V′′) · g(V′′′).

Il en résulte

F_{fg}(ν) = F_{f}(ν) · F_{g}(ν).

Pour |V | = ∞, soit F (V) l’ensemble partiellement ordonné des sous-ensembles finis de V. On a des projections canoniques p_{V′,V′′} : A[V′] → A[V′′] (V′, V′′ ∈ F (V), V′ ⊇ V′′) et l’on pose

A[V] := lim_{⟵} A[V′], V′ ∈ F (V)

pour travailler avec des fonctions génératrices de la forme

F_{f}(ν) = ∑_{V′∈F (V)} f(V′) · ν^{V′}.

Soit

V := ∑_{v∈V} ν^{{v}}

la fonction indicatrice des sous-ensembles de V de cardinalité 1 (l’usage double de V pour l’ensemble et pour un élément de A[V] ne pourra pas être à l’origine de confusions). En multipliant la fonction génératrice V plusieurs fois par ellemême, on voit que V^{n}/n! représente la fonction indicatrice des sous-ensembles de l’ensemble V de cardinalité n. L’identité

∑_{n=0}^{∞} f(n) · V^{n}/n! = ∑_{V′∈F (V)} f(|V′|) · ν^{V′}, f : ℕ → A,

fournit un plongement de l’anneau A![[V]] des fonctions génératrices de type exponentiel dans l’anneau A[V]. Ce plongement est à l’origine de (presque?) toutes les applications de A![[V]] en combinatoire, mais il nécessite l’existence d’un modèle combinatoire infini (qui ne fait intervenir que les cardinalités). Par conséquent, A[V] donne plus de flexibilité et permet un traitement algébrique, qui reflète parfaitement les opérations classiques de la combinatoire. Outre cela, A[V] est approprié, par excellence, aux calculs par ordinateur.

Remarque 2.1. L’anneau ℤ![[V]] n’est pas noethérien, mais il contient des fonctions importantes comme exp(V) et log(1 + V).

Exemple 2.2. Si char A = 2, on a

(1 + V)^{−1} = ∑_{n=0}^{∞}(−1)^{n}n! · V^{n}/n!
≡ 1 + V et
log(1 + V) = ∑_{n=1}^{∞}(−1)^{n−1}(n − 1)! · V^{n}/n!
≡ V + V^{2}/2

dans l’anneau A![[V]]. Ces identités sont à l’origine de maints résultats de parité en combinatoire.

Pour tout t ∈ A posons (t · ν)^{V′} := t^{|V′|} · ν^{V′}, V′ ⊆ V, et, par conséquent,

F_{f}(tν) = ∑_{∅⊆V′⊆V} f(V′) t^{|V′|} ν^{V′}.

Il est évident que cette définition est compatible avec l’addition et la multiplication. Les cas particuliers les plus importants sont t = −1 et t = 0: F_{f}(0) = F_{f}(0 · ν) = f(∅).

Si F_{f}(0) = 0, alors F_{f}(ν)^{n}/n! est défini pour n’importe quel anneau A, parce qu’une partition en n sous-ensembles non-vides peut être ordonnée de n! manières différentes. Voilà pourquoi A![[V]] opère sur A[V] par la substitution G(F_{f}(ν)) définie pour tout G ∈ A![[V]].

Finalement, on utilise les dérivées ∂^{v} pour tout v ∈ V définies par

∂^{v}ν^{V′} := \{ \begin{matrix}ν^{V′}, & si v ∈ V′, \\ 0, & sinon. \end{matrix}

La formule de dérivation d’un produit

∂^{v}[F_{f}(ν) · F_{g}(ν)] = (∂^{v}F_{f}(ν)) · F_{g}(ν) + F_{f}(ν) · (∂^{v}F_{g}(ν))

est l’analogue algébrique du fait ensembliste le plus fondamental:

v ∈ V′ ⊎ V′′  ⇔  v ∈ V′ ou v ∈ V′′.

La formule

∂^{v}[G(F_{f}(ν))] = G′(F_{f}(ν)) · ∂^{v}F_{f}(ν), G ∈ A![[V]],

en découle immédiatement.

Remarque 2.2. L’isomorphisme A[V] ≃ A[v_{1}, …, v_{n}]/⟨v_{1}^{2}, …, v_{n}^{2}⟩ ne fait pas correspondre ∂^{v} à ∂/∂v_{i}, mais à v_{i}∂/∂v_{i}. La dérivée partielle ∂/∂v_{i} n’a point d’analogue dans A[V].

Exemple 2.3.

a) Étant données f, g : 2^{V} → A, alors l’équivalence suivante n’est rien d’autre que le principe d’inclusion-exclusion :

F_{g}(ν) = exp[V] · F_{f}(ν) ⇔ F_{f}(ν) = exp[−V] · F_{g}(ν).

b) Étant données f, g : 2^{V} → A avec f(∅) = g(∅) = 0, l’équivalence

1 + F_{g}(ν) = exp[F_{f}(ν)] ⇔ F_{f}(ν) = log[1 + F_{g}(ν)]

s’écrit sous la forme

\begin{aligned}g(V′) & = ∑_{V′=B_{1}⊎...⊎B_{k}} f(B_{1}) ⋯ f(B_{k}) ∀ V′ ⊆ V  ⇔ \\ f(V′) & = ∑_{V′=B_{1}⊎...⊎B_{k}}(−1)^{k−1}(k − 1)! · g(B_{1}) ⋯ g(B_{k}) ∀ V′ ⊆ V \end{aligned}

et n’est rien d’autre que l’inversion de Möbius pour des fonctions multiplicatives généralisées sur l’ensemble partiellement ordonné des partitions de V (voir [1], chapitre V.1.C ou [13], chapitre 5.2). Par ailleurs, on peut se servir de ∂^{v} pour obtenir le résultat dérivé

[1 + F_{g}(ν)] · ∂^{v}F_{f}(ν) = ∂^{v}F_{g}(ν),

qui, par suite de la profusion de méthodes inductives ou récursives, est souvent beaucoup plus connu que le résultat ^{⟨⟨} pur^{⟩⟩}. En outre, ce résultat dérivé a l’avantage de n’utiliser qu’un seul produit, permettant des calculs par ordinateur particulièrement rapides.

3. Le polynôme des tours et sa parenté

Soit G = (X, Y; E) un graphe biparti simple et soit \overline{G} = (X, Y; \overline{E}) son complément biparti. Posons V := X ⊎ Y et définissons X, Y, E, \overline{E} ∈ A[V] par

X := ∑_{x∈X} ν^{\{x\}}, Y := ∑_{y∈Y} ν^{\{y\}}, E := ∑_{e∈E} ν^{e}, \overline{E} := ∑_{e∈\overline{E}} ν^{e},

où chaque arête e ∈ E (resp. e ∈ \overline{E}) est considérée comme un sous-ensemble de V de cardinalité deux. La définition du complément biparti implique alors l’identité suivante, qui est à l’origine de tous les résultats de cet article.

Lemme fondamental. Dans l’algèbre A[V] = A[X ⊎ Y], on a

E + \overline{E} = XY.

Pour ∅ ⊆ X′ ⊆ X et ∅ ⊆ Y′ ⊆ Y, notons G[X′, Y′] le sous-graphe de G engendré par X′ ∪ Y′ (c’est le graphe dont les sommets sont les éléments de X′ ∪ Y′ et dont les arêtes sont les arêtes de G ayant leurs deux extrémités dans X′ ∪ Y′). Alors exp[E] compte, pour chaque X′ ⊆ X et Y′ ⊆ Y, le nombre des couplages parfaits de G[X′, Y′]. Voilà pourquoi la proposition suivante est une conséquence immédiate des définitions du polynôme des tours et de sa parenté (voir l’introduction).

Proposition 3.1. On a

∑_{X′⊆X} ∑_{Y′⊆Y} ρ!(G[X′, Y′], z) · ν^{X′∪Y′} = exp[E] · ∑_{i=0}^{∞} ∑_{j=0}^{∞} \frac{X^{i}}{i!} · \frac{Y^{j}}{j!} · z\underline{j}
= exp[E] · exp[X] · (1 + Y)^{z} et
∑_{X′⊆X} ∑_{Y′⊆Y} ρ(G[X′, Y′], x) · ν^{X′∪Y′} = exp[−E] · exp[xX] · exp[Y],
∑_{X′⊆X} ∑_{Y′⊆Y} ρ(G[X′, Y′], x, y) · ν^{X′∪Y′} = exp[−E] · exp[xX] · exp[yY],
∑_{X′⊆X} ∑_{Y′⊆Y} \overline{ρ}(G[X′, Y′], x, y) · ν^{X′∪Y′} = exp[E] · exp[xX] · exp[yY].

Il est classique que ρ(\overline{G}, x) est complètement déterminé par ρ(G, x), un résultat que Riordan [28], chapitre 7.7, démontra à l’aide de la proposition suivante.

Proposition 3.2. Soit G = (X, Y; E) un graphe biparti simple avec |X| = n et |Y | = m. Alors on a pour le polynôme des tours du graphe biparti complémentaire \overline{G} = (X, Y; \overline{E}) l’identité

ρ(\overline{G}, x) = ∑_{r=0}^{min(n,m)} p(G, r) · ρ(K_{n−r,m−r}, x).

Démonstration. En utilisant l’algèbre A[V] = A[X ⊎ Y], on a

∑_{i=0}^{∞} ∑_{j=0}^{∞} ρ(K_{i,j}, x) · \frac{X^{i}}{i!} · \frac{Y^{j}}{j!} = exp[xX + Y − XY].

Par conséquent, l’identité suivante implique bien notre proposition :

exp[xX + Y − \overline{E}] = exp[xX + Y − XY + E] = exp[E] · exp[xX + Y − XY].

Pour les polynômes des tours symétriques, nous pouvons établir des théorèmes de dualité apparemment nouveaux.

Théorème 3.1. Pour tout graphe biparti simple G = (X, Y; E), on a

\begin{aligned}\overline{ρ}(\overline{G}, x, y) & = e^{−xy} · ρ(G, \frac{d}{dy} , \frac{d}{dx}) · e^{xy}, \\ ρ(\overline{G}, x, y) & = e^{xy} · \overline{ρ}(G, −\frac{d}{dy} , −\frac{d}{dx}) · e^{−xy}. \end{aligned}

Démonstration. D’après le théorème de Taylor formel on a

f(x + a, y + b) = exp[\frac{d}{dx}a + \frac{d}{dy} b] · f(x, y)

pour des variables x, y, a, b et une série formelle f. Il s’ensuit

exp[−xy] · exp[\frac{d}{dy} X + \frac{d}{dx}Y − E] · exp[xy]
= exp[−xy] · exp[−E] · exp[\frac{d}{dx}Y + \frac{d}{dy} X] · exp[xy]
= exp[−xy] · exp[−E] · exp[(x + Y)(y + X)]
= exp[xX + yY + \overline{E}].

La deuxième égalité est démontrée de la même façon.

Comme [(\frac{d}{dx} \frac{d}{dy})^{i}(xy)^{j}]_{y=1} = (\frac{d}{dx}x\frac{d}{dx})^{i}x^{j} pour tout i, j ∈ ℕ, nous obtenons le corollaire suivant pour le polynôme des tours lui-même.

Corollaire 3.1. Soit G = (X, Y; E) un graphe biparti simple tel que |X| = |Y | = n. Alors on a pour le polynôme des tours de \overline{G} = (X, Y; \overline{E}) les identités

\begin{aligned}ρ(\overline{G}, −x) & = (−1)^{n} · e^{−x}ρ(G, \frac{d}{dx}x\frac{d}{dx})e^{x}, \\ ρ(\overline{G}, x) & = (−1)^{n} · e^{x}ρ(G, −\frac{d}{dx}x\frac{d}{dx})e^{−x}. \end{aligned}

Au lieu de reproduire des généralisations du corollaire précédent au cas |X| ≠ |Y | (qui sont moins belles), nous préférons donner une autre forme des théorèmes de dualité faisant intervenir des opérateurs différentiels.

Théorème 3.2. Pour tout graphe biparti simple G = (X, Y; E), on a

\begin{aligned}\overline{ρ}(\overline{G}, x, y) & = exp[\frac{d}{dx} \frac{d}{dy} ] · ρ(G, x, y), \\ ρ(\overline{G}, x, y) & = exp[−\frac{d}{dx} \frac{d}{dy} ] · \overline{ρ}(G, x, y). \end{aligned}

Démonstration. Puisque \frac{d}{dx} \frac{d}{dy} exp[xX + yY − E] = XY · exp[xX + yY − E], nous avons

exp[xX + yY + \overline{E}] = exp[XY] · exp[xX + yY − E]
= exp[\frac{d}{dx} \frac{d}{dy} ] · exp[xX + yY − E].

L’opérateur différentiel exp[−\frac{d}{dx} \frac{d}{dy} ] est l’inverse de exp[\frac{d}{dx} \frac{d}{dy} ].

Le corollaire 3.2 se déduit du théorème 3.2 de la même façon que le corollaire 3.1 se déduit du théorème 3.1.

Corollaire 3.2. Soit G = (X, Y; E) un graphe biparti simple tel que |X| = |Y | = n. Alors on a pour le polynôme des tours de \overline{G} = (X, Y; \overline{E}) les identités

\begin{aligned}ρ(\overline{G}, −x) & = (−1)^{n} · exp[\frac{d}{dx}x\frac{d}{dx}]ρ(G, x), \\ ρ(\overline{G}, x) & = (−1)^{n} · exp[−\frac{d}{dx}x\frac{d}{dx}]ρ(G, −x). \end{aligned}

Terminons ce paragraphe avec le théorème de dualité pour le polynôme de Chow dont nous avons mentionné les spécialisations classiques dans l’introduction.

Théorème 3.3. Soit G = (X, Y; E) un graphe biparti simple avec |X| = n et |Y | = m. Alors on a

\begin{aligned}ρ!(\overline{G}, z) & = (−1)^{m}ρ!(G, m − n − 1 − z) \\ & = \frac{1}{Γ(z + 1 + n − m)} ∫_{0}^{∞} x^{z} · e^{−x}ρ(G, x) · dx. \end{aligned}

Démonstration. La proposition 3.1 permet d’exprimer la première identité dans le langage des fonctions d’ensembles. En fait, pour représenter le facteur (−1)^{m}, il suffit de multiplier chaque élément de Y (et de E) par −1. Autrement dit, il faut démontrer

exp[\overline{E}] ∑_{i=0}^{∞} ∑_{j=0}^{∞} \frac{X^{i}}{i!} \frac{Y^{j}}{j!} z\underline{j} = exp[−E] ∑_{i=0}^{∞} ∑_{j=0}^{∞} \frac{X^{i}}{i!} \frac{(−Y)^{j}}{j!} (j − i − 1 − z)\underline{j}

⇔ exp[\overline{E}] ∑_{i=0}^{∞} ∑_{j=0}^{∞} \frac{X^{i}}{i!} Y^{j}\binom{z}{j} = exp[−E] ∑_{i=0}^{∞} ∑_{j=0}^{∞} \frac{X^{i}}{i!} Y^{j}\binom{i + z}{j}

⇔ exp[\overline{E}] ∑_{i=0}^{∞} \frac{X^{i}}{i!} (1 + Y)^{z} = exp[−E] ∑_{i=0}^{∞} \frac{X^{i}}{i!} (1 + Y)^{i+z}
⇔ exp[E + \overline{E}] exp[X] = exp[X(1 + Y)].

Pour établir l’identité

(−1)^{m}ρ!(G, m − n − 1 − z) = \frac{1}{Γ(z + 1 + n − m)} ∫_{0}^{∞} e^{−x} · x^{z}ρ(G, x) · dx,

il suffit de constater que le coefficient de p(G, r) (voir l’introduction) dans le membre de gauche et dans le membre de droite vaut

\begin{aligned}(−1)^{m}(m − n − 1 − z)\underline{m−r} & = (−1)^{r}(z + n − r)\underline{m−r} = (−1)^{r} \frac{Γ(z + 1 + n − r)}{Γ(z + 1 + n − m)} \\ & = \frac{1}{Γ(z + 1 + n − m)} ∫_{0}^{∞} e^{−x} · x^{z}(−1)^{r}x^{n−r} · dx. \end{aligned}

Remarque 3.1. Dans le sens de Gessel et Stanley, il faudrait également étudier les fonctions génératrices des suites de nombres ρ!(G, z), z ∈ ℤ, une étude que nous ne reproduisons pas ici.

Remarque 3.2. Pour plusieurs applications (voir [3], [4], [5] et [16], par exemple), il est indispensable de prolonger nos résultats aux graphes bipartis pondérés G_{w} = (X, Y; E, w), où w : X ⊎ Y → A (resp. E : X × Y → A) est une fonction attachant un poids à chaque sommet (resp. arête) du graphe. Par définition, {x, y} est une arête de G_{w} si et seulement si E({x, y}) ≠ 0, de sorte qu’un graphe biparti simple est un graphe biparti pondéré tel que w(x) = w(y) = 1 et E({x, y}) ∈ {0, 1} pour tout x ∈ X et y ∈ Y.

Le complément pondéré \overline{G_{w}} = (X, Y; \overline{E}, w) du graphe G_{w} = (X, Y; E, w) est défini par

E(\{x, y\}) + \overline{E}(\{x, y\}) = w(x) · w(y)

pour tout x ∈ X et y ∈ Y. En posant

\begin{matrix}X := ∑_{x∈X} w(x) · ν^{\{x\}}, & Y := ∑_{y∈Y} w(y) · ν^{\{y\}}, \\ E := ∑_{x∈X} ∑_{y∈Y} E(\{x, y\}) · ν^{\{x,y\}}, & \overline{E} := ∑_{x∈X} ∑_{y∈Y} \overline{E}(\{x, y\}) · ν^{\{x,y\}}, \end{matrix}

notre lemme fondamental

E + \overline{E} = XY

reste alors valable.

Un r-couplage de G_{w}, finalement, est un recouvrement de tous les n sommets de X et de tous les m sommets de Y par r arêtes non-adjacentes, n − r sommets de X et m − r sommets de Y. Le poids du r-couplage est égal au produit des poids de ses r arêtes, ses n − r sommets de X et ses m − r sommets de Y.

Notons p(G_{w}, r) la somme des poids de tous les r-couplages de G_{w}, p(G_{w}, 0) = [∏_{x∈X} w(x)] · [∏_{y∈Y} w(y)]. De cette manière, la proposition 3.1 ainsi que tous les autres résultats de ce paragraphe restent effectivement valables pour les graphes bipartis pondérés. Autrement dit, nous avons établi des théorèmes de dualité pour les permanents des matrices de dimensions n × m.

4. Chemins et circuits hamiltoniens

Supposons dorénavant que |X| = |Y | = n et fixons une bijection entre X et Y. Ceci nous permet d’identifier le graphe biparti simple G = (X, Y; E), E ⊆ X × Y, à un graphe orienté simple G = (V, E) avec |V | = n et E ⊆ V × V.

[figure: graphe orienté :; •; •; •; •; •; graphe biparti :; •; •; •; •; •; •; •; •; •; •]

Notons que V n’est plus égal à X ⊎Y à partir de ce paragraphe. La définition du graphe biparti complémentaire fournit une définition naturelle du graphe orienté complémentaire, à savoir \overline{G} = (V, \overline{E}), où \overline{E} = (V × V)\E. En particulier, G contient une boucle autour de v ∈ V si et seulement si \overline{G} n’a pas de boucle autour de v. Un r-couplage du graphe biparti, finalement, n’est rien d’autre qu’une partition de V en plusieurs circuits hamiltoniens et n−r chemins hamiltoniens du graphe orienté, de sorte que tous les résultats du paragraphe précédent peuvent être interprétés dans le langage des graphes orientés.

Pour tout ∅ ⊂ V′ ⊆ V, notons G[V′] le sous-graphe du graphe orienté G = (V, E) qui est engendré par V′ (c’est le graphe dont les sommets sont les éléments de V′ et dont les arcs sont les arcs de G ayant leurs deux extrémités dans V′). Soit cyc(G[V′]) le nombre de circuits hamiltoniens de G[V′] et soit lin(G[V′]) le nombre de chemins hamiltoniens de G[V′], où un seul sommet v ∈ V est un chemin hamiltonien de G[{v}] dont v est à la fois le sommet initial et le sommet terminal, alors qu’une boucle autour de v est bien un circuit hamiltonien de G[{v}]. Les deux éléments

cyc_{G}(ν) := ∑_{∅⊂V′⊆V} cyc(G[V′]) · ν^{V′}, lin_{G}(ν) := ∑_{∅⊂V′⊆V} lin(G[V′]) · ν^{V′}

de l’algèbre A[V], |V | = n, sont au centre du reste de cet article. En fait, si l’on pose n = m et z = 0 dans la première identité du théorème 3.3, alors le membre de gauche de cette identité est égal au coefficient de ν^{V} dans exp[cyc\overline{G}(ν)], tandis que le membre de droite est égal au coefficient de ν^{V} de la fonction d’ensembles exp[cyc_{G}(−ν)] · [1 + lin_{G}(−ν)]^{−1}. Autrement dit, notre théorème 3.3 implique la relation

exp[cyc\overline{G}(ν)] = exp[cyc_{G}(−ν)] · [1 + lin_{G}(−ν)]^{−1},

imaginée par Berge [7] sans utiliser les fonctions d’ensembles. En intervertissant les rôles de G et \overline{G}, nous obtenons le théorème suivant, qui est à l’origine de tous les résultats des paragraphes 4 et 5.

Théorème 4.1. (Identité de Berge) Soit G = (V, E) un graphe orienté simple. Alors on a

1 + lin\overline{G}(ν) = [1 + lin_{G}(−ν)]^{−1} = exp[cyc\overline{G}(ν) − cyc_{G}(−ν)],
log[1 + lin\overline{G}(ν)] = − log[1 + lin_{G}(−ν)] = cyc\overline{G}(ν) − cyc_{G}(−ν) et

[1+lin_{G}(−ν)]·∂^{v}lin\overline{G}(ν) = −[1+lin\overline{G}(ν)]·∂^{v}lin_{G}(−ν) = ∂^{v}[cyc\overline{G}(ν)−cyc_{G}(−ν)]

pour chaque sommet v ∈ V.

Remarque 4.1. Pour des applications futures, il est indispensable de prolonger nos résultats aux graphes orientés pondérés G_{it} = (V, E, i, t), où i, t : V → A et E : V × V → A sont des fonctions attachant des poids à chaque sommet et arc, respectivement. Par définition, (u, v) est un arc de G_{it} si et seulement si E((u, v)) ≠ 0, de sorte qu’un graphe orienté simple est un graphe orienté pondéré tel que i(v) = t(v) = 1 et E((u, v)) ∈ {0, 1} pour tout u, v ∈ V. Le complément pondéré \overline{G_{it}} = (V, \overline{E}, i, t) du graphe G_{it} = (V, E, i, t) est défini par

E((u, v)) + \overline{E}((u, v)) = i(u) · t(v)

pour tout u, v ∈ V. Finalement, le poids d’un circuit hamiltonien est égal au produit des poids de ses arcs, tandis que le poids d’un chemin hamiltonien est égal au produit des poids de ses arcs multiplié par t(u)·i(v) si u (resp. v) est le sommet initial (resp. terminal) du chemin.

Pour tout ∅ ⊂ V′ ⊆ V, notons cyc(G_{it}[V′]) (resp. lin(G_{it}[V′])) la somme des poids de tous les circuits (resp. chemins) hamiltoniens de G_{it}[V′]. Avec ces définitions, notre remarque 3.2 permet de conclure que le théorème 4.1 reste valable pour les graphes orientés pondérés. Autrement dit, nous avons établi un théorème de dualité pour les matrices carrées de dimension n×n. En fait, la diagonale principale d’une matrice carrée fournit une bijection canonique entre l’ensemble des lignes et l’ensemble des colonnes (voir le début de ce paragraphe). Remarquons finalement que les autres résultats des paragraphes 4 et 5 peuvent également être prolongés au cas pondéré. Nous laissons au lecteur le soin d’expliciter ceci.

Grâce à notre exemple 2.2, on peut simplifier le théorème 4.1 sensiblement en le considérant modulo 2 :

1 + lin\overline{G}(ν) ≡ 1 + lin_{G}(ν) (mod 2),
lin\overline{G}(ν) + lin\overline{G}(ν)^{2}/2 ≡ lin_{G}(ν) + lin_{G}(ν)^{2}/2 ≡ cyc\overline{G}(ν) + cyc_{G}(ν) (mod 2).

Puisque le coefficient de ν^{V} dans lin_{G}(ν)^{2}/2 compte le nombre de bi-chemins hamiltoniens de G = (V, E) (voir l’introduction), nous avons établi le résultat principal de l’article [7] de Berge (voir [6], chapitre 10, théorème 1 et exercice 9).

Corollaire 4.1. (Berge) Pour tout graphe orienté simple G = (V, E), on a

lin(\overline{G}) ≡ lin(G) (mod 2), bilin(\overline{G}) ≡ bilin(G) (mod 2),

lin(\overline{G}) + bilin(\overline{G}) ≡ lin(G) + bilin(G) ≡ cyc(\overline{G}) + cyc(G) (mod 2).

Soit G = (V, E) un graphe orienté simple. Chung et Graham [12] (resp. D’Antona et Munarini [2]) ont introduit et étudié le polynôme C!(G, x, y) (resp. C(G, x, z)) appelé polynôme de recouvrement (resp. polynôme de recouvrement géométrique). À l’aide des fonctions d’ensembles, on peut définir ces polynômes comme suit :

1 + ∑_{∅⊂V′⊆V} C!(G[V′], x, y) · ν^{V′} := exp[x · cyc_{G}(ν)] · [1 + lin_{G}(ν)]^{y},

1 + ∑_{∅⊂V′⊆V} C(G[V′], x, z) · ν^{V′} := exp[x · cyc_{G}(ν)] · exp[z · lin_{G}(ν)].

Il est évident que nos définitions sont équivalentes à celles proposées par Chung et Graham [12], D’Antona et Munarini [2] et Chow [10]. Chung et Graham ont posé la question de savoir si C!(\overline{G}, x, y) est déterminé par C!(G, x, y). Une réponse affirmative fut trouvée par Chow (et Gessel) [10], qui ont établi une belle relation entre les deux polynômes, soulignant davantage le caractère visionnaire de la définition de Chung et Graham. Nous montrons que la relation imaginée par Chow (et Gessel) ainsi que notre relation entre C!(\overline{G}, x, y) et C(G, x, z) sont des corollaires directs de l’identité de Berge. Les différentes démonstrations de Chow et Gessel [10] sont toutes plus longues.

Théorème 4.2. Soit G = (V, E) un graphe orienté simple avec |V | = n. Alors on a

\begin{aligned}C!(\overline{G}, x, y) & = (−1)^{n}C!(G, x, −x − y) \\ & = \frac{(−1)^{n}}{Γ(x + y)} ∫_{0}^{∞} e^{−z} · C(G, x, −z) · z^{x+y} · \frac{dz}{z} . \end{aligned}

Démonstration. Dans le langage des fonctions d’ensembles, la première identité du corollaire s’exprime comme suit :

exp[x · cyc\overline{G}(ν)] · [1 + lin\overline{G}(ν)]^{y} = exp[x · cyc_{G}(−ν)] · [1 + lin_{G}(−ν)]^{−x−y}
⇔ (exp[cyc\overline{G}(ν) − cyc_{G}(−ν)])^{x} = [1 + lin_{G}(−ν)]^{−x}.

La seconde identité se vérifie de la façon suivante :

\frac{1}{Γ(x + y)} ∫_{0}^{∞} e^{−z} · exp[x · cyc_{G}(−ν)] · exp[−z · lin_{G}(−ν)] · z^{x+y−1} · dz

= exp[x · cyc_{G}(−ν)] · \frac{1}{Γ(x + y)} ∫_{0}^{∞} exp(−z[1 + lin_{G}(−ν)]) · z^{x+y−1} · dz

= exp[x · cyc_{G}(−ν)] · \frac{1}{Γ(x + y)} ∫_{0}^{∞} e^{−t} · (\frac{t}{1 + lin_{G}(−ν)})^{x+y−1} · \frac{dt}{1 + lin_{G}(−ν)}

= exp[x · cyc_{G}(−ν)] · [1 + lin_{G}(−ν)]^{−x−y} · \frac{1}{Γ(x + y)} ∫_{0}^{∞} e^{−t} · t^{x+y−1} · dt

= exp[x · cyc_{G}(−ν)] · [1 + lin_{G}(−ν)]^{−x−y}.

Remarque 4.2. Évidemment, le théorème 4.1 est aussi une conséquence immédiate du théorème 4.2. Le théorème 4.1, cependant, est bien le chaînon essentiel entre l’algèbre et la combinatoire.

Pour tout n ∈ ℕ, n ≥ 1, soit K_{n} le graphe orienté complet avec n sommets. Évidemment, son complément ne contient aucun arc, et l’on a cyc(K_{n}) = (n − 1)! et lin(K_{n}) = n!. Définissons le graphe infini complet K_{∞} dans le sens du paragraphe 2 pour obtenir les identités

cyc_{K_{∞}}(ν) = ∑_{n=1}^{∞} cyc(K_{n}) · V^{n}/n! = − log(1 − V),

lin_{K_{∞}}(ν) = ∑_{n=1}^{∞} lin(K_{n}) · V^{n}/n! = \frac{V}{1 − V} .

Les polynômes de Laguerre généralisés Le_{n}^{(α)}(z) furent introduits dans l’introduction pour α ∈ ℕ. La proposition suivante est facile à établir pour eux (voir notre relation entre graphes bipartis et graphes orientés). De plus, elle nous servira de définition des polynômes de Laguerre pour α ∉ ℕ. L’orthogonalité par rapport à z^{α}e^{−z}dz des polynômes Le_{n}^{(α)}(z) ainsi définis sera une conséquence immédiate de notre corollaire 4.2.

Proposition 4.1. On a

1 + ∑_{n=1}^{∞} Le_{n}^{(α)}(z) · V^{n}/n! = (1 + V)^{−α−1} · exp[\frac{z · V}{1 + V} ]

= exp[(α + 1) · cyc_{K_{∞}}(−ν)] · exp[−z · lin_{K_{∞}}(−ν)].

Autrement dit, Le_{n}^{(α)}(z) = (−1)^{n} · C(K_{n}, α + 1, −z).

Soit K_{n_{1}} ⊎…⊎K_{n_{k}} l’union disjointe des graphes complets K_{n_{1}}, …, K_{n_{k}} de sorte que l’on a l’identité évidente

Le_{n_{1}}^{(α)}(z) ⋯ Le_{n_{k}}^{(α)}(z) = (−1)^{n_{1}+...+n_{k}} · C(K_{n_{1}} ⊎ … ⊎ K_{n_{k}}, α + 1, −z).

Le théorème 4.2 implique donc le corollaire suivant.

Corollaire 4.2. On a

\begin{matrix}C!(\overline{K_{n_{1}} ⊎ … ⊎ K_{n_{k}}}, α + 1, β) \\ = \frac{1}{Γ(α + β + 1)} ∫_{0}^{∞} e^{−z} · (∏_{h=1}^{k} Le_{n_{h}}^{(α)}(z)) · z^{α+β} · dz. \end{matrix}

Le cas le plus important du corollaire précédent, à savoir β = 0, fut imaginé par Foata et Zeilberger [16, théorème 1]. Si, de plus, on pose k = 2, alors on obtient l’orthogonalité par rapport à z^{α}e^{−z}dz pour nos polynômes Le_{n}^{(α)}(z) définis à l’aide de la proposition 4.1. Ceci montre qu’ils s’agit bien des polynômes de Laguerre (généralisés) classiques.

Remarque 4.3. Dans le sens de la remarque 4.1, choisissons des poids λ_{1}, …, λ_{k} et définissons le graphe orienté pondéré (K_{n_{1}} ⊎ … ⊎ K_{n_{k}})_{it} en posant i(v) := λ_{h} si et seulement si v est un sommet de K_{n_{h}}, alors que tous les autres poids sont conservés, i. e. t(v) = 1 pour chaque sommet, par exemple. De cette manière, on a

Le_{n_{1}}^{(α)}(λ_{1}z) ⋯ Le_{n_{k}}^{(α)}(λ_{k}z) = (−1)^{n_{1}+...+n_{k}} · C((K_{n_{1}} ⊎ … ⊎ K_{n_{k}})_{it}, α + 1, −z) et le cas β = 0 de l’identité

\begin{matrix}C!(\overline{(K_{n_{1}} ⊎ … ⊎ K_{n_{k}})_{it}}, α + 1, β) \\ = \frac{1}{Γ(α + β + 1)} ∫_{0}^{∞} e^{−z} · (∏_{h=1}^{k} Le_{n_{h}}^{(α)}(λ_{h}z)) · z^{α+β} · dz \end{matrix}

n’est rien d’autre que le théorème 2 de [16], c’est-à-dire le théorème principal de cet article de Foata et Zeilberger.

5. Tournois et graphes non-orientés

Un tournoi G = (V, E) est un graphe orienté simple sans boucles et tel que pour deux sommets distincts u, v ∈ V on ait toujours exactement l’une des relations (u, v) ∈ E ou bien (v, u) ∈ E. Si G = (V, E) est un tournoi, alors chaque sommet de \overline{G} contient une boucle et l’on a lin\overline{G}(ν) = lin_{G}(ν) ainsi que cyc\overline{G}(ν) = V + cyc_{G}(ν). Voilà pourquoi le théorème 4.1 implique le résultat suivant.

Théorème 5.1. Pour chaque tournoi G = (V, E), on a

1 + lin_{G}(ν) = [1 + lin_{G}(−ν)]^{−1} = exp[V] · exp[cyc_{G}(ν) − cyc_{G}(−ν)] et

log[1 + lin_{G}(ν)] = − log[1 + lin_{G}(−ν)] = V + cyc_{G}(ν) − cyc_{G}(−ν).

Grâce à notre exemple 2.2, on peut simplifier le théorème précédent sensiblement en le considérant modulo 2 :

1 + lin_{G}(ν) ≡ exp[V] (mod 2), lin_{G}(ν) + lin_{G}(ν)^{2}/2 ≡ V (mod 2).

On n’obtient ainsi rien d’autre que les théorèmes classiques de Rédei et de Berge, formulés dans le langage des fonctions d’ensembles (voir [6], chapitre 10, théorème 6 et exercice 9). La démonstration du théorème de Rédei imaginée par Berge est plus longue, bien qu’elle simplifie déjà considérablement les preuves classiques (voir [33], [26], p. 21-23).

Corollaire 5.1. (Rédei, Berge) Pour chaque tournoi G = (V, E) tel que |V | > 1, on a lin(G) ≡ bilin(G) ≡ 1 (mod 2).

Finalement, soit E ⊎ \overline{E} = \binom{V}{2} une partition de la famille des sous-ensembles de cardinalité 2 de l’ensemble V, et soient G = (V, E) et \overline{G} = (V, \overline{E}) deux graphes simples non-orientés qui sont complémentaires. Pour tout ∅ ⊂ V′ ⊆ V, notons G[V′] le sous-graphe de G engendré par V′ (c’est le graphe dont les sommets sont les éléments de V′ et dont les arêtes sont les arêtes de G ayant leurs deux extrémités dans V′). Soit hc(G[V′]) (resp. hp(G[V′])) le nombre de circuits (resp. chemins) hamiltoniens de G[V′], où hc(G[V′]) := 0 (resp. hp(G[V′]) := 0) si |V′| < 3 (resp. |V′| < 2). Posons

HC_{G}(ν) := ∑_{∅⊂V′⊆V} hc(G[V′]) · ν^{V′}, HP_{G}(ν) := ∑_{∅⊂V′⊆V} hp(G[V′]) · ν^{V′}

ainsi que E := ∑_{e∈E} ν^{e} et \overline{E} := ∑_{e∈\overline{E}} ν^{e} de sorte que E + \overline{E} = V^{2}/2 dans l’algèbre A[V].

Suivant la suggestion de Berge (voir [6], préface), remplaçons chaque arête de G et de \overline{G} par deux arcs d’orientations opposées et munissons chaque sommet de \overline{G} d’une boucle pour obtenir deux graphes simples orientés qui sont complémentaires. Tout circuit (resp. chemin) hamiltonien non-orienté conduit à deux circuits (resp. chemins) hamiltoniens orientés. De plus, une arête non-orienté (resp. un sommet) conduit à un circuit (resp. chemin) hamiltonien orienté. Par conséquent, le théorème 4.1 fournit le résultat suivant.

Théorème 5.2. Soient G = (V, E) et \overline{G} = (V, \overline{E}) deux graphes simples nonorientés qui sont complémentaires. Alors on a

1 + V + 2HP\overline{G}(ν) = [1 − V + 2HP_{G}(−ν)]^{−1}
= exp[V + \overline{E} + 2HC\overline{G}(ν) − E − 2HC_{G}(−ν)],
log[1 + V + 2HP\overline{G}(ν)] = − log[1 − V + 2HP_{G}(−ν)]
= V + \overline{E} − E + 2[HC\overline{G}(ν) − HC_{G}(−ν)].

Pour obtenir des relations plus simples modulo 2, commençons par développer la fonction exponentielle dans le théorème précédent modulo 4 :

exp[V + \overline{E} + 2HC\overline{G}(ν) − E − 2HC_{G}(−ν)]
≡ exp[log(1 + V) + 2(\overline{E} + HC\overline{G}(ν) + HC_{G}(ν) + V^{3}/3! + V^{4}/4!)]
≡ [1 + V ][1 + 2(\overline{E} + HC\overline{G}(ν) + HC_{G}(ν) + V^{3}/3! + V^{4}/4!)] (mod 4).

On en tire le corollaire suivant.

Corollaire 5.2. Pour tout graphe simple non-orienté G = (V, E), on a

HP\overline{G}(ν) + \overline{E}(1 + V) ≡ HP_{G}(ν) + E(1 + V)

≡ [HC\overline{G}(ν) + HC_{G}(ν)][1 + V ] + V^{3}/3! + V^{4}/4! + V^{5}/5! (mod 2).

Un chemin (resp. circuit) de G = (V, E) (|V | = n) est dit élémentaire s’il ne rencontre pas deux fois le même sommet. Notons hp_{k}(G) (resp. hc_{k}(G)) le nombre de chemins (resp. circuits) élémentaires de k sommets, k ≥ 3. En particulier, hp_{n}(G) = hp(G) (resp. hc_{n}(G) = hc(G)) dénombre les chemins (resp. circuits) hamiltoniens de G, et l’on a

hp_{k}(G) = ∑_{V′∈\binom{V}{k}} hp(G[V′]), hc_{k}(G) = ∑_{V′∈\binom{V}{k}} hc(G[V′]),

si \binom{V}{k} désigne l’ensemble des sous-ensembles de V de cardinalité k. Multiplions l’identité du corollaire 5.2 par V^{h}/h!, h ∈ ℕ :

HP\overline{G}(ν)\frac{V^{h}}{h!} + \overline{E}(1 + V)\frac{V^{h}}{h!} ≡ HP_{G}(ν)\frac{V^{h}}{h!} + E(1 + V)\frac{V^{h}}{h!}

≡ [HC\overline{G}(ν) + HC_{G}(ν)][\frac{V^{h}}{h!} + (h + 1)\frac{V^{h+1}}{(h + 1)!}]

+ \binom{h + 3}{3}\frac{V^{h+3}}{(h + 3)!} + \binom{h + 4}{4}\frac{V^{h+4}}{(h + 4)!} + \binom{h + 5}{5}\frac{V^{h+5}}{(h + 5)!} (mod 2).

En regardant le coefficient de ν^{V} nous déduisons le corollaire suivant, puisque (h + 1) et \binom{h+5}{5} sont pairs si h est un nombre impair.

Corollaire 5.3. Soient G = (V, E) et \overline{G} = (V, \overline{E}) deux graphes simples nonorientés qui sont complémentaires, et soient k et h deux entiers avec k ≥ 5, h ≥ 1 et k + h = n = |V |. Si h est impair, alors on a modulo 2 :

hp_{k}(\overline{G}) ≡ hp_{k}(G) ≡ hc_{k}(\overline{G}) + hc_{k}(G),

hp_{k+1}(\overline{G}) ≡ hp_{k+1}(G) ≡ hc_{k}(\overline{G}) + hc_{k}(G) + hc_{k+1}(\overline{G}) + hc_{k+1}(G),

hp_{k}(\overline{G}) + hp_{k+1}(\overline{G}) ≡ hp_{k}(G) + hp_{k+1}(G) ≡ hc_{k+1}(\overline{G}) + hc_{k+1}(G).

L’identité hp_{k+1}(\overline{G}) ≡ hp_{k+1}(G) (mod 2) fut imaginée par Lovász [24, 5.19] dans le cas particulier k + 1 = n.

Un graphe simple non-orienté G = (V, E) est appelé auto-complémentaire si et seulement si G et \overline{G} sont isomorphes. Pour de tels graphes, notre corollaire 5.3 fournit le théorème principal de l’article [27] de Rao, que ce dernier a démontré sur plusieurs pages.

Corollaire 5.4. (Rao) Soit G = (V, E) un graphe auto-complémentaire avec |V | = n. Alors hp_{k}(G) est pair pour tout 5 < k ≤ n.

Le cas le plus important du théorème précédent, à savoir k = n, fut imaginé par Camion [8].

6. Fonctions symétriques et fonctions d’ensembles

Dans l’introduction de sa thèse [11], Chow a suggéré une direction prometteuse pour étendre son étude des fonctions symétriques et saisir ainsi davantage de problèmes en combinatoire. Il nous semble que les fonctions d’ensembles permettent, par excellence, de réaliser cette idée de Chow.

Soient donc f, g : 2^{V} → A deux fonctions d’ensembles telles que f(∅) = g(∅) = 0. Nous définissons, pour chaque ∅ ⊂ V′ ⊆ V, la fonction symétrique de Stanley ST_{f,V′}(x_{1}, x_{2}, x_{3}, …) et la fonction symétrique de Chow CH_{g,V′}(x_{1}, x_{2}, x_{3}, …) par

\begin{aligned}1 + ∑_{∅⊂V′⊆V} ST_{f,V′}(x_{1}, x_{2}, x_{3}, …) · ν^{V′} & := ∏_{i=1}^{∞}[1 + F_{f}(x_{i} · ν)], \\ 1 + ∑_{∅⊂V′⊆V} CH_{g,V′}(x_{1}, x_{2}, x_{3}, …) · ν^{V′} & := exp[∑_{i=1}^{∞} F_{g}(x_{i} · ν)], \end{aligned}

respectivement (voir le début du paragraphe 2). La relation fondamentale entre la fonction symétrique de Chow et celle de Stanley est donnée par le théorème suivant.

Théorème 6.1. Si log[1 + F_{f}(ν)] = F_{g}(ν) ou bien 1 + F_{f}(ν) = exp[F_{g}(ν)], alors on a pour tout ∅ ⊂ V′ ⊆ V

ST_{f,V′}(x_{1}, x_{2}, x_{3}, …) = CH_{g,V′}(x_{1}, x_{2}, x_{3}, …).

Démonstration. On a en effet

\begin{aligned}1 + ∑_{∅⊂V′⊆V} ST_{f,V′}(x_{1}, x_{2}, …) · ν^{V′} & = exp[∑_{i=1}^{∞} log[1 + F_{f}(x_{i} · ν)]] \\ & = 1 + ∑_{∅⊂V′⊆V} CH_{g,V′}(x_{1}, x_{2}, …) · ν^{V′}. \end{aligned}

Exemple 6.1. Les fonctions symétriques de Stanley les plus fondamentales (voir [22], [32, chapitre 7], [25, chapitre 1.2]) sont la fonction symétrique élémentaire e_{n} = Λ^{n}(x_{1}, x_{2}, x_{3}, …) et la fonction symétrique complète h_{n} = S^{n}(x_{1}, x_{2}, x_{3}, …), n ∈ ℕ :

\begin{aligned}1 + V = 1 + F_{f}(ν) & ⇒  ST_{f,V′}(x_{1}, x_{2}, x_{3}, …) = |V′|! · e_{|V′|}, \\ (1 − V)^{−1} = 1 + F_{f}(ν) & ⇒  ST_{f,V′}(x_{1}, x_{2}, x_{3}, …) = |V′|! · h_{|V′|}. \end{aligned}

Les fonctions symétriques les plus simples, cependant, sont bien les sommes des puissances p_{n} = ψ_{n}(x_{1}, x_{2}, x_{3}, …) = ∑_{i=1}^{∞} x_{i}^{n}. À l’aide de cette base de l’espace des fonctions symétriques, on définit l’involution ω par ω(p_{n}) := (−1)^{n−1}p_{n}. Grâce à l’exemple précédent, le théorème suivant devient une généralisation directe des identités classiques ω(e_{n}) = h_{n} et ω(h_{n}) = e_{n}.

Théorème 6.2. Pour des fonctions d’ensembles f, g : 2^{V} → A telles que f(∅) = g(∅) = 0, on a

\begin{aligned}1 + ∑_{∅⊂V′⊆V} ω(ST_{f,V′}(x_{1}, x_{2}, x_{3}, …)) · ν^{V′} & = ∏_{i=1}^{∞}[1 + F_{f}(−x_{i} · ν)]^{−1}, \\ 1 + ∑_{∅⊂V′⊆V} ω(CH_{g,V′}(x_{1}, x_{2}, x_{3}, …)) · ν^{V′} & = exp[− ∑_{i=1}^{∞} F_{g}(−x_{i} · ν)]. \end{aligned}

Démonstration. Supposons, sans restreindre la généralité, que 1 + F_{f}(ν) = exp[F_{g}(ν)]. Il s’ensuit :

ω(∏_{i=1}^{∞}[1 + F_{f}(x_{i} · ν)]) = ω(exp[∑_{i=1}^{∞} F_{g}(x_{i} · ν)])

= exp[ω(∑_{i=1}^{∞} F_{g}(x_{i} · ν))] = exp[− ∑_{i=1}^{∞} F_{g}(−x_{i} · ν)]

= ∏_{i=1}^{∞}[1 + F_{f}(−x_{i} · ν)]^{−1}.

Dans l’article [23], nous avons introduit, pour chaque graphe simple non-orienté G = (V, E), la fonction indicatrice des ensembles de sommets indépendants I_{G}(ν) ainsi que la fonction d’ensembles A_{G}(ν) (resp. A_{G}^{∗}(ν)) dénombrant les orientations acycliques (resp. avec une seule source fixée) pour tous les sous-graphes engendrés de G. Nous avons établi les identités

[1 + I_{G}(−ν)]^{−1} = 1 + A_{G}(ν), − log[1 + I_{G}(−ν)] = log[1 + A_{G}(ν)] = A_{G}^{∗}(ν).

Stanley [30] a introduit et étudié la fonction chromatique X_{G} = X_{G}(x_{1}, x_{2}, x_{3}, …), qui est, par excellence, une fonction symétrique ^{⟨⟨} de Stanley^{⟩⟩} :

1 + ∑_{∅⊂V′⊆V} X_{G[V′]} · ν^{V′} := ∏_{i=1}^{∞}[1 + I_{G}(x_{i} · ν)].

Le corollaire suivant formule plusieurs théorèmes principaux de l’article [30] de Stanley dans le langage des fonctions d’ensembles.

Corollaire 6.1. (Stanley) On a

\begin{aligned}1 + ∑_{∅⊂V′⊆V} X_{G[V′]} · ν^{V′} & = ∏_{i=1}^{∞}[1 + I_{G}(x_{i} · ν)] = exp[− ∑_{i=1}^{∞} A_{G}^{∗}(−x_{i} · ν)], \\ 1 + ∑_{∅⊂V′⊆V} ω(X_{G[V′]}) · ν^{V′} & = ∏_{i=1}^{∞}[1 + A_{G}(x_{i} · ν)] = exp[∑_{i=1}^{∞} A_{G}^{∗}(x_{i} · ν)]. \end{aligned}

Selon Stanley [30], une série formelle p = p(x, y) en deux ensembles de variables x = (x_{1}, x_{2}, x_{3}, …) et y = (y_{1}, y_{2}, y_{3}, …) est appelée fonction supersymétrique si et seulement si p est symétrique par rapport aux variables x_{i} et y_{j} et

p(x, y)|_{y_{1}=−x_{1}} = p(x, y)|_{y_{1}=x_{1}=0}.

Notons ω_{y} l’involution ω n’agissant que sur les variables y en supposant que x_{1}, x_{2}, x_{3}, … sont des constants. Si p(x) est une fonction symétrique, définissons la superfication p(x/y) de p par

p(x/y) := ω_{y}(p(x, y)),

c’est-à-dire en remplaçant les variables x_{1}, x_{2}, … par x_{1}, x_{2}, …, y_{1}, y_{2}, … (c’est une soi-disante addition des deux alphabets) et en utilisant ω_{y} ensuite. Pour les fonctions symétriques de Stanley et de Chow, notre théorème 6.2 donne le résultat suivant.

Théorème 6.3. Soient f, g : 2^{V} → A telles que f(∅) = g(∅) = 0, alors on a

\begin{aligned}1 + ∑_{∅⊂V′⊆V} ST_{f,V′}(x/y) · ν^{V′} & = ∏_{i=1}^{∞} \frac{1 + F_{f}(x_{i} · ν)}{1 + F_{f}(−y_{i} · ν)}, \\ 1 + ∑_{∅⊂V′⊆V} CH_{g,V′}(x/y) · ν^{V′} & = exp[∑_{i=1}^{∞}(F_{g}(x_{i} · ν) − F_{g}(−y_{i} · ν))]. \end{aligned}

Le théorème précédent implique immédiatement le corollaire suivant, qui exprime le théorème 4.3 de [30] dans le langage des fonctions d’ensembles. La démonstration proposée par Stanley est la plus longue de tout l’article [30] et utilise les fonctions de Schur.

Corollaire 6.2. (Stanley) On a

1 + ∑_{∅⊂V′⊆V} X_{G[V′]}(x/y) · ν^{V′} = (∏_{i=1}^{∞}[1 + I_{G}(x_{i} · ν)]) · (∏_{i=1}^{∞}[1 + A_{G}(y_{i} · ν)]).

Étudions finalement la thèse de Chow [11] ou bien son article [10]. Il est utile de noter nos alphabets (x) = (x_{1}, x_{2}, …) et (y) = (y_{1}, y_{2}, …) de sorte que (−x) = (−x_{1}, −x_{2}, …) et (−y) = (−y_{1}, −y_{2}, …). L’addition des alphabets (x) + (y) déjà introduite peut être généralisée en considérant des combinaisons linéaires quelconques λ(x) + μ(y), λ, μ ∈ A, où il faut faire attention que −(−x) ≠ (x), puisque (−x) est une multiplication des variables par −1 tandis que −(x) est une soustraction de l’alphabet (x) (voir [22]). Le théorème suivant est évident ou bien une définition.

Théorème 6.4. Soient f, g : 2^{V} → A telles que f(∅) = g(∅) = 0, alors on a pour tout λ, μ ∈ A :

\begin{aligned}1 + ∑_{∅⊂V′⊆V} ST_{f,V′}[λ(x) + μ(y)] · ν^{V′} & = ∏_{i=1}^{∞}[(1 + F_{f}(x_{i}ν))^{λ}(1 + F_{f}(y_{i}ν))^{μ}], \\ 1 + ∑_{∅⊂V′⊆V} CH_{g,V′}[λ(x) + μ(y)] · ν^{V′} & = exp[∑_{i=1}^{∞}(λ · F_{g}(x_{i}ν) + μ · F_{g}(y_{i}ν))]. \end{aligned}

En particulier,

\begin{aligned}ω_{y}(ST_{f,V′}[λ(x) + μ(y)]) & = ST_{f,V′}[λ(x) − μ(−y)], \\ ST_{f,V′}[(x)/(y)] & = ST_{f,V′}[(x) − (−y)], \\ ω(ST_{f,V′}[(x)]) & = ST_{f,V′}[−(−x)]. \end{aligned}

Soient cyc_{G}(ν), lin_{G}(ν), cyc\overline{G}(ν) et lin\overline{G}(ν) quatre fonctions d’ensembles quelconques qui satisfont à l’identité de Berge, c’est-à-dire au théorème 4.1. Nous définissons, pour chaque ∅ ⊂ V′ ⊆ V, la fonction symétrique de Chow-Stanley CS_{G[V′]}[(x); (y)] par

1 + ∑_{∅⊂V′⊆V} CS_{G[V′]}[(x); (y)] · ν^{V′} := exp[∑_{i=1}^{∞} cyc_{G}(x_{i}ν)] · ∏_{j=1}^{∞}[1 + lin_{G}(y_{j}ν)].

Maintenant nous sommes en mesure de formuler notre généralisation du théorème principal de la thèse de Chow [11].

Théorème 6.5. (Théorème de dualité pour la fonction de Chow-Stanley) Pour tous λ_{c}, λ_{l}, μ_{c}, μ_{l} ∈ A, on a

\begin{matrix}CS\overline{G}[λ_{c}(x) + μ_{c}(y); λ_{l}(x) + μ_{l}(y)] \\ = CS_{G}[λ_{c}(−x) + μ_{c}(−y); −(λ_{c} + λ_{l})(−x) − (μ_{c} + μ_{l})(−y)]. \end{matrix}

Démonstration. Dans le langage des fonctions d’ensembles, il s’agit de démontrer l’identité suivante, que nous établissons à l’aide de l’identité de Berge :

exp[λ_{c} ∑_{i=1}^{∞} cyc\overline{G}(x_{i}ν)] · exp[μ_{c} ∑_{j=1}^{∞} cyc\overline{G}(y_{j}ν)]·

(∏_{i=1}^{∞}[1 + lin\overline{G}(x_{i}ν)])^{λ_{l}} · (∏_{j=1}^{∞}[1 + lin\overline{G}(y_{j}ν)])^{μ_{l}}

= exp[λ_{c} ∑_{i=1}^{∞} cyc_{G}(−x_{i}ν)] · exp[μ_{c} ∑_{j=1}^{∞} cyc_{G}(−y_{j}ν)]·

(∏_{i=1}^{∞}[1 + lin_{G}(−x_{i}ν)])^{−λ_{c}−λ_{l}} · (∏_{j=1}^{∞}[1 + lin_{G}(−y_{j}ν)])^{−μ_{c}−μ_{l}}

⇔  (exp[∑_{i=1}^{∞}(cyc\overline{G}(x_{i}ν) − cyc_{G}(−x_{i}ν))])^{λ_{c}}·

(exp[∑_{j=1}^{∞}(cyc\overline{G}(y_{j}ν) − cyc_{G}(−y_{j}ν))])^{μ_{c}}

= (∏_{i=1}^{∞}[1 + lin_{G}(−x_{i}ν)])^{−λ_{c}} · (∏_{j=1}^{∞}[1 + lin_{G}(−y_{j}ν)])^{−μ_{c}}.

Posons λ_{c} = μ_{l} = 1 et λ_{l} = μ_{c} = 0 pour obtenir le théorème principal de la thèse de Chow [11] et de l’article [10].

Corollaire 6.3. (Chow) On a

\begin{aligned}CS\overline{G}[(x); (y)] & = CS_{G}[(−x); −(−x) − (−y)] \\ & = [ω_{y}(CS_{G}[(−x); (y)])]_{y→(x,y)}. \end{aligned}

Chow a également trouvé un deuxième cas particulier du théorème 6.5, à savoir λ_{c} = −2, μ_{c} = 0 et λ_{l} = μ_{l} = 1.

Corollaire 6.4. (Chow) On a

\begin{aligned}CS\overline{G}[−2(x); (x) + (y)] & = CS_{G}[−2(−x); (−x) − (−y)] \\ & = ω_{y}(CS_{G}[−2(−x); (−x) + (y)]). \end{aligned}

Tous les autres cas du théorème 6.5 sont nouveaux. De notre point de vue, cependant, le théorème 6.5 et l’identité de Berge sont aussi des corollaires immédiats des résultats de Chow. Par ailleurs, Chow [10, paragraphe 6] a posé la question de mieux comprendre le rôle des inversions qu’il a considérées. Il nous semble, que l’addition des alphabets répond parfaitement à cette question. Au moins, il devient évident qu’il s’agit bien d’inversions, un fait que Chow a dû démontrer.

Remarquons finalement, que Gessel a aussi imaginé une démonstration de l’identité

CS\overline{G}[0; (y)] = ω_{y}(CS_{G}[0; (y)]),

qui se trouve dans l’intersection des deux résultats de Chow. Cette preuve de Gessel reproduite dans [10], cependant, s’étend, elle aussi, sur plus d’une page tout en utilisant les fonctions de Schur.

Remerciements. En tout premier lieu, je tiens à remercier D. Foata de toute son aide et assistance et notamment de ses explications stimulantes en ce qui concerne l’article [16]. Mes remerciements vont aussi à A. Lascoux, qui m’a recommandé, lors du magnifique Séminaire Lotharingien de Combinatoire 44 au Domaine Saint-Jacques, son article [22] ^{⟨⟨} sur l’importance de l’addition dans l’œuvre mathématique de Gian-Carlo Rota^{⟩⟩}. C’est ainsi que je me suis rendu compte de l’importance de la soustraction (des alphabets) dans les œuvres de T. Chow et de R. Stanley.

Références bibliographiques

[1] M. Aigner, ^{⟨⟨} Combinatorial Theory^{⟩⟩}, Springer-Verlag, Heidelberg, 1979.

[2] O. M. D’Antona et E. Munarini, The cycle-path indicator polynomial of a digraph, Advances in Appl. Math. 25 (2000), 41-56.

[3] R. Askey et G. Gasper, Convolution structures for Laguerre polynomials, J. Analyse Math. 31 (1977), 48–68.

[4] R. Askey et M. Ismail, Permutation problems and special functions, Canad. J. Math. 28 (1976), 853-874.

[5] R. Askey, M. Ismail et T. Koornwinder, Weighted permutation problems and Laguerre Polynomials, J. Combin. Theory Ser. A 25 (1978), 277-287.

[6] C. Berge, ^{⟨⟨} Graphes^{⟩⟩}, Bordas, Paris, 1983.

[7] C. Berge, Chemins hamiltoniens, ICC Research Report n^{o} 67/2, 1967.

[8] P. Camion, Hamiltonian chains in self-complementary graphs, Cahiers Centre Études Recherche Opér. 17 (1975), 173-183.

[9] T. Chow, A short proof of the rook reciprocity theorem, Electronic J. Combin. 3 (1996), R10.

[10] T. Chow, The path-cycle symmetric function of a digraph, Advances in Math. 118 (1996), 71-98.

[11] T. Chow, ^{⟨⟨} Symmetric Function Generalizations of Graph Polynomials^{⟩⟩}, Ph.D. Thesis, MIT, 1995.

[12] F. R. K. Chung et R. L. Graham, On the cover polynomial of a digraph, J. Combin. Theory Ser. B 65 (1995), 273-290.

[13] P. Doubilet, G.-C. Rota, R. Stanley, On the foundations of combinatorial theory (VI), dans : Proceedings of the Sixth Berkely Symposium on Mathematical Statistics and Probability, v. II, University of California Press, Berkeley (1972), 267-318.

[14] S. Even et J. Gillis, Derangements and Laguerre polynomials, Math. Proc. Camb. Phil. Soc. 79 (1976), 135-143.

[15] D. Foata et M.-P. Schützenberger, On the rook polynomials of Ferrers relations, dans : Combinatorial Theory and its Applications, vol. 2 (P. Erdös, A. Renyi et V. T. Sós, eds.), Colloq. Math. Soc. János Bolyai 4 (1970), North-Holland, Amsterdam, 431-436.

[16] D. Foata et D. Zeilberger, Laguerre polynomials, weighted derangements and positivity, SIAM J. Disc. Math. 1 (1988), 425-433.

[17] C. D. Godsil, ^{⟨⟨} Algebraic Combinatorics^{⟩⟩}, Chapman & Hall, New York, 1993.

[18] C. D. Godsil, Hermite polynomials and a duality relation for matchings polynomials, Combinatorica 1 (1981), 257-262.

[19] J. R. Goldman, J. T. Joichi, D. E. White, Rook theory I, Rook equivalence of Ferrers boards, Proc. Amer. Math. Soc. 52 (1975), 485-492.

[20] D. M. Jackson, Laguerre polynomials and derangements, Math. Proc. Camb. Phil. Soc. 80 (1976), 213-214.

[21] S. A. Joni et G.-C. Rota, A vector space analog of permutations with restricted position, J. Combinatorial Theory, Series A 29 (1980), 59-73.

[22] A. Lascoux, Couper les alphabets en quatre, http://phalanstere.univ-mlv.fr/ al/; version anglaise : Alphabet splitting, dans : Algebraic Combinatorics and Computer Science, A Tribute to Gian-Carlo Rota (H. Crapo et D. Senato, eds.), Springer-Verlag, Milano (2001), 431-444.

[23] B. Lass, Orientations acycliques et le polynôme chromatique, Europ. J. Combinatorics 22 (2001), 1101-1123.

[24] L. Lovász, ^{⟨⟨} Combinatorial Problems and Exercises^{⟩⟩}, Akadémiai Kiadó, Budapest, 1993.

[25] I. G. Macdonald, ^{⟨⟨} Symmetric Functions and Hall Polynomials^{⟩⟩}, Clarendon Press, Oxford, 1979.

[26] J. W. Moon, ^{⟨⟨} Topics on tournaments^{⟩⟩}, Holt, Rinehart and Winston, New York-Montreal, 1968.

[27] S. B. Rao, The number of open chains of length three and the parity of the number of open chains of length k in self-complementary graphs, Discrete Math. 28 (1979), 291-301.

[28] J. Riordan, ^{⟨⟨} An Introduction to Combinatorial Analysis^{⟩⟩}, Wiley, New York, 1958.

[29] M. de Sainte-Catherine et G. Viennot, Combinatorial interpretation of integrals of products of Hermite, Laguerre and Tchebycheff polynomials, dans : Polynômes orthogonaux et applications (C. Brezinski, et al., eds.), Bar-le-Duc, 1984, Lecture Notes in Mathematics 1175 (1985), Springer-Verlag, Berlin, 120-128.

[30] R. P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.

[31] R. P. Stanley, ^{⟨⟨} Enumerative Combinatorics^{⟩⟩}, Volume 1, Cambridge University Press, Cambridge, 1997.

[32] R. P. Stanley, ^{⟨⟨} Enumerative Combinatorics^{⟩⟩}, Volume 2, Cambridge University Press, Cambridge, 1999.

[33] T. Szele, Kombinatorische Untersuchungen über gerichtete vollständige Graphen, Publ. Math. Debrecen 13 (1966), 145-168.

[34] G. Viennot, ^{⟨⟨} Une théorie combinatoire des polynômes orthogonaux généraux^{⟩⟩}, Notes de conférences données à l’Université du Québec à Montréal, 1983.