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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005155 Number of degree sequences of n-node graphs.
(Formerly M1886)
2
1, 1, 2, 8, 54, 533, 6944, 111850, 2135740, 47003045, 1168832808, 32363244260, 986532609608, 32810811179569, 1181865951824800, 45823912079507918, 1902469319507438352, 84195282530581058825, 3956365033583165905568, 196716723188140236180160 (list; graph; refs; listen; history; text; internal format)
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

James Spahlinger and 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 A073564 A199576 * A133316 A234301 A005440

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 16 00:11 EST 2018. Contains 317252 sequences. (Running on oeis4.)