cp's OEIS Frontend

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

%I A271878 #18 Nov 10 2017 05:55:21
%S A271878 2,4,3,14,8,4,52,38,12,5,214,160,62,16,6,916,741,288,86,20,7,4116,
%T A271878 3416,1408,416,110,24,8,18996,16270,6856,2110,544,134,28,9,89894,
%U A271878 78408,34036,10576,2812,672,158,32,10,433196,384033,169936,53892,14352
%N A271878 Triangle T(n,t) read by rows: number of rooted forests with n 2-colored nodes and t rooted trees.
%C A271878 See eq. (27) of the reference for a recurrence.
%H A271878 Alois P. Heinz, <a href="/A271878/b271878.txt">Rows n = 1..141, flattened</a>
%H A271878 R. J. Mathar, <a href="http://arxiv.org/abs/1603.00077">Topologically distinct sets of non-intersecting circles in the plane</a>, arXiv:1603:00077 [math.CO] (2016), Table 3.
%e A271878 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)).
%e A271878 2 ;
%e A271878 4 3;
%e A271878 14 8 4;
%e A271878 52 38 12 5;
%e A271878 214 160 62 16 6;
%e A271878 916 741 288 86 20 7 ;
%e A271878 4116 3416 1408 416 110 24 8;
%e A271878 18996 16270 6856 2110 544 134 28 9 ;
%e A271878 89894 78408 34036 10576 2812 672 158 32 10;
%e A271878 433196 384033 169936 53892 14352 3514 800 182 36 11;
%e A271878 2119904 1901968 856902 275264 74238 18128 4216 928 206 40 12;
%e A271878 10503612 9519710 4350520 1416051 384512 94668 21904 4918 1056 230 44 13;
%e A271878 52594476 48061472 22238446 7317080 2002850 494544 115098 25680 5620 1184 254 48 14 ;
%p A271878 g:= proc(n) option remember; `if`(n<2, 2*n, (add(add(d*g(d),
%p A271878        d=numtheory[divisors](j))*g(n-j), j=1..n-1))/(n-1))
%p A271878     end:
%p A271878 b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
%p A271878       `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j)*
%p A271878        binomial(g(i)+j-1, j), j=0..min(n/i, p)))))
%p A271878     end:
%p A271878 T:= (n, k)-> b(n$2, k):
%p A271878 seq(seq(T(n, k), k=1..n), n=1..14);  # _Alois P. Heinz_, Apr 13 2017
%t A271878 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)];
%t A271878 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 A271878 T[n_, k_] := b[n, n, k];
%t A271878 Table[Table[T[n, k], {k, 1, n}], {n, 1, 14}] // Flatten (* _Jean-François Alcover_, Nov 10 2017, after _Alois P. Heinz_ *)
%Y A271878 Cf. A033185 (1-colored nodes), A038055 (column k=1), A000151 (row sums), A271879 (3-colored nodes)
%K A271878 nonn,tabl
%O A271878 1,1
%A A271878 _R. J. Mathar_, Apr 16 2016