§26.6 Other Lattice Path Numbers

Permalink:: http://dlmf.nist.gov/26.6

§26.6(i) Definitions
§26.6(ii) Generating Functions
§26.6(iii) Recurrence Relations
§26.6(iv) Identities

§26.6(i) Definitions

Notes:: See Comtet (1974, pp. 80–81) and Stanley (1999, pp. 237–238, 241). (26.6.4) is a consequence of André’s reflection principle; see Comtet (1974, pp. 22–23). Tables 26.6.1–26.6.4 were computed by the author.
Permalink:: http://dlmf.nist.gov/26.6.i

¶ Dellanoy Number $D(m,n)$

Keywords:: Dellanoy numbers

$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)=\sum _{{k=0}}^{n}\binom{n}{k}\binom{m+n-k}{n}=\sum _{{k=0}}^{n}2^{k}\binom{m}{k}\binom{n}{k}.$

Defines:: $D(m,n)$ : Dellanoy number
Symbols:: $\binom{m}{n}$ : binomial coefficient, $k$ : nonnegative integer, $m$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.6.E1
Encodings:: TeX, pMML, png

See Table 26.6.1.

Table 26.6.1: Dellanoy numbers $D(m,n)$ .

$m$	$n$
$m$	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

Symbols:: $D(m,n)$ : Dellanoy number, $m$ : nonnegative integer and $n$ : nonnegative integer
Keywords:: Dellanoy numbers
Referenced by:: ¶ ‣ §26.6(i), §26.6(i)
Permalink:: http://dlmf.nist.gov/26.6.T1

¶ Motzkin Number $M(n)$

Keywords:: Motzkin numbers

$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)=\sum _{{k=0}}^{n}\frac{(-1)^{k}}{n+2-k}\binom{n}{k}\binom{2n+2-2k}{n+1-k}.$

Defines:: $M(n)$ : Motzkin number
Symbols:: $\binom{m}{n}$ : binomial coefficient, $k$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.6.E2
Encodings:: TeX, pMML, png

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

Symbols:: $M(n)$ : Motzkin number and $n$ : nonnegative integer
Keywords:: Motzkin numbers
Referenced by:: ¶ ‣ §26.6(i)
Permalink:: http://dlmf.nist.gov/26.6.T2

¶ Narayana Number $N(n,k)$

Keywords:: Narayana numbers

$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)=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}.$

Defines:: $N(n,k)$ : Narayana number
Symbols:: $\binom{m}{n}$ : binomial coefficient, $k$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.6.E3
Encodings:: TeX, pMML, png

See Table 26.6.3.

Table 26.6.3: Narayana numbers $N(n,k)$ .

$n$	$k$
$n$	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

Symbols:: $N(n,k)$ : Narayana number, $k$ : nonnegative integer and $n$ : nonnegative integer
Keywords:: Narayana numbers
Referenced by:: ¶ ‣ §26.6(i)
Permalink:: http://dlmf.nist.gov/26.6.T3

¶ Schröder Number $r(n)$

Keywords:: Schröder numbers

$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),$ $n\geq 1$ .

Defines:: $r(n)$ : Schröder number
Symbols:: $D(m,n)$ : Dellanoy number and $n$ : nonnegative integer
Referenced by:: §26.6(i)
Permalink:: http://dlmf.nist.gov/26.6.E4
Encodings:: TeX, pMML, png

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