login
This site is supported by donations to The OEIS Foundation.
Logo

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001187 Number of connected labeled graphs with n nodes.
(Formerly M3671 N1496)
34
1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344, 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

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]

REFERENCES

Matthias Beck, Benjamin Braun and Nguyen Le, Mahonian partition identities via polyhedral geometry, arXiv:1103.1070, 2011. - from N. J. A. Sloane, Dec 29 2012

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). - From N. J. A. Sloane, Apr 06 2012

E. N. Gilbert, Enumeration of labeled graphs, Canad. J. Math., 8 (1956), 405-411.

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.

M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections, http://www.math.ucla.edu/~pak/papers/CayleyComp4.pdf. - From N. J. A. Sloane, Dec 22 2012

Nijenhuis, Albert; Wilf, Herbert S. 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, 2012. - From N. J. A. Sloane, Oct 15 2012

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

Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 138

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.

FORMULA

n*2^binomial(n, 2) = Sum_k binomial(n, k)*k*a(k)*2^binomial(n-k, 2).

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

EXAMPLE

1 + x + x^2 + 4*x^3 + 38*x^4 + 728*x^5 + 26704*x^6 + 1866256*x^7 + 251548592*x^8 + ...

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);

MATHEMATICA

g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, 20}]; Range[0, 20]! CoefficientList[Series[Log[g] + 1, {x, 0, 20}], x] (*Geoffrey Critzer, Nov 12 2011*)

PROG

(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 */

CROSSREFS

Logarithmic transform of A006125 (labeled graphs). Cf. A053549.

Row sums of triangle A062734.

Sequence in context: A084284 A084285 A084286 * A093377 A178017 A131591

Adjacent sequences:  A001184 A001185 A001186 * A001188 A001189 A001190

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane.

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified May 21 07:04 EDT 2013. Contains 225477 sequences.