26 Combinatorial Analysis Properties 26.5 Lattice Paths: Catalan Numbers 26.7 Set Partitions: Bell Numbers

§26.6 Other Lattice Path Numbers

ⓘ

Referenced by:: Erratum (V1.0.10) for Section 26.6
Permalink:: http://dlmf.nist.gov/26.6
Errata (effective with 1.0.10):: The spelling of the name Delannoy was corrected in several places in this section. Previously it was mispelled as Dellanoy.
See also:: Annotations for Ch.26

§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
See also:: Annotations for §26.6 and Ch.26

Delannoy Number $D(m,n)$

ⓘ

Keywords:: Delannoy numbers, definition, relation to lattice paths
See also:: Annotations for §26.6(i), §26.6 and Ch.26

$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}\genfrac{(}{)}{0.0pt}{}{n}{k}\genfrac{(}{)}{0.0pt}{}{m+n-% k}{n}=\sum_{k=0}^{n}2^{k}\genfrac{(}{)}{0.0pt}{}{m}{k}\genfrac{(}{)}{0.0pt}{}{% n}{k}.$
ⓘ Defines: $D(m,n)$ : Delannoy number (locally) Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{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 also: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

See Table 26.6.1.

Table 26.6.1: Delannoy 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:: $m$ : nonnegative integer, $n$ : nonnegative integer and $D(m,n)$ : Delannoy number
Keywords:: Delannoy numbers, table
Referenced by:: §26.6(i), §26.6(i)
Permalink:: http://dlmf.nist.gov/26.6.T1
See also:: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

Motzkin Number $M(n)$

ⓘ

Keywords:: Motzkin numbers, definition, relation to lattice paths
See also:: Annotations for §26.6(i), §26.6 and Ch.26

$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}\genfrac{(}{)}{0.0pt}{}{n}{k}\genfrac% {(}{)}{0.0pt}{}{2n+2-2k}{n+1-k}.$
ⓘ Defines: $M(n)$ : Motzkin number (locally) Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $k$ : nonnegative integer and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.6.E2 Encodings: TeX, pMML, png See also: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

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:: $n$ : nonnegative integer and $M(n)$ : Motzkin number
Keywords:: Motzkin numbers, table
Referenced by:: §26.6(i)
Permalink:: http://dlmf.nist.gov/26.6.T2
See also:: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

Narayana Number $N(n,k)$

ⓘ

Keywords:: Narayana numbers, definition, relation to lattice paths
See also:: Annotations for §26.6(i), §26.6 and Ch.26

$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}\genfrac{(}{)}{0.0pt}{}{n}{k}\genfrac{(}{)}{0.0pt}{}{n}{k-1}.$
ⓘ Defines: $N(n,k)$ : Narayana number (locally) Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $k$ : nonnegative integer and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.6.E3 Encodings: TeX, pMML, png See also: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

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:: $k$ : nonnegative integer, $n$ : nonnegative integer and $N(n,k)$ : Narayana number
Keywords:: Narayana numbers, table
Referenced by:: §26.6(i)
Permalink:: http://dlmf.nist.gov/26.6.T3
See also:: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

Schröder Number $r(n)$

ⓘ

Keywords:: Schröder numbers, definition, relation to lattice paths
See also:: Annotations for §26.6(i), §26.6 and Ch.26

$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 (locally) Symbols: $n$ : nonnegative integer and $D(m,n)$ : Delannoy number Referenced by: §26.6(i) Permalink: http://dlmf.nist.gov/26.6.E4 Encodings: TeX, pMML, png See also: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

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$

ⓘ

Symbols:: $n$ : nonnegative integer and $r(n)$ : Schröder number
Keywords:: Schröder numbers, table
Referenced by:: §26.6(i), §26.6(i)
Permalink:: http://dlmf.nist.gov/26.6.T4
See also:: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

§26.6(ii) Generating Functions

ⓘ

Keywords:: Delannoy numbers, Motzkin numbers, Narayana numbers, Schröder numbers, generating function, generating functions
Notes:: See Comtet (1974, p. 81) and Stanley (1999, pp. 238, 241).
Permalink:: http://dlmf.nist.gov/26.6.ii
See also:: Annotations for §26.6 and Ch.26

For sufficiently small $|x|$ and $|y|$ ,

26.6.5		$\sum_{m,n=0}^{\infty}D(m,n)x^{m}y^{n}=\frac{1}{1-x-y-xy},$
ⓘ Symbols: $m$ : nonnegative integer, $n$ : nonnegative integer, $D(m,n)$ : Delannoy number, $x$ : small and $y$ : small Permalink: http://dlmf.nist.gov/26.6.E5 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26

26.6.6		$\sum_{n=0}^{\infty}D(n,n)x^{n}=\frac{1}{\sqrt{1-6x+x^{2}}},$
ⓘ Symbols: $n$ : nonnegative integer, $D(m,n)$ : Delannoy number and $x$ : small Permalink: http://dlmf.nist.gov/26.6.E6 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26

26.6.7		$\sum_{n=0}^{\infty}M(n)x^{n}=\frac{1-x-\sqrt{1-2x-3x^{2}}}{2x^{2}},$
ⓘ Symbols: $n$ : nonnegative integer, $M(n)$ : Motzkin number and $x$ : small Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E7 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26

26.6.8		$\sum_{n,k=1}^{\infty}N(n,k)x^{n}y^{k}=\frac{1-x-xy-\sqrt{(1-x-xy)^{2}-4x^{2}y}% }{2x},$
ⓘ Symbols: $k$ : nonnegative integer, $n$ : nonnegative integer, $N(n,k)$ : Narayana number, $x$ : small and $y$ : small Permalink: http://dlmf.nist.gov/26.6.E8 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26

26.6.9		$\sum_{n=0}^{\infty}r(n)x^{n}=\frac{1-x-\sqrt{1-6x+x^{2}}}{2x}.$
ⓘ Symbols: $n$ : nonnegative integer, $r(n)$ : Schröder number and $x$ : small Permalink: http://dlmf.nist.gov/26.6.E9 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26

§26.6(iii) Recurrence Relations

ⓘ

Keywords:: Delannoy numbers, Motzkin numbers, recurrence relation
Notes:: For (26.6.10) see Comtet (1974, p. 81). (26.6.11) is a consequence of (26.6.7).
Permalink:: http://dlmf.nist.gov/26.6.iii
See also:: Annotations for §26.6 and Ch.26

26.6.10	$\displaystyle D(m,n)$	$\displaystyle=D(m,n-1)+D(m-1,n)+D(m-1,n-1),$
$m,n\geq 1$ ,
ⓘ Symbols: $m$ : nonnegative integer, $n$ : nonnegative integer and $D(m,n)$ : Delannoy number Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E10 Encodings: TeX, pMML, png See also: Annotations for §26.6(iii), §26.6 and Ch.26
26.6.11	$\displaystyle M(n)$	$\displaystyle=M(n-1)+\sum_{k=2}^{n}M(k-2)\,M(n-k),$
$n\geq 2$ .
ⓘ Symbols: $k$ : nonnegative integer, $n$ : nonnegative integer and $M(n)$ : Motzkin number Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E11 Encodings: TeX, pMML, png See also: Annotations for §26.6(iii), §26.6 and Ch.26

§26.6(iv) Identities

ⓘ

Keywords:: Catalan numbers, Motzkin numbers, Narayana numbers, identities, identity, lattice paths
Notes:: See Stanley (1999, pp. 237–238).
Permalink:: http://dlmf.nist.gov/26.6.iv
See also:: Annotations for §26.6 and Ch.26

26.6.12		$C\left(n\right)=\sum_{k=1}^{n}N(n,k),$
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number, $k$ : nonnegative integer, $n$ : nonnegative integer and $N(n,k)$ : Narayana number Permalink: http://dlmf.nist.gov/26.6.E12 Encodings: TeX, pMML, png See also: Annotations for §26.6(iv), §26.6 and Ch.26

26.6.13		$M(n)=\sum_{k=0}^{n}(-1)^{k}\genfrac{(}{)}{0.0pt}{}{n}{k}C\left(n+1-k\right),$
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number, $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $k$ : nonnegative integer, $n$ : nonnegative integer and $M(n)$ : Motzkin number Permalink: http://dlmf.nist.gov/26.6.E13 Encodings: TeX, pMML, png See also: Annotations for §26.6(iv), §26.6 and Ch.26

26.6.14		$C\left(n\right)=\sum_{k=0}^{2n}(-1)^{k}\genfrac{(}{)}{0.0pt}{}{2n}{k}M(2n-k).$
ⓘ Symbols: $C\left(\NVar{n}\right)$ : Catalan number, $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, $k$ : nonnegative integer, $n$ : nonnegative integer and $M(n)$ : Motzkin number Permalink: http://dlmf.nist.gov/26.6.E14 Encodings: TeX, pMML, png See also: Annotations for §26.6(iv), §26.6 and Ch.26