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

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

References

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

Links

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

Crossrefs

Cf. A002829, A004109.

Programs

Maple

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

Mathematica

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

Formula

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