A248869 Satisfies Sum_{n>=0} a(n)*x^n = x * Product_{n>=0} (1 + x^n + x^(2*n))^a(n).

0, 1, 1, 2, 3, 7, 15, 34, 79, 190, 459, 1136, 2833, 7154, 18206, 46723, 120656, 313514, 818763, 2148434, 5660790, 14972103, 39734107, 105779291, 282403830, 755921733, 2028277115, 5454368549, 14697955778, 39682793675, 107330573239, 290783511134, 789032648219

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

a(n) = A004111(n) + A318859(n). - Kevin Ryde, Jul 11 2019

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

Cf. A000081, A004111, A073075, A115593, A213920, A248870, A309352.

Column k=2 of A318757.

Sequence in context: A198683 A001932 A213920 * A005909 A003006 A052321

Adjacent sequences: A248866 A248867 A248868 * A248870 A248871 A248872

Keyword

nonn

Author

Joerg Arndt, Mar 04 2015

Status

approved