A110039 -id:A110039 - cp's OEIS frontend

A110040 Number of {2,3}-regular graphs; i.e., labeled simple graphs (no multi-edges or loops) on n vertices, each of degree 2 or 3.

1, 0, 0, 1, 10, 112, 1760, 35150, 848932, 24243520, 805036704, 30649435140, 1322299270600, 64008728200384, 3447361661136640, 205070807479444088, 13388424264027157520, 953966524932871436800, 73817914562041635228928

Offset: 0

Marni Mishna, Jul 08 2005

P-recursive.
Starting at n=3, number of symmetric binary matrices with all row sums 3. - R. H. Hardin, Jun 12 2008
From R. J. Mathar, Apr 07 2017: (Start)
These are the row sums of the following matrix, which counts symmetric n X n {0,1} matrices with each row and column sum equal to 3 and trace t, 0 <= t <= n:
0:  1
1:  0 0
2:  0 0 0
3:  0 0 0 1
4:  1 0 6 0 3
5:  0 30 0 70 0 12
6:  70 0 810 0 810 0 70
7:  0 5670 0 19355 0 9660 0 465
This has A001205 on the diagonal. (End)
The traceless (2n) X (2n) binary matrices in that triangle seem to be counted in A002829. - Alois P. Heinz, Apr 07 2017

			(Graphs listed by edgeset)
a(3)=1: {(1,2), (2,3), (3,1)}
a(4)=10: {(1,2), (2,3), (3,4), (4,1)}, {(1,2), (2,3), (3,4), (4,1), (1,4)}, {(1,2), (2,3), (3,4), (4,1), (2,3)}, {(1,2), (2,4), (3,4), (1,3)}, {(1,2), (2,4), (3,4), (1,3), (2,3)}, {(1,2), (2,4), (3,4), (1,3), (1,4)}, {(1,3), (2,3), (2,4), (1,4)}, {(1,3), (2,3), (2,4), (1,4), (1,2)}, {(1,3), (2,3), (2,4), (1,4), (3,4)}, {(1,2), (1,3), (1,4) (2,3), (2,4), (3,4)},

Tan and S. Gao, Enumeration of (0,1)-Symmetric Matrices, submitted [From Shanzhen Gao, Jun 05 2009]

Vaclav Kotesovec, Table of n, a(n) for n = 0..320
I. P. Goulden and D. M. Jackson, 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.]

Cf. A002829, A110039, A110041.

Cf. A000986 (sums 2), A000085 (sums 1), A139670 (sums 3).

RecurrenceTable[{-b[n] - b[1 + n] + (-2 + 3*n)*b[2 + n] - 14*b[3 + n] + (105 + 30*n)*b[4 + n] + (-69 - 12*n)*b[5 + n] + (582 + 147*n + 9*n^2)* b[6 + n] + (-20 - 6*n)*b[7 + n] + (1160 + 363*n + 27*n^2)*b[8 + n] + (1554 + 255*n + 9*n^2)* b[9 + n] + (-2340 - 414*n - 18*n^2)*b[10 + n] + (-528 - 48*n)*b[11 + n] + (288 + 24*n)*b[12 + n] == 0, b[0] == 1, b[1] == 0, b[2] == 0, b[3] == 1/6, b[4] == 5/12, b[5] == 14/15, b[6] == 22/9, b[7] == 3515/504, b[8] == 30319/1440, b[9] == 10823/162, b[10] == 8385799/37800, b[11] == 510823919/665280}, b, {n, 0, 25}] * Range[0, 25]! (* Vaclav Kotesovec, Oct 23 2023 *)

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) + (-11028590*n^4 - 65*n^9 - n^10 - 2310945*n^5 - 1860*n^8 - 30810*n^7 - 326613*n^6 - 80627040*n - 39916800 - 34967140*n^3 - 70290936*n^2)*a(n + 1) + (3*n^10 - 39916800 + 187*n^9 + 5076*n^8 + 78558*n^7 + 761103*n^6 + 4757403*n^5 + 18949074*n^4 + 44946092*n^3 + 51046344*n^2 - 793440*n)*a(n + 2) + (-93139200 - 16175880*n^3 - 56394184*n^2 - 110513760*n - 2854446*n^4 - 14*n^8 - 840*n^7 - 21756*n^6 - 317520*n^5)*a(n + 3) + (45780*n^6 + 1785*n^7 + 111580320*n^2 + 660450*n^5 + 5856270*n^4 + 32645865*n^3 + 174636000 + 213450300*n + 30*n^8)*a(n + 4) + (-22952160 - 681*n^6 - 16419*n^5 - 217995*n^4 - 8082204*n^2 - 20896956*n - 12*n^7 - 1721253*n^3)*a(n + 5) + (1804641*n^3 + 9*n^7 + 14442*n^5 + 208920*n^4 + 32266080 + 9307488*n^2 + 26537388*n + 552*n^6)*a(n + 6) + (-158400 - 15160*n - 3994*n^3 - 31072*n^2 - 6*n^5 - 248*n^4)*a(n + 7) + (20123*n^3 + 706210*n + 27*n^5 + 170067*n^2 + 1148400 + 1173*n^4)*a(n + 8) + (7899*n^2 + 60684*n + 444*n^3 + 9*n^4 + 170940)*a(n + 9) + (-6894*n - 25740 - 18*n^3 - 612*n^2)*a(n + 10) + (-48*n - 528)*a(n + 11) + 24*a(n + 12).
Differential equation satisfied by the exponential generating function {F(0) = 1, 9*t^4*(t^4 + t - 2 + 3*t^2)^2*(d^2/dt^2)F(t) + 3*t*(t^4 + t - 2 + 3*t^2)*(10*t^8 + 34*t^3 - 16*t + 16*t^6 - 2*t^5 - 24*t^2 - 4*t^7 + 8 + t^10 - 14*t^4)*(d/dt)F(t) - t^3*(-22*t^2 + t^8 - 24*t^3 + t^9 + 8*t^7 + 14*t^6 + 15*t^5 + 12 + 16*t + 9*t^4)*(t^4 + t - 2 + 3*t^2)*F(t)}.
Sum_{a_2 = 0..n} Sum_{d_2 = 0..min(floor((3n - 2a_2)/2), floor(n/2), n - a_2)} Sum_{d_3 = 0..min(floor((3n - 2a_2 - 2d_2)/3), floor((n-2d_2)/3), n - a_2 - d_2} Sum_{d_1 = 0..min(3n - 2a_2 - 2d_2 - 3d_3, n - 2d_2 - 3d_3) Sum_{b = 0..min(floor((3n - 2a_2 - 2d_2 - 3d_3 - d_1)/4), floor((n - d_2 - d_3 - a_2)/2)} Sum_{c = 0..min(floor((3n - 2a_2 - 2d_2 - 3d_3 - d_1 - 4b)/6), floor((n - a_2 - 2b - d_2 - d_3)/2))} Sum_{a_1 = ceiling((3n - (2a_2 + 4b + 6c + d_1 + 2d_2 + 3d_3))/2)..floor((3n - (2a_2 + 4b + 6c + d_1 + 2d_2 + 3d_3))/2)} (-1)^(a_2 + b + d_2)*n!*(2a_1 + d_1)!/(2^(n + a_1 - c - d_3)*3^(n - a_2 - 2b - d_2 - c)*a_1!*a_2!*b!*c!*d_1!*d_2!*d_3!*(n - a_2 - 2b - d_2 - 2c - d_3)!). - Shanzhen Gao, Jun 05 2009
Recurrence (of order 8): 12*(27*n^4 - 423*n^3 + 2427*n^2 - 5639*n + 4384)*a(n) = 6*(n-1)*(81*n^4 - 1242*n^3 + 7011*n^2 - 15528*n + 10352)*a(n-1) + 3*(n-2)*(n-1)*(81*n^5 - 1269*n^4 + 7551*n^3 - 20841*n^2 + 29934*n - 16040)*a(n-2) - 3*(n-2)*(n-1)*(135*n^5 - 2115*n^4 + 13287*n^3 - 37537*n^2 + 46430*n - 21848)*a(n-3) + (n-3)*(n-2)*(n-1)*(567*n^5 - 9396*n^4 + 59895*n^3 - 169590*n^2 + 191744*n - 57040)*a(n-4) - 2*(n-4)*(n-3)*(n-2)*(n-1)*(135*n^4 - 1386*n^3 + 5034*n^2 - 6529*n + 648)*a(n-5) + (n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(81*n^5 - 1566*n^4 + 11367*n^3 - 37080*n^2 + 47872*n - 17424)*a(n-6) - (n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(27*n^4 - 315*n^3 + 1113*n^2 - 1433*n + 348)*a(n-7) - (n-7)*(n-6)*(n-5)*(n-4)*(n-3)*(n-2)*(n-1)*(27*n^4 - 315*n^3 + 1320*n^2 - 1946*n + 776)*a(n-8). - Vaclav Kotesovec, Oct 23 2023
a(n) ~ 3^(n/2) * n^(3*n/2) / (2^(n + 1/2) * exp(3*n/2 - sqrt(3*n) + 13/4)) * (1 + 119/(24*sqrt(3*n)) - 2519/(3456*n)). - Vaclav Kotesovec, Oct 27 2023, extended Oct 28 2023

Edited and extended by Max Alekseyev, May 08 2010

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.

Original entry on oeis.org

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

Offset: 0

Marni Mishna, Jul 08 2005

P-recursive.

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

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.]

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

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

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

Edited and extended by Max Alekseyev, Apr 28 2010

cp's OEIS Frontend

A110040 Number of {2,3}-regular graphs; i.e., labeled simple graphs (no multi-edges or loops) on n vertices, each of degree 2 or 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A333158 Irregular triangle read by rows: T(n,k) is the number of k-regular graphs on n labeled nodes with loops allowed, n >= 1, 0 <= k <= n + 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula