A Relation Between Restricted and Unrestricted Weighted Motzkin Paths

Wen-jin Woan Howard University Washington, DC 20059 USA

                     wwoan@fac.howard.edu

Abstract

We consider those lattice paths that use the steps “up”, “level”, and “down” with assigned weights w, b, c. In probability theory, the total weight is 1. In combinatorics, we replace weight by the number of colors. Here we give a combinatorial proof of a relation between restricted and unrestricted weighted Motzkin paths.

1 Introduction

We consider those lattice paths in the Cartesian plane starting from (0, 0) that use the steps {U, L, D}, where U = (1, 1), an up-step, L = (1, 0), a level-step and D = (1, −1), a downstep, with assigned weights w, b, and c. In probability theory, the total weight is 1. In combinatorics, we regard weight as the number of colors and normalize by setting w = 1. Let P be a path. We define the weight w(P) to be the product of the weight of the steps. Let A(n, k) be the set of all weighted lattice 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} be the sum of all w(P) with P in A(n, k) and let m_{n,k} be the sum of all w(P) with P in M(n, k). Note that

a_{n,k} = a_{n−1,k−1} + ba_{n−1,k} + ca_{n−1,k+1},

and the same relationship holds for b_{n,k} and m_{n,k}. In combinatorics, we regard the weights as the number of colors. Then A(n, k) is the set of all colored lattice paths ending at the point (n, k) and M(n, k) is the set of all colored lattice paths in A(n, k) that never go below the x-axis. Then a_{n,k} = |A(n, k)|, m_{n,k} = |M(n, k)|, and m_{n} = |M(n, 0)|. The sequence {m_{n}} is called the bc-Motzkin sequence for the bc-Motzkin lattice path. Let B(n, k) denote the set of lattice paths in A(n, k) that never return to the x-axis after the initial U step and let b_{n,k} = |B(n, k)| . Note that the paths in M(n, k) and B(n, k) are restricted paths. For definitions and results please refer to Stanley [5].

2 Some Examples

Example 1. For b = 2, c = 1, all matrices are infinite by infinite. Partial entries are as follows:

(a_{n,k}) = [ \begin{matrix}n\k & −5 & −4 & −3 & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 1 & 4 & 6 & 4 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 1 & 6 & 15 & 20 & 15 & 6 & 1 & 0 & 0 \\ 4 & 0 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 & 0 \\ 5 & 1 & 10 & 45 & 120 & 210 & 252 & 210 & 120 & 45 & 10 & 1 \end{matrix} ] ,

(m_{n,k}) = [ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 5 & 4 & 1 & 0 & 0 & 0 \\ 3 & 14 & 14 & 6 & 1 & 0 & 0 \\ 4 & 42 & 48 & 27 & 8 & 1 & 0 \\ 5 & 132 & 165 & 110 & 44 & 10 & 1 \end{matrix} ] ,

(b_{n,k}) = [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 5 & 4 & 1 & 0 & 0 & 0 \\ 0 & 14 & 14 & 6 & 1 & 0 & 0 \\ 0 & 42 & 48 & 27 & 8 & 1 & 0 \\ 0 & 132 & 165 & 110 & 44 & 10 & 1 \end{matrix} ] .

The 21-Motzkin sequence 1, 2, 5, 14, 42, 132, ... of the first column of (m_{n,k}) is the Catalan sequence (Sloane’s \underline{A000108}). Please refer to Stanley [5].

Example 2. For b = 3, c = 2, partial entries are as follows:

(a_{n,k}) = [ \begin{matrix}n\k & −5 & −4 & −3 & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 2 & 3 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 4 & 12 & 13 & 6 & 1 & 0 & 0 & 0 \\ 3 & 0 & 0 & 8 & 36 & 66 & 63 & 33 & 9 & 1 & 0 & 0 \\ 4 & 0 & 16 & 96 & 248 & 360 & 321 & 180 & 62 & 12 & 1 & 0 \\ 5 & 32 & 240 & 800 & 1560 & 1970 & 1683 & 985 & 390 & 100 & 15 & 1 \end{matrix} ] ,

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

(b_{n,k}) = [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 1 & 0 & 0 & 0 & 0 \\ 0 & 11 & 6 & 1 & 0 & 0 & 0 \\ 0 & 45 & 31 & 9 & 1 & 0 & 0 \\ 0 & 197 & 156 & 60 & 12 & 1 & 0 \\ 0 & 903 & 785 & 360 & 98 & 15 & 1 \end{matrix} ] .

The 32-Motzkin sequence 1, 3, 11, 45, 197, ...of the first column of (m_{n,k}) is the little Schroeder sequence (Sloane’s \underline{A001003}).

Example 3. Let b = 4, c = 3. Partial entries 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 & 3 & 4 & 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 9 & 24 & 22 & 8 & 1 & 0 & 0 \\ 3 & 0 & 27 & 108 & 171 & 136 & 57 & 12 & 1 & 0 \\ 4 & 81 & 432 & 972 & 1200 & 886 & 400 & 108 & 16 & 1 \end{matrix} ] ,

(m_{n,k}) = [ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 4 & 1 & 0 & 0 & 0 \\ 2 & 19 & 8 & 1 & 0 & 0 \\ 3 & 100 & 54 & 12 & 1 & 0 \\ 4 & 562 & 352 & 105 & 16 & 1 \end{matrix} ] ,

(b_{n,k}) = [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 4 & 1 & 0 & 0 & 0 \\ 0 & 19 & 8 & 1 & 0 & 0 \\ 0 & 100 & 54 & 9 & 1 & 0 \\ 0 & 562 & 356 & 105 & 16 & 1 \end{matrix} ] .

3 Main results

We now give a bijective proof for Theorem 4. a_{n,k} = ∑_{i=0} c^{i}m_{n},_{2i+k} for n, k ≥ 0.

Proof. Let P be a lattice path in A(n, k). Find the leftmost lowest point of the path, and let this point be p = (m, −i). Now we obtain path P′ in M(n, 2i + k) from P as follows: first, replace U with D, and D with U for the section of P before the point p. Next, reverse the order of those steps and attach those steps to the end of the rest of the path. This gives us a path P′ with i fewer down steps and w(P) = c^{i}w(P′). Note that the attached point is the rightmost point of height i + k; this identification suggests the inverse mapping.

Example 5. Let P = (UDDD)LUDUUUDU ∈ A(15, 1), P′ = LUDUUUDU (UUUD) ∈ M(15, 5).

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

P′ == \begin{aligned}& & & & & & & & & & & ∘ \\ & & & & & & & & & & ∘ & & ∘ \\ & & & & & & & & & ∘ \\ & & & & & & ∘ & & • \\ & & & & & ∘ & & ∘ \\ & & ∘ & & ∘ \\ × & ∘ & & ∘ \end{aligned} ∈ M(12, 2 ∗ 2 + 1)

Remark 6. Theorem 4 shows us the relationship between (m_{n,k}) and (a_{n,k}).

For Example 1

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 5 & 4 & 1 & 0 & 0 & 0 \\ 14 & 14 & 6 & 1 & 0 & 0 \\ 42 & 48 & 27 & 8 & 1 & 0 \\ 132 & 165 & 110 & 44 & 10 & 1 \end{matrix} ] [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ]

= [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 6 & 4 & 1 & 0 & 0 & 0 \\ 20 & 15 & 6 & 1 & 0 & 0 \\ 70 & 56 & 28 & 8 & 1 & 0 \\ 252 & 210 & 120 & 45 & 10 & 1 \end{matrix} ] .

For Example 2

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 11 & 6 & 1 & 0 & 0 & 0 \\ 45 & 31 & 9 & 1 & 0 & 0 \\ 197 & 156 & 60 & 12 & 1 & 0 \\ 903 & 785 & 360 & 98 & 15 & 1 \end{matrix} ] [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 1 & 0 & 0 \\ 4 & 0 & 2 & 0 & 1 & 0 \\ 0 & 4 & 0 & 2 & 0 & 1 \end{matrix} ]

= [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 13 & 6 & 1 & 0 & 0 & 0 \\ 63 & 33 & 9 & 1 & 0 & 0 \\ 321 & 180 & 62 & 12 & 1 & 0 \\ 1683 & 985 & 390 & 100 & 15 & 1 \end{matrix} ] .

For Example 3

[ \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 19 & 8 & 1 & 0 & 0 \\ 100 & 54 & 12 & 1 & 0 \\ 562 & 352 & 105 & 16 & 1 \end{matrix} ] [ \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 3 & 0 & 1 & 0 & 0 \\ 0 & 3 & 0 & 1 & 0 \\ 9 & 0 & 3 & 0 & 1 \end{matrix} ]

= [ \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 22 & 8 & 1 & 0 & 0 \\ 136 & 57 & 12 & 1 & 0 \\ 886 & 400 & 108 & 16 & 1 \end{matrix} ] .

We now give a bijective proof for Theorem 7. a_{n,−k} = c^{k}a_{n,k}. Proof. Let P be in A(n, −k). Then P has k more D steps than U steps. We obtain P′ ∈ A(n, k) from P by interchanging D steps and U steps. Then P has k more D steps than P′. Hence a_{n,−k} = c^{k}a_{n,k}.

For examples, see Examples 1, 2 and 3.

We now give a bijective proof for Theorem 8. (1 + b + c)^{n} = ∑_{k=−n}^{n} a_{n,k} = a_{n,0} + ∑_{k=1}^{n}(c^{k} + 1)a_{n,k}. Proof. For each step we have (1 + b + c) choices. Let us index the columns of (a_{n,k}) by the power k of y. The generating function going from one row to next is multiplied by w(y) = y + b + cy^{−1}. Hence the generating function of the n^{th} row of (a_{n,k}) is w(y)^{n}. By setting y = 1 we have

(1 + b + c)^{n} = ∑_{k=−n}^{n} a_{n,k}

= ∑_{k=−n}^{−1} a_{n,k} + a_{n,0} + ∑_{k=1}^{n} a_{n,k}

= ∑_{k=1}^{n} c^{k}a_{n,k} + a_{n,0} + ∑_{k=1}^{n} a_{n,k}

= a_{n,0} + ∑_{k=1}^{n}(c^{k} + 1)a_{n,k}.

Remark 9. Apply Theorem 8 to

Example 1:

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 6 & 4 & 1 & 0 & 0 & 0 \\ 20 & 15 & 6 & 1 & 0 & 0 \\ 70 & 56 & 28 & 8 & 1 & 0 \\ 252 & 210 & 120 & 45 & 10 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 2 \\ 2 \\ 2 \\ 2 \\ 2 \end{matrix} ] = [ \begin{matrix}1 \\ 4 \\ 16 \\ 64 \\ 256 \\ 1024 \end{matrix} ] .

.

Example 2

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 13 & 6 & 1 & 0 & 0 & 0 \\ 63 & 33 & 9 & 1 & 0 & 0 \\ 321 & 180 & 62 & 12 & 1 & 0 \\ 1683 & 985 & 390 & 100 & 15 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 3 \\ 5 \\ 9 \\ 17 \\ 33 \end{matrix} ] = [ \begin{matrix}1 \\ 6 \\ 36 \\ 216 \\ 1296 \\ 7776 \end{matrix} ] .

Example 3

[ \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 22 & 8 & 1 & 0 & 0 \\ 136 & 57 & 12 & 1 & 0 \\ 886 & 400 & 108 & 16 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 4 \\ 10 \\ 28 \\ 82 \end{matrix} ] = [ \begin{matrix}1 \\ 8 \\ 64 \\ 512 \\ 4096 \end{matrix} ] .

Please refer to Getu [2] for Riordan matrices.

Definition 10. A lower triangular matrix A = (g, f) is said to be a Riordan matrix if the generating function A_{k} of the k^{th} column is gf^{k}, where g = g(x) = 1 + g_{1}x + g_{2}x^{2} + ⋯ and f = f(x) = x + f_{2}x^{2} + f_{3}x^{3} + · · ·. Let R be the set of all Riordan matrices.

Lemma 11. Let D = (d_{n,k}) = (g, f) ∈ R and A = [a_{i}] a column vector with generating function A(x) = ∑ a_{i}x^{i}. Then the generating function for B = DA is gA(f).

Proof. b_{n} = ∑ a_{i}([x^{n}]gf^{i}) = [x^{n}] ∑ a_{i}gf^{i} = [x^{n}]gA(f).

Remark 12. Let M = (g, f) and N = (h, l) be in R. Then MN = (g, f)(k, l) = (gk(f), l(f)) and R is a group with (g, f)^{−1} = (\frac{1}{g(f^{−1})}, f^{−1}).

Definition 13. For each A ∈ R, we define the Stieltjes Matrix. S_{A} = A^{−1}\overline{A} or AS_{A} = \overline{A}, where \overline{A} is the matrix obtaining from A by removing the first row. The entries of the Stieltjes matrix are of the following form:

S_{A} = [ \begin{matrix}× & 1 & 0 & 0 & 0 & 0 \\ × & × & 1 & 0 & 0 & 0 \\ × & × & × & 1 & 0 & 0 \\ × & × & × & × & 1 & 0 \\ × & × & × & × & × & 1 \\ × & × & × & × & × & × \end{matrix} ] .

For the following Remark please refer to Peart [3] and Spitzer [4].

Remark 14. Let A = (g, f) ∈ R be a matrix with tridiagonal Stieltjes matrix of the form

[ \begin{matrix}a & 1 & 0 & 0 & 0 & 0 \\ d & b & 1 & 0 & 0 & 0 \\ 0 & c & b & 1 & 0 & 0 \\ 0 & 0 & c & b & 1 & 0 \\ 0 & 0 & 0 & c & b & 1 \\ 0 & 0 & 0 & 0 & c & b \end{matrix} ] .

Then f = f(x) = x(1 + bf + cf^{2}), g = \frac{1}{1−ax−dxf}.

For Example 1, f = x(1 + 2f + f^{2}) = \frac{1−2x−\sqrt{1−4x}}{2x} ,

(a_{n,k}) = (g, f) with g = \frac{1}{1−2x−2xf} ,

(m_{n,k}) = (\frac{f}{x}, f),

S_{(a_{n,k})} = [ \begin{matrix}2 & 1 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 2 \end{matrix} ] , S_{(m_{n,k})} = [ \begin{matrix}2 & 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 2 \end{matrix} ]

.

For Example 2, f = x(1 + 3f + 2f^{2}) = \frac{1−3x−\sqrt{1−6x+x^{2}}}{4x} , (a_{n,k}) = (g, f) with g = \frac{1}{1−3x−4xf} , (m_{n,k}) = (\frac{f}{x}, f),

S_{(a_{n,k})} = [ \begin{matrix}3 & 1 & 0 & 0 & 0 & 0 \\ 4 & 3 & 1 & 0 & 0 & 0 \\ 0 & 2 & 3 & 1 & 0 & 0 \\ 0 & 0 & 2 & 3 & 1 & 0 \\ 0 & 0 & 0 & 2 & 3 & 1 \\ 0 & 0 & 0 & 0 & 2 & 3 \end{matrix} ] , S_{(m_{n,k})} = [ \begin{matrix}3 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 0 & 2 & 3 & 1 & 0 & 0 \\ 0 & 0 & 2 & 3 & 1 & 0 \\ 0 & 0 & 0 & 2 & 3 & 1 \\ 0 & 0 & 0 & 0 & 2 & 3 \end{matrix} ] .

Theorem 15. For bc-Motzkin sequences we have (m_{n,k})(\frac{1}{1−cx^{2}} , x) = (a_{n,k}). Proof. It follows by Theorem 4. Theorem 16. For bc-Motzkin sequences we have (a_{n,k})(\frac{1}{1−cx} + \frac{x}{1−x}) = \frac{1}{1−kx}, k = 1 + b + c. Proof. By Theorem 8. Theorem 17. For bc-Motzkin sequences we have (m_{n,k})(\frac{1}{(1−cx)(1−x)} ) = \frac{1}{1−kx}. Proof. By Theorems 15, 16. Remark 18. Apply Theorem 17 to

Example 1.

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 5 & 4 & 1 & 0 & 0 & 0 \\ 14 & 14 & 6 & 1 & 0 & 0 \\ 42 & 48 & 27 & 8 & 1 & 0 \\ 132 & 165 & 110 & 44 & 10 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \end{matrix} ] = [ \begin{matrix}1 \\ 4 \\ 16 \\ 64 \\ 256 \\ 1024 \end{matrix} ] .

.

Example 2. Please refer to Cameron [1] for this example.

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 \\ 11 & 6 & 1 & 0 & 0 & 0 \\ 45 & 31 & 9 & 1 & 0 & 0 \\ 197 & 156 & 60 & 12 & 1 & 0 \\ 903 & 785 & 360 & 98 & 15 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 3 \\ 7 \\ 15 \\ 31 \\ 63 \end{matrix} ] = [ \begin{matrix}1 \\ 6 \\ 36 \\ 216 \\ 1296 \\ 7776 \end{matrix} ] .

Example 3.

[ \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 19 & 8 & 1 & 0 & 0 \\ 100 & 54 & 12 & 1 & 0 \\ 562 & 352 & 105 & 16 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 4 \\ 13 \\ 40 \\ 121 \end{matrix} ] = [ \begin{matrix}1 \\ 8 \\ 64 \\ 512 \\ 4096 \end{matrix} ]

.

Remark 19. Theorem 17 applies only to Stieltjes matrices of the form

[ \begin{matrix}b & 1 & 0 & 0 & 0 & 0 \\ c & b & 1 & 0 & 0 & 0 \\ 0 & c & b & 1 & 0 & 0 \\ 0 & 0 & c & b & 1 & 0 \\ 0 & 0 & 0 & c & b & 1 \\ 0 & 0 & 0 & 0 & c & b \end{matrix} ]

.

The following is a generalization.

Theorem 20. Let A = (g, f) ∈ R be a Riordan matrix with tridiagonal Stieltjes matrix of the form

[ \begin{matrix}a & 1 & 0 & 0 & 0 & 0 \\ d & b & 1 & 0 & 0 & 0 \\ 0 & c & b & 1 & 0 & 0 \\ 0 & 0 & c & b & 1 & 0 \\ 0 & 0 & 0 & c & b & 1 \\ 0 & 0 & 0 & 0 & c & b \end{matrix} ]

and A(x) = \frac{(1−cx)+(k−a−1)x+(c−d)x^{2}}{(1−x)(1−cx)} , then (g, f)A(x) = \frac{1}{1−kx}, where k = 1 + b + c.

Proof. Let A(x) = 1 + (k − a)x + [(k − a − 1)c + (c − d) + (k − a)]x^{2} + [((k − a − 1)c + c − d)c + (k − a − 1)c + (c − d) + (k − a)]x^{3} + · · · .

Then A(x) − xA(x) = \frac{(1−cx)+(k−a−1)x+(c−d)x^{2}}{1−cx} .

Now

(g, f)A(x) = \frac{1}{1 − ax − dxf} \frac{1 + (k − a − c − 1)f + (c − d)f^{2}}{(1 − f)(1 − cf)}
= \frac{1}{1 − ax − dxf} \frac{1 + (b − a)f + (c − d)f^{2}}{(1 − f)(1 − cf)} = \frac{1}{1 − ax − dxf} \frac{1 + bf + cf^{2} − af − df^{2}}{(1 − f)(1 − cf)}
= \frac{1}{1 − ax − dxf} \frac{\frac{f}{x} − af − df^{2}}{(1 − f)(1 − cf)}
= \frac{f}{x(1 − f)(1 − cf)}
= \frac{f}{x(1 − f − cf + cf^{2})}
= \frac{f}{x − xf − cxf + cxf^{2}}
= \frac{f}{f − xbf − xf − cxf}
= \frac{f}{f − xf(b + c + 1)}
= \frac{1}{1 − kx}.

Remark 21. Apply Theorem 20 and Peart [3]. Example 1.

S_{A} = [ \begin{matrix}1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 2 \end{matrix} ] , A = [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 5 & 9 & 5 & 1 & 0 & 0 \\ 14 & 28 & 20 & 7 & 1 & 0 \\ 42 & 90 & 75 & 35 & 9 & 1 \end{matrix} ] = (g, f),

where f = x(1 + 2f + f^{2}) = \frac{1−2x−\sqrt{1−4x}}{2x} , g = \frac{1}{1−x−xf} = \frac{1−\sqrt{1−4x}}{2} , A(x) = \frac{1+x}{(1−x)(1−x)} = 1 + 3x + 5x^{2} + 7x^{3} + 9x^{4} + 11x^{5} + 13x^{6} + O (x^{7}) ,

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 \\ 5 & 9 & 5 & 1 & 0 & 0 \\ 14 & 28 & 20 & 7 & 1 & 0 \\ 42 & 90 & 75 & 35 & 9 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 3 \\ 5 \\ 7 \\ 9 \\ 11 \end{matrix} ] = [ \begin{matrix}1 \\ 4 \\ 16 \\ 64 \\ 256 \\ 1024 \end{matrix} ] .

Example 2.

S_{A} = [ \begin{matrix}2 & 1 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 \\ 0 & 2 & 3 & 1 & 0 \\ 0 & 0 & 2 & 3 & 1 \\ 0 & 0 & 0 & 2 & 3 \end{matrix} ] , A = [ \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 6 & 5 & 1 & 0 & 0 \\ 22 & 23 & 8 & 1 & 0 \\ 90 & 107 & 49 & 11 & 1 \end{matrix} ] = (g, f),

where f = x(1 + 3f + 2f^{2}) = \frac{1−3x−\sqrt{1−6x+x^{2}}}{4x} , g = \frac{1}{1−2x−2xf} ,

A(x) = \frac{1+x}{(1−x)(1−2x)} = 1 + 4x + 10x^{2} + 22x^{3} + 46x^{4} + 94x^{5} + 190x^{6} + 382x^{7} + O (x^{8}) ,

[ \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 6 & 5 & 1 & 0 & 0 \\ 22 & 23 & 8 & 1 & 0 \\ 90 & 107 & 49 & 11 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 4 \\ 10 \\ 22 \\ 46 \end{matrix} ] = [ \begin{matrix}1 \\ 6 \\ 36 \\ 216 \\ 1296 \end{matrix} ] .

.

4 Acknowledgments

The author wishes to thank the referee for the valuable comments that improved the presentation of the paper.

References

[1] N. Cameron and A. Nkwanta, On some (Pseudo) involutions in the Riordan group, J. Integer Seq., 8 (2005), article 05.3.7.

[2] S. Getu, L. Shapiro, W. J. Woan and L. Woodson, The Riordan groups, Discrete Appl. Math., 34 (1991), 229–239.

[3] P. Peart and W. J. Woan, Generating functions via Hankel and Stieltjes matrices, J. Integer Seq., 3 (2000), article 00.2.1.

[4] F. Spitzer, Principles of Random Walk, Van Nostrand, Princeton, 1964.

[5] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

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

(Concerned with sequences \underline{A000108} and \underline{A001003}.)

Received October 4 2005; revised version received January 28 2006. Published in Journal of Integer Sequences, January 29 2006.

Return to Journal of Integer Sequences home page.