Weakly Binary Tree

Author

Eric W. Weisstein
September 26, 2007

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/WeaklyBinaryTree.nb.

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

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

Counts

Count[#,_?WeaklyBinaryTreeQ]&/@RootedTrees/@Range[11]//Timing

Count[#,_?WeaklyBinaryTreeQ]&/@RootedTrees/@Range[12]//Timing

Recurrence

g[0]:=0
g[1]:=1
g[2]:=1
g[3]:=1
g[n_]:=g[n]=Block[{j},
If[OddQ[n],
Total[Table[g[n-j]g[j],{j,(n-1)/2}]],
g[n/2](g[n/2]+1)/2+Total[Table[g[n-j]g[j],{j,n/2-1}]]]
]

g/@Range[12]

g[x_,n_:20]:=Polynomial[g/@Range[n,0,-1],x]

Expand[g[x]]

Enumeration

ShowGraphArray[
Flatten[
Map[Partition[#,11,11,{1,1},{}]&,
Select[#,WeaklyBinaryTreeQ]&/@RootedTrees/@Range[7],
{1}],1]]

Constants

ListPlot[Table[((g[n](n^(3/2)))/(2.4832535361^(n-1))),{n,1,500}],Joined->True]

With[{n=500},((g[n](n^(3/2)))/(2.4832535361^(n-1)))]

FindFit[Table[{n,g[n](n^(3/2))},{n,400,500}],η (ξ^(n-1)),{η,ξ},n,WorkingPrecision->100,MaxIterations->200]

x/.Block[{$RecursionLimit=2000},
FindRoot[g[1/x,1500]==1,{x,2.4,2.5},WorkingPrecision->20]
]

RSolve[{c[n]==c[n-1]^2+2,c[0]==0},c[n],n]

c[0]:=2
c[n_]:=c[n]=c[n-1]^2+2

c/@Range[5]

N[Table[c[n]^(2^(-n)),{n,4}],20]

N[Table[c[n]^(2^(-n)),{n,7,9}],110]

ξ=N[With[{n=8},c[n]^(2^(-n))],110];

1/2Sqrt[ξ/Pi]Sqrt[3+Plus@@(1/Rest[FoldList[Times,1,Array[c,#]]])]&/@{6,7,8}

η=1/2Sqrt[ξ/Pi]Sqrt[3+Plus@@(1/Rest[FoldList[Times,1,Array[c,7]]])]