Motzkin Number

Author

Eric W. Weisstein
November 22, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/MotzkinNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/MotzkinNumber.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Code

Motzkin[0]:=1
Motzkin[1]:=1
Motzkin[n_]:=Motzkin[n]=((3 (-1+n) Motzkin[n-2]+(1+2 n) Motzkin[n-1])/(2+n))
MotzkinM[n_]:=Hypergeometric2F1[(1/2)(1-n),-(1/2)n,2,4]

Eumeration

l=Motzkin/@Range[0,10]

(MotzkinDirect[#];//Timing)&/@{1000,2000,3000}

Table[Hypergeometric2F1[(1/2)(1-n),-(1/2)n,2,4],{n,0,10}]

Block[{$RecursionLimit=3000},(Motzkin[#];//Timing)&/@{1000,2000,3000}]

Recognizing

FindSequenceFunction[l]

FindLinearRecurrence[l]

FindGeneratingFunction[l,x]

SeriesCoefficient[%,{x,0,n}]

Powers of 10

Series

Series[Hypergeometric2F1[(1/2)(1-n),-(1/2)n,2,4],{n,∞,1}]

Enumeration

Table[Digits[Hypergeometric2F1[(1/2)(1-10^n),-(1/2)10^n,2,4]],{n,0,6}]//Timing

Table[Digits[Hypergeometric2F1[(1/2)(1-10^n),-(1/2)10^n,2,4]],{n,0,7}]//Timing

Table[Digits[Hypergeometric2F1[(1/2)(1-10^n),-(1/2)10^n,2,4]],{n,0,8}]//Timing

...crashes on Mac...

Exact

N[Log[10,3],20]

Series

expr=Simplify[Normal[Series[Log[10,Hypergeometric2F1[(1/2)(1-x),-(1/2)x,2,4]],{x,∞,1}]/.x->10^n],n∈Integers&&n>0]

Sequence Limit

Limit[Log[10,Hypergeometric2F1[(1/2)(1-n),-(1/2)n,2,4]]/n,n->∞]//Timing

ListPlot[Table[Log[10,Hypergeometric2F1[(1/2)(1-n),-(1/2)n,2,4]]/n,{n,1,1000}],PlotJoined->True,PlotStyle->Red]

SequenceLimit[N[Table[Log[10,Hypergeometric2F1[(1/2)(1-n),-(1/2)n,2,4]]/n,{n,1,1000}],100]]//Timing

SequenceLimit[N[Table[Log[10,Hypergeometric2F1[(1/2)(1-n),-(1/2)n,2,4]]/n,{n,1,10^4}],100]]//Timing

SequenceLimit[N[Table[Log[10,Hypergeometric2F1[(1/2)(1-n),-(1/2)n,2,4]]/n,{n,1,10^4}],500]]//Timing

Primes

(p=Position[Motzkin/@Range[1000],_?PrimeQ]//Flatten)//Timing

(p=Position[Motzkin/@Range[10^4],_?PrimeQ]//Flatten)//Timing

Digits[Motzkin[36]]//Timing

(p=Position[Motzkin/@Range[10^5],_?PrimeQ]//Flatten)//Timing

MotzkinM/@p

Continued Fraction

Series[(1-x-Sqrt[1-2x-3x^2])/(2x^2),{x,0,6}]

Quadratic

Solve[m==1+x m+x^2m^2,m]

Table[Motzkin[n],{n,0,10}]

Continued Fraction

1/NestList[1-x-x^2/#&,1,4]

Series[1/Nest[1-x-x^2/#&,1,20],{x,0,10}]

(1/(1-x+ContinuedFractionK[-x^2,1-x,{k,∞}]))//FullSimplify//ExpandAll

Series[(2/(1-x+(Sqrt[1-2 x-3 (x^2)]))),{x,0,10}]

Taylor

TaylorTerm[f_,{x_,x0_,n_}]:=Limit[ Derivative[n][Function[x,f]][x1]/n!,x1->x0]

Table[TaylorTerm[(1-x-Sqrt[1-2x-3x^2])/(2x^2),{x,0,n}],{n,0,10}]

Derivative[1][Function[x,(1-x-Sqrt[1-2x-3x^2])/(2x^2)]][0]

Series Coefficient

V5.2

<<DiscreteMath`RSolve`

SeriesTerm[(1-x-Sqrt[1-2x-3x^2])/(2x^2),{x,0,n}]

V6

SeriesCoefficient[(1-x-Sqrt[1-2x-3x^2])/(2x^2),{x,0,n}]

FullSimplify[%,n∈Integers&&n>0]

Table[%,{n,0,10}]//FullSimplify

V7

SeriesCoefficient[(1-x-Sqrt[1-2x-3x^2])/(2x^2),{x,0,n}]

Recurrence

Nested Sum

m[0]:=1
m[n_]:=m[n]=m[n-1]+Plus@@Table[m[k]m[n-2-k],{k,0,n-2}]

m/@Range[0,10]

Zeilbergen

<<"zb_alg.m"

Solve[First[Zb[-(1/2)(((-3))^k)Binomial[1/2,k]Binomial[1/2,n-k],k,n,2]/.{F[k_,n_]:>a[n],Delta[__]:>0}]/.n->n-2,a[n]]//Simplify

((3 (-3+n) mm[-2+n]+(-3+2 n) mm[-1+n])/n)/.n->n+2//Simplify

Explicit

m[0]:=1
m[1]:=1
m[n_]:=((3 (-1+n) m[n-2]+(1+2 n) m[n-1])/(2+n))

m/@Range[0,20]

RSolve[{3 (-1+n) m[n-2]+(1+2 n) m[n-1]==m[n](2+n),m[0]==1,m[1]==1},m[n],n]

RSolve

V6

RSolve[{m[n]==((3 (-1+n) m[n-2]+(1+2 n) m[n-1])/(2+n)),m[0]==m[1]==1},m[n],n]

V7

RSolve[{m[n]==((3 (-1+n) m[n-2]+(1+2 n) m[n-1])/(2+n)),m[0]==m[1]==1},m[n],n]//FunctionExpand

Last/@Flatten[Table[%,{n,10}]]

Table[Hypergeometric2F1[(1/2)(1-n),-(n/2),2,4],{n,10}]

Closed Forms

Table[Motzkin[n],{n,0,10}]

(Hypergeometric2F1[((1-n)/2), -(n/2), 2, 4])

Table[Hypergeometric2F1[(1/2)(1-n),-(n/2),2,4],{n,0,10}]

-(((Sqrt[π]) (Hypergeometric2F1Regularized[-(1/2), -n-2, -n-(1/2), -3]))/(4 (Gamma[n+3])))

Table[-(((Sqrt[π]) Hypergeometric2F1Regularized[-(1/2),-2-n,-(1/2)-n,-3])/(4 Gamma[3+n])),{n,0,10}]

((Trinomial(n+1,1))/(n+1))

Trinomial[n,2]

Table[(1/(n+1))Trinomial[n+1,1],{n,0,10}]

(1/2) (i^n) (3^(n/2)) (3 (LegendreP[n, -(i/(Sqrt[3]))])+3 (LegendreP[n+2, -(i/(Sqrt[3]))])+2 i (Sqrt[3]) (LegendreP[n+1, -(i/(Sqrt[3]))]))

Table[(1/2) (I^n) (3^(n/2)) (3 LegendreP[n,-(I/(Sqrt[3]))]+2 I (Sqrt[3]) LegendreP[1+n,-(I/(Sqrt[3]))]+3 LegendreP[2+n,-(I/(Sqrt[3]))]),{n,0,10}]//Expand

Sums

-(1/2) (∑_(a=0)^(n+2))(((-3))^a) (Binomial[(1/2), a]) (Binomial[(1/2), -a+n+2])

V6

$Version

-(1/2)Sum[(((-3))^a)Binomial[(1/2),a]Binomial[(1/2),(n+2-a)],{a,0,n+2}]

FullSimplify[%,n∈Integers&&n>0]//TraditionalForm

Table[-((Sqrt[π]) Hypergeometric2F1Regularized[-(1/2),-n-2,-n-(1/2),-3])/(4 Gamma[n+3]),{n,0,10}]

((((-3))^a)/((2a-1)(2b-1)))Binomial[2a,a]Binomial[2b,b]/.b->(n+2-a)//Simplify

{2b,b,2b-1}/.b->(n+2-a)//Simplify

V7

$Version

-(1/2)Sum[(((-3))^a)Binomial[(1/2),a]Binomial[(1/2),(n+2-a)],{a,0,n+2}]

((((-1))^(n+1))/(2^(2 n+5))) (∑_(a=0)^(n+2))-(((((-3))^a) (Binomial[2 a, a]) (Binomial[-2 a+2 n+4, -a+n+2]))/((2 a-1) (2 a-2 n-3)))

V6

((((-1))^(n+1))/(2^(2n+5)))Sum[-((((-3))^a) Binomial[2 a,a] Binomial[4-2 a+2 n,2-a+n])/((-1+2 a) (-3+2 a-2 n)),{a,0,n+2}]

FullSimplify[%,n∈Integers&&n>0]

V7

((((-1))^(n+1))/(2^(2n+5)))Sum[-((((-3))^a) Binomial[2 a,a] Binomial[4-2 a+2 n,2-a+n])/((-1+2 a) (-3+2 a-2 n)),{a,0,n+2}]

FullSimplify[%,n∈Integers&&n>0]

(1/n)(∑_(i=0)^(n-1))(Binomial[n, i]) (Binomial[i, -i+n-1])

V6

1/n Sum[Binomial[n,i]Binomial[i,n-i-1],{i,0,n-1}]

FullSimplify[%,n∈Integers]

V7

1/n Sum[Binomial[n,i]Binomial[i,n-i-1],{i,0,n-1}]

Table[Hypergeometric2F1[((2-n)/2),((1-n)/2),2,4],{n,10}]

Figure

sgrid[n_]:=Module[{i},
{GrayLevel[.5],Table[{Line[{{0,i},{n,i}}],Line[{{i,0},{i,n}}]},
{i,0,n}],{Dashing[{.1,.1}],Line[{{0,0},{n,n}}]}}
]

SquareGrid[n_,j_:0]:=Module[{i},
{GrayLevel[.5],Table[{Line[{{j,i},{n,i}}],Line[{{i,j},{i,n}}]},{i,j,n}]}
]

SquareGrid[x_List]:=Module[{i},
{GrayLevel[.5],
Table[Line[{{x[[1,1]],i},{x[[2,1]],i}}],{i,x[[1,2]],x[[2,2]]}],
Table[Line[{{i,x[[1,2]]},{i,x[[2,2]]}}],{i,x[[1,1]],x[[2,1]]}]
}]

si[{segs_,grid_,box___},{n_,k_}]:=Module[{i},
	Table[
		Show[Graphics[{
	{GrayLevel[.7],Polygon[box[n][[i]]]},
	grid[k],
	{Thickness[.05],RGBColor[1,0,0],Line[Map[path,segs[n]][[i]]]}
}],
AspectRatio->Automatic,DisplayFunction->Identity],
{i,Length[segs[n]]}]
]

m[1]:={{e}}
m[2]:={{ne,se},{e,e}}
m[3]:={{ne,se,e},{e,ne,se},{ne,e,se},{e,e,e}}
m[4]:={{e,e,e,e},{ne,se,e,e},{e,ne,se,e},{e,e,ne,se},{ne,se,ne,se},
		{ne,e,e,se},{ne,ne,se,se},{e,ne,e,se},{ne,e,se,e}}

Show[GraphicsArray[
	Flatten[{{si[{m,SquareGrid},1]},partition[si[{m,SquareGrid},2],6],
				partition[si[{m,SquareGrid},3],6],
			partition[si[{m,SquareGrid},4],5]},1]],
	DisplayFunction->$DisplayFunction]