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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A332957 Number of labeled forests with n trees and 2*n nodes without trees of order exceeding n - floor(n/4). 0
 0, 3, 195, 5145, 504945, 47896695, 4900634739, 432180333585, 57753467156385, 8322385282168815, 1297830988347128235, 195029484510994774641, 36350420770495795788825, 7233322663694914389377775, 1534057832485607065840824075 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS When n increases practically all forests do not have trees of order exceeding n - floor (n/4). See table below. n = 1 4 8 16 28 44 48 83 a(n)/A302112(n)*100 = 0.0% 27.3% 61.5% 85.8% 95.6% 98.8% 99.1% 99.94% REFERENCES D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley, 2005, pp. 39, 47. LINKS Table of n, a(n) for n=1..15. FORMULA a(n) = (2*n)! * Sum_{P(2*n,n)} Product_{p=1..2*n} f(p)^c_p / (c_p! * p!^c_p), where f(n) = A000272(n) = n^(n-2), and P(2*n,n) are the partitions of 2*n with n parts, without parts exceeding n - floor(n/4): c_1 + 2*c_2 + ... + (2*n)*c_(2*n) = 2n; c_1, c_2, ..., c_(2*n) >= 0. EXAMPLE E.g., a(4) = 5145. The partitions of 2*n = 8 with four parts, no parts exceeding n - floor(n/4) = 3 are [1*2 + 3*2], [1*1 + 2*2 + 3*1], and [2*4]. The first partition corresponds to f(1)^2*f(3)^2 / ((2!*1!^2)*(2!*3!^2)) = 1^2*3^2 / (2*2*36) = 1/16, the second corresponds to f(1)^1 * f(2)^2 * f(3)^1 / ((1!*1!^1)*(2!*2!^2)*(1!*3!^1)) = 1/16, and the last corresponds to f(2)^4 / (4!*2!^4) = 1/384. Finally 8! * (1/16 + 1/16 + 1/384)= 5145. (See formula). PROG (PARI) a(n) = { my(S=0); forpart(aa=2*n, my(D = Set(aa)); S += prod(j= 1, #D, my(p=D[j], c=#select(x-> x==p, Vec(aa))); (p^(p-2))^c / (c!* p!^c)), [1, n-n\4], [n, n]); (2*n)! * S}; (PARI) a(n)={my(p=sum(k=1, n-n\4, k^(k-2)*x^k/k!)); (2*n)!*polcoef( polcoef( exp(y*p + O(x*x^(2*n))), 2*n, x), n, y)} \\ Andrew Howroyd, Apr 10 2020 CROSSREFS Cf. A000272, A302112. Sequence in context: A257038 A202109 A230171 * A203749 A093978 A101382 Adjacent sequences: A332954 A332955 A332956 * A332958 A332959 A332960 KEYWORD nonn AUTHOR Washington Bomfim, Apr 09 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.

Last modified June 22 15:32 EDT 2024. Contains 373587 sequences. (Running on oeis4.)