A002032 Number of n-colored connected graphs on n labeled nodes.

1, 1, 2, 24, 912, 87360, 19226880, 9405930240, 10142439229440, 24057598104207360, 125180857812868300800, 1422700916050060841779200, 35136968950395142864227532800, 1876028272361273394915958613606400, 215474119792145796020405035320528076800

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Every connected graph on n nodes can be colored with n colors in exactly n! ways, so this sequence is just n! * A001187(n). - Andrew Howroyd, Dec 03 2018

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50
• R. C. Read, E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.

Crossrefs

Cf. A002027. A002028, A002029, A002030, A002031.

Cf. A001187, A322278, A322279, A322280.

Programs

Mathematica

(* b = A001187 *) b[n_] := b[n] = If[n == 0, 1, 2^(n(n-1)/2) - Sum[k* Binomial[n, k]*2^((n-k)(n-k-1)/2)*b[k], {k, 1, n-1}]/n];
a[n_] := n! b[n];
Array[a, 14] (* Jean-François Alcover, Aug 16 2019, using Alois P. Heinz's code for A001187 *)

PARI

seq(n) = {Vec(serlaplace(serlaplace(1 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, O(x*x^n))))))} \\ Andrew Howroyd, Dec 03 2018

Formula

a(n) = n!*A001187(n). - Andrew Howroyd, Dec 03 2018

Define M_0(k)=1, M_n(0)=0, M_n(k) = Sum_{r=0..n} C(n,r)*2^(r*(n-r))*M_r(k-1) [M_n(k) = A322280(n,k)], m_n(k) = M_n(k) -Sum_{r=1..n-1} C(n-1,r-1)*m_r(k)*M_{n-r}(k) [m_n(k) = A322279(n,k)], f_n(k) = Sum_{r=1..k} (-1)^(k-r)*C(k,r)*m_n(r). This sequence gives a(n) = f_n(n). - Sean A. Irvine, May 29 2013, edited Andrew Howroyd, Dec 03 2018

The above formula is referenced by sequences A002027-A002030, A002031. - Andrew Howroyd, Dec 03 2018

Extensions

More terms from Sean A. Irvine, May 29 2013

Name clarified by Andrew Howroyd, Dec 03 2018

a(0)=1 prepended by Andrew Howroyd, Jan 05 2024