% Motzkin 3 juillet 2000 corrections 18 juillet % Plain Tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \magnification=1200 %\overfullrule 0mm \frenchspacing \def\s{\scriptstyle } \def\ff{ f^{\l,n}} \def\WW{{\cal W}(\l,n)} \def\ss{\sigma} \def\a{\alpha} \def\b{\beta} \def\l{\lambda} \def\L{\Lambda} \def\e{\epsilon} \def\y{\xi} \def\vt{\vartheta} \font\goth=eufm10 \font\sgoth=eufm10 at 7pt \font\bb=msbm10 \font\sbb=msbm10 at 7pt \def\N{\hbox{\bb N}} \def\Z{\hbox{\bb Z}} \def\C{\hbox{\bb C}} \def\R{\hbox{\bb R}} \def\A{\hbox{\bb A}} \def\sA{\hbox{\sbb A}} \def\sS{\hbox{\sgoth S}} \def\S{\hbox{\goth S}} \def\Sym{\hbox{\goth Sym}} \def\MP{Motzkin paths } \def\dsp{\displaystyle } \def\moins{\! -\!} \def\plus{\! +\!} \def\Def{\noindent{\it Definition.}\ } \def\kk{\quad} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \centerline{\bf Motzkin paths and powers of continued fractions} \medskip \centerline{\bf Alain Lascoux} \bigskip\noindent Abstract. \ \it We show that the combinatorial description of cumulants by Lehner, in terms of Motzkin paths, can be extended to the description of powers of continued fractions. \bigskip\rm Given an alphabet $\A =\{ a\}$, let $\L^n(A)$, $n=0,1,2,\ldots$, be the $n$-th {\it elementary symmetric function} in $\A$, i.e. the coefficient of $x^n$ in $\l_x(A):=\prod_{a\in\sA} (1+ax)$. Let furthemore the {\it complete functions} $S^n(\A)$ be the coefficients of $\sigma_x(\A)=\prod_{a\in\sA} 1/(1-ax)$ and, for any $k\in\R$, let $\L^n(k\A)$ be the coefficient of of $x^n$ in $\l_x(k\A):= (\l_x(\A))^k$. We wish to express the symmetric function $\L^n(k\A)$ in terms of the coefficients of the continued fraction expression of $$ \sigma_x(\A)= \sum x^n S^n(\A) := {1\over \l_{-x}(\A)} = \qquad{}{1\over \dsp (1-\a _0 x)- {\strut x^2\y_1\over \dsp (1-\a_1x)- {\strut x^2\y_2\over \dsp (1-\a_2x)- {\strut x^2\y_3\over \dsp \ddots}}}} \eqno (1) $$ i.e. we wish to give the expansion of the $k$-th power of the continued fraction on the right. \smallskip Wronski [Wr] determined the parameters $\a_0,\a_1,\ldots$, $\y_1,\y_2,\ldots$ as symmetric functions of $\A$ (see [L1] for a translation) and produced an algorithm (essentially Euclidean division) to generate them. Flajolet ([Fl]; see also [FV], [Vi], [GJ]) has given a combinatorial interpretation of the complete functions $S^n(\A)$ in terms of the parameters $\a_i,\y_j$, that we shall use after recalling the necessary definitions. First, we shall let the cardinality of $\A$ tend toward infinity, so that the elementary symmetric functions are algebraically independent. \smallskip \Def {\it \MP} are paths in the positive integral plane, with East, North-East and South-East steps, starting and finishing at level zero. A {\it weight} is attributed to each step: $\a_i$ for an horizontal step at level $i$, $\y_i$ for a South-East step between level $i$ and $i-1$. The {\it weight} of the path itself is the product of the weights of its steps. An {\it irreducible Motzkin path} is a path which does not touch level zero, except at both ends. One can also write a path as a word, recording the levels attained at each quantum step. For example $$\matrix{ & &&&&&& 3&3&3&3\cr & &&&2&&2& &&&& 2 & &2 \cr & & 1&1&&1&&&&&& & 1 &&1\cr & 0 &&&&&&&&&&&&&& 0\cr\cr {\s word} & 0 &1 &1 &2 &1&2&3 &3 &3 &3 &2 &1 &2 &1 &0\cr {\s weight}& &\kk\a_1 & &\kk\y_2 & & &\kk\a_3 &\kk\a_3&\kk\a_3&\kk\y_3&\kk\y_2&&\kk\y_1&\kk\y_0 }$$ It is clear that \MP can be uniquely factored into irreducible paths, level zero points being the cutting points. When we write an equality between a function in the $\a_i,\y_j$ and a sum of paths, we shall mean that one has to replace each path by its weight in the later. \medskip \noindent Theorem (Flajolet [Fl]). \sl For any $n\in \N$, the complete function $S_n(\A)$ is equal to the sum of \MP of length $n$, the parameters $\a_i,\y_j$ being defined by (1). \rm \medskip The concatenation product of paths is not commutative. To recover a ring of symmetric functions from the preceding combinatorial interpretation of complete functions, it suffices to take the commutative algebra with the irreducible \MP as generators (one also has theories of non commutative symmetric functions !). Any symmetric polynomial in $\A$ can now be interpreted as a polynomial function of in the irreducible Motzkin paths. We shall write $\equiv$ when allowing commutation of \MP. \setbox2=\hbox{ sum of all irreducible \MP of length $n$} For example, since $1/\sigma_x(\A) = \l_{-x}(\A)$, then $$(-1)^{n-1} \L^n(\A) \equiv \ \box2 \eqno(2)$$ The hook-Schur functions $S_{j+1,1^i}$ are expressible as $$ S_{j+1,1^i} = \L^{i+1} S^j - \L^{i+2} S^{j-1} +\ \cdots +\pm \L^{i+j+1} S^0 \eqno(3) $$ Each term of the sum (3) can be interpreted as the sum of all \MP with first return to level 0 in position $i+1, i+2, i+3, \ldots$ respectively. Therefore $$ (-1)^i\, S_{j+1,1^i}(\A) \equiv \sum\nolimits_{\vt(w)\geq i+1} w \ , \eqno(4) $$ sum over all \MP $w$ of length $i+j+1$, $\vt(w)$ denoting the position of the first return to level 0. A power sum $\psi_n$ is equal to the alternating sum of all hook-Schur functions of degree $n$ (i.e. $\psi_n= S_n- S_{n-1,1} + S_{n-2,1,1} -\cdots$). Therefore, one gets from (4): $$ \psi_n(\A)= \sum\nolimits_{w:\, length(w)=n} \vt(w)\, w \eqno(5) $$ \medskip The Cauchy formula allows to expand elementary or complete functions of a product of two alphabets. In particular, it gives several expansions of the $\L^n(k\A)$, $k\in \R$ (these functions can be interpreted as coefficients of the powers of the Lagrange inverse of $x\sigma_x(\A)$, see [L2]). The Cauchy formula says that $$ \L^n(k\A) = \sum_{m_1,m_2,\ldots} {k(k-1)\cdots (k-\ell+1)\over m_1! m_2! \cdots} (\L^1(\A))^{m_1} (\L^2(\A))^{m_2} \cdots \ ,\eqno(6) $$ sum over all partitions $1^{m_1} 2^{m_2}\cdots $ of weight $1m_1+2m_2+\cdots =n$, $\ell = m_1+m_2+\cdots$ denoting the length of the partition. By (2), the products $(\L^1(\A))^{m_1} (\L^2(\A))^{m_2} \cdots$ are the sum of \MP which touch the ground at positions $1,2,\ldots,m_1$; $m_1+2,m_1+4,\ldots, m_1+2m_2$; $m_1+2m_2+3,\ldots$ If we enumerate all \MP instead of the preceeding ones, we have to correct by a factor $\ell/ m_1§\, m_2!\cdots$ which tells how many paths can be obtained from a given one by permutation of its irreducible components. Therefore one has : \medskip \noindent Theorem. \sl For any $n\in \N$, any $k\in \R$ , one has $$ \L^n(k\A) \equiv \sum (-1)^{n-\ell} {k\choose \ell} w \ ,\eqno (7) $$ sum over all \MP of length $n$, where $\ell$ is the number of ground points (origin excepted) of the path. \medskip\rm To express cumulants, Lehner [Le] needed the functions ${1\over n-1} \L^n((n-1)\A)$ and obtained the above theorem (for $k=n-1$) by direct computation. For example, for $n=4$, writing words $w[]$ multiplied by weights instead of paths, one has $$ \L^4(k\A) = {k\choose 4} w[0,0,0,0,0] \a_0^4 - {k\choose 3} \bigl( w[0,0,0,1,0]+w[0,0,1,0,0]+w[0,1,0,0,0] \bigr) \a_0^2 \y_1 $$ $$\kern 1cm + {k\choose 2} w[0,1,0,1,0] y_1^2 + {k\choose 2} \bigl( w[0,0,1,1,0] +w[0,1,1,0,0] \bigr) \a_0\a_1 \y_1 $$ $$\kern 1cm - {k\choose 1} w[0,1,1,1,0] \a_1^2\y_1 - {k\choose 1} w[0,1,2,1,0] \y_1\y_2 $$ We notice that $k=0$ gives at the limit the logarithm of $\sigma_x(\A)$. Indeed, the limit, for $k=0$, of $ {1\over k}\, \L^n(k\A)$, $n>0$, is ${1\over n} \psi_n(\A)$. Therefore (7) implies $$ {1\over n} \psi_n(\A) \equiv \sum {1\over \ell}\, w \ , \eqno(8) $$ where the statistics differ from (5). For example, for $n=4$, formula (5) gives $${1\over 4}\psi_4(\A)= {1\over 4} w[0,0,0,0,0] + {1\over 4} w[0,0,1,0,0] + {1\over 4} w[0,0,1,0,0] +{2\over 4} w[0,1,0,0,0] $$ $$ \kern 20pt + {2\over 4} w[0,1,0,1,0] + {3\over 4} w[0,1,1,0,0] + {4\over 4} w[0,1,1,1,0] + {4\over 4}w[0,1,2,1,0] $$ while (8) states that $${1\over 4}\psi_4(\A)= {1\over 4} w[0,0,0,0,0] + {1\over 3} \Bigl( w[0,0,0,1,0]+w[0,0,1,0,0]+w[0,1,0,0,0] \Bigr) $$ $$\kern 1cm +{1\over 2} w[0,1,0,1,0] + {1\over 2}\Bigl( w[0,0,1,1,0] +w[0,1,1,0,0] \Bigr) + w[0,1,1,1,0] + w[0,1,2,1,0] $$ \medskip\noindent {\it Acknowledg(e)ments. \ Je remercie E. Motzkin pour son aide linguistique}. \bigskip \centerline{\bf References} \parindent 0 mm \medskip [Fl] P. Flajolet. {\it Combinatorial aspects of continued fractions}, Discrete Math. {\bf 32} (1980) 125-161. [FV] J. Fran\c{c}on, X. Viennot. {\it Permutations selon leurs pics ..}, Discrete Math. {\bf 28} (1979) 21--35. [GJ] I.P. Goulden, D.M. Jackson. {\it Combinatorial enumeration}, Wiley (1983). [L1] A. Lascoux. {\it Diviser !}, \it in \rm" Mots " (ed. par Lothaire), Hermes,Paris (1990). [L2] A. Lascoux. {\it Alphabet splitting}, Maratea Conference dedicated to Gian-Carlo Rota (1999), to be published by Springer, ({\tt http://phalanstere.univ-mlv.fr/~al}. [Le] F. Lehner, article in the process of being written. [Vi] X. Viennot. {\it Une th\'eorie combinatoire des polyn\^omes orthogonaux g\'en\'eraux}, Lecture Notes, Universit\'e du Qu\'ebec a Montr\'eal , Montr\'eal (1984). [Wr] H. Wronski. {\it Philosophie de la Technie algorithmique: Loi supr\^eme et universelle; r\'eforme des math\'ematiques}, Paris 1815--1817. \vskip 15mm {\obeylines \hfill C.N.R.S., Institut Gaspard Monge \hfill \hfill Universit\'e de Marne-la-Vall\'ee, \hfill \hfill 5 Bd Descartes, Champs sur Marne, \hfill \hfill 77454 Marne La Vall\'ee Cedex 2 FRANCE \hfill \hfill \tt Alain.Lascoux@univ-mlv.fr \hfill http://phalanstere.univ-mlv.fr/$\sim$al } \bye