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,1

Comments

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

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.

Example

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 ;

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

Crossrefs

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

Sequence in context: A297901 A079308 A189825 * A259476 A271363 A115399

Adjacent sequences: A271875 A271876 A271877 * A271879 A271880 A271881

Keyword

nonn,tabl

Author

R. J. Mathar, Apr 16 2016

Status

approved