A339067 -id:A339067 - cp's OEIS frontend

A000107 Number of rooted trees with n nodes and a single labeled node; pointed rooted trees; vertebrates.

0, 1, 2, 5, 13, 35, 95, 262, 727, 2033, 5714, 16136, 45733, 130046, 370803, 1059838, 3035591, 8710736, 25036934, 72069134, 207727501, 599461094, 1731818878, 5008149658, 14496034714, 41993925955, 121747732406, 353221737526, 1025471857282, 2978995353959, 8658997820084

Offset: 0

N. J. A. Sloane

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 61, 62 (2.1.8-2.1.10).
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 134.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 (first 201 terms from T. D. Noe)
Bernhard Gittenberger, Emma Yu Jin, Michael Wallner, On the shape of random Pólya structures, arXiv|1707.02144 [math.CO], 2017-2018; Discrete Math., 341 (2018), 896-911.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
R. Harary, R. W. Robinson, Isomorphic factorizations VIII: bisectable trees, Combinatorica 4 (2) (1984) 169-179, eq. (4.12).
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 123
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Table 6.
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Row sums of A339067.
INVERT transform of A000081.
Column k=1 of A008295.

with(numtheory): b:= proc(n) option remember; `if`(n<2, n, add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1) /(n-1)) end: a:= proc(n) option remember; b(n) +add(a(n-i) *b(i), i=1..n-1) end: seq(a(n), n=0..26); # Alois P. Heinz, Jun 02 2009

b[0] = 0; b[1] = 1; b[n_] := b[n] = Sum[ Sum[ d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}]/(n-1); a[n_] := a[n] = b[n] + Sum[ a[n-i]*b[i], {i, 1, n-1}]; Table[ a[n], {n, 0, 26}](* Jean-François Alcover, Mar 07 2012, after Alois P. Heinz *)

G.f.: A000081(x)/(1-A000081(x)), where A000081(x) is the g.f. of A000081 [Harary-Robinson]. - R. J. Mathar, Sep 16 2015

a(n) ~ A340310 * A051491^n / sqrt(n). - Vaclav Kotesovec, Jan 04 2021

Better description from Christian G. Bower, Apr 15 1998

A339428 Triangle read by rows: T(n,k) is the number of connected functions on n points with a loop of length k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 6, 3, 1, 1, 20, 16, 9, 4, 1, 1, 48, 37, 23, 11, 4, 1, 1, 115, 96, 62, 35, 14, 5, 1, 1, 286, 239, 169, 97, 46, 18, 5, 1, 1, 719, 622, 451, 282, 145, 63, 21, 6, 1, 1, 1842, 1607, 1217, 792, 440, 206, 80, 25, 6, 1, 1

Offset: 1

Andrew Howroyd, Dec 03 2020

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    4,   3,   1,   1;
    9,   6,   3,   1,   1;
   20,  16,   9,   4,   1,  1;
   48,  37,  23,  11,   4,  1,  1;
  115,  96,  62,  35,  14,  5,  1, 1;
  286, 239, 169,  97,  46, 18,  5, 1, 1;
  719, 622, 451, 282, 145, 63, 21, 6, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Columns 1..12 are A000081, A027852, A029852, A029853, A029868, A029869, A029870, A029871, A032205, A032206, A032207, A032208.
Row sums are A002861.
Cf. A033185, A217781, A339067.

\\ TreeGf is A000081 as g.f.
TreeGf(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
ColSeq(n,k)={my(r=TreeGf(max(0,n+1-k))); Vec(sumdiv(k, d, eulerphi(d)*subst(r + O(x*x^(n\d)), x, x^d)^(k/d))/k, -n)}
M(n, m=n)=Mat(vector(m, k, ColSeq(n,k)~))
{ my(T=M(12)); for(n=1, #T~, print(T[n,1..n])) }

G.f. of k-th column: (1/k)*Sum_{d|k} phi(d) * r(x^d)^(k/d) where r(x) is the g.f. of A000081.

A000106 2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees.

Original entry on oeis.org

1, 2, 5, 12, 30, 74, 188, 478, 1235, 3214, 8450, 22370, 59676, 160140, 432237, 1172436, 3194870, 8741442, 24007045, 66154654, 182864692, 506909562, 1408854940, 3925075510, 10959698606, 30665337738, 85967279447, 241433975446, 679192039401, 1913681367936, 5399924120339

Offset: 2

N. J. A. Sloane

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 2..1000 (terms n = 2..200 from T. D. Noe)
Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 385
Index entries for sequences related to rooted trees

Column d=1 of A335362.
Column 2 of A339067.
Cf. A000081, A000242, A000300, A000343, A000395, A027852 (forests of 2 rooted trees).

a000106 n = a000106_list !! (n-2)
a000106_list = drop 2 $ conv a000081_list [] where
   conv (v:vs) ws = (sum $ zipWith (*) ws' $ reverse ws') : conv vs ws'
                    where ws' = v : ws
-- Reinhard Zumkeller, Jun 17 2013

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-1)^2, x=0, n+1), x,n): seq(a(n), n=2..35); # Alois P. Heinz, Aug 21 2008

<Jean-François Alcover, Nov 02 2011 *)
b[n_] := b[n] = If[n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[b[n+1-j*k], {j, 1, Quotient[n, k]}]; B[n_] := B[n] = Sum[b[k]*x^k, {k, 1, n}]; a[n_] := SeriesCoefficient[B[n-1]^2, {x, 0, n}]; Table[a[n], {n, 2, 35}] (* Jean-François Alcover, Dec 01 2016, after Alois P. Heinz *)

Self-convolution of rooted trees A000081.
a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.87984802514205060808180678... . - Vaclav Kotesovec, Sep 11 2014
In the asymptotics above the constant c = 2 * A187770. - Vladimir Reshetnikov, Aug 13 2016

More terms from Christian G. Bower, Nov 15 1999

A000242 3rd power of rooted tree enumerator; number of linear forests of 3 rooted trees.

Original entry on oeis.org

1, 3, 9, 25, 69, 186, 503, 1353, 3651, 9865, 26748, 72729, 198447, 543159, 1491402, 4107152, 11342826, 31408719, 87189987, 242603970, 676524372, 1890436117, 5292722721, 14845095153, 41708679697, 117372283086, 330795842217

Offset: 3

N. J. A. Sloane

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Column 3 of A339067.

Cf. A000081, A000106, A000300, A000343, A000395.

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-2)^3, x=0, n+1), x,n): seq(a(n), n=3..29); # Alois P. Heinz, Aug 21 2008

max = 29; b[n_] := b[n] = If[n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[ b[n+1-j*k], {j, 1, Quotient[n, k]}]; f[x_] := Sum[ b[k]*x^k, {k, 0, max}]; Drop[ CoefficientList[ Series[f[x]^3, {x, 0, max}], x], 3] (* Jean-François Alcover, Oct 25 2011, after Alois P. Heinz *)

G.f.: B(x)^3 where B(x) is g.f. of A000081.

a(n) ~ 3 * A187770 * A051491^n / n^(3/2). - Vaclav Kotesovec, Jan 03 2021

More terms from Christian G. Bower, Nov 15 1999

A000300 4th power of rooted tree enumerator: linear forests of 4 rooted trees.

Original entry on oeis.org

1, 4, 14, 44, 133, 388, 1116, 3168, 8938, 25100, 70334, 196824, 550656, 1540832, 4314190, 12089368, 33911543, 95228760, 267727154, 753579420, 2123637318, 5991571428, 16923929406, 47857425416, 135478757308, 383929643780, 1089118243128, 3092612497260

Offset: 4

N. J. A. Sloane

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 4..500
Index entries for sequences related to rooted trees

Column 4 of A339067.

Cf. A000081, A000106, A000242, A000343, A000395.

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-3)^4, x=0, n+1), x,n): seq(a(n), n=4..30); # Alois P. Heinz, Aug 21 2008

b[n_] := b[n] = If[ n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[ b[n + 1 - j*k], {j, 1, n/k}]; bb[n_] := bb[n] = Sum[b[k]*x^k, {k, 1, n}]; a[n_] := Coefficient[ Series[ bb[n - 3]^4, {x, 0, n + 1}], x, n]; Table[a[n], {n, 4, 31}] (* Jean-François Alcover, Jan 25 2013, translated from Alois P. Heinz's Maple program *)

G.f.: B(x)^4 where B(x) is g.f. of A000081.

a(n) ~ 4 * A187770 * A051491^n / n^(3/2). - Vaclav Kotesovec, Jan 03 2021

More terms from Christian G. Bower, Nov 15 1999

A000343 5th power of rooted tree enumerator; number of linear forests of 5 rooted trees.

Original entry on oeis.org

1, 5, 20, 70, 230, 721, 2200, 6575, 19385, 56575, 163952, 472645, 1357550, 3888820, 11119325, 31753269, 90603650, 258401245, 736796675, 2100818555, 5990757124, 17087376630, 48753542665, 139155765455, 397356692275, 1135163887190, 3244482184720, 9277856948255

Offset: 5

N. J. A. Sloane

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 5..750
Index entries for sequences related to rooted trees

Column 5 of A339067.

Cf. A000081, A000106, A000242, A000300, A000395.

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-4)^5, x=0, n+1), x,n): seq(a(n), n=5..29); # Alois P. Heinz, Aug 21 2008

b[n_] := b[n] = If[n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[b[n+1-j*k], {j, 1, Quotient[n, k]}]; B[n_] := B[n] = Sum[b[k]*x^k, {k, 1, n}]; a[n_] := Coefficient[Series[B[n-4]^5, {x, 0, n+1}], x, n]; Table[a[n], {n, 5, 32}] (* Jean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

G.f.: B(x)^5 where B(x) is g.f. of A000081.

a(n) ~ 5 * A187770 * A051491^n / n^(3/2). - Vaclav Kotesovec, Jan 03 2021

More terms from Christian G. Bower, Nov 15 1999

A000395 6th power of rooted tree enumerator; number of linear forests of 6 rooted trees.

Original entry on oeis.org

1, 6, 27, 104, 369, 1236, 3989, 12522, 38535, 116808, 350064, 1039896, 3068145, 9004182, 26314773, 76652582, 222705603, 645731148, 1869303857, 5404655358, 15611296146, 45060069406, 129989169909, 374843799786, 1080624405287

Offset: 6

N. J. A. Sloane

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 6..1000
Index entries for sequences related to rooted trees

Column 6 of A339067.

Cf. A000081, A000106, A000242, A000300, A000343.

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-5)^6, x=0, n+1), x,n): seq(a(n), n=6..30);  # Alois P. Heinz, Aug 21 2008

b[n_] := b[n] = If[n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[b[n+1-j*k], {j, 1, Quotient[n, k]}]; B[n_] := B[n] = Sum[b[k]*x^k, {k, 1, n}]; a[n_] := SeriesCoefficient[B[n-5]^6, {x, 0, n}]; Table[a[n], {n, 6, 30}] (* Jean-François Alcover, Oct 13 2014, after Alois P. Heinz *)

G.f.: B(x)^6 where B(x) is g.f. of A000081.

a(n) ~ 6 * A187770 * A051491^n / n^(3/2). - Vaclav Kotesovec, Jan 03 2021

More terms from Christian G. Bower, Nov 15 1999

A339303 Triangle read by rows: T(n,k) is the number of unoriented linear forests with n nodes and k rooted trees.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 3, 2, 1, 9, 6, 6, 2, 1, 20, 16, 15, 8, 3, 1, 48, 37, 41, 22, 12, 3, 1, 115, 96, 106, 69, 38, 15, 4, 1, 286, 239, 284, 194, 124, 52, 20, 4, 1, 719, 622, 750, 564, 377, 189, 77, 24, 5, 1, 1842, 1607, 2010, 1584, 1144, 618, 292, 100, 30, 5, 1

Offset: 1

Andrew Howroyd, Dec 04 2020

Linear forests (A339067) are considered up to reversal of the linear order.

T(n,k) is the number of unlabeled trees on n nodes rooted at two indistinguishable nodes at distance k-1 from each other.

			Triangle read by rows:
    1;
    1,   1;
    2,   1,   1;
    4,   3,   2,   1;
    9,   6,   6,   2,   1;
   20,  16,  15,   8,   3,   1;
   48,  37,  41,  22,  12,   3,  1;
  115,  96, 106,  69,  38,  15,  4,  1;
  286, 239, 284, 194, 124,  52, 20,  4, 1;
  719, 622, 750, 564, 377, 189, 77, 24, 5, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Columns 1..4 are A000081, A027852, A280788(n-3), A339302.
Row sums are A303840(n+2).
Row sums excluding the first column are A303833.
Cf. A339067.

\\ TreeGf is A000081 as g.f.
TreeGf(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
ColSeq(n,k)={my(r=TreeGf(max(0,n+1-k))); Vec(r^k + r^(k%2)*subst(r, x, x^2)^(k\2), -n)/2}
M(n, m=n)=Mat(vector(m, k, ColSeq(n,k)~))
{ my(T=M(12)); for(n=1, #T~, print(T[n,1..n])) }

G.f of column k: (r(x)^k + r(x)^(k mod 2)*r(x^2)^floor(k/2))/2 where r(x) is the g.f. of A000081.

A038002 Number of connected functions on n points with a single labeled point.

Original entry on oeis.org

0, 1, 3, 9, 27, 81, 242, 722, 2150, 6395, 19003, 56428, 167458, 496724, 1472835, 4365692, 12936998, 38327764, 113529027, 336221554, 995586119, 2947641940, 8726093434, 25829729702, 76450357119, 226257478851, 669566448376, 1981320898874, 5862583555761

Offset: 0

Christian G. Bower

nonn

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

Cf. A000107, A027853, A339067.

G.f.: B(x)(B(x)+1) where B(x) is g.f. of A000107.
a(n) = Sum_{k=1..n} k * A339067(n,k). - Alois P. Heinz, Dec 04 2020
G.f.: A000081(x) / (1 - A000081(x))^2, where A000081(x) is the g.f. of A000081. - Vaclav Kotesovec, Jan 03 2021

A339440 Number of linear forests with n rooted trees and 2*n-1 nodes.

Original entry on oeis.org

0, 1, 2, 9, 44, 230, 1236, 6790, 37832, 213057, 1209660, 6912367, 39705516, 229055918, 1326168018, 7701734250, 44846271632, 261735599172, 1530650010312, 8967361033572, 52619233554120, 309203221308702, 1819290987055630, 10716835948503349, 63196331969007264

Offset: 0

Alois P. Heinz, Dec 04 2020

nonn

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

Cf. A339067, A245102, A245103.

b:= proc(n) option remember; `if`(n<2, n, (add(add(d*b(d),
      d=numtheory[divisors](j))*b(n-j), j=1..n-1))/(n-1))
    end:
T:= proc(n, k) option remember; `if`(k=1, b(n), (t->
      add(T(j, t)*T(n-j, k-t), j=1..n-1))(iquo(k, 2)))
    end:
a:= n-> T(2*n-1, n):
seq(a(n), n=0..24);

b[n_] := b[n] = If[n<2, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}])/(n - 1)];
T[n_, k_] := T[n, k] = If[k == 1, b[n], With[{t = Quotient[k, 2]}, Sum[T[j, t]*T[n - j, k - t], {j, 1, n - 1}]]];
a[n_] := T[2n-1, n];
a /@ Range[0, 24] (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz *)

a(n) = A339067(2n-1,n).

a(n) ~ c * d^n / sqrt(n), where d = 6.031382795097860532993547039674008662345079835351392549515262162478014679... and c = 0.05599525103242350197279211300654208236718263537075... - Vaclav Kotesovec, Dec 18 2020

cp's OEIS Frontend

A000107 Number of rooted trees with n nodes and a single labeled node; pointed rooted trees; vertebrates.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A339428 Triangle read by rows: T(n,k) is the number of connected functions on n points with a loop of length k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A000106 2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A000242 3rd power of rooted tree enumerator; number of linear forests of 3 rooted trees.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000300 4th power of rooted tree enumerator: linear forests of 4 rooted trees.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000343 5th power of rooted tree enumerator; number of linear forests of 5 rooted trees.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000395 6th power of rooted tree enumerator; number of linear forests of 6 rooted trees.

Views

Author

Keywords

References

Links

Crossrefs

Programs