|
%I M3671 N1496 #155 Sep 29 2023 11:51:22
%S 1,1,1,4,38,728,26704,1866256,251548592,66296291072,34496488594816,
%T 35641657548953344,73354596206766622208,301272202649664088951808,
%U 2471648811030443735290891264,40527680937730480234609755344896,1328578958335783201008338986845427712
%N Number of connected labeled graphs with n nodes.
%C "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 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 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 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 398-402.
%D D. G. Cantor, personal communication.
%D 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 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 518.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 7.
%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).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.1.
%D H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 78.
%H T. D. Noe, <a href="/A001187/b001187.txt">Table of n, a(n) for n = 0..50</a>
%H 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 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 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 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 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 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 138.
%H 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 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 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 E. N. Gilbert, <a href="/A001187/a001187.pdf">Enumeration of labelled graphs</a> (Annotated scanned copy)
%H 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 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 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 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 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 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 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%H R. W. Robinson, <a href="/A001187/a001187_1.pdf">First 50 terms of A1187 and A1188</a>
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LabeledGraph.html">Labeled Graph</a>
%H 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 n * 2^binomial(n, 2) = Sum_{k=1..n} binomial(n, k) * k * a(k) * 2^binomial(n-k, 2).
%F E.g.f.: 1 + log(Sum_{n>=0} 2^binomial(n, 2) * x^n / n!). - _Michael Somos_, Jun 12 2000
%e 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 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 # second Maple program:
%p a:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
%p add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*a(k), k=1..n-1)/n)
%p end:
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Aug 26 2013
%p # Alternative:
%p a := proc(n) option remember;
%p 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 end:
%p seq(a(n), n=0..16); # _Peter Luschny_, Feb 21 2023
%t 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 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 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 (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 (Sage)
%o @cached_function
%o def A001187(n):
%o if n == 0: return 1
%o 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(n) for n in (0..15)] # _Peter Luschny_, Jan 17 2016
%o (Magma)
%o m:=30;
%o f:= func< x | 1+Log( (&+[2^Binomial(n,2)*x^n/Factorial(n): n in [0..m+3]]) ) >;
%o R<x>:=PowerSeriesRing(Rationals(), m);
%o Coefficients(R!(Laplace( f(x) ))); // _G. C. Greubel_, Oct 04 2022
%Y Logarithmic transform of A006125 (labeled graphs).
%Y Row sums of triangle A062734.
%Y Cf. A053549.
%K nonn,nice,easy
%O 0,4
%A _N. J. A. Sloane_
|
