|
%I #45 Jun 18 2022 14:26:41
%S 0,1,3,15,110,1080,13377,200704,3542940,72000000,1656409535,
%T 42568187904,1208912928522,37603105146880,1271514111328125,
%U 46443371157258240,1822442358054692408,76461926986744528896,3415753581721829617275
%N Number of forests with two connected components in the complete graph K_{n}.
%C Note that the above sequence is dominated by the sequence n^{n-2} (n > 0), A000272, which enumerates the number of spanning trees in K_{n} : 1, 1, 3, 16, 125, 1296, 16807, 262144, ... This is a consequence of the result in [EKT] which shows that the sequence of independent set numbers of cycle matroid of K_{n} is (strictly) monotone increasing (when n > 3).
%D W. Kook, Categories of acyclic graphs and automorphisms of free groups, Ph.D. thesis (G. Carlsson, advisor), Stanford University, 1996.
%H Vincenzo Librandi, <a href="/A083483/b083483.txt">Table of n, a(n) for n = 1..200</a>
%H N. Eaton, W. Kook, and L. Thoma, <a href="http://citeseerx.ist.psu.edu/viewdoc/citations;jsessionid=BCC4A366B3073B1A7E5529AFD4EE87DE?doi=10.1.1.330.825">Monotonicity for complete graphs</a>, preprint
%H A. Kassel, R. Kenyon, and W. Wu, <a href="https://doi.org/10.1214/14-AIHP625">Random two-component spanning forests</a>, Ann. Inst. H. Poincaré Probab. Statist., 51 (2015), 1457-1464.
%H C. J. Liu and Yutze Chow, <a href="http://dx.doi.org/10.1137/0605038">On operator and formal sum methods for graph enumeration problems</a>, SIAM J. Algebraic Discrete Methods, 5 (1984), no. 3, 384--406. MR0752043 (86d:05059). See Eq. (47). - From _N. J. A. Sloane_, Apr 09 2014
%F E.g.f.: T(x)^{2}/2!, where T(x) is the e.g.f. for the number of spanning trees in K_{n}, i.e., T(x) = Sum_{i>=1} i^(i-2)*x^i/i!.
%F E.g.f.: (1/8)*LambertW(-x)^2*(2+LambertW(-x))^2. - _Vladeta Jovovic_, Jul 08 2003
%F a(n) = n^(n-4)*(n-1)*(n+6)/2. - _Vaclav Kotesovec_, Oct 18 2013
%p f:=n->(n-1)!*n^(n-4)*(n+6)/(2*(n-2)!); [seq(f(n),n=2..30)]; # _N. J. A. Sloane_, Apr 09 2014
%t (* first 20 terms starting with n=1 *) T := Sum[i^(i - 2)*(x^i)/i!, {i, 1, 20}]; T2 := Expand[(T^{2})/2! ]; C2[i_] := Coefficient[T2, x^{i}]*i!; M := MatrixForm[Table[C2[i], {i, 20}]]; M
%t Table[n^(n - 4) (n - 1) (n + 6)/2, {n, 1, 40}] (* _Vincenzo Librandi_, Apr 10 2014 *)
%o (Magma) [n^(n-4)*(n-1)*(n+6)/2 : n in [1..20]]; // _Vincenzo Librandi_, Apr 10 2014
%o (PARI) for(n=1,30, print1(n^(n-4)*(n-1)*(n+6)/2, ", ")) \\ _G. C. Greubel_, Nov 14 2017
%Y Cf. A000272, A053506, A239910.
%Y Column m=2 of A105599. A diagonal of A138464. - _Alois P. Heinz_, Apr 10 2014
%K nonn
%O 1,3
%A Woong Kook (andrewk(AT)math.uri.edu), Jun 08 2003
%E Edited by _N. J. A. Sloane_, Apr 09 2014
|
