Digital Library of Mathematical Functions
About the Project
NIST
26 Combinatorial AnalysisProperties

§26.6 Other Lattice Path Numbers

Contents

§26.6(i) Definitions

Dellanoy Number D(m,n)

D(m,n) is the number of paths from (0,0) to (m,n) that are composed of directed line segments of the form (1,0), (0,1), or (1,1).

26.6.1 D(m,n)=k=0n(nk)(m+n-kn)=k=0n2k(mk)(nk).

See Table 26.6.1.

Table 26.6.1: Dellanoy numbers D(m,n).
m n
0 1 2 3 4 5 6 7 8 9 10
0 1 1 1 1 1 1 1 1 1 1 1
1 1 3 5 7 9 11 13 15 17 19 21
2 1 5 13 25 41 61 85 113 145 181 221
3 1 7 25 63 129 231 377 575 833 1159 1561
4 1 9 41 129 321 681 1289 2241 3649 5641 8361
5 1 11 61 231 681 1683 3653 7183 13073 22363 36365
6 1 13 85 377 1289 3653 8989 19825 40081 75517 1 34245
7 1 15 113 575 2241 7183 19825 48639 1 08545 2 24143 4 33905
8 1 17 145 833 3649 13073 40081 1 08545 2 65729 5 98417 12 56465
9 1 19 181 1159 5641 22363 75517 2 24143 5 98417 14 62563 33 17445
10 1 21 221 1561 8361 36365 1 34245 4 33905 12 56465 33 17445 80 97453

Motzkin Number M(n)

M(n) is the number of lattice paths from (0,0) to (n,n) that stay on or above the line y=x and are composed of directed line segments of the form (2,0), (0,2), or (1,1).

26.6.2 M(n)=k=0n(-1)kn+2-k(nk)(2n+2-2kn+1-k).

See Table 26.6.2.

Table 26.6.2: Motzkin numbers M(n).
n M(n) n M(n) n M(n) n M(n) n M(n)
0 1 4 9 8 323 12 15511 16 8 53467
1 1 5 21 9 835 13 41835 17 23 56779
2 2 6 51 10 2188 14 1 13634 18 65 36382
3 4 7 127 11 5798 15 3 10572 19 181 99284

Narayana Number N(n,k)

N(n,k) is the number of lattice paths from (0,0) to (n,n) that stay on or above the line y=x, are composed of directed line segments of the form (1,0) or (0,1), and for which there are exactly k occurrences at which a segment of the form (0,1) is followed by a segment of the form (1,0).

26.6.3 N(n,k)=1n(nk)(nk-1).

See Table 26.6.3.

Table 26.6.3: Narayana numbers N(n,k).
n k
0 1 2 3 4 5 6 7 8 9 10
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 6 6 1
5 0 1 10 20 10 1
6 0 1 15 50 50 15 1
7 0 1 21 105 175 105 21 1
8 0 1 28 196 490 490 196 28 1
9 0 1 36 336 1176 1764 1176 336 36 1
10 0 1 45 540 2520 5292 5292 2520 540 45 1

Schröder Number r(n)

r(n) is the number of paths from (0,0) to (n,n) that stay on or above the diagonal y=x and are composed of directed line segments of the form (1,0), (0,1), or (1,1).

26.6.4 r(n)=D(n,n)-D(n+1,n-1),
n1.

See Table 26.6.4.

Table 26.6.4: Schröder numbers r(n).
n r(n) n r(n) n r(n) n r(n) n r(n)
0 1 4 90 8 41586 12 272 97738 16 2 09271 56706
1 2 5 394 9 2 06098 13 1420 78746 17 11 18180 26018
2 6 6 1806 10 10 37718 14 7453 87038 18 60 03188 53926
3 22 7 8558 11 52 93446 15 39376 03038 19 323 67243 17174

§26.6(ii) Generating Functions

For sufficiently small |x| and |y|,

26.6.5 m,n=0D(m,n)xmyn=11-x-y-xy,
26.6.6 n=0D(n,n)xn=11-6x+x2,
26.6.7 n=0M(n)xn=1-x-1-2x-3x22x2,
26.6.8 n,k=1N(n,k)xnyk=1-x-xy-(1-x-xy)2-4x2y2x,
26.6.9 n=0r(n)xn=1-x-1-6x+x22x.

§26.6(iii) Recurrence Relations

26.6.10 D(m,n) =D(m,n-1)+D(m-1,n)+D(m-1,n-1),
m,n1,
26.6.11 M(n) =M(n-1)+k=2nM(k-2)M(n-k),
n2.

§26.6(iv) Identities

26.6.14 C(n)=k=02n(-1)k(2nk)M(2n-k).