A288950
Number of relaxed compacted binary trees of right height at most one with empty initial and final sequence on level 0.
Original entry on oeis.org
1, 0, 1, 2, 15, 140, 1575, 20790, 315315, 5405400, 103378275, 2182430250, 50414138775, 1264936572900, 34258698849375, 996137551158750, 30951416768146875, 1023460181133390000, 35885072600989486875, 1329858572860198631250, 51938365373373313209375
Offset: 0
Denote by L the leaf and by o nodes. Every node has exactly two out-going edges or pointers. Internal edges are denoted by - or |. Pointers are omitted and may point to any node further right. The root is at level 0 at the very left.
The general structure is
L-o-o-o-o-o-o-o-o-o
| | | |
o o-o-o o-o o.
For n=0 the a(0)=1 solution is L.
For n=1 we have a(1)=0 because we need nodes on level 0 and level 1.
For n=2 the a(2)=1 solution is
L-o
|
o
and the pointers of the node on level 1 both point to the leaf.
For n=3 the a(3)=2 solutions have the structure
L-o
|
o-o
where the pointers of the last node have to point to the leaf, but the pointer of the next node has 2 choices: the leaf of the previous node.
Cf.
A001147 (relaxed compacted binary trees of right height at most one).
Cf.
A082161 (relaxed compacted binary trees of unbounded right height).
Cf.
A000032,
A000246,
A001879,
A051577,
A177145,
A213527,
A288950,
A288952,
A288953,
A288954 (subclasses of relaxed compacted binary trees of right height at most one, see the Wallner link).
-
terms = 21; (z + (1 - z)/3*(2 - z + (1 - 2z)^(-1/2)) + O[z]^terms // CoefficientList[#, z] &) Range[0, terms-1]! (* Jean-François Alcover, Dec 04 2018 *)
A288952
Number of relaxed compacted binary trees of right height at most one with empty sequences between branch nodes on level 0.
Original entry on oeis.org
1, 0, 1, 2, 15, 92, 835, 8322, 99169, 1325960, 19966329, 332259290, 6070777999, 120694673748, 2594992240555, 59986047422378, 1483663965460545, 39095051587497488, 1093394763005554801, 32347902448449172530, 1009325655965539561231, 33125674098690460236620
Offset: 0
- Muniru A Asiru, Table of n, a(n) for n = 0..100
- Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.
- Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017.
Cf.
A001147 (relaxed compacted binary trees of right height at most one).
Cf.
A082161 (relaxed compacted binary trees of unbounded right height).
-
a := [1,0];; for n in [3..10^2] do a[n] := (n-2)*a[n-1] + (n-2)^2*a[n-2]; od; a; # Muniru A Asiru, Jan 26 2018
-
a:=proc(n) option remember: if n=0 then 1 elif n=1 then 0 elif n>=2 then (n-1)*procname(n-1)-(n-1)^2*procname(n-2) fi; end:
seq(a(n),n=0..100); # Muniru A Asiru, Jan 26 2018
-
Fold[Append[#1, (#2 - 1) Last[#1] + #1[[#2 - 1]] (#2 - 1)^2] &, {1, 0}, Range[2, 21]] (* Michael De Vlieger, Jan 28 2018 *)
A288954
Number of relaxed compacted binary trees of right height at most one with minimal sequences between branch nodes except before the first and after the last branch node on level 0.
Original entry on oeis.org
1, 1, 3, 13, 79, 555, 4605, 42315, 436275, 4894155, 60125625, 794437875, 11325612375, 172141044075, 2793834368325, 48009995908875, 874143494098875, 16757439016192875, 338309837281040625, 7157757510792763875, 158706419654857449375, 3673441093896736036875
Offset: 2
Cf.
A288953 (variation without initial sequence).
Cf.
A177145 (variation without initial and final sequence).
Cf.
A001147 (relaxed compacted binary trees of right height at most one).
Cf.
A082161 (relaxed compacted binary trees of unbounded right height).
-
terms = 22; egf = 1/(3(1-z))(1/Sqrt[1-z^2] + (3z^3 - z^2 - 2z + 2)/((1-z)(1-z^2))) + O[z]^terms;
CoefficientList[egf, z] Range[0, terms-1]! (* Jean-François Alcover, Dec 13 2018 *)
A316666
Number of simple relaxed compacted binary trees of right height at most one with no sequences on level 1 and no final sequences on level 0.
Original entry on oeis.org
1, 0, 1, 3, 15, 87, 597, 4701, 41787, 413691, 4512993, 53779833, 695000919, 9680369943, 144560191149, 2303928046437, 39031251610227, 700394126116851, 13270625547477177, 264748979672169681, 5547121478845459983, 121784530649198053263, 2795749225338111831429, 66981491857058929294653
Offset: 0
- G. C. Greubel, Table of n, a(n) for n = 0..448
- Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.
- Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017.
-
m:=25; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( (3*Exp(-x) + x-2)/(1-x)^2 )); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Dec 12 2018
-
aseq := n-> 3*round((n+2)*n!/exp(1))-(n+2)*n!: bseq := n-> (n+2)*n!- 2* round((n+2)*n!/exp(1)): s := (a,b,n)-> a*aseq(n) + b*bseq( n): seq(s(1,0,n),n = 0..20); # Gary Detlefs, Dec 11 2018
-
terms = 24;
CoefficientList[(3E^-z+z-2)/(1-z)^2 + O[z]^terms, z] Range[0, terms-1]! (* Jean-François Alcover, Sep 14 2018 *)
-
Vec(serlaplace((3*exp(-x + O(x^25)) + x - 2)/(1 - x)^2)) \\ Andrew Howroyd, Jul 10 2018
Showing 1-4 of 4 results.
Comments