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

1, 3, 15, 15, 195, 435, 105, 5145, 11865, 18865, 945, 152145, 504945, 819945, 1092105, 10395, 6039495, 27106695, 47896695, 65859255, 79170399, 135135, 276351075, 1663737075, 3429501075, 4900634739, 6111948843, 6899167275, 2027025, 14985795825, 120931635825, 286156695825, 432180333585

Offset: 1

Author

Washington Bomfim, May 11 2020

Keywords

• nonn
• tabl
• easy

Comments

The first formula is based on Kolchin's formula (1.4.2) [see the Kolchin reference].

Let S be the set of labeled forests with n trees and 2n nodes.

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.

The percentages goes to 61%, 83%, and 100% respectively for (5/7)*(n+1) nodes, (6/7)*(n+1) nodes, and n+1 nodes.

Examples

			Triangle T(n,k) begins:
      1;
      3,      15;
     15,     195,      435;
    105,    5145,    11865,    18865;
    945,  152145,   504945,   819945,  1092105;
  10395, 6039495, 27106695, 47896695, 65859255, 79170399;
  ...
The graphs for T(2,2) and T(2,3) are illustrated below:
   o---o   :   o---o     o   o
           :             |
   o---o   :   o---o     o---o
T(2,2) = 3 since the first graph on the left has 3 labelings.
T(2,3) = 15 since the first graph has 3 labelings, and the second has 12 labelings.
		

References

• V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.

Crossrefs

Cf. A302112, A332959, A000272, A001147, A332960.

Diagonal is A302112.

Columns k=2..3 are A001147, A001147 + A332960.

Programs

PARI

T(n,k) = { my(S = 0, D, p, c);
forpart(a = 2*n, D = Set(a);
   S += prod(j=1,#D, p=D[j]; c=#select(x-> x==p,Vec(a)); (p^(p-2)/p!)^c /c!)
, [1, k], [n, n]); (2*n)! * S };

Formula

T[n,k] = Sum_{j=2..k} (T1[n,j]), where T1[n,j] is the triangle A332959.

T(n,k) = ((2*n)!/n!) * Sum_{compositions p_1 + ... + p_n = 2*n, 1 <= p_i <= k}

Product_{j=1..n} f(p_j) / p_j!, where f(p_j) = A000272(p_j) = p_j^(p_j-2).