cp's OEIS Frontend

A001187 Number of connected labeled graphs with n nodes.

%I A001187 M3671 N1496 #179 Aug 20 2025 22:11:44
%S A001187 1,1,1,4,38,728,26704,1866256,251548592,66296291072,34496488594816,
%T A001187 35641657548953344,73354596206766622208,301272202649664088951808,
%U A001187 2471648811030443735290891264,40527680937730480234609755344896,1328578958335783201008338986845427712
%N A001187 Number of connected labeled graphs with n nodes.
%C A001187 "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]
%C A001187 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
%C A001187 a(n) is also the number of tournaments on {1,...,n} for which 1 is reachable from every vertex. - _Don Knuth_, Aug 06 2020
%D A001187 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 398-402.
%D A001187 D. G. Cantor, personal communication.
%D A001187 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).
%D A001187 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 518.
%D A001187 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 7.
%D A001187 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001187 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001187 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.1.
%D A001187 H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 78.
%H A001187 T. D. Noe, <a href="/A001187/b001187.txt">Table of n, a(n) for n = 0..50</a>
%H A001187 Matthias Beck, Benjamin Braun and Nguyen Le, <a href="http://arxiv.org/abs/1103.1070">Mahonian partition identities via polyhedral geometry</a>, arXiv:1103.1070 [math.NT], 2011.
%H A001187 Huantian Cao, <a href="https://getd.libs.uga.edu/pdfs/cao_huantian_200205_ms.pdf">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, MS Thesis, 2002.
%H A001187 Marco Coraggio and Mario di Bernardo, <a href="https://arxiv.org/abs/2309.10941">Data-driven design of complex network structures to promote synchronization</a>, arXiv:2309.10941 [eess.SY], 2023.
%H A001187 Patrick De Causmaecker and Stefan De Wannemacker, <a href="http://arxiv.org/abs/1407.4288">On the number of antichains of sets in a finite universe</a>, arXiv:1407.4288 [math.CO], 2014.
%H A001187 Steven R. Finch, <a href="https://doi.org/10.1017/9781316997741">Mathematical Constants II</a>, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
%H A001187 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 138.
%H A001187 Philippe Fournier Viger, Ganghuan He, Chun-Wei Jerry Lin, and Heitor Murilo Gomes, <a href="https://doi.org/10.1007/978-3-030-59065-9_14">Mining Attribute Evolution Rules in Dynamic Attributed Graphs</a>, Proceedings of the Big Data Analytics and Knowledge Discovery, 22nd International Conference, (Bratislava, Slovakia, DaWaK 2020).
%H A001187 Adriano M. Garsia, James Haglund, Dun Qiu, and Marino Romero, <a href="https://arxiv.org/abs/1904.07912">e-Positivity Results and Conjectures</a>, arXiv:1904.07912 [math.CO], 2019.
%H A001187 E. N. Gilbert, <a href="http://dx.doi.org/10.4153/CJM-1956-046-2">Enumeration of labelled graphs</a>, Canad. J. Math., 8 (1956), 405-411.
%H A001187 E. N. Gilbert, <a href="/A001187/a001187.pdf">Enumeration of labelled graphs</a> (Annotated scanned copy)
%H A001187 Markus Kirchweger and Stefan Szeider, <a href="https://doi.org/10.1145/3670405">SAT Modulo Symmetries for Graph Generation and Enumeration</a>, ACM Trans. Comput. Logic (2024). See p. 27.
%H A001187 M. Konvalinka and I. Pak, <a href="https://www.math.ucla.edu/~pak/papers/CayleyComp7.pdf">Cayley compositions, partitions, polytopes, and geometric bijections</a>, preprint.
%H A001187 M. Konvalinka and I. Pak, <a href="https://doi.org/10.1016/j.jcta.2013.11.008">Cayley compositions, partitions, polytopes, and geometric bijections</a>, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91.
%H A001187 Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, <a href="https://arxiv.org/abs/2407.11877">Bridging Weighted First Order Model Counting and Graph Polynomials</a>, arXiv:2407.11877 [cs.LO], 2024. See p. 32.
%H A001187 Arun P. Mani and R. J. Stones, <a href="https://doi.org/10.1137/15M1024615">The Number of Labeled Connected Graphs Modulo Prime Powers</a>, SIAM Journal on Discrete Mathematics, Vol. 30, No. 2, pp. 1046-1057.
%H A001187 Alexey A. Melnikov, Leonid E. Fedichkin, Ray-Kuang Lee, and Alexander Alodjants, <a href="https://arxiv.org/abs/2001.05472">Machine learning transfer efficiencies for noisy quantum walks</a>, arXiv:2001.05472 [quant-ph], 2020. Also in <a href="https://doi.org/10.1002/qute.201900115">Advanced Quantum Technologies</a> (2020) Vol. 3, 1900115.
%H A001187 Albert Nijenhuis and Herbert S. Wilf, <a href="http://dx.doi.org/10.1016/0097-3165(79)90023-2">The enumeration of connected graphs and linked diagrams</a>, J. Combin. Theory Ser. A 27 (1979), no. 3, 356--359. MR0555804 (82b:05074)
%H A001187 J. Novak, <a href="http://arxiv.org/abs/1205.2097">Three lectures on free probability</a>, arXiv preprint arXiv:1205.2097 [math.CO], 2012.
%H A001187 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%H A001187 R. W. Robinson, <a href="/A001187/a001187_1.pdf">First 50 terms of A1187 and A1188</a>
%H A001187 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A001187 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>
%H A001187 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LabeledGraph.html">Labeled Graph</a>
%H A001187 H. S. Wilf, <a href="http://www.math.upenn.edu/~wilf/DownldGF.html">Generatingfunctionology</a>, 2nd edn., Academic Press, NY, 1994, p. 87, Eq. 3.10.2.
%F A001187 n * 2^binomial(n, 2) = Sum_{k=1..n} binomial(n, k) * k * a(k) * 2^binomial(n-k, 2).
%F A001187 E.g.f.: 1 + log(Sum_{n>=0} 2^binomial(n, 2) * x^n / n!). - _Michael Somos_, Jun 12 2000
%e A001187 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! + ...
%p A001187 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);
%p A001187 # second Maple program:
%p A001187 a:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
%p A001187       add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*a(k), k=1..n-1)/n)
%p A001187     end:
%p A001187 seq(a(n), n=0..20);  # _Alois P. Heinz_, Aug 26 2013
%p A001187 # Alternative:
%p A001187 a := proc(n) option remember;
%p A001187     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)
%p A001187 end:
%p A001187 seq(a(n), n=0..16); # _Peter Luschny_, Feb 21 2023
%t A001187 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 *)
%t A001187 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_ *)
%t A001187 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 *)
%o A001187 (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 */
%o A001187 (Sage)
%o A001187 @cached_function
%o A001187 def A001187(n):
%o A001187     if n == 0: return 1
%o A001187     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
%o A001187 [A001187(n) for n in (0..15)] # _Peter Luschny_, Jan 17 2016
%o A001187 (Magma)
%o A001187 m:=30;
%o A001187 f:= func< x | 1+Log( (&+[2^Binomial(n,2)*x^n/Factorial(n): n in [0..m+3]]) ) >;
%o A001187 R<x>:=PowerSeriesRing(Rationals(), m);
%o A001187 Coefficients(R!(Laplace( f(x) ))); // _G. C. Greubel_, Oct 04 2022
%o A001187 (Python)
%o A001187 from functools import lru_cache
%o A001187 import gmpy2
%o A001187 @lru_cache(None)
%o A001187 def A001187(n):
%o A001187   if n == 0:
%o A001187     return 1
%o A001187   s = gmpy2.mpz(0)
%o A001187   for k in range(1, n):
%o A001187     s += k * gmpy2.comb(n, k) * 2**((n - k)*(n - k - 1)//2) * A001187(k)
%o A001187   return 2**(n*(n-1)//2) - s // n # _John Reimer Morales_, Aug 15 2025
%Y A001187 Logarithmic transform of A006125 (labeled graphs).
%Y A001187 Row sums of triangle A062734.
%Y A001187 Cf. A053549.
%K A001187 nonn,nice,easy
%O A001187 0,4
%A A001187 _N. J. A. Sloane_