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

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

Author

R. J. Mathar, Apr 16 2016

Keywords

• nonn
• tabl

Comments

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

Examples

			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 ;
		

Links

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

Crossrefs

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

Programs

Maple

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

Mathematica

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