Schröder Number

Author

Eric W. Weisstein
October 4, 2008

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

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

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

Formulas

s[0]:=1
s[n_]:=s[n]=s[n-1]+Sum[s[k]s[n-1-k],{k,0,n-1}]

s/@Range[0,10]

Forms

S(n)==2 (Hypergeometric2F1[1-n, n+2, 2, -1])

Table[2Hypergeometric2F1[-n+1,n+2,2,-1],{n,0,10}]

S(n)==-(1/2) (Subscript[C, n+1]^((-1/2)))(3)

Table[-(1/2) GegenbauerC[1+n,-(1/2),3],{n,0,10}]

S(n)==(1/2) (-(LegendreP[n-1, 3])+6 (LegendreP[n, 3])-(LegendreP[n+1, 3]))

Table[(1/2) (-LegendreP[-1+n,3]+6 LegendreP[n,3]-LegendreP[1+n,3]),{n,0,10}]

Generating Function

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

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

1+Sum[-(1/2) GegenbauerC[1+n,-(1/2),3](x^n),{n,∞}]//Factor

Sum[2Hypergeometric2F1[-n+1,n+2,2,-1](x^n),{n,0,∞}]

Sum[2Hypergeometric2F1[-n+1,n+2,2,-1](x^n),{n,0,10}]

Sum[(1/2) (-LegendreP[-1+n,3]+6 LegendreP[n,3]-LegendreP[1+n,3])(x^n),{n,0,∞}]

Factor[Expand//@FullSimplify[%]]

V5

<<DiscreteMath`RSolve`

SeriesTerm[(1-x-(1-6*x+x^2)^(1/2))/(2*x),{x,0,n}]

Solve[(1-x)g[x]-x g[x]^2==1,g[x]]

V6

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

FullSimplify[SeriesCoefficient[(1-x-(1-6*x+x^2)^(1/2))/(2*x),{x,0,n}],n≥1]

Table[(1/2) (-LegendreP[-1+n,3]+6 LegendreP[n,3]-LegendreP[1+n,3]),{n,0,10}]

V7

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

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

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

Powers of 10

Series

Series[Hypergeometric2F1[-n+1,n+2,2,-1],{n,∞,1}]

Enumeration

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

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

...crashes on Mac...

Exact

N[Log[10,3+2Sqrt[2]],20]

Closed Form

Limit[Log[10,Hypergeometric2F1[-n+1,n+2,2,-1]]/n,n->∞]//Timing

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

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

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

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

Graphic

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]]}]
]

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

s[1]:={{ne},{e,n}}
s[2]:={{e,e,n,n},{e,ne,n},{e,n,e,n},{e,n,ne},{ne,e,n},{ne,ne}}
s[3]:={{e,e,e,n,n,n},{e,e,ne,n,n},{e,e,n,e,n,n},{e,e,n,ne,n},{e,e,n,n,e,n},{e,e,n,n,ne},
		{e,ne,e,n,n},{e,ne,n,e,n},{e,ne,ne,n},{e,ne,n,ne},{e,n,e,n,e,n},{e,n,e,e,n,n},
		{e,n,e,ne,n},{e,n,e,n,ne},{e,n,ne,e,n},{e,n,ne,ne},{ne,e,e,n,n},{ne,e,ne,n},
		{ne,e,n,e,n},{ne,e,n,ne},{ne,ne,e,n},{ne,ne,ne}}

Show[GraphicsArray[
	Flatten[{{si[s,1]},partition[si[s,2],6],partition[si[s,3],6]},1]],
	DisplayFunction->$DisplayFunction]

Show[GraphicsArray[
	Flatten[{{si[s,1]},partition[si[s,2],6],partition[si[s,3],6]},1]],
	DisplayFunction->$DisplayFunction]