A005155 Number of degree sequences of n-node graphs. (Formerly M1886)

1, 1, 2, 8, 54, 533, 6944, 111850, 2135740, 47003045, 1168832808, 32363244260, 986532609608, 32810811179569, 1181865951824800, 45823912079507918, 1902469319507438352, 84195282530581058825, 3956365033583165905568, 196716723188140236180160

Offset

0,3

Comments

Given a simple graph, the degree sequence maps each vertex to the valence or degree of that vertex.

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.

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

Example

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

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

Prog

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

Crossrefs

Cf. A004251 for graphs up to isomorphism.

Sequence in context: A052662 A365599 A199576 * A133316 A234301 A345249

Adjacent sequences: A005152 A005153 A005154 * A005156 A005157 A005158

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

Minor edits by Vaclav Kotesovec, Mar 31 2014

Status

approved