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

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

Offset

1,3

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.

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

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

Crossrefs

Cf. A002829, A004109.

Sequence in context: A007100 A103157 A364305 * A004109 A002829 A177637

Adjacent sequences: A007096 A007097 A007098 * A007100 A007101 A007102

Keyword

nonn

Author

N. J. A. Sloane

Status

approved