Séminaire Lotharingien de Combinatoire 44 (2000), Article B44f

On the powers of Motzkin paths

Jiang Zeng

Institut Girard Desargues, Universite Claude Bernard (Lyon 1),

43 Bd du 11 novembre 1918, 69622 Villeurbanne Cedex, France

                     zeng@desargues.univ-lyon1.fr

Abstract We give a simple combinatorial proof of a recent formula of Lascoux

for the powers of continued fractions.

Given an alphabet 𝔸 composed of commuting letters a’s, let λ_{x}(𝔸) = ∏_{a∈𝔸}(1 + ax). For any k ∈ ℝ, let Λ^{n}(k𝔸) and S^{n}(k𝔸) be the coefficients of x^{n} in (λ_{x}(𝔸))^{k} and (λ_{−x}(𝔸))^{−k} respectively. Recall that the weight of a Motzkin path π, noted w(π), is the product of the weights of its steps : 1 for a North-East step, α_{i} for an horizontal step at level i, ξ_{i} for a South-East step between level i and i − 1.

Assuming that one has the following continued fraction expansion :

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

then Lascoux [2], generalizing a result of Lehner, proved the following :

Theorem 1 (Lascoux) For any n ∈ ℕ, any k ∈ ℝ , one has

Λ^{n}(k𝔸) = ∑_{π}(−1)^{n−ℓ}\binom{k}{ℓ}w(π)  (2)

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

Lascoux’s proof of (2) is of lots eruditions. Here we show how to derive it directly from Flajolet’s classical result [1].

First we note that by definition S^{n}(k𝔸) = (−1)^{n}Λ^{n}((−k)𝔸), so (2) can be paraphrased as follows :

S^{n}(k𝔸) = ∑_{π} \binom{k + ℓ − 1}{ℓ}w(π),  (3)

where the sum is the same as in (2). Since the two sides of (3) are polynomials of k, it suffices to prove (3) for k ∈ ℕ. In view of Flajolet’s result [1], which corresponds to the k = 1 case of (3), the symmetric function S^{n}(k𝔸) is equal to ∑ w(π_{1} ⋯ π_{k}), where the sum is over all the k-tuples (π_{1}, …, π_{k}) of Motzkin paths such that the product (or juxtaposition) π_{1} ⋯ π_{k} is a Motzkin path of length n. By convention, an empty Motzkin paths is of length 0. Clearly, each Motzkin path π having ℓ ground points (other than the origin) can be ontained in such a way from \binom{k+ℓ−1}{ℓ} k-tuples (π_{1}, …, π_{k}) of Motzkin paths, which is exactly what (3) means.

References

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

[2] A. Lascoux, Motzkin paths and powers of continued fractions, Séminaire Lotharingien de Combinatoire 44 (2000), Article B44e.