Motzkin paths and powers of continued fractions

Alain Lascoux

Abstract. 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.

Given an alphabet composed of letters a, 𝔸 = {a ∈ 𝔸}, let Λ^{n}(𝔸), n = 0, 1, 2, …, be the n-th elementary symmetric function in 𝔸, i.e. the coefficient of x^{n} in λ_{x}(A) := ∏_{a∈𝔸}(1 + ax). Let furthemore the complete functions S^{n}(𝔸) be the coefficients of σ_{x}(𝔸) = ∏_{a∈𝔸} 1/(1 − ax) and, for any k ∈ ℝ, let Λ^{n}(k𝔸) be the coefficient of of x^{n} in λ_{x}(k𝔸) := (λ_{x}(𝔸))^{k}. We wish to express the symmetric function Λ^{n}(k𝔸) in terms of the coefficients of the continued fraction expression of

σ_{x}(𝔸) = ∑ x^{n}S^{n}(𝔸) := \frac{1}{λ_{−x}(𝔸)} = \frac{1}{(1 − α_{0}x) − \frac{x^{2}ξ_{1}}{(1 − α_{1}x) − \frac{x^{2}ξ_{2}}{(1 − α_{2}x) − \frac{x^{2}ξ_{3}}{...}}}}  (1)

i.e. we wish to give the expansion of the k-th power of the continued fraction on the right.

Wronski [Wr] determined the parameters α_{0}, α_{1}, …, ξ_{1}, ξ_{2}, … as symmetric functions of 𝔸 (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}(𝔸) in terms of the parameters α_{i}, ξ_{j}, that we shall use after recalling the necessary definitions. First, we shall let the cardinality of 𝔸 tend toward infinity, so that the elementary symmetric functions are algebraically independent. Definition. Motzkin paths are paths in the positive integral plane, with East, North-East and South-East steps, starting and finishing at level zero. A weight is attributed to each step: α_{i} for an horizontal step at level i, ξ_{i} for a South-East step between level i and i − 1. The weight of the path itself is the product of the weights of its steps. An 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

3  3  3  3
2  2  2  2
1 1  1  1  1
0  0
word 0 1 1 2 1 2 3  3  3  3  2 1 2  1 0
weight  α_{1}  ξ_{2}  α_{3}  α_{3}  α_{3}  ξ_{3}  ξ_{2}  ξ_{1}  ξ_{0}

It is clear that Motzkin paths can be uniquely factored into irreducible paths, level zero points being the cutting points.

When we write an equality between a function in the α_{i}, ξ_{j} and a sum of paths, we shall mean that one has to replace each path by its weight in the latter.

Theorem (Flajolet [Fl]). For any n ∈ ℕ, the complete function S_{n}(𝔸) is equal to the sum of Motzkin paths of length n, the parameters α_{i}, ξ_{j} being defined by (1).

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 Motzkin paths as generators (one also has theories of non commutative symmetric functions !). Any symmetric polynomial in 𝔸 can now be interpreted as a polynomial function in the irreducible Motzkin paths. We shall write ≡ when allowing commutation of Motzkin paths .

For example, since 1/σ_{x}(𝔸) = λ_{−x}(𝔸), then

(−1)^{n−1}Λ^{n}(𝔸) ≡ sum of all irreducible Motzkin paths of length n .  (2)

The hook-Schur functions S_{j+1,1^{i}} are expressible as

S_{j+1,1^{i}} = Λ^{i+1}S^{j} − Λ^{i+2}S^{j−1} + ⋯ + ±Λ^{i+j+1}S^{0} .  (3)

Each term of the sum (3) can be interpreted as the sum of all Motzkin paths of length n with first return to level 0 in position i + 1, i + 2, i + 3, …, respectively. Therefore

(−1)^{i} S_{j+1,1^{i}}(𝔸) ≡ ∑_{ϑ(w)≥i+1} w ,  (4)

where the sum is over all Motzkin paths w of length i + j + 1, ϑ(w) denoting the position of the first return to level 0.

A power sum ψ_{n} is equal to the alternating sum of all hook-Schur functions of degree n (i.e., ψ_{n} = S_{n} − S_{n−1,1} + S_{n−2,1,1} − ⋯). Therefore, one gets from (4):

ψ_{n}(𝔸) = ∑_{w: length(w)=n} ϑ(w) w .  (5)

The Cauchy formula allows to expand elementary or complete functions of a product of two alphabets. In particular, it gives several expansions of the Λ^{n}(k𝔸), k ∈ ℝ (these functions can be interpreted as coefficients of the powers of the Lagrange inverse of xσ_{x}(𝔸), see [L2]).

The Cauchy formula says that

Λ^{n}(k𝔸) = ∑_{m_{1},m_{2},...} \frac{k(k − 1) ⋯ (k − ℓ + 1)}{m_{1}!m_{2}! ⋯}(Λ^{1}(𝔸))^{m_{1}}(Λ^{2}(𝔸))^{m_{2}} ⋯,  (6)

where the sum is over all partitions 1^{m_{1}}2^{m_{2}} ⋯ of weight 1m_{1} + 2m_{2} + ⋯ = n, ℓ = m_{1} + m_{2} + ⋯ denoting the length of the partition.

By (2), the products (Λ^{1}(𝔸))^{m_{1}}(Λ^{2}(𝔸))^{m_{2}} ⋯ are the sum of Motzkin paths which touch the ground at positions 1, 2, …, m_{1}; m_{1} + 2, m_{1} + 4, …, m_{1} + 2m_{2}; m_{1} + 2m_{2} + 3, … If we enumerate all Motzkin paths instead of the preceding ones, we have to correct by a factor ℓ!/m_{1}! m_{2}! ⋯ which tells how many paths can be obtained from a given one by permutation of its irreducible components. Therefore one has :

Theorem. For any n ∈ ℕ, any k ∈ ℝ , one has

Λ^{n}(k𝔸) ≡ ∑(−1)^{n−ℓ}\binom{k}{ℓ}w ,  (7)

where the sum is over all Motzkin paths of length n, where ℓ is the number of ground points (other than origin) of the path.

To express cumulants, Lehner [Le] needed the functions \frac{1}{n−1}Λ^{n}((n−1)𝔸) 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

Λ^{4}(k𝔸) = \binom{k}{4}w[0, 0, 0, 0, 0]α_{0}^{4} − \binom{k}{3}(w[0, 0, 0, 1, 0] + w[0, 0, 1, 0, 0] + w[0, 1, 0, 0, 0])α_{0}^{2}ξ_{1}

+\binom{k}{2}w[0, 1, 0, 1, 0]ξ_{1}^{2} + \binom{k}{2}(w[0, 0, 1, 1, 0] + w[0, 1, 1, 0, 0])α_{0}α_{1}ξ_{1}

−\binom{k}{1}w[0, 1, 1, 1, 0]α_{1}^{2}ξ_{1} − \binom{k}{1}w[0, 1, 2, 1, 0]ξ_{1}ξ_{2} .

We notice that k = 0 gives at the limit the logarithm of σ_{x}(𝔸). Indeed, the limit, for k = 0, of \frac{1}{k} Λ^{n}(k𝔸), n > 0, is \frac{1}{n}ψ_{n}(𝔸). Therefore (7) implies

\frac{1}{n}ψ_{n}(𝔸) ≡ ∑ \frac{1}{ℓ} w ,  (8)

where the statistics differ from (5).

For example, for n = 4, formula (5) gives

\frac{1}{4}ψ_{4}(𝔸) = \frac{1}{4}w[0, 0, 0, 0, 0]α_{0}^{4} + \frac{1}{4}w[0, 0, 1, 0, 0]α_{0}^{2}ξ_{1} + \frac{1}{4}w[0, 0, 1, 0, 0]α_{0}^{2}ξ_{1}

+\frac{1}{4}w[0, 0, 1, 1, 0]α_{0}α_{1}ξ_{1} + \frac{2}{4}w[0, 1, 0, 0, 0]α_{0}^{2}ξ_{1} + \frac{2}{4}w[0, 1, 0, 1, 0]ξ_{1}^{2}

+\frac{3}{4}w[0, 1, 1, 0, 0]α_{0}α_{1}ξ_{1} + \frac{4}{4}w[0, 1, 1, 1, 0]α_{1}^{2}ξ_{1} + \frac{4}{4}w[0, 1, 2, 1, 0]ξ_{1}ξ_{2} ,

while (8) states that \frac{1}{4}ψ_{4}(𝔸) = \frac{1}{4}w[0, 0, 0, 0, 0]α_{0}^{4} + \frac{1}{3}(w[0, 0, 0, 1, 0] + w[0, 0, 1, 0, 0] + w[0, 1, 0, 0, 0])α_{0}^{2}ξ_{1}

+\frac{1}{2}w[0, 1, 0, 1, 0]ξ_{1}^{2} + \frac{1}{2}(w[0, 0, 1, 1, 0] + w[0, 1, 1, 0, 0])α_{0}α_{1}ξ_{1} + w[0, 1, 1, 1, 0]α_{1}^{2}ξ_{1}

+w[0, 1, 2, 1, 0]ξ_{1}ξ_{2} .

Acknowledg(e)ments. Je remercie E. Motzkin pour son aide linguistique.

References

[Fl] P. Flajolet. Combinatorial aspects of continued fractions, Discrete Math. 32 (1980) 125-161.

[FV] J. Françon, X. Viennot. Permutations selon les pics, creux, doubles montées, doubles descentes, nombres d’Euler et nombres de Genocchi, Discrete Math. 28 (1979) 21–35.

[GJ] I.P. Goulden, D.M. Jackson. Combinatorial enumeration, Wiley (1983).

[L1] A. Lascoux. Diviser !, in ” Mots ” (ed. par Lothaire), Hermes,Paris (1990).

[L2] A. Lascoux. Alphabet splitting, Maratea Conference dedicated to Gian-Carlo Rota (1999), to be published by Springer, (http://phalanstere.univ-mlv.fr/∼al).

[Le] F. Lehner, article in the process of being written.

[Vi] X. Viennot. Une théorie combinatoire des polynômes orthogonaux généraux, Lecture Notes, Université du Québec à Montréal , Montréal (1984).

[Wr] H. Wronski. Philosophie de la Technie algorithmique: Loi suprême et universelle; réforme des mathématiques, Paris 1815–1817.

C.N.R.S., Institut Gaspard Monge Université de Marne-la-Vallée,

5 Bd Descartes, Champs sur Marne, 77454 Marne La Vallée Cedex 2 FRANCE

                                                  Alain.Lascoux@univ-mlv.fr
                                        http://phalanstere.univ-mlv.fr/∼al