A332959 -id:A332959 - cp's OEIS frontend

A332960 Number of labeled forests with n trees and 2n nodes and with the largest tree having exactly 3 nodes.

0, 12, 180, 5040, 151200, 6029100, 276215940, 14983768800, 919653134400, 63694663332300, 4888759865289300, 412920835111184400, 38015644799992860000, 3791220682538296507500, 407033985027273005902500, 46814497435454120812440000, 5742194963898519585098640000, 748255970051952172869045487500

Offset: 1

Washington Bomfim, Apr 15 2020

nonn

Given a forest of 2n nodes and n trees, suppose that it has c_1 trees of 1 node, c_2 trees of 2 nodes, and c_3 trees of 3 nodes. We have c_1 + c_2 + c_3 = n, and c_1 + 2c_2 + 3c_3 = 2n, so c_1 = c_3, and c_2 = n - 2c_1. Because c_2 >= 0, c_1 <= floor(n/2). In this case the first formula in A332959 (with k = 3) reduces to the first formula below.

			a(6) = 12! * ( 1 / (1!^2 * (6-2*1)! * 2^(6-1)) + 1 / (2!^2 * (6-2*2)! * 2^(6-2)) + 1 / (3!^2 * (6-2*3)! * 2^(6-3)) ) = 6029100.

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley, 2005, pp. 39.

Column k=3 of A332959.

Table[(2*n)! * (Hypergeometric2F1[1/2 - n/2, -n/2, 1, 8] - 1) / (2^n * n!), {n, 2, 20}] (* Vaclav Kotesovec, Apr 17 2020 *)

a(n)= {(2*n)! * sum(c=1, n\2, 1/(c!^2 * (n-2*c)! * 2^(n-c)))};

a(n) = (2*n)! * Sum_{c=1..floor(n/2)} 1/(c!^2 * (n-2*c)! * 2^(n-c)).
From Vaclav Kotesovec, Apr 17 2020: (Start)
a(n) ~ (2 + 4*sqrt(2))^(n + 1/2) * n^(n - 1/2) / (2^(5/4) * sqrt(Pi) * exp(n)).
a(n) ~ n! * (2 + 4*sqrt(2))^(n + 1/2) / (2^(7/4)*Pi*n). (End)

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

Original entry on oeis.org

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

Washington Bomfim, May 11 2020

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.

			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.

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

Cf. A302112, A332959, A000272, A001147, A332960.
Diagonal is A302112.
Columns k=2..3 are A001147, A001147 + A332960.

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 };

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

cp's OEIS Frontend

A332960 Number of labeled forests with n trees and 2n nodes and with the largest tree having exactly 3 nodes.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

PARI

Formula