A255636 -id:A255636 - cp's OEIS frontend

A002955 Number of (unordered, unlabeled) rooted trimmed trees with n nodes.

1, 1, 1, 2, 4, 8, 17, 36, 79, 175, 395, 899, 2074, 4818, 11291, 26626, 63184, 150691, 361141, 869057, 2099386, 5088769, 12373721, 30173307, 73771453, 180800699, 444101658, 1093104961, 2695730992, 6659914175, 16481146479, 40849449618

Offset: 1

N. J. A. Sloane

A rooted trimmed tree is a tree without limbs of length >= 2. Limbs are the paths from the leafs (towards the root) to the nearest branching point (with the root considered to be a branching point). [clarified by Joerg Arndt, Mar 03 2015]
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.
Also counts the unordered rooted trees without "x x" in the level sequence for the pre-order walk. The bijection transforms the two outmost nodes in all limbs of lengths >= 2 into V-shaped subtrees. - Joerg Arndt, Mar 03 2015

K. L. McAvaney, personal communication.
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 = 1..1000 (terms n = 1..300 from Vincenzo Librandi)
F. Goebel and R. P. Nederpelt, The number of numerical outcomes of iterated powers, Amer. Math. Monthly, 80 (1971), 1097-1103.
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis (annotated cached copy)
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A002988-A002992, A052318-A052329.

Column k=2 of A255636.

with(numtheory): a:= proc(n) option remember; local d,j,aa; aa:= n-> a(n)-`if`(n=2,1,0); if n<=1 then n else (add(d*aa(d), d=divisors(n-1)) +add(add(d*aa(d), d=divisors(j)) *a(n-j), j=1..n-2))/ (n-1) fi end: seq(a(n), n=1..32); # Alois P. Heinz, Sep 06 2008

a[n_] := a[n] = (Total[ #*b[#]& /@ Divisors[n-1] ] + Sum[ Total[ #*b[#]& /@ Divisors[j] ]*a[n-j], {j, 1, n-2}]) / (n-1); a[1] = 1; b[n_] := a[n]; b[2] = 0; Table[ a[n], {n, 1, 32}](* Jean-François Alcover, Nov 18 2011, after Maple *)

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

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

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

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

Original entry on oeis.org

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

A255704 Number T(n,k) of n-node rooted trees in which the maximal number of nodes in paths starting at a leaf and ending at the first branching node or at the root equals k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 1, 1, 0, 4, 3, 1, 1, 0, 8, 7, 3, 1, 1, 0, 17, 18, 8, 3, 1, 1, 0, 36, 45, 21, 8, 3, 1, 1, 0, 79, 116, 56, 22, 8, 3, 1, 1, 0, 175, 298, 152, 59, 22, 8, 3, 1, 1, 0, 395, 776, 413, 163, 60, 22, 8, 3, 1, 1, 0, 899, 2025, 1131, 450, 166, 60, 22, 8, 3, 1, 1

Offset: 1

Alois P. Heinz, Mar 02 2015

			:    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   o
:                       |       |     |   |  / \
:                       o       o     o   o o   o
:                                           |
: T(6,3) = 7                                o
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   1,   1;
  0,   2,   1,   1;
  0,   4,   3,   1,  1;
  0,   8,   7,   3,  1,  1;
  0,  17,  18,   8,  3,  1, 1;
  0,  36,  45,  21,  8,  3, 1, 1;
  0,  79, 116,  56, 22,  8, 3, 1, 1;
  0, 175, 298, 152, 59, 22, 8, 3, 1, 1;

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

Columns k=1-10 give: A063524, A002955 (for n>1), A318899, A318900, A318901, A318902, A318903, A318904, A318905, A318906.
Row sums give A000081.
T(2*n+1,n+1) gives A255705.
Cf. A255636.

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:
T:= (n, k)-> g(n-1, k) -`if`(k=1, 0, g(n-1, k-1)):
seq(seq(T(n, k), k=1..n), n=1..14);

g[n_, k_] := g[n, k] = If[n == 0, 1, Sum[DivisorSum[j, #*(g[#-1, k] - If[# == k, 1, 0])&] * g[n-j, k], {j, 1, n}]/n];
T[n_, k_] := g[n-1, k] - If[k == 1, 0, g[n-1, k-1]];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 24 2017, translated from Maple *)

T(n,1) = A255636(n,1), T(n,k) = A255636(n,k) - A255636(n,k-1) for k>1.

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

Original entry on oeis.org

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

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.
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

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, A003006 (first 10 terms match), A052318-A052329.

Column k=3 of A255636.

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

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

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

A052328 Number of rooted trees with a forbidden limb of length 5.

Original entry on oeis.org

1, 1, 2, 4, 9, 19, 46, 110, 273, 684, 1747, 4505, 11763, 30956, 82153, 219437, 589747, 1593170, 4324445, 11787195, 32251520, 88548011, 243877256, 673605521, 1865445693, 5178574184, 14408195935, 40170674295, 112213616851

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-A052329.

Column k=5 of A255636.

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-> 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==5, 1, 0]), {d, Divisors[j]}] g[n-j], {j, 1, n}]/n];
a[n_] := g[n-1];
Array[a, 35] (* Jean-François Alcover, Dec 18 2020, after Alois P. Heinz *)

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

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

A255705 Number of 2n+1-node rooted trees in which the maximal number of nodes in paths starting at a leaf and ending at the first branching node or at the root equals n+1.

Original entry on oeis.org

1, 1, 3, 8, 22, 60, 167, 465, 1306, 3681, 10422, 29597, 84313, 240757, 689035, 1975753, 5675145, 16326198, 47032200, 135658367, 391733593, 1132357784, 3276330780, 9487885056, 27497891241, 79753806451, 231474005120, 672250119756, 1953523496677, 5680002466125

Offset: 0

Alois P. Heinz, Mar 02 2015

nonn

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

Cf. A255636, A255704, A318754, A318758.

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:= a-> g(2*n, n+1) -`if`(n=0, 0, g(2*n, n)):
seq(a(n), n=0..40);

g[n_, k_] := g[n, k] = If[n == 0, 1, Sum[DivisorSum[j, #*(g[# - 1, k] - If[# == k, 1, 0]) &]*g[n - j, k], {j, 1, n}]/n];
a[n_] :=  g[2n, n+1] - If[n == 0, 0, g[2n, n]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 24 2017, translated from Maple *)

a(n) = A255704(2*n+1,n+1).
a(n) ~ c * d^n / sqrt(n), where d = A051491 = 2.955765285651994974714817524... and c = 0.70755335886284109851526791506579... . - Vaclav Kotesovec, Feb 28 2016
a(n) = A318754(2n+2,n+1) = A318758(2n+2,n+1). - Alois P. Heinz, Sep 02 2018

A052327 Number of rooted trees with a forbidden limb of length 4.

Original entry on oeis.org

1, 1, 2, 4, 8, 18, 43, 102, 251, 625, 1584, 4055, 10509, 27451, 72307, 191697, 511335, 1370995, 3693452, 9991671, 27133149, 73934800, 202096673, 553999573, 1522651908, 4195087022, 11583820212, 32052475655, 88860186023

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-A052329.

Column k=4 of A255636.

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-> g(n-1):
seq(a(n), n=1..35);  # Alois P. Heinz, Jul 04 2014

g[n_] := g[n] = If[n == 0, 1, Sum[DivisorSum[j, #*(g[# - 1] - If[# == 4, 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 *)

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

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

A255637 Number of n-node rooted trees with a forbidden limb of length 7.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 48, 114, 284, 714, 1829, 4731, 12391, 32711, 87084, 233349, 629137, 1705039, 4642999, 12696374, 34851662, 95997401, 265253845, 735035099, 2042203194, 5687771773, 15876641362, 44409566681, 124460776515, 349437246152, 982732274507

Offset: 1

Alois P. Heinz, Feb 28 2015

nonn

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

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

Column k=7 of A255636.

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-> g(n-1, 7):
seq(a(n), n=1..40);

a(n) ~ c * d^n / n^(3/2), where d = 2.954528470057707474794966340476752099204837575... and c = 0.43932847920704393138249966062251759371... . - Vaclav Kotesovec, Feb 28 2016

A255638 Number of n-node rooted trees with a forbidden limb of length 8.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 48, 115, 285, 717, 1837, 4753, 12451, 32878, 87549, 234654, 632814, 1715446, 4672544, 12780511, 35091842, 96684570, 267223650, 740691451, 2058470490, 5734620428, 16011730686, 44799543203, 125587727914, 352696990890, 992169406959

Offset: 1

Alois P. Heinz, Feb 28 2015

nonn

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

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

Column k=8 of A255636.

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-> g(n-1, 8):
seq(a(n), n=1..40);

a(n) ~ c * d^n / n^(3/2), where d = 2.95534758805897943282870965508636011438518881375... and c = 0.43969195292137654501555629074396535899093... . - Vaclav Kotesovec, Feb 28 2016

A255639 Number of n-node rooted trees with a forbidden limb of length 9.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 48, 115, 286, 718, 1840, 4761, 12473, 32938, 87716, 235119, 634120, 1719126, 4682962, 12810093, 35176103, 96925151, 267912108, 742665338, 2064139687, 5750927832, 16058703976, 44935017987, 125978892299, 353827590946, 995440328858

Offset: 1

Alois P. Heinz, Feb 28 2015

nonn

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

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

Column k=9 of A255636.

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

a(n) ~ c * d^n / n^(3/2), where d = 2.95562406748808419554567595195333686205085952464972655... and c = 0.439835068532467809288350528155403598039874... . - Vaclav Kotesovec, Feb 28 2016

cp's OEIS Frontend

A002955 Number of (unordered, unlabeled) rooted trimmed trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A255704 Number T(n,k) of n-node rooted trees in which the maximal number of nodes in paths starting at a leaf and ending at the first branching node or at the root equals k; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A052328 Number of rooted trees with a forbidden limb of length 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A255705 Number of 2n+1-node rooted trees in which the maximal number of nodes in paths starting at a leaf and ending at the first branching node or at the root equals n+1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A052327 Number of rooted trees with a forbidden limb of length 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A255637 Number of n-node rooted trees with a forbidden limb of length 7.