\documentclass[11pt, a4paper]{article} \usepackage{amsmath,amsfonts,amssymb,amsthm} \setlength{\textwidth}{6.3in} \setlength{\textheight}{8.7in} \setlength{\topmargin}{0pt} \setlength{\headsep}{0pt} \setlength{\headheight}{0pt} \setlength{\oddsidemargin}{0pt} \setlength{\evensidemargin}{0pt} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtheorem{theorem}{Th\'eor\`eme}%[section] \newtheorem{thm}{Th\'eor\`eme} \newtheorem{proposition}{Proposition} \newtheorem{prop}{Proposition} \newtheorem{corollary}{Corollaire}%[section] \newtheorem{coro}{Corollaire}%[section] \newtheorem{lemma}{Lemme}%[section] \newtheorem{fact}{Fact}%[section] \newtheorem{definition}{D\'efinition}%[section] \newtheorem{example}{Exemple} \newcommand\cyc{\mathop{\rm cyc}} %\newenvironment{proof}{{\em Proof.}}{\mbox{}\hfill $\Box$\medskip} %\newenvironment{example}{\smallskip\noindent{\bf Exemple. }}{\smallskip} \newenvironment{remark}{\smallskip\noindent{\bf Remarque. }}{\smallskip} %binomial coefficients:\bi{#1}{#2} \newcommand\bi[2]{{{#1}\atopwithdelims(){#2}}} %q-binomial coefficients:\qbi{#1}{#2}{#3} \newcommand\qbi[3]{{{#1}\atopwithdelims[]{#2}}_{#3}} \pagestyle{plain} \newtheorem*{theo}{Th\'eor\`eme} \newtheorem{conj}{Conjecture} \newtheorem{lem}{Lemme} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\refname{BIBLIOGRAPHIE} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \title{Sur une g\'en\'eralisation des coefficients binomiaux} \author{Fr\'ed\'eric Jouhet, Bodo Lass et Jiang Zeng\\ \small Institut Girard Desargues, Universit\'e Claude Bernard (Lyon 1)\\[-0.8ex] \small 43, bd du 11 Novembre 1918, 69622 Villeurbanne cedex, France\\[-0.8ex] \small \{\texttt{jouhet, lass, zeng}\} @ \texttt{igd.univ-lyon1.fr}\\[-0.8ex] } \date{} %\small 2000 Mathematics Subject Classification : 05A10, 33C20} \maketitle %\centerline{\it Combinatorica lux mea} \begin{abstract} We prove a recent conjecture of Lassalle about positivity and integrality of coefficients in some polynomial expansions. We also give a combinatorial interpretation of those numbers. Finally, we show that this question is closely related to the fundamental problem of calculating the linearization coefficients for binomial coefficients. \bigskip \centerline{\bf Key words} \smallskip Positivity and integrality conjectures, linearization coefficients, calculus of finite differences \bigskip \centerline{\bf AMS subject classifications} \smallskip 05A05, 05A10, 05A15, 05A17, 05A18, 05A19, 05E05, 33C20 \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} Une partition $\mu= (\mu_1\geq \mu_2\geq \cdots \geq \mu_l>0)$ de $n$ est une suite d\'ecroissante d'entiers strictement positifs de somme $n=|\mu|$. Le nombre $l=l(\mu)$ est appel\'e la longueur de $\mu$. Pour tout $i\geq 1$, l'entier ${m}_{i} (\mu) = \textrm{card} \{j: {\mu }_{j} = i\}$ est la multiplicit\'e de $i$ dans $\mu$. D\'efinissons \[{z}_{\mu} = \prod\limits_{i \ge 1}^{} {i}^{{m}_{i}(\mu)} {m}_{i}(\mu) ! .\] % % Pour $n\geq 1$ les factorielles \emph{montantes} et \emph{descendantes} sont d\'efinies comme suit~: $$ (x)_n= x (x+1) \cdots (x+n-1),\qquad \langle x\rangle_n = x (x-1) \cdots (x-n+1). $$ Notons que $\langle -x\rangle_n=(-1)^n(x)_n$ et que les coefficients binomiaux valent $\binom{x}{n} = {\langle x\rangle}_{n}/n!$. Dans ses travaux sur les \emph{polyn\^omes de Jack}~\cite{La02} Lassalle a r\'ecemment pos\'e la conjecture suivante. \begin{conj} Soit $X$ une ind\'etermin\'ee, $m$ et $n$ deux entiers strictement positifs et ${\bf r}=(r_1,\ldots,r_m)$ une suite d'entiers positifs telle que $|{\bf r}| = \sum_{i = 1}^m r_i>0$. On a \begin{equation}\label{eq:las} \sum_{|\mu| = n} \frac{X^{l(\mu) - 1}} {z_{\mu }} \left( \sum_{i = 1}^{l(\mu )} \prod_{k = 1}^m \frac{{(\mu_i)}_{r_k}}{r_{k}!} \right) = \frac{1}{|{\bf r}|} \sum_{k = 1}^{\min (n,|r|)} c_k^{({\bf r})} \binom{X +n - 1}{n - k} , \end{equation} o\`u les coefficients $c_k^{({\bf r})}$ sont des entiers positifs \`a d\'eterminer. \end{conj} Remarquons d'abord que le membre de gauche de (\ref{eq:las}) est un polyn\^ome en $X$ de degr\'e $n-1$, donc il peut \^etre d\'evelopp\'e dans la base $\{\binom{X+n-1}{n-k}\}$ ($1\leq k\leq n$) d'une seule fa\c con. Ceci implique l'existence et l'unicit\'e des coefficients rationnels $c_k^{({\bf r})}$ au membre de droite de (\ref{eq:las}). Comme nous allons le d\'emontrer, les nombres~$c_k^{({\bf r})}$ sont en fait des entiers positifs et in\-d\'e\-pen\-dants de~$n$. Pour $m=1$ et $m=2$ les coefficients $c_k^{({\bf r})}$ ont \'et\'e d\'etermin\'es et la conjecture a \'et\'e v\'erifi\'ee~(voir~\cite{Ei,La00,La02,Z}). Dans le premier cas, on a $c_k^{(r_1)}=\binom{r_1}{k}$ et dans le deuxi\`eme cas Lassalle~\cite{La02} a obtenu plusieurs formules exprimant $c_k^{(r_1, r_2)}$, qui se r\'eduisent au cas pr\'ec\'edent lorsque $r_2=0$. Donc les coefficients $c_k^{({\bf r})}$ sont des extensions des coefficients binomiaux classiques. L'objectif de cet article est de donner une solution compl\`ete de ce probl\`eme, ceci par \emph{trois} approches distinctes utilisant des techniques compl\`etement diff\'erentes. Plus pr\'ecis\'ement, la section~2 donne une r\'eponse analytique \`a la conjecture~1, ainsi que quelques identit\'es du m\^eme type, ceci \`a l'aide des fonctions g\'en\'eratrices multivari\'ees. Dans la troisi\`eme section, nous donnons une interpr\'etation combinatoire de l'identit\'e suivante~: \begin{equation}\label{eq:bigeq} \sum_{|\mu| = n} \frac{n!} {z_{\mu }} X^{l(\mu) - 1} \sum_{i = 1}^{l(\mu )} \prod_{k = 1}^m \mu_i \binom{\mu_i+r_k-1}{r_k-1} =\frac{\prod_{j} r_{j}}{|{\bf r}|} \sum_{k = 1}^{\min (n,|r|)} c_k^{({\bf r})} k!\binom{n}{k} (X+k)_{n-k}, \end{equation} qui est l'identit\'e \eqref{eq:las} au facteur $n!r_1\ldots r_m$ pr\`es. Dans la derni\`ere section, nous d\'etaillons une troisi\`eme d\'emonstration de la conjecture de Lassalle qui utilise le calcul aux diff\'erences et le cas particulier $m = 1$ de \eqref{eq:bigeq} , c'est-\`a-dire l'identit\'e~: \begin{equation}\label{eq:bigeq1} \sum_{|\mu| = n} \frac{n!} {z_{\mu }} X^{l(\mu) - 1} \sum_{i = 1}^{l(\mu )} \mu_i \binom{\mu_i+r_1-1}{r_1-1} =\sum_{k \geq 1} \binom{r_1}{k} k!\binom{n}{k} (X+k)_{n-k}=(X+r_1)_n-(X)_n, \end{equation} dont la d\'emonstration est facile, voir \cite{La00} pour une preuve alg\'ebrique et \cite{Z} pour une preuve combinatoire. Dans ce paragraphe, nous voyons que le probl\`eme essentiel soulev\'e par la conjec\-ture de Lassalle est le calcul de certains coefficients de lin\'earisation. Malgr\'e l'importance fondamentale de cette question, il semble que, jusqu'\`a pr\'esent, les coefficients de lin\'earisation ne furent \'etudi\'es que pour les polyn\^omes orthogonaux. C'est pourquoi nous ajoutons un traitement combinatoire du probl\`eme dans cette section. Afin de rendre la lecture la plus autonome possible nous rappelons ici quelques formules fr\'equemment utilis\'ees dans la suite. D'abord la formule binomiale peut s'\'ecrire~: \begin{equation}\label{eq:binom} (1-x)^{-\alpha}=\sum_{n\geq 0}\frac{(\alpha)_n}{n!}x^n. \end{equation} Nous aurons aussi besoin de la transformation suivante, qui est un cas limite de la formule de Whipple \cite[p. 142]{AAR}~: \begin{equation}\label{whip} {}_3F_2\!\left[\begin{matrix}-n,a,b\\c,d\end{matrix};1\right]= \frac{(c-a)_n}{(c)_n}{}_3F_2\! \left[\begin{matrix}-n,a,d-b\\d,a+1-n-c\end{matrix};1\right], \end{equation} et qui se r\'eduit \`a la formule de sommation de Chu-Vandermonde lorsque $b=d$~: \begin{equation}\label{cvd} {}_2F_1\!\left[\begin{matrix}-n,a\\c\end{matrix};1\right]= \frac{(c-a)_n}{(c)_n}, \end{equation} o\`u \[ {}_pF_q\!\left[\begin{matrix}a_1,a_2,\dots,a_p\\ b_1,b_2,\dots,b_q\end{matrix};z\right]= \sum _{k\geq 0} \frac {(a_1)_k\cdots(a_p)_k} {(b_1)_k\cdots(b_q)_k}\frac{z^k}{k!}. \] est la d\'efinition des fonctions hyperg\'eom\'etriques classiques. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Fonctions g\'en\'eratrices} En multipliant le membre de gauche de (\ref{eq:las}) par $t^nx_1^{r_1}\cdots x_m^{r_m}$ et en sommant sur $n\geq 1$ et les entiers $r_1,\ldots, r_m\geq 0$ tels que $|{\bf r}|\neq 0$, par la formule binomiale (\ref{eq:binom}), nous sommes amen\'es \`a \'evaluer l'expression $$ \sum_{|\mu|\geq 1} t^{|\mu|} {\frac{{X}^{l(\mu)-1}}{{z}_{\mu }}} \sum_{i = 1}^{l(\mu)}\left( \prod_{l=1}^m (1-x_l)^{-\mu_i}-1\right). $$ \begin{lem} Soit $y$ une ind\'etermin\'ee, alors \begin{equation}\label{eq:gauche} \sum_{|\mu|\geq 1} t^{|\mu|} {\frac{{X}^{l(\mu)-1}}{{z}_{\mu }}} \sum_{i = 1}^{l(\mu)}(y^{\mu_i}-1)=\sum_{n\geq 1} t^n \sum_{k=1}^n \binom{X+n-1}{n-k} \frac{(y - 1 )^k}{k}. \end{equation} \end{lem} \begin{proof}[Preuve] Toute partition $\mu$ non nulle correspond de fa\c con biunivoque \`a une suite non nulle \`a support fini ${\mathbf m}=(m_1,m_2,\ldots)$ telle que $\mu=(1^{m_1}2^{m_2}\ldots)$. On a donc \begin{eqnarray} \sum_{|\mu|\geq 1} t^{|\mu|}{\frac{{X}^{l(\mu)-1}}{{z}_{\mu }}} \sum_{i = 1}^{l(\mu)}y^{\mu_i} &=&\sum_{\mathbf m}X^{-1}\prod_{j\geq 1}\left(\frac{Xt^j}{j}\right)^{m_j}\frac{1}{m_j!}\sum_{i\geq 1}m_iy^{i} \nonumber\\ &=& \sum_{i\geq 1}y^i \left(\sum_{m_i\geq 0}m_i\left(\frac{Xt^i}{i}\right)^{m_i} \frac{X^{-1}}{m_i!}\right)\cdot \prod_{j\neq i}\sum_{m_j\geq 0}\left(\frac{Xt^j}{j}\right)^{m_j}\frac{1}{m_j!}\nonumber\\ &=&\sum_{i\geq 1}\frac{(yt)^i}{i}\exp\left(\frac{Xt^i}{i}\right) \prod_{j\neq i}\exp\left({\frac{Xt^j}{j}}\right)\nonumber\\ &=& (1-t)^{-X} \log ( 1 -yt)^{-1}.\label{fg} \end{eqnarray} Par soustraction du terme correspondant \`a $y=1$, nous obtenons \begin{eqnarray} \sum_{|\mu|\geq 1} t^{|\mu|} {\frac{{X}^{l(\mu)-1}}{{z}_{\mu }}} \sum_{i = 1}^{l(\mu)}(y^{\mu_i}-1)&=& (1-t)^{-X}\log \left( 1 - \frac{t}{1-t}(y - 1) \right)^{-1}\nonumber\\ &=&\sum_{k\geq 1} (1-t)^{-X-k}\frac{t^k( y- 1 )^k }{k}\nonumber\\ &=&\sum_{n\geq 1} t^n \sum_{k=1}^n \binom{X+n-1}{n-k} \frac{(y - 1 )^k}{k},\nonumber %\label{eq:frederic2} \end{eqnarray} ce qui ach\`eve la d\'emonstration. \end{proof} Notons, pour toute fonction multivari\'ee $f$, par $[x_1^{r_1} \cdots x_m^{r_m}]f(x_1, \dots, x_m)$ le coefficient de $x_1^{r_1} \cdots x_m^{r_m}$ dans $f$. Nous d\'eduisons donc de (\ref{eq:gauche}), en posant $y=1/(1-x_1)(1-x_2)\cdots (1-x_m)$, le r\'esultat suivant. \begin{thm} Soient $c_k^{({\bf r})}$ les nombres rationnels d\'efinis par (\ref{eq:las}). Alors \begin{equation}\label{eq:frederic3} \frac{c_k^{({\bf r})} }{|{\bf r}|}=[x_1^{r_1} \cdots x_m^{r_m}]\;\frac{1}{k} \left( \frac{1}{(1-x_1) \cdots (1-x_m)} - 1 \right)^k. \end{equation} En particulier, ${kc_k^{({\bf r})} }/{|{\bf r}|}$ est un entier positif et ne d\'epend pas de~$n$. \end{thm} Il en r\'esulte que \begin{eqnarray} c_k^{({\bf r})}&=&[x_1^{r_1} \cdots x_m^{r_m}]\; \frac{d}{dz} \Biggl|_{z=1} \frac{1}{k} \left( \frac{1}{(1-zx_1) \cdots (1-zx_m)} - 1 \right)^k \label{expr1}\\ &=& [x_1^{r_1} \cdots x_m^{r_m}]\;\left( \frac{1}{(1-x_1) \cdots (1-x_m)} - 1 \right)^{k-1} \frac{\frac{x_1}{1-x_1}+\cdots + \frac{x_m}{1-x_m}} {(1-x_1) \cdots (1-x_m)}.\nonumber \end{eqnarray} La derni\`ere expression montre clairement le corollaire suivant. \begin{coro} Les nombres $c_k^{({\bf r})}$ sont des entiers positifs. \end{coro} Il est aussi possible de d\'eduire le corollaire au moyen des \emph{fonctions sym\'etriques homog\`enes} sur $\{x_1,\dots,x_m\}$, qui sont d\'efinies~\cite{JZ, Ma} par la fonction g\'en\'eratrice~: \begin{equation*}\label{fgh} \sum_{n\geq 0}h_n(x_1,\ldots,x_m)z^n=\prod_{i=1}^m(1-zx_i)^{-1}, \end{equation*} et donc ceci, \`a l'aide de (\ref{expr1}), permet d'\'ecrire : \begin{eqnarray} && \sum_{k\geq 1}\sum_{r_1,\ldots,r_m\geq 0} c_k^{({\bf r})}t^kx_1^{r_1}\cdots x_m^{r_m} \nonumber\\ &=& -\frac{d}{dz} \Biggl|_{z=1}\log\left(1-t\sum_{n\geq 1}h_n(x_1,\ldots,x_m)z^n\right)\nonumber\\ &=& \sum_{\lambda} |\lambda| \frac{t^{l(\lambda)}}{l(\lambda)} \binom{l(\lambda)}{m_1(\lambda),m_2(\lambda),\ldots} h_\lambda(x_1,\ldots,x_m)\nonumber\\ &=& \sum_{\lambda}t^{l(\lambda)} \sum_{i \ge 1} i \binom{l(\lambda)-1} {m_1(\lambda),m_2(\lambda),\ldots, m_i(\lambda)-1, \ldots} h_\lambda(x_1,\ldots,x_m)\label{waring1}, \end{eqnarray} ce qui montre aussi que $c_k^{({\bf r})}\in\mathbb{N}$. Notons que le membre de droite de (\ref{waring1}) s'apparente au d\'eveloppement de la $n$i\`eme fonction sym\'etrique \emph{puissance} $p_n(x_1,\ldots,x_m)$ dans la base des fonctions sym\'etriques homog\`enes donn\'e par la formule de Waring \cite{JZ, Macmahon}. \bigskip D'autre part, en d\'eveloppant le membre de droite de (\ref{eq:frederic3}) par la formule binomiale, nous obtenons \begin{eqnarray*} &&\frac{(-1)^k}{k}+\frac{1}{k}\sum_{i\geq 1}(-1)^{k-i} \binom{k}{i}(1-x_1)^{-i}\cdots (1-x_m)^{-i}\\ &=& {\sum_{|{\bf r}|> 0}} \; {\sum_{i\geq 1}} \frac{(-1)^{k-i}}{i}\binom{k-1}{i-1} \prod_{l=1}^m\binom{r_l+i-1}{r_l}x_l^{r_l}, \end{eqnarray*} ce qui donne, en extrayant le coefficient de $x_1^{r_1}\cdots x_m^{r_m}$, le r\'esultat suivant. \begin{coro} On a la formule explicite pour $c_k^{(\bf r)}$~: \begin{eqnarray} c_k^{(\bf r)}&=&|{\bf r}|\sum_{i\geq 1}\frac{(-1)^{k-i}}{i}\binom{k-1}{i-1} \prod_{l=1}^m\binom{r_l+i-1}{r_l}\label{eq:explicit}\\ &=&\sum_{j=1}^m\sum_{i=1}^k (-1)^{k-i}\binom{k-1}{i-1}\binom{i+r_j-1}{r_j-1} \prod_{l=1,l\neq j}^m\binom{r_l+i-1}{r_l}.\label{eq:entiere} \end{eqnarray} \end{coro} En particulier, pour $m=1$ et $m=2$, la formule~(\ref{eq:explicit}) permet de retrouver les deux expressions explicites de Lassalle~\cite{La02}. En fait, pour $m=1$ la formule (\ref{eq:frederic3}) se r\'eduit directement \`a \begin{equation}\label{eq:m=1} \frac{k}{r_1}c_k^{(r_1)}=[x_1^{r_1}]\;x_1^k(1-x_1)^{-k}=[x_1^{r_1}]\;\sum_{l\geq k}\binom{l-1}{k-1}x_1^l\Longrightarrow c_k^{(r_1)}=\binom{r_1}{k}. \end{equation} Pour $m=2$ la formule~(\ref{eq:explicit}) s'\'ecrit \begin{eqnarray*} c_k^{(r_1,r_2)}&=&\frac{r_1+r_2}{k}\sum_{i=1}^k (-1)^{k-i}\binom{k}{i}\binom{i+r_1-1}{r_1}\binom{i+r_2-1}{r_2}\\ &=&(-1)^{k-1}(r_1+r_2)\;{}_3F_2\!\left[\begin{matrix} -k+1,r_1+1,r_2+1\\2,1\end{matrix};1\right]. \end{eqnarray*} Appliquons deux fois la formule~(\ref{whip}) \`a l'expression ci-dessus, ce qui donne bien $$ c_k^{(r_1,r_2)}= \binom{r_1+r_2}{k}\;{}_3F_2\! \left[\begin{matrix}-k+1,-r_1,-r_2\\1-r_1-r_2,1\end{matrix};1\right]. $$ Remarquons qu'en appliquant une troisi\`eme fois (\ref{whip}), on retrouve une autre expression de \cite{La02}~: \begin {eqnarray*} c_k^{(r_1,r_2)}&=& \binom{r_1+r_2}{k}\binom{r_1+r_2}{r_1} {}_3F_2\!\left[\begin{matrix}-r_1,-r_2, k-r_1-r_2\\ 1-r_1-r_2, -r_1-r_2\end{matrix};1\right]\\ &=&\sum_{i \geq 0} (-1)^i \binom{r_1+r_2-i}{k}\frac{r_1+r_2}{r_1+r_2-i}\binom{r_1+r_2-i}{i} \binom{r_1+r_2-2i}{r_1-i}. \end {eqnarray*} Enfin, en multipliant le membre de gauche de (\ref{eq:las}) par $t^nx_1^{r_1}\cdots x_m^{r_m}$ et en sommant sur $n\geq 1$ et les entiers $r_1,\ldots, r_m\geq 0$, nous obtenons $$ \sum_{|\mu|\geq 1} t^{|\mu|} {\frac{{X}^{l(\mu)-1}}{{z}_{\mu }}} \sum_{i = 1}^{l(\mu)}\prod_{l=1}^m (1-x_l)^{-\mu_i}, $$ ce qui peut se d\'evelopper directement \`a l'aide de (\ref{fg}) comme suit~: \begin{equation*} \sum_{n\geq 0}t^n\frac{(X)_n}{n!}\sum_{k\geq 1}\frac{1}{k} \left( \frac{t}{(1-x_1) \cdots (1-x_m)}\right)^k=\sum_{n,k\geq 1}\frac{t^n}{k}\binom{X +n-k- 1}{n - k}\prod_{l=1}^m\sum_{r_l\geq 0}\frac{(k)_{r_l}}{r_l!}x_l^{r_l}, \end{equation*} et donc nous obtenons l'identit\'e \begin{equation}\label{eq:las0'} \sum_{|\mu| = n} \frac{X^{l(\mu) - 1}} {z_{\mu }} \sum_{i= 1}^{l(\mu )} \prod_{k = 1}^m \frac{{(\mu_i)}_{r_k}}{r_{k}!} =\sum_{k = 1}^{n}\frac{1}{k} \prod_{l=1}^m\binom{r_l+k- 1}{r_l}\binom{X +n -k- 1}{n - k}. \end{equation} Il est possible d'\'etablir une extension de (\ref{eq:las0'}) comme suit. \begin{prop} Pour toute partition $\mu$ et tout $p\in \mathbb{N}$, soit $\genfrac{\langle}{\rangle}{0pt}{}{\mu}{p}$ le nombre de fa\c cons de choisir $p$ \'el\'ements dans le diagramme de Ferrers de $\mu$, dont au moins un par ligne, alors \begin{eqnarray} &&\sum_{|\mu| = n} \genfrac{\langle}{\rangle}{0pt}{}{\mu}{p} \frac{X^{l(\mu) -1}} {z_{\mu }}\left( \sum_{i= 1}^{l(\mu )} \prod_{k = 1}^m\frac{{(\mu_i)}_{r_k}}{r_{k}!} \right)\nonumber\\ &&=\sum_{k = 1}^{p}\frac{1}{k} \left(\sum_{j= k}^{n-p+k}\binom{j-1}{k-1}\binom{n-j-1}{p-k-1}\prod_{l=1}^m\binom{r_l+j- 1}{r_l}\right)\binom{X +p -k- 1}{p - k}.\label{eq:las0''} \end{eqnarray} \end{prop} \begin{proof}[Preuve] Rappelons la fonction g\'en\'eratrice suivante \cite{JZ} : $$ \sum_{p\geq 1} \genfrac{\langle}{\rangle}{0pt}{}{\mu}{p} x^p=\prod_{k\geq 1}\left((1+x)^k-1\right)^{m_k(\mu)}. $$ Nous pouvons ainsi, comme pour (\ref{eq:las0'}), calculer la fonction g\'en\'eratrice du membre de gauche de (\ref{eq:las0''}), en le multipliant par $t^nx^px_1^{r_1}\cdots x_m^{r_m}$ et en sommant sur $n,p\geq 1$ et $r_1,\ldots, r_m\geq 0$ : \begin{eqnarray*} &&\sum_{|\mu|\geq 1} t^{|\mu|}{\frac{{X}^{l(\mu )-1}}{{z}_{\mu }}}\sum_{p\geq 1}\genfrac{\langle}{\rangle}{0pt}{}{\mu}{p} x^p\sum_{i = 1}^{l(\mu)}\prod_{l=1}^m (1-x_l)^{-\mu_i}\\ &&=\left(1-\frac{tx}{1-t}\right)^{-X}\left[\log\left(1 -\frac{t}{(1-x_1) \cdots (1-x_m)}\right)- \log\left(1 -\frac{t(1+x)}{(1-x_1) \cdots (1-x_m)}\right)\right]. \end{eqnarray*} D\'eveloppons alors cette derni\`ere expression, ce qui donne : \begin{eqnarray*} &&\sum_{p\geq 0}\left(\frac{tx}{1-t}\right)^p\frac{(X)_p}{p!}\sum_{j\geq 1}\frac{1}{j} \left(\frac{t}{(1-x_1) \cdots (1-x_m)}\right)^j\left((1+x)^j-1\right)\\&&=\sum_{j,k\geq 1}\sum_{p\geq 0}\frac{1}{j}\left(\frac{tx}{1-t}\right)^p\frac{(X)_p}{p!}\left(\frac{t}{(1-x_1) \cdots (1-x_m)}\right)^j\binom{j}{k}x^k\\ &&=\sum_{j,k,p\geq 1}\frac{1}{j}\binom{j}{k}\binom{X+p-k-1}{p-k}x^p\left(\prod_{l=1}^m\sum_{r_l\geq 0}\frac{(j)_{r_l}}{r_l!}x_l^{r_l}\right)t^{p+j-k}(1-t)^{-p+k}. \end{eqnarray*} Mais en utilisant la formule binomiale sous la forme : $$(1-t)^{-p+k}=\sum_{n\geq 0}\frac{(p-k)_{n}}{n!}t^n,$$ en rempla\c cant $n$ par $n-p-j+k$ et en extrayant le coefficient devant $x^pt^nx_1^{r_1}\cdots x_m^{r_m}$, nous obtenons la fonction g\'en\'eratrice du membre de droite. \end{proof} \begin{remark} Pour $p=n$, l'identit\'e (\ref{eq:las0''}) donne bien (\ref{eq:las0'}). Lorsque tous les $r_i$ sont nuls, le membre de droite de (\ref{eq:las}) n'a pas de sens. Or il r\'esulte de (\ref{eq:gauche}) avec $y=0$ que $$ (1-t)^{-X}\log(1-t)^{-1}=\sum_{n\geq 1} t^n \sum_{k=1}^n \binom{X+n-1}{n-k} \frac{(- 1 )^{k-1}}{k}, $$ ce qui donne le prolongement suivant de (\ref{eq:las}) pour ${\bf r}=0$~: \begin{equation}\label{eq;mac} \sum_{|\mu| = n} \frac{X^{l(\mu) - 1}} {z_{\mu }}{l(\mu )} =\sum_{k = 1}^n\frac{(-1)^{k-1}}{k} \binom{X +n - 1}{n - k}. \end{equation} Cette formule est en fait la \emph{d\'eriv\'ee} d'une formule de Macdonald~\cite[p. 26]{Ma}~: $$ \sum_{|\mu|=n}\frac{X^{l(\mu)}}{z_\mu}=\binom{X+n-1}{n}. $$ \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Interpr\'etations combinatoires} Une permutation $\sigma$ de l'ensemble $E=\{a_1,\ldots, a_k\}$ est un \emph{cycle} si $E=\{a_1, \sigma(a_1),\ldots, \sigma^{k-1}(a_1)\}$. On note $\sigma=(a_i,\sigma(a_i),\ldots, \sigma^{k-1}(a_i))$ pour $1\leq i\leq k$ et on appelle $\sigma$ un cycle de longueur $k$ ou un $k$-cycle et $E$ le \emph{support} de $\sigma$. Il est d'usage d'identifier $\sigma$ avec son \emph{graphe sagittal} $G_\sigma$, c'est-\`a-dire, $a_i\to a_j$ est un arc de $G_\sigma$ si et seulement si $\sigma(a_i)=a_j$. Si $\alpha=(a_1, a_2, \ldots, a_k)$ et $\beta=(b_1,b_2,\ldots, b_r)$ sont deux cycles de supports disjoints, un \emph{m\'elange} de $\alpha$ et $\beta$ est d\'efini comme un cycle $(c_1,\ldots, c_{k+r})$, o\`u le mot $w=c_1\ldots c_{k+r}$ est un r\'earrangement de $$a_1a_2 \ldots a_kb_ib_{i+1}\ldots b_rb_1b_2\ldots b_{i-1},\qquad i\in \{1,\ldots, r\}, $$ tel que $ a_1a_2 \ldots a_k$ et $b_ib_{i+1}\ldots b_rb_1b_2\ldots b_{i-1}$ sont deux sous-mots de $w$. G\'eom\'etriquement m\'elanger deux cycles $\alpha$ et $\beta$ consiste \`a ins\'erer $\beta$ dans $\alpha$ (ou l'inverse) pour former un nouveau cycle de longueur $k+r$ en gardant la m\^eme orientation. %\vspace{1.5cm} \begin{example} Soient $\alpha=(1,2,3,4,5,6)$ et $\beta=(a,b,c,d,e)$. Alors $(1,c,2,3,4,d,e,5,6,a,b)$ est un m\'elange de $\alpha$ et $\beta$ (voir l'illustration Figure~1). \begin{figure}[!ht] $$ %\vspace{0.5cm} \setlength{\unitlength}{0.2mm} \begin{picture}(680,100)(170,700) \thinlines \put(230,770){\circle{25}}\put(225,765){1}\put(195,750){$\swarrow$} \put(185,735){\circle{25}}\put(180,730){2}\put(180,705){$\downarrow$} \put(185,685){\circle{25}}\put(180,680){3}\put(195,655){$\searrow$} \put(230,650){\circle{25}}\put(225,645){4}\put(245,655){$\nearrow$} \put(270,685){\circle{25}}\put(265,680){5}\put(265,705){$\uparrow$} \put(270,735){\circle{25}}\put(265,730){6}\put(245,750){$\nwarrow$} \put(195,600){cycle $\alpha$} %%%%%%%%%%%%%%%%%%%%%%%% \put(400,770){\circle{25}}\put(395,765){a}\put(365,750){$\swarrow$} \put(355,735){\circle{25}}\put(350,730){b} \put(354.7,715){\line(0, -1){ 40}}\put(350,675){$\downarrow$} \put(355,650){\circle{25}}\put(350,645){c} \put(375,650){\line(1, 0){ 40}}\put(410,645){$\rightarrow$} \put(445,650){\circle{25}}\put(440,645){d} \put(440,700){$\uparrow$}\put(444.8,670){\line(0, 1){ 40}} \put(445,735){\circle{25}}\put(440,730){e}\put(415,750){$\nwarrow$} \put(370,600){cycle $\beta$} \put(500,700){$\Longrightarrow$} %%%%%%%%%%%%%%%%%%%%%%%%%%% \put(700,790){\circle{25}}\put(695,785){1}\put(665,785){$\leftarrow$} \put(650,790){\circle{25}}\put(645,785){c}\put(615,770){$\swarrow$} \put(750,790){\circle{25}}\put(745,785){b}\put(715,785){$\leftarrow$} \put(605,755){\circle{25}}\put(600,750){2}\put(600,725){$\downarrow$} \put(605,705){\circle{25}}\put(600,700){3}\put(600,675){$\downarrow$} \put(605,655){\circle{25}}\put(600,650){4}\put(625,650){$\rightarrow$} \put(665,655){\circle{25}}\put(660,650){d}\put(685,650){$\rightarrow$} \put(725,655){\circle{25}}\put(720,650){e}\put(745,650){$\rightarrow$} \put(785,655){\circle{25}}\put(780,650){5}\put(790,675){$\nearrow$} \put(815,705){\circle{25}}\put(810,700){6}\put(810,725){$\uparrow$} \put(815,755){\circle{25}}\put(810,750){a}\put(775,775){$\nwarrow$} \put(620,600){un m\'elange de $\alpha$ et $\beta$} %\put(400,550){{\bf Figure 1:} Un m\'elange de deux cycles} \end{picture} $$ \vspace{1.5cm} \caption{Un m\'elange de deux cycles}\label{fig1} \end{figure} \end{example} \begin{lem}\label{com} Soient $\alpha$ et $\beta$ deux cycles de supports disjoints et de longueur $k$ et $r$ respectivement. Alors le nombre de m\'elanges de $\alpha$ et $\beta$ est donn\'e par $$ F_k(r)= \frac{(k+r-1)!}{(k-1)!(r-1)!}=k\binom{k+r-1}{r-1}=r\binom{k+r-1}{k-1}. $$ \end{lem} \noindent En effet, il y a $(k+r-1)!$ mani\`eres de constituer un cycle \`a l'aide de $k+r$ \'el\'ements, mais l'ordre des cycles initiaux de longueurs $k$ et $r$ devant \^etre respect\'e, on obtient le r\'esultat. \begin{remark} Comme $\binom{k+r}{k}$ compte le nombre de mani\`eres de m\'elanger deux chemins orient\'es de longueur~$k$ et $r$, respectivement, pour obtenir un chemin orient\'e de longueur~$k+r$, on pourrait appeler $F_k(r)$ \emph{coefficient binomial cyclique}. Or, il semble difficile d'interpr\'eter $F_k(r)$ dans le contexte des coefficients binomiaux g\'en\'eralis\'es de~\cite{AU}. En effet, $\binom{k+r}{k} = \binom{X^{k+r}}{X^k}$, o\`u $X^k$ est un chemin orient\'e avec $k$~sommets, mais le coefficient binomial cyclique de~\cite{AU}, \`a savoir $\binom{C_{k+r}}{C_k}$ ($C_k$ est un circuit orient\'e avec $k$~sommets), est \'egal \`a $1$ si $k$ est un diviseur de $k+r$ et \'egal \`a $0$ sinon. \end{remark} La notion de m\'elange a l'avantage d'\^etre sym\'etrique par rapport aux deux cycles, mais on aura besoin d'une variante asym\'etrique du m\'elange dans la suite. Dans un m\'elange $\gamma$ de deux cycles $\alpha$ et $\beta$, un sommet $a$ de $\alpha$ est \emph{$\beta$-d\'ecor\'e} par un sommet $b$ de $\beta$ s'il existe un arc $b\to a$. La $\beta$-\emph{d\'ecoration} de $\alpha$ associ\' ee \`a $\gamma$ est le graphe $\gamma'$ obtenu en posant $\gamma'(b)=\gamma(b)$ pour tout $b$ de $\beta$ ainsi que $\gamma'(a)=\alpha(a)$ pour tout $a$ de $\alpha$. \begin{example} On reprend l'exemple de la Figure~\ref{fig1}. Les \'el\'ements 1, 2 et 5 sont d\'ecor\'es par $b$, $c$ et $e$ respectivement. \begin{figure}[!ht] $$ \vspace{0.5cm} \setlength{\unitlength}{0.2mm} \begin{picture}(680,120)(170,700) %\thinlines \put(260,790){\circle{25}}\put(255,785){1}\put(225,785){$\leftarrow$} \put(210,790){\circle{25}}\put(205,785){c}\put(175,770){$\swarrow$} \put(310,790){\circle{25}}\put(305,785){b}\put(275,785){$\leftarrow$} \put(165,755){\circle{25}}\put(160,750){2}\put(160,725){$\downarrow$} \put(165,705){\circle{25}}\put(160,700){3}\put(160,675){$\downarrow$} \put(165,655){\circle{25}}\put(160,650){4}\put(185,650){$\rightarrow$} \put(225,655){\circle{25}}\put(220,650){d}\put(245,650){$\rightarrow$} \put(285,655){\circle{25}}\put(280,650){e}\put(305,650){$\rightarrow$} \put(345,655){\circle{25}}\put(340,650){5}\put(350,675){$\nearrow$} \put(375,705){\circle{25}}\put(370,700){6}\put(370,725){$\uparrow$} \put(375,755){\circle{25}}\put(370,750){a}\put(335,775){$\nwarrow$} \put(450,700){$\Longrightarrow$} %%%%%%%%%%%%%%%%%%%%%%%%%% \put(630,770){\circle{25}}\put(625,765){1}\put(595,750){$\swarrow$} \put(700,770){\circle{25}}\put(695,765){b}\put(650,765){$\longleftarrow$} \put(750,770){\circle{25}}\put(745,765){a}\put(715,765){$\leftarrow$} \put(585,735){\circle{25}}\put(580,730){2}\put(580,705){$\downarrow$} \put(515,735){\circle{25}}\put(510,730){c}\put(535,730){$\longrightarrow$} \put(585,685){\circle{25}}\put(580,680){3}\put(595,655){$\searrow$} \put(630,650){\circle{25}}\put(625,645){4}\put(645,655){$\nearrow$} \put(670,685){\circle{25}}\put(665,680){5}\put(665,705){$\uparrow$} \put(740,685){\circle{25}}\put(735,680){e}\put(690,680){$\longleftarrow$} \put(790,685){\circle{25}}\put(785,680){d}\put(755,680){$\leftarrow$} \put(670,735){\circle{25}}\put(665,730){6}\put(645,750){$\nwarrow$} %\put(200,600){{\bf Figure~2}: Un m\'elange de $\alpha$ et $\beta$ %et sa $\beta$-d\'ecoration de $\alpha$ correspondante} \end{picture} $$ \vspace{0.6cm} \caption{Un m\'elange de $\alpha$ et $\beta$ et sa $\beta$-d\'ecoration de $\alpha$ correspondante}\label{fig2} \end{figure} \end{example} %\vspace{1cm} \noindent La notion de d\'ecoration permet de donner une autre expression pour $F_k(r)$ comme suit~: $$ F_k(r)=\sum_{i\geq 1}i\binom{r}{i}\binom{k}{i}. $$ En effet, pour constituer une $\beta$-d\'ecoration de $\alpha$ ayant $i$ \'el\'ements $\beta$-d\'ecor\'es, on peut d'abord choisir ces \'el\'ements dans $\alpha$ de $\binom{k}{i}$ mani\`eres, et puis choisir les $i$ \'el\'ements du cycle $\beta$ les d\'ecorant de $\binom{r}{i}$ mani\`eres. Il ne reste plus qu'\`a associer cycliquement ces deux familles de $i$ \'el\'ements, ce qui donne $i$ choix, et ceci d\'emontre l'identit\'e ci-dessus. \begin{remark} On aurait pu aussi d\'eduire la formule pr\'ec\'edente du lemme~2 en partant du membre de droite et en utilisant la formule de Chu-Vandermonde. Inversement on obtient une preuve combinatoire de cette derni\`ere sous la forme suivante~: $$ \sum_{i\geq 1}i\binom{r}{i}\binom{k}{i}=k\binom{k+r-1}{r-1}=r\binom{k+r-1}{k-1}. $$ \end{remark} Consid\'erons maintenant une g\'en\'eralisation de la notion de m\'elange ou d\'ecoration comme suit. Soient $\alpha, \beta_1, \ldots, \beta_m$ des cycles de supports deux \`a deux disjoints. On note {\boldmath $\beta$}=$(\beta_1,\ldots, \beta_m) $ et on d\'efinit une \emph{{\boldmath $\beta$}-d\'ecoration} de $\alpha$ comme \'etant le graphe obtenu en d\'ecorant $\alpha$ par chacun de ces $m$ cycles. De plus, on dit qu'une {\boldmath $\beta$}-d\'ecoration de $\alpha$ est \emph{surjective} si chaque sommet de $\alpha$ est d\'ecor\'e par au moins un sommet des cycles $\beta_1,\ldots, \beta_m$. \begin{example} Soient $\alpha=(1,\dots,6)$, $\beta_1=(a,b,c,d,e)$ et $\beta_2=(x,y,z,t)$. Consid\'erons les $\beta_1$-d\'ecoration et $\beta_2$-d\'ecoration suivantes de $\alpha$ ainsi que la $(\beta_1,\beta_2)$-d\'ecoration de $\alpha$ correspondante~: \begin{figure}[!ht] $$ \vspace{0.5cm} \setlength{\unitlength}{0.2mm} \begin{picture}(680,100)(100,700) \thinlines \put(250,770){\circle{25}}\put(245,765){1}\put(215,750){$\swarrow$} \put(320,770){\circle{25}}\put(315,765){b}\put(270,765){$\longleftarrow$} \put(370,770){\circle{25}}\put(365,765){a}\put(335,765){$\leftarrow$} \put(205,735){\circle{25}}\put(200,730){2}\put(200,705){$\downarrow$} \put(135,735){\circle{25}}\put(130,730){c}\put(155,730){$\longrightarrow$} \put(205,685){\circle{25}}\put(200,680){3}\put(215,655){$\searrow$} \put(250,650){\circle{25}}\put(245,645){4}\put(265,655){$\nearrow$} \put(290,685){\circle{25}}\put(285,680){5}\put(285,705){$\uparrow$} \put(360,685){\circle{25}}\put(355,680){e}\put(310,680){$\longleftarrow$} \put(410,685){\circle{25}}\put(405,680){d}\put(375,680){$\leftarrow$} \put(290,735){\circle{25}}\put(285,730){6}\put(265,750){$\nwarrow$} \put(180,600){$\beta_1$-d\'ecoration de $\alpha$} %%%%%%%%%%%%%%%%%%%%%%%%%% \put(630,770){\circle{25}}\put(625,765){1}\put(595,750){$\swarrow$} \put(560,770){\circle{25}}\put(555,765){$x$}\put(580,765){$\longrightarrow$} \put(585,735){\circle{25}}\put(580,730){2}\put(580,705){$\downarrow$} \put(585,685){\circle{25}}\put(580,680){3}\put(595,655){$\searrow$} \put(515,685){\circle{25}}\put(510,680){$y$}\put(535,680){$\longrightarrow$} \put(630,650){\circle{25}}\put(625,645){4}\put(645,655){$\nearrow$} \put(700,650){\circle{25}}\put(695,645){$z$}\put(650,645){$\longleftarrow$} \put(670,685){\circle{25}}\put(665,680){5}\put(665,705){$\uparrow$} \put(670,735){\circle{25}}\put(665,730){6}\put(645,750){$\nwarrow$} \put(740,735){\circle{25}}\put(735,730){$t$}\put(690,730){$\longleftarrow$} \put(560,600){$\beta_2$-d\'ecoration de $\alpha$} \end{picture} $$ \vspace{2cm} $$ \setlength{\unitlength}{0.2mm} \begin{picture}(680,100)(120,700) \thinlines \put(450,770){\circle{25}}\put(445,765){1}\put(415,750){$\swarrow$} \put(520,770){\circle{25}}\put(515,765){b}\put(470,765){$\longleftarrow$} \put(570,770){\circle{25}}\put(565,765){a}\put(535,765){$\leftarrow$} \put(450,820){\circle{25}}\put(445,815){$x$}\put(445,790){$\downarrow$} \put(405,735){\circle{25}}\put(400,730){2}\put(400,705){$\downarrow$} \put(335,735){\circle{25}}\put(330,730){c}\put(355,730){$\longrightarrow$} \put(405,685){\circle{25}}\put(400,680){3}\put(415,655){$\searrow$} \put(335,685){\circle{25}}\put(330,680){$y$}\put(355,680){$\longrightarrow$} \put(450,650){\circle{25}}\put(445,645){4}\put(465,655){$\nearrow$} \put(520,650){\circle{25}}\put(515,645){$z$}\put(470,645){$\longleftarrow$} \put(490,685){\circle{25}}\put(485,680){5}\put(485,705){$\uparrow$} \put(560,685){\circle{25}}\put(555,680){e}\put(510,680){$\longleftarrow$} \put(610,685){\circle{25}}\put(605,680){d}\put(575,680){$\leftarrow$} \put(490,735){\circle{25}}\put(485,730){6}\put(465,750){$\nwarrow$} \put(560,735){\circle{25}}\put(555,730){$t$}\put(510,730){$\longleftarrow$} %\put(300,600){{\bf Figure~3}: Une $(\beta_1,\beta_2)$-d\'ecoration %de $\alpha$ } \end{picture} $$ \vspace{1.5cm} \caption{Une $(\beta_1,\beta_2)$-d\'ecoration de $\alpha$}\label{fig3} \end{figure} \end{example} \noindent On notera que cette d\'ecoration est surjective, alors que celle de la Figure~\ref{fig2} ne l'\'etait pas. %\vspace{2cm} \begin{prop} Soient $\alpha,\beta_1,\ldots,\beta_m$ des cycles de longueur $k,r_1,\ldots,r_m$ respectivement, et de supports deux \`a deux disjoints. Si $F_k ({\bf r})$ (resp.~$S_k ({\bf r})$) est le nombre de {\boldmath $\beta$}-d\'ecorations (resp.~surjectives) de $\alpha$, alors on a \begin{equation}\label{eq:comvide} F_k ({\bf r})=\prod_{i=1}^mF_{k} ({r_i})= \prod_{l=1}^m r_l \binom{k+r_l-1}{r_l}, \end{equation} et \begin{equation}\label{eq:comnonvide} S_k ({\bf r})= \sum_{i=1}^k (-1)^{k-i} \binom{k}{i} \prod_{l=1}^m r_l \binom{i+r_l-1}{r_l}. \end{equation} \end{prop} \noindent En effet, d'apr\`es le lemme~\ref{com} la formule (\ref{eq:comvide}) est \'evidente car les $m$ d\'ecorations sont ind\'ependantes les unes des autres. D'autre part, il est clair que le nombre de {\boldmath $\beta$}-d\'ecorations de $\alpha$ ayant $i$ sommets d\'ecor\'es est $\binom{k}{i}S_i({\bf r})$, donc $F_k ({\bf r}) = \sum_{i=1}^k \binom{k}{i} S_i ({\bf r})$ et par inversion on obtient $$ S_k ({\bf r})= \sum_{i=1}^k (-1)^{k-i} \binom{k}{i} F_i ({\bf r}), $$ qui permet de d\'eduire (\ref{eq:comnonvide}) par substitution de (\ref{eq:comvide}). Interpr\'etons maintenant le membre de gauche de (\ref{eq:bigeq}) \`a l'aide du mod\`ele pr\'ec\'edent. Pour tout entier positif $n$ on note $[n]$ l'ensemble $\{1,2,\ldots, n\}$. Un $\cal L$-\emph{complexe} sur $[n]$ est un triplet $(\sigma, \alpha, {\mbox{\boldmath $\beta$} })$, o\`u $\sigma$ est une permutation de $[n]$, $\alpha$ un cycle de $\sigma$ et {\boldmath $\beta$} est une suite de $m$ cycles qui d\'ecorent $\alpha$. \'Etant donn\'ee une partition $\mu$ de $n$, il y a $n!/z_\mu$ permutations de $[n]$ de type $\mu$, c'est-\`a dire ayant $m_i(\mu)$~cycles de longueur $i$ ($1\leq i\leq n$). Choisissons un cycle (de longueur $\mu_i$) \`a d\'ecorer parmi les $l(\mu)$ possibles, les autres cycles \'etant compt\'es \`a l'aide de la variable $X$. La fonction g\'en\'eratrice des $\cal L$-\emph{complexes} sur $[n]$ selon le nombre de cycles non d\'ecor\'es est \'egale \`a $$ \sum_{|\mu|=n}\frac{n!}{z_\mu} X^{l(\mu)-1} \sum_{i=1}^{l(\mu)} F_{\mu_i} ({\bf r}). $$ D'autre part, on pourrait construire un $\cal L$-complexe de $[n]$ en constituant d'abord un $k$-cycle \`a d\'ecorer. Il y a $(k-1)!\binom{n}{k}$ mani\`eres diff\'erentes de choisir ces \'el\'ements, et de les placer sous forme de cycle, qu'on d\'ecore ensuite de $F_k({\bf r})$ fa\c cons (cf. proposition~2). Enfin, comme la fonction g\'en\'eratrice des permutations des $n-k$ \'el\'ements restants selon le nombre de cycles est $(X)_{n-k}$, on obtient donc l'identit\'e (\ref{eq:las0'}), i.e., \begin{equation} \sum_{|\mu|=n}\frac{n!}{z_\mu} X^{l(\mu)-1} \sum_{i=1}^{l(\mu)} F_{\mu_i} ({\bf r}) =\sum_{k=1}^n F_k ({\bf r}) (k-1)! \binom{n}{k} (X)_{n-k}.\label{eq:vraif} \end{equation} Rappelons le r\'esultat suivant, d\^u \`a Berge~\cite{B}, Foata et Strehl~\cite{FS} (voir aussi \cite[p. 91]{BLL} et \cite{C,CG,L} pour d'autres g\'en\'eralisations r\'ecentes)~: \begin{equation}\label{eq:berge} \sum_{f} X^{{\mathrm{cyc}}\, f} = (X+k)_{n-k}, \end{equation} o\`u la somme porte sur toutes les injections $f: [n-k] \to [n]$ ($\mathrm{cyc}\, f$ est le nombre de cycles de~$f$). En notant que ces injections peuvent \^etre d\'ecompos\'ees en cycles et en $k$ chemins (dont certains peuvent \^etre vides), on peut en pr\'esenter une preuve rapide~: \begin{equation*} \exp \left[ X \sum_{i\geq 1} (i-1)! \frac{t^i}{i!} \right] \left[ 1+ \sum_{i\geq 1} i! \frac{t^i}{i!} \right]^k = \exp\left[ -X\log(1-t) \right] ( 1-t )^{-k} \nonumber \end{equation*} \begin{equation*} = (1-t )^{-X-k} =1 + \sum_{i\geq 1} (X+k)_i \frac{t^i}{i!}. \nonumber \end{equation*} Afin d'interpr\'eter le membre de droite de (\ref{eq:bigeq}) on a besoin d'une notion plus subtile que celle de d\'ecoration. Soit $\gamma'$ une $\beta$-d\'ecoration de $\alpha$. Associons \`a $\gamma'$ son \emph{squelette} $\gamma''$ en posant $\gamma''(b)=\gamma'(b)$ pour tout $b$ de $\beta$ ainsi que $\gamma''(a)=\gamma'(a)$ pour tout $a$ de $\alpha$ qui n'est pas $\beta$-d\'ecor\'e. En revanche, si $a$ de $\alpha$ est $\beta$-d\'ecor\'e, alors nous posons $\gamma''(a)=\gamma'^{p}(a)$ o\`u $p$ est le plus petit entier positif pour lequel $\gamma'^{p}(a)$ est $\beta$-d\'ecor\'e. \begin{example} On reprend l'exemple de la Figure~\ref{fig2}: le squelette obtenu a pour cycle $(1,2,5)$. \begin{figure}[!ht] $$ \setlength{\unitlength}{0.2mm} \begin{picture}(680,100)(170,700) \put(280,770){\circle{25}}\put(275,765){1}\put(245,750){$\swarrow$} \put(350,770){\circle{25}}\put(345,765){b}\put(300,765){$\longleftarrow$} \put(400,770){\circle{25}}\put(395,765){a}\put(365,765){$\leftarrow$} \put(235,735){\circle{25}}\put(230,730){2}\put(230,705){$\downarrow$} \put(165,735){\circle{25}}\put(160,730){c}\put(185,730){$\longrightarrow$} \put(235,685){\circle{25}}\put(230,680){3}\put(245,655){$\searrow$} \put(280,650){\circle{25}}\put(275,645){4}\put(295,655){$\nearrow$} \put(320,685){\circle{25}}\put(315,680){5}\put(315,705){$\uparrow$} \put(390,685){\circle{25}}\put(385,680){e}\put(340,680){$\longleftarrow$} \put(440,685){\circle{25}}\put(435,680){d}\put(405,680){$\leftarrow$} \put(320,735){\circle{25}}\put(315,730){6}\put(295,750){$\nwarrow$} \put(480, 700){$\Longrightarrow$} \put(650,750){\circle{25}}\put(645,745){1}\put(615,730){$\swarrow$} \put(720,750){\circle{25}}\put(715,745){b}\put(670,745){$\longleftarrow$} \put(770,750){\circle{25}}\put(765,745){a}\put(735,745){$\leftarrow$} \put(650,800){\circle{25}}\put(645,795){6}\put(645,770){$\downarrow$} \put(605,715){\circle{25}}\put(600,710){2}%\put(400,525){$\downarrow$} \put(535,715){\circle{25}}\put(530,710){c}\put(555,710){$\longrightarrow$} \put(695,715){\circle{25}}\put(690,710){5}\put(635,710){$\longrightarrow$} \put(650,665){\circle{25}}\put(646,660){4}\put(660,685){$\nearrow$} \put(600,665){\circle{25}}\put(598,660){3}\put(615,660){$\rightarrow$} \put(765,715){\circle{25}}\put(760,710){e}\put(715,710){$\longleftarrow$} \put(815,715){\circle{25}}\put(810,710){d}\put(780,710){$\leftarrow$} \put(665,730){$\nwarrow$} %\put(300,610){{\bf Figure~4}: Une %$\beta$-d\'ecoration de $\alpha$ et son squelette} \end{picture} $$ \vspace{1.5cm} \caption{Une $\beta$-d\'ecoration de $\alpha$ et son squelette}\label{fig4} \end{figure} \end{example} %\vspace{1.5cm} On d\'efinit de fa\c con analogue le \emph{squelette} d'une $(\beta_1, \ldots, \beta_m)$-d\'ecoration de $\alpha$, o\`u $\alpha, \beta_1,\ldots, \beta_m$ sont des cycles de supports deux \`a deux disjoints et $\beta_i$ est de longueur $r_i$ pour $1\leq i\leq m$. Interpr\'etons maintenant le membre de droite de (\ref{eq:bigeq}). Pour construire un $\cal L$-complexe sur $[n]$ on peut d'abord former le $k$-cycle $\delta$ du squelette du cycle $\alpha$ d\'ecor\'e. Il y a $(k-1)!\binom{n}{k}$ mani\`eres diff\'erentes de former un tel cycle. On d\'ecore ensuite $\delta$ de $S_k({\bf r})$ fa\c cons (cf. proposition~2), car le cycle du squelette est par d\'efinition {\boldmath $\beta$}-d\'ecor\'e surjectivement. Enfin, comme la fonction g\'en\'eratrice des injections de $n-k$ \'el\'ements restant dans les $k$ \'el\'ements de $\delta$ selon le nombre de cycles est $(X+k)_{n-k}$ (voir \eqref{eq:berge}), on a \'etabli le r\'esultat suivant. \begin{thm} La fonction g\'en\'eratrice des $\cal L$-complexes sur $[n]$ selon le nombre de cycles non d\'ecor\'es peut s'exprimer comme suit~: \begin{equation} \sum_{|\mu|=n}\frac{n!}{z_\mu} X^{l(\mu)-1} \sum_{i=1}^{l(\mu)} F_{\mu_i} ({\bf r}) = \sum_{k=1}^n S_k ({\bf r}) (k-1)!\binom{n}{k} (X+k)_{n-k}. \label{eq:vrais} \end{equation} \end{thm} Par comparaison avec (\ref{eq:bigeq}), on en d\'eduit alors que \begin{equation} \label{eq:last} c_k^{({\bf r})} = \frac{|{\bf r}|} {k\cdot \prod_{j} r_{j}} S_k ({\bf r}) = \sum_{j=1}^m \frac{S_k ({\bf r})\cdot r_j} {k \cdot r_1 \cdots r_m}, \end{equation} ce qui montre que $c_k^{({\bf r})}$ est positif et ne d\'epend pas de~$n$, et par substitution de (\ref{eq:comnonvide}), on retrouve les formules du corollaire~2, dont la derni\`ere, \`a savoir (\ref{eq:entiere}), montre que $c_k^{({\bf r})}$ est un entier. \medskip En fait, nous pouvons renforcer le dernier r\'esultat, c'est-\`a-dire la conjecture de Lassalle en supposant que le support de chacun des cycles $\delta$, $\beta_1,\;\ldots,\; \beta_m$ est \emph{totalement ordonn\'e}. \begin{thm} Soit $T_k({\bf r};j)$ le nombre de $(\beta_1, \ldots, \beta_m)$-d\'ecorations surjectives de $\delta$ telles que le plus grand \'el\'ement d\'ecorant de $\beta_j$ d\'ecore le plus grand \'el\'ement de $\delta$, et le plus grand \'el\'ement de tout autre cycle d\'ecore le plus grand \'el\'ement de $\delta$ d\'ecor\'e par ce cycle. Alors on a $$ T_k({\bf r};j)=\frac{S_k ({\bf r})\cdot r_j}{k \cdot r_1 \cdots r_m}, \qquad \hbox{pour}\quad 1\leq j\leq m. $$ \end{thm} \begin{proof}[Preuve] Il suffit de regarder l'action de la permutation cyclique $\delta$ ainsi que l'action de la permutation cyclique $\beta_i$ pour tout $i\not= j$. \end{proof} La formule (\ref{eq:last}) montre par le th\'eor\`eme~3 que nous avons trouv\'e une interpr\'etation combinatoire pour $c_k^{({\bf r})}=\sum_{j=1}^mT_k({\bf r};j)$. \bigskip On suppose maintenant que $p$ \'el\'ements de $[n]$ sont marqu\'es d'une \'etoile, dont au moins un par cycle de la permutation de type $\mu$. Ceci donne la fonction g\'en\'eratrice suivante $$ \sum_{\left|{\mu }\right| = n} \genfrac{\langle}{\rangle}{0pt}{}{\mu}{p} {\frac{n!}{{z}_{\mu }}} {X}^{l(\mu ) - 1} \left(\sum_{i = 1}^{l(\mu)} F_{\mu_i} ({\bf r}) \right). $$ On peut d'autre part commencer par choisir les $p$~\'el\'ements marqu\'es, et noter~$i$ (resp.~$j$) le nombre d'\'el\'ements marqu\'es (resp.~non marqu\'es) parmi les $\mu_i$~ du cycle choisi pour \^etre d\'ecor\'e. Si l'on isole les \'el\'ements non marqu\'es de tous les autres cycles, alors la fonction g\'en\'eratrice est $$ \binom{n}{p} \sum_{i=1}^p \sum_{j=0}^{n-p} F_{i+j} ({\bf r}) (i+j-1)!\binom{p}{i}\binom{n-p}{ j} (X)_{p-i}. $$ Comme il y a $(p-i)(p-i+1)(p-i+2)\cdots (n-i-j-1) = (p-i)_{n-p-j}$ mani\`eres diff\'erentes de r\'eintroduire les $n-p-j$~\'el\'ements restants, on a d\'emontr\'e l'identit\'e suivante \begin{equation*} \sum_{\left|{\mu }\right| = n} \genfrac{\langle}{\rangle}{0pt}{}{\mu}{p} {\frac{n!}{{z}_{\mu }}} {X}^{l(\mu ) - 1} \left(\sum_{i = 1}^{l(\mu)} F_{\mu_i} ({\bf r}) \right) \nonumber \end{equation*} \begin{equation*}\label{eq:graf} \, = \, \binom{n}{p} \sum_{i=1}^p \sum_{j=0}^{n-p} F_{i+j} ({\bf r}) (p-i)_{n-p-j} (i+j-1)! \binom{p}{i}\binom{n-p}{j} (X)_{p-i}, \end{equation*} qui est exactement l'identit\'e (\ref{eq:las0''}). \begin{remark} Lorsque $m=1$ une preuve analogue de (\ref{eq:las0''}) a \'et\'e donn\'ee dans \cite{Z}. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Liens avec les coefficients de lin\'earisation} Remarquons d'abord qu'en posant $X=0$ dans l'\'equation (\ref{eq:las}) nous obtenons \begin{equation}\label{eq:poly} \prod_{i=1}^m\frac{(n)_{r_i}}{r_i!} = \frac{1}{|{\bf r}|}\sum_{k=0}^{|{\bf r}|} k\,c_k^{({\bf r})}\,\frac{\langle n\rangle_{k}}{k!}. \end{equation} Comme $c_k^{({\bf r})}$ est ind\'ependant de $n$, la d\'etermination de $c_k^{({\bf r})}$ appara\^{\i}t donc comme le calcul des coefficients du d\'eveloppement du polyn\^ome $(x)_{r_1}\cdots (x)_{r_m}$ dans la base $(\langle x\rangle_{k})_{k\geq 0}$. De plus, si nous pouvons d\'emontrer autrement que les nombres $c_k^{({\bf r})}$ sont ind\'ependants de $n$, cette approche fournirait une nouvelle preuve de la conjecture de Lassalle. Supposons $x$ entier positif et consid\'erons $m$ ensembles $E_1$, $E_2$, \dots, $E_m$, deux \`a deux disjoints et tels que card$(E_i) = r_i$ pour tout $i \in [m]$. Nous appelons une famille de fonctions $(f_1,\dots,f_m)$, $f_i : E_i \to [x]$ pour tout $i \in [m]$, injective si et seulement si chaque fonction $f_i$ est injective. Le nombre de familles de fonctions injectives vaut $\langle x\rangle_{r_1} \cdots \langle x\rangle_{r_m}$. D'autre part, nous pouvons poser $E = E_1 \cup \cdots \cup E_m$ et faire correspondre, de fa\c con bijective, \`a chaque famille de fonctions injectives une fonction $f : E \to [x]$ telle que, pour tout $j \in [x]$ et tout $i\in[m]$, card$(f^{-1}(j) \cap E_i) \in \{0,1\}$. Appelons de mani\`ere g\'en\'erale un sous-ensemble $T\subseteq E$ \emph{transversal} si card$(T \cap E_i) \in \{0,1\}$ pour tout $i \in [m]$. Ceci d\'emontre le th\'eor\`eme suivant. \begin{thm} Soit $d_k(r_1,\dots,r_m)$ le nombre de mani\`eres diff\'erentes de partitionner $E$ en $k$~transversaux non-vides, alors \begin{equation}\label{eq:linm} \langle x\rangle_{r_1}\cdots \langle x\rangle_{r_m} = \sum_{k\geq 0}d_k({\bf r}) \langle x\rangle_{k}. \end{equation} En particulier, nous avons la formule de lin\'earisation classique~: \begin{equation} \langle x\rangle_{r_1}\langle x\rangle_{r_2} =\sum_{k\geq 0}\binom{{r_1}}{k}\binom{{r_2}}{k}k! \langle x\rangle_{{r_1}+{r_2}-k}. \label{eq:lin2} \end{equation} \end{thm} \noindent En effet, pour $m=2$, s'il y a $k$~transversaux de cardinal deux et si le nombre total de transversaux vaut $r_1+r_2-k$, alors nous pouvons les choisir de $\binom{r_1}{k} \binom{r_2}{k} k!$ fa\c cons distinctes, c'est-\`a-dire $$ d_{r_1+r_2-k} (r_1,r_2) = \binom{r_1}{k} \binom{r_2}{k} k!. $$ Il est encore plus simple de choisir directement, de fa\c con ind\'ependante, $m$~sous-ensembles de~$[x]$ de cardinaux $r_1$, \dots, $r_m$, respectivement. Ceci est possible de $\binom{x}{r_1} \cdots \binom{x}{r_m}$ mani\`eres distinctes et montre le th\'eor\`eme suivant. \begin{thm} Soit $\tilde{d}_k({\bf r})$ le nombre de mani\`eres diff\'erentes de choisir $m$~sous-ensembles de~$[k]$ de cardinaux $r_1$, \dots, $r_m$, respectivement, de sorte que chaque \'el\'ement de~$[k]$ soit choisi au moins une fois. Alors \begin{equation}\label{eq:linbin} \binom{x}{r_1}\cdots \binom{x}{r_m} = \sum_{k\geq 0} \tilde{d}_k({\bf r}) \binom{x}{k}, \qquad \tilde{d}_k({\bf r}) = \frac{k! \, d_k({\bf r}) } {r_1! \cdots r_m!}. \end{equation} En particulier, on a $$ \tilde{d}_{r_1+r_2-k} (r_1,r_2) = \binom{r_1+r_2-k}{k,r_1-k,r_2-k}. $$ \end{thm} \noindent On peut aussi donner une preuve directe de ce dernier r\'esultat. En effet, choisir deux sous-ensembles $E_1$ et $E_2$ de~$[x]$ tels que $|E_1|=r_1$, $|E_2|=r_2$ et $|E_1\cap E_2|=k$ \'equivaut \`a choisir un sous-ensemble de~$[x]$ de cardinal~$r_1+r_2-k$ et puis le partitionner en trois blocs de cardinaux $k$, $r_1-k$, $r_2-k$, respectivement. D'o\`u $\tilde{d}_{r_1+r_2-k} (r_1,r_2) = \binom{r_1+r_2-k}{k,r_1-k,r_2-k}$. Au lieu de choisir, de fa\c con ind\'ependante, $r_1$, \dots, $r_m$ \'el\'ements de~$[x]$ sans r\'ep\'etition, choisissons-les maintenant avec des \emph{r\'ep\'etitions} possibles. Comme le nombre de fa\c cons de choisir $n$ \'el\'ements dans $[x]$ avec des r\'ep\'etitions possibles, c'est-\`a-dire le nombre de $n$-\emph{multi-ensembles} sur $[x]$ d'apr\`es Stanley~\cite[p. 15]{St}, est \begin{equation}\label{eq:repet} \left(\binom{x}{n}\right) = \binom{x+n-1}{n}=\frac{(x)_{n}}{n!}, \end{equation} le nombre de sc\'enarios distincts est donc \'egal \`a $\bigl(\binom{x}{r_1}\bigr) \cdots \bigl(\binom{x}{r_m}\bigr)$. D'autre part, le nombre de fa\c cons de choisir $k$ \'el\'ements dans $[x]$ sans r\'ep\'etition est $\binom{x}{k}$. On en d\'eduit le r\'esultat suivant. \begin{thm} Soit $\tilde{c}_k({\bf r})$ le nombre de mani\`eres diff\'erentes de choisir $r_1$, \dots, $r_m$ \'el\'ements de~$[k]$ avec des r\'ep\'etitions possibles, de sorte que chaque \'el\'ement de~$[k]$ soit choisi au moins une fois, alors \begin{equation}\label{eq:linlas} \biggl(\binom{x}{r_1}\biggr) \cdots \biggl( \binom{x}{r_m}\biggr) = \sum_{k\geq 0} \tilde{c}_k({\bf r}) \binom{x}{k}. \end{equation} \end{thm} \noindent On en d\'eduit en particulier pour $m=1$ \begin{equation}\label{eq:1} \tilde{c}_k(r_1)=\binom{r_1-1}{r_1-k}, \end{equation} d'apr\`es (\ref{eq:repet}), et pour $m=2$ \begin{equation} \tilde{c}_k({r_1, r_2})=\sum_{k_1+k_2=k+l}\binom{k}{l,k_1-l,k_2-l} \binom{r_1-1}{r_1-k_1}\binom{r_2-1}{r_2-k_2}. \end{equation} En effet, supposons que les choix de $r_1$ et $r_2$ \'el\'ements dans $[k]$ avec r\'ep\'etitions possibles ont respectivement $k_1$ et $k_2$ \'el\'ements distincts et $l$ \'el\'ements communs. Comme chaque \'el\'ement de $[k]$ doit \^etre choisi au moins une fois, ceci donne des couples $(E_1, E_2)$ de parties de $[k]$ tels que $$ |E_1|=k_1, \quad |E_2|=k_2,\quad |E_1\cap E_2|=l, \quad E_1\cup E_2=[k]. $$ Il y a clairement $\binom{k}{l,k_1-l,k_2-l}$ tels couples. Nous appliquons ensuite (\ref{eq:1}) \`a $E_1$ et $E_2$ respectivement, ce qui donne le nombre $\binom{r_1-1}{r_1-k_1}\binom{r_2-1}{r_2-k_2}$ de choix correspondant au couple $(E_1, E_2)$. \medskip \noindent Notons que l'identit\'e (\ref{eq:lin2}) s'\'ecrit encore \begin{equation}\label{eq:binom2} \frac{(x)_{r_1}}{r_1!} \frac{(x)_{r_2}}{r_2!} = \sum_{l\geq 0}(-1)^l \binom{r_1+r_2-l}{l,r_1-l,r_2-l} \frac{(x)_{r_1+r_2-l}}{(r_1+r_2-l)!}. \end{equation} En reportant (\ref{eq:binom2}) dans (\ref{eq:las}) nous d\'eduisons le r\'esultat suivant. \begin{lem} Les coefficients $c_k^{({\bf r})}$ satisfont la relation de r\'ecurrence suivante~: \begin{equation}\label{eq:recurr} \frac{c_k^{( r_1,r_2,r_3,\dots,r_m)}} {r_1+r_2+r_3+\cdots+r_m} = \sum_{l \ge 0} (-1)^l \binom{r_1+r_2-l}{l,r_1-l,r_2-l} \frac{c_k^{( r_1+r_2-l,r_3,\dots,r_m)}} {r_1+r_2 -l+r_3+\cdots+r_m}. \end{equation} En particulier, comme $c_k^{(r_1)}=\binom{r_1}{k}$ (voir (\ref{eq:m=1})), les coefficients $c_k^{({\bf r})}$ sont ind\'ependants de $n$. \end{lem} En vue de d\'eduire une nouvelle preuve de la conjecture de Lassalle, nous introduisons quelques notations suppl\'ementaires. Pour tout polyn\^ome $p(x)$ d\'efinissons les op\'erateurs $E$, $I$ et $\Delta$ comme suit~: $$E p(x) = p(x+1), \quad I p(x)=p(x)\quad \hbox{et}\quad \Delta =E-I. $$ Pour tout $k\geq 0$ posons $\Delta^0=I$ et $\Delta^{k+1}=\Delta(\Delta^k)$. La formule binomiale implique alors que \begin{equation}\label{eq:diff} \Delta^np(x) =(E-I)^np(x)= \sum_{k=0}^n(-1)^k\binom{n}{k}p(x+n-k), \end{equation} et d'autre part nous avons le d\'eveloppement de Taylor suivant~: \begin{equation}\label{eq:taylor} p(x) = \sum_{k\geq 0}\frac{\Delta^kp(0)}{ k!}\langle x\rangle_k. \end{equation} En appliquant (\ref{eq:diff}) et (\ref{eq:taylor}) au polyn\^ome $p(x)=(x)_{r_1}\cdots (x)_{r_m}$ nous obtenons \begin{equation}\label{eq:connex} \prod_{i=1}^m(x)_{r_i} = \sum_{k=0}^{|{\bf r}|} \left(\frac{1}{k!}\sum_{j=0}^k(-1)^j\binom{k}{ j} \prod_{i=1}^m (k-j)_{r_i}\right)\, \langle x\rangle_{k}. \end{equation} Gr\^ace au lemme~3 la comparaison de (\ref{eq:poly}) avec (\ref{eq:linlas}) et (\ref{eq:connex}) montre le th\'eor\`eme suivant. \begin{thm} On a d'une part \begin{equation}\label{eq:positive} c_k^{({\bf r})}=\frac{r_1+\cdots +r_m}{k}\tilde{c}_k({\bf r}), \end{equation} et d'autre part la formule explicite (\ref{eq:entiere}), c'est-\`a-dire, \begin{equation}\label{eq:entiere'} c_k^{({\bf r})}=\sum_{j=1}^m\sum_{i=1}^k (-1)^{k-i}\binom{k-1}{i-1}\binom{i+r_j-1}{r_j-1} \prod_{l=1,l\neq j}^m\binom{r_l+i-1}{r_l}. \end{equation} \end{thm} \noindent Il r\'esulte respectivement de (\ref{eq:entiere'}) et (\ref{eq:positive}) que $c_k^{({\bf r})}$ est entier et positif. \begin{remark} Il est \'evident que (\ref{eq:linlas}) et (\ref{eq:frederic3}) fournissent exactement les m\^emes interpr\'etations combinatoires pour les nombres $c_k^{({\bf r})}$. Enfin, des $q$-analogues naturels de ces coefficients ont \'et\'e introduits dans~\cite{HZ}. \end{remark} \noindent {\bf Remerciements}. Les auteurs remercient Pierre Leroux ainsi que les deux rapporteurs ano\-nymes pour leurs conseils avis\'es concernant la r\'edaction de la troisi\`eme section. \begin{thebibliography}{99} \bibitem{AAR} G.~Andrews, R.~Askey et R.~Roy, \emph{Special Functions}, Encyclopedia of Math. and its Applications, \textbf{71} (2000). \bibitem{AU} P.~Auger, G.~Labelle et P.~Leroux, \emph{Generalized binomial coefficients for molecular species}, Journal of Combinatorial Theory, Series A, Special Issue dedicated to the Memory of Professor G.-C.~Rota, \textbf{91} (2000), 15-48. \bibitem{B} C.~Berge, \emph{Chemins hamiltoniens}, ICC Research Report n$^o$ 67/2 (1967). \bibitem{BLL} F.~Bergeron, G.~Labelle et P.~Leroux, \emph{Th\'eo\-rie des esp\`eces et combinatoire des structures arborescentes}, Publ. LACIM, vol.~19, Montr\'eal (1994). \bibitem{C} T.~Chow, \emph{The path-cycle symmetric function of a digraph}, Advances in Mathematics, \textbf{118} (1996), 71-98. \bibitem{CG} F.~R.~K.~Chung et R.~L.~Graham, \emph{On the cover polynomial of a digraph}, Journal of Combinatorial Theory, Series B, \textbf{65} (1995), 273-290. \bibitem{Ei} T.~Eisenk\"olbl, \emph{Proof of a partition identity conjectured by Lassalle}, arXiv:math.CO/9903019. \bibitem{FS} D.~Foata et V.~Strehl, \emph{Combinatorics of Laguerre polynomials}, in Enumeration and design (Waterloo, Ont., 1982), Academic Press, Toronto, ON, 1984, 123--140. \bibitem{HZ} S. J. X.~Hou et J.~Zeng, \emph{Two new families of q-positive integers}, arXiv:math.CO/0403064. \bibitem{JZ} F.~Jouhet et J.~Zeng, \emph{G\'en\'eralisation de formules de type Waring}, S\'eminaire Lotharingien de Combinatoire {\bf 44}, 2000. \bibitem{L} B.~Lass, \emph{Variations sur le th\`eme E+$\overline E$ = XY}, Advances in Applied Mathematics, \textbf{29} (2002), 215-242. \bibitem{La00} M. Lassalle, \emph{Une identit\'e en th\'eorie des partitions}, Journal of Combinatorial Theory, Series A, \textbf{89} (2000), 270--288. \bibitem{La02} M. Lassalle, \emph{A new family of positive integers}, Ann. Combin. \textbf{6} (2002), 399--405. \bibitem{Ma} I.~G.~Macdonald, \emph{Symmetric Functions and Hall Polynomials}, Second Edition, Oxford Science Publications, 1995. \bibitem{Macmahon} M.~P.~MacMahon, \emph{Combinatory analysis}, reprinted by Chelsea Publ. Company, 1960. \bibitem{St} R.~Stanley, \emph{Enumerative Combinatorics}, vol. 1, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, 1997. \bibitem{Z} J.~Zeng, \emph{A bijective proof of Lassalle's partition identity}, Journal of Combinatorial Theory, Series A, \textbf{89} (2000), 289--290. \end{thebibliography} \end{document}