A038055 -id:A038055 - cp's OEIS frontend

A000151 Number of oriented rooted trees with n nodes. Also rooted trees with n nodes and 2-colored non-root nodes.

1, 2, 7, 26, 107, 458, 2058, 9498, 44947, 216598, 1059952, 5251806, 26297238, 132856766, 676398395, 3466799104, 17873508798, 92630098886, 482292684506, 2521610175006, 13233573019372, 69687684810980, 368114512431638, 1950037285256658, 10357028326495097, 55140508518522726, 294219119815868952, 1573132563600386854, 8427354035116949486, 45226421721391554194

Offset: 1

N. J. A. Sloane

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 286.
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 307 and 564.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 60, R(x).
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.
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).

Vaclav Kotesovec, Table of n, a(n) for n = 1..1300 (terms 1..500 from N. J. A. Sloane)
Sølve Eidnes, Order theory for discrete gradient methods, arXiv:2003.08267 [math.NA], 2020.
L. Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA], 2018.
Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 387
P. Leroux and B. Miloudi, Generalisations de la formule d'Otter, Ann. Sci. Math. Quebec 16 (1992), no 1, 53-80.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97.
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)
S. G. Wagner, An identity for the cycle indices of rooted tree automorphism groups, Elec. J. Combinat., 13 (2006), #R00.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000238, A038055.
Also the self-convolution of A005750. - Paul D. Hanna, Aug 17 2002
Column k=2 of A242249.
Cf. A005751, A245870.

R:=series(x+2*x^2+7*x^3+26*x^4,x,5); M:=500;
for n from 5 to M do
series(add( subs(x=x^k,R)/k, k=1..n-1),x,n);
t4:=coeff(series(x*exp(%)^2,x,n+1),x,n);
R:=series(R+t4*x^n,x,n+1); od:
for n from 1 to M do lprint(n,coeff(R,x,n)); od: # N. J. A. Sloane, Mar 10 2007
with(combstruct):norootree:=[S, {B = Set(S), S = Prod(Z,B,B)}, unlabeled] :seq(count(norootree,size=i),i=1..30); # with Algolib (Pab Ter)

terms = 30; A[] = 0; Do[A[x] = x*Exp[2*Sum[A[x^k]/k, {k, 1, terms}]] + O[x]^(terms+1) // Normal, terms+1]; CoefficientList[A[x], x] // Rest
(* Jean-François Alcover, Jun 08 2011, updated Jan 11 2018 *)

seq(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 2/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); A} \\ Andrew Howroyd, May 13 2018

Generating function A(x) = x+2*x^2+7*x^3+26*x^4+... satisfies A(x)=x*exp( 2*sum_{k>=1}(A(x^k)/k) ) [Harary]. - Pab Ter (pabrlos2(AT)yahoo.com), Oct 12 2005
G.f.: x*Product_{n>=1} 1/(1 - x^n)^(2*a(n)) = Sum_{n>=1} a(n)*x^n.
a(n) ~ c * d^n / n^(3/2), where d = A245870 = 5.64654261623294971289271351621..., c = 0.2078615974229174213216534920508516879353537904602582293754027908931077971... - Vaclav Kotesovec, Aug 20 2014, updated Dec 26 2020

Extended with alternate description by Christian G. Bower, Apr 15 1998

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 12 2005

A245870 Decimal expansion of a constant related to A000151.

Original entry on oeis.org

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

Offset: 1

Vaclav Kotesovec, Aug 25 2014

			5.646542616232949712892713516216913838149821911605384392385817...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 307 and 564.

Cf. A000151, A000238, A005750, A005751, A038055, A198760.

Equals lim n -> infinity A000151(n)^(1/n).
Equals lim n -> infinity A005751(n)^(1/n).
Equals lim n -> infinity A038055(n)^(1/n).
Equals lim n -> infinity A005750(n)^(1/n).
Equals lim n -> infinity A198760(n)^(1/n).

More terms from Vaclav Kotesovec, Sep 11 2014 and Dec 26 2020

A038062 Number of labeled trees with 3-colored nodes.

Original entry on oeis.org

1, 3, 9, 81, 1296, 30375, 944784, 36756909, 1719926784, 94143178827, 5904900000000, 417703359617577, 32905425960566784, 2857282535902251951, 271165225379757133824, 27925772039747314453125

Offset: 0

Christian G. Bower, Jan 04 1999

nonn

Index entries for sequences related to trees

Cf. A000272, A038055-A038061.

A038061/n. E.g.f. B(3x) where B(x) is e.g.f. of A000272.

A198760 Number of initial spin configurations in two-colored rooted trees with n nodes.

Original entry on oeis.org

2, 8, 32, 136, 596, 2712, 12642, 60234, 291840, 1434184, 7130640, 35807114, 181339236, 925139186, 4750176056, 24528421712, 127294780994, 663591911824, 3473315219722, 18246162722278, 96169600405626, 508413199626078, 2695245063006696, 14324688031734740

Offset: 2

N. J. A. Sloane, Oct 29 2011

nonn

Also the number of two-colored rooted trees that have for a given color of the root at least one nearest neighbor node of the root in the other color. - Martin Paech, Apr 16 2012

G. Gruber, Entwicklung einer graphbasierten Methode zur Analyse von Hüpfsequenzen auf Butcherbäumen und deren Implementierung in Haskell, Diploma thesis, Marburg, 2011

Alois P. Heinz, Table of n, a(n) for n = 2..500
E. Kalinowski and W. Gluza, Evaluation of High Order Terms for the Hubbard Model in the Strong-Coupling Limit, arXiv:1106.4938, 2011 (Physical Review B, January 2012).
M. Paech, E. Kalinowski, W. Apel, G. Gruber, R. Loogen, and E. Jeckelmann, Ground-state energy and beyond: High-accuracy results for the Hubbard model on the Bethe lattice in the strong-coupling limit, DPG Spring Meeting, Berlin, TT 45.91 (2012).

Cf. A000081, A038055, A198761, A225823, A245870.

g:= proc(n, i, t) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(t*g(i-1$2, 2)+j-1, j)*g(n-i*j, i-1, t), j=0..n/i)))
    end:
a:= n-> 2*(g(n-1$2, 2) -g(n-1$2, 1)):
seq(a(n), n=2..30);  # Alois P. Heinz, May 12 2014

g[n_, i_, t_] := g[n, i, t] = If[n == 0, 1, If[i < 1, 0, Sum[ Binomial[t*g[i-1, i-1, 2]+j-1, j]*g[n-i*j, i-1, t], {j, 0, n/i}]]]; a[n_] := 2*(g[n-1, n-1, 2] - g[n-1, n-1, 1]) // FullSimplify; Table[a[n], {n, 2, 30}] (* Jean-François Alcover, Nov 25 2014, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = A245870 = 5.6465426162329497128927135162..., c = 0.29201514711473716704145008728... . - Vaclav Kotesovec, Sep 12 2014

Terms a(8) and a(9) added by Martin Paech, Apr 16 2012
Term a(10) added by Martin Paech, Jul 30 2013
a(11)-a(25) from Alois P. Heinz, May 12 2014

A038056 Number of trees with n 2-colored nodes.

Original entry on oeis.org

2, 3, 6, 18, 54, 189, 700, 2778, 11486, 49377, 217936, 984818, 4533004, 21198962, 100471862, 481754806, 2333465628, 11404047817, 56177574628, 278710061814, 1391617108600, 6988781174376, 35283390923324, 178990052273558, 912019786448570, 4665994686718118

Offset: 1

Christian G. Bower, Jan 04 1999

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for sequences related to trees

Cf. A000055, A038055-A038062. Row sums of A294783.

G.f.: B(x) - B^2(x)/2 + B(x^2)/2, where B(x) is g.f. for A038055.

A198761 Number of hopping sequences in four-colored rooted trees with n nodes, starting and ending with the same "initial state" from all of the (two-colored) rooted trees in A198760. See comments.

Original entry on oeis.org

2, 20, 648, 45472, 5644880, 1099056000, 310007943616, 119777421416192

Offset: 2

N. J. A. Sloane, Oct 29 2011

Compared to A225823, both node colors of the initial states are mobile on the tree (Hubbard model). - Eva Kalinowski, Jul 30 2013

G. Gruber, Entwicklung einer graphbasierten Methode zur Analyse von Hüpfsequenzen auf Butcherbäumen und deren Implementierung in Haskell, Diploma thesis, Marburg, 2011
M. Paech, E. Kalinowski, W. Apel, G. Gruber, R. Loogen, and E. Jeckelmann, Ground-state energy and beyond: High-accuracy results for the Hubbard model on the Bethe lattice in the strong-coupling limit, DPG Spring Meeting, Berlin, TT 45.91 (2012)

Eva Kalinowski and Władysław Gluza, Evaluation of High Order Terms for the Hubbard Model in the Strong-Coupling Limit arXiv:1106.4938, 2011 (Physical Review B, January 2012)
Martin Paech, Numerische und algebraisch-graphentheoretische Algorithmen für korrelierte Quantensysteme, Dissertation, Hannover, 2015 (in German with an abstract in English).

Cf. A000081, A038055, A136793, A198760, A225823.

Terms a(8) and a(9) added by Martin Paech, Apr 16 2012

A339831 Number of rooted bicolored trees on n nodes such that black nodes are not adjacent to each other.

Original entry on oeis.org

2, 3, 9, 28, 97, 346, 1302, 5014, 19830, 79813, 326344, 1350918, 5652334, 23861787, 101519790, 434827232, 1873491739, 8114411769, 35309142309, 154288183928, 676730773252, 2978405318453, 13149337960554, 58218455727085, 258435947527696, 1149982662789042

Offset: 1

Andrew Howroyd, Dec 19 2020

nonn

			a(1) = 2: B, W.
a(2) = 3: B(W), W(B), W(W).
a(3) = 9: B(WW), W(BB), W(BW), W(WW), B(W(B)), B(W(W)), W(B(W)), W(W(B)), W(W(W)).

Andrew Howroyd, Table of n, a(n) for n = 1..500

Cf. A038055 (rooted bicolored trees), A339830 (unrooted case), A339835, A339838.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=v=[]); for(n=1, n, my(t=concat([1], EulerT(v))); v=concat([1], EulerT(u + v)); u=t); u + v}

A339835 Number of rooted bicolored trees on n unlabeled nodes such that every white node is adjacent to a black node.

Original entry on oeis.org

1, 3, 9, 30, 111, 424, 1705, 7024, 29692, 127748, 558219, 2469403, 11039992, 49796803, 226348740, 1035750855, 4767429667, 22058219466, 102534463563, 478602668159, 2242383155726, 10541976883286, 49714185649417, 235109360767014, 1114782699692044, 5298494249055391

Offset: 1

Andrew Howroyd, Dec 19 2020

nonn

			a(1) = 1: B.
a(2) = 4: B(B), B(W), W(B).
a(3) = 9: B(BB), B(BW), B(WW), W(BB), B(B(B)), B(B(W)), B(W(B)), W(B(B)), W(B(W)).

Andrew Howroyd, Table of n, a(n) for n = 1..500

Cf. A038055 (rooted bicolored trees), A339831, A339834 (unrooted), A339838.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=v=w=[]); for(n=1, n, my(t1=EulerT(v), t2=EulerT(u+v)); u=concat([1], EulerT(u+v+w)); v=concat([0], t2-t1); w=concat([1], t1)); u+v}

A038057 a(n) = 2^n*n^(n-1).

Original entry on oeis.org

2, 8, 72, 1024, 20000, 497664, 15059072, 536870912, 22039921152, 1024000000000, 53119845582848, 3043362286338048, 190857913323364352, 13004222844995895296, 956593800000000000000, 75557863725914323419136

Offset: 1

Christian G. Bower, Jan 04 1999

nonn

Labeled rooted trees with n 2-colored nodes.

Index entries for sequences related to rooted trees

Cf. A000169, A019762 (2*e), A038055-A038062.

Equals 2 * A052746(n).

nn=16;f[x_]:=Sum[a[n]x^n/n!,{n,0,nn}];s=SolveAlways[0==Series[f[x]-2x Exp[f[x]],{x,0,nn}],x];Table[a[n],{n,1,nn}]/.s
(* or *)
nn=16;Drop[Range[0,nn]!CoefficientList[Series[-LambertW[-2x],{x,0,nn}],x],1]
(* or *)
Table[2^n*n^(n-1),{n,1,16}]  (* Geoffrey Critzer, Mar 17 2013 *)

E.g.f.: B(2*x) where B(x) is e.g.f. of A000169.

Limit_{n->oo} a(n+1)/(n*a(n)) = 2*e. - Stefano Spezia, Mar 12 2023

New description from Vladeta Jovovic, Mar 08 2003

A038059 Number of rooted trees with 3-colored nodes.

Original entry on oeis.org

3, 9, 45, 246, 1485, 9432, 62625, 428319, 3000393, 21410436, 155106693, 1137703869, 8432624850, 63060142671, 475196487363, 3604851603690, 27507181503069, 210988219961637, 1625848092941463, 12580709718788622, 97714211996345868, 761528782558088202

Offset: 1

Christian G. Bower, Jan 04 1999

Shifts left and divides by 3 under Euler transform.

L. Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA] (2018).
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Table 4.
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000081, A038055-A038062, A271879 (multisets).

with(numtheory): a:= proc(n) option remember; `if`(n<2, 3*n, (add(add(d*a(d), d=divisors(j)) *a(n-j), j=1..n-1))/ (n-1)) end: seq(a(n), n=1..30); # Alois P. Heinz, Sep 06 2008

a[n_] := a[n] = If[n<2, 3*n, Sum[Sum[d*a[d], {d, Divisors[j]}] *a[n-j], {j, 1, n-1}]/(n-1)]; Array[a, 30] (* Jean-François Alcover, Feb 24 2016, after Alois P. Heinz *)

a(n) = 3 * A006964(n).

cp's OEIS Frontend

A000151 Number of oriented rooted trees with n nodes. Also rooted trees with n nodes and 2-colored non-root nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A245870 Decimal expansion of a constant related to A000151.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

A038062 Number of labeled trees with 3-colored nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A198760 Number of initial spin configurations in two-colored rooted trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A038056 Number of trees with n 2-colored nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A198761 Number of hopping sequences in four-colored rooted trees with n nodes, starting and ending with the same "initial state" from all of the (two-colored) rooted trees in A198760. See comments.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A339831 Number of rooted bicolored trees on n nodes such that black nodes are not adjacent to each other.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A339835 Number of rooted bicolored trees on n unlabeled nodes such that every white node is adjacent to a black node.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A038057 a(n) = 2^n*n^(n-1).

Views

Author