Journal of Integer Sequences, Vol. 3 (2000), Article 00.1.1 |
Abstract: Consider lattice paths in the plane allowing the steps (1,1), (1,-1), and (w,0), for some nonnegative integer w. For n > 1, let E(n,0) denote the set of paths from (0,0) to (n,0) running strictly above the x-axis except initially and finally. Generating functions are given for sums of moments of the ordinates of the lattice points on the paths in E(n,0). In particular, recurrencess are derived for the cardinality, the sum of the first moments (essentially the area), and the sum of the second moments for paths in E(n,0). These recurrences unify known results for w= 0, 1, 2, i.e. those for the Dyck (or Catalan), Motzkin, and Schröder paths, respectively. The sum of the second moments is seen to equal the number of unrestricted paths running from (0,0) to (0,n-2).
Contents:
1. Introduction: The paths and their moments
2. The recurrences
3. Enumerating restricted paths
4. Factorial moments
5. Area and second moments
6. Relating second moments to central numbers
7. Examples
8. Related studies
9. Bibliography
Let w be a fixed nonnegative integer. We will consider those lattice paths in the Cartesian plane whose permitted step types are the up diagonal step (1,1) denoted by U, the down diagonal step (1,-1) denoted by D, and the horizontal step (w,0) denoted by H. When w= 0, only U-steps and D-steps are permitted. We weight the steps by assigning 1 to each U-step, 1 to each D-step, and an indeterminate t to each H-step. The t-weight of a path P, denoted by |P|, is the product of the weights of its steps; and the t-weight of a set of paths S, denoted by |S|, is the sum of the t-weights of the paths in S.
Often we will suppress the parameter w and the indeterminate t in our notation. Let U(x,y) denote the set of all unrestricted lattice paths using the permitted step types and running from (0,0) to (x,y). We define the set of generalized Motzkin paths, denoted by M(x,y), to be the set of paths in U(x,y) that never run below the x-axis except initially and perhaps finally. Of particular interest is the set of elevated paths, denoted by E(x,y), consisting of those paths in M(x,y) that never touch the x-axis except initially and perhaps finally. For an example, see Figure 1 and the left column of Table 1 which give the four paths in E(5,0) when w = 1.
Let f_{n}(w) denote |E(n,0) | for n >= 2, with f_{0}(w) = f_{1}(w) = 0. For t = 1, there are three classical sequences covered by this notation, specifically for w = 0, 1 or 2. When w = 0, there are no horizontal steps and the paths of E(n,0) are the so-called elevated Dyck (or Catalan) paths; the corresponding sequence (f_{n}(0))_{n >= 2} = (1, 0, 1, 0, 2, 0, 5, 0, 14, . . . ) is the sequence of (aerated) Catalan numbers. For w = 1 and t = 1, (f_{n}(1))_{n >= 2} is the sequence of Motzkin numbers. For w = 2 and t = 1, (f_{n}(2))_{n >= 2} is the sequence of (aerated) large Schröder numbers. See Table 2 in Section 7. In 1948, using different indexing, Motzkin [12] introduced the sequence (f_{n}(1))_{n >= 2}, where f_{n}(1) denotes the number of ways to join n-2 points on a circle by nonintersecting chords. Donaghey and Shapiro [4] made an early study of this sequence which included lattice paths equivalent to those of M(n,0) with w= 1.
Consider a
path P in E(n,0) as a rectilinear curve. Let
(0, P(0)), (1, P(1)), ..., (n, P(n)) be the list of
all
lattice
points (points with integer coordinates)
on the path P. We will refer to the values
P(0), P(1), P(2), ..., P(n) as
the path ordinates of P. Define
the r^{th} moment of P to be
path | contribution | contribution | contribution | contribution |
to f_{5}(1) | to g_{5}(1) | to total area | to h_{5}(1) | |
UHUDD | t | 5t/4 | 5 | 7t/4 |
UUHDD | t | 6t/4 | 6 | 10t/4 |
UUDHD | t | 5t/4 | 5 | 7t/4 |
UHHHD | t^{3} | 4t^{3}/4 | 4 | 4t^{3}/4 |
Table 1: This table gives the contributions
to
f_{5}(1) = 3t+t^{3},
g_{5}(1) = 4t+t^{3},
h_{5}(1) = 6t+t^{3}, and the total area by the
the four paths
of E(5,0) for w = 1.
For fixed w >= 0 and for n >= 2, we define the following sums of
t-weighted moments for the path set E(n,0):
The main results of this paper are the three recurrences for these sequences, given uniformly in equations (5), (6), and (7), and the generating function for the factorial moments given in Proposition 5. In Section 2 we state these recurrences, which we then establsh by generating function methods in Sections 3, 4, and 5. In Section 6 we prove a surprising result relating second moments to central unrestricted numbers. In Section 7 we will give some examples of these sequences.
For any w >= 0, consider the following unified set of
recurrences
for the sequences,
(f_{n})_{n >= 2},
(g_{n})_{n >= 2}, and
(h_{n})_{n >= 2}, which we have defined above
in terms of t-weighted elevated
paths:
n f_{n} | = | 4(n-3) f_{n-2} + (2n - 3 w ) t f_{n-w} - (n - 3 w ) t^{2} f_{n-2w}, | (5) |
(n-1)g_{n} | = | 4(n-3) g_{n-2} + (2n - 2w-2)tg_{n-w} - (n - 2 w-1)t^{2} g_{n-2w}, | (6) |
(n-2)h_{n} | = | 4(n-3) h_{n-2} + (2n - w - 4 )th_{n-w} - (n - w - 2)t^{2} h_{n-2w}. | (7) |
Proposition 1.
For w = 0,
the sequences
(f_{n}(0))_{n >= 2},
(g_{n}(0))_{n >= 2}, and
(h_{n}(0))_{n >= 2} satisfy
n f_{n}(0) | = | 4(n-3) f_{n-2}(0) | (8) |
(n-1) g_{n}(0) | = | 4(n-3) g_{n-2}(0) | (9) |
(n-2) h_{n}(0) | = | 4(n-3) h_{n-2}(0) | (10) |
The proof of this Proposition is covered by the proofs of Propositions 2, 3, and 4. Recurrence (8) dates from about 1758, when Euler [5] recorded it, slightly re-indexed, when he and Segner [14] were considering counting triangulations of convex polygons. See Section 8. It follows immediately that, for k >= 0,
For w >= 1, we have the following more general result, which in proved in the next section:
With a_{n} = a_{n}(w) denoting the t-weighted area, , the trapezoidal area formula shows that a_{n} = (n-1)g_{n} for all n >= 2. The following result, proved in Section 5, generalizes one of Kreweras [9] for w = 2 and t = 1.
We remark that (10) is a well-known recurrence for the central binomial coefficients. In the case when w = 1 with t = 1, recurrence (7) dates from 1764, as Euler [6] proved that the central trinomial coefficients satisfy this recurrence when appropriately re-indexed. Our knowledge that these central coefficients are solutions to the recurrences (7) and (10) led to an interesting relationship between second moments and central numbers of the form |U(n,0)| for arbitrary w. Specifically, in Section 6 we will see that |U(n-2, 0 )| satisfies a recurrence that is also satisfied by h_{n}(t); thus we have a proof of identity (13) below. The proof of the first part of the following appears in Section 5.
Consider the generating function
.
With
the exception of the point path, each path in
M(n,0) either begins with an H-step
or immediately leaves the x-axis and then later returns
for a first time.
Consequently, with L denoting
and with
juxtaposition indicating concatenation,
we have a decomposition
that defines L recursively:
Note that the coefficient of
z^{n} both in
the power
series for F(z) and in the power series for
RECUR(n): | n f_{n} = 4(n-3) f_{n-2} + (2n - 3 w) t f_{n-w} - (n - 3 w) t^{2} f_{n-2w} |
RECUR(3w): | 3wf_{3w} = 4(3w-3) f_{3w-2} + 3wt f_{2w} - 0 t^{2} f_{w}, |
Here we extend a method for summing path ordinates,
given by Woan, Shapiro, and Rogers [21],
to one for summing falling factorials of ordinates for paths of E(n,0).
For a positive integer r we will consider the t-weighted sum of the
falling factorial moments, given by (with the divisor n - 1 missing)
Proof. We use the following temporary notation. Let B(A) = 1 if A is a true statement and B(A) = 0 if is false. Let ``(i,k) step end of P'' abbreviate ``(i,k) is an end point of a step of path P''. Let ``(i,k) interior of P'' abbreviate ``(i,k) is an interior lattice point on a horizontal step of path P''. Such a horizontal step will run from (j,k) to (j+w,k) in our notation. Let Q be any path in E(j,k). Let R and R' denote arbitrary paths that never pass below the x-axis with R running from (j,k) to (n,0) and R' running from (j+w,k) to (n,0). By symmetry, R can be matched with a path in E(n-j,k). Let m(j,k) denote |E(j,k)|.
For n >= 2,
= | |||
= | |||
= | |||
= | |||
= | |||
= |
With M denoting M(z), we
claim that the
following string of equations holds:
To establish this string we first
note that
each path in E(j,k) must depart from each line y = c,
for integer c,
0 <= c < k,
for a last time.
Hence a simple convolution argument shows
that the generating function for m(j,k) satisfies
To
handle the middle fraction in (19)
we use (14)
twice:
To handle the last fraction in (19)
use the following
result derived from formula (15),
with
:
Setting r = 1 in
Proposition 5, we obtain a
generating function for sums of the t-weighted areas:
There is an interesting corollary when w = 1. Using
partial fractions decomposition, the generating function
(21) yields
To obtain the generating function for the second moments,
,
we use
the following, where the constant of integration is checked to be
0:
Let
.
From (22), differentiation with respect to z yields
We begin with a straightforward extension of the André reflection method to paths that contain horizontal steps. We obtain the following string of bijections:
M(n,0) | = | U(n,0) - { P in U(n,0) : P intersects the line y = -1} | |
<-> | U(n,0) - { P' : P' runs from (0,-2) to (n,0) } | (23) | |
<-> | U(n,0) - U(n,2). | (24) |
Let u(x,y) denote |U(x,y)|.
Since any path to the point (n+1,k) must end with a U, D, or H step,
we have
2f_{n+2} | = | 2u(n,0) - 2u(n,2) | |
= | 4 u(n,0) - 2u(n+1,1) +2 t u(n-w+1,1) | ||
= | 4 u(n,0) + t u(n-w+2,0)- u(n+2,0) - (t^{2}u(n-2w+2,0)-t u(n-w+2,0)) | ||
= | -u(n+2,0) + 4 u(n,0) + 2 t u(n-w+2,0) -t^{2} u(n-2w+2,0). | (25) |
Returning to results (16) and (22),
we observe that they imply
= | |||
= |
The first formula of (11) yields the following known
relation between
the Catalan numbers and the central binomial numbers.
Upon replacing 2k+2 by n in that formula, we find for
h = 0, n >= 2 and n even,
Proof: One can substitute expressions given by recurrence (7) and (26) into (5), which is valid for n > 2w. Our substitutions were facilitated using a computer algebra program. Equation (13) then is applied to complete the proof.
In Table 2, we record the previously studied, and named, examples satisfying the recurrences in Propositions 1 to 4, along with their reference number from Sloane's On-Line Encyclopedia of Integer Sequences [16]. These examples correspond to sets of elevated paths, (E(n,0) )_{n >= 2}, so in the table n = 2, 3, 4 . . . and k = 1, 2, 3 . . . .
t | Sequence | Name | Sloane | |
1 | f_{n}(0) | 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42 | aerated Catalan nos. | |
1 | f_{2k}(0) | 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 | Catalan nos. | A000108 |
1 | a_{2k}(0) | 1, 4, 16, 64, 256, 1024, 4096, 16384 | powers of 4 | A000302 |
1 | h_{2k}(0) | 1, 2, 6, 20, 70, 252, 924, 3432, 12870 | central binomial nos. | A000984 |
1 | f_{n}(1 ) | 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188 | Motzkin nos. | A001006 |
2 | f_{n}(1 ) | 1, 2, 5, 14, 42, 132, 429, 1430, 4862 | (lacking initial 1) | A000108 |
3 | f_{n}(1 ) | 1, 3, 10, 36, 137, 543, 2219, 9285, 39587 | (tree-like polyhexes) | A002212 |
4 | f_{n}(1 ) | 1, 4, 17, 76, 354, 1704, 8421, 42508 | (walks on cubic lattice) | A005572 |
1 | a_{n}(1) | 1, 2, 7, 20, 61, 182, 547, 1640, 4921 | A014983 | |
1 | h_{n}(1 ) | 1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139 | central trinomial nos. | A002426 |
1 | f_{2k}(2) | 1, 2, 6, 22, 90, 394, 1806, 8558, 41586 | large Schröder | A006318 |
1 |
a_{2k}(2) | 1, 7, 41, 239, 1393, 8119, 47321, 275807 | A002315 | |
1 | h_{2k}(2) | 1, 3, 13, 63, 321, 1683, 8989, 48639 | central Delannoy nos. | A001850 |
1 | f_{n}(3 ) | 1, 0, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136 | A005418 | |
1 | a_{n}(3) | 1, 0, 4, 4, 16, 24, 71, 128, 328, 650 | A053441 | |
1 | h_{n}(3 ) | 1, 0, 2, 1, 6, 6, 21, 30, 82, 141, 342, 650 | A053442 |
In Table 2, the ``walks on cubic lattice'' entry illustrates one role played by the indeterminate t. Corresponding to the case w = 1 and t = 4, Guy [7] found f_{n} (mildly re-indexed) to count the walks on a three-dimensional lattice that use unit steps in all six standard directions (i.e. the positive and negative unit steps parallel to the three axes), that start at (0,0,0), end on the x-y plane, and never pass beneath that plane. More generally, for m > 3, w = 1 and t = 2^{m-1}, we find that f_{n} counts the walks of length n-2 on the m-dimensional integer lattice that use the unit steps in all 2^{m} standard directions, start at the origin, end on the hyperplane, x_{1} + ... +x_{m-1} = 0, and never pass through a lattice point (x_{1}, ... , x_{m}) for which x_{m} < 0. To see this we identify the unit step in the positive x_{m} direction with the U-step, the unit step in the negative x_{m} direction with the D-step, and the set of the other 2^{m-1} steps, none of which affects the distance from the hyperplane, x_{1} + ... +x_{m-1} = 0, with a weighed H-step.
Another example utilizing t is the enumeration of the horizontal
steps over all paths in E(n,0). Let f_{n,k} denote the number of
paths in
E(n,0) having k horizontal steps. We find that the
generating function for the total
number of
horizontal steps on paths having k horizontal steps satisfies
As noted in [8], in the 1730's, Ming An-tu, a Mongolian mathematician, was aware of the Catalan numbers, (c_{n})_{n>=0} = (1, 1, 2, 5, 14, ...), in a non-combinatorial sitting. He discovered several recurrence for these numbers including the well-known convolution recurrence, c_{n} = c_{0}c_{n-1} + c_{1}c_{n-2} + . . . + c_{n-1}c_{0}. In about 1758, Euler [5] and Segner [14] made the first European discovery of these numbers while counting the triangulations of a convex polygon. They observed that c_{n-2} is the number of ways to draw non-crossing diagonals between the vertices of a convex n-gon. Segner recorded and proved the above convolution recurrence in terms of triangulations of polygons. Euler observed, without giving a proof, that c_{n} = (4n-2)/(n+1) c_{n-1}, which is essentially (8), and then gave a closed form for c_{n} as a product of ratios that reduces to a ratio of product as in the first formula of (11).
There are several studies on lattice paths, in addition to those mentioned previously, that have influenced our results. Barcucci, Pinzani, and Sprugnoli [1] have made a systematic analysis containing recurrences - many mixed - for the Motzkin paths, i.e. w = 1 and t = 1, involving the sequences for count, central entries (central trinomial coefficients), and other related statistics. Recently the author [20] has established (5), (6), and (7) bijectively for Motzkin paths.
Besides Kreweras [9], Bonin, Shapiro, and Simion [2] have considered elevated Schröder paths and the recurrence (12) for w = 2. For w = 2 the author [18] has employed bijective schema to establish recurrences (5) and (12); in [19] he has considered (5), (6), and (7) in terms of parallelogram polyominoes. Most recently for w = 2, Merlini, Sprugnoli, and Verri [11] have given additional proofs for (5) with essentially an arbitrary t, while Pergola and Pinzani [13] have developed an encoding relating area to path count to obtain (12) bijectively.
Merlini, Sprugnoli, and Verri [10] have developed generating functions for the total area bounded by lattice paths where the permitted steps are more general than our U, D, and H. For Dyck paths, Chapman [3] has considered the generating functions for the sums of path moments and the relationship between the generating functions for elevated versus non-elevated paths.
Stanley [17] has given an extensive treatment of generalizations of the central entries, |U(n,0)|, under the name ``diagonals''. In [17] his results for differentiably finite power series relate to our use of the generating functions and of Sections 3 and 5. Correspondingly, he considered polynomially recursive sequences, for which our sequences (f_{n}), (g_{n}), and (h_{n}) are prime examples.
Acknowledgements: The author thanks Lou Shapiro for sharing an early draft of [21] and for his suggestions improving this paper. The author also thanks Joyce Sulanke for her assistance in translating [5], [6], and [14].
(This paper uses lattice paths to produce a unified treatment of sequences A000108, A000302, A000984, A001006, A001850, A002212, A002315, A002426, A005418, A005572, A006318, A014983, A053441, A053442 in the On-Line Encyclopedia of Integer Sequences.)