|
|
A001187
|
|
Number of connected labeled graphs with n nodes.
(Formerly M3671 N1496)
|
|
121
|
|
|
1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344, 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896, 1328578958335783201008338986845427712
(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]
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
|
|
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
|
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
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.
|
|
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
|
|
EXAMPLE
|
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! + ...
|
|
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:
# 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:
|
|
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 *)
|
|
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 */
(Sage)
@cached_function
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
(Magma)
m:=30;
f:= func< x | 1+Log( (&+[2^Binomial(n, 2)*x^n/Factorial(n): n in [0..m+3]]) ) >;
R<x>:=PowerSeriesRing(Rationals(), m);
|
|
CROSSREFS
|
Logarithmic transform of A006125 (labeled graphs).
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|