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.

1, 0, 1, 4, 41, 512, 8285, 166582, 4054953, 116797432, 3912076929, 150190759240, 6532014077809, 318632936830136, 17286883399233149, 1035508343364348938, 68053563847088272945, 4879593083836366195728, 379847137967853770523937, 31960371880691511556886988

Offset: 0

Author

Marni Mishna, Jul 08 2005

Keywords

• easy
• nonn

Comments

P-recursive.

Examples

			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)}.
		

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

• Alois P. Heinz, Table of n, a(n) for n = 0..150

Crossrefs

Cf. A110040, A110039, A002829, A001205, A001147.

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

Limit_{n->oo} A110041(n)/A110040(n) = exp(2). - Vaclav Kotesovec, Nov 05 2023

Extensions

Edited and extended by Max Alekseyev, Apr 28 2010