A052328 -id:A052328 - cp's OEIS frontend

A052329 Number of rooted trees with a forbidden limb of length 6.

1, 1, 2, 4, 9, 20, 47, 113, 281, 706, 1807, 4671, 12224, 32247, 85782, 229683, 618767, 1675618, 4559263, 12457483, 34168574, 94040433, 259637564, 718892281, 1995739380, 5553867981, 15490305017, 43293762352, 121235084565

Offset: 1

Christian G. Bower, Dec 15 1999

nonn

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.

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

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

Column k=6 of A255636.

with(numtheory):
g:= proc(n) g(n):= `if`(n=0, 1, add(add(d*(g(d-1)-
      `if`(d=6, 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, Jul 04 2014

g[n_] := g[n] = If[n == 0, 1, Sum[Sum[d*(g[d-1]-If[d == 6, 1, 0]), {d, Divisors[j]} ]*g[n-j], {j, 1, n}]/n]; a[n_] := g[n-1]; Table[a[n], {n, 1, 35}] (* Jean-François Alcover, Feb 24 2015, after Alois P. Heinz *)

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

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

A255636 Number A(n,k) of n-node rooted trees with a forbidden limb of length k; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 2, 0, 1, 1, 2, 3, 4, 0, 1, 1, 2, 4, 7, 8, 0, 1, 1, 2, 4, 8, 15, 17, 0, 1, 1, 2, 4, 9, 18, 35, 36, 0, 1, 1, 2, 4, 9, 19, 43, 81, 79, 0, 1, 1, 2, 4, 9, 20, 46, 102, 195, 175, 0, 1, 1, 2, 4, 9, 20, 47, 110, 251, 473, 395, 0

Offset: 1

Alois P. Heinz, Feb 28 2015

Any rootward k-node path starting at a leaf contains the root or a branching node.

			:    o      o        o      o    o       o      o    o
:  /(|)\    |       / \    /|\   |       |     / \   |
: o ooo o   o      o   o  o o o  o       o    o   o  o
:         /( )\   /|\    / \     |      / \   |      |
:        o o o o o o o  o   o    o     o   o  o      o
:                               /|\   / \    / \     |
:                              o o o o   o  o   o    o
: A(6,2) = 8                                        / \
:                                                  o   o
Square array A(n,k) begins:
  1,   1,   1,   1,   1,   1,   1,   1,   1,   1, ...
  0,   1,   1,   1,   1,   1,   1,   1,   1,   1, ...
  0,   1,   2,   2,   2,   2,   2,   2,   2,   2, ...
  0,   2,   3,   4,   4,   4,   4,   4,   4,   4, ...
  0,   4,   7,   8,   9,   9,   9,   9,   9,   9, ...
  0,   8,  15,  18,  19,  20,  20,  20,  20,  20, ...
  0,  17,  35,  43,  46,  47,  48,  48,  48,  48, ...
  0,  36,  81, 102, 110, 113, 114, 115, 115, 115, ...
  0,  79, 195, 251, 273, 281, 284, 285, 286, 286, ...
  0, 175, 473, 625, 684, 706, 714, 717, 718, 719, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened

Columns k=1-10 give: A063524, A002955, A052321, A052327, A052328, A052329, A255637, A255638, A255639, A255640.
Main diagonal gives A000081.
Cf. A255704.

with(numtheory):
g:= proc(n, k) option remember; `if`(n=0, 1, add(add(d*(g(d-1, k)-
      `if`(d=k, 1, 0)), d=divisors(j))*g(n-j, k), j=1..n)/n)
    end:
A:= (n, k)-> g(n-1, k):
seq(seq(A(n, 1+d-n), n=1..d), d=1..14);

g[n_, k_] := g[n, k] = If[n == 0, 1, Sum[Sum[d*(g[d - 1, k] - If[d == k, 1, 0]), {d, Divisors[j]}]*g[n - j, k], {j, 1, n}]/n]; A[n_, k_] := g[n - 1, k]; Table[Table[A[n, 1 + d - n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)

A002991 Number of n-node trees with a forbidden limb of length 5.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 5, 10, 21, 43, 97, 215, 503, 1187, 2876, 7033, 17510, 43961, 111664, 285809, 737632, 1915993, 5008652, 13163785, 34774873, 92282214, 245930746, 657931603, 1766481135, 4758553683, 12858286083, 34844908142, 94681272368

Offset: 0

N. J. A. Sloane

nonn

A tree with a forbidden limb of length k is a tree where the path from any leaf inward hits a branching node or another leaf within k steps. - Christian G. Bower, Dec 15 1999

A. J. Schwenk, Almost all trees are cospectral, pp. 275-307 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972.
Index entries for sequences related to trees

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

with(numtheory):
g:= proc(n) g(n):= `if`(n=0, 1, add(add(d*(g(d-1)-
      `if`(d=5, 1, 0)), d=divisors(j))*g(n-j), j=1..n)/n)
    end:
a:= n-> `if`(n=0, 1, g(n-1)+(`if`(irem(n, 2, 'r')=0,
         g(r-1), 0)-add(g(i-1)*g(n-i-1), i=1..n-1))/2):
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 06 2014

g[n_] := g[n] = If[n == 0, 1, Sum[Sum[d*(g[d-1]-If[d == 5, 1, 0]), {d, Divisors[j] }]*g[n-j], {j, 1, n}]/n]; a[n_] := If[n == 0, 1, g[n-1] + (If[Mod[n, 2 ] == 0, g[Quotient[n, 2]-1], 0] - Sum[g[i-1]*g[n-i-1], {i, 1, n-1}])/2]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 26 2015, after Alois P. Heinz *)

G.f.: 1 + B(x) + (B(x^2) - B(x)^2)/2 where B(x) is g.f. of A052328. - Christian G. Bower, Dec 15 1999

a(n) ~ c * d^n / n^(5/2), where d = 2.9447916575019743775137795109303..., c = 0.521642401804532770865780146005... . - Vaclav Kotesovec, Aug 25 2014

More terms from Christian G. Bower, Dec 15 1999

A002990 Number of n-node trees with a forbidden limb of length 4.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 5, 9, 19, 38, 86, 188, 439, 1026, 2472, 5997, 14835, 36964, 93246, 236922, 607111, 1565478, 4062797, 10599853, 27797420, 73224806, 193709710, 514406793, 1370937140, 3665714528, 9831891555, 26445886506, 71325268179

Offset: 0

N. J. A. Sloane

nonn

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

A. J. Schwenk, Almost all trees are cospectral, pp. 275-307 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972.
Index entries for sequences related to trees

Cf. A002955, A002988, A002989, A002990, A002991, A002992.
Cf. A052318, A052319, A052320.
Cf. A052321, A052322, A052323, A052324, A052325, A052326.
Cf. A052327, A052328, A052329.

with(numtheory):
g:= proc(n) g(n):= `if`(n=0, 1, add(add(d*(g(d-1)-
      `if`(d=4, 1, 0)), d=divisors(j))*g(n-j), j=1..n)/n)
    end:
a:= n-> `if`(n=0, 1, g(n-1)+(`if`(irem(n, 2, 'r')=0,
         g(r-1), 0)-add(g(i-1)*g(n-i-1), i=1..n-1))/2):
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 06 2014

g[n_] := g[n] = If[n == 0, 1, Sum[Sum[d*(g[d-1]-If[d == 4, 1, 0]), {d, Divisors[j] }]*g[n-j], {j, 1, n}]/n]; a[n_] := If[n == 0, 1, g[n-1] + (If[Mod[n, 2 ] == 0, g[Quotient[n, 2]-1], 0] - Sum[g[i-1]*g[n-i-1], {i, 1, n-1}])/2]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 26 2015, after Alois P. Heinz *)

G.f.: 1 + B(x) + (B(x^2) - B(x)^2)/2 where B(x) is g.f. of A052327.

a(n) ~ c * d^n / n^(5/2), where d = 2.9224691962496551739365155005926..., c = 0.503471518908815272581177797536... . - Vaclav Kotesovec, Aug 25 2014

More terms, formula and comments from Christian G. Bower, Dec 15 1999

cp's OEIS Frontend

A052329 Number of rooted trees with a forbidden limb of length 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A255636 Number A(n,k) of n-node rooted trees with a forbidden limb of length k; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A002991 Number of n-node trees with a forbidden limb of length 5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A002990 Number of n-node trees with a forbidden limb of length 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions