A052321 Number of rooted trees with a forbidden limb of length 3.

1, 1, 2, 3, 7, 15, 35, 81, 195, 473, 1171, 2924, 7396, 18848, 48446, 125311, 326145, 853188, 2242616, 5919197, 15683008, 41694334, 111195166, 297393668, 797475499, 2143631474, 5775002574, 15590201095, 42168292074, 114260967888, 310124721255, 843053354234

Offset

1,3

Comments

A rooted tree with a forbidden limb of length k is a rooted tree where the path from any leaf inward hits a branching node or the root within k steps.

Likely a duplicate of A003006. - R. J. Mathar, Mar 23 2012

Only first 10 terms match, but then a(11) = 1171, and A003006(11) = 1170. - Vladimir Reshetnikov, Mar 05 2019

Links

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

N. J. A. Sloane, Transforms

Index entries for sequences related to rooted trees

Formula

a(n) satisfies a = SHIFT_RIGHT(EULER(a-b)) where b(3)=1, b(k)=0 if k != 3.

a(n) ~ c * d^n / n^(3/2), where d = 2.851157026715821487965080545784048..., c = 0.4192933669718878505916053142459... . - Vaclav Kotesovec, Aug 24 2014

Maple

with(numtheory):
g:= proc(n) g(n):= `if`(n=0, 1, add(add(d*(g(d-1)-
      `if`(d=3, 1, 0)), d=divisors(j))*g(n-j), j=1..n)/n)
    end:
a:= n-> g(n-1):
seq(a(n), n=1..35);  # Alois P. Heinz, Jun 26 2014

Mathematica

g[n_] := g[n] = If[n==0, 1, Sum[DivisorSum[j, #*(g[#-1] - If[#==3, 1, 0])&] * g[n-j], {j, 1, n}]/n];
a[n_] := g[n-1];
Table[a[n], {n, 1, 35}] (* Jean-François Alcover, Apr 04 2017, after Alois P. Heinz *)

Crossrefs

Cf. A002955, A002988-A002992, A003006 (first 10 terms match), A052318-A052329.

Column k=3 of A255636.

Sequence in context: A248869 A005909 A003006 * A114584 A328779 A039826

Adjacent sequences: A052318 A052319 A052320 * A052322 A052323 A052324

Keyword

nonn

Author

Christian G. Bower, Dec 15 1999

Status

approved