A005155 - OEIS

%I M1886 #57 Oct 27 2023 22:07:51

%S 1,1,2,8,54,533,6944,111850,2135740,47003045,1168832808,32363244260,

%T 986532609608,32810811179569,1181865951824800,45823912079507918,

%U 1902469319507438352,84195282530581058825,3956365033583165905568,196716723188140236180160

%N Number of degree sequences of n-node graphs.

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

%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 Problem 5.16.

%H Alois P. Heinz, <a href="/A005155/b005155.txt">Table of n, a(n) for n = 0..386</a> (first 101 terms from James Spahlinger)

%H R. Simion, <a href="http://dx.doi.org/10.1006/aama.1996.0505">Convex Polytopes and Enumeration</a>, Adv. in Appl. Math. 18 (1997) pp. 149-180.

%H R. P. Stanley, <a href="http://math.mit.edu/~rstan/pubs/pubfiles/83.pdf">A zonotope associated with graphical degree sequences</a>, in Applied Geometry and Discrete Combinatorics. DIMACS Series in Discrete Math., Amer. Math. Soc., Vol. 4, pp. 555-570, 1991.

%H Kai Wang, <a href="http://arxiv.org/abs/1604.04148">Efficient Counting of Degree Sequences</a>, arXiv:1604.04148 [math.CO], 2016, p. 2 and p. 13.

%F There is an explicit formula and e.g.f.

%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

%F 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

%e 1 + x + 2*x^2 + 8*x^3 + 54*x^4 + 533*x^5 + 6944*x^6 + 111850*x^7 + 2135740*x^8 + ...

%e 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

%t 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_ *)

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

%Y Cf. A004251 for graphs up to isomorphism.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_

%E Minor edits by _Vaclav Kotesovec_, Mar 31 2014