A108242 a(n) is the number of coverings of 1..n by cyclic words of length 3, such that each value from 1 to n appears precisely 3 times. That is, the union of all the letters in all of the words of a given covering is the multiset {1,1,1,2,2,2,...,n,n,n}. Repeats of words are allowed in a given covering.

1, 1, 2, 16, 256, 7184, 311944, 19191448, 1584972224, 169021538944, 22595033625856, 3699135711988736, 727774085471066752, 169399730544125355136, 46039989792346454771456, 14447317177670702438831104, 5183889091511674280049885184, 2108937872584292649560886222848

Offset

0,3

Comments

The asymptotic growth of the coefficients is a(n) ~ C (3/2)^n (n!)^2 /n with C approx 0.277.

In closed form, C = sqrt(3)/(2*Pi) = 0.27566444771089602475566324915648472... . - Vaclav Kotesovec, Feb 28 2016

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..240

Formula

Exponential generating function satisfies the linear differential equation: {(6 + 499*t^6 + 270*t^4 + 408*t^8 - 162*t^11 - 558*t^9 - 12*t - 96*t^3 + 66*t^2 - 654*t^7 + 60*t^12 + 154*t^10 - 342*t^5 + 9*t^14)*F(t) + (81*t^10 + 72*t^4 + 198*t^6 + 216*t^8 + 9*t^2)*(d^2/dt^2)F(t) + (-474*t^6 - 252*t^10 - 6 + 126*t^3 + 594*t^7 - 66*t^2 + 324*t^9 - 54*t^12 - 420*t^8 + 18*t - 264*t^4 + 378*t^5)*(d/dt)F(t), F(0) = 1}

The a(n) satisfy the recurrence: {a(0) = 1, a(1) = 1, ( - 20779902*n^7 - 134970693*n^6 - 1971620508*n^4 - 2248389*n^8 - 3*n^12 - 4459328640*n - 4242044664*n^3 - 5794678656*n^2 - 618210450*n^5 - 234*n^11 - 1437004800 - 8151*n^10 - 167310*n^9)*a(n) + ( - 7295434560*n - 4550515200 - 914850*n^7 - 5131406304*n^2 - 545289740*n^4 - 2088314700*n^3 - 11400627*n^6 - 95574465*n^5 - 1425*n^9 - 47310*n^8 - 19*n^10)*a(n + 2) + (711103032*n^4 + 8622028800 + 13032306*n^6 + 116250876*n^5 + 2944635984*n^3 + 12385923840*n + 7897844736*n^2 + 18*n^10 + 1404*n^9 + 48708*n^8 + 989496*n^7)*a(n + 3) + ( - 915980400*n - 898128000 - 3060*n^7 - 90090*n^6 - 1499400*n^5 - 15424605*n^4 - 100395540*n^3 - 403611660*n^2 - 45*n^8)*a(n + 4) + (2882376*n^5 + 890994600*n^2 + 2137510944*n + 30916662*n^4 + 210700728*n^3 + 166740*n^6 + 5472*n^7 + 78*n^8 + 2227357440)*a(n + 5) + ( - 1050477120 - 60979*n^6 - 1088733*n^5 - 12105088*n^4 - 27*n^8 - 85853091*n^3 - 379422466*n^2 - 955621272*n - 1944*n^7)*a(n + 6) + (57398400*n + 114*n^6 + 91238400 + 161430*n^4 + 2078100*n^3 + 14985456*n^2 + 6660*n^5)*a(n + 7) + ( - 1225827*n^3 - 58806000 - 63*n^6 - 9078336*n^2 - 92961*n^4 - 3753*n^5 - 35812260*n)*a(n + 8) + (571080*n + 1504800 + 5100*n^3 + 120*n^4 + 81060*n^2)*a(n + 9) + ( - 233178*n - 635976 - 32079*n^2 - 1962*n^3 - 45*n^4)*a(n + 10) + (1116*n + 48*n^2 + 6480)*a(n + 11) + ( - 225*n - 9*n^2 - 1410)*a(n + 12) + 6*a(n + 13) = 0,

with a(2) = 2, a(3) = 16, a(4) = 256, a(5) = 7184, a(6) = 311944, a(7) = 19191448, a(8) = 1584972224, a(9) = 169021538944, a(10) = 22595033625856, a(11) = 3699135711988736, a(12) = 727774085471066752}

Example

a(2)=2 because the two cyclic word coverings are {112, 221} and {111, 222}
a(3)=16: {111 222 333} {111 223 233} {112 122 333} {112 133 223} {113 122 233} {113 123 223} {113 132 223} {112 132 233} {113 133 222} {122 123 133} {122 132 133} {112 123 233} {123 123 123} {123 132 123} {123 132 132} {132 132 132}

Mathematica

RecurrenceTable[{-(-10 + n) (-9 + n) (-8 + n) (-7 + n) (-6 + n) (-5 + n) (-4 + n) (-3 + n) (-2 + n) (-1 + n) (25 - 243 n + 243 n^2) a[-11 + n] + 90 (-9 + n) (-8 + n) (-7 + n) (-6 + n) (-5 + n) (-4 + n) (-3 + n) (-2 + n) (-1 + n) a[-10 + n] - 6 (-8 + n) (-7 + n) (-6 + n) (-5 + n) (-4 + n) (-3 + n) (-2 + n) (-1 + n) (52 - 270 n + 243 n^2) a[-9 + n] + 6 (-7 + n) (-6 + n) (-5 + n) (-4 + n) (-3 + n) (-2 + n) (-1 + n) (-40 + 1240 n - 1458 n^2 + 243 n^3) a[-8 + n] - (-6 + n) (-5 + n) (-4 + n) (-3 + n) (-2 + n) (-1 + n) (-917 - 3537 n + 3159 n^2) a[-7 + n] + 6 (-5 + n) (-4 + n) (-3 + n) (-2 + n) (-1 + n) (-711 + 4555 n - 4941 n^2 + 972 n^3) a[-6 + n] - 9 (-4 + n) (-3 + n) (-2 + n) (-1 + n) (-110 - 3557 n + 5128 n^2 - 1944 n^3 + 243 n^4) a[-5 + n] + 6 (-3 + n) (-2 + n) (-1 + n) (-508 + 4580 n - 5022 n^2 + 1215 n^3) a[-4 + n] - 6 (-2 + n) (-1 + n) (692 - 6471 n + 9309 n^2 - 4374 n^3 + 729 n^4) a[-3 + n] + 6 (-1 + n) (-92 + 2798 n - 3726 n^2 + 1215 n^3) a[-2 + n] - 3 (482 - 2451 n + 4206 n^2 - 2916 n^3 + 729 n^4) a[-1 + n] + 6 (511 - 729 n + 243 n^2) a[n] == 0, a[0] == 1, a[1] == 1, a[2] == 2, a[3] == 16, a[4] == 256, a[5] == 7184, a[6] == 311944, a[7] == 19191448, a[8] == 1584972224, a[9] == 169021538944, a[10] == 22595033625856}, a, {n, 0, 20}] (* Vaclav Kotesovec, Feb 28 2016 *)

Crossrefs

Cf. A052502, A110105, A110106, A110104.

Sequence in context: A009044 A019318 A090727 * A140307 A114039 A090305

Adjacent sequences: A108239 A108240 A108241 * A108243 A108244 A108245

Keyword

nonn

Author

Marni Mishna, Jun 17 2005

Extensions

More terms from Vaclav Kotesovec, Feb 28 2016

Status

approved