|
|
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).
|
|
0
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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.
|
|
REFERENCES
|
V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.
|
|
LINKS
|
|
|
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).
|
|
EXAMPLE
|
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.
|
|
PROG
|
(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 };
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|