Lemme de Lindström-Gessel-Viennot

En mathématiques, le lemme de Lindström-Gessel-Viennot est une méthode pour compter le nombre de listes de chemins dans un réseau qui ne se coupent pas ou, plus généralement, de chemins sur un graphe orienté.

Le lemme doit son nom à Bernt Lindström, Ira Gessel et Gérard Viennot. C'est Bernt Lindtröm qui l'a énoncé et démontré en 1972 dans le cadre des matroïdes mais il est à l'époque resté confidentiel. En 1985, il a été reformulé et démontré par Ira Gessel et Gérard Viennot dans le cadre des graphes, qui en ont montré toute la polyvalence et l'ont instantanément rendu très populaire^[1].

Soit G un graphe orienté acyclique localement fini. Cela signifie que G ne contient aucun cycle orienté et que chaque sommet a un degré fini. On attribue un poids ${\displaystyle w_{e}}$ à chaque arête orientée e. Les poids des arêtes sont supposés appartenir à un anneau commutatif fixé. Pour chaque chemin orienté P entre deux sommets, on note ${\displaystyle w(P)}$ le produit des poids des arêtes du chemin. Pour deux sommets a et b, on note e(a, b) la somme ${\displaystyle e(a,b)=\sum _{P:a\to b}w(P)}$ qui porte sur tous les chemins de a à b. Cette somme est bien définie s'il n'y a qu'un nombre fini de chemins entre deux points quelconques ; cependant, même s'il y a un nombre infini de chemins, il peut arriver que la somme soit bien définie (par exemple lorsque tous les poids des arêtes sont des indéterminées deux à deux distinctes et que ${\displaystyle e(a,b)}$ est considéré comme une série formelle). En particulier, si l'on attribue le poids 1 à chaque arête, alors e(a, b) compte le nombre de chemins de a à b. Enfin, on fixe un ensemble de sommets « sources » ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$ et un ensemble de sommets « buts » ${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$.

Dans ce contexte, on définit

${\displaystyle M=M_{G,w}(A,B)={\begin{pmatrix}e(a_{1},b_{1})&e(a_{1},b_{2})&\cdots &e(a_{1},b_{n})\\e(a_{2},b_{1})&e(a_{2},b_{2})&\cdots &e(a_{2},b_{n})\\\vdots &\vdots &\ddots &\vdots \\e(a_{n},b_{1})&e(a_{n},b_{2})&\cdots &e(a_{n},b_{n})\end{pmatrix}}}$.

Une n-liste de chemins sans intersection de A à B est la donnée d'une n-liste (P₁,..., P_n) de chemins de G qui a les propriétés suivantes :

• il existe une permutation ${\displaystyle \sigma }$ de ${\displaystyle \left\{1,2,...,n\right\}}$ telle que pour tout i, le chemin P_i soit un chemin allant de ${\displaystyle a_{i}}$ à ${\displaystyle b_{\sigma (i)}}$ ;
• pour toute paire d'indices ${\displaystyle i\neq j}$, les chemins P_i et P_j n'ont pas de sommet en commun (pas même des extrémités).

Pour une telle n-liste (P₁,..., P_n), on note ${\displaystyle \sigma (P)}$ la permutation de ${\displaystyle \sigma }$ définie par la première condition.

Le lemme de Lindström-Gessel-Viennot exprime alors que le déterminant de M est la somme alternée portant sur toutes les n-listes P = (P₁,..., P_n) de chemins non sécants de A à B :

${\displaystyle \det(M)=\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\operatorname {sign} (\sigma (P))\prod _{i=1}^{n}w(P_{i})}$

(où ${\displaystyle \operatorname {sign} (\sigma (P))}$ est la signature de ${\displaystyle \sigma (P)}$).

Autrement dit, le déterminant de M compte les poids de toutes les n-listes de chemins non sécants partant de A et se terminant en B, chacun affecté du signe de la permutation déterminée par le chemin ${\displaystyle P_{i}}$, qui conduit ${\displaystyle a_{i}}$ en ${\displaystyle b_{\sigma (i)}}$.

En particulier, si la seule permutation possible est l'identité (c'est-à-dire que toute n-liste de chemins non sécants de A à B envoie a_i sur b _i pour tout i) et que tous les poids sont égaux à 1, alors det(M) est exactement le nombre de n-listes de chemins non sécants partant de A et se terminant en B.

Avant de prouver le lemme de Lindström-Gessel-Viennot, on introduit quelques notations.

Étant donné deux n-listes de sommets de G, disons${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ et ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$, un n-chemin de ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ à${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ est une n-liste ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$ de chemins dans G, où chaque ${\displaystyle P_{i}}$ mène de ${\displaystyle a_{i}}$ à ${\displaystyle b_{i}}$. Ce n-chemin est dit sans intersection si deux chemins ${\displaystyle P_{i}}$ et ${\displaystyle P_{j}}$ associés à des indices distincts ${\displaystyle i\neq j}$ n'ont aucun sommet en commun (y compris à leurs extrémités). Sinon, on l'appellera enchevêtré.

Étant donné un n-chemin ${\displaystyle P=(P_{1},P_{2},\ldots ,P_{n})}$, son poids ${\displaystyle w(P)}$ est défini comme le produit des poids ${\displaystyle w(P_{1})w(P_{2})\cdots w(P_{n})}$.

Un n-chemin tordu de ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ à ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ est un n-chemin ${\displaystyle P}$ de ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ à ${\displaystyle \left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)}$ pour une permutation ${\displaystyle \sigma }$ convenable du groupe symétrique ${\displaystyle {\mathfrak {S}}_{n}}$. Cette permutation ${\displaystyle \sigma }$ sera appelé la torsion de ce n-chemin tordu et notée ${\displaystyle \sigma (P)}$. Ceci, bien sûr, généralise la notation ${\displaystyle \sigma (P)}$ utilisée ci-dessus.

En revenant à la définition de M, on peut développer det M comme une somme alternée indexée par les permutations ; on obtient ainsi

${\displaystyle {\begin{aligned}\det M&=\sum _{\sigma \in S_{n}}\operatorname {sign} (\sigma )\prod _{i=1}^{n}e(a_{i},b_{\sigma (i)})\\&=\sum _{\sigma \in S_{n}}\operatorname {sign} (\sigma )\prod _{i=1}^{n}\sum _{P_{i}:a_{i}\to b_{\sigma (i)}}w(P_{i})\\&=\sum _{\sigma \in S_{n}}\operatorname {sign} (\sigma )\sum \{w(P):P~{\text{un}}~n{\text{-chemin de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)\}\\&=\sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=\sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu sans intersection de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&\quad +\sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu enchevêtré}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\operatorname {sign} (\sigma (P))w(P)\\&\quad +\underbrace {\sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu enchevêtré de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}} _{=0\,?}.\\\end{aligned}}}$

Il s'agit donc de montrer que la somme des ${\displaystyle \operatorname {sign} (\sigma (P))w(P)}$ sur tous les n-chemins tordus enchevêtrés est nulle. Pour cela, on définit une involution qui fixe le poids et change la signature de la permutation associée sur l'ensemble ${\displaystyle {\mathcal {E}}}$ des n-chemins tordus enchevêtrés. Autrement dit, on construit une involution ${\displaystyle f:{\mathcal {E}}\longrightarrow {\mathcal {E}}}$ avec les propriétés ${\displaystyle w(f(P))=w(P)}$ et ${\displaystyle \operatorname {sign} (\sigma (f(P)))=-\operatorname {sign} (\sigma (P))}$ pour tout ${\displaystyle P\in {\mathcal {E}}}$. L'existence d'une telle involution montre que la somme qui reste,

${\displaystyle \sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu enchevêtré de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}=\sum _{P\in {\mathcal {E}}}\operatorname {sign} (\sigma (P))w(P)}$

est nulle, puisque ses termes s'éliminent deux à deux : le terme correspondant à chaque ${\displaystyle P\in {\mathcal {E}}}$ simplifie le terme correspondant à ${\displaystyle f(P)}$ (vu que les permutations associées à ${\displaystyle P}$ et ${\displaystyle f(P)}$ sont différentes, ${\displaystyle f}$ n'a pas de point fixe).

Construisons donc l'involution ${\displaystyle f}$. L'idée consiste à choisir deux chemins qui s'intersectent dans un n-chemin enchevêtré et à échanger leurs queues après leur point d'intersection. Dans un tel n-chemin, il y a en général plusieurs paires de chemins qui se croisent, qui peuvent d'ailleurs se croiser plusieurs fois ; il faut donc faire un choix judicieux. Soit ${\displaystyle P=\left(P_{1},P_{2},...,P_{n}\right)}$ un n-chemin tordu enchevêtré, on définit ${\displaystyle f(P)}$ de la façon suivante. On dit qu'un sommet est encombré s'il appartient à au moins deux des chemins ${\displaystyle P_{1},P_{2},...,P_{n}}$. Du fait que le graphe est acyclique, cela équivaut à « apparaître au moins deux fois dans tous les chemins »^{[n 1]}. Comme P est enchevêtré, il possède au moins un sommet encombré. On choisit le plus petit indice ${\displaystyle i\in \{1,2,\ldots ,n\}}$ tel que ${\displaystyle P_{i}}$ contient un sommet encombré. Ensuite, on choisit le premier sommet encombré v sur ${\displaystyle P_{i}}$ (c'est-à-dire « rencontré en premier lors d'un voyage le long de ${\displaystyle P_{i}}$ »), et on choisit le plus grand j tel que v appartient à ${\displaystyle P_{j}}$. Comme ${\displaystyle v}$ est encombré, que le graphe est acyclique et que ${\displaystyle i}$ est minimal, on a ${\displaystyle j>i}$. On écrit les deux chemins ${\displaystyle P_{i}}$ et ${\displaystyle P_{j}}$ sous la forme

${\displaystyle {\begin{array}{rcl}P_{i}&\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha -1}\to \overbrace {\mathbf {u} _{\alpha }\to u_{\alpha +1}\ldots \to u_{r}=b_{\sigma (i)}} ^{{\text{queue de}}~P_{i}}\\P_{j}&\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta -1}\to \underbrace {\mathbf {v} _{\beta }\to v_{\beta +1}\ldots \to v_{s}=b_{\sigma (j)}} _{{\text{queue de}}~P_{j}}\\\end{array}}}$

où ${\displaystyle \sigma =\sigma (P)}$ et où ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ sont tels que v soit le ${\displaystyle \alpha }$-ième sommet de ${\displaystyle P_{i}}$ et le ${\displaystyle \beta }$-ième sommet de ${\displaystyle P_{j}}$ (c'est-à-dire ${\displaystyle v=u_{\alpha }=v_{\beta }}$). On pose ${\displaystyle \alpha _{P}=\alpha }$ et ${\displaystyle \beta _{P}=\beta }$ et ${\displaystyle i_{P}=i}$ et ${\displaystyle j_{P}=j}$ . Le ${\displaystyle k}$-ième chemin de ${\displaystyle f(P)}$ est ${\displaystyle P_{k}}$ si ${\displaystyle k}$ est différent de ${\displaystyle i}$ et ${\displaystyle j}$ ; par ailleurs, les chemins ${\displaystyle P_{i}}$ et ${\displaystyle P_{j}}$ sont remplacés par les suivants :

${\displaystyle {\begin{array}{rcl}P'_{i}&\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha -1}\to \overbrace {v_{\beta _{P}}\to v_{\beta _{P}+1}\ldots \to v_{s}=b_{\sigma (j)}} ^{{\text{queue de}}~P_{j}}\\P'_{j}&\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta -1}\to \underbrace {u_{\alpha _{P}}\to u_{\alpha _{P}+1}\ldots \to u_{r}=b_{\sigma (i)}} _{{\text{queue de}}~P_{i}}\\\end{array}}}$

Il est immédiat de voir que ${\displaystyle f(P)}$ est un n-chemin tordu enchevêtré. En revenant sur la construction, on constate que ${\displaystyle i_{f(P)}=i_{P}}$, ${\displaystyle j_{f(P)}=j_{P}}$, que ${\displaystyle \alpha _{f(P)}=\alpha _{P}}$ et ${\displaystyle \beta _{f(P)}=\beta _{P}}$, de sorte que pour calculer l'image de ${\displaystyle f(P)}$ par ${\displaystyle f}$, on échange à nouveau les queues de ${\displaystyle f(P)_{i},f(P)_{j}}$ en laissant les autres chemins intacts. On en déduit que ${\displaystyle f(f(P))=P}$ , c'est-à-dire que ${\displaystyle f}$ est une involution. Il reste à vérifier les propriétés d’anti-symétrie annoncées.

Par construction, la permutation ${\displaystyle \sigma (f(P))}$ coïncide avec ${\displaystyle \sigma =\sigma (P)}$ sauf qu'elle échange ${\displaystyle \sigma (i)}$ et ${\displaystyle \sigma (j)}$ – c'est-à-dire que ${\displaystyle \sigma (f(P))=(\sigma (i),\sigma (j))\sigma (P)}$ – ce qui entraîne que ${\displaystyle \operatorname {sign} (\sigma (f(P)))=-\operatorname {sign} (\sigma (P))}$. Pour montrer que ${\displaystyle w(f(P))=w(P)}$, on calcule d'abord, à cause de l'échange des queues :

${\displaystyle {\begin{aligned}w(P'_{i})w(P'_{j})&=\left(\prod _{t=0}^{\alpha -1}w(u_{t},u_{t+1})\cdot \prod _{t=\beta }^{s-1}w(v_{t},v_{t+1})\right)\cdot \left(\prod _{t=0}^{\beta -1}w(v_{t},v_{t+1})\cdot \prod _{t=\alpha }^{r-1}w(u_{t},u_{t+1})\right)\\&=\prod _{t=0}^{r-1}w(u_{t},u_{t+1})\cdot \prod _{t=0}^{s-1}w(v_{t},v_{t+1})\\&=w(P_{i})w(P_{j}).\end{aligned}}}$

Ainsi ${\displaystyle w(f(P))=\prod _{k=1}^{n}w(f(P)_{k})=\prod _{k=1,~k\neq i,j}^{n}w(P_{k})\cdot w(P'_{i})w(P'_{j})=\prod _{k=1,~k\neq i,j}^{n}w(P_{k})\cdot w(P_{i})w(P_{j})=\prod _{k=1}^{n}w(P_{k})=w(P)}$ .

La construction de cette involution ayant les propriétés souhaitées termine la preuve du lemme de Lindström-Gessel-Viennot.

Remarque. On trouve des arguments semblables à celui-ci dans plusieurs sources, avec des variations concernant le choix des queues à échanger. C'est une version avec j le plus petit (différent de i) au lieu du plus grand qui apparaît dans (Gessel et Viennot 1989, démonstration du théorème 1).

Le premier exemple est assez trivial mais illustratif. Étant donné un entier n et n² éléments d'un anneau quelconque (ou indéterminées) ${\displaystyle m_{ij}}$ (${\displaystyle 1\leq i,j\leq n}$) on considère le graphe biparti complet ayant 2n sommets ${\displaystyle \{a_{1},\dots ,a_{n},b_{1},\dots ,b_{n}\}}$ et une arête de ${\displaystyle a_{i}}$ vers ${\displaystyle b_{j}}$ de poids ${\displaystyle m_{ij}}$ pour tout couple ${\displaystyle (i,j)}$. On prend naturellement ${\displaystyle A=\{a_{1},\dots ,a_{n}\}}$ et ${\displaystyle B=\{b_{1},\dots ,b_{n}\}}$ : il y a exactement un chemin de ${\displaystyle a_{i}}$ vers ${\displaystyle b_{j}}$ et son poids est ${\displaystyle m_{ij}}$. La matrice ${\displaystyle M}$ du lemme est donc simplement ${\displaystyle (m_{ij})_{1\leq i,j\leq n}}$. Un n-chemin sans intersection ${\displaystyle P=(P_{1},\dots ,P_{n})}$ est donné par la permutation ${\displaystyle \sigma }$ : le chemin ${\displaystyle P_{i}}$ est l'arête de ${\displaystyle a_{i}}$ à ${\displaystyle b_{\sigma (i)}}$ ; son poids est ${\displaystyle m_{i,\sigma (i)}}$ et le poids de ${\displaystyle P}$ est ${\displaystyle w(P)=m_{1,\sigma (1)}\cdots m_{n,\sigma (n)}}$. Ainsi, le lemme de Lindström-Gessel-Viennot s'écrit simplement

${\displaystyle \det M=\sum _{\sigma \in {\mathfrak {S}}_{n}}\operatorname {sign} (\sigma )\prod _{i=1}^{n}m_{i,\sigma (i)}}$,

ce qui le réduit à la définition du déterminant...

On peut utiliser le lemme de Lindström-Gessel-Viennot pour démontrer la formule de Binet-Cauchy, d'où l'on peut en particulier déduire la multiplicativité du déterminant.

On peut utiliser le lemme de Lindström-Gessel-Viennot pour démontrer l'équivalence de deux définitions différentes des polynômes de Schur. Étant donné une partition ${\displaystyle \lambda =\lambda _{1}\geq \cdots \geq \lambda _{r}>0}$ de n en r parts, le polynôme de Schur ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})}$ peut être indifféremment défini par les égalités :

• ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})=\sum _{T}w(T),}$

où la somme porte sur tous les tableaux de Young semi-standards T de forme λ (c'est-à-dire que l'on affecte un entier i de {1,..., n} à chaque case du diagramme de Young de T de sorte qu'une case soit inférieure ou égale à celle qui est à sa droite et strictement inférieure à celle qui est en dessous), et où le poids ${\displaystyle w(T)}$ d'un tableau T est défini comme le monôme obtenu comme le produit des x_i indexés par les coefficients i de T. Par exemple, le poids du tableau est ${\displaystyle x_{1}x_{3}x_{4}^{3}x_{5}x_{6}x_{7}}$ ;

• ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})=\det \left((h_{\lambda _{i}+j-i})_{1\leq i,j\leq r}\right),}$

où les h_i sont les polynômes symétriques homogènes complets (en) (et h_i vaut 0 si i est négatif). Par exemple, pour la partition (3,2,2,1), le déterminant correspondant est

${\displaystyle s_{(3,2,2,1)}={\begin{vmatrix}h_{3}&h_{4}&h_{5}&h_{6}\\h_{1}&h_{2}&h_{3}&h_{4}\\1&h_{1}&h_{2}&h_{3}\\0&0&1&h_{1}\end{vmatrix}}.}$

On montre l'équivalence entre ces deux définitions. On définit un graphe orienté : ses sommets sont les points de ${\displaystyle \mathbb {Z} ^{2}}$, ou plutôt ${\displaystyle \mathbb {N} \times \{1,\dots ,n\}}$ ; il y a une arête « est » de ${\displaystyle (i,j)}$ à ${\displaystyle (i+1,j)}$ de poids ${\displaystyle x_{i}}$ et, si ${\displaystyle j\leq n-1}$, une arête « nord » de ${\displaystyle (i,j)}$ à ${\displaystyle (i,j+1)}$ de poids ${\displaystyle 1}$

À présent, on fixe une partition λ et on considère les r points de départ ${\displaystyle a_{i}=(r+1-i,1)}$ et les r points d'arrivée ${\displaystyle b_{j}=(\lambda _{j}+r+1-j,n)}$. Avec cette définition, les r-listes de chemins de A à B s'identifient aux tableaux de Young semi-standard de forme λ, et le poids d'une telle r-liste est la somme correspondante dans la première définition des polynômes de Schur. Par exemple, le tableau correspond au quadruplet de chemins suivant.

Par ailleurs, la matrice M est exactement la matrice écrite ci-dessus pour le graphe orienté introduit plus haut. Ceci montre l'équivalence requise. (Voir également (Sagan 2010, §4.5), ou la première preuve de (Stanley 1999, théorème 7.16.1), ou (Fulmek 2012, §3.3), ou (Martin 2012, §9.13), pour de légères variations sur cet argument.)

On peut citer, entre autres :

• le calcul de certains « déterminants binomiaux », la positivité de tous les mineurs de la matrice ${\displaystyle \left({\binom {i}{j}}\right)_{1\leq i,j}}$ et de formules analogue à la formule des équerres, cf. (Gessel et Viennot 1985) ;
• le calcul du nombre de partitions planes (en) dans une boîte (résultat dû à Percy Alexander MacMahon), cf. (Gessel et Viennot 1989) ;
• les deux formules de Jacobi-Trudi (en)...

L'hypothèse que G est acyclique est essentielle dans le lemme de Lindström-Gessel-Viennot ; elle garantit (dans des situations raisonnables) que les sommes ${\displaystyle e(a,b)}$ sont bien définies, et elle apparaît dans la démonstration (si G n'est pas acyclique, alors f pourrait transformer une auto-intersection d'un chemin en une intersection de deux chemins distincts, ce qui détruit l'argument d'où vient le fait que f est une involution). Néanmoins, l’article (Talaska 2012) établit une formule généralisant le lemme à des graphes orientés arbitraires. Les sommes ${\displaystyle e(a,b)}$ sont remplacées par des séries formelles de puissances, et la somme sur les listes de chemins sans intersection devient désormais une somme sur des collections de chemins et de cycles sans intersection ni auto-intersection, divisée par une somme sur des collections de cycles sans intersection. Cf. l’article de Talaska pour plus de détails.

• Théorème de Kirchhoff

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lindström–Gessel–Viennot lemma » (voir la liste des auteurs).

• Ira M. Gessel et Xavier G. Viennot, « Binomial determinants, paths, and hook length formulae », Advances in Mathematics, vol. 58, n^o 3,‎ 1985, p. 300-321 (DOI 10.1016/0001-8708(85)90121-5)
• Ira M. Gessel et Xavier G. Viennot (36 p. ; prépublication non publiée), « Determinants, Paths and Plane Partitions », xavierviennot.org,‎ 1989 (lire en ligne)
• Bernt Lindström, « On the vector representations of induced matroids », Bulletin of the London Mathematical Society, vol. 5, n^o 1,‎ 1973, p. 85-90 (DOI 10.1112/blms/5.1.85)
• Bruce E. Sagan, The symmetric group, Springer, coll. « Graduate Texts in Mathematics » (n^o 203), 2010, 2^e éd. (1^re éd. 2001), xvi + 240 p. (ISBN 978-0-387-95067-9 et 978-1-4419-2869-6, DOI 10.1007/978-1-4757-6804-6)
• Richard P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge, Cambridge University Press, 1999
• (en) Kelli Talaska, « Determinants of weighted path matrices », 2012.
• Jeremy Martin, Lecture Notes on Algebraic Combinatorics (notes de cours), 2012 (lire en ligne)
• Markus Fulmek, « Viewing determinants as nonintersecting lattice paths yields classical determinantal identities bijectively », The Electronic Journal of Combinatorics, vol. 19, n^o 3,‎ 2012 (DOI 10.37236/2530, arXiv 1010.3860v1)

• Portail des mathématiques