login
Number of n-colored connected graphs on n labeled nodes.
(Formerly M2141 N0852)
6

%I M2141 N0852 #42 Jan 05 2024 23:32:36

%S 1,1,2,24,912,87360,19226880,9405930240,10142439229440,

%T 24057598104207360,125180857812868300800,1422700916050060841779200,

%U 35136968950395142864227532800,1876028272361273394915958613606400,215474119792145796020405035320528076800

%N Number of n-colored connected graphs on n labeled nodes.

%C 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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%H Andrew Howroyd, <a href="/A002032/b002032.txt">Table of n, a(n) for n = 0..50</a>

%H R. C. Read, E. M. Wright, <a href="http://dx.doi.org/10.4153/CJM-1970-066-1">Colored graphs: A correction and extension</a>, Canad. J. Math. 22 1970 594-596.

%F a(n) = n!*A001187(n). - _Andrew Howroyd_, Dec 03 2018

%F 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

%F The above formula is referenced by sequences A002027-A002030, A002031. - _Andrew Howroyd_, Dec 03 2018

%t (* 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];

%t a[n_] := n! b[n];

%t Array[a, 14] (* _Jean-François Alcover_, Aug 16 2019, using _Alois P. Heinz_'s code for A001187 *)

%o (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

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

%Y Cf. A001187, A322278, A322279, A322280.

%K nonn

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Sean A. Irvine_, May 29 2013

%E Name clarified by _Andrew Howroyd_, Dec 03 2018

%E a(0)=1 prepended by _Andrew Howroyd_, Jan 05 2024