A110105 a(n) is the number of coverings of 1..n by cyclic words of length n, 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 not allowed in a given covering.
1, 1, 2, 12, 192, 5744, 260904, 16542648, 1395722688, 151232990208, 20468918305536, 3384387717897216, 671260382408564352, 157302245641224362112, 42996605332700377396992, 13558408172347636250832384, 4885584146166061652811300864, 1994958243661170192648338792448
Offset: 0
Examples
a(2)=2 because the two cyclic word coverings are {112, 221} and {111, 222}.
a(3)=12: {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}.
Links
- Vaclav Kotesovec, Table of n, a(n) for n = 0..240
Programs
-
Mathematica
RecurrenceTable[{-(-10+n) (-9+n) (-8+n) (-7+n) (-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) (-49-243 n+243 n^2) a[-11+n]-126 (-9+n) (-8+n) (-7+n) (-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) a[-10+n]-2 (-8+n) (-7+n) (-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) (-130-162 n+243 n^2) a[-9+n]+6 (-7+n) (-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) (196+1166 n-1458 n^2+243 n^3) a[-8+n]+3 (-6+n) (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) (-931-117 n+243 n^2) a[-7+n]+54 (-5+n) (-4+n) (-3+n) (-2+n) (-1+n) (61-63 n+9 n^2) a[-6+n]-(-4+n) (-3+n) (-2+n) (-1+n) (-3686-21339 n+38682 n^2-17496 n^3+2187 n^4) a[-5+n]-18 (-3+n) (-2+n) (-1+n) (412+410 n-918 n^2+243 n^3) a[-4+n]+18 (-2+n) (-1+n) (14-1659 n+2867 n^2-1458 n^3+243 n^4) a[-3+n]-6 (-1+n) (-344+680 n-810 n^2+243 n^3) a[-2+n]-3 (118-2013 n+3984 n^2-2916 n^3+729 n^4) a[-1+n]+6 (437-729 n+243 n^2) a[n]==0, a[0]==1, a[1]==1, a[2]==2, a[3]==12, a[4]==192, a[5]==5744, a[6]==260904, a[7]==16542648, a[8]==1395722688, a[9]==151232990208, a[10]==20468918305536}, a, {n, 0, 20}] (* Vaclav Kotesovec, Feb 28 2016 *)
Formula
Differential equation satisfied by e.g.f.: {( - 6 + 12*t - 138*t^7 - 12*t^12 + 213*t^6 - 92*t^8 - 126*t^9 - 9*t^14 - 170*t^4 + 54*t^2 + 162*t^11 - 72*t^3 + 162*t^5 + 38*t^10)*F(t) + (6 + 54*t^12 + 72*t^4 + 126*t^3 + 54*t^6 - 324*t^9 - 156*t^8 - 42*t^2 - 18*t - 36*t^10 + 594*t^7 - 378*t^5)*(d/dt)F(t) + (-81*t^10 - 9*t^2 + 216*t^8 - 198*t^6 + 72*t^4)*(d^2/dt^2)F(t), F(0) = 1}.
Recurrence satisfied by a(n): {a(0) = 1, a(10) = 20468918305536, a(11) = 3384387717897216, a(12) = 671260382408564352, a(2) = 2, a(3) = 12, a(4) = 192, a(5) = 5744, a(6) = 260904, a(7) = 16542648, a(8) = 1395722688, a(9) = 151232990208, a(1) = 1, 0 = (3*n^12 + 618210450*n^5 + 20779902*n^7 + 4242044664*n^3 + 134970693*n^6 + 4459328640*n + 1971620508*n^4 + 1437004800 + 5794678656*n^2 + 234*n^11 + 8151*n^10 + 167310*n^9 + 2248389*n^8)*a(n) + (25151175*n^5 + 12450*n^8 + 3000165*n^6 + 1919851200*n + 143497300*n^4 + 549556500*n^3 + 1350370080*n^2 + 5*n^10 + 375*n^9 + 1197504000 + 240750*n^7)*a(n + 2) + (-116250876*n^5 - 18*n^10 - 12385923840*n - 711103032*n^4 - 2944635984*n^3 - 7897844736*n^2 - 8622028800 - 1404*n^9 - 48708*n^8 - 989496*n^7 - 13032306*n^6)*a(n + 3) + (-748*n^7 - 24541132*n^3 - 22022*n^6 - 3770459*n^4 - 98660628*n^2 - 219542400 - 366520*n^5 - 223906320*n - 11*n^8)*a(n + 4) + (240408*n^5 + 2653854*n^4 + 18626328*n^3 + 81157896*n^2 + 200675232*n + 215550720 + 6*n^8 + 432*n^7 + 13524*n^6)*a(n + 5) + (84272481*n^3 + 1083375*n^5 + 11978658*n^4 + 27*n^8 + 60885*n^6 + 914771880*n + 1944*n^7 + 987940800 + 368381790*n^2)*a(n + 6) + (6874416*n^2 + 26085888*n + 75330*n^4 + 961740*n^3 + 41057280 + 54*n^6 + 3132*n^5)*a(n + 7) + (-63*n^6 - 58045680 - 92897*n^4 - 1223139*n^3 - 9036160*n^2 - 35519268*n - 3753*n^5)*a(n + 8) + (-1188*n^2 - 13032*n - 47520 - 36*n^3)*a(n + 9) + (634392 + 232902*n + 45*n^4 + 32067*n^2 + 1962*n^3)*a(n + 10) + (-3024 - 540*n - 24*n^2)*a(n + 11) + (-9*n^2 - 1410 - 225*n)*a(n + 12) + 6*a(n + 13)}.
a(n) ~ 3^(n+1/2) * n^(2*n) / (2^n * exp(2*n)). - Vaclav Kotesovec, Feb 28 2016
Extensions
Original recurrence corrected by Vaclav Kotesovec, following a suggestion of Matthew House, Feb 28 2016
More terms from Vaclav Kotesovec, Feb 28 2016
Comments