A001187 Number of connected labeled graphs with n nodes.

1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344, 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896, 1328578958335783201008338986845427712

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy
• changed

Comments

"Based on experimental data obtained using the software LattE [14] and the Online Encyclopedia of Integer Sequences [19], we make the following conjecture: Conjecture 11. For j >= 2, Vol(C_j ) is equal to the number of labeled connected graphs on j - 1 vertices." [Beck et al., 2011]

For n > 1, a(n) is log-convex. Furthermore, a(n+1)*a(n-1) ~ 2*a(n)*a(n). - Ran Pan, Oct 28 2015

a(n) is also the number of tournaments on {1,...,n} for which 1 is reachable from every vertex. - Don Knuth, Aug 06 2020

Examples

			E.g.f.: 1 + x + x^2/2! + 4*x^3/3! + 38*x^4/4! + 728*x^5/5! + 26704*x^6/6! + 1866256*x^7/7! + 251548592*x^8/8! + ...
		

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 398-402.
• D. G. Cantor, personal communication.
• Cowan, D. D.; Mullin, R. C.; Stanton, R. G. Counting algorithms for connected labelled graphs. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 225-236. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0414417 (54 #2519).
• J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 518.
• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 7.
• 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).
• R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.1.
• H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 78.

Links

• T. D. Noe, Table of n, a(n) for n = 0..50
• Matthias Beck, Benjamin Braun and Nguyen Le, Mahonian partition identities via polyhedral geometry, arXiv:1103.1070 [math.NT], 2011.
• Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, MS Thesis, 2002.
• Marco Coraggio and Mario di Bernardo, Data-driven design of complex network structures to promote synchronization, arXiv:2309.10941 [eess.SY], 2023.
• Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.
• Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 138.
• Philippe Fournier Viger, Ganghuan He, Chun-Wei Jerry Lin, and Heitor Murilo Gomes, Mining Attribute Evolution Rules in Dynamic Attributed Graphs, Proceedings of the Big Data Analytics and Knowledge Discovery, 22nd International Conference, (Bratislava, Slovakia, DaWaK 2020).
• Adriano M. Garsia, James Haglund, Dun Qiu, and Marino Romero, e-Positivity Results and Conjectures, arXiv:1904.07912 [math.CO], 2019.
• E. N. Gilbert, Enumeration of labelled graphs, Canad. J. Math., 8 (1956), 405-411.
• E. N. Gilbert, Enumeration of labelled graphs (Annotated scanned copy)
• Markus Kirchweger and Stefan Szeider, SAT Modulo Symmetries for Graph Generation and Enumeration, ACM Trans. Comput. Logic (2024). See p. 27.
• M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections, preprint.
• M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91.
• Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 32.
• Arun P. Mani and R. J. Stones, The Number of Labeled Connected Graphs Modulo Prime Powers, SIAM Journal on Discrete Mathematics, Vol. 30, No. 2, pp. 1046-1057.
• Alexey A. Melnikov, Leonid E. Fedichkin, Ray-Kuang Lee, and Alexander Alodjants, Machine learning transfer efficiencies for noisy quantum walks, arXiv:2001.05472 [quant-ph], 2020. Also in Advanced Quantum Technologies (2020) Vol. 3, 1900115.
• Albert Nijenhuis and Herbert S. Wilf, The enumeration of connected graphs and linked diagrams, J. Combin. Theory Ser. A 27 (1979), no. 3, 356--359. MR0555804 (82b:05074)
• J. Novak, Three lectures on free probability, arXiv preprint arXiv:1205.2097 [math.CO], 2012.
• Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
• R. W. Robinson, First 50 terms of A1187 and A1188
• N. J. A. Sloane, Transforms
• Eric Weisstein's World of Mathematics, Connected Graph
• Eric Weisstein's World of Mathematics, Labeled Graph
• H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 87, Eq. 3.10.2.

Crossrefs

Logarithmic transform of A006125 (labeled graphs).

Row sums of triangle A062734.

Cf. A053549.

Programs

Magma

m:=30;
f:= func< x | 1+Log( (&+[2^Binomial(n,2)*x^n/Factorial(n): n in [0..m+3]]) ) >;
R:=PowerSeriesRing(Rationals(), m);
Coefficients(R!(Laplace( f(x) ))); // G. C. Greubel, Oct 04 2022

Maple

t1 := 1+log( add(2^binomial(n,2)*x^n/n!,n=0..30)): t2 := series(t1,x,30): A001187 := n->n!*coeff(t2,x,n);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
      add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*a(k), k=1..n-1)/n)
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 26 2013
# Alternative:
a := proc(n) option remember;
    2^((n-1)*n/2) - add(binomial(n-1, k)*2^((k-n+1)*(k-n+2)/2)*a(k+1), k=0..n-2)
end:
seq(a(n), n=0..16); # Peter Luschny, Feb 21 2023

Mathematica

m:=20; g = Sum[2^Binomial[n, 2] x^n/n!, {n,0,m}]; Range[0,m]! CoefficientList[Series[Log[g] +1, {x,0,m}], x] (* Geoffrey Critzer, Nov 12 2011 *)
a[n_]:= a[n]= If[n==0, 1, 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]* 2^((n-k)*(n-k-1)/2)*a[k], {k,1,n-1}]/n]; Table[a[n], {n,0,20}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *)
a[ n_]:= If[n<0, 0, n! SeriesCoefficient[1 +Log[ Sum[2^(k(k-1)/2) x^k/k!, {k,0, n}]], {x, 0, n}]]; (* Michael Somos, Jul 11 2019 *)

PARI

{a(n) = if(n<0, 0, n! * polcoeff( 1 + log( sum( k=0, n, 2^binomial(k, 2) * x^k / k!, x * O(x^n))), n))}; /* Michael Somos, Jun 12 2000 */

Python

from functools import lru_cache
import gmpy2
@lru_cache(None)
def A001187(n):
  if n == 0:
    return 1
  s = gmpy2.mpz(0)
  for k in range(1, n):
    s += k * gmpy2.comb(n, k) * 2**((n - k)*(n - k - 1)//2) * A001187(k)
  return 2**(n*(n-1)//2) - s // n # John Reimer Morales, Aug 15 2025

Sage

@cached_function
def A001187(n):
    if n == 0: return 1
    return 2^(n*(n-1)/2)- sum(k*binomial(n, k)*2^((n-k)*(n-k-1)/2)*A001187(k) for k in (1..n-1))/n
[A001187(n) for n in (0..15)] # Peter Luschny, Jan 17 2016

Formula

n * 2^binomial(n, 2) = Sum_{k=1..n} binomial(n, k) * k * a(k) * 2^binomial(n-k, 2).

E.g.f.: 1 + log(Sum_{n>=0} 2^binomial(n, 2) * x^n / n!). - Michael Somos, Jun 12 2000