A038055 -id:A038055 - cp's OEIS frontend

A339838 Number of rooted bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other and every white node is adjacent to a black node.

1, 2, 4, 10, 27, 75, 221, 662, 2042, 6402, 20407, 65828, 214720, 706600, 2343767, 7826752, 26293468, 88796471, 301290197, 1026595232, 3511246069, 12050780294, 41488523002, 143246116231, 495881545520, 1720771421470, 5984652387281, 20857113949868, 72829214554641, 254762923125929

Offset: 1

Andrew Howroyd, Dec 20 2020

nonn

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

Cf. A038055 (rooted bicolored trees), A339831, A339835, A339837.

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(v+w)); v=concat([0], t2-t1); w=concat([1], t1)); u+v}

A038058 Number of labeled trees with 2-colored nodes.

Original entry on oeis.org

1, 2, 4, 24, 256, 4000, 82944, 2151296, 67108864, 2448880128, 102400000000, 4829076871168, 253613523861504, 14681377947951104, 928873060356849664, 63772920000000000000, 4722366482869645213696, 375183514207494575620096

Offset: 0

Christian G. Bower, Jan 04 1999

nonn

Robert Israel, Table of n, a(n) for n = 0..321
Index entries for sequences related to trees

Cf. A000272, A038055-A038062.

1, seq(2^n * n^(n-2), n=1..20); # Robert Israel, Nov 02 2014

nn = 17; f[x_] := Sum[n^(n - 2) x^n/n!, {n, 1, nn}];
Range[0, nn]! CoefficientList[Series[f[2 x] + 1, {x, 0, nn}], x] (* Geoffrey Critzer, Nov 02 2014 *)

a(n) = A038057(n)/n = 2^n * n^(n-2) for n>=1. E.g.f. B(2*x) where B(x) is e.g.f. of A000272.

A225823 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. Compared to A198761, only one node color of the initial states is mobile on the tree (Falicov-Kimball model).

Original entry on oeis.org

1, 4, 54, 1568, 80680, 6510624, 761286848, 121944722176, 25668462562560

Offset: 2

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, A198761.

Term a(10) added by Martin Paech, Sep 02 2013, calculated on a HP Integrity Superdome 2-32s by courtesy of Hewlett-Packard Development Company, L.P.

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

A339643 Number of rooted trees with n nodes colored using exactly 3 colors.

Original entry on oeis.org

0, 0, 9, 102, 870, 6744, 50421, 371676, 2731569, 20113005, 148752507, 1106207331, 8274878880, 62263100994, 471138360426, 3584051515209, 27399942354822, 210432444531798, 1622954350900455, 12565580096217270, 97634810663895132, 761110656740387865, 5951117699678438271

Offset: 1

Andrew Howroyd, Dec 11 2020

nonn

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

Column 3 of A141610.

Cf. A000081, A000151, A006964, A038055, A038059, A339642.

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, 3)-3*b(n, 2)+3*b(n, 1):
seq(a(n), n=1..23);  # 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, 3] - 3 b[n, 2] + 3 b[n, 1];
Array[a, 23] (* Jean-François Alcover, Jan 04 2021, after Alois P. Heinz *)

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

a(n) = A038059(n) - 3*A038055(n) + 3*A000081(n).

a(n) = 3*(A006964(n) - 2*A000151(n) + A000081(n)).

A038061 a(n) = 3^n*n^(n-1).

Original entry on oeis.org

3, 18, 243, 5184, 151875, 5668704, 257298363, 13759414272, 847288609443, 59049000000000, 4594736955793347, 394865111526801408, 37144672966729275363, 3796313155316599873536, 418886580596209716796875

Offset: 1

Christian G. Bower, Jan 04 1999

nonn

Labeled rooted trees with 3-colored nodes.

Index entries for sequences related to rooted trees

Cf. A000169, A038055-A038062.

A038061:=n->3^n*n^(n-1): seq(A038061(n), n=1..20); # Wesley Ivan Hurt, Feb 13 2017

Table[3^n n^(n-1),{n,20}] (* Harvey P. Dale, Aug 24 2012 *)

E.g.f. B(3x) where B(x) is e.g.f. of A000169.

New description from Vladeta Jovovic, Mar 08 2003

A242353 Number T(n,k) of two-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Original entry on oeis.org

2, 4, 8, 6, 16, 12, 16, 8, 32, 24, 32, 16, 32, 24, 20, 24, 10, 64, 48, 64, 32, 64, 48, 40, 48, 20, 64, 48, 64, 32, 64, 48, 48, 36, 40, 32, 12, 128, 96, 128, 64, 128, 96, 80, 96, 40, 128, 96, 128, 64, 128, 96, 96, 72, 80, 64, 24, 128, 96, 128, 64, 128, 96, 80

Offset: 1

Martin Paech, May 11 2014

The underlying partitions of n-1 (cf. A000041) for the construction of the trees with n nodes are generated in descending order, the elements within a partition are sorted in ascending order, e.g.,
n = 1
  {0} |-> () |-> 10_2
n = 2
  {1} |-> (()) |-> 1100_2
n = 3
  {2} > {1, 1} |-> ((())) > (()()) |-> 111000_2 > 110100_2
n = 4
  {3} > {1, 2} > {1, 1, 1} |-> (((()))) > ((()())) > (()(())) > (()()()) |-> 11110000_2 > 11101000_2 > 11011000_2 > 11010100_2
The decimal equivalents of the binary encoded rooted trees in row n are the descending ordered elements of row n in A216648.

			Let {u, d} be a set of two colors, corresponding each with the up-spin and down-spin electrons in the underlying physical problem. (We consider each rooted tree as a cutout of the Bethe lattice in infinite dimensions.) Then for
n = 1 with A000081(1) = 1
  u(), d() are the 2 two-colored trees of the first and only structure k = 1 (sum is 2 = A038055(1)); for
n = 2 with A000081(2) = 1
  u(u()), u(d()), d(u()), d(d()) are the 4 two-colored trees of the first and only structure k = 1 (sum is 4 = A038055(2)); for
n = 3 with A000081(3) = 2
  u(u(u())), u(u(d())), u(d(u())), u(d(d())), d(u(u())), d(u(d())), d(d(u())), d(d(d())) are the 8 two-colored trees of the structure k = 1 and
  u(u()u()), u(u()d()), u(d()d()), d(u()u()), d(u()d()), d(d()d()) are the 6 two-colored trees of the structure k = 2 (sum is 14 = A038055(3)).
Triangle T(n,k) begins:
2;
4;
8,   6;
16, 12, 16,  8;
32, 24, 32, 16, 32, 24, 20, 24, 10;

G. Gruber, Entwicklung einer graphbasierten Methode zur Analyse von Hüpfsequenzen auf Butcherbäumen und deren Implementierung in Haskell, Diploma thesis, Marburg, 2011
Eva Kalinowski, Mott-Hubbard-Isolator in hoher Dimension, Dissertation, Marburg: Fachbereich Physik der Philipps-Universität, 2002.

Martin Paech, Rows n = 1..14, flattened
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 85, 045105, Jan 2012)
E. Kalinowski and M. Paech, Table of two-colored Butcher trees B(n,k,m) up to order n = 5.
M. Paech, A sonification of this sequence, created with MUSICALGORITHMS, using simple 'division operation' instead of modulo scaling (3047 elements, 240 bpm).
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)

Row sums give A038055.
Row length is A000081.
Total number of elements up to and including row n is A087803.
Cf. A216648.

A038060 Number of trees with 3-colored nodes.

Original entry on oeis.org

1, 3, 6, 18, 75, 342, 1773, 9894, 58596, 362061, 2314119, 15185223, 101830986, 695253993, 4819762446, 33851833506, 240472935735, 1725315714729, 12487872432924, 91097741283408, 669227023979088, 4947500029023540, 36786363204267282, 274949933519917908

Offset: 0

Christian G. Bower, Jan 04 1999

nonn

Index entries for sequences related to trees

Cf. A000055, A038055-A038062.

Equals 3 * A006965(n).

b[n_] := b[n] = If[n < 2, 3n, (Sum[Sum[b[d] d, {d, Divisors[j]}] b[n - j], {j, 1, n - 1}])/(n - 1)];
a[n_] := If[n == 0, 1, b[n] - (Sum[b[k] b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2];
a /@ Range[0, 25] (* Jean-François Alcover, Nov 01 2020, after Alois P. Heinz in A006965 *)

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

A384867 Array A(T,k) read down antidiagonals: Number of typed decorated trees of cardinality T on k vertices with D=2 decorations.

Original entry on oeis.org

2, 4, 2, 14, 8, 2, 52, 52, 12, 2, 214, 376, 114, 16, 2, 916, 2998, 1228, 200, 20, 2, 4116, 25256, 14568, 2864, 310, 24, 2, 18996, 222128, 18, 3132, 45140, 5540, 444, 28, 2

Offset: 1

R. J. Mathar, Jun 11 2025

Is the array obtained by deleting each second column of A242249, transposing, and multiplying each entry by 2?

			Array starts with rows T=1,2,3.. and columns k=1,2,3.. as
  2  4   14    52     214      916       4116      18996
  2  8   52   376    2998    25256     222128    2013680
  2 12  114  1228   14568   183132    2401410    32465640
  2 16  200  2864   45140   754640   13156232   236477200
  2 20  310  5540  108930  2272804   49446000  1109081180
  2 24  444  9512  224154  5606520  146204792  3930863232
  2 28  602 15036  413028 12043500  366122190 11475005616
  2 32  784 22368  701768 23373216  811575408 29052861280
  2 36  990 31764 1120590 41969844 1638712716 65965167108
  2 40 1220 43480 1703710 70875208 3073688160

L. Foissy, Algebraic structures on typed decorated rooted trees, SIGMA 17 (2021) 086, Appendix 6.1 D=2.

Cf. A242249 (D=1), A038055 (row 1), A136794 (row 2).

cp's OEIS Frontend

A339838 Number of rooted bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other and every white node is adjacent to a black node.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A038058 Number of labeled trees with 2-colored nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A225823 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. Compared to A198761, only one node color of the initial states is mobile on the tree (Falicov-Kimball model).

Views

Author

Keywords

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A339643 Number of rooted trees with n nodes colored using exactly 3 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A038061 a(n) = 3^n*n^(n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A242353 Number T(n,k) of two-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Views

Author

Keywords

Comments

Examples

References