PERMUTATIONS WITH RESTRICTED

PATTERNS AND DYCK PATHS

C. Krattenthaler^{†}

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Ap.Univie.Ac.At

       WWW: http://www.mat.univie.ac.at/People/kratt

Dedicated to Dominique Foata

Abstract. We exhibit a bijection between 132-avoiding permutations and Dyck paths. Using this bijection, it is shown that all the recently discovered results on generating functions for 132-avoiding permutations with a given number of occurrences of the pattern 12 … k follow directly from old results on the enumeration of Motzkin paths, among which is a continued fraction result due to Flajolet. As a bonus, we use these observations to derive further results and a precise asymptotic estimate for the number of 132-avoiding permutations of {1, 2, …, n} with exactly r occurrences of the pattern 12 … k. Second, we exhibit a bijection between 123-avoiding permutations and Dyck paths. When combined with a result of Roblet and Viennot, this bijection allows us to express the generating function for 123-avoiding permutations with a given number of occurrences of the pattern (k − 1)(k − 2) … 1k in form of a continued fraction and to derive further results for these permutations.

1. Introduction. In the recent papers [2, 4, 6, 9], the authors considered 132avoiding permutations with a prescribed number of occurrences of the pattern 12 … k (the most general results being contained in [6]) and 123-avoiding permutations which also avoid the pattern (k − 1)(k − 2) … 1k. (See the end of this section for the precise definition of permutations which avoid a certain pattern, and of Dyck paths.) They found that generating functions for these permutations can be expressed in terms of continued fractions and Chebyshev polynomials.

The purpose of this paper is to make a case for the paradigm:

‘Whenever you encounter generating functions which can be expressed in terms of continued fractions or Chebyshev polynomials, then expect that

1991 Mathematics Subject Classification. Primary 05A05; Secondary 05A15, 05A16. Key words and phrases. permutations with restricted patterns, Chebyshev polynomials, contin-

ued fraction, Dyck paths.

† Research partially supported by the Austrian Science Foundation FWF, grant P13190-MAT

Typeset by AMS-TEX

Dyck or Motzkin paths are at the heart of your problem, and will help to solve it.’

Indeed, as I am going to demonstrate in Section 2, there is an obvious bijection between 132-avoiding permutations and Dyck paths. (In particular, as is well-known, 132-avoiding permutations are counted by Catalan numbers.) Surprisingly, this bijection seems to be new^{1}. Known results for generating functions for Motzkin paths (one of which due to Flajolet [3], the other being folklore; Dyck paths being special Motzkin paths) then allow one immediately to express the generating functions in which we are interested in terms of continued fractions and Chebyshev polynomials (thus making the speculation in [2, Sec. 5] precise and explicit). In particular, we recover all the relevant results from [2, 6, 9]. Furthermore, by exploiting the relation between 132-avoiding permutations and Dyck paths further, we are able to find an explicit expression for the generating function for 132-avoiding permutations with exactly r occurrences of the pattern 12 … k, thus extending a result from [6]. This, in turn, allows us to provide a precise asymptotic estimate for the number of these permutations of {1, 2, …, n} as n becomes large. All these results can be found in Section 3, as well as generating functions for 132-avoiding permutations with no occurrence or one occurrence of the pattern 23 … k1.

In Section 4 we exhibit a bijection between 123-avoiding permutations and Dyck paths, which also, and again surprisingly, seems to be new^{2}. (In particular, as is also well-known, 123-avoiding permutations are counted by Catalan numbers.) In Section 5 we combine this bijection with a result of Roblet and Viennot [10] on the enumeration of Dyck paths to obtain a continued fraction for the generating function of 123-avoiding permutations with a given number of occurrences of the pattern (k − 1)(k − 2) … 1k. Further results on these permutations (which extend another result from [2]) can be found in Section 5 as well, including precise asymptotic estimates. (By combining this bijection between 123-avoiding permutations and Dyck paths with our bijection between the latter and 132-avoiding permutations, we obtain a bijection between 123-avoiding and 132-avoiding permutations. This bijection appears to be new. In particular, it is different from the one by Simion and Schmidt [11, Sec. 6] and the one by West [15], as can be immediately seen by considering the examples given in [11, Examples after Prop. 19] and [15, Ex. 2.7], respectively.)

For the convenience of the reader, we recall the results on Motzkin and Dyck paths, on which we rely so heavily, in an appendix at the end of the paper.

At the end of the introduction, let us recall the basic definitions.

Let π = π_{1}π_{2} … π_{n} be a permutation of {1, 2, …, n} and σ = σ_{1}σ_{2} … σ_{k} be a permutation of {1, 2, …, k}, k ≤ n. We say that the permutation π contains the pattern σ, if there are indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n such that π_{i_{1}}π_{i_{2}} … π_{i_{k}} is in the same relative order as σ_{1}σ_{2} … σ_{k}. Otherwise, π is said to avoid the pattern σ, or, alternatively, we say that π is σ-avoiding.

1Independently, and at the same time, Emeric Deutsch (private communication) discovered this bijection in an equivalent form.

2Also this bijection was independently and at the same time discovered by Emeric Deutsch (private communication). It does not translate into the bijection between 321-avoiding permutations and Dyck paths in [1, after the proof of Theorem 2.1]

A Dyck path is a lattice path in the plane integer lattice ℤ^{2} (ℤ denoting the set of integers) consisting of up-steps (1, 1) and down-steps (1, −1), which never passes below the x-axis. See Figure 1 for an example. (To be very explicit: The definition of Dyck path that we use in this paper is wider than usually, in that we do not require that a Dyck path starts and ends on the x-axis. The latter type of path is, though, the type of path that we will encounter most of the time, Figure 1 being an example.)

2. A bijection between 132-avoiding permutations and Dyck paths. In this section we define a map Φ which maps 132-avoiding permutations to Dyck paths which start at the origin and return to the x-axis as follows. Let π = π_{1}π_{2} … π_{n} be a 132-avoiding permutation. We read the permutation π from left to right and successively generate a Dyck path. When π_{j} is read, then in the path we adjoin as many up-steps as necessary, followed by a down-step from height h_{j} + 1 to height h_{j} (measured from the x-axis), where h_{j} is the number of elements in π_{j+1} … π_{n} which are larger than π_{j}.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

The Dyck path corresponding to 74352681

Figure 1

For example, let π = 74352681. The first element to be read is 7. There is 1 element in 4352681 which is larger than 7, therefore the path starts with two up-steps followed by a down-step, thus reaching height 1 (see Figure 1). Next 4 is read. There are 3 elements in 352681 which are larger than 4, therefore the path continues with three up-steps followed by a down-step, thus reaching height 3. Etc. The complete Dyck path Φ(74352681) is shown in Figure 1.

The reader should note that, for the map Φ to be well-defined, it is essential that the permutation π to which the map is applied is 132-avoiding. For this guarantees that always h_{j} − 1 ≤ h_{j+1}, so that it is always possible to connect the down-step from height h_{j} + 1 to h_{j} (formed by definition of Φ when considering π_{j}) by a number of up-steps (this number being possibly zero) to the down-step from height h_{j+1} + 1 to h_{j+1}. Conversely, given a Dyck path starting at the origin and returning to the x-axis, the obvious inverse of Φ produces a 132-avoiding permutation.

In summary, the map Φ is a bijection between 132-avoiding permutations of {1, 2, …, n} and Dyck paths from (0, 0) to (2n, 0). We remark that, in view of the standard bijection between rooted ordered trees and Dyck paths through a depthfirst traversal of the trees (cf. e.g. [13, Prop. 6.2.1 (i) and (v), Cor. 6.2.3 (i) and (v)]), this map is equivalent to the bijection between 132-avoiding permutations and rooted ordered trees given by Jani and Rieper [4].

For the sake of completeness, and to show the close relation between the map Φ and the map Ψ that is to be defined in Section 4, we provide an alternative way to define the map Φ. Let π = π_{1}π_{2} … π_{n} be a 132-avoiding permutation. In π, we determine all the left-to-right minima. A left-to-right minimum is an element π_{i} which is smaller than all the elements to its left, i.e., smaller than all π_{j} with j < i. For example, the left-to-right minima in the permutation 74352681 are 7, 4, 3, 2, 1.

Let the left-to-right minima in π be m_{1}, m_{2}, …, m_{s}, so that

π = m_{1}w_{1}m_{2}w_{2} … m_{s}w_{s},  (3.1)

where w_{i} is the subword of π in between m_{i} and m_{i+1}. Read the decomposition (3.1) from left to right. Any left-to-right minimum m_{i} is translated into m_{i−1} − m_{i} up-steps (with the convention m_{0} = n+1). Any subword w_{i} is translated into |w_{i}|+1 down-steps (where |w_{i}| denotes the number of elements of w_{i}).

In the lemma below we list two properties of the bijection Φ, which will be subsequently used in Section 3.

Lemma Φ. Let π = π_{1}π_{2} … π_{n} be a 132-avoiding permutation, and let P = Φ(π) be the corresponding Dyck path. Then,

(1) a down-step in P from height i to height i − 1 corresponds in a one-to-one fashion to an element π_{j} in the permutation which is the first element in an increasing subsequence in π of length i (i.e., an occurrence of the pattern 12 … i) that is maximal with respect to the property that π_{j} is its first element.

(2) a portion of the path P which starts at height h+i−1 and eventually falls down to height h, for some h, followed by an up-step corresponds to an occurrence of the pattern 23 … i1 in π.

Proof. Re (1): By the definition of Φ, a down-step from height i to height i − 1 in P = Φ(π) means that we read an element π_{j} which has the property that there are i − 1 elements in π_{j+1} … π_{n} which are larger than π_{j}. Since π is 132-avoiding, these i − 1 elements have to appear in increasing order, thus, together with π_{j}, form an increasing subsequence of length i that cannot be made longer under the assumption that π_{j} is the first element in the subsequence.

Re (2): In a path portion which starts at height h + i − 1 and eventually falls down to height h we must find a down-step from height h + i − 1 to h + i − 2, a down-step from height h + i − 2 to h + i − 3, …, a down-step from height h + 1 to h. If, in this path portion, we choose the first down-step from height h + i − 1 to h + i − 2, the first down-step from height h + i − 2 to h + i − 3, …, the first down-step from height h + 1 to h, then, under the correspondence Φ, these down-steps correspond to an increasing subsequence π_{j_{1}}π_{j_{2}} … π_{j_{i−1}} of length i−1 in π. If now the path continues by (at least) one up-step, then the following down-step corresponds to an element π_{j_{i}}, j_{i} > j_{i−1}, with the property that there are more elements in π_{j_{i+1}} … π_{n} that are larger than π_{j_{i}} than there are elements in π_{j_{i}} … π_{n} that are larger than π_{j_{i−1}}. Evidently, this is only possible if π_{j_{i−1}} > π_{j_{i}}. Since π is 132-avoiding, this implies that we have even π_{j_{1}} > π_{j_{i}}. Hence, π_{j_{1}}π_{j_{2}} … π_{j_{i−1}}π_{j_{i}} is an occurrence of the pattern 23 … i1 in π. □

3. The enumeration of 132-avoiding permutations with a prescribed number of occurrences of the patterns 12 … k and 23 … k1. In this section we provide explicit expressions for generating functions for 132-avoiding permutations with a prescribed number of occurrences of the pattern 12 … k, and for 132-avoiding permutations with a prescribed number of occurrences of the pattern 23 … k1.

First we consider the former permutations. Given a 132-avoiding permutation π, we denote the number of occurrences of the pattern 12 … k in π by N(12 … k; π).

Given a Dyck path P, we assign a weight to it, denoted by w_{1}(k; P). It is defined as the sum ∑_{d} \binom{i(d)−1}{k−1}, where the sum is over all down-steps d of P, and where i(d) is the height of the starting point of d. For example, the weight w_{1}(3; .) of the Dyck path in Figure 1 is

\binom{1}{2} + \binom{3}{2} + \binom{3}{2} + \binom{2}{2} + \binom{2}{2} + \binom{1}{2} + \binom{0}{2} + \binom{0}{2} = 8.

From Lemma Φ.(1) it is immediate that

N(12 … k; π) = w_{1}(k; Φ(π)).  (3.2)

This observation, combined with Flajolet’s continued fraction theorem for the generating function of Motzkin paths (see Theorem A1), allows us to express the generating function which counts 132-avoiding permutations with respect to the number of occurrences of the pattern 12 … k in form of a continued fraction. This result was first obtained by Mansour and Vainshtein [6, Theorem 2.1]. In the statement of the theorem, and in the following, we write |π| for the number of elements which are permuted by π. For example, we have |74352681| = 8.

Theorem 1. The generating function ∑_{π} y^{N(12...k;π)}x^{|π|}, where the sum is over all 132-avoiding permutations, is given by

\frac{1}{1 − \frac{xy^{\binom{0}{k−1}}}{1 − \frac{xy^{\binom{1}{k−1}}}{1 − \frac{xy^{\binom{2}{k−1}}}{1 − ⋯}}}} .  (3.3)

Proof. Apply Theorem A1 with b_{i} = 0 and λ_{i} = xy^{\binom{i−1}{k−1}}, i = 0, 1, …, and use (3.2). □

We remark that the above proof is essentially equivalent to the one in [4, proof of Corollary 7]. It is obvious that the refinement in [6, expression for W_{k}(…) after Proposition 2.3] could also easily be derived by using the correspondence Φ and Flajolet’s continued fraction.

Next we turn our attention to 132-avoiding permutations with a fixed number of occurrences of the pattern 12 … k. The theorem below was first obtained by Chow and West [2, Theorem 3.6, second case] in an equivalent form.

Theorem 2. The generating function ∑_{π} x^{|π|}, where the sum is over all 132-avoiding permutations which also avoid the pattern 12 … k, is given by

\frac{U_{k−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})},  (3.4)

where U_{n}(x) denotes the n-th Chebyshev polynomial of the second kind, U_{n}(cos t) = sin((n + 1)t)/ sin t.

Proof. By Lemma Φ.(1), the permutations in the statement of the theorem are in bijection with Dyck paths, which start at the origin, return to the x-axis, and do not exceed the height k − 1. Now apply Theorem A2 with b_{i} = 0, λ_{i} = 1, i = 0, 1, …, K = k − 1, r = s = 0, x replaced by \sqrt{x}, and use Fact A3. □

The next theorem extends a result by Mansour and Vainshtein [6, Theorems 3.1 and 4.1], who proved the special case when r is at most k(k + 3)/2.

Theorem 3. Let r and b be positive integers such that \binom{k+b−1}{k} ≤ r < \binom{k+b}{k}. The generating function ∑_{π} x^{|π|}, where the sum is over all 132-avoiding permutations with exactly r occurrences of the pattern 12 … k, is given by

∑ \binom{ℓ_{1} + ℓ_{2} − 1}{ℓ_{2}}\binom{ℓ_{2} + ℓ_{3} − 1}{ℓ_{3}} ⋯ \binom{ℓ_{b−1} + ℓ_{b} − 1}{ℓ_{b}}

· \begin{matrix}(U_{k−1} (\frac{1}{2\sqrt{x}})) & ℓ_{1}−1 \\ (U_{k} (\frac{1}{2\sqrt{x}})) & ℓ_{1}+1 \end{matrix} x^{\frac{1}{2} (ℓ_{1}−1)+(ℓ_{2}+ℓ_{3}+···+ℓ_{b})}, (3.5)

where the sum is over all nonnegative integers ℓ_{1}, ℓ_{2}, …, ℓ_{b} with

ℓ_{1}\binom{k − 1}{k − 1} + ℓ_{2}\binom{k}{k − 1} + ℓ_{3}\binom{k + 1}{k − 1} + ⋯ + ℓ_{b}\binom{k + b − 2}{k − 1} = r,  (3.6)

and where U_{n}(x) denotes the n-th Chebyshev polynomial of the second kind.

Remark. The binomials in (3.5) have the effect that if ℓ_{t} = 0, then ℓ_{j} = 0 for all j ≥ t in order to obtain a nonvanishing summand in the sum (3.5). Furthermore, the sum (3.5) reduces to just one term if r ≤ k, thus recovering [6, Theorem 3.1], and it reduces to a single sum if k < r ≤ k(k + 3)/2, thus recovering [6, Theorem 4.1].

Proof of Theorem 3. Let π be a permutation of the statement of the theorem. We apply Φ to obtain the corresponding Dyck path P = Φ(π). The Dyck path P has a unique decomposition of the form

P_{0}V_{1}d_{1}P_{1}V_{2}d_{2}P_{2} … V_{s}d_{s}P_{s},  (3.7)

where P_{0} is the portion of P from the origin until the first time the height k − 1 is reached, where the d_{i}’s are the down steps whose end points have at least the height k − 1, where the P_{i}’s, i = 1, 2, …, s − 1, are path portions which start and end at height k −1 and never exceed height k −1, where the V_{i}’s are path portions consisting of several subsequent up-steps which fill the gaps in between, and where P_{s} is the portion of P from the last point at height k − 1 until the end of the path. The path portion P_{i} can only be nonempty if d_{i} is a down-step from height k to k − 1. Clearly, d_{s} must be a down-step from height k to height k − 1.

Now suppose that among the d_{i}’s there are ℓ_{1} down-steps from height k to height k − 1, ℓ_{2} down-steps from height k + 1 to height k, etc. Because of (3.2) the relation (3.6) must hold.

Let us for the moment fix ℓ_{1}, ℓ_{2}, … and ask how many orderings of ℓ_{1} down-steps from height k to height k − 1, ℓ_{2} down-steps from height k + 1 to height k, etc., there are which can come from a decomposition (3.7) when we ignore the P_{i}’s and V_{i}’s. In fact, there are many restrictions to be obeyed: After a down-step from height h + 1 to height h there can only follow a down step of at least that height or at worst from height h to height h − 1. Let t be maximal so that ℓ_{t} is nonzero. Then the above observation tells us that after a down-step from height t + k − 1 to t + k − 2 there can only follow another down-step of this sort (of course, with an up-step in between) or a down-step from height t + k − 2 to t + k − 3. Hence, if we just concentrate on these two types of down-steps, of which there are ℓ_{t} and ℓ_{t−1}, respectively, then there are exactly \binom{ℓ_{t−1}+ℓ_{t}−1}{ℓ_{t}} different possible orderings between these steps, taking into account that the last step out of these must necessarily be a step from height t+k −2 to t + k − 3. Next, by similar considerations, one concludes that, given an ordering of the down-steps from height t + k − 1 to t + k − 2 and from height t + k − 2 to t + k − 3, there are \binom{ℓ_{t−2}+ℓ_{t−1}−1}{ℓ_{t−1}} different possibilities to intersperse ℓ_{t−2} down-steps from height t + k − 3 to t + k − 4. Etc. This explains the product of binomials in (3.5).

To explain the remaining expression, we observe that after any of the ℓ_{1} down-steps, from height k to height k − 1, d_{i} say, except for the last, there follows a (possibly empty) path P_{i}, which is a Dyck path which starts and ends at height k −1 and never exceeds height k − 1. By Theorem A2 with b_{i} = 0, λ_{i} = 1, i = 0, 1, …, K = k − 1, r = s = k − 1, x replaced by \sqrt{x}, and use of Fact A3, we conclude that the generating function for these paths is equal to

\frac{x^{(k−1)/2}U_{k−1} (\frac{1}{2\sqrt{x}})}{x^{k/2}U_{k} (\frac{1}{2\sqrt{x}})}.

By again applying Theorem A2, this time with b_{i} = 0, λ_{i} = 1, i = 0, 1, …, K = k −1, r = 0, s = k − 1, x replaced by \sqrt{x}, and using Fact A3, we obtain that the generating function for paths P_{0} from the origin to height k − 1, never exceeding height k − 1, is equal to

\frac{x^{(k−1)/2}}{x^{k/2}U_{k} (\frac{1}{2\sqrt{x}})}.  (3.8)

Similarly, the generating function for paths P_{s} from height k − 1 to height 0, never exceeding height k−1, is also given by (3.8). If everything is combined, the expression (3.5) results. □

Theorem 3 can be readily used to find an asymptotic formula for the number of 132-avoiding permutations with exactly r occurrences of the pattern 12 … k. The corresponding result, given in the theorem below, extends [2, Corollary 4.2]. Before we state the theorem, we recall an elementary lemma (cf. e.g. [7, Sec. 9.1]).

Lemma 4. Let f(x) and g(x) be polynomials. It is assumed that all the zeroes of g(x) have modulus larger than a > 0. Consider the expansion

\frac{f(x)}{(x − a)^{R}g(x)} = ∑_{n=0}^{∞} c_{n}x^{n}.

Then, as n becomes large, we have

c_{n} ∼ (−1)^{R} \frac{n^{R−1}}{(R − 1)!}a^{−n−R} \frac{f(a)}{g(a)} (1 + O (\frac{1}{n})) .  (3.9)

□

Theorem 5. Let r and k be fixed nonnegative integers. Then, as n becomes large, the number of 132-avoiding permutations with exactly r occurrences of the pattern 12 … k is asymptotically

(\frac{4 sin^{2} \frac{π}{k+1}}{k + 1} )^{r+1} \frac{n^{r}}{r!} (4 cos^{2} \frac{π}{k + 1})^{n−r} (1 + O (\frac{1}{n})) .  (3.10)

Proof. The zeroes of the Chebyshev polynomials are well-known. In particular, the zero with smallest modulus of the polynomial x^{k/2}U_{k} (1/2\sqrt{x}) is x = 1/4 cos^{2}(π/(k + 1)).

If r = 0, then we apply Theorem 2 and Lemma 4 with a = 1/4 cos^{2}(π/(k + 1)), R = 1, f(x) = x^{(k−1)/2}U_{k−1}(1/2\sqrt{x}), and

g(x) = \frac{x^{k/2}U_{k} (\frac{1}{2\sqrt{x}})}{(x − _{\frac{1}{4 cos^{2}(\frac{π}{k+1})}})}.  (3.11)

In order to compute the right-hand side of (3.9), we need to substitute x = 1/4 cos^{2}(π/(k + 1)) in our choices of f(x) and g(x). By the definition of the Chebyshev polynomials, we obtain for f(x) = x^{(k−1)/2}U_{k−1}(1/2\sqrt{x}):

f (\frac{1}{4 cos^{2}(π/(k + 1))}) = (\frac{1}{2 cos \frac{π}{k+1}} )^{k−1} \begin{matrix}sin & (k \frac{π}{k+1}) \\ sin & \frac{π}{k+1} \end{matrix} = (\frac{1}{2 cos \frac{π}{k+1}} )^{k−1} .

For our choice (3.11) of g(x) we obtain

g (\frac{1}{4 cos^{2}(π/(k + 1))}) = lim_{x→_{\frac{1}{4 cos^{2}(\frac{π}{k+1})}}} \frac{x^{k/2}U_{k} (\frac{1}{2\sqrt{x}})}{(x − _{\frac{1}{4 cos^{2}(\frac{π}{k+1})}})}

= (\frac{1}{2 cos \frac{π}{k+1}} )^{k} lim_{ϑ→ \frac{π}{k+1}} \frac{sin ((k + 1)ϑ)/ sin ϑ}{(\frac{1}{4 cos^{2} ϑ} − _{\frac{1}{4 cos^{2}(\frac{π}{k+1})}})}.

This limit is easily evaluated by means of de l’Hôpital’s rule.

If r ≥ 1, we start from the generating function given in Theorem 3. It should be observed that, in view of Lemma 4, the summand in (3.5) which asymptotically yields the largest contribution is the one with ℓ_{1} = r and all other ℓ_{i}’s equal to zero. Then an application of Lemma 4 and computations that are very similar to the ones above give finally (3.10). □

The next group of results concerns the enumeration of 132-avoiding permutations with a given number of occurrences of the pattern 23 … k1. We use again the map Φ to translate these permutations into Dyck paths. The property of Φ which is important now is given by Lemma Φ.(2). It says that we can recognize the occurrence of a pattern 23 … k1 in a 132-avoiding permutation in the corresponding Dyck path by a portion of the path which starts at height h + k − 1, eventually falls down to height k, and is then followed by an up-step.

As the first application of our approach we show how to rederive another result due to Chow and West [2, Theorem 3.6, third case], which is reformulated here in an equivalent form.

Theorem 6. The generating function ∑_{π} x^{|π|}, where the sum is over all 132-avoiding permutations which also avoid the pattern 23 … k1, is given by

\frac{U_{k−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})},  (3.12)

where U_{n}(x) denotes the n-th Chebyshev polynomial of the second kind.

Proof. Let π be a permutation of the statement of the theorem. By the observation above the statement of the theorem (which was based on Lemma Φ.(2)), for the corresponding Dyck path P = Φ(π) there are two possibilities: Either P never exceeds the height k − 2 (and, thus, π does not contain any increasing subsequence of length k − 1), or P can be decomposed as

P_{0}u_{0}P_{1}u_{1} … P_{s}u_{s}P_{s+1}D,  (3.13)

where P_{0} is a path from the origin to height k − 2 never exceeding height k − 2, where for i = 1, 2, …, s the portion P_{i} is a path starting and ending at height i+k−2, never running below height i, and never exceeding height i + k − 2, where for i = 0, 1, …, s the step u_{i} is an up-step from height i + k − 2 to height i + k − 1, where P_{s+1} is a path from height s + k − 1 to s + 1, never running below height s + 1, and never exceeding height s + k − 1, and where D consists of s + 1 down-steps, from height s + 1 to height 0.

By Theorem A2 with b_{i} = 0, λ_{i} = 1, i = 0, 1, …, K = k − 2, r = s = 0, x replaced by \sqrt{x}, and Fact A3, the generating function for the Dyck paths which never exceed height k − 2 is equal to

\frac{x^{(k−2)/2}U_{k−2} (\frac{1}{2\sqrt{x}})}{x^{(k−1)/2}U_{k−1} (\frac{1}{2\sqrt{x}})}.  (3.14)

By Theorem A2 with b_{i} = 0, λ_{i} = 1, i = 0, 1, …, K = k − 2, r = 0, s = k − 2, x replaced by \sqrt{x}, and Fact A3, the generating function for the possible paths P_{0} in the decomposition (3.13) is equal to

\frac{x^{(k−2)/2}}{x^{(k−1)/2}U_{k−1} (\frac{1}{2\sqrt{x}})},

as well as the generating function for the possible paths P_{s+1}. Finally, for any fixed j between 1 and s, by Theorem A2 with b_{i} = 0, λ_{i} = 1, i = 0, 1, …, K = k − 2, r = s = k−2, x replaced by \sqrt{x}, and Fact A3, the generating function for the possible paths P_{j} in the decomposition (3.13) is also given by (3.14).

If everything is combined, then we obtain that the generating function for the permutations of the statement of the theorem is given by

\frac{U_{k−2} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})} + ∑_{s≥0} \frac{1}{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})} (\frac{U_{k−2} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})})^{s} \frac{1}{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})}x^{s+1}.

The sum is a geometric series and can therefore be evaluated. It is then routine to convert the resulting expression into the expression (3.12), by using standard identities for the Chebyshev polynomials. □

It seems difficult to find an explicit expression for the generating function for 132avoiding permutations with exactly r occurrences of the pattern 23 … k1 for general r. Yet, as long as 1 ≤ r ≤ k − 1 such an explicit expression can be easily derived.

Theorem 7. The generating function ∑_{π} x^{|π|}, where the sum is over all 132-avoiding permutations with exactly one occurrence of the pattern 23 … k1, is given by

\frac{x}{U_{k−2} (\frac{1}{2\sqrt{x}}) U_{k} (\frac{1}{2\sqrt{x}})},  (3.15)

where U_{n}(x) denotes the n-th Chebyshev polynomial of the second kind.

More generally, let 1 ≤ r ≤ k −1. Then the generating function ∑_{π} x^{|π|}, where the sum is over all 132-avoiding permutations with exactly r occurrences of the pattern 23 … k1, is given by

\frac{1}{U_{k−3} (\frac{1}{2\sqrt{x}}) U_{k} (\frac{1}{2\sqrt{x}})} ∑_{ℓ|r} \frac{1}{ℓ + 1}\binom{2ℓ}{ℓ}x^{ℓ+ \frac{r}{2ℓ} − \frac{1}{2}} (\frac{U_{k−3} (\frac{1}{2\sqrt{x}})}{U_{k−2} (\frac{1}{2\sqrt{x}})})^{r/ℓ} .  (3.16)

Proof. Let π be a 132-avoiding permutation with exactly r occurrences of the pattern 23 … k1. Analogously to the argument in the proof of Theorem 6, the Dyck path Φ(π) corresponding to π can be decomposed as

P_{0}u_{0}P_{1}u_{1} … P_{s−1}u_{s−1}P_{s}u_{s}d_{s}P_{s+1}u_{s+1}d_{s+1}P_{s+2} … u_{s+ℓ−1}d_{s+ℓ−1}P_{s+ℓ}d_{s+ℓ}P_{s+ℓ+1}D,

where for i = 0, 1, …, s the portions P_{i} and steps u_{i} are as in (3.13), where the step d_{s} is a down-step from height s + k − 1 to height s + k − 2, where for i = 1, 2, …, ℓ − 1 the path P_{s+i} is a path starting and ending at height s + k − 2, never running below height s + 1, and never exceeding height s + k − 2, the step u_{s+i} is an up-step from height s + k − 2 to height s + k − 1, and the step d_{s+i} is a down-step from height s + k − 1 to height s + k − 2, where P_{s+ℓ} is a path from height s + k − 2 to s + 1, never running below height s + 1, and never exceeding height s + k − 2, where d_{s+ℓ} is a down-step from height s + 1 to height s, where P_{s+ℓ+1} is a path of length 2r/ℓ, starting and ending at height s, and never running below height s, and where D consists of s down-steps, from height s to height 0.

Still following the arguments in the proof of Theorem 6, and taking into account that the number of possible paths P_{s+ℓ+1} is the (r/ℓ)-th Catalan number, this decomposition implies that the generating function that we are looking for is given by

∑_{ℓ|r} ∑_{s≥0} \frac{1}{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})} (\frac{U_{k−2} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k−1} (\frac{1}{2\sqrt{x}})})^{s}

· (\frac{U_{k−3} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k−2} (\frac{1}{2\sqrt{x}})})^{ℓ−1} \frac{1}{\sqrt{x}U_{k−2} (\frac{1}{2\sqrt{x}})} \frac{1}{r/ℓ + 1}\binom{2r/ℓ}{r/ℓ}x^{s+ℓ+ \frac{r}{ℓ} +1/2}.

The inner sum is again a geometric series and can therefore be evaluated. A routine calculation, followed by a replacement of ℓ by r/ℓ, then transforms the resulting expression into (3.15). □

It is obvious that in both cases (that is, for 132-avoiding permutations with no occurrence of the pattern 23 … k1, respectively with r ≤ k − 1 occurrences) Lemma 4 could be applied to derive asymptotic formulas for the number of such permutations of {1, 2, …, n}, as n becomes large. We omit the statement of the corresponding formulas for the sake of brevity.

It appears that, for generic r (i.e., also for r ≥ k), the number of 132-avoiding permutations of {1, 2, …, n} with exactly r occurrences of the pattern 23 … k1 is asymptotically of the order Θ((4 cos^{2} \frac{π}{k+1})^{n}), but we are not able to offer a rigorous proof.

4. A bijection between 123-avoiding permutations and Dyck paths. In this section we define another map, Ψ, between permutations and Dyck paths, which maps 123-avoiding permutations to Dyck paths which start in the origin and return to the x-axis.

Let π = π_{1}π_{2} … π_{n} be a 123-avoiding permutation. In π, we determine all the right-to-left maxima. A right-to-left maximum is an element π_{i} which is larger than all the elements to its right, i.e., larger than all π_{j} with j > i. For example, the right-to-left maxima in the permutation 58327641 are 1, 4, 6, 7, 8.

Let the right-to-left maxima in π be m_{1}, m_{2}, …, m_{s}, from right to left, so that

π = w_{s}m_{s}w_{s−1}m_{s−1} … w_{1}m_{1},  (4.1)

where w_{i} is the subword of π in between m_{i+1} and m_{i}. Since π is 123-avoiding, for all i the elements in w_{i} must be in decreasing order. Moreover, for all i all the elements of w_{i} are smaller than all the elements of w_{i+1}.

Now we are able to define the map Ψ. Read the decomposition (4.1) from right to left. Any right-to-left maximum m_{i} is translated into m_{i} − m_{i−1} up-steps (with the convention m_{0} = 0). Any subword w_{i} is translated into |w_{i}| + 1 down-steps (where, again, |w_{i}| denotes the number of elements of w_{i}). Finally, the resulting path is reflected into a vertical line. (Alternatively, we could have said that we generate the Dyck path from the back to the front.) The Dyck path which corresponds to our special permutation 58327641 is the one in Figure 1.

It is easy to see that the map Ψ is a bijection between 123-avoiding permutations of {1, 2, …, n} and Dyck paths from (0, 0) to (2n, 0). The lemma below states the crucial property of this bijection, which will be subsequently used in Section 5.

Lemma Ψ. Let π = π_{1}π_{2} … π_{n} be a 123-avoiding permutation and let P = Ψ(π) be the corresponding Dyck path. Then a peak in P of height i (i.e., an up-step from height i−1 to height i followed by a down-step from height i to height i−1) corresponds in a one-to-one fashion to an element π_{j} in the permutation which is the last element in an occurrence of the pattern (i − 1)(i − 2) … 1i that is maximal with respect to the property that π_{j} is its last element.

Proof. By construction of Ψ, any peak in the Dyck path corresponds to a right-to-left maximum, m say, in the permutation. Furthermore, by induction one sees that the height of the peak is exactly by 1 larger than the number of elements to the left of m that are smaller than m. Clearly, all these elements belong to some w_{j} in the decomposition (4.1) of the permutation. By the observations above, these elements are in decreasing order, and, thus, together with m form an occurrence of the pattern (i−1)(i−2) … 1i that cannot be made longer under the assumption that m is the last element in the occurrence of the pattern. This proves the assertion of the lemma. □

5. The enumeration of 123-avoiding permutations with a prescribed number of occurrences of the pattern (k − 1)(k − 2) … 1k. Let π be a 123-avoiding permutation. We denote the number of occurrences of the pattern (k −1)(k −2) … 1k in π by N((k − 1)(k − 2) … 1k; π).

Given a Dyck path P, we assign a weight to it, denoted by w_{2}(k; P). It is defined as the sum ∑_{p} \binom{i(p)−1}{k−1}, where the sum is over all peaks p of P, and where i(p) is the height of the peak. For example, the weight w_{2}(3; .) of the Dyck path in Figure 1 is

\binom{1}{2} + \binom{3}{2} + \binom{3}{2} + \binom{2}{2} + \binom{0}{2} = 7.

From Lemma Ψ it is immediate that

N((k − 1)(k − 2) … 1k; π) = w_{2}(k; Ψ(π)).  (4.2)

This observation, combined with Roblet and Viennot’s continued fraction theorem for the generating function of Dyck paths (see Theorem A5), allows us to express the generating function which counts 123-avoiding permutations with respect to the number of occurrences of the pattern (k − 1)(k − 2) … 1k in form of a continued fraction. Again, in the statement of the theorem, we write |π| for the number of elements which are permuted by π.

Theorem 8. The generating function ∑_{π} y^{N((k−1)(k−2)...1k;π)}x^{|π|}, where the sum is over all 123-avoiding permutations, is given by

\frac{1}{1 − x (y^{\binom{0}{k−1}} − 1) − \frac{x}{1 − x (y^{\binom{1}{k−1}} − 1) − \frac{x}{1 − x (y^{\binom{2}{k−1}} − 1) − ⋯}}} .  (4.3)

Proof. Apply Theorem A5 with λ_{i} = x and ν_{i} = xy^{\binom{i−1}{k−1}}, i = 0, 1, …, and use (4.2). □

Next, similar to Section 3, we study generating functions for 123-avoiding permutations with a fixed number of occurrences of the pattern (k − 1)(k − 2) … 1k. The first theorem restates a result due to Chow and West [2, Theorem 3.6, first case]. The proof however is different, as it is based on our Dyck path approach.

Theorem 9. The generating function ∑_{π} x^{|π|}, where the sum is over all 123-avoiding permutations which also avoid the pattern (k − 1)(k − 2) … 1k, is given by

\frac{U_{k−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})},  (4.4)

where U_{n}(x) denotes the n-th Chebyshev polynomial of the second kind.

Proof. By Lemma Ψ, the permutations in the statement of the theorem are in bijection with Dyck paths, which start at the origin, return to the x-axis, and do not exceed the height k − 1. Now we apply Theorem A2 with b_{i} = 0, λ_{i} = 1, i = 0, 1, …, K = k − 1, r = s = 0, x replaced by \sqrt{x}, and use Fact A3. □

Theorem 10. Let 1 ≤ r ≤ k − 1. The generating function ∑_{π} x^{|π|}, where the sum is over all 123-avoiding permutations with exactly r occurrences of the pattern (k − 1)(k − 2) … 1k, is given by

x^{(r−1)/2} \begin{matrix}(U_{k−1} (\frac{1}{2\sqrt{x}})) & r−1 \\ (U_{k} (\frac{1}{2\sqrt{x}})) & r+1 \end{matrix} ,  (4.5)

where U_{n}(x) denotes the n-th Chebyshev polynomial of the second kind.

Proof. By Lemma Ψ, the permutations in the statement of the theorem are in bijection with Dyck paths, which start at the origin, return to the x-axis, do not exceed height k, and have exactly r peaks at height k. (It should be noted that it is here where we use the assumption r ≤ k−1. For, a peak of height i corresponds to \binom{i−1}{k−1} occurrences of the pattern (k − 1)(k − 2) … 1k, all of which are subsequences of the occurrence of the pattern (i − 1)(i − 2) … 1i guaranteed by Lemma Ψ. Therefore, if r ≥ k then we would also have to consider paths with peaks of height higher than just k.) Such a Dyck path can be decomposed as

P_{0}u_{1}d_{1}P_{1}u_{2}d_{2}P_{2} … u_{r}d_{r}P_{r},

where P_{0} is the portion of P from the origin until the first time the height k − 1 is reached, where the u_{i}’s are up-steps from height k − 1 to height k, where the d_{i}’s are down-steps from height k to height k − 1, where the P_{i}’s, i = 1, 2, …, r − 1, are path portions which start and end at height k −1 and never exceed height k −1, and where P_{r} is the portion of P from the last point at height k − 1 until the end of the path. Application of Theorem A2 and use of Fact A3 implies, by arguments that are more or less identically to those in the proof of Theorem 3, that the generating function for those paths is equal to

\frac{1}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})} (\frac{U_{k−1} (\frac{1}{2\sqrt{x}})}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})})^{r−1} \frac{1}{\sqrt{x}U_{k} (\frac{1}{2\sqrt{x}})}x^{r},

which simplifies to (4.5). □

The special case k = 3 and r = 1 of Theorem 10 appears, in an equivalent form, in [8, Theorem 2].

We could use an idea similar to the one in the proof of Theorem 3 to express, for general r, the generating function for 123-avoiding permutations with exactly r occurrences of the pattern (k − 1)(k − 2) … 1k in form of a sum, taken over all possible ways to arrange the peaks that are at least at height k. However, it appears that it is not possible to write the result in a way that is similarly elegant as (3.5). However, for the asymptotics, the same reasoning as in the proof of Theorem 5 remains valid. I.e., in this sum, the summand which, asymptotically, provides the largest contribution, is again the summand (4.5) (which is the same as the summand in (3.5) with ℓ_{1} = r and all other ℓ_{i}’s equal to zero). Therefore an analogue of Theorem 5 in the present context is true. More precisely, the number of 123-avoiding permutations with exactly r occurrences of the pattern (k − 1)(k − 2) … 1k is asymptotically as large as the number of 132-avoiding permutations with exactly r occurrences of the pattern 12 … k. This extends [2, Corollary 4.2].

Theorem 11. Let r and k be fixed nonnegative integers. Then, as n becomes large, the number of 123-avoiding permutations with exactly r occurrences of the pattern (k − 1)(k − 2) … 1k is asymptotically

(\frac{4 sin^{2} \frac{π}{k+1}}{k + 1} )^{r+1} \frac{n^{r}}{r!} (4 cos^{2} \frac{π}{k + 1})^{n−r} (1 + O (\frac{1}{n})) .  (4.6)
□

Appendix. Generating functions for Motzkin and Dyck paths

A Motzkin path is a lattice path in the plane integer lattice ℤ^{2}, consisting of upsteps (1, 1), level-steps (1, 0), and down-steps (1, −1), which never passes below the x-axis. See Figure 2 for an example.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

A Motzkin path

Figure 2

Clearly, a Dyck path is just a Motzkin path without level-steps.

Given a Motzkin path P, we denote the length of the path (i.e., the number of steps) by ℓ(P). Furthermore, we define the weight w(P) of P to be the product of the weights of all its steps, where the weight of an up-step is 1 (hence, does not contribute anything to the weight), the weight of a level-step at height h is b_{h}, and the weight of a down-step from height h to h − 1 is λ_{h}. Thus, the weight of the Motzkin path in Figure 2 is b_{2}λ_{2}b_{1}b_{1}λ_{3}λ_{2} = b_{1}^{2}b_{2}λ_{2}^{2}λ_{3}.

The theorem below, due to Flajolet, expresses the corresponding generating function for all Motzkin paths which start at the origin and return to the x-axis in form of a continued fraction.

Theorem A1. (Flajolet [3, Theorem 1]) With the weight w defined as above, the generating function ∑_{P} w(P), where the sum is over all Motzkin paths starting at the origin and returning to the x-axis, is given by

\frac{1}{1 − b_{0} − \frac{λ_{1}}{1 − b_{1} − \frac{λ_{2}}{1 − b_{2} − ⋯}}} .  (A.1)

□

Next we recall the expression, in terms of orthogonal polynomials, for the generating function for Motzkin paths in a strip. Although this is a result in the folklore of combinatorics, probability, and statistics, the only explicit mention that I am able to provide is [14, Ch. V, (27)], which is a volume that is not easily accessible. Therefore I include a sketch of proof.

Theorem A2. Define the sequence (p_{n}(x))_{n≥0} of polynomials by

xp_{n}(x) = p_{n+1}(x) + b_{n}p_{n}(x) + λ_{n}p_{n−1}(x),  for n ≥ 1,  (A.2)

with initial conditions p_{0}(x) = 1 and p_{1}(x) = x − b_{0}. Furthermore, define (Sp_{n}(x))_{n≥0} to be the sequence of polynomials which arises from the sequence (p_{n}(x)) by replacing λ_{i} by λ_{i+1} and b_{i} by b_{i+1}, i = 0, 1, 2, …, everywhere in the three-term recurrence (A.2) and in the initial conditions. Finally, given a polynomial p(x) of degree n, we denote the corresponding reciprocal polynomial x^{n}p(1/x) by p^{∗}(x).

With the weight w defined as before, the generating function ∑_{P} w(P)x^{ℓ(P)}, where the sum is over all Motzkin paths which start at (0, r), terminate at height s, and do not pass above the line y = K, is given by

\{ \begin{matrix}\frac{x^{s−r}p_{r}^{∗}(x)S^{s+1}p_{K−s}^{∗}(x)}{p_{K+1}^{∗}(x)} & r ≤ s, \\ λ_{r} ⋯ λ_{s+1} \frac{x^{r−s}p_{s}^{∗}(x)S^{r+1}p_{K−r}^{∗}(x)}{p_{K+1}^{∗}(x)} & r ≥ s. \end{matrix}  (A.3)

Sketch of Proof. Motzkin paths which never exceed height K correspond in a oneto-one fashion to walks on the path P_{K+1} with loops attached to each vertex (this is the graph on the vertices v_{0}, v_{1}, … v_{K} where for i = 0, 1, …, K − 1 the vertices v_{i} and v_{i+1} are connected by an edge, and there is a loop for each vertex v_{i}). In this correspondence, an up-step from height h to h + 1 in the Motzkin path corresponds to a step from vertex v_{h} to vertex v_{h+1} in the walk, and similarly for level- and downsteps. It is well-known (see e.g. [12, Theorem 4.7.2]) that the generating function for walks from v_{r} to v_{s} is given by

\frac{(−1)^{r+s} det(I − xA; s, r)}{det(I − xA)},

where A is the (weighted) adjacency matrix of P_{K+1}, where I is the (K + 1) × (K + 1) identity matrix, and where det(I − xA; s, r) is the minor of (I − xA) with the s-th row and r-th column deleted.

Now, the (weighted) adjacency matrix of P_{K+1} with the property that the weight of a particular walk would correspond to the weight w of the corresponding Motzkin path is the tridiagonal matrix

A = ( \begin{matrix}b_{0} & 1 & 0 & … \\ λ_{1} & b_{1} & 1 & 0 & … \\ 0 & λ_{2} & b_{2} & 1 & 0 & … \\ ⋮ & ... & ... & ... & ... & ... & ⋮ \\ & … & 0 & λ_{K−2} & b_{K−2} & 1 & 0 \\ & & … & 0 & λ_{K−1} & b_{K−1} & 1 \\ & & & … & 0 & λ_{K} & b_{K} \end{matrix} ) .

It is easily verified that, with this choice of A, we have det(I − xA) = p_{K+1}^{∗}(x) (by expanding the determinant with respect to the last row and comparing with the three-term recurrence (A.2)), and, similarly, that the numerator in (A.3) agrees with (−1)^{r+s} det(I − xA; r, s). □

The special cases of Theorem A2 in which r = s = 0, respectively r = 0 and s = K, appear also in [3, Sec. 3.1].

The following is a well-known and easily verifiable fact:

Fact A3. If b_{i} = 0 and λ_{i} = 1 for all i, then the polynomials p_{n}(x) defined by the three-term recurrence (A.2) are Chebyshev polynomials of the second kind,

p_{n}(x) = U_{n}(x/2).  □

Fact A3, in combination with Theorem A2, tells that Chebyshev polynomials of the second kind are intimately tied to the enumeration of Dyck paths.

Although we do not make use of it in this paper, we wish to emphasize that the enumeration of Motzkin paths (i.e., also allowing level-steps) is also intimately tied to Chebyshev polynomials of the second kind.

Fact A4. If b_{i} = 1 and λ_{i} = 1 for all i, then the polynomials p_{n}(x) defined by the three-term recurrence (A.2) are also Chebyshev polynomials of the second kind, namely

p_{n}(x) = U_{n}((x − 1)/2).  □

Now we restrict our attention to Dyck paths. We refine the above defined weight w in the following way, so that in addition it also takes into account peaks: Given a Dyck path P, we define the weight ŵ(P) of P to be the product of the weights of all its steps, where the weight of an up-step is 1, the weight of a down-step from height h to h − 1 which follows immediately after an up-step (thus, together, form a peak of the path) is ν_{h}, and where the weight of a down-step from height h to h − 1 which follows after another down-step is λ_{h}. Thus, the weight of the Dyck path in Figure 1 is ν_{2}ν_{4}ν_{4}λ_{3}ν_{3}λ_{2}λ_{1}ν_{1} = ν_{1}ν_{2}ν_{3}ν_{4}^{2}λ_{1}λ_{2}λ_{3}.

The theorem below, due to Roblet and Viennot, expresses the corresponding generating function for all Dyck paths which start at the origin and return to the x-axis in form of a continued fraction.

Theorem A5. (Roblet and Viennot [10, Proposition 1]) With the weight ŵ defined as above, the generating function ∑_{P} ŵ(P), where the sum is over all Dyck paths starting at the origin and returning to the x-axis, is given by

\frac{1}{1 − (ν_{1} − λ_{1}) − \frac{λ_{1}}{1 − (ν_{2} − λ_{2}) − \frac{λ_{2}}{1 − (ν_{3} − λ_{3}) − ⋯}}} .  (A.4)

□

Finally, we remark that, from a different angle, Katzenbeisser and Panny [5] have undertaken an independent study of the enumeration of Motzkin paths.

Remark. I am indebted to the referee for an extremely careful reading of the manuscript.

References

1. S. C. Billey, W. Jockusch and R. P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), 345–374.

2. T. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, Discrete Math. 204 (1999), 119–128.

3. P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

4. M. Jani and R. G. Rieper, Continued fractions and Catalan problems, Electron. J. Combin. 7 (2000), paper #R45, 8 pp.

5. W. Katzenbeisser and W. Panny, Simple random walk statistics. I. Discrete time results, J. Appl. Probab. 33 (1996), 311–330.

6. T. Mansour and A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials, Electron. J. Combin. 7 (2000), paper #R17, 9 pp.

7. A. M. Odlyzko, Asymptotic enumeration methods, Handbook of combinatorics, Vol. 2, Elsevier, Amsterdam, 1995, pp. 1063–1229.

8. A. Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Math. Theoret. Computer Science 3 (1999), 151–154.

9. A. Robertson, H. S. Wilf and D. Zeilberger, Patterns and fractions, Electron. J. Combin. 6 (1999), #R38.

10. E. Roblet and X. G. Viennot, Théorie combinatoire des T -fractions et approximants de Padé en deux points, Discrete Math. 153 (1996), 271–288.

11. R. Simion and F. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985), 383–406.

12. R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986, reprinted by Cambridge University Press, Cambridge, 1998.

13. R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.

14. X. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, UQAM, Montreal, Quebec, 1983.

15. J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995), 247–262.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.