Catalan Number

Author

Eric W. Weisstein
April 12, 2010

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

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

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

Usage

?CatalanNumber

Plots

<<Utilities`Plot`

Real Axis

Plot[CatalanNumber[n],{n,-3,7},AxesLabel->{n,CatalanNumber[n]},PlotRange->200,WorkingPrecision->50,PlotPoints->1000,MaxRecursion->10,Epilog->{{Thickness[.003],Blue,Dashing[{.02}],Line[{{-#,-1000},{-#,1000}}]&/@Range[1/2,5/2]},Red,PointSize[.02],Point[Table[{n,CatalanNumber[n]},{n,-10,10}]]}]

Complex Plane

ComplexPlot3D[CatalanNumber[z],{z,-5,5},PlotPoints->100]

ComplexPlot3D[CatalanNumber[z],{z,-5,5},PlotPoints->100,"PolygonReduction"->.3]

ComplexContourPlot[CatalanNumber[z],{z,-5,5}]

ComplexContourPlot[CatalanNumber[z],{z,-5,5},Contours->10,"MeshRegions"->False,"PackGraphicsComplex"->True]

Enumeration

CatalanNumber[Range[0,10]]

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

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

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

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

Roots

Plot[CatalanNumber[x],{x,-3,2},Exclusions->{Mod[2x,1]==0}]

Plot[CatalanNumber[x],{x,-3.5,3},Exclusions->Range[-5/2,0],MaxRecursion->10,PlotPoints->100,PlotStyle->{Red,Thickness[.005]},Method->{"AxesInFront"->False}]

CatalanNumber/@Range[-4,4]

Solve[CatalanNumber[z]==0,z,Complexes]

Reduce[CatalanNumber[z]==0,z,Complexes]

FindInstance[CatalanNumber[z]==0,z,Complexes]

FunctionExpand[CatalanNumber[z]]

Identities

(Subscript[C, n])==(((2^n) (2 n-1)!!)/((n+1)!))/; n∈ℤ

FullSimplify[(((2^n)(2n-1)!!)/((n+1)!))]

FullSimplify[Subtract@@{Catalan[n],(((2^n) (2 n-1)!!)/((n+1)!))},n∈Integers]

Equal@@@Table[{CatalanNumber[n],(((2^n) (2 n-1)!!)/((n+1)!))}/.n->RandomComplex[5(I+1){-1,1},WorkingPrecision->20],{10^3}]//Union//Timing//Quiet

Equal@@@Table[{CatalanNumber[n],(((2^n) (2 n-1)!!)/((n+1)!))}/.n->RandomReal[5,WorkingPrecision->20]{-1,1},{10^3}]//Union//Timing

Equal@@@Table[{CatalanNumber[n],(((2^n) (2 n-1)!!)/((n+1)!))}/.n->RandomInteger[5]{-1,1},{10^3}]//Union//Timing

(Subscript[C, n])==(((4^n) Γ(n+(1/2)))/((Sqrt[π]) Γ(n+2)))

FullSimplify[(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[2+n]))]

FullSimplify[Subtract@@{CatalanNumber[n],(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[2+n]))}]

Equal@@@Table[{CatalanNumber[n],(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[2+n]))}/.n->RandomComplex[5(I+1){-1,1},WorkingPrecision->20],{10^3}]//Union//Timing

(CatalanNumber[n])==(((-1))^n) (2^(2 n+1)) (Binomial[(1/2), n+1])

(((-1))^n) (2^(1+2 n)) Binomial[(1/2),1+n]

(CatalanNumber[n])==(Subscript[, 2])(Subscript[F, 1])(1-n,-n;2;1)

FunctionExpand[Hypergeometric2F1[1-n,-n,2,1],n>0]

FullSimplify[Hypergeometric2F1[1-n,-n,2,1],n>0]

FullSimplify[Hypergeometric2F1[1-n,-n,2,1]-CatalanNumber[n],n>0]

FunctionExpand[Hypergeometric2F1[1-n,-n,2,1]-CatalanNumber[n],n>0]

Series

(CatalanNumber[x])==...+(x^4) (2 ζ(3)+((π^2)/6)+((19 (π^4))/360)+1)+(x^3) (-2 ζ(3)-((π^2)/6)-1)+(1+((π^2)/6)) (x^2)-x+1

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

Series[CatalanNumber[x],{x,0,3}]

Series[CatalanNumber[x],{x,0,5}]

(CatalanNumber[x])==(4^x) ((((((1/x)))^(3/2))/(Sqrt[π]))-((9 ((((1/x)))^(5/2)))/(8 (Sqrt[π])))+((145 ((((1/x)))^(7/2)))/(128 (Sqrt[π])))+...)

SeriesCoefficient[CatalanNumber[x],{x,∞,n}]

Series[CatalanNumber[x],{x,∞,12}]

Normal[%]

Simplify[(4^(-x))Sqrt[π]%/y^3/.x->1/y^2,y>0]

CoefficientList[%,y][[1;;-1;;2]]

Through[{Numerator,Denominator}[%]]

FindSequenceFunction[First[%]]

Table[Binomial[2n-1/2,-1/2],{n,0,10}]

Series[(x/((Sqrt[1+x])-(Sqrt[1-x]))),{x,0,20}]

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

FunctionExpand[%]

Derivative and Integral

Derivative

D[CatalanNumber[x],x]

FullSimplify[%]

TraditionalForm[%]

Integrals

Indefinite

Integrate[CatalanNumber[x],x]

Integrate[FunctionExpand[CatalanNumber[x]]//FullSimplify,x]

Generating Function

GF==((1-(Sqrt[1-4 x]))/(2 x))

V7?

GeneratingFunction[CatalanNumber[n],n,x]

Sum[CatalanNumber[n](x^n),{n,0,∞}]

Sum[CatalanNumber[n](x^n),{n,0,∞},GenerateConditions->True]

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

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

FullSimplify[(((-1))^n) (2^(1+2 n)) Binomial[(1/2),1+n]-CatalanNumber[n],n>0&&n∈Integers]

FullSimplify[(((-1))^n) (2^(1+2 n)) Binomial[(1/2),1+n]-CatalanNumber[n],n>0&&n∈Integers]

V8

Sum[CatalanNumber[n]x^n,{n,0,∞}]//FullSimplify

GeneratingFunction[CatalanNumber[n],n,z]

Better GF = (2/(1+(Sqrt[1-4x])))

FullSimplify[(2/(1+(Sqrt[1-4x])))-((1-(Sqrt[1-4 x]))/(2 x))]

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

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

Sum[CatalanNumber[n](x^n),{n,0,10}]

EGF==(e^(2 x)) ((Subscript[I, 0])(2 x)-(Subscript[I, 1])(2 x))

Sum[((x^n)/(n!))CatalanNumber[n],{n,0,∞}]

FullSimplify[SeriesCoefficient[(E^(2 x)) (BesselI[0,2 x]-BesselI[1,2 x]),{x,0,n}],n∈Integers&&n>0]

ExponentialGeneratingFunction[CatalanNumber[n],n,x]

DirichletGeneratingFunction

Sum[((CatalanNumber[n])/(n^s)),{n,∞}]

Sum[((((2n)!)/(n!(n+1)!))/(n^s)),{n,∞}]

Lambert Series

Sum[((CatalanNumber[n](x^n))/(1-(x^n))),{n,∞}]

FunctionExpand[CatalanNumber[n]]

Sum[(((((2^(2 n)) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[2+n]))(x^n))/(1-(x^n))),{n,∞}]

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

Sums giving C

(∑_(k=0)^(n-1))(CatalanNumber[k]) (CatalanNumber[-k+n-1])==(CatalanNumber[n])

Sum[CatalanNumber[k]CatalanNumber[n-1-k],{k,0,n-1}]

(∑_(k=0)^(n-1))(CatalanNumber[k]) (2^(-2 k+n-1)) (Binomial[n-1, 2 k])==(CatalanNumber[n])

Sum[Binomial[n-1,2k](2^(n-2k-1))CatalanNumber[k],{k,0,n-1}]

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

Subtract@@@Table[{(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[2+n])),CatalanNumber[n]},{n,0,10}]//Union

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

V7

(1/n)Sum[CatalanNumber[n-k-1]Binomial[2k+1,k+1],{k,0,n-1}]

(∑_(k=0)^n)(((-1))^k) (2^(n-k)) (Binomial[n, k]) (Binomial[k, ⌊(k/2)⌋])==(CatalanNumber[n])

Sum[(((-1))^k)(2^(n-k))Binomial[n,k]Binomial[k,Floor[k/2]],{k,0,n}]

Table[{Sum[(((-1))^k)(2^(n-k))Binomial[n,k]Binomial[k,Floor[k/2]],{k,0,n}],CatalanNumber[n]},{n,0,10}]

(∑_(k=0)^(⌊n/2⌋))((((((-2 k+n+1)/(-k+n+1))) (Binomial[n, n-k])))^2)==(CatalanNumber[n])

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

Sums Involving C

(∑_(n=0)^∞)(CatalanNumber[n]) (x^n)==((1-(Sqrt[1-4 x]))/(2 x))

Sum[CatalanNumber[n](x^n),{n,0,∞}]

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

Series[((1-(Sqrt[1-4 x]))/(2 x)),{x,0,5}]

(∑_(n=0)^∞)(((CatalanNumber[n]) (x^n))/(n!))==(e^(2 x)) ((Subscript[I, 0])(2 x)-(Subscript[I, 1])(2 x))

Sum[((x^n)/(n!))CatalanNumber[n],{n,0,∞}]

SeriesCoefficient[(E^(2 x)) (BesselI[0,2 x]-BesselI[1,2 x]),{x,0,n}]

Series[(E^(2 x)) (BesselI[0,2 x]-BesselI[1,2 x]),{x,0,10}]

Through[{Numerator,Denominator}[CoefficientList[Normal[%],x]]]

(∑_n^∞)((CatalanNumber[n])/(4^n))==1

Sum[((CatalanNumber[n])/(4^n)),{n,∞}]

(∑_(n=0)^∞)(((CatalanNumber[n]) (x^(2 n)))/((2 n)!))==(((Subscript[I, 1])(2 x))/x)

Sum[CatalanNumber[n]((x^(2n))/((2n)!)),{n,0,∞}]

(∑_k^n)(CatalanNumber[k])==-((2 (Binomial[2 (n+1), n+1]) (Hypergeometric2F1[n+(3/2), 1, n+3, 4])+(1+i (Sqrt[3])) (n+2))/(2 (n+2)))

Sum[CatalanNumber[k],{k,n}]

FullSimplify[%]

Accumulate[CatalanNumber[Range[10]]]

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

Sum[(2k)!/k!/(k+1)!,{k,1,n}]

FullSimplify[%]

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

Table[

Generating function

(1-sqrt(1-4x))/(2x(1-x))

GeneratingFunction[-(1/2)-((I (Sqrt[3]))/2)-Binomial[2 (1+n),1+n] Gamma[2+n] Hypergeometric2F1Regularized[(3/2)+n,1,3+n,4],n,x]

Sum[(-(1/2)-((I (Sqrt[3]))/2)-Binomial[2 (1+n),1+n] Gamma[2+n] Hypergeometric2F1Regularized[(3/2)+n,1,3+n,4])(x^n),{n,0,∞}]

Sum[(-(1/2)-((I (Sqrt[3]))/2)-Binomial[2 (1+n),1+n] Gamma[2+n] Hypergeometric2F1Regularized[(3/2)+n,1,3+n,4])(x^n),{n,0,10}]//Expand

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

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

Products

(1/((n+1)!))(∏_k^n)(4 k-2)==(CatalanNumber[n])

((Product[k,{k,2,4n-2,4}])/((n+1)!))

((Product[4k-2,{k,n}])/((n+1)!))

FullSimplify[(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) (1+n)!))-CatalanNumber[n]]

Recurrence

c(n+1)==((2 (2 n+1) c(n))/(n+2))

V5

RSolve[{c[n+1]==2(2n+1)/(n+2)c[n],c[1]==1},c[n],n]

Table[(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[2+n])),{n,10}]

V6

RSolve[{c[n+1]==2(2n+1)/(n+2)c[n],c[1]==1},c[n],n]

FullSimplify[(((4^(-1+n)) Pochhammer[(3/2),-1+n])/(Pochhammer[3,-1+n]))]

FullSimplify[(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[2+n]))-CatalanNumber[n]]

V7

RSolve[{c[n+1]==2(2n+1)/(n+2)c[n],c[1]==1},c[n],n]

V8

RSolve[{c[n+1]==2(2n+1)/(n+2)c[n],c[1]==1},c[n],n]//FullSimplify

FindLinearRecurrence[CatalanNumber/@Range[20]]

e[n] = Total[e[# + 1] e[n - #] & /@ Range[n - 2]]

Seegner

e[1]:=1
e[2]:=1
e[n_]:=e[n]=Total[e[#+1]e[n-#]&/@Range[n-2]]

e/@Range[10]

CatalanNumber/@Range[10]

Powers of 10

Limit

Limit[((Log[10,CatalanNumber[n]])/n),n->∞]

N[Log[10,4],20]

Enumeration

V5

Table[IntegerLength[CatalanNumber[10^n]],{n,0,7}]//Timing

Table[IntegerLength[CatalanNumber[10^n]],{n,0,8}]//Timing

V7

Table[IntegerLength[CatalanNumber[10^n]],{n,0,7}]//Timing

Table[IntegerLength[CatalanNumber[10^n]],{n,0,8}]//Timing

Series

V5

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

Table[1+Floor[expr],{n,0,20}]

V7

Series[CatalanNumber[x],{x,∞,3}]

Simplify[Normal[Series[Log[10,CatalanNumber[x]],{x,∞,2}]/.x->10^n],n∈Integers&&n>0]

s1=Table[1+Floor[(((4^(1-n)) (5^(-2 n))-9 (10^(-n))+(2^(4+n)) (5^n) Log[2]-12 n Log[10]-4 Log[π])/(8 Log[10]))],{n,0,20}]

Simplify[Normal[Series[Log[10,CatalanNumber[x]],{x,∞,3}]/.x->10^n],n∈Integers&&n>0]

s2=Table[1+Floor[-((-(2^(5-2 n)) (5^(-2 n))+9 (2^(3-n)) (5^(-n))+21 (10^(-3 n))-(2^(7+n)) (5^n) Log[2]+96 n Log[10]+32 Log[π])/(64 Log[10]))],{n,0,20}]

s1-s2

Large Values

V5

(10^6)

c6=With[{n=10^6},(((4^n) Gamma[(1/2)+n])/((Sqrt[π]) Gamma[2+n]))];//Timing

c62=With[{n=10^6},(4^n)((((2n-1)!!(Sqrt[π]))/(2^n))/((Sqrt[π])Gamma[n+2]))];//Timing

c6-c62

(10^8)

CatalanNumber[10^8]//Timing

With[{n=10^8},(((2n)!)/((n+1)!n!))]

With[{n=10^8},(((2^n)(2n-1)!!)/((n+1)!))]

V7

CatalanNumber[10^7];//Timing

CatalanNumber[10^8];//Timing

MaxMemoryUsed[]/10.^6

V8

$Version

{CatalanNumber[10^7];,MaxMemoryUsed[]/10.^6}//Timing

{CatalanNumber[10^8];,MaxMemoryUsed[]/10.^6}//Timing

$Version

{CatalanNumber[10^9];,MaxMemoryUsed[]/10.^6}//Timing

Primes

(Subscript[C, 2])=2 and (Subscript[C, 3])=5 are the only Catalan primes

Flatten[Position[CatalanNumber[Range[10^4]],_?PrimeQ]]//Timing

CatalanNumber/@{2,3}

10^4+Flatten[Position[CatalanNumber[Range[10^4+1,10^5]],_?PrimeQ]]//Timing

Odd

Position[CatalanNumber[Range[2000]],_?OddQ]//Flatten//Timing

Table[2^k-1,{k,10}]

CatalanNumber/@Table[2^k-1,{k,5}]

FullSimplify[(((2n)!)/((n+1)!n!))/.n->2^k-1,k∈Integers]

Timing[d=IntegerDigits[#,10,1]&/@CatalanNumber/@Table[2^k-1,{k,20}]//Flatten]

Timing[d=IntegerDigits[#,10,1]&/@CatalanNumber/@Table[2^k-1,{k,22}]//Flatten]

Position[IntegerDigits[2^Range[10^4]-1,5],_?(Complement[#,{0,1,2}]==={}&),1,Heads->False]//Flatten//Timing

Position[IntegerDigits[2^Range[10^5]-1,5],_?(Complement[#,{0,1,2}]==={}&),1,Heads->False]//Flatten//Timing

Takes ~23 GB

Lists

catalanLists[n_]:=Select[Flatten[Outer[List,Sequence@@Table[{-1,1},{2n}]],2n-1],Plus@@#==0&&PositiveSubsequencesQ[Drop[#,-1]]&]

PositiveSubsequencesQ[l_List]:=And@@Positive[Plus@@@NestList[Drop[#,-1]&,l,Length[l]]]

catalanLists[1]

catalanLists[2]

catalanLists[3]

catalanLists[4]

Length/@Table[catalanLists[n],{n,7}]

Nonegative Partial Sums

NonNegativePartialSumsQ[l_List]:=NonNegative/@(And@@FoldList[Plus,0,l])

Table[Select[Permutations[Flatten[Table[{-1,1},{n}]]],NonNegativePartialSumsQ],{n,4}]//ColumnForm

Table[Count[Permutations[Flatten[Table[{-1,1},{n}]]],_?NonNegativePartialSumsQ],{n,10}]//Timing