|
| |
|
|
A110041
|
|
a(n) = number of labeled graphs on n vertices (with no isolated vertices, multi-edges or loops) such that the degree of every vertex is at most 3.
|
|
3
|
|
|
|
1, 0, 1, 4, 41, 512, 8285, 166582, 4054953, 116797432, 3912076929, 150190759240, 6532014077809, 318632936830136, 17286883399233149, 1035508343364348938, 68053563847088272945, 4879593083836366195728, 379847137967853770523937, 31960371880691511556886988
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
P-recursive.
|
|
|
REFERENCES
|
Goulden, I. P.; Jackson, D. M. Labelled graphs with small vertex degrees and $P$-recursiveness. SIAM J. Algebraic Discrete Methods 7(1986), no. 1, 60--66. MR0819706 (87k:05093) [Gives e.g.f.]
|
|
|
LINKS
|
|
|
|
FORMULA
|
Satisfies the linear recurrence: (-150917976*n^2 - 105258076*n^3 - 1925*n^9 - 13339535*n^5 - 45995730*n^4 - 357423*n^7 - 2637558*n^6 - 120543840*n - n^11 - 66*n^10 - 39916800 - 32670*n^8)*a(n) + (22057180*n^4 + 2*n^10 + 69934280*n^3 + 140581872*n^2 + 161254080*n + 4621890*n^5 + 79833600 + 130*n^9 + 3720*n^8 + 61620*n^7 + 653226*n^6)*a(n + 1) +
(3*n^10 + 6932835*n^5 + 5580*n^8 + 92430*n^7 + 979839*n^6 + 241881120*n + 33085770*n^4 + 104901420*n^3 + 210872808*n^2 + 119750400 + 195*n^9)*a(n + 2) + (6932520*n^3 + 39916800 + 136080*n^5 + 24168936*n^2 + 9324*n^6 + 47363040*n + 1223334*n^4 + 6*n^8 + 360*n^7)*a(n + 3) + (6*n^8 + 1431654*n^4 + 372*n^7 + 9996*n^6 + 152040*n^5 + 59875200 + 8545908*n^3 + 31580424*n^2 + 66054960*n)*a(n + 4) + (9100956*n + 6*n^7 + 9646560 + 3631220*n^2 + 335*n^6 + 7929*n^5 + 103085*n^4 + 794709*n^3)*a(n + 5) +
(492*n^6 + 9*n^7 + 11032560 + 11359*n^5 + 143385*n^4 + 1067026*n^3 + 4671483*n^2 + 11110486*n)*a(n + 6) + (1021680 + 1041*n^4 + 17838*n^3 + 150699*n^2 + 626358*n + 24*n^5)*a(n + 7) + (461340 + 7027*n^3 + 9*n^5 + 61461*n^2 + 267044*n + 399*n^4)*a(n + 8) + (100980 + 5751*n^2 + 9*n^4 + 39408*n + 372*n^3)*a(n + 9) + (-6414*n - 588*n^2 - 18*n^3 - 23364)*a(n + 10) + (-48*n - 528)*a(n + 11) + 24*a(n + 12) = 0.
Differential equation satisfied by the exponential generating function: {F(0) = 1, 9*t^4*(t^4 + t + t^2 - 2)^2*(d^2/dt^2)F(t) + 3*t*(-4*t^6 + 8*t^5 - 16*t + t^10 - 16*t^2 + 2*t^7 + 8 - 2*t^4 + 2*t^8 + 10*t^3)*(t^4 + t + t^2 - 2)*(d/dt)F(t) - t^2*(t^4 + t + t^2 - 2)*(t^10 - 2*t^9 - 6*t^7 - 12*t^6 + t^5 - t^4 + 39*t^3 - 10*t^2 + 24)*F(t)}.
Satisfies the recurrence (of order 8): 12*(81*n^4 - 837*n^3 + 2997*n^2 - 4326*n + 1987)*a(n) = 18*(n-1)*(81*n^4 - 810*n^3 + 2709*n^2 - 3435*n + 1036)*a(n-1) + 3*(n-1)*(243*n^6 - 2997*n^5 + 14499*n^4 - 35118*n^3 + 44823*n^2 - 26766*n + 3244)*a(n-2) + 3*(n-2)*(n-1)*(81*n^5 - 1080*n^4 + 4968*n^3 - 9825*n^2 + 7666*n - 178)*a(n-3) + (n-3)*(n-2)*(n-1)*(243*n^5 - 2430*n^4 + 8721*n^3 - 13896*n^2 + 8637*n - 2468)*a(n-4) + (n-4)*(n-3)*(n-2)*(n-1)*(405*n^4 - 3537*n^3 + 11934*n^2 - 15915*n + 6008)*a(n-5) + (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(243*n^5 - 2916*n^4 + 11799*n^3 - 19593*n^2 + 11382*n + 502)*a(n-6) + (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(162*n^4 - 1026*n^3 + 2241*n^2 - 1884*n + 182)*a(n-7) - (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^4 - 513*n^3 + 972*n^2 - 519*n - 98)*a(n-8). - Vaclav Kotesovec, Sep 10 2014
a(n) ~ 3^(n/2) * exp(sqrt(3*n) - 3*n/2 - 5/4) * n^(3*n/2) / 2^(n + 1/2) * (1 + 23/(24*sqrt(3*n))). - Vaclav Kotesovec, Nov 04 2023, extended Nov 06 2023
|
|
|
EXAMPLE
|
Graphs listed by edgeset: a(3) = 4: {(1,2), (2,3)}, {(1,3), (2,3)}, {(1,3), (1,2)}, {(2,3), (1,2), (1,3)}.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
