OFFSET
0,4
COMMENTS
What kind of trees are counted by this sequence (compare with A000081, A004111, A073075, and A115593)?
a(n) is the number of rooted trees of n vertices that have everywhere at most 2 siblings with the same (i.e., isomorphic) subtree below. The g.f. assembles a(n) as a root with child subtrees from among the smaller a(), but takes only 0, 1 or 2 copies of any one of them. Compare asymmetric trees A004111 g.f. which takes 0 or 1 copies. Here the x^(2*n) term allows a 2nd copy. The siblings condition is equivalent to the condition that the tree automorphisms form a 2-group, i.e., group order some power 2^k. 2 same siblings are a swap. 3 same siblings would be an element of order 3 and hence factor 3 in the group order. a(n) >= A213920 since the latter limits same size siblings, whereas here only limits same size plus structure. - Kevin Ryde, Jul 11 2019
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..2213
FORMULA
a(n) ~ c * d^n / n^(3/2), where d = 2.8458470164106425911151048..., c = 0.41694347809945986693376... . - Vaclav Kotesovec, Mar 17 2015
MAPLE
h:= proc(n, m, t) option remember; `if`(m=0, binomial(n+t, t),
`if`(n=0, 0, add(h(n-1, m-j, t+1), j=1..min(2, m))))
end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(b(n-i*j, i-1)*h(a(i), j, 0), j=0..n/i)))
end:
a:= n-> `if`(n<2, n, b(n-1$2)):
seq(a(n), n=0..35); # Alois P. Heinz, Sep 04 2018
MATHEMATICA
h[n_, m_, t_] := h[n, m, t] = If[m == 0, Binomial[n + t, t], If[n == 0, 0, Sum[h[n - 1, m - j, t + 1], {j, 1, Min[2, m]}]]];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i j, i - 1]* h[a[i], j, 0], {j, 0, n/i}]]];
a[n_] := If[n < 2, n, b[n - 1, n - 1]];
a /@ Range[0, 32] (* Jean-François Alcover, Oct 02 2019, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Joerg Arndt, Mar 04 2015
STATUS
approved