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

ⓘ

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

26.5 Lattice Paths: Catalan Numbers 26.7 Set Partitions: Bell Numbers

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov

§26.6 Other Lattice Path Numbers

Contents

§26.6(i) Definitions

Delannoy Number $D(m,n)$

Motzkin Number $M(n)$

Narayana Number $N(n,k)$

Schröder Number $r(n)$

§26.6(ii) Generating Functions

§26.6(iii) Recurrence Relations

§26.6(iv) Identities

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!

§26.6 Other Lattice Path Numbers

Contents

§26.6(i) Definitions

Delannoy Number D⁡(m,n)

Motzkin Number M⁡(n)

Narayana Number N⁡(n,k)

Schröder Number r⁡(n)

§26.6(ii) Generating Functions

§26.6(iii) Recurrence Relations

§26.6(iv) Identities

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!

Delannoy Number $D(m,n)$

Motzkin Number $M(n)$

Narayana Number $N(n,k)$

Schröder Number $r(n)$