Parametric Production Matrices and Weighted Succession Rules: a Dyck Path

Example

Robert Parviainen ARC Centre of Excellence for Mathematics and Statistics of Complex Systems The University of Melbourne 139 Barry Street 3010 Victoria Australia

                   robertp@ms.unimelb.edu.au

Abstract We introduce weighted succession rules and parametric production matrices — simple extensions of the standard ECO method succession rules and production matrices. The purpose is to enumerate combinatorial objects with respect to several variables. We consider one main example, from the theory of Dyck paths. The path statistics primarily considered are peak height, rise height, and certain subwalks. Many classical sequences (such as the Catalan, Motzkin, Narayana and Schroeder numbers) are incorporated in this example.

1 Introduction

Recently Deutsch, Ferrari and Rinaldi [2] introduced production matrices as a device for ECO method calculations. Building on the concept of generating trees, the Enumeration of Combinatorial Objects method was developed and systematised by Barcucci and collaborators [1]. It is a general method for enumerating combinatorial objects by studying how the objects grow according to a parameter. At the centre of method are the succession rules that describe how the objects grow — production matrices translate these to matrix notation.

The production matrices considered by Deutsch et al. are integer valued. The step to include matrices with parameters is natural and straightforward, and corresponds to weighted succession rules. In this paper we study a rich example of a parametric production matrix. Although only one matrix, it embodies many well known combinatorial number sequences, such as the Catalan, Motzkin, and Narayana numbers. The underlying objects for our matrix are Dyck paths, and the main statistics considered are heights of peaks and rises, and occurrences of certain subwalks. We recover known results about the height distribution of peaks, and use the matrix to show that it is equivalent to a rise height distribution.

In Section 2 we give a brief description of the ECO method, define succession rules and production matrices, and introduce weighted successions. We recall results from Deutsch et. al [2] for operations on product matrices (which continue to hold in the parametric case). In Section 3 we define Dyck paths and some of their statistics. We then define a parametric production matrix and show how it is related to those statistics.

2 The ECO method

The core of the ECO method is a recursive description of a class of combinatorial objects. This should be done in such a way that, if O_{n} denotes the set of objects of size n, each object O′ ∈ O_{n+1} is achieved from one and only one object O ∈ O_{n}. We say that O′ is a successor of O.

We assign a label (k), k ∈ ℕ^{+} (the positive integers), to each object. An object’s label gives the number of successors of that object. The succession rule dictates the labels of these successors. The rule also includes an axiom (a), a ∈ ℕ^{+}, which gives the label of the smallest object. In the basic case a succession rule Ω is written as

Ω = \begin{cases}(a) \\ (k) ⇝ (e_{1}(k)) (e_{2}(k)) ⋯ (e_{k}(k)) \end{cases} ,

where e_{i}(k) : ℕ^{+} → ℕ^{+} gives the labels of the k successors of an object with label k.

It is natural to think of a succession rule as a generating tree: the root of the tree is the axiom, (a), and if a node has label (k), it has k children labelled e_{1}(k), e_{2}(k), …, e_{k}(k).

A succession rule Ω defines a sequence of positive integers a_{n} = the number of nodes at level n, n ≥ 0. The generating function for a_{n} is defined by f_{Ω}(z) = ∑_{n} a_{n}z^{n}.

The production matrix P (Ω) = P = (p_{i,j})_{i,j≥1} of a succession rule is defined as follows. List all labels of a rule. Let this list be l_{1}, l_{2}, . . .. Then p_{i,j} equals the number of successors with label l_{j} produced by an object with label l_{i}.

Example 1. The succession rule

Ω = \begin{cases}(1) \\ (1) ⇝ (2) \\ (2) ⇝ (1)(2) \end{cases} ,

has production matrix

P (Ω) = ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) ,

since label (1) has one successor with label (2) and (2) has two successors with labels (1) and (2). The sequence defined by Ω is the Fibonacci sequence (A000045^{1}), a_{n} = 1, 1, 2, 3, 5, 8, . . ..

2.1 Parametric production matrices and weighted succession rules

Naturally, one would like to use the ECO method to obtain not only the size distribution of the objects, but also multi–dimensional distributions.

One strategy is to choose the labels wisely, since the distribution of labels on objects of a given size might be acquired. Indeed, using production matrices this is essentially as easy (or hard) as getting the size distribution. Another strategy is to use the succession rule and other data to find functional relations for the multivariate generating function.

One of the aims of this paper is to demonstrate an alternative way of using production matrices to find multivariate distributions, by introducing weighted succession rules and parametric production matrices. The idea is simple:

Assume we are interested in the distribution of property, jointly with size. If a succession (k) ⇝ (l) adds one property, we give that succession weight x. The sequence generated by the succession rule now is the weighted sum over objects of given size, and the generating function for the sequence is the bivariate generating function for property and size.

Let W be a set of weights, and consider a matrix P = (p_{i,j})_{i,j≥1} where p_{i,j} ∈ W. This parametric production matrix corresponds to a weighted succession rule. A weighted succession rule is written as

Ω = \begin{cases}(a; w (a)) \\ (k) ⇝ (e_{1}(k); w (e_{1}(k))) (e_{2}(k); w (e_{2}(k))) ⋯ (e_{k}(k); w (e_{k}(k))) \end{cases} ,

where again e_{i}(k) : ℕ^{+} → ℕ^{+} gives the labels of the k successors of an object with label (k), and w (e_{i}(k)) ∈ W gives the weight of that particular succession. We also have the possibility to give the axiom a a weight w(a). Of course, if W = {1} we recover the unweighted succession rules.

The generating tree interpretation is as follows. Give the root weight w(a) and label (a). A node in the tree with label (k) has k children, labelled e_{1}(k) to e_{k}(k). Give the edge between the parent and child e_{i}(k) weight w (e_{i}(k)). Using the tree interpretation, the weight of an object is easily defined: it is the product of the weight of the root and the weights of the edges in the (unique) path in the generating tree from the root to the node corresponding to the object.

From a weighted succession rule Ω, a parametric production matrix P (Ω) = P = (p_{i,j})_{i,j≥1} is defined as follows. List all labels of a rule. Let this list be l_{1}, l_{2}, . . .. Then p_{i,j} equals the sum of weights of successors with label l_{j} produced by an object with label l_{i}. The sequence {a_{n}}_{n≥0} produced by Ω is now a sequence of polynomials in W, and we write

f_{Ω}(W, z) = ∑_{n=0}^{∞} a_{n}z^{n}.

1Six-digit numbers prefixed by ‘A’ indicate the corresponding entry in The On-Line Encyclopedia of Integer Sequences [4].

Example 2. The succession rule

Ω = \begin{cases}(1; 1) \\ (1) ⇝ (2; 1) \\ (2) ⇝ (1; x)(2; 1) \end{cases} ,

has production matrix

P (Ω) = ( \begin{matrix}0 & 1 \\ x & 1 \end{matrix} ) .

The sequence defined by Ω gives the Fibonacci polynomials (\underline{A011973}) a_{n} = 1, 1, 1 + x, 1 + 2x, 1 + 3x + x^{2}, 1 + 4x + 3x^{2}, . . ..

Let us fix some notation. Let u^{⊤} = {1 0 0 …}, e = {1 1 1 …}^{⊤} and I define a row vector, column vector, and identity matrix, respectively, of appropriate size. If a succession rule Ω defines a sequence a_{n} with generating function f_{Ω}(W, z), we say that P = P (Ω) defines a_{n} and write P → a_{n} and P → f_{Ω}(W, z).

We now cite some useful results for production matrices. These are from Deutsch et. al [2], where they were stated in terms of integer valued production matrices. To verify that these still hold in the parametric case is trivial.

Fact 1 (Fact (iii), [2]). If P → a_{n} then a_{n} = u^{⊤}P^{n}e.

Fact 2 (Fact (v), [2]). If P → f(W, z) then f(W, z) = u^{⊤}(I − zP)^{−1}e.

Theorem 3 (Theorem 3.2, [2]). If b, c and r are nonnegative integers or weights and P → f(W, z), then

M = ( \begin{matrix}b & ru^{⊤} \\ ce & P \end{matrix} ) → \frac{1 + rzf(W, z)}{1 − bz − rcz^{2}f(W, z)}.

Corollary 4 (Corollary 3.1, [2]). If b, c and r are nonnegative integers or weights and

P = ( \begin{matrix}b & ru^{⊤} \\ ce & P \end{matrix} ) → f(W, z),

then f(W, z) satisfies

rcz^{2}f^{2}(W, z) − (1 − (b + r)z)f(W, z) + 1 = 0.

3 The Main Example

3.1 Dyck paths

A Dyck path is a lattice path in the first quadrant from (0, 0) to (2n, 0) that uses steps (1, 1), we call these up, or u, steps, and (1, −1) (down, or d, steps). We will call n the semilength of the path. Let 𝔻_{n} denote the set of Dyck paths of semilength n. The number of Dyck paths of semilength n are given by the nth Catalan number c_{n} (\underline{A000108}),

c_{n} = \frac{1}{n + 1}\binom{2n}{n}.

The generating function for the Catalan numbers satisfies

C(z) = 1 + zC^{2}(z) = ∑_{n=0}^{∞} c_{n}z^{n} = \frac{1 − \sqrt{1 − 4z}}{2z} .

A peak in a Dyck path p is an occurrence of an up step immediately followed by a down step. The height of the peak is the height of the start point of the u step. A high peak is a peak at height 1 or higher. A rise is a maximal sequence of consecutive u steps. The height of the rise is the number of u steps minus 1. A high rise is a rise with positive height. A contact is any place the path touches the x-axis. A segment is any subpath consisting of consecutive steps. The segment is a level segment if it starts and ends at the same height. An excursion is the segment of the walk between two contacts with no other contact in between. Note that a Dyck path p with k + 1 contacts can be decomposed uniquely into its k excursions p = e_{1}e_{2} ⋯ e_{k}.

Figure 1: A Dyck path of semilength 9. The height of the rises are, in order, 1,2,0,1,0. The path has 4 high peaks, of heights 1,3,3,3. Using succession rule Ω of Theorem 5 the path will have weight x_{0}^{5}x_{1}x_{2}^{3}y_{1}^{1}y_{2}^{2}y_{4}^{1}. Using succession rule Ω′ of Theorem 8 the path will have weight y_{1}^{1}y_{3}^{3}.

3.2 The matrix

We are interested in the following matrix.

P = ( \begin{matrix}x_{1}y_{1} & x_{0} & 0 & 0 & 0 & 0 & ⋯ \\ x_{2}y_{1} & x_{1}y_{2} & x_{0} & 0 & 0 & 0 & ⋯ \\ x_{3}y_{1} & x_{2}y_{2} & x_{1}y_{3} & x_{0} & 0 & 0 & ⋯ \\ x_{4}y_{1} & x_{3}y_{2} & x_{2}y_{3} & x_{1}y_{4} & x_{0} & 0 & ⋯ \\ x_{5}y_{1} & x_{4}y_{2} & x_{3}y_{3} & x_{2}y_{4} & x_{1}y_{5} & x_{0} & ⋯ \\ x_{6}y_{1} & x_{5}y_{2} & x_{4}y_{3} & x_{3}y_{4} & x_{2}y_{5} & x_{1}y_{6} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

It is, as is shown below, the production matrix for Dyck paths, where the y_{k} marks the height of rise number k and x_{k} marks level segments of the form u(uq_{k}d)^{k}d, where q_{k} are Dyck paths. We note that many classical number sequences arise from specialisations of the sequence associated with P. See Section 3.3.

Theorem 5. For a Dyck path p, let h_{k}(p) denote the height of rise number k in p and let s_{k}(p) denote the number of level segments of type u(uq_{k}d)^{k}d, where q_{k} are Dyck paths. Then the weighted sum a_{n} over Dyck paths of semilength n is given by

a_{n} := ∑_{p∈𝔻_{n}} x_{0}^{h_{0}(p)}y_{1}^{s_{1}(p)}x_{1}^{h_{1}(p)}y_{2}^{s_{2}(p)} ⋯ = u^{⊤}P^{n}e,

and the generating function is given by

F (x_{0}, x_{1}, …; y_{1}, y_{2}, …; z) : = ∑_{n} z^{n} ∑_{p∈𝔻_{n}} x_{0}^{h_{0}(p)}y_{1}^{s_{1}(p)}x_{1}^{h_{1}(p)}y_{2}^{s_{2}(p)} ⋯
= u^{⊤}(I − zP)^{−1}e.

Figure 2: The generating tree associated with the succession rule of Theorem 5.

Proof. We will describe a weighted succession rule Ω for Dyck paths whose parametric production matrix is P. The labels are the number of contacts (= the number of excursions + 1). The axiom is the path ud with label (2; x_{0}). The generating tree for this rule is sketched in Figure 2.

Given a Dyck path p of length n with k excursions, p = e_{1}e_{2} ⋯ e_{k} we now explain how the successors are derived. There are k + 1 successors to p, with 1, 2, ⋯, k + 1 excursions. They are, respectively,

1 ue_{1}e_{2} ⋯ e_{k}d

2 e_{1}ue_{2} ⋯ e_{k}d ⋮

k e_{1}e_{2} ⋯ e_{k−1}ue_{k}d k+1 e_{1}e_{2} ⋯ e_{k}ud.

Now, let a succession from a path with k excursions to one with l, 1 ≤ l ≤ k +1, have weight y_{l}x_{k−l+1}. The succession increases the height of rise number l by one and adds one excursion, by default a level segment, of type u(uqd)^{k−l+1}d to the path as desired. Furthermore, each path has exactly one parent: the path obtained by lowering the last excursion uqd to q, a Dyck path.

In the following, we will use the notation x = (x_{0}, x_{1}, x_{2}, …) and y = (y_{1}, y_{2}, y_{3}, …). If x_{k} = 1 for k > n we will write F (x_{1}, …, x_{n}; y; z) instead of F (x; y; z), and similarly for y.

Corollary 6.

F_{0} := F (x_{0}, x_{1}; ; z) = \frac{1 − (x_{0} + x_{1})z − \sqrt{(1 − (x_{0} + x_{1})z)^{2} − 4x_{0}z^{2}}}{2x_{0}z^{2}}

Proof. It follows from Corollary 4 that

x_{0}z^{2}F_{0}^{2} − (1 − (x_{0} + x_{1})z) F_{0} + 1 = 0.

Applying Theorem 3 we get

Corollary 7.

F_{1} := F (x_{0}, x_{1}; y_{1}; z) = \frac{1 + x_{0}zF_{0}(x_{0}, x_{1}; ; z)}{1 − x_{1}y_{1}z − x_{0}y_{1}z^{2}F_{0}(x_{0}, x_{1}; ; z)},

and in general

F_{k} := F (x_{0}, x_{1}; y_{1}, y_{2}, …, y_{k}; z) = \frac{1 + x_{0}zF_{k−1}(x_{0}, x_{1}; y_{2}, …, y_{k}; z)}{1 − x_{1}y_{1}z − x_{0}y_{1}z^{2}F_{k−1}(x_{0}, x_{1}; y_{2}, …, y_{k}; z)}.

Note the use of F_{k−1}(x_{0}, x_{1}; y_{2}, …, y_{k}; z) and not of F_{1}(x_{0}, x_{1}; y_{1}, …, y_{k−1}; z).

Below we find bivariate generating functions F (1, …, 1, x_{k}; 1; z) for length and height of rise number k in a Dyck path. First we show that the heights of high rises have the same distribution as the number of high peaks. The reason for not using the perhaps more familiar high peak statistics in the definition of the main production matrix is that the joint distribution of number of high peaks and level segments is not the same as the joint distribution of heights of rises and level segments.

Theorem 8. The number of Dyck paths with whose high rises have heights (in order) k_{1}, …, k_{l} equals the number of Dyck paths with k_{1}, …, k_{l} high peaks of heights 1, …, l, respectively.

Figure 3: The generating tree associated with the succession rule of Theorem 8.

Proof. The result can be proved by describing an appropriate succession rule Ω′. This will be such that P (Ω′) = P (Ω)|_{x=0}. The generating tree for this rule is sketched in Figure 3.

Paths are labeled by the number of steps in the last descent minus 1, except if that number is 0, in which we have two subcases:

i. If the path is a sequence of uds, the label is the number of those uds plus 1.

ii. Otherwise the label is the number of successive uds at the end plus the number of steps in the last descent.

In both cases the label equals the parent’s label plus 1. The axiom is the path ud, and is given weight 1. The successors of a path p with label (k) are paths p_{1}, …, p_{k+1} with labels (1) to (k + 1). The path p_{k+1} is pud. The path p_{l}, l ≤ k, is achieved from p as follows. It is a combination of the paths p and q = u^{l+1}d^{l+1}; the latter is placed such that it ends at 2n + 2 and in p_{l} we follow p up to the first intersection of p and q, after which we follow q. See Figure 4 for illustration.

Now, note that the high peaks (if any) of p are preserved in p_{l}, and if, l ≤ k, p_{l} has an extra peak at height l. It is thus clear that if we give the updates of (k) weights y_{1}, …, y_{k}, 1 the succession rule corresponds to heights of high peaks as desired. It is also easy to see that each path has a unique parent.

The next result is essentially equivalent to one of Mansour, [3, Theorem 1.1(ii)]. Mansour gives generating functions for k peaks of height h in terms of Chebyshev polynomials. These can be summed to give an equivalent function for peaks of height h. As a function of t, the function G_{n} below is of the form \frac{a+bt}{c+dt}, and so can easily be expanded in t to give one–dimensional generating functions if desired.

Figure 4: Example of the use of the concatenation rule used in the proof of Theorem 8.

Corollary 9. Let G_{n}(t, z) be the generating function for high peaks of height n ≥ 1,

G_{n}(t, z) = ∑_{i=0}^{∞} ∑_{j=0}^{∞} g_{i,j}z^{i}t^{j},

where g_{i,j} is the number of Dyck paths of semilength i + 1 with j high peaks at height n.

Then

G_{1}(t, z) = \frac{1 + zC(z)^{2}}{1 − tz − tz^{2}C(z)^{2}} ,

and for n ≥ 2

G_{n}(t, z) = \frac{G_{1}(t, z)zU(n − 4, \frac{1}{2\sqrt{z}}) − U(n − 2, \frac{1}{2\sqrt{z}})}{G_{1}(t, z)z^{2}U(n − 2, \frac{1}{2\sqrt{z}}) − zU(n, \frac{1}{2\sqrt{z}})}

Proof. The first statement follows from Corollaries 6 and 7.

Let P_{n} be the matrix P with all parameters except y_{n} set to 1. Now

P_{n} = ( \begin{matrix}1 & u^{⊤} \\ e & P_{n−1} \end{matrix} ) .

By Theorem 3 the generating function for P_{n}, n ≥ 2 is

G_{n} = \frac{1 + zG_{n−1}}{1 − z − z^{2}G_{n−1}}

Now, straightforward but cumbersome calculations show that \frac{G_{1}zU(n−4, \frac{1}{2\sqrt{z}})−U(n−2, \frac{1}{2\sqrt{z}})}{G_{1}z^{2}U(n−2, \frac{1}{2\sqrt{z}})−U(n, \frac{1}{2\sqrt{z}})} satis-

fies the recursion.

Remark 1. The stated formula for G_{n} in fact holds for n = 0 and n = 1 as well.

3.3 Examples

As mentioned earlier, many well–known combinatorial sequences are contained in the sequence produced by the main matrix P. Here we list a selection of the most interesting of these.

• F (; ; z) → 1, 2, 5, 14, … = the Catalan numbers = the number of Dyck paths. (\underline{A000108}).

• F (1, 0; ; z) → 1, 1, 2, 4, 9, … = the Motzkin numbers = the number of Motzkin paths. (\underline{A001006}).

• F (2; ; z) → 1, 3, 11, 45, … = the little Schroeder numbers = the number of Schroeder paths with no peaks at height 1 (\underline{A001003}).

• F (s; ; z) → 1, 1 + t, 1 + 3t + t^{2}, 1 + 6t + 6t^{2} + t^{3}, … = the Narayana numbers = the number of Dyck paths with k peaks. (\underline{A001263}).

• F (2s; ; z) → 1, 1 + 2t, 1 + 6t + 4t^{2}, 1 + 12t + 24t^{2} + 8t^{3}, … = the number of double rise bi-colored Dyck paths with k double rises. (\underline{A114687}).

• F (1 + s; ; z) → 1, 2 + t, 5 + 5t + t^{2}, 14 + 21t + 9t^{2} + t^{3}, … = the number of Schroeder paths with k peaks, but none at height 1 = the number of double rise bi-colored Dyck paths with k double rises of a given color. (\underline{A126216}).

• F (1, 2; ; z) → 1, 3, 10, 36, 137, … = the number of Schroeder paths with 0 peaks at odd level. (\underline{A002212}).

• F (1, s; ; z) → 1, 1 + t, 2 + 2t + t^{3}, 4 + 6t + 3t^{2} + t^{3}, … = the number of Dyck paths with k peaks at even height. (\underline{A091869}).

• F (t, 2; ; z) → 1, 2 + t, 4 + 5t + t^{2}, 8 + 18t + 9t^{2} + t^{3}, … = the number of hex tree by edges and left edges (\underline{A126182}).

• F (1, 1 + t; ; z) → 1, 2 + t, 5 + 4t + t^{2}, 14 + 15t + 6t^{2} + t^{3}, … = the number of hex tree by edges and median children (\underline{A126181}).

• F (; 2; z) → 1, 3, 10, 35, … = the number of times a fixed Dyck word of length 2k occurs in all Dyck words of length 2n + 2k = \binom{2n+1}{n+1}, (\underline{A001700}).

• F (; 1 + t; z) → 1, 2 + t, 5 + 4t + t^{2}, 14 + 14t + 6t^{2} + t^{3}, … = the number of leaves at level k+1 in all ordered trees with n+1 edges (\underline{A039598}).

• F (0, 1; 1 + t; z) → 1, 1 + t, 1 + 2t + t^{3}, 1 + 3t + 3t^{2} + 1, … = Pascal’s triangle (\underline{A007318}).

• F (0, 1 + t; 1; z) → 1, 1 + t, 1 + 2t + t^{3}, 1 + 3t + 3t^{2} + 1, … = Pascal’s triangle (\underline{A007318}).

• F (1, 0; t; z) → 1, 1, 1+t, 2+2t, 4+4t+t^{2}, … = the number of Motzkin paths by height of final descent (\underline{A098979}).

Note that in all these cases Corollary 4 can be use to find a quadratic equation for the generating function. Conversely, we have the following result.

Corollary 10 (Corollary 3.2, [2]). If a generating function f satisfies an equation of the form

x_{0}y_{1}z^{2}f^{2} − (1 − (x_{1}y_{1} + x_{0})z) f + 1 = 0,

then f = F (x_{0}, x_{1}; y_{1}; z).

References

[1] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. Eco: A methodology for the Enumeration of Combinatorial Objects. J. Difference Eq. Appl., 5 (1999), 435–490.

[2] E. Deutsch, L. Ferrari, and S. Rinaldi. Production matrices. Advances Appl. Math., 34 (2005), 101–122.

[3] T. Mansour. Counting peaks at height k in a Dyck path. J. Integer Sequences, 5 (2002), Article 02.1.1.

[4] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. Published electronically

   at http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: Primary 05A05; Secondary 05A15.

Keywords: ECO method, succession rule, generating tree, production Matrix, Dyck path.

(Concerned with sequences \underline{A000045}, \underline{A000108}, \underline{A001003}, \underline{A001006}, \underline{A001263}, \underline{A001700}, \underline{A002212}, \underline{A007318}, \underline{A011973}, \underline{A039598}, \underline{A091869}, \underline{A098979}, \underline{A114687}, \underline{A126181}, \underline{A126182}, and \underline{A126216}.)

Received January 29 2007; revised version received June 6 2007. Published in Journal of Integer Sequences, June 6 2007.

Return to Journal of Integer Sequences home page.