login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002829 Number of trivalent (or cubic) labeled graphs with 2n nodes.
(Formerly M5346 N2324)
21
1, 0, 1, 70, 19355, 11180820, 11555272575, 19506631814670, 50262958713792825, 187747837889699887800, 976273961160363172131825, 6840300875426184026353242750, 62870315446244013091262178375075, 741227949070136911068308523257857500 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

REFERENCES

Miklos Bona, 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

R. W. Robinson and 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.

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.

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_{a2=0..2n} Sum_{c=0..min(floor((3n-a2)/3),floor((2n-a2)/2))} Sum_{b=0..min(floor(3n-a2-3c)/2),floor((2n-a2-2c)/2))} ((-1)^(a2+b)*(2n)!(2*(3n-a2-2b-3c))!)/(2^(5n-a2-2b-4c)*3^(2n-a2-2b-c)*(3n-a2-2b-3c)!a2!b!c!(2n-a2-2b-2c)!). - Shanzhen Gao, Jun 05 2009

.

. === ALTERNATIVE PROPOSAL FOR THE ABOVE ENTRY ===

.

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

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

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: A103157 A007099 A004109 * A177637 A145410 A177638

Adjacent sequences:  A002826 A002827 A002828 * A002830 A002831 A002832

KEYWORD

nonn,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Mar 25 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 18:05 EST 2018. Contains 317323 sequences. (Running on oeis4.)