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

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

Author

R. J. Mathar, Apr 16 2016

Keywords

• nonn
• tabl

Comments

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

Examples

			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 ;
		

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

Crossrefs

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

Programs

Maple

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

Mathematica

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