The Lagrange Inversion Formula and Divisibility Properties

Wen-jin Woan^{1} Howard University Washington, DC 20059 USA

                     wjwoan@sbcglobal.net

Abstract

Wilf stated that the Lagrange inversion formula (LIF) is a remarkable tool for solving certain kinds of functional equations, and at its best it can give explicit formulas where other approaches run into stone walls. Here we present the LIF combinatorially in the form of lattice paths, and apply it to the divisibility property of the coefficients of a formal power series expansion. For the LIF, the coefficients are in a commutative ring with identity. As for divisibility, we require the coefficients to be in a principal ideal domain.

1 Introduction

Wilf [10] stated that the Lagrange inversion formula (LIF) is a remarkable tool for solving certain kinds of functional equations, and at its best it can give explicit formulas where other approaches run into stone walls. Here we present the LIF combinatorially in the form of lattice paths and apply it to the divisibility property of the coefficients of formal power series expansion. For the LIF the coefficients are in a commutative ring with identity. As for divisibility, we require the coefficients to be in a principal ideal domain (PID).

We consider those weighted lattice paths in the Cartesian plane beginning at (0, 0) and proceeding with weighted steps from S = {w_{−m} = (1, −m), m = −1, 0, 1, 2, ...}, where w_{i} represents the step and also the weight. We normalize the weight by setting w_{1} = 1 and let w(y) = ∑_{i≤1} w_{i}y^{i} be the weight generating function. Let p(x) = x(w(x^{−1})) = ∑ w_{i}x^{1−i} = 1+w_{0}x+w_{−1}x^{2}+w_{−2}x^{3}+... be the weight formal power series. The weight of a lattice path is the product of the weights of the steps. Let A(n, k) be the set of all weighted lattice paths ending at the point (n, k) (the terminal point) and for k > 0, let B(n, k) ⊂ A(n, k) denote the set of paths that stay above the x-axis except the initial point. Let a_{n,k} = w(A(n, k)) be the sum of the weights of all paths in A(n, k) and b_{n,k} = w(B(n, k)) be the sum of the weights of all paths in B(n, k). Note that the generating function of the n^{th} row of (a_{n,k}) is w(y)^{n}, i.e., a_{n,k} = [y^{k}](w(y))^{n} = ∑_{i≤1} w_{i}a_{n−1,(k−1)+1−i}, where the summation represents the partition of the paths in A(n, k) by the positions preceding to the last step. Similarly we can write b_{n,k} = ∑_{i≤1} w_{i}b_{n−1,(k−1)+1−i}, for k > 0.

1Author’s current address: 2103 Opal Ridge, Vista, CA 92081, USA.

In combinatorics the weights are non-negative integers, and a_{n,k} count the number of colored paths.

2 Some Examples

Example 1. w_{1} = w_{−1} = 1 and w_{i} = 0, otherwise. Then w(y) = y + y^{−1} = y(1 + y^{−2}), p(x) = 1 + x^{2} and a_{n,k} = \binom{2m+k}{m} is the binomial coefficient, where n = 2m + k. Some entries of (a_{n,k}) and (b_{n,k}) are as follows:

(a_{n,k}) → [ \begin{matrix}n\k & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 3 & 0 & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 4 & 0 & 6 & 0 & 4 & 0 & 1 & 0 & 0 & 0 & 0 \\ 5 & 0 & 10 & 0 & 10 & 0 & 5 & 0 & 1 & 0 & 0 & 0 \\ 6 & 15 & 0 & 20 & 0 & 15 & 0 & 6 & 0 & 1 & 0 & 0 \\ 7 & 0 & 35 & 0 & 35 & 0 & 21 & 0 & 7 & 0 & 1 & 0 \\ 8 & 56 & 0 & 70 & 0 & 56 & 0 & 28 & 0 & 8 & 0 & 1 \end{matrix} ] ,

(b_{n,k}) → [ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 \\ 5 & 0 & 2 & 0 & 3 & 0 & 1 & 0 & 0 & 0 \\ 6 & 0 & 0 & 5 & 0 & 4 & 0 & 1 & 0 & 0 \\ 7 & 0 & 5 & 0 & 9 & 0 & 5 & 0 & 1 & 0 \\ 8 & 0 & 0 & 14 & 0 & 14 & 0 & 6 & 0 & 1 \end{matrix} ] .

Example 2. w_{i} = 1 for i = 1, 0, −1 and 0, otherwise. In this example w(y) = y+1+y^{−1} = y(1 + y^{−1} + y^{−2}), p(x) = 1 + x + x^{2} and (a_{n,k}) are the trinomial coefficients. Some entries of (a_{n,k}) and (b_{n,k}) are as follows:

(a_{n,k}) → [ \begin{matrix}n\k & −2 & −1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 2 & 3 & 2 & 1 & 0 & 0 & 0 & 0 \\ 3 & 3 & 6 & 7 & 6 & 3 & 1 & 0 & 0 & 0 \\ 4 & 10 & 16 & 19 & 16 & 10 & 4 & 1 & 0 & 0 \\ 5 & 30 & 45 & 51 & 45 & 30 & 15 & 5 & 1 & 0 \\ 6 & 90 & 126 & 141 & 126 & 90 & 50 & 21 & 6 & 1 \end{matrix} ] .

The generating function of row 5 is w(y)^{5} = (y(1 + y^{−1} + y^{−2}) )^{5} = y^{−5} + 5y^{−4} + 15y^{−3} + 30y^{−2} + 45y^{−1} + 51 + 45y + 30y^{2} + 15y^{3} + 5y^{4} + y^{5},

(b_{n,k}) → [ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 2 & 2 & 1 & 0 & 0 & 0 & 0 \\ 4 & 0 & 4 & 5 & 3 & 1 & 0 & 0 & 0 \\ 5 & 0 & 9 & 12 & 9 & 4 & 1 & 0 & 0 \\ 6 & 0 & 21 & 30 & 25 & 14 & 5 & 1 & 0 \\ 7 & 0 & 51 & 76 & 69 & 44 & 20 & 6 & 1 \end{matrix} ] .

Example 3. w_{1} = 1, w_{0} = 3, w_{−1} = 2 and 0 otherwise. In this example w(y) = y + 3 + 2y^{−1} = y( 1 + 3y^{−1} + 2y^{−2}) and p(x) = 1 + 3x + 2x^{2}. Some entries of (a_{n,k}) and (b_{n,k}) are as follows:

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

The generating function of row 4 is w(y)^{4} = (y + 3 + 2y^{−1})^{4} = 16y^{−4} + 96y^{−3} + 248y^{−2} + 360y^{−1} + 321 + 180y + 62y^{2} + 12y^{3} + y^{4},

(b_{n,k}) → [ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 11 & 6 & 1 & 0 & 0 & 0 & 0 \\ 4 & 0 & 45 & 31 & 9 & 1 & 0 & 0 & 0 \\ 5 & 0 & 197 & 156 & 60 & 12 & 1 & 0 & 0 \\ 6 & 0 & 903 & 785 & 360 & 98 & 15 & 1 & 0 \\ 7 & 0 & 4279 & 3978 & 2061 & 684 & 145 & 18 & 1 \end{matrix} ] .

Note that (b_{n,1}) is the Schröder sequence of the first kind.

Example 4. Let w_{i} = 2 − i for i ≤ 1. Then w(y) = y(1 + 2y^{−1} + 3y^{−2} + 4y^{−3} + ...) and some entries of (a_{n,k}) and (b_{n,k}) are as follows:

(a_{n,k}) → [ \begin{matrix}n\k & −2 & −1 & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 4 & 3 & 2 & 1 & 0 & 0 \\ 2 & 35 & 20 & 10 & 4 & 1 & 0 \\ 3 & 252 & 126 & 56 & 21 & 6 & 1 \\ 4 & 1716 & 792 & 330 & 120 & 36 & 8 \\ 5 & 11440 & 5005 & 2002 & 715 & 220 & 55 \\ 6 & 75582 & 31824 & 12376 & 4368 & 1365 & 364 \\ 7 & 497420 & 203490 & 77520 & 27132 & 8568 & 2380 \end{matrix} ] .

The generating function of row 4 is w(y)^{4} with coefficients the same as p(x)^{4} = (\frac{1}{(1−x)^{2}} )^{4} = 1 + 8x + 36x^{2} + 120x^{3} + 330x^{4} + 792x^{5} + 1716x^{6} + 3432x^{7} + 6435x^{8} + O (x^{9}) ,

(b_{n,k}) → [ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 7 & 4 & 1 & 0 & 0 & 0 & 0 \\ 4 & 0 & 30 & 18 & 6 & 1 & 0 & 0 & 0 \\ 5 & 0 & 143 & 88 & 33 & 8 & 1 & 0 & 0 \\ 6 & 0 & 838 & 455 & 182 & 52 & 10 & 1 & 0 \\ 7 & 0 & 4096 & 2558 & 1020 & 320 & 75 & 12 & 1 \end{matrix} ] .

Example 5. Let w_{1} = 1 and w_{i} = 2 for i ≤ 0. Then w(y) = y(1 + 2y^{0} + 2y^{−1} + 2y^{−2} + ... + 2y^{−n} + ...) and p(x) = \frac{1+x}{1−x}. Some entries of (a_{n,k}) and (b_{n,k}) are as follows:

(a_{n,k} ) → [ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 8 & 4 & 1 & 0 & 0 & 0 & 0 \\ 3 & 38 & 18 & 6 & 1 & 0 & 0 & 0 \\ 4 & 192 & 88 & 32 & 8 & 1 & 0 & 0 \\ 5 & 1002 & 450 & 170 & 50 & 10 & 1 & 0 \end{matrix} ] ,

(b_{n,k}) → [ \begin{matrix}n\k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 2 & 1 & 0 & 0 & 0 & 0 \\ 3 & 0 & 6 & 4 & 1 & 0 & 0 & 0 \\ 4 & 0 & 22 & 16 & 6 & 1 & 0 & 0 \\ 5 & 0 & 90 & 68 & 30 & 8 & 1 & 0 \\ 6 & 0 & 394 & 304 & 146 & 48 & 10 & 1 \end{matrix} ] .

Note that (b_{n,1}) is the large Schröder sequence. For some of the above examples please refer to [7].

3 Main Theorems

Please refer to [6, 4] for the following remark.

Remark 6. Let A_{k}(x) = ∑ a_{n,k}x^{n} be the generating function of the k^{th} column of (a_{n,k})_{n≥k≥0} and B_{k}(x) = ∑ b_{n,k}x^{n} be the generating function of the k^{th} column of (b_{n,k})_{n≥k}. Let g = g(x) = A_{0}(x) and f = f(x) = B_{1}(x). The following generating functions correspond to Examples 1, 2, 3.

1 + 3x + 2x^{2} p(x)  f(x)  g(x)  Sloane A  Name 1 + x^{2}  ^{\frac{1−\sqrt{1−4x^{2}}}{2x}}  ^{\frac{1}{\sqrt{1−4x^{2}}}}  000108,000984 Catalan, Central binomial 1 + x + x^{2} ^{\frac{1−x−\sqrt{1−2x−3x^{2}}}{2x}} ^{\frac{1}{\sqrt{1−2x−3x^{2}}}} 001006,002426 Motzkin, Central trinomial^{\frac{1−3x−\sqrt{1−6x+x^{2}}}{4x}} ^{\frac{1}{\sqrt{1−6x+x^{2}}}} 001003,001850 Schröder, Central Delannoy .

Let P ∈ A(n, k), find the last point on P where the second coordinate is of height k − 1. This point splits P into subpaths F, B with P = F B, and F ∈ A(j, k − 1), B ∈ B(n − j, 1). Then by induction and by the convolution property,

A_{k}(x) = (gf^{k−1})f = gf^{k} , B_{k}(x) = (f^{k−1})f = f^{k}.

From Introduction we have the recurrence relation

b_{n,k} = ∑_{i≤1} w_{i}b_{n−1,(k−1)+1−i}, for k > 0. Hence

f(x) = ∑ b_{n,1}x^{n} = ∑(∑_{i≤1} w_{i}b_{n−1, 1−i})x^{n} = x(∑_{i≤1} w_{i}(∑ b_{n−1,1−i}x^{n−1}))

= x(∑_{i≤1} w_{i} f^{1−i})) = xp(f) and p(x) = \frac{x}{\overline{f}}, where \overline{f} is the inverse function of f.

The following theorem is the LIF (Wilf [10]).

Theorem 7. (LIF) Let f(x) = x + ∑_{i=2} b_{i}x^{i}. Then [x^{n}](\overline{f}(x))^{k} = \frac{k}{n}[x^{n−k}](\frac{x}{f(x)})^{n}, where \overline{f} is the inverse function of f.

The following theorem (The hitting time theorem in probability theory) is the LIF in the form of lattice paths. A vast literature exists on this subject, see, e.g., [3, 6, 9]. This result is well-known for k = 1 in some special cases [11, 12].

Theorem 8. For 0 < k < n, nb_{n,k} = ka_{n,k}.

We shall provide two proofs of Theorem 8. In the first proof we use LIF to prove Theorem 8 algebraically whereas in the second proof we use lattice paths bijection to prove it combinatorially. First proof. By Remark 6 and Theorem 7 we obtain that b_{n,k} = [x^{n}]f^{k} = \frac{k}{n}[x^{n−k}]( \frac{x}{\overline{f}(x)})^{n} = \frac{k}{n}[x^{n−k}](p(x))^{n} = \frac{k}{n}[x^{−k}](w(\frac{1}{x}))^{n} = \frac{k}{n}[y^{k}](w(y))^{n} = \frac{k}{n}a_{n,k}. Second proof. We construct a bijection between the set of all pairs (P, i) with P ∈ A(n, k) and i ∈ {0, 1, 2, 3, ..., k − 1} and the set of all pairs (Q, j) with Q ∈ B(n, k) and j ∈ [n], as follows: For P ∈ A(n, k) and i ∈ {0, 1, 2, 3, ..., k − 1}, let l(P) be the second coordinate of the lowest point of P and let j be the maximum element of [n] such that the point (j, i + l(P)) ∈ P. This point splits the path P into two subpaths F, B with P = F B.

We define Q = BF. Every point of B in Q (apart from the initial point) lies above the x-axis, because of the maximality of j.

Moreover, every point of F in Q is elevated by k − (l(P) + i) units, so that the lowest point of F in Q has second coordinate equal to l(P) + k − (l(P) + i) = k − i > 0 and hence F lies above the x-axis. This shows that Q ∈ B(n, k).

Conversely, for Q ∈ B(n, k) and j ∈ [n], the j^{th} point (apart from the initial point) of Q splits Q into two subpaths F, B with Q = F B. Note that in Q , 0 < l(B) ≤ k, thus k = l(B) + i with 0 ≤ i < k. We define P = BF ∈ A(n, k); the (n − j)^{th} point of P splits P into two subpaths B, F. Since the second coordinates of the points of F are larger than the second coordinate of the initial point of F, n − j is the maximum element in [n] such that (n − j, l(P) + i) ∈ P. Hence the mapping (Q, j) → (P, i) is the inverse of the above mapping.

Note that the mappings involve only switching the steps, and hence they preserve the weights.□

Let us use an example to illustrate the mapping in the above theorem.

For P = w_{−3}w_{0}w_{1}w_{1}w_{0}w_{−1}w_{1}w_{0}w_{1}w_{1}w_{1}w_{0}w_{1} ∈ A(13, 3), k = 3, i = 0, 1, 2 we have respectively

(P, 0) = w_{−3}w_{0} ∗ w_{1}w_{1}w_{0}w_{−1}w_{1}w_{0}w_{1}w_{1}w_{1}w_{0}w_{1} →
(Q, 11) = w_{1}w_{1}w_{0}w_{−1}w_{1}w_{0}w_{1}w_{1}w_{1}w_{0}w_{1} ∗ w_{−3}w_{0}.
(P, 1) = w_{−3}w_{0} w_{1}w_{1}w_{0}w_{−1} ∗ w_{1}w_{0}w_{1}w_{1}w_{1}w_{0}w_{1} →
(Q, 7) = w_{1}w_{0}w_{1}w_{1}w_{1}w_{0}w_{1} ∗ w_{−3}w_{0} w_{1}w_{1}w_{0}w_{−1}.
(P, 2) = w_{−3}w_{0}w_{1}w_{1}w_{0}w_{−1}w_{1}w_{0} ∗ w_{1}w_{1}w_{1}w_{0}w_{1} →
(Q, 5) = w_{1}w_{1}w_{1}w_{0}w_{1} ∗ w_{−3}w_{0}w_{1}w_{1}w_{0}w_{−1}w_{1}w_{0}

where the symbol * marks the splitting point of each path.

Graphically, for the second pair of paths (i.e., for i = 1) we have

(P, 1) = [ \begin{matrix}& & & & & & & & & & & & & ∘ \\ & & & & & & & & & & & ∘ & ∘ \\ & & & & & & & & & & ∘ \\ × & & & & & & & & & ∘ \\ & & & & ∘ & ∘ & & ∘ & ∘ \\ & & & ∘ & & & • \\ & ∘ & ∘ \end{matrix} ] →

(Q, 7) = [ \begin{matrix}& & & & & & & • \\ & & & & & ∘ & ∘ & & & & & ∘ & ∘ \\ & & & & ∘ & & & & & & ∘ & & & ∘ \\ & & & ∘ & & & & & ∘ & ∘ \\ & ∘ & ∘ \\ × \end{matrix} ]

where × marks the origin (0, 0).

For the following divisibility properties please refer to [1, 2].

Corollary 9. Let d = g.c.d.(n, k). Then for 0 < k < n (1) \frac{n}{d} divides a_{n,k},

(2) \frac{k}{d} divides b_{n,k},

(3) g.c.d.(n, a_{n,k}) > 1.

Corollary 10. a_{2n+1,1} = \binom{2n+1}{n} = (2n + 1)b_{2n+1,1} is odd if and only if n = 2^{m} − 1 for some m.

Proof. b_{2n+1,1} = c_{n} is the Catalan number. It is well known that the Catalan number c_{n} is odd if and only if n = 2^{m} − 1.

Corollary 11. If n = p^{m} for some m and prime p, then p divides a_{n,k} for 0 < k < n.

For the proof of the next result, it is enough to apply Corollary 11 and use the fact that a_{n,k} = a_{n−1,k−1} + w_{0}a_{n−1,k} + w_{−1}a_{n−1,k+1}.

Corollary 12. If n = p^{m} + 1 for some prime p and w_{i} = 0 for i < −1, then p divides a_{n,k} for 1 < k < n − 2.

Corollary 13. If p^{m} divides n for some m and prime p, then p divides b_{n,k} for n ≠ 0(mod(p^{m})).

The following generalization of Corollary 11 can be proved by applying Corollary 9.

Corollary 14. If p^{m} divides n for some m and prime p, then p divides a_{n,k} for k ≠ 0(mod(p^{m})).

Remark 15. Let A(x) = 1 + 2x^{1} + 3x^{2} + ... = (\frac{1}{1−x})^{2} and B(x) = xA(x) = x (\frac{1}{1−x})^{2}. Then \overline{B}(x) = \frac{1+2x−\sqrt{1+4x}}{2x}, by Remark 6, let p(x) = \frac{x}{\overline{B}(x)} and f = f(x) = xp(f) = B(x). By Corollary 13, if p^{m} divides n for some m and prime p, and A(x)^{n} = ∑ a_{n,k}x^{k}, then p divides a_{n,k} for k ≠ 0(mod(p^{m})).

Remark 16. Theorem 8 may be used for a combinatorial proof of [1, Corollary 2.2].

Remark 17. In the course of the work we never use the weights of lattice path, so one may be able to prove the divisibility by using only factorials and combinations.

4 Acknowledgments

The author wishes to express his gratitude to the referee for several comments and suggestions, especially for the substantial improvement of the main result.

References

[1] M. Bóna and B. Sagan, On divisibility of Narayana numbers by primes, J. Integer Seq. 8 (2005), Article 05.2.4.

[2] E. Deutsch and B. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory 117 (2006), 191–215.

[3] G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, 2nd edition, Oxford Science Publications, 1992.

[4] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, Underdiagonal lattice paths with unrestricted steps, Discrete Appl. Math. 91 (1999), 197–213.

[5] G. Raney, Functional composition patterns and power series reversion, Trans. Amer. Math. Soc. 94 (1960), 441–451.

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

[7] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[8] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999. Sections 5.3, 5.4.

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

[10] H. S. Wilf, Generatingfunctionology, Academic Press, 1994.

[11] W. J. Woan, Uniform partitions of Lattice paths and Chung-Feller generalizations, Amer. Math. Monthly 108 (2001), 556–559.

[12] W. J. Woan, A recursive relation for weighted Motzkin sequences, J. Integer Seq. 8 (2005), Article 05.1.6.

2000 Mathematics Subject Classification: Primary 0515; Secondary 05A19, 11B65. Keywords: enumerative combinatorics, lattice paths, Lagrange inversion formula.

Received November 19 2006; revised version received July 26 2007. Published in Journal of Integer Sequences, August 2 2007.

Return to Journal of Integer Sequences home page. 9