A006964 -id:A006964 - cp's OEIS frontend

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.

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

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

A052751 A simple grammar.

Original entry on oeis.org

1, 1, 4, 19, 107, 647, 4167, 27847, 191747, 1349743, 9671316, 70297105, 517079157, 3841701488, 28787546360, 217317367487, 1651144126659, 12616570941114, 96891439504019, 747452640586114, 5789461514134881

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 707

Cf. A006964.

spec := [S,{S=Set(B),B=Prod(S,S,S,Z)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

{a(n)=local(A=1+x+x*O(x^n));if(n==0,1,for(i=1,n, A=exp(sum(k=1,n,subst(x*A^3,x,x^k+x*O(x^n))/k)));polcoeff(A,n,x))} \\ Paul D. Hanna, Jul 13 2006

G.f.: A(x) = exp(A(x)^3*x + A(x^2)^3*x^2/2 + A(x^3)^3*x^3/3 +...), A(0)=1; also, A(x)^3 = Sum_{n>=0} A006964(n+1)*x^n. - Paul D. Hanna, Jul 13 2006

A271879 Triangle T(n,t) by rows: The number of rooted forests with n 3-colored nodes and t rooted trees.

Original entry on oeis.org

3, 9, 6, 45, 27, 10, 246, 180, 54, 15, 1485, 1143, 405, 90, 21, 9432, 7704, 2856, 720, 135, 28, 62625, 52731, 20682, 5385, 1125, 189, 36, 428319, 369969, 150282, 40914, 8730, 1620, 252, 45, 3000393, 2638332, 1104702, 309510, 68400, 12891, 2205, 324, 55

Offset: 1

R. J. Mathar, Apr 16 2016

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

			3 ;
9 6 ;
45 27 10;
246 180 54 15;
1485 1143 405 90 21;
9432 7704 2856 720 135 28;
62625 52731 20682 5385 1125 189 36;
428319 369969 150282 40914 8730 1620 252 45;
3000393 2638332 1104702 309510 68400 12891 2205 324 55;
21410436 19097802 8183943 2353989 531702 103140 17868 2880 405 66;
155106693 139921470 61122222 17954262 4140105 816858 145134 23661 3645 495 78;
1137703869 1035882315 459695791 137490273 32241834 6466053 1164978 194382 30270 4500 594 91 ;
8432624850 7737370857 3479520051 1056731244 251493255 51104574 9331833 1576062 250884 37695 5445 702 105 ;

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

Cf. A033185 (1-colored nodes), A038059 (column k=1), A006964 (row sums), A271878 (2-colored nodes).

g:= proc(n) option remember; `if`(n<2, 3*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, 3*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 *)

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

A363471 G.f. satisfies A(x) = exp( 3 * Sum_{k>=1} A(-x^k) * x^k/k ).

Original entry on oeis.org

1, 3, -3, -26, 48, 444, -920, -9126, 19587, 204214, -449496, -4841001, 10856283, 119585034, -271813440, -3044796399, 6991433415, 79341313335, -183641493481, -2105713558467, 4905239040894, 56722082044512, -132833292089826, -1546827734185557

Offset: 0

Seiichi Manyama, Jun 03 2023

sign

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A006964, A200402, A363470.

seq(n) = my(A=1); for(i=1, n, A=exp(3*sum(k=1, i, subst(A, x, -x^k)*x^k/k)+x*O(x^n))); Vec(A);

A(x) = B(x)^3 where B(x) is the g.f. of A200402.
A(x) = Sum_{k>=0} a(k) * x^k = 1/Product_{k>=0} (1-x^(k+1))^(3 * (-1)^k * a(k)).
a(0) = 1; a(n) = (3/n) * Sum_{k=1..n} ( Sum_{d|k} d * (-1)^(d-1) * a(d-1) ) * a(n-k).

A345241 G.f. A(x) satisfies: A(x) = x + x^2 * exp(3 * Sum_{k>=1} A(x^k) / k).

Original entry on oeis.org

1, 1, 3, 9, 28, 93, 315, 1109, 3969, 14505, 53726, 201588, 764001, 2921730, 11257881, 43669590, 170383933, 668236581, 2632898016, 10416893159, 41368099791, 164841324837, 658883345595, 2641064296638, 10613953319448, 42757746556377, 172628891937513, 698398635475974

Offset: 1

Ilya Gutkovskiy, Jun 11 2021

nonn

Cf. A006964, A007562, A345200, A345242.

nmax = 28; A[] = 0; Do[A[x] = x + x^2 Exp[3 Sum[A[x^k]/k, {k, 1, nmax}]] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest
a[1] = a[2] = 1; a[n_] := a[n] = (3/(n - 2)) Sum[Sum[d a[d], {d, Divisors[k]}] a[n - k], {k, 1, n - 2}]; Table[a[n], {n, 1, 28}]

G.f.: x + x^2 / Product_{n>=1} (1 - x^n)^(3*a(n)).

a(n+2) = (3/n) * Sum_{k=1..n} ( Sum_{d|k} d * a(d) ) * a(n-k+2).

A014276 Number of directed rooted trees on n nodes with forbidden limbs.

Original entry on oeis.org

0, 1, 3, 15, 82, 495, 3144, 20874, 142766, 1000083, 7136463, 51699614, 379214625, 2810720045, 21018835670, 158389275075, 1201541422730, 9168456492986, 70324572634341, 541910543713685, 4193257236992896, 32568879336517050, 253822497160605899, 1984276479881989537, 15556238037968354214, 122274773948426045945

Offset: 0

N. J. A. Sloane

nonn

T. Lu, The enumeration of trees with and without given limbs, Discr. Math., 154 (1996), 153-165, example 5.
Index entries for sequences related to rooted trees

Cf. A006964.

nmax = 30; b = ConstantArray[0, nmax+1]; b[[1]] = 0; b[[2]] = 1; Do[b[[n+1]] = SeriesCoefficient[(x-x^7-x^8+x^13) / Product[(1 - x^p)^(3*b[[p+1]]), {p, 1, n-1}], {x, 0, n}], {n, 2, nmax}]; b (* Vaclav Kotesovec, Feb 28 2016 *)

G.f. (x-x^7-x^8+x^13)/[Product_{p>=1} (1-x^p)^(3*a(p))], in implicit form. - R. J. Mathar, Feb 26 2016

A345883 G.f. A(x) satisfies: A(x) = x / exp(3 * Sum_{k>=1} A(x^k) / k).

Original entry on oeis.org

1, -3, 12, -64, 372, -2268, 14394, -94296, 632328, -4317846, 29925108, -209966748, 1488507931, -10645680858, 76717312932, -556528367791, 4060765734816, -29782931545368, 219444442931836, -1623585342758532, 12057148232386980, -89842712017158526, 671521130395037280

Offset: 1

Ilya Gutkovskiy, Jun 28 2021

sign

Cf. A006964, A045648, A052757, A345878.

a:= proc(n) option remember; `if`(n=1, 1, -3*add(a(n-k)*
      add(d*a(d), d=numtheory[divisors](k)), k=1..n-1)/(n-1))
    end:
seq(a(n), n=1..23);  # Alois P. Heinz, Jun 28 2021

nmax = 23; A[] = 0; Do[A[x] = x/Exp[3 Sum[A[x^k]/k, {k, 1, nmax}]] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest
a[1] = 1; a[n_] := a[n] = -(3/(n - 1)) Sum[Sum[d a[d], {d, Divisors[k]}] a[n - k], {k, 1, n - 1}]; Table[a[n], {n, 1, 23}]

G.f.: x * Product_{n>=1} (1 - x^n)^(3*a(n)).

a(n+1) = -(3/n) * Sum_{k=1..n} ( Sum_{d|k} d * a(d) ) * a(n-k+1).

A345885 G.f. A(x) satisfies: A(x) = x * exp(3 * Sum_{k>=1} (-1)^k * A(x^k) / k).

Original entry on oeis.org

1, -3, 15, -82, 486, -3090, 20497, -140010, 979131, -6976603, 50461716, -369533691, 2734423934, -20414010219, 153571115619, -1163003999342, 8859172575069, -67835214598017, 521824159637718, -4030828937892966, 31252886542570119, -243142210911325273, 1897466281615297698

Offset: 1

Ilya Gutkovskiy, Jun 28 2021

sign

Cf. A006964, A049075, A052757, A345884.

a:= proc(n) option remember; `if`(n=1, 1, 3*add(a(n-k)*add(d*a(d)
      *(-1)^(k/d), d=numtheory[divisors](k)), k=1..n-1)/(n-1))
    end:
seq(a(n), n=1..23); # Alois P. Heinz, Jun 28 2021

nmax = 23; A[] = 0; Do[A[x] = x Exp[3 Sum[(-1)^k A[x^k]/k, {k, 1, nmax}]] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest
a[1] = 1; a[n_] := a[n] = (3/(n - 1)) Sum[Sum[(-1)^(k/d) d a[d], {d, Divisors[k]}] a[n - k], {k, 1, n - 1}]; Table[a[n], {n, 1, 23}]

G.f.: x / Product_{n>=1} (1 + x^n)^(3*a(n)).

a(n+1) = (3/n) * Sum_{k=1..n} ( Sum_{d|k} (-1)^(k/d) * d * a(d) ) * a(n-k+1).

cp's OEIS Frontend

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

A038059 Number of rooted trees with 3-colored nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A052751 A simple grammar.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A271879 Triangle T(n,t) by rows: The number of rooted forests with n 3-colored nodes and t rooted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A363471 G.f. satisfies A(x) = exp( 3 * Sum_{k>=1} A(-x^k) * x^k/k ).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A345241 G.f. A(x) satisfies: A(x) = x + x^2 * exp(3 * Sum_{k>=1} A(x^k) / k).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A014276 Number of directed rooted trees on n nodes with forbidden limbs.

Views

Author

Keywords

Links

Crossrefs