A051491 -id:A051491 - cp's OEIS frontend

A244410 Number of unlabeled rooted trees with 2n+1 nodes and maximal outdegree (branching factor) n.

1, 1, 5, 16, 49, 142, 415, 1198, 3473, 10048, 29118, 84376, 244747, 710198, 2062273, 5991417, 17416400, 50652247, 147384675, 429043389, 1249508946, 3640449678, 10610613551, 30937605075, 90237313082, 263288153073, 768449666116, 2243530461066, 6552016136666

Offset: 0

Joerg Arndt and Alois P. Heinz, Jun 27 2014

nonn

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

Cf. A244372, A244407, A051491.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> `if`(n=0, 1, b(2*n$2, n$2)-b(2*n$2, n-1$2)):
seq(a(n), n=0..30);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[b[i - 1, i - 1, k, k] + j - 1, j]* b[n - i*j, i - 1, t - j, k], {j, 0, Min[t, n/i]}]] // FullSimplify] ; a[n_] := If[n == 0, 1, b[2*n, 2 n, n, n] - b[2*n, 2 n, n - 1, n - 1]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 06 2015, after Maple *)

a(n) = A244372(2n+1,n).

a(n) ~ c * d^n / sqrt(n), where d = 2.955765285651994974714817524... is the Otter's rooted tree constant (see A051491), and c = 2.806733... . - Vaclav Kotesovec, Jul 11 2014

A339984 G.f.: g(x) * g(x^2), where g(x) is the g.f. of A000081.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 5, 13, 26, 65, 147, 369, 899, 2298, 5851, 15261, 39945, 105948, 282504, 759480, 2052027, 5576017, 15216998, 41705762, 114715503, 316611401, 876466003, 2433091773, 6771462322, 18889829555, 52809592990, 147935027381, 415182991401, 1167251435240

Offset: 0

Vaclav Kotesovec, Dec 25 2020

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..2000

Cf. A000081, A217781, A309619, A339985.

max = 30; A000081 = Rest[Cases[ Import["https://oeis.org/A000081/b000081.txt", "Table"], {, }][[All, 2]]]; g81 = Sum[A000081[[k]]*x^k, {k, 1, max}]; g81x2 = Sum[A000081[[k]]*x^(2*k), {k, 1, max}]; CoefficientList[Series[g81 * g81x2, {x, 0, max}], x]

a(n) ~ A339986 * A051491^n / n^(3/2).

A339985 G.f.: g(x)^2 * g(x^2), where g(x) is the g.f. of A000081.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 6, 14, 37, 90, 232, 584, 1512, 3906, 10246, 26984, 71766, 191852, 516400, 1396760, 3797435, 10367628, 28420466, 78183462, 215791426, 597368222, 1658233794, 4614679792, 12872125836, 35982713314, 100787606966, 282832173830, 795070060983

Offset: 0

Vaclav Kotesovec, Dec 25 2020

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..2000

Cf. A000081, A217781, A339984.

max = 30; A000081 = Rest[Cases[ Import["https://oeis.org/A000081/b000081.txt", "Table"], {, }][[All, 2]]]; g81 = Sum[A000081[[k]]*x^k, {k, 1, max}]; g81x2 = Sum[A000081[[k]]*x^(2*k), {k, 1, max}]; CoefficientList[Series[g81^2 * g81x2, {x, 0, max}], x]

a(n) ~ 2 * A339986 * A051491^n / n^(3/2).

A340310 Decimal expansion of a constant related to the asymptotics of A000107.

Original entry on oeis.org

3, 6, 1, 7, 7, 8, 2, 5, 8, 3, 9, 0, 0, 2, 1, 2, 1, 9, 7, 9, 2, 6, 8, 8, 6, 2, 4, 7, 3, 1, 1, 9, 2, 4, 5, 5, 2, 7, 1, 9, 3, 1, 2, 2, 1, 8, 1, 0, 1, 6, 8, 2, 1, 4, 1, 7, 8, 4, 2, 1, 0, 9, 8, 7, 8, 3, 4, 2, 7, 8, 1, 0, 5, 6, 6, 7, 2, 5, 5, 9, 2, 4, 0, 9, 2, 4, 2, 8, 0, 6, 2, 8, 3, 1, 1, 6, 8, 7, 4, 3, 8, 4, 9, 6, 9, 6

Offset: 0

Vaclav Kotesovec, Jan 04 2021

			0.36177825839002121979268862473119245527193122181016821417842109878342781...

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

Cf. A000107.

Equals lim_{n->infinity} A000107(n) * sqrt(n) / A051491^n.

A346915 Decimal expansion of the limit as N->oo of the mean number of mems per forest taken by Knuth's algorithm O when generating the rooted forests of N vertices.

Original entry on oeis.org

3, 5, 3, 3, 9, 2, 6, 3, 9, 8, 0, 2, 3, 7, 2, 1, 7, 9, 6, 9, 1, 5, 9, 9, 9, 7, 5, 6, 9, 0, 0, 2, 7, 2, 7, 8, 4, 5, 1, 0, 8, 6, 7, 6, 0, 3, 2, 5, 7, 3, 7, 7, 2, 9, 1, 8, 0, 6, 7, 3, 4, 5, 8, 9, 4, 6, 0, 3, 4, 1, 2, 0, 6, 2, 1, 8, 6, 9, 2, 4, 9, 4, 1, 9, 7, 5, 0, 7, 7, 2, 5, 1, 2, 6, 3, 1, 2, 7, 2, 8, 7, 3, 0, 5, 5

Offset: 1

Kevin Ryde, Aug 07 2021

Knuth volume 4A section 7.2.1.6 algorithm O adapts the rooted tree iteration algorithm of Beyer and Hedetniemi (A346913) to become a forests iteration in vertex parent array form (A346914).
Knuth's exercise 88 is to count mems (memory reads + memory writes) in algorithm O.  Per Knuth's answer, the present constant is 2 + 3/(d-1) where d=A051491 is the growth power of rooted trees (and forests).
Also equals 3*S+2 where S=A346916 is the (limit) mean number of singletons in a rooted forest.  The mems are S reads to find the end-most vertex k which is not a singleton, then S+1 reads and S+1 writes to change k and the singletons to subtree copies.  Finding k examines S+1 array entries, but the algorithm holds the final p[N] in a register as well as in memory so no mem to examine it.

			3.533926398023721796915999756900272...

Kevin Ryde, Table of n, a(n) for n = 1..1799
Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1, section 7.2.1.6, exercise 88. Also in Pre-Fascicle 4A, Draft of Section 7.2.1.6, Generating All Trees algorithm O page 22, exercise 88 page 40, and answer page 66.

Cf. A051491 (rooted tree growth), A346916 (mean singletons per forest).

Cf. A346913 (levels iteration), A346914 (vpar iteration).

Equals 2 + 3/(A051491 - 1). [Knuth]

Equals 3*A346916 + 2.

A029855 Number of rooted trees where root has degree 4.

Original entry on oeis.org

1, 1, 3, 7, 19, 46, 124, 320, 858, 2282, 6161, 16647, 45352, 123861, 340000, 936098, 2586518, 7166394, 19911638, 55456892, 154814055, 433081632, 1213901668, 3408659401, 9587879987, 27011564035, 76212078500

Offset: 5

Christian G. Bower

nonn

Fourth column of A033185. - Michael Somos, Aug 20 2018

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 53.

Washington Bomfim, Table of n, a(n) for n = 5..200
Frank Ruskey, Combinatorial Generation Algorithm 4.26, p. 96
Eric Weisstein's World of Mathematics, Frequency Representation
Eric Weisstein's World of Mathematics, Rooted Tree
Index entries for sequences related to rooted trees

Cf. A000226 (root degree 3), A000081, A033185.

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];Drop[Take[CoefficientList[CycleIndex[SymmetricGroup[4],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],4]  (* Geoffrey Critzer, Oct 14 2012, after code by Robert A. Russell in A000081 *)

max_n = 200; f=vector(max_n);            \\ f[n] = A000081[n], n=1..max_n
sum2(k) = {local(s); s=0; fordiv(k, d, s += d*f[d]); return(s)};
Init_f()={f[1]=1;
for(n =1, max_n -2, s=0; for(k=1, n, s+=sum2(k)*f[n-k+1]); f[n+1]=s/n)};
S=0; P=[0,1,1,1,1,0];
visit4() = {i = 3; k = 2; p = P[2]; Pr = 1;
while(1, while(P[i]==p, i++);c=i-k;Pr*=binomial(f[P[k]]+c-1, c);
if(P[i] == 0, S += Pr; return); p = P[i]; k = i; i++)};
                                         \\ F. Ruskey partition generator
Part(n, k, s, t) = { P[t] = s;
if((k == 1) || (n == k), visit4(), L = max(1, ceil((n - s)/(k - 1)));
for(j = L, min(s, n-s-k+2), Part(n-s, k-1, j, t+1))); P[t] = 1;};
\\
a(n) = {S=0; n--; Part(2*n,4+1,n,1); return(S)}
Init_f(); for(n=5, max_n, print(n, " ", a(n)))           \\ b-file format
\\ # Washington Bomfim, Jul 10 2012

a(n)= Sum_(P){ Prod_(1^a1 2^a2 3^a3 ...){ binomial(f(i)+a_i -1, a_i) } }, where P is the set of the partitions of n with four parts, and f = A000081. - Washington Bomfim, Jul 10 2012

a(n) ~ c * A051491^n / n^(3/2), where c = 0.036592912312268101787903577... - Vaclav Kotesovec, Dec 26 2020

A029870 Number of connected functions on n points with a loop of length 7.

Original entry on oeis.org

1, 1, 5, 21, 80, 285, 970, 3192, 10236, 32197, 99743, 305276, 925342, 2783012, 8316994, 24726109, 73195582, 215911767, 635028054, 1863156727, 5455350409, 15946267328, 46545783253, 135702643984, 395246786050, 1150250414764, 3345193851398, 9723141517918

Offset: 7

Christian G. Bower

nonn

Andrew Howroyd, Table of n, a(n) for n = 7..500
C. G. Bower, Transforms

Column 7 of A339428.

"CIK[ 7 ]" (necklace, indistinct, unlabeled, 7 parts) transform of A000081.

a(n) ~ A187770 * A051491^n / n^(3/2). - Vaclav Kotesovec, Dec 25 2020

Terms a(32) and beyond from Andrew Howroyd, Dec 04 2020

A029871 Number of connected functions on n points with a loop of length 8.

Original entry on oeis.org

1, 1, 6, 25, 104, 384, 1380, 4729, 15806, 51478, 164788, 519296, 1617066, 4983855, 15233671, 46235252, 139506803, 418838281, 1252174861, 3730058316, 11077154790, 32808815240, 96953599162, 285945645659, 841909040785, 2475184643011, 7267678432397, 21315839832323

Offset: 8

Christian G. Bower

nonn

Andrew Howroyd, Table of n, a(n) for n = 8..500
C. G. Bower, Transforms

Column 8 of A339428.

"CIK[ 8 ]" (necklace, indistinct, unlabeled, 8 parts) transform of A000081.

a(n) ~ A187770 * A051491^n / n^(3/2). - Vaclav Kotesovec, Dec 25 2020

Terms a(32) and beyond from Andrew Howroyd, Dec 04 2020

A032205 Number of connected functions on n points with a loop of length 9.

Original entry on oeis.org

1, 1, 6, 30, 127, 506, 1902, 6823, 23673, 79936, 264036, 856772, 2739525, 8652707, 27049259, 83824636, 257847515, 788121922, 2395786374, 7248517868, 21840785100, 65574504200, 196266067194, 585822825763, 1744384025528, 5183186173513, 15372268502463, 45515472900289

Offset: 9

Christian G. Bower

nonn

Andrew Howroyd, Table of n, a(n) for n = 9..500
C. G. Bower, Transforms (2)

Column 9 of A339428.

"CIK[ 9 ]" (necklace, indistinct, unlabeled, 9 parts) transform of A000081.

a(n) ~ A187770 * A051491^n / n^(3/2). - Vaclav Kotesovec, Dec 25 2020

Terms a(33) and beyond from Andrew Howroyd, Dec 04 2020

A032206 Number of connected functions on n points with a loop of length 10.

Original entry on oeis.org

1, 1, 7, 34, 158, 655, 2578, 9619, 34659, 120966, 412214, 1375861, 4516058, 14611989, 46712942, 147798787, 463512254, 1442513910, 4459548539, 13706894100, 41915906463, 127607366453, 386953440455, 1169295277193, 3522431890950, 10581852932516, 31711045921908

Offset: 10

Christian G. Bower

nonn

Andrew Howroyd, Table of n, a(n) for n = 10..500
Christian G. Bower, Transforms (2)

Column 10 of A339428.

"CIK[ 10 ]" (necklace, indistinct, unlabeled, 10 parts) transform of A000081.

a(n) ~ A187770 * A051491^n / n^(3/2). - Vaclav Kotesovec, Dec 25 2020

Terms a(34) and beyond from Andrew Howroyd, Dec 04 2020

cp's OEIS Frontend

A244410 Number of unlabeled rooted trees with 2n+1 nodes and maximal outdegree (branching factor) n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A339984 G.f.: g(x) * g(x^2), where g(x) is the g.f. of A000081.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A339985 G.f.: g(x)^2 * g(x^2), where g(x) is the g.f. of A000081.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A340310 Decimal expansion of a constant related to the asymptotics of A000107.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A346915 Decimal expansion of the limit as N->oo of the mean number of mems per forest taken by Knuth's algorithm O when generating the rooted forests of N vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A029855 Number of rooted trees where root has degree 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A029870 Number of connected functions on n points with a loop of length 7.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A029871 Number of connected functions on n points with a loop of length 8.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A032205 Number of connected functions on n points with a loop of length 9.

Views

Author

Keywords

Links

Crossrefs