login
Number of ways to place 6 nonattacking queens on an n X n board.
12

%I #29 Aug 22 2024 14:07:02

%S 4,832,22708,312956,2716096,17117832,84871680,349093856,1239869972,

%T 3905117168,11139611892,29224290600,71402912960,164029487484,

%U 357164398040,741835920276,1477798367368,2836053660668,5263672510684,9478352925488,16606678238496,28378012168908

%N Number of ways to place 6 nonattacking queens on an n X n board.

%H Alois P. Heinz, <a href="/A176186/b176186.txt">Table of n, a(n) for n = 6..10000</a>

%H S. Chaiken, C. R. H. Hanusa and T. Zaslavsky, <a href="http://people.math.binghamton.edu/zaslav/Tpapers/qqs1.pdf">A q-queens problem I. General theory</a>, preprint, August 7, 2014. - From _N. J. A. Sloane_, Feb 16 2013

%H Christopher R. H. Hanusa, T Zaslavsky, S Chaiken, <a href="http://arxiv.org/abs/1609.00853">A q-Queens Problem. IV. Queens, Bishops, Nightriders (and Rooks)</a>, arXiv preprint arXiv:1609.00853 [math.CO], 2016-2020.

%H The formula below was obtained during the programming competition on my <a href="http://zealint.ru/sixqueens-results.html">blog</a> (in Russian). [From _Artem M. Karavaev_, May 10 2010]

%H <a href="/index/Rec#order_81">Index entries for linear recurrences with constant coefficients</a>, signature (-5, -13, -21, -19, 5, 57, 127, 184, 180, 70, -162, -476, -768, -889, -695, -114, 794, 1806, 2570, 2701, 1929, 234, -2072, -4374, -5898, -5950, -4180, -771, 3521, 7530, 9994, 9959, 7119, 1994, -4156, -9657, -12909, -12881, -9447, -3464, 3464, 9447, 12881, 12909, 9657, 4156, -1994, -7119, -9959, -9994, -7530, -3521, 771, 4180, 5950, 5898, 4374, 2072, -234, -1929, -2701, -2570, -1806, -794, 114, 695, 889, 768, 476, 162, -70, -180, -184, -127, -57, -5, 19, 21, 13, 5, 1).

%F Contribution from _Artem M. Karavaev_, May 10 2010: (Start)

%F a(n)=1/720*n^12-5/72*n^11+77/48*n^10-73339/3240*n^9

%F +312607/1440*n^8-66917/45*n^7+2226017/300*n^6

%F -9149222687/340200*n^5+102550276811/1488375*n^4

%F -2786721974671/23814000*n^3+453909010753/3969000*n^2

%F -2166093922711/47628000*n+1/432*(72*n^7-2916*n^6

%F +50580*n^5-485172*n^4+2750088*n^3-8977638*n^2+14596860*n

%F -7467833)*floor(1/2*n)+2/243*(216*n^5-6480*n^4+81308*n^3

%F -525474*n^2+1650126*n-1364199)*floor(1/3*n)

%F +1/243*(216*n^5-6750*n^4+88940*n^3-620184*n^2+2250534*n-3138465)*floor(1/3*n+1/3)

%F +1/4*(116*n^3-2133*n^2+12902*n-13728)*floor(1/4*n)

%F +1/4*(100*n^3-1984*n^2+13696*n-26993)*floor(1/4*n+1/4)

%F -1/4*(16*n^3-149*n^2-794*n+13265)*floor(1/4*n+1/2)

%F +8/125*(100*n^3-1778*n^2+16360*n-19739)*floor(1/5*n)

%F +4/125*(150*n^3-2842*n^2+27521*n-65479)*floor(1/5*n+1/5)

%F +4/125*(100*n^3-1978*n^2+19118*n-54269)*floor(1/5*n+2/5)

%F +4/125*(50*n^3-1014*n^2+10311*n-30319)*floor(1/5*n+3/5)

%F +2/27*(2118*n-4499)*floor(1/6*n)

%F +1/9*(1934*n-6633)*floor(1/6*n+1/6)

%F +2/27*(1566*n-10901)*floor(1/6*n+1/3)

%F -4/9*(92*n+1067)*floor(1/6*n+1/2)

%F -1/27*(2670*n+1903)*floor(1/6*n+2/3)

%F +48/49*(95*n-173)*floor(1/7*n)

%F +4/49*(920*n-3597)*floor(1/7*n+1/7)

%F +8/49*(335*n-1672)*floor(1/7*n+2/7)

%F +4/49*(600*n-3409)*floor(1/7*n+3/7)

%F +8/49*(145*n-926)*floor(1/7*n+4/7)

%F +4/49*(160*n-989)*floor(1/7*n+5/7)

%F +2*(2*n-5)*floor(1/8*n)

%F +2*(2*n-9)*floor(1/8*n+1/8)

%F +2*(2*n-11)*floor(1/8*n+1/4)

%F +2*(2*n-11)*floor(1/8*n+3/8)

%F -12*floor(1/8*n+1/2)

%F -4*floor(1/8*n+5/8).

%F G.f.: -4*x^6*(1+213*x+53192307*x^6+41638044492*x^11+6730*x^2+1148407*x^4

%F +109349*x^3+8814849*x^5+264701695*x^7+1124196463*x^8+4178943637*x^9

%F +13860639977*x^10+114647411058*x^12+65980784446603*x^21+39390545501971*x^20

%F +22595990341656*x^19+12422932793397*x^18+6526629468148*x^17

%F +3265443398940*x^16+1549727363371*x^15+694388440836*x^14

%F +106432971812268*x^22+165658741321711*x^23+249214616002036*x^24

%F +362914602952313*x^25+2587299110418159*x^33+2935747117591644*x^34

%F +3249296395578274*x^35+3508939440356435*x^36+3697993190167173*x^37

%F +3803816547345336*x^38+3819162259356822*x^39+3580483108767024*x^41

%F +512246494510867*x^26+701616116303232*x^27+933484654834212*x^28

%F +1207502931973542*x^29+1519776851512400*x^30+1862408041738532*x^31

%F +2223440299348897*x^32+3045052266009747*x^43+2706059061856895*x^44

%F +2345222492958126*x^45+1981371771386641*x^46+1631097942913736*x^47

%F +1307636222431031*x^48+1020253102328739*x^49+774143005387556*x^50

%F +570765121032393*x^51+408502373125992*x^52+283498964529980*x^53

%F +190537440843487*x^54+123839006896190*x^55+77709213130439*x^56

%F +46991003436040*x^57+27324795064304*x^58+15241746945993*x^59

%F +8132464535507*x^60+4137125169063*x^61+1998986925515*x^62

%F +913299307705*x^63+392473060699*x^64+157632673869*x^65+58720300345*x^66

%F +20096128176*x^67+6243623123*x^68+1733735219*x^69+421322394*x^70

%F +86868206*x^71+14475708*x^72+1769106*x^73+125388*x^74+292139023877*x^13

%F +3742970026288202*x^40+3342672506335632*x^42)

%F /(x-1)^13/(x+1)^8/(x^2+x+1)^6/(x^2+1)^4/(x^4+x^3+x^2+x+1)^4

%F /(x^2-x+1)^2/(x^6+x^5+x^4+x^3+x^2+x+1)^2/(x^4+1)^2.

%F Recurrence: a(0) = 0, a(1) = 0, a(2) = 0, a(3) = 0, a(4) = 0, a(5) = 0,

%F a(6) = 4,

%F a(7) = 832,

%F a(8) = 22708,

%F a(9) = 312956,

%F a(10) = 2716096,

%F a(11) = 17117832,

%F a(12) = 84871680,

%F a(13) = 349093856,

%F a(14) = 1239869972,

%F a(15) = 3905117168,

%F a(16) = 11139611892,

%F a(17) = 29224290600,

%F a(18) = 71402912960,

%F a(19) = 164029487484,

%F a(20) = 357164398040,

%F a(21) = 741835920276,

%F a(22) = 1477798367368,

%F a(23) = 2836053660668,

%F a(24) = 5263672510684,

%F a(25) = 9478352925488,

%F a(26) = 16606678238496,

%F a(27) = 28378012168908,

%F a(28) = 47398421913600,

%F a(29) = 77522788818316,

%F a(30) = 124365738451680,

%F a(31) = 195977208395580,

%F a(32) = 303748457927000,

%F a(33) = 463582807382736,

%F a(34) = 697434075907504,

%F a(35) = 1035256352634420,

%F a(36) = 1517521355687872,

%F a(37) = 2198354851112760,

%F a(38) = 3149525540545556,

%F a(39) = 4465340754179496,

%F a(40) = 6268789672000200,

%F a(41) = 8718985543275112,

%F a(42) = 12020393279930400,

%F a(43) = 16433877629761792,

%F a(44) = 22290259302807700,

%F a(45) = 30006374870365136,

%F a(46) = 40104595602917300,

%F a(47) = 53235736336244300,

%F a(48) = 70206658745546392,

%F a(49) = 92012392107526748,

%F a(50) = 119874540287319196,

%F a(51) = 155285624835663096,

%F a(52) = 200061731591400456,

%F a(53) = 256402868739653996,

%F a(54) = 326964160566718884,

%F a(55) = 414936937933564876,

%F a(56) = 524143826614930088,

%F a(57) = 659146400314780240,

%F a(58) = 825370726096096944,

%F a(59) = 1029248723087783480,

%F a(60) = 1278382175175730400,

%F a(61) = 1581726455456457436,

%F a(62) = 1949802708715765760,

%F a(63) = 2394934394370749612,

%F a(64) = 2931519277634600260,

%F a(65) = 3576331321283597364,

%F a(66) = 4348866396076652064,

%F a(67) = 5271724407012487004,

%F a(68) = 6371045245979662116,

%F a(69) = 7676988784016499040,

%F a(70) = 9224280528369282176,

%F a(71) = 11052810248193489712,

%F a(72) = 13208310203912865056,

%F a(73) = 15743096674420482872,

%F a(74) = 18716907492532573788,

%F a(75) = 22197814778572880876,

%F a(76) = 26263252803050925204,

%F a(77) = 31001134787399966700,

%F a(78) = 36511107035656245460,

%F a(79) = 42905907681877306448,

%F a(80) = 50312888556807094572,

%F a(n) = a(n-81)+5*a(n-80)+13*a(n-79)+21*a(n-78)+19*a(n-77)

%F -5*a(n-76)-57*a(n-75)-127*a(n-74)-184*a(n-73)-180*a(n-72)

%F -70*a(n-71)+162*a(n-70)+476*a(n-69)+768*a(n-68)

%F +889*a(n-67)+695*a(n-66)+114*a(n-65)-794*a(n-64)

%F -1806*a(n-63)-2570*a(n-62)-2701*a(n-61)-1929*a(n-60)

%F -234*a(n-59)+2072*a(n-58)+4374*a(n-57)+5898*a(n-56)

%F +5950*a(n-55)+4180*a(n-54)+771*a(n-53)-3521*a(n-52)

%F -7530*a(n-51)-9994*a(n-50)-9959*a(n-49)-7119*a(n-48)

%F -1994*a(n-47)+4156*a(n-46)+9657*a(n-45)+12909*a(n-44)

%F +12881*a(n-43)+9447*a(n-42)+3464*a(n-41)-3464*a(n-40)

%F -9447*a(n-39)-12881*a(n-38)-12909*a(n-37)-9657*a(n-36)

%F -4156*a(n-35)+1994*a(n-34)+7119*a(n-33)+9959*a(n-32)

%F +9994*a(n-31)+7530*a(n-30)+3521*a(n-29)-771*a(n-28)

%F -4180*a(n-27)-5950*a(n-26)-5898*a(n-25)-4374*a(n-24)

%F -2072*a(n-23)+234*a(n-22)+1929*a(n-21)+2701*a(n-20)

%F +2570*a(n-19)+1806*a(n-18)+794*a(n-17)-114*a(n-16)

%F -695*a(n-15)-889*a(n-14)-768*a(n-13)-476*a(n-12)

%F -162*a(n-11)+70*a(n-10)+180*a(n-9)+184*a(n-8)

%F +127*a(n-7)+57*a(n-6)+5*a(n-5)-19*a(n-4)-21*a(n-3)

%F -13*a(n-2)-5*a(n-1), n>80.

%F (End)

%t (* Alternative formula by Vaclav Kotesovec *)

%t q6nn = 1/720*n^12-5/72*n^11+77/48*n^10-73339/3240*n^9+312727/1440*n^8-268283/180*n^7+26932229/3600*n^6-18719233399/680400*n^5+577434913967/7938000*n^4-117739826734/893025*n^3+112056711821/756000*n^2-393833819123/4762800*n+749037381271/68040000\

%t +(1/24*n^7-27/16*n^6+1405/48*n^5-13477/48*n^4+114587/72*n^3-1496273/288*n^2+1216405/144*n-7467833/1728)*(-1)^n\

%t +(25*n^3/4-124*n^2+856*n-26993/16)*Sqrt[2]*Cos[Pi*n/2+Pi/4]\

%t +(33*n^3/4-1141*n^2/8+3027*n/4-463/16)*Sqrt[2]*Sin[Pi*n/2+Pi/4]\

%t +2/243*((383792n-552926)*Cos[Pi*n/3]\

%t +(493229-366386*n)*Cos[Pi*n/3+Pi/3]\

%t +(531641-363074*n)*Sin[Pi*n/3+Pi/6])\

%t +2*(366386*n-493229)*Sqrt[3]*Cos[2*Pi*n/3+Pi/6]/729\

%t -(16*n^5/81-500*n^4/81+177880*n^3/2187-413456*n^2/729+767584*n/729-1105852/729)*Sqrt[3]*Sin[2*Pi*n/3]\

%t +(32*n^5/81-320*n^4/27+325232*n^3/2187-77848*n^2/81+18116*n/9-832474/729)*Sqrt[3]*Sin[2*Pi*n/3+Pi/3]\

%t +(2*n-11)/2*(Sqrt[2]+1)*Cos[Pi*n/4+Pi/4]\

%t +(Sqrt[4+2*Sqrt[2]]/4)*((2*n+1)*Sin[Pi*n/4+Pi/8]+(2*n-7)*Sin[Pi*n/4+3*Pi/8])\

%t +(2*n-11)/2*(Sqrt[2]-1)*Sin[3*Pi*n/4+Pi/4]\

%t +(Sqrt[4-2*Sqrt[2]]/4)*((7-2*n)*Sin[3*Pi*n/4+Pi/8]+(2*n+1)*Sin[3*Pi*n/4+3*Pi/8])\

%t +((4*Sqrt[50+10*Sqrt[5]])/3125)*((150*n^3-2842*n^2+27521*n-65479)*Cos[2*Pi*n/5+Pi/10]\

%t -(100*n^3-1978*n^2+19118*n-54269)*Sin[2*Pi*n/5]\

%t +2*(100*n^3-1778*n^2+16360*n-19739)*Sin[2*Pi*n/5+Pi/5]\

%t -(50*n^3-1014*n^2+10311*n-30319)*Sin[2*Pi*n/5+2*Pi/5])\

%t +((4*Sqrt[50-10*Sqrt[5]])/3125)*((50*n^3-1014*n^2+10311*n-30319)*Cos[4*Pi*n/5+3*Pi/10]\

%t +(100*n^3-1978*n^2+19118*n-54269)*Sin[4*Pi*n/5]\

%t -(150*n^3-2842*n^2+27521*n-65479)*Sin[4*Pi*n/5+Pi/5]\

%t +2*(100*n^3-1778*n^2+16360*n-19739)*Sin[4*Pi*n/5+2*Pi/5])\

%t +4/(343*Sin[Pi/7])*((989-160*n)*Cos[2*Pi*n/7+Pi/14]\

%t +2*(335*n-1672)*Cos[2*Pi*n/7+3*Pi/14]\

%t +(3409-600*n)*Sin[2*Pi*n/7]\

%t +12*(95*n-173)*Sin[2*Pi*n/7+Pi/7]\

%t +2*(926-145*n)*Sin[2*Pi*n/7+2*Pi/7]\

%t +(920*n-3597)*Sin[2*Pi*n/7+3*Pi/7])\

%t +4/(343*Cos[3*Pi/14])*(2*(145*n-926)*Cos[4*Pi*n/7+Pi/14]\

%t +(920*n-3597)*Cos[4*Pi*n/7+5*Pi/14]\

%t +(600*n-3409)*Sin[4*Pi*n/7]\

%t +(989-160*n)*Sin[4*Pi*n/7+Pi/7]\

%t +12*(95*n-173)*Sin[4*Pi*n/7+2*Pi/7]\

%t +2*(1672-335*n)*Sin[4*Pi*n/7+3*Pi/7])\

%t +4/(343*Cos[Pi/14])*((160*n-989)*Cos[6*Pi*n/7+3*Pi/14]\

%t +2*(926-145*n)*Cos[6*Pi*n/7+5*Pi/14]\

%t +(3409-600*n)*Sin[6*Pi*n/7]\

%t +(3597-920*n)*Sin[6*Pi*n/7+2*Pi/7]\

%t +12*(95*n-173)*Sin[6*Pi*n/7+3*Pi/7]\

%t +2*(335*n-1672)*Sin[6*Pi*n/7+Pi/7])

%Y Cf. A108792.

%Y Column k=6 of A348129.

%K nonn,nice,easy

%O 6,1

%A _Artem M. Karavaev_, Apr 11 2010