A005155 Number of degree sequences of n-node graphs.
1, 1, 2, 8, 54, 533, 6944, 111850, 2135740, 47003045, 1168832808, 32363244260, 986532609608, 32810811179569, 1181865951824800, 45823912079507918, 1902469319507438352, 84195282530581058825, 3956365033583165905568, 196716723188140236180160
Offset: 0
Examples
1 + x + 2*x^2 + 8*x^3 + 54*x^4 + 533*x^5 + 6944*x^6 + 111850*x^7 + 2135740*x^8 + ...
a(3)=8 because we have: {0, 0, 0}, {0, 1, 1}, {1, 0, 1}, {1, 1, 0}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {2, 2, 2}. - _Geoffrey Critzer_, Aug 24 2016
References
- 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 Problem 5.16.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..386 (first 101 terms from James Spahlinger)
- R. Simion, Convex Polytopes and Enumeration, Adv. in Appl. Math. 18 (1997) pp. 149-180.
- R. P. Stanley, A zonotope associated with graphical degree sequences, in Applied Geometry and Discrete Combinatorics. DIMACS Series in Discrete Math., Amer. Math. Soc., Vol. 4, pp. 555-570, 1991.
- Kai Wang, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016, p. 2 and p. 13.
Crossrefs
Cf. A004251 for graphs up to isomorphism.
Programs
-
Mathematica
max = 18; w = ProductLog; f[x_] := (Sqrt[(1 - w[-x])/(1 + w[-x])] - w[-x]/x)*(Exp[-w[-x]^2/2]/ 2); CoefficientList[ Series[f[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Dec 12 2011, after Vladeta Jovovic *) -
PARI
{a(n) = local(A, B, C); if( n<0, 0, A = sum( k=1, n, k^k * x^k / k!, x * O(x^n)); B = intformal( 1 + A); C = intformal( 1 / (1 - B)); n! * polcoeff( (1 + (1 - B) * sqrt(1 + 2*A)) / 2 * exp(C), n))} /* Michael Somos, Aug 19 2005 */
Formula
There is an explicit formula and e.g.f.
E.g.f.: (sqrt((1-LambertW(-x))/(1+LambertW(-x)))-LambertW(-x)/x)*exp(-LambertW(-x)^2/2)/2. - Vladeta Jovovic, Jun 21 2007
a(n) ~ Gamma(3/4) * n^(n-1/4) / (2^(3/4) * exp(1/2) * sqrt(Pi)) * (1 - 11*Pi/(24*Gamma(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Jul 09 2013
Extensions
Minor edits by Vaclav Kotesovec, Mar 31 2014
Comments