OLD ARTICLE (no longer updated!)

For compatibility of links I keep this page, but I strongly recommend my book in PDF format with all these results and much more.
The book was published 22.4.2010, second edition 23.6.2010, third edition 19.1.2011, fourth edition 15.6.2011, fifth edition 9.1.2012, sixth edition 2.2.2013.

Number of ways of placing non-attacking
queens, kings, bishops and knights

on boards of various sizes

(Vaclav Kotesovec, 1996-2010)


This article is based on part of book "Between chessboard and computer", Vaclav Kotesovec, 1996. Pages 204-6 is a straight piece of combinatorial mathematics concerning the number of ways of placing non-attacking kings and queens on boards of various sizes. Now new results and formulas since 1996 are published.

Tento článek je věnován problematice počtu rozmístění neohrožujících se kamenů stejných hodnot na různých velikostech a typech šachovnic. Nejznámější z těchto problémů je tzv. n-Queens problem, který řeší počet rozmístění n neohrožujících se dam na šachovnici n x n. O tomto problému byla napsána již spousta článků a základní informace a přehled linků je možno nalézt na mojí stránce links. Můj článek má ale širší záběr a věnuje se různým typům kamenů i šachovnic. Základ článku tvoří jeho verze z roku 1996, publikovaná v mé knize "Mezi šachovnicí a počítačem", str.204-206. Od roku 1996 došlo k výraznému zrychlení počítačů, což umožnilo získat další výsledky a odvodit řadu nových vzorců.

Content - Obsah

1.1 Queens on board n x n
1.2 Queens on board k x n
1.3 Conjectures for Q(n), n ® Ą
1.4 Queens on toroidal board n x n

2.1 Kings on board n x n
2.2 Kings on board k x n
2.3 Kings on boards of various size

3.1 Rooks on board n x n
3.2 Rooks on board k x n

4.1 Bishops on board n x n
4.2 Bishops on board k x n

5.1 Knights on board n x n
5.2 Knights on board k x n
5.3 Knights on cylindrical board n x n
5.4 Knights on toroidal board n x n

6.1 Nightriders on board n x n
6.2 Nightriders on board k x n

7.1 Amazons (superqueens) on board n x n
7.2 Amazons (superqueens) on board k x n

8.1 Zebras on board n x n
8.2 Zebras on board k x n

9.1 Wazirs on board n x n
9.2 Wazirs on board k x n

10. Other fairy pieces


1.1) Queens on board n x n - Dámy na šachovnici n x n

2 Queens, board nxn (E.Lucas, 1891): n(n-1)(n-2)(3n-1)/6

3 Queens, board nxn (E.Landau, 1896): n(n-2)2(2n3-12n2+23n-10)/12, pro n sudé (even),
(n-1)(n-3)(2n4-12n3+25n2-14n+1)/12, pro n liché (odd)

4 Queens, board nxn (V.Kotesovec, 1992): n>=2 : n8/24 - 5n7/6 + 65n6/9 - 1051n5/30 + 817n4/8 - ...

a dále podle typu n:

a) n=6k, -4769n3/27 + 1963n2/12 - 1769n/30

b) n=6k+1, -9565n3/54 + 1013n2/6 - 6727n/90 + 257/27

c) n=6k+2, -4769n3/27 + 1963n2/12 - 5467n/90 + 28/27

d) n=6k+3, -9565n3/54 + 1013n2/6 - 2189n/30 + 7

e) n=6k+4, -4769n3/27 + 1963n2/12 - 5467n/90 + 68/27

f) n=6k+5, -9565n3/54 + 1013n2/6 - 6727n/90 + 217/27

Koeficienty u n3 a n2, jdou vyjádřit také takto: -19103/108 + (-1)n/4 , -3989/24 - 21(-1)n/8


V roce 2005 našel S.Perepechko pro tento můj vzorec zápis formálně sjednocující všech 6 případů. Sergey Perepechko (2005) convert these 6 formulas by Vaclav Kotesovec (1992) into 1 unified expression, kde [x]=floor(x) je celá část (largest integer not greater than x)
n(n-1)(45n6-855n5+6945n4-30891n3+78864n2-106226n+53404)/1080 + (n3-21/2*n2+28n-14)[n/2]+32/9(n-1)[n/3]+(16/9*n-4)[(n+1)/3]

Na základě řešení diferenční rovnice jsem ještě odvodil jiný jednotný vzorec pro tuto funkci (dávající pro celočíselné hodnoty n stejné výsledky):
n8/24 - 5n7/6 + 65n6/9 - 1051n5/30 + 817n4/8 - 19103n3/108 + 3989n2/24 - 18131n/270 + 253/54 + (n3/4 - 21n2/8 + 7n - 7/2)*(-1)n + 32(n-1)/27*COS(2*pi*n/3) + 40/81*3(1/2)*SIN(2*pi*n/3)

Pro k dam na šachovnici n x n je odhad průběhu této funkce:
n2k/k!-5/3n2k-1/(k-2)!+O(n2k-2)

Důkaz, že pro libovolné k je příslušná vytvořující funkce (generating function) racionální (tedy že jde o podíl dvou polynomů s celočíselnými koeficienty) uvádí v knize "Enumerative Combinatorics", vol. I (1986), Richard P. Stanley (chapter 4, exercise 15, solution page 280-1). Tím je dán tvar řešení pro všechny tyto funkce, který obsahuje vždy polynom s konstantními koeficienty plus součet dalších tzv. Quasi-polynomů (nazývaných též "pseudo-polynomial" nebo "polynomial on residue classes"), což jsou polynomy, jejichž koeficienty jsou periodické funkce s integer periodou. Odtud vyplývá, že k nalezení příslušného vzorce pro danou sekvenci potřebujeme vždy znát jen dostatečný počet známých hodnot. Potom jde o nalezení nejmenší periody a určení koeficientů přílušných polynomů. Háček je jedině v tom, že časově možný je výpočet jen do určité hodnoty n a ta nemusí být postačující pro nalezení všech koeficientů (viz např. případ 3 tátošů, kde jsem pro objevení obecného vzorce potřeboval přes 300 hodnot!). Proto vzorce pro vyšší hodnoty k budou postupně přibývat až se zrychlováním počítačů.

Vzorce jsou i v On-Line Encyclopedia of Integer Sequences (Neil J. A. Sloane)
A036464 - 2Q NxN
A047659 - 3Q NxN
A061994 - 4Q NxN
A108792 - 5Q NxN - I found formula, see my book kotesovec_non_attacking_chess_pieces_2011_4ed.pdf for more!

Viz Edouard Lucas: Théorie des nombres (1891), vzorec pro počet rozmístění 2 neohrožujících se dam najdeme na str.98, dále je uveden též v knize Edouard Lucas: Récréations mathématiques (1894) str.132
Viz Naturwissenschaftliche wochenschrift (1896) - v čísle z 2.8.1896, str.367-371 (str.380 v PDF) je článek "Ueber das Achtdamenproblem und seine Verallgemeinerung", jehož autorem je Edmund Landau. V článku jsou odvozeny vzorce pro rozmístění 3 dam na šachovnici n x n (pro sudé a liché n). Je zajímavé, že tento slavný německý matematik objevil vzorec už ve svých 19 letech.

Této problematice byly věnovány také 2 články ve francouzském časopise "Rex Multiplex". Ve druhém byly publikovány moje nové výsledky.
Rex Multiplex 18/1986, (page 615, Louis Azemard, Echecs et Mathématiques) "Placements et Configurations pour 2, 3 et 4 Dames"
Rex Multiplex 38/1992, (Louis Azemard, Echecs et Mathématiques), "Une communication de Vaclav Kotesovec"

Poznámka: Panos Louridas publikoval v idee & form 93/2007 (str. 2936-2938) obecnější vzorec pro rozmístění 3 dam na šachovnici m x n. Vzorec je však dost neelegantní (zabírá skoro půl stránky), proto zájemce odkazuji na tento článek.


Tabulka udává rozmístění k dam na šachovnici nxn, diagonála odpovídá problému n-dam.

nk=2k=3k=4k=5n queens, nxn
20   0
380  0
444242 2
5140204821010
634010249822484
770036287002461840
8128810320345684673692
9218425096131248310496352
103480544004125961535440724
115280107880112383261102562680
12770019940027393862060954414200
131086834802061062146096309473712
141492457926412654614162323448365596
1520020926324246756503961554662279184
162632014315844570472489904695214772512
1734000214804880999104191774344895815104
184324831411201381701483879011584666090624
1954264449025622793878874910808444968057848
206726062910003651067381389216423239029188884
2182460865686056968157424854703014314666222712
2210010011721600868289594430713830402691008701644
231204281564134012957759467253283179424233937684440
24143704205971041897176508119038462248227514171973736
251702002679714427299097961908492990762207893435808352
2620020034479744386643995629954750872822317699616364044
27234000439157685397191260461105824676?
28271908554117207434046062697264240408?
2931424469312516101141267901037206552414?
3036134086004800136042877061519678218528?
31413540105919940181059200062195518394830?
32471200129537600238606112363130809484640?
33534688157388960311561434764410583469036?
3460438419006054440333505448??
3568068022819766451794268148??
3676398027250850466009149958??
3785470032376778883526964218??
38953268382821120104984952954??
391060124450588876131119515534??
401175720528070800162778537232??


Zde je link na samotný "n-queens problem":
A000170 - NQ NxN - počty řešení na šachovnici NxN (Ways of placing n nonattacking queens on n x n board).


1.2) Queens on board k x n - Dámy na šachovnici k x n

2 Queens, board 2xn: (n-1)(n-2)

3 Queens, board 3xn: (n-3)(n2-6n+12), (E.Pauls, 1874)

4 Queens, board 4xn: n4-18n3+139n2-534n+840, n>=7, (M.Tarry, 1890)

5 Queens, board 5xn: n5-30n4+407n3-3098n2+13104n-24332, n>=11, (V.Kotesovec, 1992)

6 Queens, board 6xn: n6-45n5+943n4-11755n3+91480n2-418390n+870920, n>=17 (V.Kotesovec, 1992)

7 Queens, board 7xn: n7-63n6+1879n5-34411n4+417178n3-3336014n2+16209916n-36693996, n>=23 (V.Kotesovec, 1992)

8 Queens, board 8xn: n8-84n7+3378n6-85078n5+1467563n4-17723656n3+145910074n2-745654756n+1802501048, n>=31 (V.Kotesovec, 3.2.2010)


Obecně mají polynomy tvar: nk - 3k(k-1)/2*nk-1 + (9k4/8-29k3/12-k2/8+23k/12-1/4+(-1)k/4)*nk-2 - ...
(sekvence u třetího členu by tedy měla pokračovat takto: 0, 2, 30, 139, 407, 943, 1879, 3378, 5626, 8840, ...)
Koeficient u nk-1 jsem odhadl již v roce 1992, koeficient u nk-2 odvodil Ludovit Lačný v roce 2001, viz články "150 rokov problému osmich dám", L. Lacny, Pat a Mat 32/2001, str. 17-20 a Co nového v problému N - dam (What's new in N-queens problem), V. Kotesovec, Pat a Mat 32/2001, str.20-21. Nyní jsem tento vzorec potvrdil jinou metodou.

Tyto vzorce se dostaly i do OEIS
A061989 - 3Q 3xN
A061990 - 4Q 4xN
A061991 - 5Q 5xN
A061992 - 6Q 6xN
A061993 - 7Q 7xN
A172449 - 8Q 8xN

O autorech vzorců pro k=3 a k=4 se zmiňuje Wilhelm Ahrens ve své knize Mathematische Unterhaltungen und Spiele (vydání z roku 1921) na str.277.
Vzorec pro k=3 publikoval E.Pauls, "Das Maximalproblem der Damen auf dem Schachbrette", Deutsche Schachzeitung, 1874, str.261-263
Vzorec pro k=4 publikoval M. Harold Tarry na kongresu francouzských matematiků v roce 1890 v Limoges. Ve své přednášce uvedl i vzorce pro k=2 a k=3 a je proto v literatuře občas uváděn i jako autor těchto vzorců (vzorec pro k=3 však vymyslel již v roce 1874 E.Pauls). V Intermédiaire des Mathématiciens 1903, str.297-8 (str.682 v PDF) potom Tarry vyzval matematiky k nalezení obdobného vzorce pro šachovnici 5 x n, nikdo však takový vzorec nenalezl. Tento problém pak vyřešil až Václav Kotěšovec v roce 1992.

Poznámka: Ke stejným výsledkům (pro k=2,3,4,5,6) došli v článku Nonattacking queens in a rectangular strip (PDF) (na str.16) Thomas Zaslavsky, Seth Chaiken a Christopher R.H. Hanusa (2009). Bohužel jejich další výsledky (uvedené v tomto článku) pro střelce, jezdce a tátoše jsou chybné, protože uvažovali jen taková rozmístění, kde na každém sloupci stojí právě 1 kámen. To platí pro dámy a věže, ale v případě jiných kamenů může stát na jednom sloupci 2 i více neohrožujících se kamenů stejných hodnot. Formulas for queens and rooks in this article are same, but for bishops, knights and nightriders with additional condition "there is to be one piece in each row".


Jelikož vzorce pro rozmístění k dam na šachovnici kxn platí vždy až od jistého n, jsou v následující tabulce uvedeny počty i pro malá n, kde vzorce ještě neplatí (červená čísla). Sloupec vpravo představuje počty rozmístění vzájemně se neohrožujících n dam na šachovnici nxn (jehož speciálním případem je známý problém 8 dam, který vyřešil již v roce 1850 slavný matematik Gauss). Odvodit obecný vzorec se zatím nepodařilo a i jen tyto dílčí výsledky naznačují, o jak obtížný problém se jedná (porovnejte s diagonálou v tabulce).

nk=2k=3k=4k=5k=6k=7k=8n queens,nxn
20      0
320     0
4642    2
512141210   10
6203646404  4
730761401649440 40
8421403445685503129292
9562347321614229220381066352
107236414003916755296327828724
1190536246884922136237248441482680
121107564080168525285612010419527014200
13132103064043110011769433501070769873712
1415613649632540682414848350562211868365596
1518217641398089428463038189770261201362279184
1621022361968814181283881639984561532470814772512
17240278627020216932144800279070943531206495815104
1827234203626432170023982921481830075937606666090624
193064144477324643483832374265129421539429644968057848
2034249646176065454859351204556285229659053639029188884
21380588678708903532894151475580634546621416314666222712
224206916989601224212131452921215200209689107322691008701644
234628060122924163130018908302190031678165911417024233937684440
2450693241510322141428266705842898790922754780934227514171973736
255521071418374027732683696117043242015444493614422207893435808352
2660012236221528354765250409604632159540700957272822317699616364044
276501389626490044876926775818290737650210796663102?
2870215700314384561890089874912128083334816292133888?
29756176543705326969308117767194178056960224128511810?
30812197644339208569588152596220244078688435125842896?
318702203650514810453172195692094330282955050334575910?
329302447658484012656372248569672441626613271085565752?
339922709067364415218500312945122584007661899047961338?
34105629884772232181819883907532047643950612136295785608?
35112232864881300215925084841652709909701414185384054238?
3611903603610015682549909259560798412732801060249435319880?
3712603940611337802995425272778276216224041362332237569362?
3813324298012787043501410088368593220511325988438354441528?
39140646764143713240738468106662961425741598622573248773718?
40148250764160988047191028128026332032082912244743420525208?



1.3) Conjectures - Hypotézy o funkci Q(n) pro n ® Ą

Jeden z nejzajímavějších článků o problému N-dam je Igor Rivin, Ilan Vardi and Paul Zimmermann: The n-Queens Problem, The American Mathematical Monthly, 101 (7/1994), str.629-639. Autoři zde analyzují "klasický" problém N-dam a počet různých pozic označují Q(n). Pro mnohé bude překvapující, že neohrožující se dámy je možné rozestavit též na prstencové šachovnici (toroidal board) pro některá lichá n. Tuto funkci označují T(n).
(poznámka: Bernd Eickenscheidt dokázal v článku Das n-Damen-Problem auf dem Zylinderbrett (feenschach 50/1980, str.382-5), že v případě válcové nebo prstencové šachovnice má problém n-dam řešení jen pro taková n, která nejsou dělitelná 2 ani 3). Jak jsem však zjistil v literatuře, důkaz tohoto tvrzení provedl mnohem dříve již Polya.

1) Rivin, Vardi a Zimmermann vyslovují hypotézu o průběhu těchto funkcí. Obě funkce jsou podle nich řádu nan, kde konstanta a < 1. Jaká je přesně hodnota obou konstant pro tyto funkce však není známo. (hodnoty jsem doplnil o aktuální výsledky, tehdy jen do n=20)

2) Jak se zdá, byla tato hypotéza vyvrácena - Dronninger pa et skakbrat - článek v dánštině z 27.9.2000, jehož autorem je Birger Nielsen. Vyslovuje zde hypotézu, že funkce Q(n) je řádu Q(n) ~ n!*p(n-1), kde p=0.3885... Dokládá to výpočty pro N až do 23 a hodnota p je mimořádně stabilní (na rozdíl od konstant ve výše citovaném článku), z čehož lze usuzovat, že řada je možná konvergentní. Naprosto unikátní objev! (viz hodnoty v tabulce dále)

3) 10.11.2002 vyslovil podobnou hypotézu Benoit Cloitre, podle něj funkce 1/n*log(n!/Q(n)) pro n®Ą konverguje ke konstantě C~0.90... (added 10.12.2004). Je zajímavé, že mezi touto konstantou C a konstantou P z hypotézy B.Nielsena platí (pro n®Ą) jednoduchý vztah c=-log(p). Takže pokud p=0.3885..., muselo by být c=0.9454...

4) Další pozoruhodný výsledek publikovali 28.8.2008 Cheng Zhang and Jianpeng Ma. V článku Counting Solutions for the N-queens and Latin Square Problems by Efficient Monte Carlo Simulations (PDF) došli pomocí simulací metodou Monte Carlo k (zatím asi nejpřesnějšímu) vztahu:
log (n!/Q(n)) ~ 0.944001*n - 0.937
s maximální chybou 0.02 (pro n > 100)
Zatímco předchozí hypotézy vznikaly na základě pokusů o extrapolaci ze známých (přesných) výsledků, tedy pouze z něco přes 20 čísel, tento výsledek má jiný charakter. Autoři simulovali problém až do šachovnic N x N, kde N=10000. Takové výsledky, podložené teorií pravděpodobnosti, mají proto větší váhu. Jejich metoda nám sice nepřinese přesné hodnoty Q(n) pro jednotlivá N, ale u odhadů lze stanovit rozsah pravděpodobné chyby. Je to proto první rovnice, která není jen hypotézou, ale opravdovým výsledkem řešení tohoto problému. (viz hodnoty v tabulce dále)
Tento výsledek je téměř shodný s hypotézou Birger Nielsena, neboť přepočtem vychází Q(n) ~ e0.937*n!*e-0.944*n
po úpravách z toho dostaneme Q(n) ~ 2.552*n!*0.389n
což se dá napsat také jako Q(n) ~ 0.993*n!*0.389(n-1)
a nyní už je na místě otázka, zda konstanta 0.993 nemá být spíš 1 ?
Pokud bychom obráceně vyšli z (elegantnější) hypotézy Birger Nielsena, lze ji převést do tvaru
log (n!/Q(n)) ~ 0.9454*n - 0.9454
Rozdíl je tedy pouze v tom, že zde jsou obě konstanty shodné.
A pro "c" ze vztahu Benoit Cloitrea dostáváme limitně přímo hodnotu 0.944001..., resp. 0.9454...


nT(n)log T(n)/(n log n)Q(n)log Q(n)/(n log n)(Q(n)/n!)(1/(n-1))1/n*log(n!/Q(n))(0.937+log(n!/Q(n)))/n
11-1----
20-0----
30-0----
40-20.125000.4367900.62122666240.855476662
5100.28613100.286130.5372850.49698132990.684381330
60-40.128950.3539530.86549280841.021659475
7280.24463400.270810.4466200.69089741520.824754558
80-920.271810.4193820.76035179070.877476791
90-3520.296510.4200950.77091070040.875021812
100-7240.285970.3880490.85196211800.945662118
11880.1697426800.299260.3825590.87352143380.958703252
120-142000.320630.3875780.86885143760.946934771
1345240.25243737120.336120.3885420.87263407430.944710997
140-3655960.346690.3857920.88442407180.951352643
150-22791840.360390.3878490.88399622270.946462889
160-147725120.372130.3889760.88522383690.943786337
171406920.24612958151040.381560.3885060.88983191510.944949562
180-6660906240.390500.3883710.89325049530.945306051
198204960.2434149680578480.399080.3886020.89545207160.944767861
200-390291888840.407030.3888220.89740204120.944252041
210-3146662227120.414080.3885750.90025526640.944874314
220-26910087016440.420870.3885830.90228382410.944874733
231288500480.25894242339376844400.427340.3887170.90382175720.944560888
240-2275141719737360.433410.3888230.90527065630.944312323
2519577250000.2658622078934358083520.439040.3887960.90691159850.944391599
260-223176996163640440.444380.3887950.90836712680.944405588
270-?????
280-?????
296059170553560.27782?????
300-?????
31134049476817120.28394?????
320-?????
330-?????
340-?????
35???????
.       
Ą ®1 ? ®1 ?®0.3885... ?®0.9454... ?®0.9440... ?
Updated for n=24 (4.12.2004), for n=25 (25.6.2005) and for n=26 (21.1.2010)

Pokud přijmeme hypotézu B.Nielsena, pak s použitím Stirlingova vzorce n! ~ nn e-n Ö(2 p n) dostaneme

lim
n® Ą 
ć
ç
č
log Q(n)
n log(n)
ö
÷
ř
=1
a tím pádem obě konstanty z hypotézy Rivin+Vardi+Zimmermann ®1, což tuto hypotézu znehodnocuje.

Odkazy na jiné stránky s podobnou problematikou links


1.4) Queens on toroidal board n x n - Dámy na prstencové šachovnici n x n

Prstencová šachovnice je kombinace vertikální a horizontální válcové šachovnice. Toroidal chessboard (anchor-ring) - board on which the a- and h-files are joined and the bottom and top ranks are also joined. The anchor-ring is a combination of the vertical and horizontal cylinders.

2 Queens, toroidal board nxn:
n2(n-2)2/2, pro n sudé (even),
n2(n-1)(n-3)/2, pro n liché (odd)

3 Queens, toroidal board nxn:
n2(n-2)(n-4)(n2-6n+12)/6, pro n sudé (even), (V. Kotesovec, 31.1.2010)
n2(n-1)(n-3)(n2-8n+18)/6, pro n liché (odd), (V. Kotesovec, 31.1.2010)

4 Queens, toroidal board nxn:
Počet rozmístění 4 neohrožujících se dam na prstencové šachovnici se dá vyjádřit buď tímto jedním vzorcem nebo 12 vzorci odpovídajícími velikosti šachovnice (podle zbytku po dělení 12). Někoho možná překvapí funkce cosinus ve vzorci, taková řešení však jsou obvyklá, pokud charakteristická rovnice pro příslušnou diferenční rovnici má imaginární kořeny. Výsledné hodnoty jsou vždy celočíselné a nejmenší perioda je 12.
(n8/24 - n7 + 245n6/24 - 113n5/2 + 2843n4/16 - 593n3/2 + 4757n2/24) + (n6/8 - 5n5/2 + 305n4/16 - 129n3/2 + 629n2/8)*(-1)n + 8n2*COS(2*pi*n/3)/3 + 9n2*COS(pi*n/2)/2, (V. Kotesovec, 5.2.2010)

explicit formula by Vaclav Kotesovec

4 Queens
toroidal nxn
n=
n8n7n6n5n4n3n2n1n0
12a1/24-131/3-59787/4-36128400
12a+11/24-1121/12-541269/8-232473/400
12a+21/24-131/3-59787/4-36127100
12a+31/24-1121/12-541269/8-232489/400
12a+41/24-131/3-59787/4-36128000
12a+51/24-1121/12-541269/8-232473/400
12a+61/24-131/3-59787/4-36127500
12a+71/24-1121/12-541269/8-232473/400
12a+81/24-131/3-59787/4-36128000
12a+91/24-1121/12-541269/8-232489/400
12a+101/24-131/3-59787/4-36127100
12a+111/24-1121/12-541269/8-232473/400

Rekurentní vztah:
an = -an-1+3an-2+6an-3+3an-4-9an-5-20an-6-11an-7+15an-8+40an-9+31an-10-15an-11-53an-12-50an-13+50an-15+53an-16+15an-17-31an-18-40an-19-15an-20+11an-21+20an-22+9an-23-3an-24-6an-25-3an-26+an-27+an-28
(pro n>=29, člen n-14 má koeficient 0)


5 Queens, toroidal board nxn:
1/120*n10-1/3*n9+143/24*n8-373/6*n7+99377/240*n6-3603/2*n5+119627/24*n4-23833/3*n3+16342/3*n2
+ (1/24*n8-3/2*n7+1111/48*n6-391/2*n5+7595/8*n4-2487*n3+8032/3*n2)*(-1)n
+ (9/2*n4-78*n3+374*n2)*COS(pi*n/2)
+ (8/3*n4-128/3*n3+656/3*n2)*COS(2*pi*n/3)
+ 80/3*n2*COS(pi*n/3)
+ 16/5*n2*COS(2*pi*n/5)
+ 16/5*n2*COS(pi*n/5)*(-1)n, (V. Kotesovec, 24.2.2010)

explicit formula by Vaclav Kotesovec

Rekurentní vztah:
an = -3an-1-5an-2-5an-3+2an-4+17an-5+37an-6+49an-7+35an-8-16an-9-101an-10-185an-11-215an-12-139an-13+56an-14+321an-15+544an-16+588an-17+368an-18-99an-19-656an-20-1069an-21-1111an-22-689an-23+84an-24+929an-25+1488an-26+1506an-27+939an-28-939an-30-1506an-31-1488an-32-929an-33-84an-34+689an-35+1111an-36+1069an-37+656an-38+99an-39-368an-40-588an-41-544an-42-321an-43-56an-44+139an-45+215an-46+185an-47+101an-48+16an-49-35an-50-49an-51-37an-52-17an-53-2an-54+5an-55+5an-56+3an-57+an-58, n>58

OEIS linky:
A172517 - 2Q toroidal NxN
A172518 - 3Q toroidal NxN
A172519 - 4Q toroidal NxN
A173775 - 5Q toroidal NxN


n2 queens3 queens4 queens5 queens
2000 
30000
432000
51001005010
62885762880
758821562450882
8115271681638413312
91944174966220885536
10320041600233600561440
114840822806388802276736
12720016128017550729471744
1310140280540390153427991470
1414112486080877217685725696
151890077490017051850209107890
1625088123289633507328525062144
17323681844976591756401116665944
184147227578881055579042437807104
195198439334561735702444691672964
206480056064002879040009234168960
2179380769986044788577416462896030
22968001057056070204200029919532544
2311638014081980104489455450215537658
2413939218754560156538598485687824384
25165000243650002247132500136944081500
26194688316476163244194304222030242304
27227448402582964519015596340788006540
28264992512046086326171264529663525888
29306124639799168590557654785790131238
3035280079934400117166680001178695280160
3140362098348740155672293901698736557198
32460800120995840207636316162472214872064
33522720146884320270708193803475005224724
34591872178301440354160668164927131387904
35666400213914400454167427006776457658740
36749088256628736584219848329392614619904
378378283046901167383363357012672854468658
389357123617393289357139060817218696084992
39104036442550887611673133219822840988228838
40115520050050560014599142400030491340899840
41127756058384492018002403902039839128802924
42141120068104512022249967745652352705728512
43155316078848756027151576894467478117820624
44170755291286272033202392256087430668092416
4518711001049687100401355457650111314431376010
4620482881207000256486095146064142404689281536
4722355081379308436582569828310179295582644310
4824376321576194048699422837760226741660434432
(Hodnoty pro k=4 byly ověřeny výpočtem až do n=120)

Poznámka: Z matematického pohledu je zajímavější prstencová šachovnice než válcová (z šachového pohledu je to asi obráceně). V případě dam, věží nebo střelců jsou výsledky pro prstencovou šachovnici shodné jako pro válcovou šachovnici. V případě bodových kamenů (např. jezdců) to ale neplatí.
For queens, rooks and bishops are results for toroidal and cylindrical chessboard same, but for leapers (for example knights) are results different.

Zde je link na samotný "n-queens problem" na prstencové šachovnici:
A007705 - NQ NxN - počty řešení na prstencové šachovnici (Nonattacking queens on a 2n+1 x 2n+1 toroidal board).


2.1) Kings on board n x n - Králové na šachovnici n x n

Velmi zajímavý (i když poněkud jiný) je problém rozmístění neohrožujících se králů.

2 Kings, board nxn: (n-1)(n-2)(n2+3n-2)/2, (E. Lucas, 1891)

3 Kings, board nxn: (n-1)(n-2)(n4+3n3-20n2-30n+132)/6, (E. Landau, before 1901)

4 Kings, board nxn: (n8-54n6+72n5+995n4-2472n3-5094n2+21480n-17112)/24, n>=3, (K.Fabel + K.Soltsien, 1966)

5 Kings, board nxn: (n-4)(n9+4n8-74n7-176n6+2411n5+1844n4-38194n3+18944n2+236520n-316320)/120, n>=4, (V.Kotesovec, 1992)

6 Kings, board nxn: (n12-135n10+180n9+7465n8-18840n7-202665n6+751860n5+2442334n4-13441200n3-3643800n2+89860320n-108217440)/720, n>=5, (V. Kotesovec, 27.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n2k/k! - 9n2k-2/2/(k-2)! + 6n2k-3/(k-2)! ...

Tyto vzorce jsou i v OEIS
A061995 - 2K NxN
A061996 - 3K NxN
A061997 - 4K NxN
A061998 - 5K NxN
A172158 - 6K NxN

Viz Edouard Lucas: Théorie des nombres (1891), vzorec pro počet rozmístění 2 neohrožujících se králů najdeme na str.98 (ve vzorci vypadlo "/2"), viz též Edouard Lucas: Récréations mathématiques (1894) str.132 (i zde vypadlo "/2", v následujících dvou knihách Ahrense a Fabela je tento vzorec uveden správně).
Vzorec pro k=3 uvádí v knize Mathematische unterhaltungen und spiele (1901) Wilhelm Ahrens na str.155 s tím, že mu jej v dopise zaslal Edmund Landau.
Vzorec pro k=4 uvádí v knize Schach und Zahl (1966) na str.54 Karl Fabel.


n2 kings3 kings4 kings5 kings6 kings
2000  
3168100
4781407900
522896419871974978
65203920168344236862266
7102011860852753970141220298
8180629708317471232632012033330
92968652409620891008762877784658
104608129984251526235464464377818258
11684024024058821091067833201492665418
129790418220126050952853361285042436754
13135966933082517519169333114615062292834
1418408110344047443474155898681640736208186
15243881696604851524873286192514101489568538


2.2) Kings on board k x n - Králové na šachovnici k x n

2 kings, board 2xn: 2(n-1)(n-2)
3 kings, board 3xn: (n-2)(9n2-45n+70)/2, n>=2, (V. Kotesovec, 27.1.2010)
4 kings, board 4xn: (64n4-720n3+3347n2-7569n+6894)/6, n>=3, (V. Kotesovec, 27.1.2010)
5 kings, board 5xn: (625n5-9750n4+66415n3-247626n2+504664n-446544)/24, n>=4, (V. Kotesovec, 27.1.2010)
6 kings, board 6xn: 2(162n6-3240n5+29160n4-151830n3+483798n2-895085n+749335)/5, n>=5, (V. Kotesovec, 27.1.2010)
7 kings, board 7xn: (117649n7-2873997n6+32197753n5-215350695n4+932130286n3-2618213868n2+4424623272n-3468569760)/720, n>=6, (V. Kotesovec, 28.1.2010)
8 kings, board 8xn: (1048576n8-30277632n7+406210560n6-3319585920n5+18136811049n4-68048382318n3+171628664735n2-266425935930n+194935658400)/2520, n>=7, (V. Kotesovec, 30.1.2010)

První členy těchto vzorců mají obecně tvar (kn)k/k! - 3(k-1)(3k-2)(kn)k-1/2/k! + ...

OEIS linky:
A172202 - 3 kings 3 X n
A172203 - 4 kings 4 X n
A172204 - 5 kings 5 X n
A172205 - 6 kings 6 X n
A172206 - 7 kings 7 X n
A172261 - 8 kings 8 X n


n2 kings3 kings4 kings5 kings6 kings7 kings8 kings
20000000
348915162425
41234791944089261847
5241054541974854437282162531
64024815669856622663942022501726
760490410334475291908248438221243084
884858900995466102125410999618119138166
9112137917484224589291623238168864502726650
1014420803098446885471793141108998781724809105
11180298851221893646157905722816386025059647669
1222041308016315858503179539064376643213132889249
132645533120034265697659638832135235892130905051345
1431272241733144246284105546666265112945867124176002
15364923024273965239091779530444906381466136380034610
164201157833130196939862879748388648792662261909043488
17480142954422481399777544993263214623854922479315827404
18544174085790841971678668191837023851793294841394145399
1961220944745569271759041006409660376977877021424246670499
2068424930945719367465141450930734579533208842334919892115
21760293931183806488496262048760064869294761073720787187147
228403436014643586395900028396846341275630082025780929883024
239243985817921598260427138708008681835360114628779782913128
241012459142172249105374074519736221425941000794613063328442266
251104525552609924132919169688367338436077527973219078137617070


2.3) Kings on boards of various size - Králové na šachovnicích jiných rozměrů

Maximální možný počet neohrožujících se králů na šachovnici n x n je n2/4 (pro n sudé) a (n2+1)/4 (pro n liché), více viz Kings Problem

Řadu výsledků najdeme v knize Schach und Zahl, 1966, jejíž autoři jsou E.Bonsdorff, K.Fabel, O.Riihimaa. Speciální je případ, kdy králů je na šachovnici právě tolik, že každý musí být ve svém pevném čtverci velikosti 2x2. Celkový počet králů je v těchto případech roven vždy čtvrtině počtu polí příslušné šachovnice.

Number of ways to place n nonattacking kings on a 2 x 2n chessboard.
V citované knize na str.53 najdeme (pro tento jednoduchý případ) vzorec:
f1(n) = (n+1)*2n


A061593 - Number of ways to place 2n nonattacking kings on a 4 x 2n chessboard.
Na str.53 knihy Schach und Zahl (1966) nalezneme i excelentní vzorec pro rozmístění 2m neohrožujících se králů na šachovnici 2m x 4, jehož autorem je C.Bandelow. Stejný vzorec najdeme v článku Nonattacking kings on a chessboard, D. E. Knuth, 1994.
f2(n) = (17n-109)*3n+2*Fibonacci(2n+10)
Kdo by čekal v obecném vzorci Fibonacciho čísla? Explicitní tvar tohoto vzorce je
f2(n) = (17n-109)*3n + 2/sqrt(5)*(((3+sqrt(5))/2)n+5 - ((3-sqrt(5))/2)n+5)
Ještě je možno poznamenat, že tato (poněkud divoká) funkce je řešením diferenční rovnice
an = 9an-1-28an-2+33an-3-9an-4


A061594 - Number of ways to place 3n nonattacking kings on a 6 x 2n chessboard
Herbert S. Wilf se dostal ještě trochu dál, když v článku The Problem of the Kings, Electronic Journal of Combinatorics (1995), uvedl pro šachovnici 6x2n a 3n neohrožujících se králů odhad:
f3(n) = 231*n*4n - 2377*4n - 384*3n + O(1.707n)
Článek Non-attacking placements on chessboards (.ps), jehož autorem je Sergey Kitaev, má shodné výsledky a kromě králů řeší i rozmístění neohrožujících se pěšců na polích stejné barvy (number of nonattacking pawns, all of the same colour). V případě pěšců Sergey Kitaev a Toufik Mansour ještě došli k dalším výsledkům, které popisují v článku The Problem of the Pawns, Annals of Combinatorics (2004) (z článku je bohužel volně dostupný jen abstract). Jakási verze je k dispozici zde The problem of the pawns (2003)

Podařilo se mi najít přesný vzorec (exact formula by Vaclav Kotesovec, 5.2.2010):
exact formula by Vaclav Kotesovec

f3(n) = (231n-2377)*4n - 384*3n + (1953*sqrt(2)/2+1381+(35*sqrt(2)+99/2)*n)*(2+sqrt(2))n + (1381-1953*sqrt(2)/2+(99/2-35*sqrt(2))*n)*(2-sqrt(2))n
kde sqrt(2) = odmocnina ze 2. Je tedy vidět, že Wilfův odhad zbytku byl poněkud nepřesný, správně mělo být + O(n*3.4142n)

Příslušná diferenční rovnice je
an=19an-1 - 148an-2 + 604an-3 - 1364an-4 + 1644an-5 - 928an-6 + 192an-7


A173782 - Number of ways to place 4n nonattacking kings on a 8 x 2n chessboard
Herbert S. Wilf ve svém článku z roku 1995 dále uvádí, že pro 4n králů na šachovnici 8 x 2n má první člen podobné rovnice tvar
f4(n) ~ (7963567/2610)*n*5n + ...

Pro případ 4n králů na šachovnici 8 x 2n jsem odvodil vytvořující funkci (Generating function) (V. Kotesovec, 24.2.2010):
x*(22500x16-382125x15+2723005x14-10917322x13+27938661x12-48873227x11+60780149x10-54895129x9+36368733x8-17776175x7+6499001x6-1854479x5+446565x4-94300x3+15732x2-1673x+80) / ((1-x)(x2-4x+1)(x3-6x2+5x-1)(4x-1)(5x-1)2(3x2-5x+1)2(5x2-5x+1)2)

a rekurentní vzorec (Recurrence:)
an = 44an-1-887an-2+10855an-3-90083an-4+536398an-5-2365292an-6+7860674an-7-19852652an-8+38152568an-9-55523880an-10+60518766an-11-48502595an-12+27783210an-13-10888525an-14+2721025an-15-382125an-16+22500an-17, n>17


Vytvořující funkce není přímo explicitním vzorcem pro danou posloupnost, ale příslušná posloupnost z ní jde vytvořit tak, že vygenerujeme Taylorův rozvoj pro danou vytvořující funkci a jednotlivé členy této posloupnosti jsou koeficienty tohoto rozvoje. Přesněji: člen an posloupnosti je n-tá derivace vytvořující funkce v nule dělena n faktoriál. Obvykle není tento postup pro výpočet členů posloupnosti ten nejefektivnější, ale v případech, kdy je obtížné určit explicitní vzorec, je vyjímečně takový postup rychlejší. Ohledně vytvořujících funkcí je třeba ještě poznamenat, že z jejího jmenovatele lze snadno odvodit rekurentní vzorec, který vznikne roznásobením všech členů jmenovatele a nahrazením všech členů xk výrazy an-k.
Jmenovatel (denominator) pak dále určuje tvar parciálních členů řešení příslušné diferenční rovnice. Zde ho naopak potřebujeme ve faktorizovaném tvaru a pokud je kořen takto vzniklé rovnice t, je jedním z parciálních řešení funkce 1/tn. Pokud tedy např. v případě této posloupnosti obsahuje jmenovatel vytvořující funkce člen (5x-1), odpovídá tomu kořen 1/5 a parciální člen řešení diferenční rovnice 5n.
Každé takovéto parciální řešení je třeba násobit polynomem (s neznámými koeficienty) jehož stupeň je roven násobnosti příslušného kořene - 1. V našem případě měl člen (5x-1)2 stupeň 2, tvar příslušného parciálního řešení proto bude (f0+f1*n)* 5n, kde konstanty f0 a f1 budou určeny podle počátečních hodnot posloupnosti.
V případě, že má denominator (tzv. charakteristická rovnice) komplexní kořeny, je situace složitější. Pokud má rovnice kořen a+b*i (jak je známo, musí mít současně i komplexně sdružený a-bi), pak mají parciální řešení diferenční rovnice tvar
(a2+b2)n/2 *COS(n*ATAN(b/a))
a
(a2+b2)n/2 *SIN(n*ATAN(b/a))
Častým výrazem ve jmenovateli bývá např. člen x2+1, ze kterého dostáváme kořeny +i a -i, kterým odpovídají parciální řešení COS(pi*n) a SIN(pi*n). Tento případ je typický, pokud se odlišují vzorce na šachovnicích sudých a lichých rozměrů. Pro celá čísla je však člen SIN(pi*n) vždy roven 0 a člen COS(pi*n) lze nahradit příjemnějším výrazem (-1)n. O násobnostech kořenů platí totéž jako v případě kořenů reálných.


Tvar explicitního vzorce vyplývá ze jmenovatele vytvořující funkce, koeficienty jsem určil nejprve numericky:
f4(n) = ("f0"+"f1"*n)*5n + "p3"*4n + "p4"
+ "p1"*(2-SQRT(3))n+"p2"*(2+SQRT(3))n
+ ("c0"+"c1"*n)*((5-SQRT(5))/2)n+("d0"+"d1"*n)*((5+SQRT(5))/2)n
+ ("a0"+"a1"*n)*((5-SQRT(13))/2)n+("b0"+"b1"*n)*((5+SQRT(13))/2)n
+ "x1"*(SQRT(3)/(2*(SQRT(3)-SQRT(7)*COS(ATAN(SQRT(3)/9)/3+pi/3))))n
+ "x2"*(SQRT(3)/(2*(SQRT(3)-SQRT(7)*SIN(ACOT(-SQRT(3)/9)/3))))n
+ "x3"*(SQRT(3)/(2*(SQRT(7)*COS(ATAN(SQRT(3)/9)/3)+SQRT(3))))n

x1=-0.26377035674015103140762...
x2=1775.680242270463563416958...
x3=0.000114426854513301676567...
a0=0.016247286549426572256187...
a1=0.004738824796414161533626...
b0=50967.32103081995944916738...
b1=2377.824321004263414898295...
c0=0.205693095526376627060778...
c1=0.011423393098813887747739...
d0=13320.19430690447362337293...
d1=-25.2114233930988138877477...
p1=-0.00264173363558122860165...
p2=-26046.7751360441421965491...
f0=-41306.0010866693090236490...
f1=3051.175095785440613026819...
p3=1290.666666666666666666666...
p4=-0.04166666666666666666666...

Pro konstanty x1,x2,x3 platí x1+x2+x3 = 252338184/142129
Některé z těchto koeficientů lze snadno vyjádřit i algebraicky, problémy však dělají 3 reálné kořeny kubické rovnice, které jde vyjádřit jen pomocí trigonometrických funkcí a takové výrazy se pak obtížně upravují a zjednodušují.

Tady je explicitní vzorec v algebraickém tvaru (V. Kotesovec, 25.2.2010): explicit formula by Vaclav Kotesovec

Konstanty a, b, c (převrácené hodnoty kořenů kubické rovnice x3-6x2+5x-1) mají tyto numerické hodnoty:
[a = 1.554958132087371191419255..., b = 3.246979603717467061021860..., c = 0.198062264195161747527865...]

Zde musím upozornit na různou implementaci funkce ArcCot v programu Mathematica7 pro záporné argumenty. Podle tohoto programu vyjde např. ArcCot(-1)=-pi/4, zatímco Derive6 dává svou funkcí ACOT(-1)=3*pi/4, což je správná hodnota (=right value), viz např. "Schaum's outlines - Trigonometry", str.139, Chapter 13 "Inverses of Trigonometric Functions". Pro kladné argumenty jsou výsledky totožné. Výše uvedený vzorec pracuje s interpretací ACOT.


A173783 - Number of ways to place 5n nonattacking kings on a 10 x 2n chessboard

Pro získání této funkce jsem
1) napsal poměrně jednoduchý program, který vygeneroval transformační matici (program je obecný pro libovolné m a vygenerování trvá jen pár vteřin)
2) bylo nutno provést inverzi této matice (pro m=5 velikosti 192 x 192).

Zajímavé je zde srovnání současných matematických programů, které zvládají výpočty na úrovni symbolických výrazů. Inverzi matice 192x192 zvládne "Derive 6" za 69 minut, "Matlab 7" za 7 minut a "Mathematica 7" za 10 minut, musí se ale nastavit Method -> "OneStepRowReduction" (což není předdefinovaná hodnota). Při použití stejné metody a funkce "LinearSolve" (místo inverze matice) se dostane "Mathematica 7" dokonce těsně pod 1 minutu, tato metoda však selhává pro větší matice (např. 448x448), protože je nesmírně paměťově náročná, nestačí ani 4 GB RAM. Proto se jako nejvhodnější pro symbolické výpočty s velkými poli zdá program "Matlab 7" (inverze matice je v jeho případě nezbytná, protože analogická funkce "linsolve" lze použít jen pro numerické výpočty). Pro výpočet determinantu matice na symbolické úrovni je naopak nejrychlejší "Mathematica 7" (např. determinant 448x448 zvládne za pouhých 12 vteřin).

Vytvořující funkce (Generating function) (V. Kotesovec, 24.2.2010):

2x*(292626432x30-7695378432x29+94084706304x28-712519981056x27+3757888797696x26-14715718076160x25+44556058968960x24-107273952716256x23+209645023363168x22-337824014576768x21+454329405135504x20-514643686425920x19+494203416082160x18-403847150294172x17+281135354205764x16-166453721883480x15+83456844800670x14-35182845104124x13+12345883162136x12-3557728594620x11+827346101101x10-152042822189x9+21726065190x8-2499103126x7+289877178x6-45817212x5+7810422x4-1012942x3+86355x2-4311x+96) / ((1-2x)(x2-4x+1)(4x-1)(6x-1)2(2x2-4x+1)(2x2-5x+1)(4x2-6x+1)2(6x2-6x+1)2(7x2-6x+1)2(2x3-8x2+6x-1)(3x3-9x2+6x-1)2)

Rekurentní vzorec:
an = 85an-1-3441an-2+88303an-3-1613002an-4+22327010an-5-243429637an-6+2145452227an-7-15565947848an-8+94202823084an-9-480152808502an-10+2075863416838an-11-7651361422835an-12+24128330540449an-13-65240466585284an-14+151411770874148an-15-301613628545814an-16+515173613407544an-17-753006145475828an-18+939001403456656an-19-994821988961592an-20+890558910282768an-21-668920434927504an-22+417832289937792an-23-214574645977920an-24+89258591798784an-25-29486236792320an-26+7526493775872an-27-1426182018048an-28+188221833216an-29-15390756864an-30+585252864an-31, n>31


Tvar explicitního vzorce vyplývá ze jmenovatele vytvořující funkce, koeficienty jsem vypočítal nejprve numericky. Nejzajímavější je koeficient "a1" u členu s nejvyšší váhou, který určuje chování funkce pro n jdoucí do nekonečna.
f5(n) = ("a0"+"a1"*n)*6n + "b0"*4n
+"c0"*2n+"d0"*(2+SQRT(3))n+"d1"*(2-SQRT(3))n
+"e0"*(2+SQRT(2))n+"e1"*(2-SQRT(2))n
+"f0"*((5+SQRT(17))/2)n+"f1"*((5-SQRT(17))/2)n
+("g0"+"g1"*n)*(3+SQRT(5))n+("g2"+"g3"*n)*(3-SQRT(5))n
+("h0"+"h1"*n)*(3+SQRT(3))n+("h2"+"h3"*n)*(3-SQRT(3))n
+("i0"+"i1"*n)*(3+SQRT(2))n+("i2"+"i3"*n)*(3-SQRT(2))n
+"j1"*(1/(4/3-2*SQRT(7)*COS(ATAN(3*SQRT(111)/67)/3+pi/3)/3))n
+"j2"*(1/(4/3-2*SQRT(7)*SIN(ACOT(-3*SQRT(111)/67)/3)/3))n
+"j3"*(1/(2*SQRT(7)*COS(ATAN(3*SQRT(111)/67)/3)/3+4/3))n
+("k1"+"k2"*n)*(SQRT(3)/(2*COS(pi/18)+SQRT(3)))n
+("k3"+"k4"*n)*(SQRT(3)/(SQRT(3)-2*SIN(2*pi/9)))n
+("k5"+"k6"*n)*(SQRT(3)/(SQRT(3)-2*SIN(pi/9)))n

"a0"=-678713.914029838744250543...
"a1"=40881.99638391654123778175...
"b0"=-34068
"c0"=-1.16666666666666666666666...
"d0"=-51446.4849177672922717349...
"d1"=-0.00015892757463292217669...
"e0"=-10107.4970977440220279807...
"e1"=-0.00144453003045015334953...
"f0"=-684492.238277441947051457...
"f1"=-0.01172255805294854295976...
"g0"=926641.4858544337556115334...
"g1"=38562.08938946586577992332...
"g2"=0.050993455065133123680865...
"g3"=0.004591899029712395988044...
"h0"=-62326.0581297792402651458...
"h1"=723.9986187818953543472362...
"h2"=0.058129779240265145814576...
"h3"=0.001381218104645652763714...
"i0"=451705.3288256058621516918...
"i1"=-464.669820354223846560962...
"i2"=-105.212207530060402420677...
"i3"=-1.61589393149043915332353...
"j1"=0.681071493211076255730644...
"j2"=-5142.77599692595609626251...
"j3"=0.015530347678857435892035...
"k1"=-0.01214865752499437628069...
"k2"=0.001607392808026484702220...
"k3"=147951.3666730136147131534...
"k4"=1491.573767571326753514216...
"k5"=105.3857202386842498663759...
"k6"=-2.43062880321861841180229...

Pro konstanty platí j1+j2+j3 = -2720160/529, k1+k3+k5 = 4989255563912/33698267, k2+k4+k6 = 1398248840/938961

První část vzorce jde vyjádřit i v algebraickém tvaru (V. Kotesovec, 28.2.2010):
explicit formula (first part) by Vaclav Kotesovec
(first part of formula in closed form)


A174154 - Number of ways to place 6n nonattacking kings on a 12 x 2n chessboard
Tento případ vyžadoval provést (na symbolické úrovni) inverzi matice velikosti 448 x 448, což je na hranici možností současných matematických programů (Derive6 ani Mathematica7 si s tím neporadí, na tyto velké matice je ale vhodný program Matlab7, který inverzi zvládl v čase 68 minut).
Vytvořující funkce (Generating function) (V. Kotesovec, 8.3.2010):

-x*(9881265328704000000x^74-745460194573987200000x^73 +27058441331237911560000x^72-630574519733958189096000x^71 +10620992412418133969628300x^70-137991665381256761637404520x^69 +1441187713449842720703280065x^68-12449684907187405839719194626x^67 +90833482252388172827285029638x^66-568749753878989316529701677248x^65 +3094959104534048177533681352799x^64-14786591491557537432688402148814x^63 +62546683770100863224056803287942x^62-235893075161001219428756666935555x^61 +797978924681191303527565813197295x^60-2433648791133257840409309484158509x^59 +6721172925589000338821415074614101x^58-16874983210908760792785651385114152x^57 +38649671515505567165916997301106375x^56-80999469039951794157868014640691605x^55 +155756628296635763280353356415757902x^54-275499172743267856241417580914101161x^53 +449253470876074605154885582765085506x^52-676816476591070935766817355948817667x^51 +943857986354193371364615928444017845x^50-1220661704439047432548206117121008699x^49 +1466533837456537613456821872852081734x^48-1639525223616587182652341410467569787x^47 +1708305101435402614973823579541075741x^46-1661495320924220763537985553529107570x^45 +1510621894675464930498400295672730343x^44-1285696520181304471064162857556756892x^43 +1025670064685839353596509770775335305x^42-767836201105618743331897589888819260x^41 +539952432414375273203309417443882230x^40-356956219188072917117313500791428647x^39 +221967416303673380170960689222016760x^38-129868144295605689997008303392471184x^37 +71491160008257450681327802590567504x^36-37017322185220125774414395796648083x^35 +18017697561193232235536013176700652x^34-8236705210457078339411642367777062x^33 +3532451891465875904778828049906178x^32-1419311438083676683034744726952652x^31 +533432327695298858210381553149285x^30-187205875643334525147970829585222x^29 +61228416399158699804621484828993x^28-18622737469829899757436340257385x^27 +5254673072129348277153109543997x^26-1371752804262578223890375168964x^25 +330267098353842775956388942842x^24-73061510988747055309122504069x^23 +14782596349429679171765334301x^22-2719571348796162565504741678x^21 +451339375837487448675798746x^20-66805240600688222182861662x^19 +8661523087250332029653805x^18-952009254666126966673796x^17 +82335998894700394651901x^16-4266725433179907174031x^15-184755253316270694616x^14 +83877913428258704659x^13-13092670253017397215x^12 +1433917521601031600x^11-120787644461247815x^10 +7805125834561750x^9-355282797168619x^8 +7110673719021x^7 +486018670449x^6-61151293377x^5 +3632842475x^4-141485072x^3 +3689608x^2-59281x+448) /(x-1)/(2x-1)/(4x-1)/(7x-1)^2/(x^2-3x+1)/(2x^2-5x+1)/(3x^2-5x+1)/(3x^2-6x+1)/(5x^2-7x+1)^2/(8x^2-7x+1)^2/(9x^2-7x+1)^3/(11x^2-7x+1)^2/(x^3-9x^2+6x-1)/(3x^3-11x^2+7x-1)^2/(3x^3-12x^2+7x-1)^2/(4x^3-11x^2+7x-1)/(5x^3-12x^2+7x-1)^2/(5x^3-13x^2+7x-1)^2/(7x^3-14x^2+7x-1)^2/(x^4-7x^3+13x^2-7x+1)/(x^4-8x^3+14x^2-7x+1)

Rekurentní vzorec:
an = 200an-1 -19591an-2 +1252845an-3 -58827505an-4 +2162753808an-5 -64829889078an-6 +1629240689182an-7 -35031124501133an-8 +654454967945240an-9 -10752566037209576an-10 +156879699829988516an-11 -2048776097631017397an-12 +24108171056426689513an-13 -257034531080309116618an-14 +2494772567482865677279an-15 -22133280277582878693605an-16 +180118887001001382183984an-17 -1348636789867805112026274an-18 +9315545713899467284553179an-19 -59499168382845285726017972an-20 +352120178477097682063693543an-21 -1934323013107671509059832463an-22 +9878966314646961189006272617an-23 -46972249732573258020377866081an-24 +208183877121467820793024020729an-25 -860974589150724576064816096663an-26 +3325616222441474827288188284748an-27 -12007102646405027060206035093213an-28 +40549313398041902425202637254740an-29 -128160961960827405525713512244418an-30 +379279006512370536257299017344107an-31 -1051368905565268405109177617606550an-32 +2730662700682795572522784530198834an-33 -6646355208785503282827723317955069an-34 +15161829507999599355831555503563964an-35 -32418089419841604310504626066285593an-36 +64963905091650869917279263108816530an-37 -121998193028385383238635351043687855an-38 +214657313735486368434302654748877496an-39 -353777524153903526644871915284150291an-40 +545952447651523245976395515654219577an-41 -788557229845726031285071277862716138an-42 +1065477899782050092815249173889044974an-43 -1345958367592910697332763314344919726an-44 +1588548886423131006699445390007535964an-45 -1750322460004952351721691789849070497an-46 +1798910520031476972425563369104737493an-47 -1722886523923952992401312780338774274an-48 +1536009690078173688532095945663171041an-49 -1273224933191855545781650218877302946an-50 +979983174726292730062221357725344727an-51 -699362171154778642087707164485332698an-52 +462015283859449079185102433429700638an-53 -282037700090254407809166846000612848an-54 +158780300135911015654982957271875917an-55 -82256781284683621993873503316293537an-56 +39117488543991922262702977386610326an-57 -17029736085111484438301715527001011an-58 +6766292666982799092814924628874630an-59 -2445102358065760086073498440897006an-60 +800463457818116640733412431607635an-61 -236339003295391504639451351871623an-62 +62608507068414191797382321464409an-63 -14791881602747947642116948625728an-64 +3094801634963547035936901282789an-65 -568588000125534978580839232812an-66 +90798410660368398860732240817an-67 -12444769805881872152497521690an-68 +1440691704088085224964754909an-69 -137955444475738809516914520an-70 +10619160418237292545913100an-71 -630516845227291857576000an-72 +27057588402917527560000an-73 -745460194573987200000an-74 +9881265328704000000an-75, n>75

Explicitní vzorec (numericky) (V. Kotesovec, 9.3.2010):
f6(n) = ("c1"*n+"c2")*7n
+"c3"*4n
+"c4"*2n
+"c5"
+("c6"*n^2+"c7"*n+"c8")*(SQRT(13)/2+7/2)n
+("c9"*n^2+"c10"*n+"c11")*(7/2-SQRT(13)/2)n
+("c12"*n+"c13")*(SQRT(29)/2+7/2)n
+("c14"*n+"c15")*(7/2-SQRT(29)/2)n
+("c16"*n+"c17")*(SQRT(17)/2+7/2)n
+("c18"*n+"c19")*(7/2-SQRT(17)/2)n
+("c20"*n+"c21")*(SQRT(5)/2+7/2)n
+("c22"*n+"c23")*(7/2-SQRT(5)/2)n
+"c24"*(SQRT(5)/2+3/2)n
+"c25"*(3/2-SQRT(5)/2)n
+"c26"*(SQRT(17)/2+5/2)n
+"c27"*(5/2-SQRT(17)/2)n
+"c28"*(SQRT(13)/2+5/2)n
+"c29"*(5/2-SQRT(13)/2)n
+"c30"*(SQRT(6)+3)n
+"c31"*(3-SQRT(6))n
+("c32"*n+"c33")*(9/(11-2*SQRT(58)*COS(ATAN(9*SQRT(303)/413)/3+pi/3)))n
+("c34"*n+"c35")*(9/(11-2*SQRT(58)*SIN(ACOT(-9*SQRT(303)/413)/3)))n
+("c36"*n+"c37")*(9/(2*SQRT(58)*COS(ATAN(9*SQRT(303)/413)/3)+11))n
+("c38"*n+"c39")*(3/(2*(2-3*COS(2*ACOT(-SQRT(107)/107)/3))))n
+("c40"*n+"c41")*(3/(2*(2-3*SIN(2*ATAN(SQRT(107)/107)/3+pi/6))))n
+("c42"*n+"c43")*(3/(2*(3*COS(2*ATAN(SQRT(107)/107)/3)+2)))n
+("c44"*n+"c45")*(5*SQRT(3)/(2*(2*SQRT(3)-SQRT(13)*COS(ATAN(5*SQRT(3)/9)/3+pi/3))))n
+("c46"*n+"c47")*(5*SQRT(3)/(2*(2*SQRT(3)-SQRT(13)*SIN(ACOT(-5*SQRT(3)/9)/3))))n
+("c48"*n+"c49")*(5*SQRT(3)/(2*(SQRT(13)*COS(ATAN(5*SQRT(3)/9)/3)+2*SQRT(3))))n
+("c50"*n+"c51")*(15/(13-16*COS(2*ACOT(-5*SQRT(111)/333)/3)))n
+("c52"*n+"c53")*(15/(13-16*SIN(2*ATAN(5*SQRT(111)/333)/3+pi/6)))n
+("c54"*n+"c55")*(15/(16*COS(2*ATAN(5*SQRT(111)/333)/3)+13))n
+("c56"*n+"c57")*(3/(2*(1-COS(2*ACOT(-SQRT(3)/9)/3))))n
+("c58"*n+"c59")*(3/(2*(1-SIN(2*ATAN(SQRT(3)/9)/3+pi/6))))n
+("c60"*n+"c61")*(3/(2*(COS(2*ATAN(SQRT(3)/9)/3)+1)))n
+"c62"*(1/(3-2*SQRT(7)*COS(ATAN(SQRT(3)/37)/3+pi/3)))n
+"c63"*(1/(3-2*SQRT(7)*SIN(ACOT(-SQRT(3)/37)/3)))n
+"c64"*(1/(2*SQRT(7)*COS(ATAN(SQRT(3)/37)/3)+3))n
+"c65"*(12/(11-2*SQRT(37)*COS(ATAN(6*SQRT(687)/161)/3+pi/3)))n
+"c66"*(12/(11-2*SQRT(37)*SIN(ACOT(-6*SQRT(687)/161)/3)))n
+"c67"*(12/(2*SQRT(37)*COS(ATAN(6*SQRT(687)/161)/3)+11))n
+"c68"*(SQRT(38-14*SQRT(5))/4-SQRT(5)/4+7/4)n
+"c69"*(-SQRT(38-14*SQRT(5))/4-SQRT(5)/4+7/4)n
+"c70"*(SQRT(14*SQRT(5)+38)/4+SQRT(5)/4+7/4)n
+"c71"*(-SQRT(14*SQRT(5)+38)/4+SQRT(5)/4+7/4)n
+"c72"*(SQRT(6*SQRT(5)+30)/4+SQRT(5)/4+7/4)n
+"c73"*(-SQRT(6*SQRT(5)+30)/4+SQRT(5)/4+7/4)n
+"c74"*(SQRT(30-6*SQRT(5))/4-SQRT(5)/4+7/4)n
+"c75"*(-SQRT(30-6*SQRT(5))/4-SQRT(5)/4+7/4)n

Z konstant c1 až c75 je nejzajímavější konstanta c1 u členu s nejvyšší váhou, viz též tabulka dále
"c1"=5.6305092363081393300...*10^5
"c2"=-1.104167141369220611...*10^7
"c3"=-2.357744324111866969...*10^6
"c4"=21.0432
"c5"=0.4722222222222222222...
"c6"=3190.3093489289550735...
"c7"=3.3724816112053204772...*10^5
"c8"=2.2171312563933296610...*10^7
"c9"=-0.155502775108919675...
"c10"=163.7653409000415659...
"c11"=2.052693391056922234...*10^4
"c12"=5.758468547897144015...*10^5
"c13"=1.624760528438350563...*10^7
"c14"=0.001165834594259474...
"c15"=-0.41441832002393772...
"c16"=2.300478493334472119...*10^5
"c17"=-1.44639696705190542...*10^7
"c18"=0.338908296854086023...
"c19"=8.005890335704876443...
"c20"=-4380.77992117273774...
"c21"=1.552146086172787699...*10^7
"c22"=74.67426089779847392...
"c23"=-4.21203713796980065...*10^4
"c24"=-1466.89599084080095...
"c25"=3.191774075165802562...*10^(-5)
"c26"=-1.36341829271227595...*10^6
"c27"=0.053980304804581505...
"c28"=7.075976996099561648...*10^4
"c29"=-0.02122530224411394...
"c30"=-1.46797239653638789...*10^7
"c31"=0.098837563176994140...
"c32"=0.011468815268292507...
"c33"=-34.8712694667255141...
"c34"=-2931.17833825432167...
"c35"=2.359570457373671675...*10^6
"c36"=-0.01023220098644473...
"c37"=-0.00976071273489356...
"c38"=79.63702226259701650...
"c39"=7623.522283711869170...
"c40"=-2.50405135693327250...*10^4
"c41"=-4.37105580792831970...*10^6
"c42"=-0.00017645871779939...
"c43"=-0.01873137641764468...
"c44"=182.8430686773159592...
"c45"=-2.05091907645515941...*10^4
"c46"=4.369015291089355051...*10^4
"c47"=-8.98717155512840790...*10^6
"c48"=0.030434481624558909...
"c49"=0.091021909918317851...
"c50"=81.04059263702932797...
"c51"=1.249689694089438109...*10^4
"c52"=6218.228392475138846...
"c53"=4.152739581799171110...*10^5
"c54"=-0.00911244704526967...
"c55"=0.070667837190544279...
"c56"=-277.104247927338245...
"c57"=2.816445813687916256...*10^4
"c58"=-2410.10041406045040...
"c59"=1.906847363789349701...*10^5
"c60"=-6.04826431426482591...*10^(-5)
"c61"=-0.03986068056420358...
"c62"=-1145.44167952134069...
"c63"=5.746421629805880771...*10^4
"c64"=-1.27578541046112266...*10^(-5)
"c65"=2.716923048103320883...
"c66"=-1.24844204776308025...*10^6
"c67"=-0.02476586191937392...
"c68"=-9.69121675380289883...
"c69"=0.002234055238103441...
"c70"=3.227848424788018850...*10^4
"c71"=-0.01279090254065370...
"c72"=1.446790521731934022...*10^6
"c73"=-0.17181958108958812...
"c74"=-3559.96835962473958...
"c75"=0.000767722202736206...


A174155 - Number of ways to place 7n nonattacking kings on a 14 x 2n chessboard
Tento případ vyžadoval pro získání vytvořující funkce provést (na symbolické úrovni!) inverzi matice velikosti 1024 x 1024, což ze současných matematických programů na PC zvládl pouze Matlab7 v čase přes 8 hodin.
Vytvořující funkce (Generating function) (V. Kotesovec, 9.3.2010):

-2x(54222672911274911289059573760000000x^123-6279364401720347209864467972096000000x^122 +355916700860805743977756391154647040000x^121-13165656678159747994229085738759094272000x^120 +357580968786334728976290764494328561664000x^119-7606685500377828944402424153754395444510720x^118 +132025070498240400453821981247031745011777536x^117-1923148717983096485894432339969762419764363264x^116 +24001598451495916558037784079325597030940672000x^115-260733912714136996693533608123205367579054964736x^114 +2496313284158021796255065102282597952375849222144x^113-21277865832851787547991827395328601974018991456256x^112 +162819416994113682338598213096466301319887512928256x^111-1126358581030907656491986254406033294612551232913408x^110 +7086514400960731390328723893313619097901288581496832x^109-40757758341169693402147178689047453376348442921533440x^108 +215257037478349801305513176871426454908220485492801536x^107-1048058512243529559822666262068066405115673243213627392x^106 +4720742792928429097850271439387849238995832815146369024x^105-19732519791798674006897568748598939801049082241955069952x^104 +76756113443806605398650302720172795659712890994488901632x^103-278543117088434677065138311184638719760885595939909009408x^102 +945165490091678324412551307244000361076544393234133614592x^101-3005076664126071245872244757805376845758973901952126877696x^100 +8969167160819063116493944158832282378058214481923144220672x^99-25173494362748757456491747023570336965099474666885947408384x^98 +66544578438810679866701792371902931683947858391489794482176x^97-165915150472108230394017571109190057361624463233617396158464x^96 +390695976354665890074513984612903966800905181381260806209536x^95-869962058942296909688656575338098822622973290164727090757632x^94 +1833820369440762614157730722855821504244851903462283741575168x^93-3663162558208576997437411808620528134488856302642268009722880x^92 +6940816834168452591527174228257133363210122586267517300846592x^91-12485300731198250918868702608084089861324343287261785436221440x^90 +21338793564228109772500185812748834074577991696545058663716864x^89-34677121465423066397628237863087661065799673463314127032121856x^88 +53618151940174275326509797819558207050312413538008687145720320x^87-78930471903810521140079827741654338728936679603061202109775616x^86 +110684484068511808086435721720485932701236358427760746915584128x^85-147931694677541828719396650661604635971538787804520097489430720x^84 +188525824622441412447766259940603893941456175662333549010704640x^83-229191721343564863372095426973769973171257827414431011627276224x^82 +265895245461053857121393536010031648750961599245321451639861696x^81-294478601111715286464524887097776472383327199903667055093108064x^80 +311429881070928442091929664868298832042011215780888541843889024x^79-314591478165462374119104556767298517772413598384303253181601680x^78 +303610313847801927302628453791220291803390622403746890286002928x^77-280000546810486798955803689372202305079421577088215075049437392x^76 +246804103133939308093322655758451920966947006188480655154502768x^75-207953075119753681934511769916178379442671053267567217312801856x^74 +167516671923783503099492383592992508412397913200612862784395728x^73-129028318635429191186157503073887054868563348499260954458336584x^72 +95038266464215381821909442668919890469926733009931919704337376x^71-66950284625201671155069063428880073031737512053977063096825228x^70 +45113692375805864259297990894062359371832009035289711397936572x^69-29083271562407026217147121592147394606754705984695471985211124x^68 +17941543124532772358042257555368380493701702794985559340294296x^67-10594988086421513826949788846676673068705561304545158471667176x^66 +5991920401275728684972283544592363416138938055314116591319068x^65-3247426373656460046505919451533942542620882729601342871800392x^64 +1688165453584027719109749622892479797351061811465406015315584x^63-842820130777935012431294163831220960459990279182114470001058x^62 +404786291367071435200584329565320034572896308441820233742492x^61-187427652608776303903657214006392302066849785191588678445115x^60 +83896074599720207110842887078480982574996945714857399371613x^59-36421099514154882084087090198951010669125624752881141912710x^58 +15389237595338812516875007712544226815442894222052921181201x^57-6351568145491846549236967852474091662341017080740623603308x^56 +2568470735966551607363059267449023563857322215129129292009x^55-1019698617782603122804098776612193889543052048554602751427x^54 +397651156321907497202559006733450549773666880896232550657x^53-152155733575897092189571737592541028133454734267411181214x^52 +56981485495617844103050419523305702033850394150958337929x^51-20812575067663039288298005399000342062645182032314841804x^50 +7385399296884771556614272143326975515992615453424039706x^49-2536378970991959824151513109283300166684452996715135613x^48 +840120945435246927097038897868232751926844215337475933x^47-267592212832787322394881575729138879628424476161213860x^46 +81762553246257166816899290032251339568459510030642883x^45-23918585500218748129692083027726169290403007263721516x^44 +6688609148248353532236759219142184861585117521757998x^43-1785680002635931884417620662660932079655295846414621x^42 +454652885121393630298466575461039200141902454472294x^41-110298017418873798104313766968125280060424724687194x^40 +25474543483790572391832217810646566581743665805776x^39-5596951496464420802889764068394845225964455321014x^38 +1168846911565928114777696452748844131217296980641x^37-231826928991979522819676069949495409863663665362x^36 +43629602459789761964817967344186988839256111996x^35-7783590869696391606863804898013090431960663692x^34 +1314850860746222381862072936753225528249707603x^33-210047845174210030771347734473617776144382113x^32 +31685847252072174706283091894572485340220424x^31-4505742353308488104812488551253836156494412x^30 +602733132978025015539972306763269356694723x^29-75657550530238560567564832465918129450573x^28 +8883682779620708497014362847653861413872x^27-971875320372166677407922243420697610663x^26 +98534825191761089609265874805355318687x^25-9189253210485381832768469226798168077x^24 +779442384966136549958627866012748423x^23-59012906619949767531288773139867455x^22 +3845953582977736963079436642919696x^21-197099229113974036917550559274814x^20 +5292802547783405050936604984656x^19 +373035447202117049725952469283x^18-77596506283090099467584030538x^17 +8167182777939867059910623158x^16-661371544219142909103681829x^15 +44836253686866816392727278x^14-2615582192513759386391326x^13 +132326561350181298705400x^12-5789711318908782442591x^11 +216507299180594552002x^10-6754590417985251086x^9 +167279960378322251x^8-2883766637590816x^7 +15171573646232x^6 +1034726376990x^5-43935972146x^4 +988301639x^3-14215547x^2 +124457x-512) /(x-1)/(2x-1)^4/(3x-1)/(4x-1)^2/(5x-1)^2/(6x-1)^2/(8x-1)^2/(x^2-3x+1)/(2x^2-5x+1)/(2x^2-6x+1)^2/(3x^2-5x+1)/(3x^2-6x+1)/(4x^2-6x+1)/(5x^2-5x+1)/(4x^2-7x+1)/(6x^2-6x+1)/(6x^2-8x+1)^2/(x^3-5x^2+6x-1)^2/(10x^2-8x+1)^2/(11x^2-8x+1)^2/(14x^2-8x+1)^2/(2x^3-12x^2+7x-1)/(3x^3-12x^2+7x-1)/(4x^3-15x^2+8x-1)^2/(6x^3-14x^2+8x-1)/(7x^3-15x^2+8x-1)^2/(6x^3-16x^2+8x-1)/(7x^3-17x^2+8x-1)/(8x^3-17x^2+8x-1)^2/(9x^3-17x^2+8x-1)/(10x^3-18x^2+8x-1)^2/(13x^3-19x^2+8x-1)^2/(2x^4-12x^3+18x^2-8x+1)/(2x^4-13x^3+19x^2-8x+1)/(2x^4-16x^3+20x^2-8x+1)/(3x^4-17x^3+20x^2-8x+1)^2

Rekurentní vzorec:
an = 355*an-1 -62230*an-2 +7181407*an-3 -613713773*an-4 +41424053008*an-5 -2300132364916*an-6 +108057442428713*an-7 -4383953038266400*an-8 +156019190373932213*an-9 -4931027930452931529*an-10 +139784688779506280122*an-11 -3583425170015054558692*an-12 +83642898320877743078649*an-13 -1788040425415361381095757*an-14 +35181295448283382870926529*an-15 -639901931020563711201074856*an-16 +10800089806681857038851260471*an-17 -169708489277667670527670553256*an-18 +2490164949669281400008934703650*an-19 -34209628251326791851770501894019*an-20 +441055288914550947143816216610085*an-21 -5347966902979544937526517923821060*an-22 +61104504039422023705912415093725325*an-23 -659032554611721554539403323301392328*an-24 +6720192949816044716232213169179554002*an-25 -64882805116093293907803507888980509652*an-26 +593920909802707572074736203520468111015*an-27 -5160703522797399132569345666788973860423*an-28 +42614522062811899586385927814456985353588*an-29 -334751895136451803946683064352275034359880*an-30 +2503907651659320142301076243661317011090301*an-31 -17849439080689433456741551238042933830148067*an-32 +121365103409983215634920731453706282402989836*an-33 -787682779457226999619540178398463725925966321*an-34 +4883125137114593719681433214140387829336583657*an-35 -28934196085932348822191609052145794097781155747*an-36 +163964259705601110511077019136782444452849185661*an-37 -889096467412574593575239829002444819262058789807*an-38 +4615620894756910152737471910113313680781105674422*an-39 -22950686917289066656110074511663942441885518753279*an-40 +109353457449972177331586073421680895966478823429493*an-41 -499473845738617512362949924094821709360026608128519*an-42 +2187734208783093331582990536307413775611383675314889*an-43 -9192273270269162035986926653043968654354343390001452*an-44 +37062129853043426095583096259451935804785975760076180*an-45 -143429198013863760183212109243115977359657995206014227*an-46 +532910058542910360324809278690568941113219846288868695*an-47 -1901420003705947087451752388740956303649285577893915347*an-48 +6516259041007093187423911613159101666641521933740754935*an-49 -21453256766715010406989098549201236384005949789118270289*an-50 +67862786677741974361372613468176344308979904185438584928*an-51 -206287780166253696570479597934268784316357437236102282981*an-52 +602656132334901791636594053942094239035756172510172525310*an-53 -1692241022898939503382665894593801620298884560230139707283*an-54 +4567571300316866260600043539420748909209366452509778579458*an-55 -11851263906173524614222522185343043279355263254029721988325*an-56 +29560920816547403978712649385739724088334537984011638988104*an-57 -70885121592790538286371080849899812856102357608828148982550*an-58 +163409845886211665485225388293159123346245205917080382491840*an-59 -362144494413274527626611628277027555974388120349867198704581*an-60 +771530456662294571647577757578775733382830746682477159631731*an-61 -1580051625970196573554375464352132643295757350774681162296206*an-62 +3110344753414776505140966019872337750496742905447614669866357*an-63 -5884768996639161507183480452281609414662222317037902572633129*an-64 +10700179904680098088349075595592950436046826427104304058777483*an-65 -18695761252218017203250136160781026224722427604030963411998550*an-66 +31385405428525582416952099102249644055680352511497855444441476*an-67 -50615010790428312789203366621293543617322532762055840704862044*an-68 +78401558190254541965541051943975685100181865096298253483692092*an-69 -116622609345361161550023273188650530719539499699634509198995280*an-70 +166557601271060887009843251325454304196590177972454959487144760*an-71 -228335053227695446593478422394263084067454263715584326278101612*an-72 +300401134446235301923820488428752926620010702980973240412254612*an-73 -379172847928243557624031458518329813721595270573144703516684576*an-74 +459046365839494135368978124958612394249433642265385081445950840*an-75 -532877482801746654124759269331287007133286813299814163092009072*an-76 +592936288102825622570743054492822496446897568699254213904468288*an-77 -632189153956996372446346209656511806473856827439391888927649744*an-78 +645628423168981359720232716143742154313424331606125466445192864*an-79 -631309538761675057717669169185910680560650899421336897795392864*an-80 +590802676516296103915411991460869361161536968482988725264860832*an-81 -528916884144943614094532055306563532933002357635647591545000256*an-82 +452761330701536545738119403023868339767065670518026635649577216*an-83 -370396653643622694057710469713707973757641810265926750337440128*an-84 +289431372618931391691737286015520606075875385437288774637611200*an-85 -215901264737140413666379352994934014775706019543589604786418560*an-86 +153649184549497317041659318233838481245117719730140911980842240*an-87 -104252974521213676768278500477636643016220002666862316826451968*an-88 +67395262889890487766296108102457389362138367464841581743008512*an-89 -41479473052975102408788350419058391326160347231275485649925632*an-90 +24286188570788191214124029153817764477465967752785084937249792*an-91 -13515885727784925849780266435732478478996532916115183858167808*an-92 +7143333320685061147938100094247033962091553666292792325552128*an-93 -3581905682072239982948980939843555015656793558885050106626048*an-94 +1702317826959975854072534402257549818094193265958637078077440*an-95 -765957974206249466198973766920615027158143875426684125339648*an-96 +325909060539351950294732186971109628679383105292872432025600*an-97 -130968165237993448475954170153250150473368153400646612811776*an-98 +49638708587887646409930310401068700758344054841911497785344*an-99 -17718229431449535703068175428258919870114054679778329591808*an-100 +5946636096612490129643987484131994525326081419538641305600*an-101 -1873351971906088407360195136745415764386870573863249346560*an-102 +552894140752297793897292472024667959143300503946233315328*an-103 -152559503760719436568492942301761635184890139055040757760*an-104 +39266537394375534967337770724827049041421713702333644800*an-105 -9403752773974119645286336014440818139548381446587940864*an-106 +2089612061057417202959800881701216993734109316216258560*an-107 -429504625481757418108462149946734473479836376897683456*an-108 +81375891864330772617336465883953945682230569494118400*an-109 -14156048922012863746909064485322036645034360708268032*an-110 +2250938891663231625620683440919224267817994365698048*an-111 -325484106592219042324298551387653940779270480592896*an-112 +42545385782902596634984070466084992703612208545792*an-113 -4992222373149232005879478421404380031384037621760*an-114 +521480049046471863976707137480219684646980419584*an-115 -48007121237350102099540488235719546567483457536*an-116 +3846701159492393552477177944898029698982871040*an-117 -264077394388027999670576258659387821659258880*an-118 +15214673796528838502205187025491559920435200*an-119 -715205037525577948424201523247561310208000*an-120 +26332207845103672186115068739494871040000*an-121 -711842230613175571260114828735283200000*an-122 +12558728803440694419728935944192000000*an-123 -108445345822549822578119147520000000*an-124, n>124


Explicitní vzorec (numericky) (V. Kotesovec, 10.3.2010):
f7(n) = ("c1"*n+"c2")*8n
+("c3"*n+"c4")*6n
+("c5"*n+"c6")*5n
+("c7"*n+"c8")*4n
+"c9"*3n
+("c10"*n^3+"c11"*n^2+"c12"*n+"c13")*2n
+"c14"
+("c15"*n+"c16")*(SQRT(7)+3)n
+("c17"*n+"c18")*(3-SQRT(7))n
+("c19"*n+"c20")*(SQRT(10)+4)n
+("c21"*n+"c22")*(4-SQRT(10))n
+("c23"*n+"c24")*(SQRT(6)+4)n
+("c25"*n+"c26")*(4-SQRT(6))n
+("c27"*n+"c28")*(SQRT(5)+4)n
+("c29"*n+"c30")*(4-SQRT(5))n
+("c31"*n+"c32")*(SQRT(2)+4)n
+("c33"*n+"c34")*(4-SQRT(2))n
+"c35"*(SQRT(5)/2+3/2)n
+"c36"*(3/2-SQRT(5)/2)n
+"c37"*(SQRT(17)/2+5/2)n
+"c38"*(5/2-SQRT(17)/2)n
+"c39"*(SQRT(13)/2+5/2)n
+"c40"*(5/2-SQRT(13)/2)n
+"c41"*(SQRT(6)+3)n
+"c42"*(3-SQRT(6))n
+"c43"*(SQRT(5)+3)n
+"c44"*(3-SQRT(5))n
+"c45"*(SQRT(5)/2+5/2)n
+"c46"*(5/2-SQRT(5)/2)n
+"c47"*(SQRT(33)/2+7/2)n
+"c48"*(7/2-SQRT(33)/2)n
+"c49"*(SQRT(3)+3)n
+"c50"*(3-SQRT(3))n
+("c51"*n+"c52")*(3/(5-2*SQRT(7)*COS(ACOT(-SQRT(3)/9)/3)))n
+("c53"*n+"c54")*(3/(2*SQRT(7)*SIN(ATAN(SQRT(3)/9)/3+pi/3)+5))n
+("c55"*n+"c56")*(3/(5-2*SQRT(7)*SIN(ATAN(SQRT(3)/9)/3)))n
+("c57"*n+"c58")*(4*SQRT(3)/(5*SQRT(3)-2*SQRT(43)*COS(ATAN(4*SQRT(687)/477)/3+pi/3)))n
+("c59"*n+"c60")*(4*SQRT(3)/(5*SQRT(3)-2*SQRT(43)*SIN(ACOT(-4*SQRT(687)/477)/3)))n
+("c61"*n+"c62")*(4*SQRT(3)/(2*SQRT(43)*COS(ATAN(4*SQRT(687)/477)/3)+5*SQRT(3)))n
+("c63"*n+"c64")*(7*SQRT(3)/(5*SQRT(3)-2*SQRT(19)*COS(ACOT(-3*SQRT(3)/7)/3)))n
+("c65"*n+"c66")*(7*SQRT(3)/(2*SQRT(19)*SIN(ATAN(3*SQRT(3)/7)/3+pi/3)+5*SQRT(3)))n
+("c67"*n+"c68")*(7*SQRT(3)/(5*SQRT(3)-2*SQRT(19)*SIN(ATAN(3*SQRT(3)/7)/3)))n
+("c69"*n+"c70")*(24/(17-2*SQRT(97)*COS(ATAN(24*SQRT(237)/881)/3+pi/3)))n
+("c71"*n+"c72")*(24/(17-2*SQRT(97)*SIN(ACOT(-24*SQRT(237)/881)/3)))n
+("c73"*n+"c74")*(24/(2*SQRT(97)*COS(ATAN(24*SQRT(237)/881)/3)+17))n
+("c75"*n+"c76")*(5*SQRT(3)/(3*SQRT(3)-2*SQRT(7)*COS(ATAN(5*SQRT(111)/117)/3+pi/3)))n
+("c77"*n+"c78")*(5*SQRT(3)/(3*SQRT(3)-2*SQRT(7)*SIN(ACOT(-5*SQRT(111)/117)/3)))n
+("c79"*n+"c80")*(5*SQRT(3)/(2*SQRT(7)*COS(ATAN(5*SQRT(111)/117)/3)+3*SQRT(3)))n
+("c81"*n+"c82")*(39/(19-14*COS(4*ATAN(SQRT(3)/9)/3+pi/3)))n
+("c83"*n+"c84")*(39/(19-14*SIN(4*ATAN(SQRT(3)/9)/3+pi/6)))n
+("c85"*n+"c86")*(39/(14*COS(4*ATAN(SQRT(3)/9)/3)+19))n
+"c87"*(SQRT(6)/(2*(SQRT(6)-SQRT(17)*COS(ATAN(SQRT(237)/171)/3+pi/3))))n
+"c88"*(SQRT(6)/(2*(SQRT(6)-SQRT(17)*SIN(ACOT(-SQRT(237)/171)/3))))n
+"c89"*(SQRT(6)/(2*(SQRT(17)*COS(ATAN(SQRT(237)/171)/3)+SQRT(6))))n
+"c90"*(3/(2*(2-3*COS(2*ACOT(-SQRT(107)/107)/3))))n
+"c91"*(3/(2*(2-3*SIN(2*ATAN(SQRT(107)/107)/3+pi/6))))n
+"c92"*(3/(2*(3*COS(2*ATAN(SQRT(107)/107)/3)+2)))n
+"c93"*(9/(7-2*SQRT(13)*COS(ACOT(-103*SQRT(303)/2727)/3)))n
+"c94"*(9/(2*SQRT(13)*SIN(ATAN(103*SQRT(303)/2727)/3+pi/3)+7))n
+"c95"*(9/(7-2*SQRT(13)*SIN(ATAN(103*SQRT(303)/2727)/3)))n
+"c96"*(9/(4*(2-SQRT(7)*COS(ATAN(27*SQRT(47)/563)/3+pi/3))))n
+"c97"*(9/(4*(2-SQRT(7)*SIN(ACOT(-27*SQRT(47)/563)/3))))n
+"c98"*(9/(4*(SQRT(7)*COS(ATAN(27*SQRT(47)/563)/3)+2)))n
+"c99"*(21/(17-22*COS(2*ACOT(-9*SQRT(107)/749)/3)))n
+"c100"*(21/(17-22*SIN(2*ATAN(9*SQRT(107)/749)/3+pi/6)))n
+"c101"*(21/(22*COS(2*ATAN(9*SQRT(107)/749)/3)+17))n
+"c102"*(27/(17-2*SQRT(73)*COS(ATAN(27*SQRT(771)/997)/3+pi/3)))n
+"c103"*(27/(17-2*SQRT(73)*SIN(ACOT(-27*SQRT(771)/997)/3)))n
+"c104"*(27/(2*SQRT(73)*COS(ATAN(27*SQRT(771)/997)/3)+17))n
+("c105"*n+"c106")*(-12/(SQRT(129-16*SQRT(7)*COS(ACOT(-187*SQRT(5871)/17613)/3))+SQRT(16*SQRT(7)*SIN(ATAN(187*SQRT(5871)/17613)/3+pi/3)+129)-SQRT(129-16*SQRT(7)*SIN(ATAN(187*SQRT(5871)/17613)/3))-17))n
+("c107"*n+"c108")*(-12/(SQRT(129-16*SQRT(7)*COS(ACOT(-187*SQRT(5871)/17613)/3))-SQRT(16*SQRT(7)*SIN(ATAN(187*SQRT(5871)/17613)/3+pi/3)+129)+SQRT(129-16*SQRT(7)*SIN(ATAN(187*SQRT(5871)/17613)/3))-17))n
+("c109"*n+"c110")*(12/(SQRT(129-16*SQRT(7)*COS(ACOT(-187*SQRT(5871)/17613)/3))-SQRT(16*SQRT(7)*SIN(ATAN(187*SQRT(5871)/17613)/3+pi/3)+129)-SQRT(129-16*SQRT(7)*SIN(ATAN(187*SQRT(5871)/17613)/3))+17))n
+("c111"*n+"c112")*(12/(SQRT(129-16*SQRT(7)*COS(ACOT(-187*SQRT(5871)/17613)/3))+SQRT(16*SQRT(7)*SIN(ATAN(187*SQRT(5871)/17613)/3+pi/3)+129)+SQRT(129-16*SQRT(7)*SIN(ATAN(187*SQRT(5871)/17613)/3))+17))n
+"c113"*(SQRT(4*SQRT(2)+10)/2+SQRT(2)/2+2)n
+"c114"*(-SQRT(4*SQRT(2)+10)/2+SQRT(2)/2+2)n
+"c115"*(SQRT(10-4*SQRT(2))/2-SQRT(2)/2+2)n
+"c116"*(-SQRT(10-4*SQRT(2))/2-SQRT(2)/2+2)n
+"c117"*(-8*SQRT(3)/(SQRT(203-16*SQRT(73)*COS(ATAN(3*SQRT(8331)/1217)/3+pi/3))+SQRT(203-16*SQRT(73)*SIN(ACOT(-3*SQRT(8331)/1217)/3))-SQRT(16*SQRT(73)*COS(ATAN(3*SQRT(8331)/1217)/3)+203)-13*SQRT(3)))n
+"c118"*(-8*SQRT(3)/(SQRT(203-16*SQRT(73)*COS(ATAN(3*SQRT(8331)/1217)/3+pi/3))-SQRT(203-16*SQRT(73)*SIN(ACOT(-3*SQRT(8331)/1217)/3))+SQRT(16*SQRT(73)*COS(ATAN(3*SQRT(8331)/1217)/3)+203)-13*SQRT(3)))n
+"c119"*(8*SQRT(3)/(SQRT(203-16*SQRT(73)*COS(ATAN(3*SQRT(8331)/1217)/3+pi/3))-SQRT(203-16*SQRT(73)*SIN(ACOT(-3*SQRT(8331)/1217)/3))-SQRT(16*SQRT(73)*COS(ATAN(3*SQRT(8331)/1217)/3)+203)+13*SQRT(3)))n
+"c120"*(8*SQRT(3)/(SQRT(203-16*SQRT(73)*COS(ATAN(3*SQRT(8331)/1217)/3+pi/3))+SQRT(203-16*SQRT(73)*SIN(ACOT(-3*SQRT(8331)/1217)/3))+SQRT(16*SQRT(73)*COS(ATAN(3*SQRT(8331)/1217)/3)+203)+13*SQRT(3)))n
+"c121"*(SQRT(2-SQRT(2))+2)n
+"c122"*(2-SQRT(2-SQRT(2)))n
+"c123"*(SQRT(SQRT(2)+2)+2)n
+"c124"*(2-SQRT(SQRT(2)+2))n

Zde musím znovu upozornit na různou implementaci funkce ArcCot v programu Mathematica7 (a shodně Matlab7) pro záporné argumenty. Podle tohoto programu vyjde např. ArcCot(-1)=-pi/4, zatímco Derive6 dává svou funkcí ACOT(-1)=3*pi/4. Pro kladné argumenty jsou výsledky totožné. Výše uvedený vzorec pracuje s interpretací ACOT.

"c1" = 8.008508288587027981899891832842...*10^6
"c2" = -1.81089995748716180171175024872...*10^8
"c3" = 4086940.5
"c4" = 2.713279915661047027506654835847...*10^8
"c5" = 811926.2319051077221011861534737...
"c6" = -1.31369302331806894332700374141...*10^8
"c7" = 18170.88
"c8" = -4.17999101238672438672438672438...*10^6
"c9" = -6228.83108571428571428571428571...
"c10" = 0.043738977072310405643738977072...
"c11" = 1.421557067271352985638699924414...
"c12" = -30.9432558998908205257411606617...
"c13" = -220.043520976456426191875927325...
"c14" = -5.86718496922578555231616456106...
"c15" = -418788.523607094712529342554505...
"c16" = 5.013707630801773104192477688378...*10^8
"c17" = -0.02492925229172231612073699179...
"c18" = 1.075364029453712760657536485049...
"c19" = 8.540270388258272352607112248837...*10^6
"c20" = 2.814350377821712904853391678413...*10^8
"c21" = 1.041333163798738377996052789276...
"c22" = -345.614397009437947019921430265...
"c23" = 1.324647893190896933017015071967...*10^7
"c24" = -9.73346177369950808833328888260...*10^8
"c25" = 1.628231381547022831736466874142...
"c26" = 66.98500631230045022769121311433...
"c27" = 2.461688914751622082783683674985...*10^7
"c28" = 8.426569154599938669036500370553...*10^8
"c29" = -3433.96380047215658028992763237...
"c30" = -879817.398340831956494809134168...
"c31" = -1.08277959139968522739644207730...*10^7
"c32" = -1.11370658910819897649267299049...*10^9
"c33" = -172912.835854753195647189481178...
"c34" = 1.724253902964595606877325046590...*10^7
"c35" = 72107.92221362639378910892248909...
"c36" = 0.419902292407003414221448250425...
"c37" = -8.11395447235995889385202278688...*10^6
"c38" = 0.018419861981117514634920814561...
"c39" = -1.01541967361319499179816518714...*10^7
"c40" = 0.668765201148772650662715793661...
"c41" = 2.308626082413440881556439274072...*10^9
"c42" = 1.744554864061056687088635412236...
"c43" = 8.206033292160349219251536757333...*10^6
"c44" = 0.109944913938643200084771315292...
"c45" = -385037.804303049272027195013717...
"c46" = 0.616428707628469127869660571766...
"c47" = -2.97399811196902055787451969786...*10^8
"c48" = -3.76849765053512829175687214279...
"c49" = -7.47216380568250569395536302955...*10^7
"c50" = 0.511428304931231374039374725970...
"c51" = 150738.8203858169019828385146415...
"c52" = -5.18824642004650146213559150392...*10^7
"c53" = -0.04451870042271629938786815225...
"c54" = -0.97177685106174796757718162692...
"c55" = 8.099024789246810243321779432971...
"c56" = 693.2457214795661483544460653979...
"c57" = -4849.79021955111715653639024285...
"c58" = -1.47268544573164061772075206359...*10^6
"c59" = -1.96873464171550841512243324289...*10^6
"c60" = -4.76180445236817173759036301713...*10^8
"c61" = 0.000044184748555657770987329876...
"c62" = -0.20916425493071292134244414069...
"c63" = 816616.4078745858843854181312695...
"c64" = -9.80660449239965542007095900209...*10^8
"c65" = 0.540719173758396061324902848868...
"c66" = -0.59125375316823196724737514491...
"c67" = -3592.42020892921114172992973799...
"c68" = 879957.3686633784806555529260785...
"c69" = -4952.53864665607197453048394527...
"c70" = 674174.7111370475527269617358608...
"c71" = 171415.1705115741663145562364573...
"c72" = 1.159879075216887004259128792089...*10^8
"c73" = 6.228894575576546050196855027376...
"c74" = -698.160829928694354683331412339...
"c75" = -27852.4037526076503861051686847...
"c76" = 1.750866020046519344704183669533...*10^6
"c77" = -107316.548751238334290285095491...
"c78" = 1.700036068814900126759084523105...*10^7
"c79" = 2.140556705635654663312406910040...
"c80" = 354.1446359049725509269272638600...
"c81" = -87502.0975293379311029534402413...
"c82" = -1.99097669599308099559897241304...*10^7
"c83" = 132811.7138629216765267725267322...
"c84" = 8.578295334185319271128247289640...*10^6
"c85" = 1.392883434473521545674052378508...
"c86" = 53.58861446176947274622220632354...
"c87" = 16099.37906282671383085207399636...
"c88" = 2.152950747383693795804808879121...*10^6
"c89" = -0.00863842484944510025519818691...
"c90" = 7775.413981671499525081277300107...
"c91" = 1.451226993119440000835137043482...*10^6
"c92" = -0.26714117358513685377893621605...
"c93" = -1.75372066726327368313061403810...*10^8
"c94" = 1.901644993615794344161544022622...
"c95" = -48.1080973139087033202367677395...
"c96" = 585105.8413288281531550457051346...
"c97" = 5.806336199362658824686762759793...*10^7
"c98" = -0.67302107263106564653088387790...
"c99" = 65729.17344085680201901804876663...
"c100" = -3.51421283567362680415284551317...*10^8
"c101" = -0.22095977210544169098051582936...
"c102" = 63806.84331577325805659666923283...
"c103" = 1.060674960621817083637236991780...*10^8
"c104" = -7.75572499836378041062265279038...
"c105" = -10990.5020942609060998549371647...
"c106" = 796664.5780846115765133747463153...
"c107" = 3.425535244229768667392356486178...
"c108" = -55.0827638151146581597279068191...
"c109" = 116339.6059632768281029847362073...
"c110" = 1.174182642106513753397109896870...*10^7
"c111" = 0.000115067472477431864327897940...
"c112" = 0.017174626194380625642751954060...
"c113" = 2.971646179887972534926221265784...*10^8
"c114" = 11.01012889052251677479594737182...
"c115" = 143189.9095428102115806939589428...
"c116" = 0.230170922802426304709897115210...
"c117" = -2.56586075319021143803520294878...
"c118" = -395912.481421705580918482229332...
"c119" = 14633.18010963546792895745481650...
"c120" = 0.002989002374954112674911320720...
"c121" = -43179.2433928682842768066552894...
"c122" = 0.107980606874322436416084820539...
"c123" = -1.45231903646507818317408952466...*10^6
"c124" = 0.000026638467036372604464378334...



Number of ways to place 8n nonattacking kings on a 16 x 2n chessboard
Na matici velikosti 2304 x 2304 nestačí (při 4GB RAM) ani Matlab7. Vypočetl jsem proto alespoň determinant této transformační matice. Ten určuje tvar jmenovatele vytvořující funkce, tzv. denominator, ze kterého pak vyplývá tvar explicitního řešení. Program Mathematica7 zvládl výpočet determinantu této obrovské matice ve skvělém čase 5 hodin 35 minut. Výsledkem je polynom 882 stupně, který má 208 různých kořenů.

Denominator: (-1+x)30(-1+2x)8(-1+3x)32(-1+4x)2(-1+5x)4(-1+6x)2(-1+9x)2(1-5x+x2)2(1-3x+x2)16(1-5x+2x2)4(1-6x+3x2)6(1-6x+4x2)4(1-8x+5x2)2(1-6x+6x2)8(1-9x+7x2)4(1-7x+7x2)4(1-6x+7x2)2(1-7x+8x2)2(1-9x+12x2)4(1-9x+13x2)4(1-9x+15x2)4(1-9x+16x2)2(1-9x+17x2)4(1-9x+19x2)4(-1+6x-8x2+x3)2(-1+6x-7x2+x3)8(-1+5x-6x2+x3)2(-1+6x-8x2+2x3)4(-1+6x-9x2+3x3)4(-1+8x-16x2+4x3)2(-1+8x-15x2+4x3)4(-1+9x-18x2+5x3)4(-1+9x-17x2+5x3)4(-1+8x-16x2+6x3)4(-1+8x-17x2+7x3)4(-1+9x-21x2+8x3)4(-1+9x-20x2+8x3)4(-1+9x-19x2+8x3)4(-1+9x-17x2+8x3)4(-1+9x-22x2+9x3)2(-1+9x-19x2+9x3)4(-1+9x-18x2+9x3)4(-1+9x-22x2+11x3)4(-1+9x-21x2+11x3)4(-1+9x-21x2+12x3)8(-1+9x-22x2+13x3)4(-1+9x-23x2+14x3)4(-1+9x-22x2+15x3)4(-1+9x-23x2+16x3)4(-1+9x-24x2+17x3)4(-1+9x-24x2+19x3)4(1-8x+18x2-9x3+x4)2(1-9x+24x2-20x3+3x4)4(1-9x+24x2-18x3+3x4)4(1-9x+23x2-17x3+3x4)4(1-9x+22x2-16x3+3x4)4(1-9x+21x2-15x3+3x4)4(1-9x+25x2-22x3+4x4)4(1-9x+24x2-21x3+4x4)4(1-9x+24x2-19x3+4x4)4(1-9x+22x2-17x3+4x4)2(1-9x+26x2-26x3+5x4)4(1-9x+25x2-24x3+5x4)4(1-9x+25x2-23x3+5x4)4(1-9x+24x2-22x3+5x4)4(1-9x+24x2-20x3+5x4)4(1-9x+26x2-26x3+7x4)4(1-9x+26x2-27x3+8x4)8(1-9x+26x2-28x3+9x4)2(1-9x+27x2-31x3+11x4)4(-1+9x-28x2+35x3-15x4+x5)2(-1+9x-27x2+31x3-12x4+x5)4
(V. Kotesovec, 2.3.2010)


Zajímavé by bylo odvodit, jak se funkce fm(n) chová pokud jde n do nekonečna. Z předchozích vzorců jde odhadnout tvar hlavního členu
fm(n) ~ km*n*(m+1)n, hodnota "k" ale není konstanta, ale funkce závislá na "m".

mkmkm/km-1
11.00000 
217.0000017.00000
3231.0000013.58823
43051.1750913.20855
540881.9963813.39877
6563050.9236313.77258
78008508.2885814.22341
8??

Máme zatím velmi málo výsledků pro nějaký serióznější odhad. Mám ale hypotézu, že podíl km/km-1 konverguje k nějaké konstantě.


Převrácené hodnoty kořenů určují tvar partikulárních řešení. Pokud tyto hodnoty srovnáme podle velikosti, dostaneme následující tabulku a graf (pro m=1 až m=7). Jak již teoreticky dokázal ve svém článku The Problem of the Kings H. Wilf, člen s nejvyšší váhou má vždy hodnotu m+1, což jsem nyní potvrdil výpočty až do m=8.

r1 = m + 1

Je však třeba poznamenat, že výpočet čísla druhého v pořadí, uvedený na konci citovaného článku, je chybný!
Formula for latter value in article by Wilf (1995) is wrong.
Right formula is (V. Kotesovec, 27.2.2010):


r2 = right formula by Vaclav Kotesovec (for m>1)

Dalším (poněkud překvapujícím) výsledkem je, že pro m jdoucí do nekonečna se první dvě největší čísla nevzdálí více jak o 1, přesněji

lim r1 - r2 = 1
m ® Ą
          (V. Kotesovec, 27.2.2010)


root numberm=1m=2m=3m=4m=5m=6m=7generally
12345678m+1
2 2.618033988
3/2+sqrt(5)/2
3.414213562
2+sqrt(2)
4.302775637
5/2+sqrt(13)/2
5.236067977
3+sqrt(5)
6.192582403
7/2+sqrt(29)/2
7.16227766
4+sqrt(10)
(m+1 + sqrt(m2-2m+5))/2
3 0.381966011344.7320508075.5615528126.449489742 
4  0.5857864373.7320508074.5615528125.4494897426.372281323
5   3.6180339884.4142135625.3027756376.236067977
6   3.2469796034.2143197434.9354323316
7   1.55495813244.8661982625.744826077
8   1.3819660113.8793852414.6510934085.645751311
9   13.7320508074.6180339885.507018644
10   0.6972243623.4142135624.5615528125.449489742
11   0.26794919224.4605048705.414213562
12   0.1980622641.6527036444.3902568845.323404276
13    1.5857864374.3027756375.236067977
14    1.4608111284.1700864865.086130197
15    1.26794919245.048917339
16    0.7639320223.9562952015
17    0.5857864373.8019377354.912229178
18    0.4679111133.5320888864.813606502
19    0.4384471872.6180339884.732050807
20    0.3248691282.4450418684.699628148
21    0.2679491922.3819660114.685543932
22     2.3472963554.561552812
23     2.3111078174.481194304
24     2.2391232784.460504870
25     2.2090569264.342923082
26     24.302775637
27     1.8378527914.246979603
28     1.7892441194.143864425
29     1.7261094454.061498850
30     1.6972243624
31     1.5374015773.847759065
32     1.4384471873.618033988
33     13
34     0.8074175962.858441954
35     0.7530203952.765366864
36     0.6972243622.760876721
37     0.6617387872.688892182
38     0.6227971462.618033988
39     0.5505102572.585786437
40     0.5441132192.554958132
41     0.5271660912.529316580
42     0.5188056952.470683419
43     0.4384471872.428006731
44     0.3819660112.396338530
45     0.3445576182.357926367
46     0.3003718512.334903985
47     0.2277771042.286462065
48     0.1729090842.239123278
49     0.1206147582
50      1.778123837
51      1.763932022
52      1.604068139
53      1.550510257
54      1.381966011
55      1.306177543
56      1.267949192
57      1.234633135
58      1.198062264
59      1
60      0.837722339
61      0.829913513
62      0.801308756
63      0.781690346
64      0.763932022
65      0.728669629
66      0.714857518
67      0.697224362
68      0.657076917
69      0.651105782
70      0.643104132
71      0.627718676
72      0.550510257
73      0.539495129
74      0.485863070
75      0.438447187
76      0.381966011
77      0.354248688
78      0.318669356
79      0.307978528
80      0.300371851
81      0.250882452
82      0.235985074
83      0.216003272
84      0.186393497
85      0.152240934



      Sorted values of roots for m=1 to 7


Table - number of ways to place m*n nonattacking kings on a 2m x 2n chessboard (for m=1 to 8, n=1 to 20)


nkingsboard1n/2x2nkingsboard2n/4x2nkingsboard3n/6x2nkingsboard4n/8x2nkingsboard5n/10x2nkingsboard6n/12x2nkingsboard7n/14x2nkingsboard8n/16x2n
112x2424x21236x23248x280510x2192612x2448714x21024816x22304
222x41244x47966x440888x418471010x476981212x4303191414x41146061616x4419933
332x63264x640896x63600128x6260401510x61663681812x69766402114x653927042416x628432288
442x88084x81847126x826040168x82815712010x825807542412x8211379592814x81596360303216x81134127305
552x10192104x107698156x10166368208x1025807542510x10325727563012x103573653503514x1035441921124016x1032580145116
662x12448124x1230319186x12976640248x12211379593010x123573653503612x1251091445434214x12647371651624816x12749160010737
772x141024144x14114606216x145392704288x141596360303510x1435441921124212x14647371651624914x1410275333531685616x1414677177838054
882x162304164x16419933246x1628432288328x1611341273054010x16325801451164812x167491600107375614x16146771778380546416x16254977173389319
992x185120184x181501674276x18144605184368x1876836642024510x182823591091405412x1880808135745506314x181931942653982407216x18 
10102x2011264204x205266069306x20714611200408x20501237137935010x2023350422066246012x20824251442194297014x2023831163635551828016x20 
11112x2224576224x2218174084336x223449705600448x223170762501365510x22185895462176966612x228034919532352647714x22278896026640553968816x22 
12122x2453248244x2461892669366x2416333065216488x2419554753532176010x241434226742137267212x2475454149416101458414x243125469004705799549616x24 
13132x26114688264x26208424880396x2676081271168528x26118060005075446510x2610778913524442207812x26686808002644139209114x26337809094529032489210416x26 
14142x28245760284x28695179339426x28349524164224568x28700046994071517010x2879231346158548168412x286088890938988826159814x283541223948051005591611216x28 
15152x30524288304x302299608732456x301586790140800608x304087479860456567510x30571463642096860169012x30527800657569629345610514x3036167031534733681042812016x30 
16162x321114112324x327552444115486x327130144209024648x3223550778556154358010x324054979528344086989612x324487356963644390196711214x32361185897294231505433612816x32 
17172x342359296344x3424648046806516x3431752978219904688x34134131150391180428510x34283682180140072905610212x3437515949458205008859011914x343537558667145785221294413616x34 
18182x364980736364x3679994460139546x36140298397039232728x36756231034249165279010x361960172461014788957410812x36309079970876248241628712614x3634064810821496925304077214416x36 
19192x3810485760384x38258339007890576x38615604372260736768x384225755311842960069510x3813397530877973934153611412x382513792754725676159069013314x38323174221020292467111436015216x38 
20202x4022020096404x40830619734681606x402684534626000512808x40234273205550090775310010x4090692611466447918571412012x4020213663270691098063956914014x403025897322737161330366416816016x40 

Tabulku hodnot pro šachovnice typu 8 x 2n (pro n=1 až 10) nalezneme už v knize Schach und Zahl (1966), str.53. Je až neuvěřitelné, co dokázal při tehdejší úrovni počítačů Christoph Bandelow vypočítat. Hodnoty ve sloupcích vpravo jsem v tomto případě vygeneroval pomocí vytvořujících funkcí.


A018807 - Number of ways to place n2 nonattacking kings on 2n x 2n chessboard
Jinou možností konfigurace králů je případ na obecné čtvercové šachovnici sudých rozměrů 2n x 2n, kam se vejde n2 neohrožujících se králů (tedy opět je zaplněna vždy právě čtvrtina šachovnice). V tomto případě je výsledků zatím málo, alespoň odhad průběhu této funkce v článku The Problem of Kings (.ps file) (broken link) - Michael Larsen (The electronic journal of combinatorics 2, 1995). Let f(n) the number of configurations of n2 mutually non-attacking kings on a 2n x 2n chessboard
log f(n) = 2n log n - 2n log 2 + O(n4/5log n)



3.1) Rooks on board n x n - Věže na šachovnici n x n

Na doplnění ještě uvádím vzorce pro počet postavení k neohrožujících se věží na šachovnici n x n. Jako jediný z těchto problémů byl tento zcela vyřešen, obecný vzorec je
k rooks, board nxn: (COMB(n,k))2*k!
kde COMB(n,k)=n!/k!/(n-k)! je kombinační číslo ("n nad k")
Objevit tento vzorec je poměrně snadné, cituje jej třeba už Wilhelm Ahrens Mathematische unterhaltungen und spiele (1901).

Speciálně pokud k=n, vychází počet možných pozic n neohrožujících se věží na šachovnici n x n roven n! (n faktoriál)
n rooks, board nxn: n!
2 rooks, board nxn: n2(n-1)2/2
3 rooks, board nxn: n2(n-1)2(n-2)2/6

Pro srovnání s ostatními vzorci, počet těchto kombinací je také polynom, po roznásobení dostaneme jeho koeficienty ve tvaru:
n!2/(n-k)!2/k! = n2k/k! +
n2k-1 *(-1)1 /k!/1! *k(k-1) +
n2k-2 *(-1)2 /k!/2! *k(k-1)(3k2-5k+1)/3 +
n2k-3 *(-1)3 /k!/3! *k2(k-1)3(k-2) +
n2k-4 *(-1)4 /k!/4! *k(k-1)(k-2)(15k5-75k4+125k3-81k2+7k+3)/15 +
n2k-5 *(-1)5 /k!/5! *k2(k-1)2(k-2)(k-3)(3k4-14k3+21k2-10k-3)/3 +
n2k-6 *(-1)6 /k!/6! *k(k-1)(k-2)(k-3)(63k8-630k7+2457k6-4753k5+4557k4-1453k3-612k2+131k+60)/63 +
n2k-7 *(-1)7 /k!/7! *k2(k-1)2(k-2)(k-3)(k-4)(9k7-90k6+348k5-646k4+530k3-20k2-191k-60)/9 +
n2k-8 *(-1)8 /k!/8! *k(k-1)(k-2)(k-3)(k-4)(135k11-2250k10+15615k9-58650k8+128275k7-158510k6+84541k5+23230k4-32495k3-13610k2+4269k+1890)/135 +
n2k-9 *(-1)9 /k!/9! *k2(k-1)2(k-2)(k-3)(k-4)(k-5)(15k10-255k9+1800k8-6806k7+14609k6-16481k5+4880k4+7966k3-3349k2-6159k-1890)/15 +
n2k-10*(-1)10/k!/10!*k(k-1)(k-2)(k-3)(k-4)(k-5)(99k14-2475k13+26730k12-163581k11+622974k10-1513325k9+2253768k8-1668051k7-200574k6+1086969k5+144402k4-705343k3-261879k2+108126k+45360)/99 +
n2k-11*(-1)11/k!/11!*k2(k-1)2(k-2)(k-3)(k-4)(k-5)(k-6)(9k13-231k12+2559k11-15999k10+61679k9-148707k8+208749k7-112209k6-106467k5+138243k4+110077k3-120297k2-153486k-45360)/9 + ...


Problém byl vyřešen i na obdélníkových šachovnicích, počet pozic k neohrožujících se věží na šachovnici m x n je:
(m! n!) / ((m-k)! (n-k)! k!)

Viz též Rook Polynomial nebo Rook Polynomials (broken link)

3.2) Rooks on board k x n - Věže na šachovnici k x n

Z předchozího vzorce pro obecnou obdélníkovou šachovici vyplývá (při m=k) tento vzorec pro
k rooks, board kxn: n!/(n-k)!

Pro srovnání s ostatními vzorci, počet těchto kombinací je také polynom, po roznásobení dostaneme jeho koeficienty ve tvaru:
n!/(n-k)! = nk -
nk-1*k(k-1)/2 +
nk-2*k(k-1)(k-2)(3k-1)/24 -
nk-3*k2(k-1)2(k-2)(k-3)/48 +
nk-4*k(k-1)(k-2)(k-3)(k-4)(15k3-30k2+5k+2)/5760 -
nk-5*k2(k-1)2(k-2)k-3)(k-4)(k-5)(3k2-7k-2)/11520 +
nk-6*k(k-1)(k-2)(k-3)(k-4)(k-5)(k-6)(63k5-315k4+315k3+91k2-42k-16)/2903040 - ...

Obecně má nejvyšší člen každého rozvoje tvar:
nk-i * k2i / 2i / i! + ...

Při použití kombinačních čísel (např. "k nad 12" je k!/(k-12)!/12!) lze zápis tohoto výrazu trochu zjednodušit:
n!/(n-k)! = nk +
nk-1 *(-1)1 *COMB(k,2) /21 *2 +
nk-2 *(-1)2 *COMB(k,3) /22 *(3k-1) +
nk-3 *(-1)3 *COMB(k,4) /23 *4k(k-1) +
nk-4 *(-1)4 *COMB(k,5) /24 *(15k3-30k2+5k+2)/3 +
nk-5 *(-1)5 *COMB(k,6) /25 *2k(k-1)(3k2-7k-2) +
nk-6 *(-1)6 *COMB(k,7) /26 *(63k5-315k4+315k3+91k2-42k-16)/9 +
nk-7 *(-1)7 *COMB(k,8) /27 *8k(k-1)(9k4-54k3+51k2+58k+16)/9) +
nk-8 *(-1)8 *COMB(k,9) /28 *(135k7-1260k6+3150k5-840k4-2345k3-540k2+404k+144)/15 +
nk-9 *(-1)9 *COMB(k,10)/29 *2k(k-1)(15k6-165k5+465k4+17k3-648k2-548k-144)/3 +
nk-10*(-1)10*COMB(k,11)/210*(99k9-1485k8+6930k7-8778k6-8085k5+8195k4+11792k3+2068k2-2288k-768)/9 +
nk-11*(-1)11*COMB(k,12)/211*4k(k-1)(9k8-156k7+834k6-1080k5-1927k4+1252k3+4156k2+3056k+768)/3 + ...

Koeficienty těchto polynomů se nazývají Stirlingova čísla prvního druhu, viz Stirling Numbers of the First Kind. Jsou sice známy rekurentní vzorce pro tyto koeficienty (viz např. Stirling's polynomials), ale explicitní vzorce byly doposud publikovány jen do úrovně 5, ostatní vzorce (výrazy od k-6 dále) jsou pravděpodobně mým objevem (V. Kotěšovec, 9.2.2010). Viz také OEIS - A112002.



4.1) Bishops on board n x n - Střelci na šachovnici n x n

Vzorce pro počet pozic neohrožujících se střelců na šachovnici n x n najdeme např. v knize Schach und Zahl, 1966 (str.58-62), jejímž autorem je Karl Fabel, který většinu následujících vzorců sám objevil.

2 bishops, board nxn: n(n-1)(3n2-n+2)/6

3 bishops, board nxn: n(n-2)(2n4-4n3+7n2-6n+4)/12, pro n sudé (even), (K. Fabel, 1966)
3 bishops, board nxn: (n-1)(2n5-6n4+9n3-11n2+5n-3)/12, pro n liché (odd), (K. Fabel, 1966)

4 bishops, board nxn: n(n-2)(15n6-90n5+260n4-524n3+727n2-646n+348)/360, pro n sudé (even), (K. Fabel, 1966)
4 bishops, board nxn: (n-1)(n-2)(15n6-75n5+185n4-339n3+388n2-258n+180)/360, pro n liché (odd), (K. Fabel, 1966 - tento vzorec sice není v knize "Schach und Zahl" uveden, ale předpokládám, že ho také objevil - nyní jsem ho vygeneroval a potvrdil počítačem)

5 bishops, board nxn: n(n-2)(3n8-34n7+177n6-590n5+1435n4-2592n3+3326n2-2844n+1344)/360, pro n sudé (even), (V. Kotesovec, 26.1.2010)
5 bishops, board nxn: (n-1)(n-2)(n-3)(3n7-22n6+80n5-204n4+379n3-464n2+378n-270)/360, pro n liché (odd), (V. Kotesovec, 26.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n2k/k! - 2n2k-1/3/(k-2)! + ...
Zatímco v případě dam a věží byl vždy počet kamenů maximálně n (k≤n), v případě střelců (i jezdců) může být takový počet větší než n. Horní omezení pro maximální počet střelců je 2n-2, více viz Bishops Problem.

Linky na OEIS
A172123 - 2 bishops NxN
A172124 - 3 bishops NxN
A172127 - 4 bishops NxN
A172129 - 5 bishops NxN

Nevím kdo je autorem vzorce pro k=2, ale (kromě Fabela) jej cituje již Henry Dudeney ve své knize "Amusements in Mathematics" (1917), str.96.


n2 bishops3 bishops4 bishops5 bishops
2400 
3262680
492232260112
5240112427283368
652038961642839680
79941089470792282248
81736261922428561444928
92832562967060485865552
104380110960180946420014112
116490204130419906459673360
1292843550008992684159698416
131289658919618024072391202680
141747294007234170724890095584
15231701450134617846321902427800
163016021725761072434723853570560
173862431729441796453767450556064
1848756453091229166744013829016768
1960762634218646061527224759442464
2074860872052070968622842930138864
219128011799860106947792872328779720
22110264157366001579767068118747638592
23132066207119662291594536190443610280


4.2) Bishops on board k x n - Střelci na šachovnici k x n

2 bishops, board 2xn: 2n2-3n+2
3 bishops, board 3xn: (9n3-45n2+106n-108)/2, n>=4, (V. Kotesovec, 26.1.2010)
4 bishops, board 4xn: (32n4-336n3+1702n2-4701n+5844)/3, n>=9, (V. Kotesovec, 26.1.2010)
5 bishops, board 5xn: (625n5-11250n4+98875n3-515250n2+1566016n-2194944)/24, n>=16, (V. Kotesovec, 26.1.2010)
6 bishops, board 6xn: (648n6-17820n5+240930n4-2011545n3+10806047n2-35094560n+53430940)/10, n>=25, (V. Kotesovec, 28.1.2010)

První členy těchto vzorců mají obecně tvar (kn)k/k! - (kn)k-1(2k-1)/2/(k-2)! + ...
Jiný možný zápis je (kn)k/k! - (kn)k-1*comb(2k-1,2)/2/(k-1)! + ...
kde comb(2k-1,2) je kombinační číslo "2k-1 nad 2".

OEIS linky:
A172207 - 3 bishops 3 X n
A172208 - 4 bishops 4 X n
A172210 - 5 bishops 5 X n
A172211 - 6 bishops 6 X n


n2 bishops3 bishops4 bishops5 bishops6 bishops
24691216
3112661143313
422862607702320
537211927336812160
65642625781263253744
779758596538566209428
810612341206698968683524
91371881221352223511905625
101722726376784506824664384
1121137966045784316910297579
12254511892488147911620907590
133016719136043246091239664250
143528626193650391722871114916
15407108662680936006056121559433
16466134663624128917888199459466
175291645347990312878847315906248
185961985462411818153806485124352
196672369679886525049515725031335
20742280061008208339177241057839684
21821328111256467451583081510706686
22904381381548218592223922116429956
23991440141888293766154762914190277
241082504662281780979005603950340692
2511775752127340231237012695279242444
2612766520632506221547049786964147544
2713797354838374331916659379078128011
28148682574450056823540839611705051758
29159792311524639528682973014940605138
301712102786608153834690356418893362144
311831114026701287741668289823685900265
321954126058804754849730323229455962998



5.1) Knights on board n x n - Jezdci na šachovnici n x n

Vzorce pro počet pozic neohrožujících se jezdců na šachovnici n x n.
2 knights, board nxn: (n-1)(n+4)(n2-3n+4)/2, (E.Lucas, 1891)

3 knights, board nxn: (n-2)(n+5)(n4-3n3-8n2+66n-108)/6, n>=4 , (K. Fabel, 1966)

4 knights, board nxn: (n8-54n6+144n5+1019n4-5232n3-2022n2+51120n-77184)/24, n>=6 (K. Fabel, 1966)

5 knights, board nxn: (n10-90n8+240n7+3235n6-16320n5-40530n4+396480n3-231656n2-3359520n+6509280)/120, n>=8 (V. Kotesovec, 25.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n2k/k! - 9n2k-2/2/(k-2)! + 12n2k-3/(k-2)! +...
Také v případě jezdců může být jejich počet větší než n (pro šachovnici 8x8 dokonce 32), obecně je tento maximální počet n2/2 (pro n>2 sudé) a (n2+1)/2 (pro n>1 liché), více viz Knights Problem

Linky na OEIS
A172132 - 2 knights NxN
A172134 - 3 knights NxN
A172135 - 4 knights NxN
A172136 - 5 knights NxN

Viz Edouard Lucas: Théorie des nombres (1891), vzorec pro počet rozmístění 2 neohrožujících se jezdců najdeme na str.98 (zde jsou správně znaménka, ale vypadl znak "p"), viz též Edouard Lucas: Récréations mathématiques (1894), str.132 (ve vzorci je však tisková chyba, před členem p2 má být +, ne -. Správně má být tedy (p-1)(p3+p2-8p+16)/2)


n2 knights3 knights4 knights5 knights
2641 
32836182
496276412340
5252136044369386
655047522613397580
7105613340111066649476
81848320843765603184708
9301668796108094212472084
104662135040273290941199404
1169002471526253408119171110
12985642738013204356309957412
131366870514426100160739123094
14184861118416488196771639655452
15244721715220871379343422020324
163180025552521493986086778432292
1740656371162024734994612833460256
1851238527270439716848523356032940
1963756734413662069661241051290730
20784321005090094692168469954580804


5.2) Knights on board k x n - Jezdci na šachovnici k x n

2 knights, board 2xn: 2n2-3n+4, n>=2
3 knights, board 3xn: (9n3-45n2+122n-144)/2, n>=4, (V. Kotesovec, 26.1.2010)
4 knights, board 4xn: 8(4n4-36n3+170n2-450n+537)/3, n>=6, (V. Kotesovec, 26.1.2010)
5 knights, board 5xn: (625n5-8250n4+57235n3-242778n2+608440n-705984)/24, n>=8, (V. Kotesovec, 26.1.2010)
6 knights, board 6xn: (648n6-11340n5+103770n4-606645n3+2328317n2-5466660n+6051720)/10, n>=10, (V. Kotesovec, 26.1.2010)
7 knights, board 7xn: (117649n7-2571471n6+29223943n5-216954465n4+1114503256n3-3907492824n2+8562799512n-8962924320)/720, n>=12, (V. Kotesovec, 29.1.2010)
8 knights, board 8xn: (262144n8-6881280n7+93456384n6-838693632n5+5361604836n4-24739168020n3+79766188151n2-163079018193n+160750559340)/630, n>=14, (V. Kotesovec, 27.3.2010)

První členy těchto vzorců mají obecně tvar (kn)k/k! - 3(k-1)(3k-4)(kn)k-1/k!/2 + ...
Jiný možný zápis je (kn)k/k! - comb(3k-3,2)*(kn)k-1/k! + ...
kde comb(3k-3,2) je kombinační číslo "3k-3 nad 2".

OEIS linky:
A172212 - 3 knights 3 X n
A172213 - 4 knights 4 X n
A172214 - 5 knights 5 X n
A172215 - 6 knights 6 X n
A172217 - 7 knights 7 X n
A174698 - 8 knights 8 X n


n2 knights3 knights4 knights5 knights6 knights7 knights8 knights
26121628587881
313368425972917584409
4241004121968883038588175720
53923314169386602853832462479881
658456364030842257318213534417925691
781796792882738858262889185492952858
8108128015384192336240444830108310379978716
91391935273524002775879329866698061286959255
10174278845432763984129271822198457643765248749
112133866714801360797261150085042619739805497200
122565196107608229105649238436106564284023226916560
133036805156184368122687675623210425102750866495373
14354872021983256870221487878223924818982104288896551
154091096830143284965342423665026973786593202154535834
16468135764041201233335238112712411884673662373400685738
17531165715312881745969158124957319532410762661407061211
185981998068658424179516862965246310974517681129334088897
1966923830873912328416671251190796481404916051866838857216
20744281481097432438429841776208532726886127562998390521676
218233296113615605763143224743934751073336840734693423716457
229063829616709687470922633889870701553438354347178585300523
2399344180203058495635956457091755422078883178910752346543734
241084506402445592121031712607966698030868017013815802269635646
251179577032921432151580209798418489742512672298422825234176903



5.3) Knights on cylindrical board n x n - Jezdci na válcové šachovnici n x n

Válcová šachovnice (vertical cylinder, Vertikalzylinder) je šachovnice stočená do válce tak, aby okrajové sloupce byly vedle sebe. Vertical cylinder - board with a- and h- files alongside one another.

2 knights, board nxn: n(n3-9n+12)/2, n>=5, (V. Kotesovec, 31.1.2010)
3 knights, board nxn: n(n-3)(n4+3n3-18n2-18n+164)/6, n>=6, (V. Kotesovec, 31.1.2010)
4 knights, board nxn: n(n7-54n5+72n4+1115n3-2616n2-8502n+26712)/24, n>=9, (V. Kotesovec, 31.1.2010)
5 knights, board nxn: n(n9-90n7+120n6+3395n5-8160n4-62130n3+204000n2+463464n-1888080)/120, n>=10, (V. Kotesovec, 31.1.2010)

První členy polynomu mají vždy tvar n2k/k! - 9n2k-2/2/(k-2)! + 6n2k-3/(k-2)! + ...

Počet pozic na válcové šachovnici n x n je vždy dělitelný n (to odpovídá tomu, že každou pozici je možno libovolně posunout doleva nebo doprava aniž by se nějak změnilo vzájemné napadání kamenů.)

OEIS linky:
A172964 - 2 knights cylindrical NxN
A172965 - 3 knights cylindrical NxN
A172966 - 4 knights cylindrical NxN
A172967 - 5 knights cylindrical NxN


n2 knights3 knights4 knights5 knights
2400 
318600
492240306208
5230101023653210
652240561904758056
710221206890503458157
81808300003283242524176
929706562898169310587591
104610130480254795536576380
1168422408565933257109008735
12979241896812681288289450344
131359869420025284363700477401
14184101104488475950231570789892
15243901697820853573953304892985
163171225338561468793126586928032
1740562368566824386787312530769343
1851138524160039245280322891446252


5.4) Knights on toroidal board n x n - Jezdci na prstencové šachovnici n x n

Prstencová šachovnice je kombinace vertikální a horizontální válcové šachovnice. Toroidal chessboard (anchor-ring) - board on which the a- and h-files are joined and the bottom and top ranks are also joined. The anchor-ring is a combination of the vertical and horizontal cylinders.

2 knights, board nxn: n2(n+3)(n-3)/2, n>=5, (V. Kotesovec, 31.1.2010)
3 knights, board nxn: n2(n4-27n2+218)/6, n>=6, (V. Kotesovec, 31.1.2010)
4 knights, board nxn: n2(n6-54n4+1115n2-8934)/24, n>=9, (V. Kotesovec, 31.1.2010)
5 knights, board nxn: n2(n8-90n6+3395n4-64290n2+522504)/120, n>=10, (V. Kotesovec, 31.1.2010)
6 knights, board nxn: n2(n10-135n8+8005n6-262665n4+4816354n2-39858840)/720, n>=13, (V. Kotesovec, 31.1.2010)
7 knights, board nxn: n2(n12-189n10+16135n8-801255n6+24595984n4-445931556n2+3756080880)/5040, n>=14, (V. Kotesovec, 18.2.2010)

První členy polynomu mají vždy tvar n2k/k! - 9n2k-2/2/(k-2)! + (243k+143)*n2k-4/24/(k-3)! - ...

Počet pozic na prstencové šachovnici n x n je vždy dělitelný n2 (to odpovídá tomu, že každou pozici je možno libovolně posunout ve směru obou os x nebo y aniž by se nějak změnilo vzájemné napadání kamenů). V případě bodových kamenů se se zvětšujícím se n zmenšuje rozdíl mezi normální a prstencovou šachovnicí, naopak v případě liniových kamenů tento rozdíl zůstává.

OEIS linky:
A172529 - 2 knights toroidal NxN
A172530 - 3 knights toroidal NxN
A172531 - 4 knights toroidal NxN
A172532 - 5 knights toroidal NxN
A172533 - 6 knights toroidal NxN
A173436 - 7 knights toroidal NxN


n2 knights3 knights4 knights5 knights6 knights7 knights
2200   
31860000
4882082281285616
520060060012000
6486325212357303125497280352
798010584687962839067645961359288
81760275842758881872064897289631404480
9291661992872532864318662560728339256836
1045501253002344025317029203222468002527519400
116776233772558076298179400132386826014053530964
12972040958412107196267487920459594333663100177488
13135206820842439244665901550014000143196240356217660
1418326108917246261537149690884038413461800803630856504
15243001678800834264003179369070967464108002416671974700
1631616251059214415763263820305922268344075526655251717376
174046036575842401196961220753513450049257211217015566051020
1851030520808438739392122396355496104804438436040822003107000
1963536726765260771534239617305308209698662930892679987456312
20782009961200929951100678600216804031211268200200490192134800



6.1) Nightriders on board n x n - Tátoši na šachovnici n x n

Vzorce pro počet pozic neohrožujících se tátošů na šachovnici n x n. Tátoš je liniový kámen s jednotkovým tahem jezdce. Nightrider is rider [1,2].

2 nightriders, board nxn: n(3n3-5n2+9n-4)/6, pro n sudé (even), (C. Poisson, Rex Multiplex 29/1990, p.829)
2 nightriders, board nxn: n(n-1)(3n2-2n+7)/6, pro n liché (odd), (C. Poisson, Rex Multiplex 29/1990, p.829)

3 nightriders, board nxn:
1/6*n6-5/6*n5+4031/1440*n4-621/100*n3+3313/288*n2-2623/150*n+82321/43200
+ (1/4*n3-25/32*n2+77/50*n-43/64)*(-1)n
- (1+(-1)n)/8*cos(pi*n/2)
+ 8/27*(-1)n*cos(pi*n/3)
+ (-4*(-1)n+(sqrt(5)+3+(1-sqrt(5)/5)*(-1)n)*n)*4/25*cos(pi*n/5)
+ (sqrt(58*sqrt(5)+130)-sqrt(50-22*sqrt(5))*(-1)n/5)*16/25*sin(pi*n/5)
+ (-4+(sqrt(5)/5+1+(3-sqrt(5))*(-1)n)*n)*4/25*cos(2*pi*n/5)
+ (sqrt(22*sqrt(5)+50)/5-sqrt(130-58*sqrt(5))*(-1)n)*16/25*sin(2*pi*n/5), (V. Kotesovec, 18.2.2010)

exact formula by Vaclav Kotesovec


Rekurentní vzorec:
an = 2an-1-an-3-2an-5+2an-6+an-8-3an-11+2an-13+4an-15-4an-16-2an-18+3an-20-an-23-2an-25+2an-26+an-28-2an-30+an-31, n>=32

Výše uvedený vzorec lze zapsat také ve formě tabulky takto:
n6/6-5*n5/6+4031*n4/1440-621/100*n3+3313/288*n2 -Cn*n+Dn + (1/4*n3-25/32*n2)*(-1)n

Konstanty Cn a Dn se opakují s periodou 60, tedy podle zbytku n při dělení 60, kde n je rozměr šachovnice n x n. Existuje tak 60 různých vzorců podle toho, zda je n tvaru 60a, 60a+1, ... , 60a+59 (kde a je celé nezáporné číslo). Konstanta Cn má kratší periodu 10.

n MOD 60CnDnCn, Dn periods
044/30    
11379/7575091/7200
21196/755353/450
31451/759723/800
41244/751412/225
559/3331/288
61244/75-151/50
71451/75-44717/7200
81196/75-2044/225
91379/75-3589/800
1044/31/18
111379/7575091/7200
121196/75296/25
131451/7584307/7200
141244/753049/450
1559/351/32
161244/75-892/225
171451/75-44717/7200
181196/75-407/50
191379/75-35501/7200
2044/3-4/9
211379/758699/800
221196/755353/450
231451/7584307/7200
241244/75168/25
2559/3331/288
261244/75-1559/450
271451/75-4613/800
281196/75-2044/225
291379/75-35501/7200
3044/31/2
311379/7575091/7200
321196/752564/225
331451/759723/800
341244/753049/450
3559/3331/288
361244/75-88/25
371451/75-44717/7200
381196/75-3863/450
391379/75-3589/800
4044/3-4/9
411379/7575091/7200
421196/75617/50
431451/7584307/7200
441244/751412/225
4559/351/32
461244/75-1559/450
471451/75-44717/7200
481196/75-216/25
491379/75-35501/7200
5044/31/18
511379/758699/800
521196/752564/225
531451/7584307/7200
541244/75361/50
5559/3331/288
561244/75-892/225
571451/75-4613/800
581196/75-3863/450
591379/75-35501/7200

Z výše uvedeného obecného vzorce vyplývají vzorce pro:
Cn = 2623/150 - 77/50*(-1)n - (sqrt(5)+3+(1-sqrt(5)/5)*(-1)n)*4/25*cos(pi*n/5) - (sqrt(5)/5+1+(3-sqrt(5))*(-1)n)*4/25*cos(2*pi*n/5)

Dn = 82321/43200-1/8*cos(pi*n/2)-16/25*cos(2*pi*n/5)+16/25*sqrt(58*sqrt(5)+130)*sin(pi*n/5)+16/125*sqrt(22*sqrt(5)+50)*sin(2*pi*n/5)
+ (-1)n*(-43/64-1/8*cos(pi*n/2)+8/27*cos(pi*n/3)-16/25*cos(pi*n/5)-sqrt(50-22*sqrt(5))*16/125*sin(pi*n/5)-sqrt(130-58*sqrt(5))*16/25*sin(2*pi*n/5))

Obecný vzorec byl ověřen na prvních 310 hodnotách.

Linky v OEIS
A172141 - 2 nightriders NxN
A173429 - 3 nightriders NxN


n2 nightriders3 nightriders4 nightriders
2641
3283618
496276412
524011523046
6518392017365
79801056868540
8171225348232164
9278453848655852
1043101062921680033
1163801947323855946
1291363394168279704
131268856265216532026
141720689979631456369
1522820138800856832396
1629728208390899009508
17380803044992165941072
18481024356344270328605
19599646102144427383994
20739208404204660479212
219016011380564996624154
22108966151991001476091049
23130548200198562144134416
24155216260671123066551576
25183200335518124315580852
26214838427660925994143473
27250380539816008213049038
282901926757080411127498228
293345448387673214901856642
3038383010336572819763006661
3143834012646366825947796192
3249849615374541233779182556
3356460818573218843590211584
3463712622312294855829979313
3571638026654747270956669486
3680284831684556089582262248
37896880374769664112325177234
38998982441318188140004466369
391109524517381252173440817244
401229040604134684213712999188
411357920702622052?
421496726814216544?
431645868940132020?
4418059361081959860?
4519773601241101728?
4621607581419389236?
4723565801618430292?
4825654721840319784?
4927879042086891176?
5030245502360526732?
5132759002663305556?
5235426562997922516?
5338253283366723560?
5441246463772742240?
5544411404218613152?
5647755684707735876?
5751284805243056424?
5855006625828368716?
5958926846466953812?
6063053607163029360?
6167392807920235852?
6271952868743245188?
6376739889636082848?
64817625610603906308?
65870272011651152152?
66925427812783496072?
67983158014005812832?
681043555215324329940?
691106686416744388300?
701172647018272801892?
711241506019915406448?
721313361621679638248?
731388284823571857756?
741466376625600160124?
751547710027771460968?
761632388830094552244?
771720488032576936124?
781812114235228140248?
791907344438056285612?
802006288041071675484?
812109024044283082684?
822215664647701627220?
832326290851336767992?
842441017655200483576?
852559928059302953672?
862683139863657058652?
872810738068273734740?
882942843273166808260?
893079542478348008556?
903220959083832153128?
913367182089631801732?
923518337695762809460?
9336745168102238605096?
9438358486109076128388?
9540024260116289716172?
9641743808123897441384?
9743518080131914588952?
9845348422140360414436?
9947235804149251191772?
10049181600158607409644?


6.2) Nightriders on board k x n - Tátoši na šachovnici k x n

2 nightriders, board 2xn: 2n2-3n+4, n>=2
3 nightriders, board 3xn: (9n3-57n2+210n-344)/2, n>=8, (V. Kotesovec, 26.1.2010)
4 nightriders, board 4xn: (32n4-432n3+3190n2-13323n+25530)/3, n>=18, (V. Kotesovec, 26.1.2010)
5 nightriders, board 5xn: (625n5-15250n4+197915n3-1588634n2+7645896n-17283552)/24, n>=32, (V. Kotesovec, 28.1.2010)

OEIS linky:
A172218 - 3 nightriders 3 X n
A172219 - 4 nightriders 4 X n
A172220 - 5 nightriders 5 X n


n2 nightriders3 nightriders4 nightriders5 nightriders6 nightriders
2612162858
3133684157315
42410041212483862
5392131126465019419
65840827601516285358
781712573937988256549
810811481098286958706060
91391745196951814231689706
101742528330683517083745158
112133524528016484417737606
12256476080638112739215042498
133036263118731187419428033286
143548060169368298846649685456
1540910178235135460209684688103
16468126443188906870240138994668
17531154854237339983347220999518
185981872855302814163972341148264
196692240071038919672403513146177
207442652889969026812260753927570
21823311391125059359294801084629369
22906362601390880474184821530923606
23993419181701793617232382123729778
241084481402062694793417202900209972
2511795495324787351008281753904141919
261278623842955324126796852?
271381704603498125157924785?
281488792084113058194954956?
291599886554806299238699512?
301714988285584280290042826?
3118331097546453689349944662?
3219561214607421470419443276?
3320831339738494823499658555?
3422141473209681204591795132?
35234916152810988325697145517?
36248817662412424154817093220?
37263119263513996915953115876?
382778209588157150881106788370?
392929227510175874091279785962?
403084246428196228701473887412?



7.1) Amazons (superqueens) on board n x n - Amazonky na šachovnici n x n

Amazonka je kombinovaný kámen s pohyblivostí dámy a jezdce. Amazon (=Superqueen) is queen + knight.

2 amazons, board nxn: (n-1)(n-2)(n-3)(3n+8)/6, (Christian Poisson, 1990)

3 amazons, board nxn: (2n6-20n5+31n4+314n3-1452n2+2040n-672)/12, pro sudá n (even), n>=4, (Panos Louridas, 2007)
3 amazons, board nxn: (2n6-20n5+31n4+314n3-1452n2+2034n-669)/12, pro lichá n (odd), n>=5, (Panos Louridas, 2007)

4 amazons, board nxn: n8/24-5n7/6+47n6/9+43n5/10-5053n4/24+112585n3/108-15433n2/8+55669n/270+119917/54 + (n3/4-21n2/8+7n-3/2)*(-1)n + 32/27*(n-1)*COS(2*pi*n/3) + 40*sqrt(3)*SIN(2*pi*n/3)/81, n>=6, (Vaclav Kotesovec, 12.2.2010)

Rekurentní vzorec: an = 3an-1+an-2-9an-3+12an-5+7an-6-15an-7-16an-8+16an-9+15an-10-7an-11-12an-12+9an-14-an-15-3an-16+an-17, n>=23

Explicitní vzorec pro 4 amazonky je velmi podobný vzorci pro 4 dámy, periodické členy se SIN a COS jsou shodné a polynom u (-1)n se liší jen v posledním členu. Rekurentní vzorec je dokonce zcela identický jako pro 4 dámy (sekvence vychází jen z jiných počátečních hodnot).

I když máme zatím příliš málo hodnot, je pravděpodobný průběh této funkce pro k amazonek na šachovnici n x n podobný jako pro dámy:
n2k/k! - 5/3*n2k-1/(k-2)! + ...

OEIS linky:
A172200 - 2 amazons (superqueens) n X n
A172201 - 3 amazons (superqueens) n X n
A173214 - 4 amazons (superqueens) n X n

Odkazy:
Christian Poisson, Rex Multiplex 29/1990, str. 829 (v té době vycházející francouzský časopis)
Panos Louridas, idee & form 93/2007, str. 2936-2938 (švýcarský časopis věnovaný skladebnímu šachu)


n2 amazons3 amazons4 amazons
2000
3000
42000
592482
6260424112
758019761754
81120661613074
919601785263400
10319241544234014
11492086660712248
1272601662881882132
13103402986164457246
14143005082009679760
151929282716819584514
1625480129674437367934
1733040196867667849336
18421602907016118085614
19530404189772198107620
20658925910944321870956
21809408182400508359070
229842011136168782972820
23118580149265361179105738
24141680197326001740089734
25167992257605882521359260
26197800332466643593085246
27231400424594765043058972
28269100537032166980158088
29311220673203929538095102
303580928369514412879874324
3141006010325624017202560582
3246748012648064822742900942
3353072015389675629783283628
3460016018608820038658709554
3567619222369730849764125812
3675922026742918463562947328
3784966031805537680595959410
38947940376418216101491605140
391054500443434712126976666126
401169792520101144157888541850


Problémem n neohrožujících se amazonek na šachovnici n x n se jako první zabýval matematik s přezdívkou Durango Bill, na jeho stránce Durango Bill's - The N-Queens Problem najdeme doposud známé výsledky. Na první pohled se zdá že takové rozestavení pro Amazonky (označované zde jako Superqueen) není možné, ale od šachovnice 10x10 taková řešení existují! Solution exist also for Amazone, N≥10 !
Zkusil jsem vypočítat konstanty pro amazonky podle prvních dvou hypotéz (recomputing constants by both conjectures)
Pro posouzení konvergence obou řad je však zatím k dispozici málo hodnot...

                                                         Durango Bill            Birger Nielsen  Rivin+Vardi+Zimmermann
      Order    < --- Ordinary Queens   --- >             < - Superqueens - >     (f(n)/n!)(1/(n-1))
      ("N")   Total Solutions   Unique Solutions         Tot. Sol. Unique Sol.                  log(f(n))/(n*log(n))
      --------------------------------------------------------------------------
      1                     1                  1                1              1  
      2                     0                  0                0              0
      3                     0                  0                0              0
      4                     2                  1                0              0
      5                    10                  2                0              0
      6                     4                  1                0              0
      7                    40                  6                0              0
      8                    92                 12                0              0
      9                   352                 46                0              0
      10                  724                 92                4              1  0.2177875229 0.0602059991
      11                 2680                341               44              6  0.2536469800 0.1434663320
      12                14200               1787              156             22  0.2571896108 0.1693509629
      13                73712               9233             1876            239  0.2861405294 0.2260322668
      14               365596              45752             5180            653  0.2780659430 0.2314830981
      15              2279184             285053            32516           4089  0.2863046443 0.2557679703
      16             14772512            1846955           202900          25411  0.2922654623 0.2754751459
      17             95815104           11977939          1330622         166463  0.2973799174 0.2927699845
      18            666090624           83263591          8924976        1115871  0.3013522738 0.3076183338
      19           4968057848          621012754         64492432        8062150  0.3052738993 0.3214276591
      20          39029188884         4878666808        495864256       61984976  0.3090010139 0.3341722647
      21         314666222712        39333324973       3977841852      497236090  0.3122951071 0.3457263661
      22        2691008701644       336376244042      34092182276     4261538564  0.3156003918 0.3566365819
      23       24233937684440      3029242658210     306819842212    38352532487  0.3186994535 0.3667617725
      24      227514171973736     28439272956934    2883202816808   360400504834  0.3215646055 0.3761463830
      25     2207893435808352    275986683743434   28144109776812  3518014210402  0.3241760378 0.3848344687
      26    22317699616364044   2789712466510289                ?              ?             ?            ?

Hodnoty pro N=24 a N=25 vypočítal Wolfram Schubert (2009), (updated 22.1.2010)
Hodnoty pro N=21 až 23 (updated 27.3.2007) jsou převzaty ze stránky "The Oprisch Family Web Site" N x N SuperQueens Solutions Table.

7.2) Amazons (superqueens) on board k x n - Amazonky na šachovnici k x n

Na stránce The Oprisch Family Web Site nalezneme také hodnoty i pro šachovnice k x n, včetně vzorců pro k = 2,3,4,5,6,7 a tabulek hodnot.
2xn:   (n-3)(n-2), n > 3
3xn:   (n-6)(n-5)(n-4), n > 6
4xn:   [(n-7)(n-6)(n-5)(n-4)+(n-10)(n-9)(n-8)(n-7)]/2, n > 7
5xn:   n5 -44n4 +823n3 -8168n2 +42796n -93984, n > 11
6xn:   n6 -63n5 +1775n4 -28613n3 +277462n2 -1526716n +3699966, n > 16
7xn:   n7 -85n6 +3329n5 -77911n4 +1175240n3 -11392990n2 +65448630n -171006180, n > 23

Obecně má polynom tvar: nk - (k+3)(3k-4)nk-1/2 + ...

Stejné hodnoty nalezneme také zde: OEIS - A051223, A051224


8.1) Zebras on board n x n - Zebry na šachovnici n x n

Vzorce pro počet pozic neohrožujících se zeber (skokanů [2,3]) na šachovnici n x n. Zebra is leaper [2,3].

2 zebras, board nxn: (n4-9n2+40n-48)/2, n>=2, (C. Poisson, Rex Multiplex 29/1990, p.829)

3 zebras, board nxn: (n6-27n4+120n3+74n2-1608n+2976)/6, n>=6, (V. Kotesovec, 24.1.2010)

4 zebras, board nxn: (n8-54n6+240n5+827n4-8592n3+10362n2+75600n-204864)/24, n>=9, (V. Kotesovec, 24.1.2010)

5 zebras, board nxn: (n10-90n8+400n7+2915n6-26880n5+2430n4+609920n3-1517496n2-4188480n+16581120)/120, n>=12, (V. Kotesovec, 26.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n2k/k! - 9n2k-2/2/(k-2)! + 20n2k-3/(k-2)! +...

Linky na OEIS
A172137 - 2 zebras NxN
A172138 - 3 zebras NxN
A172139 - 4 zebras NxN
A172140 - 5 zebras NxN


n2 zebras3 zebras4 zebras5 zebras
2641 
33684126126
411245211682032
52761772733420502
6582559635749160696
7109614888137970929880
81896346404389844117520
9307272712120824615037036
104726140716296938947368960
1169722550366662480132577826
12993643796813873100336828368
131375671898027144408789558314
14185821136092503895811729320120
15245761737376894240143574328936
163191225825761526382807027309888
1740776374484825183453013226773092
1851366531262040325069323959787480
1963892739157262879851641954706558
20785761010673695754316471276149776
2195652136047161427453780117848892710
22115366180560282087456085190142197976


8.2) Zebras on board k x n - Zebry na šachovnici k x n

2 zebras, board 2xn: n(2n-1), =all combinations
3 zebras, board 3xn: (9n3-21n2+50n-48)/2, n>=6, (V. Kotesovec, 26.1.2010)
4 zebras, board 4xn: 4(8n4-48n3+202n2-471n+507)/3, n>=9, (V. Kotesovec, 26.1.2010)
5 zebras, board 5xn: 5(125n5-1250n4+7575n3-28426n2+64000n-67056)/24, n>=12, (V. Kotesovec, 26.1.2010)
6 zebras, board 6xn: (1944n6-27540n5+227070n4-1222555n3+4366071n2-9580580n+9925860)/30, n>=15, (V. Kotesovec, 26.1.2010)

První členy těchto vzorců mají obecně tvar (kn)k/k! - (k-1)(9k-20)(kn)k-1/2/k! + ...

OEIS linky:
A172221 - 3 zebras 3 X n
A172222 - 4 zebras 4 X n
A172223 - 5 zebras 5 X n
A172224 - 6 zebras 6 X n


n2 zebras3 zebras4 zebras5 zebras6 zebras
262070252924
3158440619258989
4282001168653437270
545403294820502145233
666720657657710525796
7911180131221423121605490
81201808238083082544136952
91532631401686060519435413
10190367663996110533219632414
11231497097344189789937957424
122766540142516310025069050898
1332584132020724857000119351315
14378106162788287344010197524064
154351317637585610771530314935542
164961612049648415387310486171662
175611947564429621479725729604121
1863023268823132293809001068003424
19703275261037088394698351529198580
20780322761290516521755302146783422
21861375451588024679801102960869583
22946433601934476874219504018886128
2310354974823349921110988005376425842
2411285673627949481396709107098138174
2512256435133199761738641559258668837



9.1) Wazirs on board n x n - Vezíři na šachovnici n x n

Vzorce pro počet pozic neohrožujících se vezírů (skokanů [0,1]) na šachovnici n x n. Wazir is leaper [0,1].

2 wazirs, board nxn: n(n-1)(n2+n-4)/2, (C. Poisson, 1990)
3 wazirs, board nxn: (n-2)(n5+2n4-11n3-10n2+42n-12)/6, n>=2 (V. Kotesovec, 29.1.2010)
4 wazirs, board nxn: (n8-30n6+24n5+323n4-504n3-1110n2+2760n-1224)/24, n>=4, (V. Kotesovec, 29.1.2010)
5 wazirs, board nxn: (n10-50n8+40n7+995n6-1560n5-8890n4+21080n3+24264n2-97440n+59520)/120, n>=5, (V. Kotesovec, 29.1.2010)

Obecný vzorec není znám, ale první členy polynomu mají vždy tvar n2k/k! - 5n2k-2/2/(k-2)! + ...

OEIS linky:
A172225 - 2 wazirs n X n
A172226 - 3 wazirs n X n
A172227 - 4 wazirs n X n
A172228 - 5 wazirs n X n


n2 wazirs3 wazirs4 wazirs5 wazirs
2200 
3242261
496276405304
52601474502410741
6570524831320127960
7109214690133544870589
81904350124464214197456
9309674326125859016005187
104770144544312672451439096
1170402623987042930145085447
121003245058014669709369074128
131388473900228658436863338777
14187461166176530690001883786680
15247801780714939099243875953561
163216026429481598199657583888944
1741072382667026291387414206566327
1851714542099241981667625617069208
1964296753232665291251044663199283
20790401028648499183574975572017136


9.2) Wazirs on board k x n - Vezíři na šachovnici k x n

2 wazirs, board 2xn: 2(n-1)2
3 wazirs, board 3xn: (3n-5)(3n2-8n+8)/2, n>=2, (V. Kotesovec, 29.1.2010)
4 wazirs, board 4xn: (64n4-432n3+1235n2-1797n+1122)/6, n>=3, (V. Kotesovec, 29.1.2010)
5 wazirs, board 5xn: (625n5-5750n4+23535n3-54202n2+70640n-41616)/24, n>=4, (V. Kotesovec, 29.1.2010)
6 wazirs, board 6xn: 2*(486n6-5670n5+30240n4-95230n3+187899n2-220775n+120540)/15, n>=5, (V. Kotesovec, 29.1.2010)
7 wazirs, board 7xn: (117649n7-1663893n6+10942729n5-43685355n4+114945646n3-199980312n2+213228096n-107390880)/720, n>=6, (V. Kotesovec, 29.1.2010)

První členy těchto vzorců mají obecně tvar (kn)k/k! - (k-1)(5k-2)*(kn)k-1/2/k! + ...

OEIS linky:
A172229 - 3 wazirs 3 X n
A172230 - 4 wazirs 4 X n
A172231 - 5 wazirs 5 X n
A172232 - 6 wazirs 6 X n
A172234 - 7 wazirs 7 X n


n2 wazirs3 wazirs4 wazirs5 wazirs6 wazirs7 wazirs
2222222
3822611745041478
4188440519981001050726
53221515021074178052573797
6504424072384383688683581924
7727929091107004128083215516804
898129217791251354361234452550366
91281969316605225288774380149162199
1016228505244299081619049692370817854
11200396282137174888337898664831571604
1224253321230012914894703118241717417198
13288698717754646356391232090123316210152
14338895424854070896582058852046054985120
15392112603390071049036633050299210545491888
16450139324522271508917851263172017638773534
17512169975917362117863477183327628489610297
185782048276132629095524113229454044631652698
196482441496504539224013162350648868064067456
20722288201207197519987662280989952101350519742




10) Other fairy pieces - další exokameny

Další vzorce pro rozmístění neohrožujících se exokamenů publikoval Christian Poisson v roce 1990 ve francouzském časopise Rex Multiplex. Celkem 44 vzorců (převážně vždy pro rozmístění 2-3 kamenů) vyšlo ve dvou pokračováních Rex Multiplex 29/1990, str. 829-830 a Rex Multiplex 30/1990, str. 914-915.

Nejzajímavější je tento pěkný obecný vzorec pro rozmístění dvou skokanů [x,y]
Two leapers [x,y] on chessboard n x n:

x >= y >= 0 and x+y <> 0
(n4-9n2+8(x+y)n-8xy)/2, for x <> y <> 0, n>=x
(n4-5n2+4(x+y)n-4xy)/2, for x=y or y=0, n>=x

Speciálně pro x=3 a y=2 dostaneme shodný vzorec pro 2 Zebry, pro x=1 a y=0 dostaneme shodný vzorec pro 2 Vezíry.

Jak jsem však zjistil, tento vzorec objevil už Edouard Lucas v roce 1891, když ve své knize Théorie des nombres uvádí na str.97 obecnější vzorec pro počet ohrožujících se skokanů [r,s] na šachovnici p x q
(2p - r - s)(2q - r - s) - (r - s)2
Když v tomto vzorci položíme p = q = n a uvědomíme-li si, že celkový počet kombinací 2 kamenů na šachovnici n x n je n2 nad 2, dostáváme odtud pro počet neohrožujících se skokanů [r,s] výraz
n2(n2-1)/2 - (4n2 - 4n(r + s) + 4rs) = (n4 - 9n2 + 8n(r + s) - 8rs)/2, což odpovídá výše uvedenému vzorci



home page