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

Author

Marni Mishna, Jun 17 2005

Keywords

• nonn

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

Examples

			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}
		

Links

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

Crossrefs

Cf. A052502, A110105, A110106, A110104.

Programs

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

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}

Extensions

More terms from Vaclav Kotesovec, Feb 28 2016