cp's OEIS Frontend

A332961 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 at most k nodes, (n>=1, 2<=k<=n+1).

%I A332961 #12 Jul 20 2020 13:08:42
%S A332961 1,3,15,15,195,435,105,5145,11865,18865,945,152145,504945,819945,
%T A332961 1092105,10395,6039495,27106695,47896695,65859255,79170399,135135,
%U A332961 276351075,1663737075,3429501075,4900634739,6111948843,6899167275,2027025,14985795825,120931635825,286156695825,432180333585
%N A332961 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 at most k nodes, (n>=1, 2<=k<=n+1).
%C A332961 The first formula is based on Kolchin's formula (1.4.2) [see the Kolchin reference].
%C A332961 Let S be the set of labeled forests with n trees and 2n nodes.
%C A332961 We know that the largest trees in S have n+1 nodes. It follows from line n=6 of the triangle that more than 33% of the forests in S do not have trees with more than 4/7*(n+1) nodes.
%C A332961 The percentages goes to 61%, 83%, and 100% respectively for (5/7)*(n+1) nodes, (6/7)*(n+1) nodes, and n+1 nodes.
%D A332961 V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.
%F A332961 T[n,k] = Sum_{j=2..k} (T1[n,j]), where T1[n,j] is the triangle A332959.
%F A332961 T(n,k) = ((2*n)!/n!) * Sum_{compositions p_1 + ... + p_n = 2*n, 1 <= p_i <= k}
%F A332961 Product_{j=1..n} f(p_j) / p_j!, where f(p_j) = A000272(p_j) = p_j^(p_j-2).
%e A332961 Triangle T(n,k) begins:
%e A332961       1;
%e A332961       3,      15;
%e A332961      15,     195,      435;
%e A332961     105,    5145,    11865,    18865;
%e A332961     945,  152145,   504945,   819945,  1092105;
%e A332961   10395, 6039495, 27106695, 47896695, 65859255, 79170399;
%e A332961   ...
%e A332961 The graphs for T(2,2) and T(2,3) are illustrated below:
%e A332961    o---o   :   o---o     o   o
%e A332961            :             |
%e A332961    o---o   :   o---o     o---o
%e A332961 T(2,2) = 3 since the first graph on the left has 3 labelings.
%e A332961 T(2,3) = 15 since the first graph has 3 labelings, and the second has 12 labelings.
%o A332961 (PARI) T(n,k) = { my(S = 0, D, p, c);
%o A332961 forpart(a = 2*n, D = Set(a);
%o A332961    S += prod(j=1,#D, p=D[j]; c=#select(x-> x==p,Vec(a)); (p^(p-2)/p!)^c /c!)
%o A332961 , [1, k], [n, n]); (2*n)! * S };
%Y A332961 Cf. A302112, A332959, A000272, A001147, A332960.
%Y A332961 Diagonal is A302112.
%Y A332961 Columns k=2..3 are A001147, A001147 + A332960.
%K A332961 nonn,tabl,easy
%O A332961 1,2
%A A332961 _Washington Bomfim_, May 11 2020