A Recursive Relation for Weighted Motzkin Sequences

Wen-jin Woan Department of Mathematics Howard University Washington, D.C. 20059 USA

                       wwoan@howard.edu

Abstract

We consider those lattice paths that use the steps Up, Level, and Down with assigned weights w, u, and v. In probability theory, the total weight is 1. In combinatorics, we regard weight as the number of colors and normalize by setting w = 1. The lattice paths generate Motzkin sequences. Here we give a combinatorial proof of a three-term recursion for a weighted Motzkin sequence and we find the radius of convergence.

1 Introduction

We consider those lattice paths in the Cartesian plane starting from (0, 0) that use the steps U, L, and D, where U = (1, 1), an up-step; L = (1, 0), a level-step; and D = (1, −1), a down-step. Let c and d be positive integers, and color the L steps with d colors and the D steps with c colors. Let A(n, k) be the set of all colored paths ending at the point (n, k), and let M(n, k) be the set of lattice paths in A(n, k) that never go below the x-axis. Let a_{n,k} = |A(n, k)|, m_{n,k} = |M(n, k)|, and m_{n} = |M(n, 0)|. The number m_{n} is called the (1, d, c)- Motzkin number. Let B(n, k) denote the set of lattice paths in A(n, k) that never return to the x-axis and let b_{n,k} = |B(n, k)|. Note that a_{n,k} = a_{n−1,k−1} + da_{n−1,k} + ca_{n−1,k+1}. Here we give a combinatorial proof of the following three-term recursion for the (1, d, c)-Motzkin sequence:

(n + 2)m_{n} = d(2n + 1)m_{n−1} + (4c − d^{2})(n − 1)m_{n−2}.

If \frac{\sqrt{c}}{2} ≤ d, then lim_{n→∞} \frac{m_{n}}{m_{n−1}} = k = d + 2\sqrt{c}.

Example 1. The first few terms of the (1, 3, 2)-Motzkin numbers are m_{0} = 1, 3, 11, 45, 197, 903, …, k = 3+2\sqrt{2}. This sequence is the little Schroeder number sequence and is Sloane’s sequence \underline{A001003}. Some entries of the matrices (a_{n,k}), (m_{n,k}) and (b_{n,k}) are as follows;

(a_{n,k}) = [ \begin{matrix}n/k & −4 & −3 & −2 & −1 & 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 2 & 3 & 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 4 & 12 & 13 & 6 & 1 & 0 & 0 \\ 3 & 0 & 8 & 36 & 66 & 63 & 33 & 9 & 1 & 0 \\ 4 & 16 & 96 & 248 & 360 & 321 & 180 & 62 & 12 & 1 \end{matrix} ] ,

(m_{n,k}) = [ \begin{matrix}n/k & 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 3 & 1 & 0 & 0 & 0 \\ 2 & 11 & 6 & 1 & 0 & 0 \\ 3 & 45 & 31 & 9 & 1 & 0 \\ 4 & 197 & 156 & 60 & 12 & 1 \end{matrix} ] ,

(b_{n,k}) = [ \begin{matrix}n/k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 3 & 1 & 0 & 0 & 0 \\ 3 & 0 & 11 & 6 & 1 & 0 & 0 \\ 4 & 0 & 45 & 31 & 9 & 1 & 0 \\ 5 & 0 & 197 & 156 & 60 & 12 & 1 \end{matrix} ] .

Example 2. The first few terms of the (1, 2, 1)-Motzkin numbers are m_{0} = 1, 2, 5, 14, 42, …, k = 2 + 2\sqrt{1} = 4. This sequence is the Catalan sequence, Sloane’s sequence \underline{A000108}.

Example 3. The first few terms of the (1, 1, 1)-Motzkin numbers are m_{0} = 1, 1, 2, 4, 9, 21, …, k = 1 + 2\sqrt{1} = 3. The sequence is the Motzkin sequence, discussed by Woan [5], and is Sloane’s sequence \underline{A001006}.

2 Main Results

We apply the cut and paste technique to prove the following lemma. Please refer to Dershowitz and Zaks [1] and Pergola and Pinzani [2] for information about the technique.

Lemma 4. There is a combinatorial proof for the equation m_{n} = b_{n+1,1} = db_{n,1} + cb_{n,2} = dm_{n−1} + cb_{n,2}.

Proof. Let P ∈ B(n + 1, 1). Remove the first step (U) and note that the remaining is in M(n, 0).

For example, the path P = UULDLUUUDDLD ∈ B(12, 1) becomes Q = ULDLUUUDDLD ∈ M(11) where × marks the origin.

P = \begin{aligned}& & & & & & & & ∘ \\ & & & & & & & ∘ & & ∘ \\ & & ∘ & ∘ & & & ∘ & & & & ∘ & ∘ \\ & ∘ & & & ∘ & ∘ & & & & & & & ∘ \\ × \end{aligned} ,

Q = \begin{aligned}& & & & & & & ∘ \\ & & & & & & ∘ & & ∘ \\ & ∘ & ∘ & & & ∘ & & & & ∘ & ∘ \\ × & & & ∘ & ∘ & & & & & & & ∘ \end{aligned} .

Theorem 5. There is a combinatorial proof for the equation (n + 1)b_{n+1,1} = a_{n+1,1}.

Proof. Wendel [4] proved a similar result. Let

S(n + 1) = {P^{∗} : P ∈ B(n + 1, 1)

where P^{∗} is P with one vertex marked}. Then |S(n + 1)| = (n+1)b_{n+1,1}. Let P^{∗} ∈ S(n+1). The marked vertex partitions the path into P = F B, where F is the front section and B is the back section. Then Q = BF ∈ A(n + 1, 1). Note that, graphically, the point of attachment is the rightmost lowest point of Q.

Conversely, starting with any path we may find the rightmost lowest point of Q and reverse the procedure to create a marked path P^{∗} in B(n + 1, 1).

For example,

P^{∗} = \begin{aligned}& & & & & & & & ∘ \\ & & & & & & & ∘ & & ∘ \\ & & ∘ & • & & & ∘ & & & & ∘ & ∘ \\ & ∘ & & & ∘ & ∘ & & & & & & & ∘ \\ × \end{aligned} ∈ S(12),

→ Q = \begin{aligned}& & & & & ∘ \\ & & & & ∘ & & ∘ & & & & & ∘ & ∘ \\ × & & & ∘ & & & & ∘ & ∘ & & ∘ \\ & ∘ & ∘ & & & & & & & • \end{aligned} ∈ A(12, 1).

Proposition 6. The total number of L steps in M(n) is the same as that in B(n + 1, 1) and is da_{n,1}.

Proof. From the proof of Lemma 4, there is a bijection between M(n) and B(n + 1, 1). Let P = F LB ∈ B(n+1, 1) with an L step. Then Q = BF ∈ A(n, 1). Note that the attachment point is the rightmost lowest point in Q since P ∈ B(n + 1, 1). This identification suggests the inverse mapping. Note that there are d colors for an L step.

For example,

P = \begin{aligned}& & & & & & & & ∘ \\ & & & & & & & ∘ & & ∘ \\ & & • & • & & & ∘ & & & & ∘ & ∘ \\ & ∘ & & & ∘ & ∘ & & & & & & & ∘ \\ × \end{aligned} ∈ B(12, 1),

→ Q = \begin{aligned}& & & & & ∘ \\ & & & & ∘ & & ∘ & & & & & ∘ \\ × & & & ∘ & & & & ∘ & ∘ & & ∘ \\ & ∘ & ∘ & & & & & & & • \end{aligned} ∈ A(11, 1).

Proposition 7. There is a combinatorial proof for the equation

a_{n,0} = m_{n} + \frac{1}{2}(nm_{n} − da_{n,1}) = b_{n+1,1} + \frac{1}{2}(nb_{n+1,1} − dnb_{n,1}).

Proof. Let T (n) = {P^{e} : P ∈ M(n) where P^{e} is P with a U step marked}. By Theorem 5 and Proposition 6 the number of L steps among all paths in M(n) is da_{n,1} = dnb_{n,1}. The total number of steps among all paths in M(n) is nm_{n} = nb_{n+1,1}, hence the total number of U steps among all paths in M(n) is \frac{1}{2}(nb_{n+1,1} − dnb_{n,1}) = |T (n)|. Let P^{e} = F UB ∈ T (n) with a U step marked. Then Q = BUF ∈ A(n, 0) − M(n, 0) and the initial point of U in Q is the rightmost lowest point in Q. The inverse mapping starts with the rightmost lowest point. Note that |M(n, 0)| = m_{n} = b_{n+1,1}

For example,

P^{e} = \begin{aligned}& & & & ∘ & & ∘ & ∘ \\ & & & • & & ∘ & & & ∘ \\ & ∘ & • & & & & & & & ∘ & ∘ \\ × & & & & & & & & & & & ∘ \end{aligned} ∈ T (11),

Q = \begin{aligned}& ∘ & & ∘ & ∘ \\ × & & ∘ & & & ∘ & & & & & ∘ & ∘ \\ & & & & & & ∘ & ∘ & & • \\ & & & & & & & & • \end{aligned} ∈ A(11, 0).

Proposition 8. There is a combinatorial proof for the equation

a_{n,0} = a_{n−1,−1} + da_{n−1,0} + ca_{n−1,1} = 2ca_{n−1,1} + da_{n−1,0}
= 2c(n − 1)b_{n−1,1} + d(b_{n,1} + \frac{1}{2}((n − 1)b_{n,1} − d(n − 1)b_{n−1,1})) .

Proof. The first equality represents the partition of A(n, 0) by the last step (U, L or D). The second equality represents the fact that a_{n−1,−1} = ca_{n−1,1}, since elements in A(n−1, −1) have one more D step than those in A(n − 1, 1). And the last equality holds by Theorem 5 and Proposition 7.

Sulanke [3] proved the following result for the Motzkin sequence. Theorem 9. (n + 2)m_{n} = (2dn + d)m_{n−1} + (4c − d^{2})(n − 1)m_{n−2}. Proof. By Propositions 7 and 8

b_{n+1,1} + \frac{1}{2}(nb_{n+1,1} − dnb_{n,1}) = 2c(n − 1)b_{n−1,1} + db_{n,1} + (\frac{1}{2}((n − 1)b_{n,1} − d(n − 1)b_{n−1,1})) .

By Lemma 4

m_{n} + \frac{1}{2}(nm_{n} − dnm_{n−1}). = 2c(n − 1)m_{n−2} + dm_{n−1} + d(\frac{1}{2}((n − 1)m_{n−1} − d(n − 1)m_{n−2})) .

Equivalently

(n + 2)m_{n} = (2dn + d)m_{n−1} + (4c − d^{2})(n − 1)m_{n−2} .

Theorem 10. lim_{n→∞} \frac{m_{n}}{m_{n−1}} = k = d + 2\sqrt{c}. Proof. By Theorem 9, let

s_{n} := \frac{m_{n}}{m_{n−1}} = \frac{d(2n + 1)}{n + 2} + (\frac{(4c − d^{2})(n − 1)}{n + 2})\frac{m_{n−2}}{m_{n−1}} ,

and let

a_{n} := \frac{d(2n + 1)}{n + 2} = 2d − \frac{3d}{n + 2}
b_{n} := \frac{(4c − d^{2})(n − 1)}{n + 2} = (4c − d^{2})(1 − \frac{3}{n + 2}).

Then s_{n} = a_{n+} \frac{b_{n}}{s_{n−1}} .

If the sequence s_{n} = a_{n+} \frac{b_{n}}{s_{n−1}} has limit k, then k^{2} = 2dk+(4c−d^{2}) and k = ^{\frac{2d+\sqrt{4d^{2}+4(4c−d^{2})}}{2}} = d + 2\sqrt{c}. Case 1. 4c − d^{2} ≥ 0.

If s_{n−1} ≤ k, then

s_{n} = a_{n+} \frac{b_{n}}{s_{n−1}} ≥ 2d − \frac{3d}{n + 2} + \frac{(4c − d^{2})\frac{n−1}{n+2}}{k} = k − \frac{3dk + 3(4c − d^{2})}{k(n + 2)}
= k − \frac{3k^{2} − 3dk}{k(n + 2)} = k − \frac{3(k − d)}{n + 2}

and

s_{n+1} = a_{n+1} + \frac{b_{n+1}}{s_{n}} ≤ 2d − \frac{3d}{n + 3} + \frac{(4c − d^{2})(\frac{n}{n+3})}{k − \frac{3(k−d)}{n+2}}

= 2d − \frac{3d}{n + 3} + \frac{(4c − d^{2})}{k}(1 − \frac{3 dn + 9d − 3k}{(n + 3)(kn − k + 3d)})
= 2d + \frac{(4c − d^{2})}{k} − \frac{3d}{n + 3} − \frac{(4c − d^{2})}{k} \frac{3 dn + 9d − 3k}{(n + 3)(kn − k + 3d)}
= k − \frac{3(2dn(k − d) − (k − d)(k − 3d))}{(n + 3)(kn − k + 3d)}
= k − \frac{6(k − d)(d(n + 1) − \sqrt{c})}{(n + 3)(kn − k + 3d)}.

Note that s_{1} = \frac{d}{1} and s_{2} = \frac{d^{2}+c}{d} = d + \frac{c}{d}. If \frac{\sqrt{c}}{2} ≤ d, then s_{1}, s_{2} ≤ k. By induction on both odd and even n we have

k − \frac{3(k − d)}{n + 3} ≤ s_{n+1} ≤ k − \frac{6(k − d)(d(n + 1) − \sqrt{c})}{(n + 3)(kn − k + 3d)} ≤ k .

and lim_{n→∞} \frac{m_{n}}{m_{n−1}} = k.

Case 2. 4c − d^{2} < 0.

Inductively, assuming that s_{n−1} ≤ k and {s_{i}} is nondecreasing up to n − 1. Then

s_{n} = a_{n+} \frac{b_{n}}{s_{n−1}} ≤ 2d − \frac{3d}{n + 2} + \frac{(4c − d^{2})\frac{n−1}{n+2}}{k} = k − \frac{3dk + 3(4c − d^{2})}{k(n + 2)}
= k − \frac{3k^{2} − 3dk}{k(n + 2)} = k − \frac{3(k − d)}{n + 2} < k

and

s_{n} − s_{n−1} = (\frac{d(2n + 1)}{n + 2} + \frac{(4c − d^{2})(n − 1)}{s_{n−1}(n + 2)}) −

(\frac{d(2n − 1)}{n + 1} + \frac{(4c − d^{2})(n − 2)}{s_{n−2}(n + 1)})

= d(2 − \frac{3}{n + 2}) + \frac{(4c − d^{2})}{s_{n−1}}(1 − \frac{3}{n + 2}) −

(d(2 − \frac{3}{n + 1}) + \frac{(4c − d^{2})}{s_{n−2}}(1 − \frac{3}{n + 1}))

≥ −\frac{3d}{n + 2} + \frac{3d}{n + 1} + \frac{(4c − d^{2})}{s_{n−1}}(−\frac{3}{n + 2} + \frac{3}{n + 1})
= \frac{3d}{(n + 2)(n + 1)} + \frac{3(4c − d^{2})}{s_{n−1}(n + 2)(n + 1)}
= \frac{3ds_{n−1} + 3(4c − d^{2})}{s_{n−1}(n + 2)(n + 1)} ≥ \frac{12c}{s_{n−1}(n + 2)(n + 1)} > 0 .

By induction {s_{i}} is a bounded nondecreasing sequence and

lim_{n→∞} \frac{m_{n}}{m_{n−1}} = k .

References

[1] N. Dershowitz and S. Zaks, The cycle lemma and some applications, European J. Combin. 11 (1990), 34–40.

[2] E. Pergola and R. Pinzani, A combinatorial interpretation of the area of Schroeder paths, Electron. J. Combin. 6 (1999), Research paper 40, 13 pp.

[3] R. Sulanke, Moments of generalized Motzkin paths, J. Integer Seq. 3 (2000), Article 00.1.1.

[4] J. Wendel, Left-continuous random walk and the Lagrange expansion, Amer. Math. Monthly 82 (1975), 494–499.

[5] W. Woan, A Combinatorial proof of a recursive relation of the Motzkin sequence by Lattice Paths Fibonacci Quart. 40 (2002), 3–8.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: Motzkin paths, combinatorial identity.

(Concerned with sequences \underline{A000108}, \underline{A001003}, and \underline{A001006}.) Received January 9 2005; revised version received February 24 2005. Published in Journal of Integer Sequences, February 28 2005. Return to Journal of Integer Sequences home page.