A136282 Number of graphs on n labeled nodes with degree at most 3.

1, 2, 8, 64, 768, 12068, 236926, 5651384, 160054952, 5284391984, 200375581984, 8620342917808, 416471882713712, 22400989824444576, 1331457489258580672, 86887134810544955072, 6189888588922841477824, 478992737680928902742656, 40082045451011806706919808, 3612470757307682016196841216, 349398857659776033845292636416

Offset

1,2

References

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..200

Formula

Binomial transform of A110041. - Vladeta Jovovic, May 20 2008

Recurrence: 12*(81*n^4 - 837*n^3 + 3375*n^2 - 6171*n + 4192)*a(n) = 6*(243*n^5 - 2511*n^4 + 10665*n^3 - 21969*n^2 + 19476*n - 4624)*a(n-1) + 3*(n-1)*(243*n^6 - 2997*n^5 + 15147*n^4 - 39843*n^3 + 57594*n^2 - 41832*n + 10888)*a(n-2) - 3*(n-2)*(n-1)*(405*n^5 - 3699*n^4 + 13527*n^3 - 22629*n^2 + 14048*n + 388)*a(n-3) + (n-3)*(n-2)*(n-1)*(243*n^5 - 1944*n^4 + 6777*n^3 - 9738*n^2 - 2370*n + 10732)*a(n-4) + 2*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^4 - 999*n^3 + 4968*n^2 - 8646*n + 4906)*a(n-5) + (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(243*n^5 - 2916*n^4 + 12933*n^3 - 27990*n^2 + 27978*n - 8948)*a(n-6) - (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^4 - 513*n^3 + 891*n^2 - 357*n - 242)*a(n-7) - (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^4 - 513*n^3 + 1350*n^2 - 1608*n + 640)*a(n-8). - Vaclav Kotesovec, Aug 13 2013

a(n) ~ 3^(n/2) * exp(sqrt(3*n) - 3*n/2 - 5/4) * n^(3*n/2) / 2^(n + 1/2) * (1 + 71/(24*sqrt(3*n))). - Vaclav Kotesovec, Nov 05 2023

a(n) / A110041(n) ~ 1 + 2/sqrt(3*n). - Vaclav Kotesovec, Nov 06 2023

Crossrefs

Cf. A000085 (degree at most 1), A136281-A136286.

Sequence in context: A193549 A005612 A326290 * A092934 A224801 A191571

Adjacent sequences: A136279 A136280 A136281 * A136283 A136284 A136285

Keyword

nonn

Author

Don Knuth, Mar 31 2008

Extensions

More terms from Vladeta Jovovic, May 20 2008

Status

approved