login
A110039
Number of 3-regular labeled graphs on 2n vertices with no multiple edges, but loops are allowed. (3-regular = trivalent and a loop incident on a vertex counts as two edges.)
3
1, 1, 8, 730, 188790, 102737670, 102172297920, 167870491048260, 423971126389110300, 1559445481095305703900, 8010574937878696134151200, 55572909620219147733302926200, 506607333530572584517841616582600, 5931728848766374810152582924943605000
OFFSET
0,3
COMMENTS
Also the same as n X n symmetric matrices with {0,2}-entries on the diagonal and entries from {0,1} elsewhere, with row sum equal to 3.
REFERENCES
Goulden, I. P.; Jackson, D. M. Labelled graphs with small vertex degrees and $P$-recursiveness. SIAM J. Algebraic Discrete Methods 7(1986), no. 1, 60--66. MR0819706 (87k:05093)
FORMULA
Differential equation satisfied by the e.g.f. F(t) = sum_n a(n)/2n! t^n: {F(0) = 1, (-t^5+4*t^4+52*t-20*t^2-24)*F(t) + (-144*t+48-12*t^3-12*t^4+6*t^5)*(d/dt)F(t) + (36*t^4-72*t^2)*(d^2/dt^2)F(t)}.
Recurrence: {(123200*n^9 + 30135960*n + 8448*n^10 + 256*n^11 + 105258076*n^3 + 4989600 + 53358140*n^5 + 75458988*n^2 + 91991460*n^4 + 21100464*n^6 + 5718768*n^7 + 1045440*n^8)*a(n) + (-24948000 - 12736*n^9 - 90804600*n - 384*n^10 - 134879084*n^3 - 32082204*n^5 - 145393020*n^2 - 80308236*n^4 - 8713656*n^6 - 1589856*n^7 - 186624*n^8)*a(n + 1) + (11840760*n + 6932520*n^3 + 4989600 + 544320*n^5 + 12084468*n^2 + 2446668*n^4 + 74592*n^6 + 5760*n^7 + 192*n^8)*a(n + 2) + (-1108800 - 2428000*n - 1014166*n^3 - 44740*n^5 - 2148828*n^2 - 278430*n^4 - 3912*n^6 - 144*n^7)*a(n + 3) + (-6435 - 3887*n - 780*n^2 - 52*n^3)*a(n + 4) + (3003 + 1635*n + 297*n^2 + 18*n^3)*a(n + 5) - 3*a(n + 6)}.
Goulden and Jackson give a differential equation satisfied by the e.g.f, which presumably agrees with the above. - N. J. A. Sloane, Sep 02 2013
Recurrence (for n > 5): 3*(9*n^2 - 27*n + 16)*a(n) = 3*(2*n - 1)*(27*n^4 - 108*n^3 + 138*n^2 - 63*n + 4)*a(n-1) - (n-1)*(2*n - 3)*(2*n - 1)*(3*n - 4)*(18*n^2 - 27*n - 13)*a(n-2) + 2*(n-2)*(n-1)*(2*n - 5)*(2*n - 3)*(2*n - 1)*(27*n^3 - 90*n^2 + 57*n + 8)*a(n-3) - 2*(n-3)*(n-2)*(n-1)*(2*n - 7)*(2*n - 5)*(2*n - 3)*(2*n - 1)*(9*n^2 - 9*n - 2)*a(n-4). - Vaclav Kotesovec, Sep 15 2014
a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n). - Vaclav Kotesovec, Sep 15 2014
EXAMPLE
a(1)=1: {(1,1), (1,2), (2,2)}
MATHEMATICA
max = 30; f[x_] := Sum[a[n]*(x^n/n!), {n, 0, max}]; a[0] = 1; a[1] = 1; coef = CoefficientList[ 9*x^3*(x^4 - 2)*f''[x] + 3*(x^10 - 2*x^8 - 5*x^6 - 18*x^2 + 8)*f'[x] - x*(x^4 - 4*x^2 + 2)*(x^6 - 2*x^2 + 12)*f[x], x]; Table[a[n], {n, 0, max, 2}]/. Solve[Thread[coef[[2 ;; max]] == 0]][[1]] (* Vaclav Kotesovec, Sep 15 2014 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Marni Mishna, Jul 08 2005
EXTENSIONS
More terms from Vaclav Kotesovec, Sep 15 2014
STATUS
approved