A002829 -id:A002829 - cp's OEIS frontend

A110039 Number of 3-regular labeled graphs on 2n vertices with no multiple edges, but loops are allowed. (3-regular = trivalent and a loop incident on a vertex counts as two edges.)

1, 1, 8, 730, 188790, 102737670, 102172297920, 167870491048260, 423971126389110300, 1559445481095305703900, 8010574937878696134151200, 55572909620219147733302926200, 506607333530572584517841616582600, 5931728848766374810152582924943605000

Offset: 0

Marni Mishna, Jul 08 2005

nonn

Also the same as n X n symmetric matrices with {0,2}-entries on the diagonal and entries from {0,1} elsewhere, with row sum equal to 3.

			a(1)=1: {(1,1), (1,2), (2,2)}

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)

Cf. A108246, A001147, A002829, A108243, A005814.

max = 30; f[x_] := Sum[a[n]*(x^n/n!), {n, 0, max}]; a[0] = 1; a[1] = 1; coef = CoefficientList[ 9*x^3*(x^4 - 2)*f''[x] + 3*(x^10 - 2*x^8 - 5*x^6 - 18*x^2 + 8)*f'[x] - x*(x^4 - 4*x^2 + 2)*(x^6 - 2*x^2 + 12)*f[x], x]; Table[a[n], {n, 0, max, 2}]/. Solve[Thread[coef[[2 ;; max]] == 0]][[1]] (* Vaclav Kotesovec, Sep 15 2014 *)

Differential equation satisfied by the e.g.f. F(t) = sum_n a(n)/2n! t^n: {F(0) = 1, (-t^5+4*t^4+52*t-20*t^2-24)*F(t) + (-144*t+48-12*t^3-12*t^4+6*t^5)*(d/dt)F(t) + (36*t^4-72*t^2)*(d^2/dt^2)F(t)}.
Recurrence: {(123200*n^9 + 30135960*n + 8448*n^10 + 256*n^11 + 105258076*n^3 + 4989600 + 53358140*n^5 + 75458988*n^2 + 91991460*n^4 + 21100464*n^6 + 5718768*n^7 + 1045440*n^8)*a(n) + (-24948000 - 12736*n^9 - 90804600*n - 384*n^10 - 134879084*n^3 - 32082204*n^5 - 145393020*n^2 - 80308236*n^4 - 8713656*n^6 - 1589856*n^7 - 186624*n^8)*a(n + 1) + (11840760*n + 6932520*n^3 + 4989600 + 544320*n^5 + 12084468*n^2 + 2446668*n^4 + 74592*n^6 + 5760*n^7 + 192*n^8)*a(n + 2) + (-1108800 - 2428000*n - 1014166*n^3 - 44740*n^5 - 2148828*n^2 - 278430*n^4 - 3912*n^6 - 144*n^7)*a(n + 3) + (-6435 - 3887*n - 780*n^2 - 52*n^3)*a(n + 4) + (3003 + 1635*n + 297*n^2 + 18*n^3)*a(n + 5) - 3*a(n + 6)}.
Goulden and Jackson give a differential equation satisfied by the e.g.f, which presumably agrees with the above. - N. J. A. Sloane, Sep 02 2013
Recurrence (for n > 5): 3*(9*n^2 - 27*n + 16)*a(n) = 3*(2*n - 1)*(27*n^4 - 108*n^3 + 138*n^2 - 63*n + 4)*a(n-1) - (n-1)*(2*n - 3)*(2*n - 1)*(3*n - 4)*(18*n^2 - 27*n - 13)*a(n-2) + 2*(n-2)*(n-1)*(2*n - 5)*(2*n - 3)*(2*n - 1)*(27*n^3 - 90*n^2 + 57*n + 8)*a(n-3) - 2*(n-3)*(n-2)*(n-1)*(2*n - 7)*(2*n - 5)*(2*n - 3)*(2*n - 1)*(9*n^2 - 9*n - 2)*a(n-4). - Vaclav Kotesovec, Sep 15 2014
a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n). - Vaclav Kotesovec, Sep 15 2014

More terms from Vaclav Kotesovec, Sep 15 2014

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

A321425 Number of connected labeled almost cubic graphs on 2n nodes.

Original entry on oeis.org

0, 0, 6, 630, 232260, 167712300, 207994906350, 409639268108070, 1206311009131027800, 5069191623021896970600, 29288218834810895163954750, 225729928889064072869657010750, 2263331356064784471285438421502700, 28907890013735339531664032407056442500

Offset: 0

R. J. Mathar, Nov 09 2018

nonn

Almost cubic graphs are cubic graphs (A002829) where 2 points have degree 2 and these 2 points are non-adjacent. All other points have degree 3. They are constructed by removing an edge from the cubic graphs.

			There is 1 unlabeled almost cubic graph on 4 nodes (the kite, obtained by removing an edge of the tetrahedron K_4). This has 6 = binomial(4,2) labeled versions obtained by selecting two out of 4 labels for the points of degree 2.

Andrew Howroyd, Table of n, a(n) for n = 0..100
N. C. Wormald, Enumeration of labelled graphs II: cubic graphs with a given connectivity, J. Lond Math Soc s2-20 (1979) 1-7, e.g.f. a(x).

Cf. A002829, A321426.

terms = 14; egf = HypergeometricPFQ[{1/6, 5/6}, {}, 12x/(x^2 + 8x + 4)^(3/2)] Exp[-Log[1/4 x^2 + 2x + 1]/4 - x/3 + (x^2 + 8x + 4)^(3/2)/(24 x) - 1/(3x) - x^2/24 - 1] + O[x]^terms;
CoefficientList[egf, x](2 Range[0, terms-1])! 3 Range[0, terms-1] (* Jean-François Alcover, Nov 23 2018, from A002829 *)

b(n) = sum(i=0, 2*n, sum(k=0, min(floor((3*n-i)/3), floor((2*n-i)/2)), sum(j=0, min(floor((3*n-i-3*k)/2), floor((2*n-i-2*k)/2)), ((-1)^(i+j)*(2*n)!*(2*(3*n-i-2*j-3*k))!)/(2^(5*n-i-2*j-4*k)*3^(2*n-i-2*j-k)*(3*n-i-2*j-3*k)!*i!*j!*k!*(2*n-i-2*j-2*k)!)))); \\ A002829
vector(20, n, n--; 3*n*b(n)) \\ Michel Marcus, Nov 10 2018

a(n) = 3*n*A002829(n). [Wormald eq. (2.1)]

Terms a(11) and beyond from Andrew Howroyd, Nov 09 2018

A321426 Number of connected labeled fairly cubic graphs on 2n nodes.

Original entry on oeis.org

0, 0, 6, 810, 282660, 195192900, 235439369550, 454833890480970, 1320613138677432600, 5490000743915652564600, 31451199565381549069866750, 240742295353571264522056037250, 2400231508458936741386610203090700, 30511229662020079098420585892148047500

Offset: 0

R. J. Mathar, Nov 09 2018

nonn

Fairly cubic graphs are cubic graphs (A002829) where 2 points have degree 2. All other points have degree 3.

Andrew Howroyd, Table of n, a(n) for n = 0..100
N. C. Wormald, Enumeration of labelled graphs II: cubic graphs with a given connectivity, J. Lond Math Soc s2-20 (1979) 1-7, e.g.f. f(x).

Cf. A002829, A321425, A321427.

b[n_] := Sum[Sum[Sum[((-1)^(i+j)(2n)! (2(3n - i - 2j - 3k))!)/ (2^(5n -i - 2j - 4k) 3^(2n - i - 2j - k)(3n - i - 2j - 3k)! i! j! k! (2n - i - 2j - 2k)!), {j, 0, Min[Floor[(3n - i - 3k)/2], Floor[(2n - i - 2k)/2]]}], {k, 0, Min[Floor[(3n - i)/3], Floor[(2n - i)/2]]}], {i, 0, 2n}];
seq[n_] := Module[{v = Table[0, {n+1}]}, For[k = 2, k <= n, k++, v[[k+1]] = 3k b[k] + 2k(2k - 1)v[[k]] + k(2k - 1)(2k - 2)(2k - 3)v[[k-1]]]; v];
seq[13] (* Jean-François Alcover, Nov 22 2018, after Andrew Howroyd *)

\\ here b(n) is A002829
b(n) = sum(i=0, 2*n, sum(k=0, min(floor((3*n-i)/3), floor((2*n-i)/2)), sum(j=0, min(floor((3*n-i-3*k)/2), floor((2*n-i-2*k)/2)), ((-1)^(i+j)*(2*n)!*(2*(3*n-i-2*j-3*k))!)/(2^(5*n-i-2*j-4*k)*3^(2*n-i-2*j-k)*(3*n-i-2*j-3*k)!*i!*j!*k!*(2*n-i-2*j-2*k)!))));
seq(n)={my(v=vector(n+1)); for(n=2, n, v[n+1] = 3*n*b(n) + 2*n*(2*n-1)*v[n] + n*(2*n-1)*(2*n-2)*(2*n-3)*v[n-1]); v} \\ Andrew Howroyd, Nov 09 2018

a(n) = A321425(n) + n*(2*n-1)*(2*n-2)*A321427(n-2) + 2*n*(2*n-1)*a(n-1). [Wormald eq (2.3)]

a(n) = 3*n*A002829(n) + 2*n*(2*n-1)*a(n-1) + n*(2*n-1)*(2*n-2)*(2*n-3)*a(n-2). - Andrew Howroyd, Nov 09 2018

Terms a(11) and beyond from Andrew Howroyd, Nov 09 2018

A339987 The number of labeled graphs on 2n vertices that share the same degree sequence as any unrooted binary tree on 2n vertices.

Original entry on oeis.org

1, 4, 90, 8400, 1426950, 366153480, 134292027870, 67095690261600, 43893900947947050, 36441011093916429000, 37446160423265535041100, 46669357647008722700474400, 69367722399061403579194432500, 121238024532751529573125745790000, 246171692450596203263023527657431250

Offset: 1

Atabey Kaygun, Dec 25 2020

nonn

An unrooted binary tree is a tree in which all non-leaf vertices have degree 3. With 2n vertices there will be n+1 leaves and n-1 internal vertices.

Andrew Howroyd, Table of n, a(n) for n = 1..100 (terms 1..40 from Atabey Kaygun)
Atabey Kaygun, Counting Graphs with a Prescribed Degree Sequence.
Atabey Kaygun, Common LISP program that generates the sequence.
M. Kauers and C. Koutschan, Some D-finite and some possibly D-finite sequences in the OEIS, arXiv:2303.02793 [cs.SC], 2023.

Cf. A001147, A001190, A002829.

\\ See Links in A295193 for GraphsByDegreeSeq.
a(n) = {if(n==1, 1, my(d=2*n-4, M=GraphsByDegreeSeq(n-1, 3, (p,r)-> subst(deriv(p),x,1) >= d-6*r), z=(2*n)!/(n-1)!); sum(i=1, matsize(M)[1], my(p=M[i,1], r=(subst(deriv(p), x, 1)-d)/2); M[i,2]*z / (2^polcoef(p,1) * 6^polcoef(p,0) * 2^r * r!)))} \\ Andrew Howroyd, Mar 01 2023

Conjectured recurrence: 32*(1 + n)*(2 + n)*(1 + 2*n)*(3 + 2*n)*(5 + 2*n)*(7 + 2*n)*(9 + 2*n)*(11589 + 10844*n + 3300*n^2 + 328*n^3)*a(n) - 8*(2 + n)*(3 + 2*n)*(5 + 2*n)*(7 + 2*n)*(9 + 2*n)*(148119 + 232328*n + 129460*n^2 + 30664*n^3 + 2624*n^4)*a(n+1) - 16*(3 + n)*(5 + 2*n)*(7 + 2*n)*(9 + 2*n)*(341634 + 712135*n + 569267*n^2 + 219308*n^3 + 40852*n^4 + 2952*n^5)*a(n+2) + 8*(4 + n)*(7 + 2*n)*(9 + 2*n)*(527520 + 1057879*n + 818282*n^2 + 306380*n^3 + 55672*n^4 + 3936*n^5)*a(n+3) - 2*(5 + n)*(9 + 2*n)*(601452 + 1117119*n + 786236*n^2 + 264028*n^3 + 42472*n^4 + 2624*n^5)*a(n+4) + 3*(4 + n)*(6 + n)*(3717 + 5228*n + 2316*n^2 + 328*n^3)*a(n+5) = 0. - Manuel Kauers and Christoph Koutschan, Mar 01 2023

Conjecture: a(n) ~ 2^(5*n - 1/2) * n^(2*n - 3/2) / (sqrt(Pi) * 3^(n-1) * exp(2*n + 21/16)), based on the recurrence by Manuel Kauers and Christoph Koutschan. - Vaclav Kotesovec, Mar 07 2023

A006607 Number of labeled connected rooted trivalent graphs with 2n nodes.

Original entry on oeis.org

0, 4, 120, 33600, 18446400, 18361728000, 30199104936000, 76326119565696000, 280889824362219072000, 1443428429045578335360000, 10016498030869925136622080000, 91330153089556497015273454080000

Offset: 1

N. J. A. Sloane

nonn

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. C. Wormald, Triangles in labeled cubic graphs, pp. 337-345 of Combinatorial Mathematics (Canberra, 1977), Lect. Notes Math. 686, 1978.

R. W. Robinson, Table of n, a(n) for n = 1..29

Cf. A002829, A286757 (corrected version?)

A006714 Number of trivalent bipartite labeled graphs with 2n labeled nodes.

Original entry on oeis.org

10, 840, 257040, 137260200, 118273755600, 154712104747200, 292311804557572800, 766931112143320924800, 2706462791802644002128000, 12512595130808078973370704000, 74130965352250071944327288640000, 552334353713465817349513210512960000, 5092566798555894395129552704613028960000

Offset: 3

N. J. A. Sloane

nonn

R. C. Read incorrectly has a(7) = 118257539400 and a(8) = 154678050727200 which he calculated by hand. - Sean A. Irvine, Jun 27 2017

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 3..50
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)

Cf. A001501, A002829, A004109, A246599.

(* b stands for A001501 *) b[n_] := n!^2 Sum[2^(2k-n) 3^(k-n) (3(n-k))!  HypergeometricPFQ[{k-n, k-n}, {3(k-n)/2, 1/2 + 3(k-n)/2}, -9/2]/(k! (n-k)!^2), {k, 0, n}]/6^n;
(* c stands for A246599 *) c[n_] := c[n] = Binomial[2n-1, n] b[n] - Sum[ Binomial[2n-1, 2k] Binomial[2k, k] b[k] c[n-k], {k, 1, n-1}];
a[n_] := a[n] = c[n] + Sum[Binomial[2n-1, 2k-1] c[k] a[n-k], {k, 1, n-1}];
Table[a[n], {n, 3, 20}] (* Jean-François Alcover, Jul 07 2018, after Andrew Howroyd *)

\\ here b(n) is A001501
b(n) = {n!^2 * sum(j=0, n, sum(i=0, n-j, my(k=n-i-j); (j + 3*k)! / (3^i * 36^k * i! * k!^2)) / (j! * (-2)^j))}
seq(n)={my(v=vector(n,n,b(n)*binomial(2*n-1,n)), u=vector(n), s=vector(n)); for(n=1, #u, u[n]=v[n] - sum(k=3, n-3, 2*binomial(2*n-1,2*k)*v[k]*u[n-k]); s[n]=u[n] + sum(k=3, n-3, binomial(2*n-1,2*k-1)*u[k]*s[n-k])); s[3..n]} \\ Andrew Howroyd, May 22 2018

a(n) = A246599(n) + Sum_{k=1..n-1} binomial(2*n-1,2*k-1)*A246599(k)*a(n-k). - Andrew Howroyd, May 22 2018

a(n) ~ 3^(n + 1/2) * n^(3*n) / (sqrt(2) * exp(3*n+2)). - Vaclav Kotesovec, Feb 17 2024

a(7)-a(8) corrected and a(9)-a(12) computed with nauty by Sean A. Irvine, Jun 27 2017

Terms a(13) and beyond from Andrew Howroyd, May 22 2018

A007099 Number of labeled trivalent (or cubic) 2-connected graphs with 2n nodes.

Original entry on oeis.org

0, 1, 70, 19320, 11052720, 11408720400, 19285018552800, 49792044478176000, 186348919238786304000, 970566620767088881536000, 6808941648018137282054400000, 62642603299257346706851910400000

Offset: 1

N. J. A. Sloane

nonn

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
R. W. Robinson, Computer print-out, no date. Gives first 29 terms.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson, Table of n, a(n) for n = 1..29 (corrected by Michel Marcus, Jan 19 2019)
G.-B. Chae, E. M. Palmer, R. W. Robinson, Counting labeled general cubic graphs, Discr. Math. 307 (2007) 2979-2992, eqs. (23) and (24).
R. W. Robinson, Cubic labeled graphs, computer print-out, n.d.

Cf. A002829, A004109.

s := proc(n)
    option remember;
    if n = 1 then
        0;
    elif n = 2 then
        1;
    else
        3*n*procname(n-1)+2*procname(n-2)+(3*n-1)*add(procname(i)*procname(n-1-i),i=2..n-3) ;
    end if;
end proc:
A007099 := proc(n)
    if n = 1 then
        0;
    elif n = 2 then
        1;
    else
        (2*n)!/3/n/2^n*(s(n)-2*s(n-1)) ;
    end if;
end proc: # R. J. Mathar, Nov 08 2018

s[n_] := s[n] = If[n <= 2, n - 1, 3 n s[n - 1] + 2 s[n - 2] + (3 n - 1) Sum[s[i] s[n - 1 - i], {i, 2, n - 3}]]; Array[Floor[(2 #)!*(s[#] - 2 s[# - 1])/(3 # 2^#)] &, 12] (* Michael De Vlieger, Oct 11 2017 *)

a(n) = (2*n)! * (s(n) - 2*s(n-1)) / (3*n*2^n) where s(1)=0, s(2)=1, and s(n) = 3*n*s(n-1) + 2*s(n-2) + (3*n-1) * Sum_{i=2..n-3} s(i) * s(n-1-i). - Sean A. Irvine, Oct 11 2017

A007100 Number of labeled trivalent (or cubic) 3-connected graphs with 2n nodes.

Original entry on oeis.org

1, 70, 16800, 9238320, 9520156800, 16305064776000, 42856575521760000, 163329351308323200000, 864876880105205071104000, 6155146233167046820024320000, 57316399761348433188962519040000

Offset: 2

N. J. A. Sloane

nonn

R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson, Table of n, a(n) for n = 2..28
R. W. Robinson, Cubic labeled graphs, computer print-out, n.d. (see last page)

a(n) = (2*n)!*r(n)/(3*n*2^n) where r(2) = 1 and r(n) = (3*n-2) * (r(n-1) + Sum_{i=2..n-2} r(i) * r(n-i)). - Sean A. Irvine, Oct 11 2017

A246599 Number of connected trivalent bipartite labeled graphs with 2n labeled nodes.

Original entry on oeis.org

10, 840, 257040, 137214000, 118248530400, 154686980448000, 292276881344448000, 766864651478365440000, 2706292794907249067520000, 12512021073989410699165440000, 74128448237031250090060032000000, 552320243355746711191770103680000000, 5092467146398443040845772685937408000000

Offset: 3

N. J. A. Sloane, Sep 08 2014

nonn

R. C. Read incorrectly has a(7) = 118237555800 and a(8) = 154652926428000 which he calculated by hand.

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.

Andrew Howroyd, Table of n, a(n) for n = 3..50
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)

Cf. A001501, A002829, A004109, A006714.

b[n_] := n!^2*Sum[2^(2k-n) 3^(k-n)(3(n-k))!*HypergeometricPFQ[{k-n, k-n}, {3(k-n)/2, 1/2 + 3(k-n)/2}, -9/2]/(k! (n-k )!^2), {k, 0, n}]/6^n;
a[n_] := a[n] = Binomial[2n-1, n] b[n] - Sum[Binomial[2n-1, 2k] Binomial[2 k, k] b[k] a[n-k], {k, 1, n-1}];
Table[a[n], {n, 3, 20}] (* Jean-François Alcover, Jul 07 2018, after Andrew Howroyd *)

\\ here b(n) is A001501
b(n) = {n!^2 * sum(j=0, n, sum(i=0, n-j, my(k=n-i-j); (j + 3*k)! / (3^i * 36^k * i! * k!^2)) / (j! * (-2)^j))}
seq(n)={my(v=vector(n, n, b(n)*binomial(2*n, n)), u=vector(n)); for(n=1, #u, u[n]=v[n] - sum(k=3, n-3, binomial(2*n-1,2*k)*v[k]*u[n-k])); u[3..n]/2} \\ Andrew Howroyd, May 22 2018

a(n) = binomial(2*n-1, n)*A001501(n) - Sum_{k=1..n-1} binomial(2*n-1, 2*k) * binomial(2*k, k) * A001501(k) * a(n-k). - Andrew Howroyd, May 22 2018

a(n) ~ 3^(n + 1/2) * n^(3*n) / (sqrt(2) * exp(3*n + 2)). - Vaclav Kotesovec, Feb 17 2024

a(7)-a(8) corrected and a(9)-a(12) computed with nauty by Sean A. Irvine, Jun 27 2017

Terms a(13) and beyond from Andrew Howroyd, May 22 2018

cp's OEIS Frontend

A110039 Number of 3-regular labeled graphs on 2n vertices with no multiple edges, but loops are allowed. (3-regular = trivalent and a loop incident on a vertex counts as two edges.)

Views

Author

Keywords

Comments

Examples

References

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

A321425 Number of connected labeled almost cubic graphs on 2n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A321426 Number of connected labeled fairly cubic graphs on 2n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A339987 The number of labeled graphs on 2n vertices that share the same degree sequence as any unrooted binary tree on 2n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A006607 Number of labeled connected rooted trivalent graphs with 2n nodes.

Views

Author

Keywords

References

Links

Crossrefs

A006714 Number of trivalent bipartite labeled graphs with 2n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A007099 Number of labeled trivalent (or cubic) 2-connected graphs with 2n nodes.