cp's OEIS Frontend

A332959 Triangle read by rows: T(n,k) is the number of labeled forests with n trees and 2n nodes and with the largest tree having exactly k nodes, (n >= 1, 2 <= k <= n+1).

%I A332959 #67 May 17 2020 13:49:47
%S A332959 1,3,12,15,180,240,105,5040,6720,7000,945,151200,352800,315000,272160,
%T A332959 10395,6029100,21067200,20790000,17962560,13311144,135135,276215940,
%U A332959 1387386000,1765764000,1471133664,1211314104,787218432,2027025,14983768800,105945840000,165225060000,146023637760,121131410400,94466211840,54717165360
%N A332959 Triangle read by rows: T(n,k) is the number of labeled forests with n trees and 2n nodes and with the largest tree having exactly k nodes, (n >= 1, 2 <= k <= n+1).
%C A332959 The first formula is based on Kolchin's formula (1.4.2) [see the Kolchin reference].
%D A332959 V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.
%H A332959 Andrew Howroyd, <a href="/A332959/b332959.txt">Table of n, a(n) for n = 1..1275</a> (first 50 rows)
%F A332959 T(n,k) = ((2*n)!/n!) * Sum_{compositions p_1 + ... + p_n = 2*n, 1 <= p_i <= k}
%F A332959   Product_{j=1..n} f(p_j) / p_j!, where f(p_j) = A000272(p_j) = p_j^(p_j-2).
%e A332959 Triangle T(n,k) begins:
%e A332959       1;
%e A332959       3,      12;
%e A332959      15,     180,      240;
%e A332959     105,    5040,     6720,     7000;
%e A332959     945,  151200,   352800,   315000,   272160;
%e A332959   10395, 6029100, 21067200, 20790000, 17962560, 13311144;
%e A332959   ...
%e A332959 The graphs for T(2,2) and T(2,3) are illustrated below:
%e A332959    o---o   :   o   o
%e A332959            :   |
%e A332959    o---o   :   o---o
%e A332959 T(2,2) = 3 since the graph on the left has 3 labelings.
%e A332959 T(2,3) = 12 since the graph on the right has 12 labelings.
%o A332959 (PARI)
%o A332959 T(n, k) = { my(S = 0);
%o A332959   forpart(a = 2*n,
%o A332959     if(a[n] == k,
%o A332959       my(D = Set(a));
%o A332959       my(Pr = prod(j=1, #D, my(p = D[j], c = #select(x->x==p, Vec(a))); p^((p-2)*c) / (p!^c*c!)));
%o A332959        S += n!*Pr )
%o A332959   , [1, k], [n, n]); (2*n)! / n! * S };
%o A332959 (PARI)
%o A332959 B(n,k)={my(p=sum(j=1, k, j^(j-2)*x^j/j!)); (2*n)!*polcoef( polcoef( exp(y*p + O(x*x^(2*n))), 2*n, x), n, y)}
%o A332959 T(n,k)={B(n,k)-B(n,k-1)} \\ _Andrew Howroyd_, May 08 2020
%Y A332959 Columns k=2..3 are A001147, A332960.
%Y A332959 Row sums give A302112.
%Y A332959 Main diagonal is A332958.
%Y A332959 Cf. A000272, A001147, A302112, A332958, A332960.
%K A332959 nonn,tabl,easy
%O A332959 1,2
%A A332959 _Washington Bomfim_, Apr 13 2020