login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..33.

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

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

Diagonal is A302112.

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

Sequence in context: A074043 A120467 A323499 * A012634 A043060 A029476

Adjacent sequences:  A332958 A332959 A332960 * A332962 A332963 A332964

KEYWORD

nonn,tabl,easy

AUTHOR

Washington Bomfim, May 11 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 6 04:31 EDT 2022. Contains 355108 sequences. (Running on oeis4.)