A000151 -id:A000151 - cp's OEIS frontend

A245870 Decimal expansion of a constant related to A000151.

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

A038055 Number of n-node rooted trees with nodes of 2 colors.

Original entry on oeis.org

2, 4, 14, 52, 214, 916, 4116, 18996, 89894, 433196, 2119904, 10503612, 52594476, 265713532, 1352796790, 6933598208, 35747017596, 185260197772, 964585369012, 5043220350012, 26467146038744, 139375369621960, 736229024863276, 3900074570513316, 20714056652990194

Offset: 1

Christian G. Bower, Jan 04 1999

Alois P. Heinz, Table of n, a(n) for n = 1..1000
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 3.
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000081, A038056-A038062, A271878 (multisets).

Cf. A245870.

spec := [N, {N=Prod(bead,Set(N)), bead=Union(R,B), R=Atom, B=Atom}]; [seq(combstruct[count](spec, size=n), n=1..40)];
# second Maple program:
with(numtheory):
a:= proc(n) option remember; `if`(n<2, 2*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, May 11 2014

a[n_] := a[n] = If[n<2, 2*n, (Sum[Sum[d*a[d], {d, Divisors[j]}]*a[n-j], {j, 1, n-1}])/(n-1)]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)
a[1] = 2; a[n_] := a[n] = Sum[k a[k] a[n - m k]/(n-1), {k, n}, {m, (n-1)/k}]; Table[a[n], {n, 30}] (* Vladimir Reshetnikov, Aug 12 2016 *)

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] ) ); 2*A} \\ Andrew Howroyd, May 12 2018

Shifts left and halves under Euler transform.
a(n) = 2*A000151(n).
a(n) ~ c * d^n / n^(3/2), where d = A245870 = 5.646542616232949712892713516..., c = 0.41572319484583484264330698410170337587070758092051645875080558178621559423... . - Vaclav Kotesovec, Sep 11 2014, updated Dec 26 2020

A005750 Number of planted matched trees with n nodes.

Original entry on oeis.org

1, 1, 3, 10, 39, 160, 702, 3177, 14830, 70678, 342860, 1686486, 8393681, 42187148, 213828802, 1091711076, 5609297942, 28982708389, 150496728594, 784952565145, 4110491658233, 21602884608167, 113907912618599, 602414753753310, 3194684310627727, 16984594260224529

Offset: 1

N. J. A. Sloane

nonn

When convolved with itself gives A000151.
Number of rooted trees with n nodes and edges not attached to root are 2-colored or oriented.
Also number of 2-trees (with 2n+1 cells) rooted at a symmetric end-edge. - Vladeta Jovovic, Aug 22 2001

			A(x) = x + x^2 + 3*x^3 + 10*x^4 + 39*x^5 + 160*x^6 + 702*x^7 + ...

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.5.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 75, Eq. (3.5.3).
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..1325 (terms 1..500 from Alois P. Heinz)
Loïc Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA], 2018.
T. Fowler, I. Gessel, G. Labelle, P. Leroux, The specification of 2-trees, Adv. Appl. Math. 28 (2) (2002) 145-168, Table 1.
Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45. See page 20, line -3. - From _N. J. A. Sloane_, Dec 15 2012
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 428
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

Cf. A000151, A058870, A058866, A054581, A245870.

A:= proc(n) option remember; if n=0 then 0 else unapply(convert(series(x*exp(add((A(n-1)(x^k))^2/(k*x^k), k=1..2*n)), x=0,2*n), polynom), x) fi end: a:= n-> coeff(series(A(n)(x), x=0, n+1), x,n): seq(a(n), n=1..23); # Alois P. Heinz, Aug 20 2008

max = 23; f[x_] := Sum[c[k]*x^k, {k, 0, max}]; c[0] = 0; c[1] = 1; coes = CoefficientList[ Series[ Log[f[x]/x] - Sum[f[x^k]^2/(k*x^k), {k, 1, max}], {x, 0, max}], x]; eqns = Rest[ Thread[coes == 0]]; s[2] = Solve[eqns[[1]], c[2]][[1]]; Do[eqns = Rest[eqns] /. s[k-1]; s[k] = Solve[ eqns[[1]], c[k]][[1]], {k, 3, max}]; Table[c[k], {k, 1, max}] /. Flatten[ Table[s[k], {k, 2, max}]] (* Jean-François Alcover, Oct 25 2011, after g.f. *)
terms = 26; (* B = g.f. of A000151 *) B[] = 0; Do[B[x] = x*Exp[2*Sum[ B[x^k]/k, {k, 1, terms}]] + O[x]^terms // Normal, terms];
A[x_] = Exp[Sum[B[x^k]/k, {k, 1, terms}]] + O[x]^terms;
CoefficientList[A[x], x] (* Jean-François Alcover, 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] ) ); Vec(sqrt(Ser(A)))} \\ Andrew Howroyd, May 13 2018

a(n+1) is Euler transform of A000151.
G.f.: A(x) = x*exp( A(x)^2/x + A(x^2)^2/(2x^2) + A(x^3)^2/(3x^3) + ... + A(x^n)^2/(n*x^n) + ...). [Harary & Palmer (3.5.8)] - Paul D. Hanna
G.f.: sqrt(B(x)/x) where B(x) is the g.f. of A000151. - Andrew Howroyd, May 13 2018
a(n) ~ c * d^n / n^(3/2), where d = A245870 = 5.646542616232..., c = 0.06185402386554883780092844840921448929211072031752507960399709674242810089... - Vaclav Kotesovec, Sep 12 2014, updated Dec 26 2020
a(n) = A063687(n)+2*A058870(n). [Harary & Palmer (3.5.3)] - R. J. Mathar, Jan 13 2025

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

A242249 Number A(n,k) of rooted trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 2, 0, 0, 1, 3, 7, 4, 0, 0, 1, 4, 15, 26, 9, 0, 0, 1, 5, 26, 82, 107, 20, 0, 0, 1, 6, 40, 188, 495, 458, 48, 0, 0, 1, 7, 57, 360, 1499, 3144, 2058, 115, 0, 0, 1, 8, 77, 614, 3570, 12628, 20875, 9498, 286, 0, 0, 1, 9, 100, 966, 7284, 37476, 111064, 142773, 44947, 719, 0

Offset: 0

Alois P. Heinz, May 09 2014

From Vaclav Kotesovec, Aug 26 2014: (Start)
Column k > 0 is asymptotic to c(k) * d(k)^n / n^(3/2), where constants c(k) and d(k) are dependent only on k. Conjecture: d(k) ~ k * exp(1). Numerically:
d(1)   =   2.9557652856519949747148175... (A051491)
d(2)   =   5.6465426162329497128927135... (A245870)
d(3)   =   8.3560268792959953682760695...
d(4)   =  11.0699628777593263124193026...
d(5)   =  13.7856511100846851989303249...
d(6)   =  16.5022088446930015657112211...
d(7)   =  19.2192613290638657575973462...
d(8)   =  21.9366222112987115910888213...
d(9)   =  24.6541883249893084812976812...
d(10)  =  27.3718979186642404090999595...
d(100) = 272.0126359583480733207362718...
d(101) = 274.7309127032967881125015217...
d(200) = 543.8405620978790523837823296...
d(201) = 546.5588426492458787468860222...
d(101)-d(100) = 2.718276744...
d(201)-d(200) = 2.718280551...
(End)

			Square array A(n,k) begins:
  0,  0,    0,     0,      0,      0,       0,       0, ...
  1,  1,    1,     1,      1,      1,       1,       1, ...
  0,  1,    2,     3,      4,      5,       6,       7, ...
  0,  2,    7,    15,     26,     40,      57,      77, ...
  0,  4,   26,    82,    188,    360,     614,     966, ...
  0,  9,  107,   495,   1499,   3570,    7284,   13342, ...
  0, 20,  458,  3144,  12628,  37476,   91566,  195384, ...
  0, 48, 2058, 20875, 111064, 410490, 1200705, 2984142, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
L. Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 (2018), doi SIGMA 17 (2021)

Columns k=0-10 give: A063524, A000081, A000151, A006964, A052763, A052788, A246235, A246236, A246237, A246238, A246239.
Rows n=0-3 give: A000004, A000012, A001477, A005449.
Lower diagonal gives A242375.
Cf. A255517, A256064.

with(numtheory):
A:= proc(n, k) option remember; `if`(n<2, n, (add(add(d*
      A(d, k), d=divisors(j))*A(n-j, k)*k, j=1..n-1))/(n-1))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

nn = 10; t[x_] := Sum[a[n] x^n, {n, 1, nn}]; Transpose[ Table[Flatten[ sol = SolveAlways[ 0 == Series[ t[x] - x Product[1/(1 - x^i)^(n a[i]), {i, 1, nn}], {x, 0, nn}], x]; Flatten[{0, Table[a[n], {n, 1, nn}]}] /. sol], {n, 0, nn}]] // Grid (* Geoffrey Critzer, Nov 11 2014 *)
A[n_, k_] := A[n, k] = If[n<2, n, Sum[Sum[d*A[d, k], {d, Divisors[j]}] *A[n-j, k]*k, {j, 1, n-1}]/(n-1)]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 04 2014, translated from Maple *)

\\ ColGf gives column generating function
ColGf(N,k) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = k/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); x*Ser(A)}
Mat(vector(8, k, concat(0, Col(ColGf(7, k-1))))) \\ Andrew Howroyd, May 12 2018

G.f. for column k: x*Product_{n>=1} 1/(1 - x^n)^(k*A(n,k)). - Geoffrey Critzer, Nov 13 2014

A000238 Number of oriented trees with n nodes.

Original entry on oeis.org

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, 2266502, 10598452, 50235931, 240872654, 1166732814, 5702001435, 28088787314, 139354922608, 695808554300, 3494390057212, 17641695461662, 89495023510876, 456009893224285, 2332997330210440

Offset: 1

N. J. A. Sloane

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 286.
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).

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 350 terms from N. J. A. Sloane)
H. R. Afshar, E. A. Bergshoeff, W. Merbis, Interacting spin-2 fields in three dimensions, arXiv preprint arXiv:1410.6164 [hep-th], 2014-2015, JHEP 2015 (2015) # 040.
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), TOC
R. J. Mathar, Oriented trees A000238
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.
Index entries for sequences related to trees

Cf. A000060, A000151, A051437 (linear oriented), A334827 (oriented star-like).

Diagonal of A335362.

A:= proc(n) option remember; if n=0 then 0 else unapply(convert(series(x*exp(2* add(A(n-1)(x^k)/k, k=1..n-1)), x=0,n), polynom), x) fi end: a:= n-> coeff(series(A(n+1)(x) *(1-A(n+1)(x)), x=0, n+1), x,n): seq(a(n), n=1..26); # Alois P. Heinz, Aug 20 2008

A[n_][y_] := A[n][y] = If[n == 0, 0, Normal[Series[x*Exp[2*Sum[A[n-1][x^k]/k, {k, 1, n-1}]], {x, 0, n}] /. x -> y]]; a[n_] := SeriesCoefficient[A[n+1][x]*(1-A[n+1][x]), {x, 0, n}]; Table[a[n], {n, 1, 26}] (* Jean-François Alcover, Feb 12 2014, translated from Maple *)

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] ) ); Vec(Ser(A)-x*Ser(A)^2)} \\ Andrew Howroyd, May 13 2018

G.f. = x+x^2+3*x^3+8*x^4+27*x^5+... = R(x)-R(x)^2, where R(x) = g.f. for A000151.

a(n) ~ c * d^n / n^(5/2), where d = A245870 = 5.64654261623294971289271351621..., c = 0.22571615379282714232305... . - Vaclav Kotesovec, Dec 08 2014

2 errors corrected by Paul Zimmermann, Mar 01 1996

More terms from N. J. A. Sloane, Mar 10 2007

A000060 Number of signed trees with n nodes.

Original entry on oeis.org

1, 2, 3, 10, 27, 98, 350, 1402, 5743, 24742, 108968, 492638, 2266502, 10600510, 50235931, 240882152, 1166732814, 5702046382, 28088787314, 139355139206, 695808554300, 3494391117164, 17641695461662, 89495028762682, 456009893224285, 2332997356507678, 11980753878699716, 61739654456234062, 319188605907760846

Offset: 1

N. J. A. Sloane

If only trees with a degree of each node <= 2 (linear chains) are counted, we obtain A005418. If only trees with a degree of each node <= 3 are counted, we obtain 1, 2, 3, 10, 22, 76, 237, 856, ... If the degree is restricted to <= 4 we obtain 1, 2, 3, 10, 27, 92, 323, 1260, ... - R. J. Mathar, Feb 26 2018

			For n=4 nodes and 3 edges, the unsigned tree has two forms: the star and the linear chain. The star has 4 ways of signing its 3 edges: without plus (3 minus'), with one plus (2 minus'), with two plusses (1 minus) and with three plusses (no minus).  The linear chain has 6 ways of signing the edges: +++, ---, +-- (equivalent to --+), -++ (equivalent to ++-), -+- and +-+. The total number of ways is a(4) = 4+6=10. - _R. J. Mathar_, Feb 26 2018

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

T. D. Noe, Table of n, a(n) for n = 1..500
F. Harary and G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
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.
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)
Index entries for sequences related to trees

Cf. A000151, A000238.

Row sums of A302939.

unassign('x'): with(combstruct): norootree:=[S, {B = Set(S), S = Prod(Z,B,B)}, unlabeled]: S:=x->add(count(norootree,size=i)*x^i,i=1..30): seq(coeff(S(x)+S(x^2)-S(x)^2,x,i),i=1..29); # with Algolib (Pab Ter)

b[M_] := Module[{A}, A = Table[1, {M}]; For[n = 1, n <= M-1, n++, A[[n+1]] = 2/n*Sum[Sum[d*A[[d]], {d, Divisors[i]}]*A[[n-i+1]], {i, 1, n}]]; A];
seq[n_] := Module[{g}, g = x*(b[n].x^Range[0, n-1]); CoefficientList[g + (g /. x -> x^2) - g^2, x]][[2 ;; n+1]];
seq[29] (* Jean-François Alcover, Sep 04 2019, after Andrew Howroyd *)

\\ here b(N) is A000151 as vector
b(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}
seq(n) = {my(g=x*Ser(b(n))); Vec(g + subst(g, x, x^2) - g^2)} \\ Andrew Howroyd, May 13 2018

G.f.: S(x) + S(x^2) - S(x)^2, where S(x) is the generating function for A000151. - Pab Ter (pabrlos2(AT)yahoo.com), Oct 12 2005

a(n) = A000238(n) + A000151(n/2), where A000151(.) is zero for non-integer arguments. - R. J. Mathar, Apr 16 2018

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

A304489 Triangle read by rows: T(n,k) = number of rooted signed trees with n nodes and k positive edges (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 4, 9, 9, 4, 9, 26, 37, 26, 9, 20, 75, 134, 134, 75, 20, 48, 214, 469, 596, 469, 214, 48, 115, 612, 1577, 2445, 2445, 1577, 612, 115, 286, 1747, 5204, 9480, 11513, 9480, 5204, 1747, 286, 719, 4995, 16865, 35357, 50363, 50363, 35357, 16865, 4995, 719

Offset: 1

Andrew Howroyd, May 13 2018

Equivalently, the number of rooted trees with 2-colored non-root nodes, n nodes and k nodes of the first color.

			Triangle begins:
    1;
    1,    1;
    2,    3,    2;
    4,    9,    9,    4;
    9,   26,   37,   26,     9;
   20,   75,  134,  134,    75,   20;
   48,  214,  469,  596,   469,  214,   48;
  115,  612, 1577, 2445,  2445, 1577,  612,  115;
  286, 1747, 5204, 9480, 11513, 9480, 5204, 1747, 286;
  ...

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

Row sums are A000151.
Columns k=0..1 are A000081, A000243.
Cf. A294783, A302939, A331114.

R(n, y)={my(v=vector(n)); v[1]=1; for(k=1, n-1, my(p=(1+y)*v[k]); my(q=Vec(prod(j=0, poldegree(p, y), (1/(1-x*y^j) + O(x*x^(n\k)))^polcoeff(p, j)))); v=vector(n, j, v[j] + sum(i=1, (j-1)\k, v[j-i*k] * q[i+1]))); v; }
{ my(A=R(10,y)); for(n=1, #A, print(Vecrev(A[n]))) }

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
R(n, y)={my(v=[1]); for(k=2,n,v=concat([1], EulerMT(v*(1+y)))); v}
{ my(A=R(10,y)); for(n=1, #A, print(Vecrev(A[n]))) }

A005751 Number of matched trees with 2n nodes.

Original entry on oeis.org

1, 1, 2, 5, 15, 49, 180, 701, 2891, 12371, 54564, 246319, 1133602, 5300255, 25119554, 120441076, 583373822, 2851023191, 14044428996, 69677569603, 347904448580, 1747195558582, 8820848574074, 44747514381341, 228004950808983, 1166498678253839, 5990376960443432

Offset: 1

N. J. A. Sloane

nonn

This sequence also describes the number of trees on 2n vertices that are in P-position (a player 2 win) in unrooted UVG (Undirected Vertex Geography). This connection is discussed by Fraenkel, Scheinerman, and Ullman in their paper "Undirected Edge Geography." - Kaitlin Bruegge, Jul 14 2017

			a(3)=2; indeed we have the path P_6 and the tree obtained by identifying one endpoint of each of P_2, P_3, and P_3. - _Emeric Deutsch_, Apr 13 2014

S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 307 and 564.
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..400
Aviezri S. Fraenkel, Edward R. Scheinerman, and Daniel Ullman, Undirected Edge Geography, Theoretical Computer Science, 112, (1993), 371-381.
Indranil Ghosh, Python program for computing this sequence (translated from Maple code)
Rodica Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.
Rodica Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1981), 97. (Annotated scanned copy)
Index entries for sequences related to trees

Cf. A000151 for the rooted version.

Cf. A245870.

with(numtheory): r2:= proc(n) option remember; local m; `if`(n=1, 1, 2/(n-1) *add(r2(m) *add(d*r2(d), d=divisors(n-m)), m=1..n-1)) end: p2:= proc(n) option remember; local m; `if`(n=1, 1, 1/(n-1) *add(p2(m) *add(d*r2(d), d=divisors(n-m)), m=1..n-1)) end: m2:= n-> (r2(n) -add(r2(m) *r2(n-m), m=1..n-1) +`if`(irem(n, 2)=0, r2(n/2), p2((n+1)/2)))/2: seq(m2(n), n=1..30); # Alois P. Heinz, Aug 04 2009

r2[n_] := r2[n] = If[n == 1, 1, 2/(n-1)*Sum[r2[m]*Sum[d*r2[d], {d, Divisors[n-m]}], {m, 1, n-1}]]; p2[n_] := p2[n] = If[n == 1, 1, 1/(n-1)*Sum[p2[m]*Sum[d*r2[d], {d, Divisors[n-m]}], {m, 1, n-1}]]; m2[n_] := (r2[n] - Sum[r2[m]*r2[n-m], {m, 1, n-1}] + If[Mod[n, 2] == 0, r2[n/2], p2[(n+1)/2]])/2; Table[m2[n], {n, 1, 30}] (* Jean-François Alcover, Mar 17 2014, after Alois P. Heinz *)

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

More terms from Alois P. Heinz, Aug 04 2009

A271878 Triangle T(n,t) read by rows: number of rooted forests with n 2-colored nodes and t rooted trees.

Original entry on oeis.org

2, 4, 3, 14, 8, 4, 52, 38, 12, 5, 214, 160, 62, 16, 6, 916, 741, 288, 86, 20, 7, 4116, 3416, 1408, 416, 110, 24, 8, 18996, 16270, 6856, 2110, 544, 134, 28, 9, 89894, 78408, 34036, 10576, 2812, 672, 158, 32, 10, 433196, 384033, 169936, 53892, 14352

Offset: 1

R. J. Mathar, Apr 16 2016

See eq. (27) of the reference for a recurrence.

			T(4,2)=28+10=38: That forest has t=2 trees with either n=1+3 or n=2+2 nodes. The splitting 1+3 contributes T(1,1)*T(3,1) = 2*14 = 28; the splitting 2+2 contributes binomial(5,2) = 10 because there are T(2,1)=4 selectable trees and the choice of pairs is A000217(T(2,1)).
2 ;
4 3;
14 8 4;
52 38 12 5;
214 160 62 16 6;
916 741 288 86 20 7 ;
4116 3416 1408 416 110 24 8;
18996 16270 6856 2110 544 134 28 9 ;
89894 78408 34036 10576 2812 672 158 32 10;
433196 384033 169936 53892 14352 3514 800 182 36 11;
2119904 1901968 856902 275264 74238 18128 4216 928 206 40 12;
10503612 9519710 4350520 1416051 384512 94668 21904 4918 1056 230 44 13;
52594476 48061472 22238446 7317080 2002850 494544 115098 25680 5620 1184 254 48 14 ;

Alois P. Heinz, Rows n = 1..141, flattened
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603:00077 [math.CO] (2016), Table 3.

Cf. A033185 (1-colored nodes), A038055 (column k=1), A000151 (row sums), A271879 (3-colored nodes)

g:= proc(n) option remember; `if`(n<2, 2*n, (add(add(d*g(d),
       d=numtheory[divisors](j))*g(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j)*
       binomial(g(i)+j-1, j), j=0..min(n/i, p)))))
    end:
T:= (n, k)-> b(n$2, k):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Apr 13 2017

g[n_] := g[n] = If[n < 2, 2*n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[n - j], {j, 1, n - 1}])/(n - 1)];
b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[Min[i, p] < 1, 0, Sum[b[n - i*j, i - 1, p - j]*Binomial[g[i] + j - 1, j], {j, 0, Min[n/i, p]}]]]];
T[n_, k_] := b[n, n, k];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)

A339642 Number of rooted trees with n nodes colored using exactly 2 colors.

Original entry on oeis.org

0, 2, 10, 44, 196, 876, 4020, 18766, 89322, 431758, 2116220, 10494080, 52569504, 265647586, 1352621168, 6933127446, 35745747902, 185256755454, 964575991660, 5043194697556, 26467075595080, 139375175511598, 736228488297566, 3900073083063348, 20714052518640904

Offset: 1

Andrew Howroyd, Dec 11 2020

nonn

			a(3) = 10 includes 5 trees and their color complements:
   (1(12)), (1(22)), (1(1(2))), (1(2(1))), (1(2(2))).

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

Column 2 of A141610.

Cf. A000081, A000151, A038055, A339643.

b:= proc(n, k) option remember; `if`(n<2, k*n, (add(add(b(d, k)*
      d, d=numtheory[divisors](j))*b(n-j, k), j=1..n-1))/(n-1))
    end:
a:= n-> b(n, 2)-2*b(n, 1):
seq(a(n), n=1..25);  # Alois P. Heinz, Dec 11 2020

b[n_, k_] := b[n, k] = If[n < 2, k*n, (Sum[Sum[b[d, k]*d, {d, Divisors[j]}]*b[n - j, k], {j, 1, n - 1}])/(n - 1)];
a[n_] := b[n, 2] - 2*b[n, 1];
Array[a, 25] (* Jean-François Alcover, Jan 04 2021, after Alois P. Heinz *)

\\ See A141610 for U(N,m)
seq(n)={U(n,2) - 2*U(n,1)}

a(n) = A038055(n) - 2*A000081(n).

a(n) = 2*(A000151(n) - A000081(n)).

cp's OEIS Frontend

A245870 Decimal expansion of a constant related to A000151.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

A038055 Number of n-node rooted trees with nodes of 2 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A005750 Number of planted matched trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A242249 Number A(n,k) of rooted trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A000238 Number of oriented trees with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A000060 Number of signed trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A304489 Triangle read by rows: T(n,k) = number of rooted signed trees with n nodes and k positive edges (0 <= k < n).

Views

Author