cp's OEIS Frontend

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

%I A002829 M5346 N2324 #120 Apr 15 2025 08:29:00
%S A002829 1,0,1,70,19355,11180820,11555272575,19506631814670,50262958713792825,
%T A002829 187747837889699887800,976273961160363172131825,
%U A002829 6840300875426184026353242750,62870315446244013091262178375075,741227949070136911068308523257857500
%N A002829 Number of trivalent (or cubic) labeled graphs with 2n nodes.
%D A002829 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 411.
%D A002829 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 279.
%D A002829 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
%D A002829 R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
%D A002829 R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.
%D A002829 R. W. Robinson, Computer print-out, no date. Gives first 30 terms.
%D A002829 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002829 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002829 Alois P. Heinz, <a href="/A002829/b002829.txt">Table of n, a(n) for n = 0..160</a> (first 31 terms from R. W. Robinson)
%H A002829 F. Chyzak, M. Mishna and B. Salvy, <a href="https://fpsac-archive.github.io/FPSAC02/ARTICLES/Chyzak.pdf">Effective D-Finite Symmetric Functions</a>, FPSAC '02 (2002) # 19.12, see Maple output prior to the References.
%H A002829 Élie de Panafieu, <a href="https://arxiv.org/abs/2408.12459">Asymptotic expansion of regular and connected regular graphs</a>, arXiv:2408.12459 [math.CO], 2024. See p. 9.
%H A002829 Oleg Evnin and Weerawit Horinouchi, <a href="https://arxiv.org/abs/2403.04242">A Gaussian integral that counts regular graphs</a>, arXiv:2403.04242 [cond-mat.stat-mech], 2024. See p. 12.
%H A002829 I. P. Goulden and D. M. Jackson, <a href="http://dx.doi.org/10.1137/0607007">Labelled graphs with small vertex degrees and P-recursiveness</a>, SIAM J. Algebraic Discrete Methods 7(1986), no. 1, 60-66. MR0819706 (87k:05093)
%H A002829 I. P. Goulden, D. M. Jackson, and J. W. Reilly, <a href="http://dx.doi.org/10.1137/0604019">The Hammond series of a symmetric function and its application to P-recursiveness</a>, SIAM J. Algebraic Discrete Methods 4 (1983), no. 2, 179-193.
%H A002829 Atabey Kaygun, <a href="https://arxiv.org/abs/2101.02299">Enumerating Labeled Graphs that Realize a Fixed Degree Sequence</a>, arXiv:2101.02299 [math.CO], 2021.
%H A002829 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%H A002829 R. C. Read, <a href="/A002831/a002831.pdf">Letter to N. J. A. Sloane, Feb 04 1971</a> (gives initial terms of this sequence)
%H A002829 R. W. Robinson, <a href="/A002829/a002829.pdf">Cubic labeled graphs, computer print-out, n.d.</a>
%H A002829 N. C. Wormald, <a href="http://dx.doi.org/10.1112/jlms/s2-20.1.1">Enumeration of labelled graphs II: cubic graphs with a given connectivity</a>, J. Lond Math Soc s2-20 (1979) 1-7, eq. (2.6).
%F A002829 From _Vladeta Jovovic_, Mar 25 2001: (Start)
%F A002829 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.
%F A002829 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)
%F A002829 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
%F A002829 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
%F A002829 From _Vaclav Kotesovec_, Mar 11 2014: (Start)
%F A002829 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).
%F A002829 a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n+2). (End)
%p A002829 From _R. J. Mathar_, Oct 31 2010: (Start)
%p A002829 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:
%p A002829 A002829 := proc(n) (2*n)!/6^n*add( A002829aux(i)/(n-i)!,i=0..n) ; end proc: seq(A002829(n),n=0..6) ; (End)
%p A002829 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):
%p A002829 ser := convert(series(egf,x=0,30),polynom):
%p A002829 seq(coeff(ser,x,i) * (2*i)!, i=0..degree(ser)); # _Mark van Hoeij_, Nov 07 2011
%t A002829 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 *)
%t A002829 terms = 14;
%t A002829 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;
%t A002829 CoefficientList[egf, x] (2 Range[0, terms-1])! (* _Jean-François Alcover_, Nov 23 2018, after _Mark van Hoeij_ *)
%o A002829 (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
%Y A002829 A diagonal of A059441. Cf. A005814.
%Y A002829 See A004109 for connected graphs of this type.
%K A002829 nonn
%O A002829 0,4
%A A002829 _N. J. A. Sloane_
%E A002829 More terms from _Vladeta Jovovic_, Mar 25 2001