% Motzkin 3 juillet 2000  corrections 18 juillet; 13 oct.
%  Plain Tex 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\magnification=1200   %\overfullrule 0mm
\frenchspacing

%First page headline in Plain-TeX for S\'eminaire Lotharingien de Combinatoire
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\headline={\its S\'eminaire Lotharingien de
Combinatoire \bfs 44 \rms (2000), Article~B44e\hfill} 


\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 composed of letters $a$, 
$\A =\{ a\in\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)} =
{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
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 latter. 

\medskip
\noindent {\bf 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 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 
of length $n$ 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) $$
where the sum is 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) $$
where the sum is 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 preceding 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 {\bf 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) $$
where the sum is over all \MP of length $n$, where $\ell$ is the 
 number of ground points (other than the origin) 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]\a_0^4 + 
{1\over 4} w[0,0,1,0,0]\a_0^2 \y_1 +
{1\over 4} w[0,0,1,0,0]\a_0^2 \y_1$$
$$ + {1\over 4}w[0,0,1,1,0]\a_0\a_1 \y_1 
 +{2\over 4} w[0,1,0,0,0]\a_0^2 \y_1 
 + {2\over 4} w[0,1,0,1,0]\y_1^2  $$
$$+ {3\over 4} w[0,1,1,0,0]\a_0\a_1 \y_1 + {4\over 4} w[0,1,1,1,0]\a_1^2\y_1
+ {4\over 4}w[0,1,2,1,0]\y_1\y_2  \ , $$
while (8) states that 

\noindent{
${1\over 4}\psi_4(\A)= {1\over 4} w[0,0,0,0,0]\a_0^4 + {1\over 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 $

$ +{1\over 2} w[0,1,0,1,0]\y_1^2  + {1\over 2}\Bigl( w[0,0,1,1,0] +w[0,1,1,0,0]
\Bigr)\a_0\a_1 \y_1  + w[0,1,1,1,0]\a_1^2\y_1$

$  + w[0,1,2,1,0]\y_1\y_2 \ . $
}



\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 les pics, creux,
doubles mont\'ees, doubles descentes, nombres d'Euler et nombres de Genocchi},
     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/$\sim$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
