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

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

Offset

0,4

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. Misnha and B. Salvy, Effective D-Finite Symmetric Functions, FPSAC '02 (2002) # 19.12, see Maple output prior to the References.

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

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..2n} Sum_{k=0..min(floor((3n-i)/3), floor((2n-i)/2))} Sum_{j=0..min(floor(3n-i-3k)/2), floor((2n-i-2k)/2))} ((-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)!). - 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

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). - Vaclav Kotesovec, Mar 11 2014

a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n+2). - Vaclav Kotesovec, Mar 11 2014

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 *)

Prog

(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

Crossrefs

A diagonal of A059441. Cf. A005814.

See A004109 for connected graphs of this type.

Sequence in context: A364305 A007099 A004109 * A177637 A145410 A177638

Adjacent sequences: A002826 A002827 A002828 * A002830 A002831 A002832

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Mar 25 2001

Status

approved