A309352 -id:A309352 - cp's OEIS frontend

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

Joerg Arndt, Mar 04 2015

nonn

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

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

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

Column k=2 of A318757.

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

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 *)

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula