Mathematical articles and books by Vaclav Kotesovec

  • Asymptotic of subsequences of A212382, mirror - application of the theorem by Bender for ordinary generating functions (added 17.7.2014)
  • Asymptotic of sequences A161630, A212722, A212917 and A245265, mirror - application of the theorem by Bender for exponential generating functions (added 16.7.2014)
  • Asymptotic of sequences A244820, A244821 and A244822, mirror (added 11.7.2014)
  • Asymptotic of number of permutations of length n with longest increasing subsequence of length k - conjecture (added 18.3.2014)
  • Asymptotic of implicit functions if Fww = 0 - extension of theorem by Bender (added 19.1.2014)
  • Asymptotic of sequence A227403 - rigorous proof and conjecture (added 21.9.2013)
  • Asymptotic of Young tableaux of bounded height - conjecture (added 12.9.2013)
  • Asymptotic of sequence A084611 (added 26.7.2013)
  • Interesting asymptotic formulas for binomial sums (added 9.6.2013, extended 28.6.2013)
  • Asymptotic of generalized Apéry sequences with powers of binomial coefficients (added 4.11.2012, extended 23.11.2012)
  • Too many errors around coefficient C1 in asymptotic of sequence A002720 - I found bug in program Mathematica! (added 28.9.2012)
  • Asymptotic of a sums of powers of binomial coefficients * x^k (added 20.9.2012)
  • Asymptotic formula for number of fat trees on n labeled vertices - OEIS A055779 (added 27.8.2012)

    Next over 3500 of my formulas and comments can be found in the On-Line Encyclopedia of Integer Sequences, OEIS.

    Non-attacking chess pieces (2013)

    A book is devoted to the question of the number of arrangements of non-attacking chess pieces of the same kind on chessboards of various sizes and types. The best-known example is the n-Queens problem, but this publication has a much wider range and includes other chess pieces (kings, rooks, bishops, knights) and many fairy pieces. Even though the book is about chess and each problem can be placed among chess-mathematical problems, it will be more readily understandable by mathematicians than by chess players or composers. A partial knowledge of linear algebra, difference equations, generating functions and power series is necessary.


      Non-attacking chess pieces (sixth edition)
    (chess and mathematics)

    by Vaclav Kotesovec

    795 pages, over 500 formulas, many tables

    published 2.2.2013

    free download PDF (14 MB)
    temporary mirror (faster, but please don't use this link as citation)

    New in the sixth edition (this edition is probably final):
  • For pieces Rookhopper and Bishophopper (include number of stalemate positions!) see new chapters 9.9
  • For maximal number of non-attacking riders [r,s], see updated chapter 14.1
  • New formulas for semi-knights and generally for semi-leapers, see new chapter 5.1.2
  • Enhanced table of entropy constants, see page 69
  • New recurrence for bishops on an toroidal chessboard n x n if n is even, see page 280
  • Both constants in the asymptotic formula for composite pieces semi-Rook + semi-Bishop are now in closed form!, see page 717
  • Formula for 10 non-attacking kings on an n x n chessboard, see updated chapter 2.1

    New in the fifth edition:
  • For general asymptotic formulas see new chapter 13.1
  • For new results for m x n non-attacking kings on a 2m x 2n chessboard see chapters 2.3 and 2.3.9
  • For non-attacking kings on the cylindrical chessboard, see the new chapters 2.6, 2.6.9, 2.7 and 2.5
  • For new formula for the number of ways of placing n2 non-attacking kings on an 2n x 2n toroidal chessboard, see the new chapter 2.9
  • For explicit formula for the number of ways of placing 6 non-attacking queens on an n x n toroidal chessboard, see the updated chapter 1.3
  • For non-attacking nightriders on the cylindrical chessboard, see the new chapters 6.5 and 6.6
  • Roots of a polynomials as points in the complex plane
  • Added pieces semi-wazir, semi-fers and semi-knight (interesting from mathematical view point), see new chapters 9.1.1, 9.3.1, 9.4.1 and 5.1.1
  • Reduced PDF size
    Errata 5th edition

    New in the fourth edition:
  • For general formulas for the number of ways of placing k non-attacking bishops on an n x n chessboard (including the most interesting case k=n), see the updated chapters 4.1, 4.3 and new chapters 4.1.1, 4.1.2., 4.4.
  • For miscellaneous problems with rooks, see chapter 3.1.1
  • An extensive new chapter 12 is devoted to the asymptotic behaviour of sequences of numbers of ways of placing non-attacking composite pieces rook + leaper, queen + leaper, rook + rider, queen + rider. There are many new formulas, conjectures, graphs and tables of values.
  • For maximal number of non-attacking pieces, see chapter 14

    New in the third edition:
  • 8n nonattacking kings on a 16 x 2n chessboard, formula for smallest root (include limit)
  • Formula for 5 non-attacking amazons on a n x n board
  • Kings, amazons and zebras on a toroidal chessboard
  • 65 new explicit formulas added to section Riders, total more than 300 explicit formulas in third edition now
  • New results and tables for 2 riders on a toroidal chessboard
  • Method for transformation of formulas with Floor function to expressions with trigonometric functions
  • Index of citations

    New in the second edition:
  • General recurrence for number of ways of placing k non-attacking queens on an n x n chessboard
  • Leapers
  • Riders


    Related articles:
    A q-Queens Problem, I. General theory - Seth Chaiken, Christopher R. H. Hanusa, Thomas Zaslavsky, 8.3.2013, updated 21.2.2014
    A q-Queens Problem. II. The square board - Seth Chaiken, Christopher R. H. Hanusa, Thomas Zaslavsky, 21.2.2014
    A q-Queens Problem. III. Partial queens - Seth Chaiken, Christopher R. H. Hanusa, Thomas Zaslavsky, 21.2.2014
    A q-Queens Problem. V. The Bishops' Period - Seth Chaiken, Christopher R. H. Hanusa, Thomas Zaslavsky, 14.5.2014
    Nonattacking Queens in a Rectangular Strip - Seth Chaiken, Christopher R. H. Hanusa, Thomas Zaslavsky, 25.5.2011
    Podschet rasstanovok ferzey na shakhmatnoy doske - Artem M. Karavaev, Kazanskaya Nauka 10, 2010, p.13-16
    The number of {1243, 2134}-avoiding permutations - David Callan, 15.3.2013
    Strong and ratio asymptotics for Laguerre polynomials revisited - Alfredo Deano, Edmundo J. Huertas, Francisco Marcellan, 24.6.2013





    OLD ARTICLE (no longer updated!)

    For compatibility of links I keep this page, but I strongly recommend my new 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) - 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

    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