A239910 Number of forests with three connected components in the complete graph K_{n}.

0, 0, 1, 6, 45, 435, 5250, 76608, 1316574, 26100000, 587030895, 14780620800, 412069511139, 12604714327296, 419801484375000, 15123782440058880, 586049426860524300, 24307340986526810112, 1074495780444130114509, 50429952000000000000000

Offset: 1

Author

N. J. A. Sloane, Apr 09 2014

Keywords

• nonn

Comments

Equation (47) of Liu-Chow (1984) also gives the analogous formulas for four and five components. (They should also be entered into the OEIS, in case someone wants to help.)

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..200
• C. J. Liu and Yutze Chow, On operator and formal sum methods for graph enumeration problems, SIAM J. Algebraic Discrete Methods, 5 (1984), no. 3, 384-406. MR0752043 (86d:05059).

Crossrefs

Cf. A000272, A083483.

Column m=3 of A105599. A diagonal of A138464. - Alois P. Heinz, Apr 10 2014

Programs

Magma

[(n-1)*(n-2)*n^(n-6)*(n^2+13*n+60)/8: n in [1..20]]; // Vincenzo Librandi, Apr 10 2014

Maple

f := n-> (n-1)*(n-2)*n^(n-6)*(n^2+13*n+60)/8; [seq(f(n),n=3..20)];

Mathematica

Table[(n-1)*(n-2) * n^(n - 6) * (n^2 + 13 n + 60)/8, {n, 1, 20}] (* Vincenzo Librandi, Apr 10 2014, simplified by Vaclav Kotesovec, Feb 20 2020 *)

Formula

From Harry Richman, Aug 17 2022: (Start)

a(n) = n^(n-6)*(n-1)*(n-2)*(n^2+13*n+60)/8.

E.g.f.: T(x)^{3}/3!, where T(x) is the e.g.f. for the number of spanning trees in K_{n} A000272, i.e., T(x) = Sum_{i>=1} i^(i-2)*x^i/i!. (End)