A222006 Number of forests of rooted plane binary trees (all nodes have outdegree of 0 or 2) with n total nodes.

1, 1, 1, 2, 2, 4, 5, 10, 12, 27, 35, 79, 104, 244, 331, 789, 1083, 2615, 3652, 8880, 12523, 30657, 43661, 107326, 153985, 379945, 548776, 1357922, 1972153, 4892140, 7139850, 17747863, 26011843, 64776658, 95296413, 237689691, 350844814, 876313458, 1297367201, 3244521203, 4816399289

Offset

0,4

Comments

Here, the binary trees are sized by total number of nodes.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

O.g.f.: Product_{i>=1} 1/(1 - x^i)^A126120(i-1).

a(n) ~ c * 2^n / n^(3/2), where c = 1.165663931402962361339366557... if n is even, c = 1.490999501305559555120304528... if n is odd. - Vaclav Kotesovec, Aug 31 2014

Example

a(6) = 5: There is one forest with 6 trees, one forest with 4 trees and 3 forests with 2 trees, namely
1)...o..o..o..o..o..o...............
....................................
2)...o..o..o....o...................
.............../.\..................
..............o...o.................
....................................
3)...o........o.....................
..../.\....../.\....................
...o...o....o...o...................
....................................
4).....o....o.....5)......o.....o...
....../.\................/.\........
.....o...o..............o...o.......
..../.\..................../.\......
...o...o..................o...o.....

Maple

b:= proc(n) option remember; `if`(irem(n, 2)=0, 0,
      `if`(n<2, n, add(b(i)*b(n-1-i), i=1..n-2)))
    end:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(g(n-i*j, i-2)*binomial(b(i)+j-1, j), j=0..n/i)))
    end:
a:= n-> g(n, iquo(n-1, 2)*2+1):
seq(a(n), n=0..50);  # Alois P. Heinz, Feb 26 2013

Mathematica

nn=40; a=Drop[CoefficientList[Series[t=(1-(1-4x^2)^(1/2))/(2x), {x, 0, nn}], x], 1]; CoefficientList[Series[Product[1/(1-x^i)^a[[i]], {i, 1, nn-1}], {x, 0, nn}], x]

Crossrefs

Row sums of A342770.

Sequence in context: A091188 A147678 A195865 * A127712 A305840 A178113

Adjacent sequences: A222003 A222004 A222005 * A222007 A222008 A222009

Keyword

nonn

Author

Geoffrey Critzer, Feb 23 2013

Status

approved