A052318 -id:A052318 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

Christian G. Bower, Dec 15 1999

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.

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

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

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

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

A052320 Number of labeled trimmed trees with n nodes.

Original entry on oeis.org

1, 1, 1, 0, 4, 5, 96, 1057, 14848, 235881, 4234240, 84815621, 1877090304, 45524670061, 1201345331200, 34283233751145, 1052350187831296, 34582597023733073, 1211614017182760960, 45088964565749965837

Offset: 0

Christian G. Bower, Dec 15 1999

nonn

A trimmed tree is a tree with a forbidden limb of length 2.

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.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for sequences related to trees

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

CoefficientList[Series[1+x^3/2+x^4/2-LambertW[-x/E^(x^2)]-(LambertW[-x/E^(x^2)])^2/2, {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Mar 29 2014 *)

E.g.f.: 1 + x^3/2 + x^4/2 + B(x) - B(x)^2/2 where B(x) is e.g.f. of A052318.

a(n) ~ (1+LambertW(-2*exp(-2)))^(3/2) * exp((n*LambertW(-2*exp(-2)))/2) * n^(n-2). - Vaclav Kotesovec, Mar 29 2014

A052323 Number of labeled trees with a forbidden limb of length 3.

Original entry on oeis.org

1, 1, 1, 3, 4, 65, 576, 5887, 92464, 1680345, 34041520, 774906011, 19537590744, 540890740117, 16321259150392, 533305854910935, 18764822871806176, 707498057530634033, 28460428902580264416, 1216828054782241792435

Offset: 0

Christian G. Bower, Dec 15 1999

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.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for sequences related to trees

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

CoefficientList[Series[1+x^4/2+x^5/2+x^6/2-LambertW[-x*E^(-x^3)]-(LambertW[-x*E^(-x^3)])^2/2, {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Mar 29 2014 *)

E.g.f.: 1+x^4/2+x^5/2+x^6/2+B(x)-B(x)^2/2 where B(x) is e.g.f. of A052322.

a(n) ~ (1+LambertW(-3*exp(-3)))^(3/2) * exp(n/3*LambertW(-3*exp(-3))) * n^(n-2). - Vaclav Kotesovec, Mar 29 2014

A052326 Number of asymmetric trees with a forbidden limb of length 3.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 6, 11, 25, 49, 105, 211, 444, 903, 1880, 3865, 8042, 16658, 34764, 72484, 151856, 318418, 669934, 1411637, 2982407, 6311760, 13387127, 28442458, 60543586, 129084965, 275683061, 589660911, 1263128375

Offset: 0

Christian G. Bower, Dec 15 1999

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.

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
Index entries for sequences related to Lyndon words

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

G.f.: 1 + B(x) + x^4 + x^5 + x^6 - (B(x^2) + B(x)^2)/2 where B(x) is g.f. of A052325.

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

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

Typo in cross-reference corrected by Vaclav Kotesovec, Aug 25 2014

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

A284417 Triangular array read by rows. T(n,k) is the number of rooted labeled trees on n nodes with exactly k vertices whose unique descendent is a leaf, n >= 1, 0 <= k <= floor((n-1)/2) + delta_{2,n}.

Original entry on oeis.org

1, 0, 2, 3, 6, 16, 48, 145, 420, 60, 1536, 4800, 1440, 19579, 65730, 31500, 840, 290816, 1053696, 698880, 53760, 4942305, 19332936, 16367400, 2388960, 15120, 94689280, 399052800, 410296320, 93542400, 2419200, 2020278931, 9146127870, 11044008360, 3526261200, 200415600, 332640, 47523053568, 230339788800, 319018106880, 133013422080, 12986265600, 127733760

Offset: 1

Geoffrey Critzer, Mar 26 2017

Column k=0 is A052318(n) for n>2.

Row sums = n^(n-1) = A000169(n).

			Triangle begins
       1,
       0,       2,
       3,       6,
      16,      48,
     145,     420,     60,
    1536,    4800,   1440,
   19579,   65730,  31500,   840,
  290816, 1053696, 698880, 53760,
  ...
T(3,1)=6 because there are 6 labeled rooted trees (paths) o-o-o and these 6 trees have 1 vertex whose only descendent is a leaf. T(3,0) = 3 because there are 3 labeled trees of the form
    o
   / \
  o   o
and these 3 trees have no such vertices.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 183.

Cf. A055302.

nn = 10; Range[0, nn]! CoefficientList[Series[-z^2 + u z^2 - ProductLog[-E^((-1 + u) z^2) z], {z, 0, nn}], {z, u}] // Grid

E.g.f. satisfies: A(x,y) = x exp(A(x,y)) - x^2 + y x^2.

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

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

A052320 Number of labeled trimmed trees with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A052323 Number of labeled trees with a forbidden limb of length 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A052326 Number of asymmetric trees with a forbidden limb of length 3.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A284417 Triangular array read by rows. T(n,k) is the number of rooted labeled trees on n nodes with exactly k vertices whose unique descendent is a leaf, n >= 1, 0 <= k <= floor((n-1)/2) + delta_{2,n}.

Views