A002829 Number of trivalent (or cubic) labeled graphs with 2n nodes.

1, 0, 1, 70, 19355, 11180820, 11555272575, 19506631814670, 50262958713792825, 187747837889699887800, 976273961160363172131825, 6840300875426184026353242750, 62870315446244013091262178375075, 741227949070136911068308523257857500

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 411.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 279.
• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
• R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
• R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
• R. W. Robinson, Computer print-out, no date. Gives first 30 terms.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..160 (first 31 terms from R. W. Robinson)
• F. Chyzak, M. Mishna and B. Salvy, Effective D-Finite Symmetric Functions, FPSAC '02 (2002) # 19.12, see Maple output prior to the References.
• Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 9.
• Oleg Evnin and Weerawit Horinouchi, A Gaussian integral that counts regular graphs, arXiv:2403.04242 [cond-mat.stat-mech], 2024. See p. 12.
• 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)
• I. P. Goulden, D. M. Jackson, and J. W. Reilly, The Hammond series of a symmetric function and its application to P-recursiveness, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 179-193.
• Atabey Kaygun, Enumerating Labeled Graphs that Realize a Fixed Degree Sequence, arXiv:2101.02299 [math.CO], 2021.
• Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
• R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
• R. W. Robinson, Cubic labeled graphs, computer print-out, n.d.
• N. C. Wormald, Enumeration of labelled graphs II: cubic graphs with a given connectivity, J. Lond Math Soc s2-20 (1979) 1-7, eq. (2.6).

Crossrefs

A diagonal of A059441. Cf. A005814.

See A004109 for connected graphs of this type.

Programs

Maple

From R. J. Mathar, Oct 31 2010: (Start)
A002829aux := proc(i) local a,j,k ; a := 0 ; for j from 0 to i do for k from 0 to 2*(i-j) do a := a+(-1)^(j+k)/j!*doublefactorial(2*i+2*k-1)/3^k/k!/(2*i-2*j-k)! ; end do: end do: a*3^i/2^i ; end proc:
A002829 := proc(n) (2*n)!/6^n*add( A002829aux(i)/(n-i)!,i=0..n) ; end proc: seq(A002829(n),n=0..6) ; (End)
egf := hypergeom([1/6, 5/6],[],12*x/(x^2+8*x+4)^(3/2)) * exp(-ln(1/4*x^2+2*x+1)/4 - x/3 + (x^2+8*x+4)^(3/2)/(24*x) - 1/(3*x) - x^2/24 - 1):
ser := convert(series(egf,x=0,30),polynom):
seq(coeff(ser,x,i) * (2*i)!, i=0..degree(ser)); # Mark van Hoeij, Nov 07 2011

Mathematica

Flatten[{1,RecurrenceTable[{2 (-3+n) (-2+n) (-1+n) (-7+2 n) (-5+2 n) (-3+2 n) (-1+2 n) (-4+3 n) (-1+3 n) a[-4+n]-2 (-2+n) (-1+n) (-5+2 n) (-3+2 n) (-1+2 n) (-1+3 n) (43-42 n+9 n^2) a[-3+n]-(-1+n) (-3+2 n) (-1+2 n) (-104+501 n-441 n^2+108 n^3) a[-2+n]-9 (-1+n) (-1+2 n) (-7+3 n) (2-4 n+3 n^2) a[-1+n]+3 (-7+3 n) (-4+3 n) a[n]==0,a[1]==0,a[2]==1,a[3]==70,a[4]==19355},a,{n,1,15}]}] (* Vaclav Kotesovec, Mar 11 2014 *)
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)/(24x) - 1/(3x) - x^2/24 - 1] + O[x]^terms;
CoefficientList[egf, x] (2 Range[0, terms-1])! (* Jean-François Alcover, Nov 23 2018, after Mark van Hoeij *)

PARI

a(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)!)))); \\ Michel Marcus, Jan 18 2018

Formula

From Vladeta Jovovic, Mar 25 2001: (Start)

E.g.f. f(x) = Sum_{n >= 0} a(2 * n) * x^n/(2 * n)! satisfies differential equation 6 * x^2 * (-x^2 - 2 * x + 2) * (d^2/dx^2)f(x) - (x^5 + 6 * x^4 + 6 * x^3 - 32 * x + 8) * (d/dx)f(x) + (x/6) * (-x^2 - 2 * x + 2)^2 * f(x) = 0.

Recurrence: a(2 * n) = (2 * n)!/n! * v(n) where 48 * v(n) + (-72 * n^2 + 24 * n + 48) * v(n - 1) + (72 * n^3 - 432 * n^2 + 788 * n - 428) * v(n - 2) + (36 * n^4 - 324 * n^3 + 1052 * n^2 - 1428 * n + 664) * v(n - 3) + (36 * n^4 - 360 * n^3 + 1260 * n^2 - 1800 * n + 864) * v(n - 4) + (6 * n^5 - 94 * n^4 + 550 * n^3 - 1490 * n^2 + 1844 * n - 816) * v(n - 5) + (-n^5 + 15 * n^4 - 85 * n^3 + 225 * n^2 - 274 * n + 120) * v(n - 6) = 0. (End)

a(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)!). - Shanzhen Gao, Jun 05 2009

E.g.f.: hypergeom([1/6, 5/6],[],12*x/(x^2+8*x+4)^(3/2))*exp(-log(1/4*x^2+2*x+1)/4 - x/3 + (x^2+8*x+4)^(3/2)/(24*x) - 1/(3*x) - x^2/24 - 1). Multiply x^i by (2*i)! to get the generating function. - Mark van Hoeij, Nov 07 2011

From Vaclav Kotesovec, Mar 11 2014: (Start)

D-finite with recurrence: 3*(3*n-7)*(3*n-4)*a(n) = 9*(n-1)*(2*n-1)*(3*n-7)*(3*n^2 - 4*n + 2)*a(n-1) + (n-1)*(2*n-3)*(2*n-1)*(108*n^3 - 441*n^2 + 501*n - 104)*a(n-2) + 2*(n-2)*(n-1)*(2*n-5)*(2*n-3)*(2*n-1)*(3*n-1)*(9*n^2 - 42*n + 43)*a(n-3) - 2*(n-3)*(n-2)*(n-1)*(2*n-7)*(2*n-5)*(2*n-3)*(2*n-1)*(3*n-4)*(3*n-1)*a(n-4).

a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n+2). (End)

Extensions

More terms from Vladeta Jovovic, Mar 25 2001