|
|
A005814
|
|
Number of 3-regular (trivalent) labeled graphs on 2n vertices with multiple edges and loops allowed.
(Formerly M2168)
|
|
8
|
|
|
1, 2, 47, 4720, 1256395, 699971370, 706862729265, 1173744972139740, 2987338986043236825, 11052457379522093985450, 57035105822280129537568575, 397137564714721907350936061400
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
a(n) is the number of representations required for the symbolic central moments of order 3 for the multivariate normal distribution, that is, E[X1^3 X2^3 .. Xn^3|mu=0, Sigma], where n is even. These representations are the upper-triangular, positive integer matrices for which for each i, the sum of the i-th row and i-th column equals 3, the power of each component. See Phillips links below. - Kem Phillips, Aug 18 2014
|
|
REFERENCES
|
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 175, (7.5.12).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
E.g.f. f(x) = Sum_{n>=0} a(2 * n) * x^n/(2 * n)! satisfies the differential equation 6 * x^2 * (x^2 - 2 * x - 2) * (d^2/dx^2)f(x) - (x^5 - 6 * x^4 + 6 * x^3 + 24 * x^2 + 16 * x - 8) * (d/dx)f(x) + (1/6) * (x^5 - 10 * x^4 + 24 * x^3 - 4 * x^2 - 44 * x - 48) * f(x) = 0.
Recurrence: a(2 * n) = (2 * n)!/n! * v(n) where 48 * v(n) + (-72 * n^2 + 120 * n - 96) * v(n - 1) + (-72 * n^3 + 288 * n^2 - 404 * n + 188) * v(n - 2) + (36 * n^4 - 396 * n^3 + 1472 * n^2 - 2184 * n + 1072) * v(n - 3) + (36 * n^4 - 336 * n^3 + 1116 * n^2 - 1536 * n + 720) * v(n - 4) + (-6 * n^5 + 80 * n^4 - 410 * n^3 + 1000 * n^2 - 1144 * n + 480) * v(n - 5) + (n^5 - 15 * n^4 + 85 * n^3 - 225 * n^2 + 274 * n - 120) * v(n - 6) = 0.
(End)
Linear recurrence satisfied by a(n): {a(0) = 1, a(1) = 2, a(2) = 47, a(3) = 4720, a(4) = 1256395, a(5) = 699971370, and (4989600 + 5718768*n^7 + 1045440*n^8 + 123200*n^9 + 8448*n^10 + 256*n^11 + 30135960*n + 75458988*n^2 + 105258076*n^3 + 91991460*n^4 + 53358140*n^5 + 21100464*n^6)*a(n) + (-39916800 - 1756320*n^7 - 198720*n^8 - 13120*n^9 - 384*n^10 - 136306080*n - 205327944*n^2 - 179845580*n^3 - 101513280*n^4 - 38608500*n^5 - 10026072*n^6)*a(n + 1) + (19958400 + 17664*n^7 + 576*n^8 + 44868240*n + 43664892*n^2 + 24024336*n^3 + 8173284*n^4 + 1760640*n^5 + 234528*n^6)*a(n + 2) + (720720 + 144*n^7 + 1819364*n + 1758924*n^2 + 883226*n^3 + 254070*n^4 + 42356*n^5 + 3816*n^6)*a(n + 3) + (-183645 - 191119*n - 79608*n^2 - 16586*n^3 - 1728*n^4 - 72*n^5)*a(n + 4) + (-2706 - 1515*n - 285*n^2 - 18*n^3)*a(n + 5) + 3*a(n + 6)}. - Marni Mishna, Jun 17 2005
Linear differential equation satisfied by F(t)=Sum a(n) t^n/(2n)!: {F(0) = 1, - 3*t*(10*t^2 + 9*t^6 + 18*t^4 - 8 + t^10 - 6*t^8)*( - 2 - 2*t^2 + t^4)*(d/dt)F(t) + 9*t^4*( - 2 - 2*t^2 + t^4)^2*(d^2/dt^2)F(t) + t^2*(-2 - 2*t^2 + t^4)*(24*t^6 - 10*t^8 - 4*t^4 - 44*t^2 + t^10 - 48)*F(t)}. - Marni Mishna, Jun 17 2005 [Probably this defines A005814? - N. J. A. Sloane]
Equation (7.5.13) in Harary and Palmer gives asymptotic formula.
Asymptotic formula (7.5.13) exp(-2)*(6*n)!/(288^n*(3*n)!) by Harary and Palmer from this reference is for sequence A002829. - Vaclav Kotesovec, Mar 11 2014
Asymptotic for A005814 is: a(n) ~ exp(2) * (6*n)! / (288^n * (3*n)!), or a(n) ~ sqrt(2) * 6^n * n^(3*n) / exp(3*n-2). - Vaclav Kotesovec, Mar 11 2014
Recurrence (of order 4): 3*a(n) = 9*(n-1)*n*(2*n-1)*a(n-1) + (n-1)*(2*n-3)*(2*n-1)*(12*n-1)*a(n-2) - 2*(n-2)*n*(2*n-5)*(2*n-3)*(2*n-1)*(3*n-2)*a(n-3) + 2*(n-3)*(n-1)*n*(2*n-7)*(2*n-5)*(2*n-3)*(2*n-1)*a(n-4). - Vaclav Kotesovec, Mar 11 2014
|
|
EXAMPLE
|
a(1)=2: {(1,1), (1,2), (2,2)}, {(1,2), (1,2), (1,2)}.
|
|
MATHEMATICA
|
max = 11; f[x_] := Sum[a[2n]*(x^n/(2n)!), {n, 0, max}]; a[0] = 1; coes = CoefficientList[ 6x^2*(x^2 - 2x - 2)* f''[x] - (x^5 - 6x^4 + 6x^3 + 24x^2 + 16x - 8)*f'[x] + 1/6*(x^5 - 10x^4 + 24x^3 - 4x^2 - 44x - 48)*f[x], x]; Table[a[2 n], {n, 0, max}] /. Solve[Thread[coes[[1 ;; max]] == 0]][[1]](* Jean-François Alcover, Nov 29 2011 *)
|
|
CROSSREFS
|
Even bisection of column k=3 of A333467.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|