A052325 Number of asymmetric rooted trees with a forbidden limb of length 3.

1, 1, 1, 1, 1, 2, 4, 8, 15, 30, 60, 122, 249, 513, 1061, 2210, 4620, 9708, 20472, 43337, 92023, 196018, 418653, 896485, 1924154, 4139014, 8921349, 19266067, 41679483, 90318082, 196020800, 426055601, 927317334, 2020949226, 4409764169

Offset

1,6

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.

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(WEIGH(a-b)) where b(3)=1, b(k)=0 if k != 3.

a(n) ~ c * d^n / n^(3/2), where d = 2.27671458388797627098091744865..., c = 0.2935911773459468433271794078... . - Vaclav Kotesovec, Aug 25 2014

Maple

b:= proc(n, i) option remember;
      `if`(n=0, 1, `if`(i<1, 0, add(binomial(a(i)-
      `if`(i=3, 1, 0), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<1, 1, b(n-1, n-1)):
seq(a(n), n=1..50);  # Alois P. Heinz, Jul 06 2014

Mathematica

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[a[i]- If[i==3, 1, 0], j]*b[n-i*j, i-1], {j, 0, n/i}]]];
a[n_] := If[n<1, 1, b[n-1, n-1]];
Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Mar 01 2016, after Alois P. Heinz *)

Crossrefs

Cf. A002955, A002988-A002992, A052318-A052329.

Sequence in context: A251750 A251764 A191497 * A302774 A300520 A243082

Adjacent sequences: A052322 A052323 A052324 * A052326 A052327 A052328

Keyword

nonn,eigen

Author

Christian G. Bower, Dec 15 1999

Status

approved