Wielomian Rooka

	A	B	C	D	mi	F	G	H
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	B	C	D	mi	F	G	H

Jedno z możliwych rozmieszczeń wież na szachownicy 8 × 8, w którym żadne dwie figury nie dzielą rzędu ani kolumny.

W matematyce kombinatorycznej wielomian wieży jest wielomianem generującym liczbę sposobów umieszczenia nieatakujących wież na szachownicy wyglądającej jak szachownica ; to znaczy, że żadne dwie wieże nie mogą znajdować się w tym samym rzędzie lub kolumnie. Plansza to dowolny podzbiór kwadratów prostokątnej planszy z m rzędami i n kolumnami; myślimy o tym jak o polach, na których można postawić wieżę. Szachownica jest zwykłą szachownicą , jeśli wszystkie pola są dozwolone i m = n = 8 i szachownicę dowolnej wielkości, jeśli dozwolone są wszystkie kwadraty oraz m = n . Współczynnik x   ^k w wielomianu wieży RB _B ( x ) to liczba sposobów ułożenia k wież , z których żadna nie atakuje drugiej, w kwadratach B . Gawrony są ułożone w taki sposób, że w tym samym rzędzie lub kolumnie nie ma pary wież. W tym sensie układ to ustawienie wież na statycznej, nieruchomej desce; układ nie będzie inny, jeśli plansza zostanie obrócona lub odbita, utrzymując kwadraty nieruchome. Wielomian pozostaje taki sam również w przypadku zamiany wierszy lub kolumn.

Termin „wielomian wieży” został ukuty przez Johna Riordana . Pomimo tego, że nazwa wywodzi się od szachów , impulsem do badania wielomianów wieżowych jest ich związek z liczeniem permutacji (lub permutacji częściowych ) z ograniczonymi pozycjami. Plansza B będąca podzbiorem szachownicy n × n odpowiada permutacjom n obiektów, które możemy przyjąć za liczby 1, 2, ..., n , takie, że liczba a _j w j -ta pozycja w permutacji musi być numerem kolumny dozwolonego kwadratu w wierszu j B . Słynne przykłady obejmują liczbę sposobów umieszczenia n nieatakujących wież na:

• cała szachownica n × n , co jest elementarnym problemem kombinatorycznym;
• zabroniona jest ta sama plansza z ukośnymi kwadratami; jest to zaburzenia lub „hakowania kapelusza” (jest to szczególny przypadek problème des rencontres );
• ta sama plansza bez kwadratów na jej przekątnej i bezpośrednio nad jej przekątną (i bez lewego dolnego kwadratu), co jest istotne przy rozwiązaniu problemu ménages .

Zainteresowanie rozmieszczeniem wież pojawia się w czystej i stosowanej kombinatoryce, teorii grup , teorii liczb i fizyce statystycznej . Szczególna wartość wielomianów wież wynika z użyteczności podejścia opartego na funkcji generującej, a także z faktu, że zera wielomianu wieży szachownicy dostarczają cennych informacji o jej współczynnikach, tj. liczbie nieatakujących rozmieszczeń wież k . .

Definicja

Wielomian wieży RB ( x ) deski B jest funkcją generującą liczbę układów wież nieatakujących _:

${\ Displaystyle R_ {B} (x) = \ suma _ {k = 0} ^ {\ min {(m, n)}}r_{k}(B)x^{k},}$

gdzie $_$ liczbą sposobów na szachownicy . Szachownica może pomieścić maksymalną liczbę nieatakujących wież; w istocie $być więcej$ niż liczba rzędów lub liczba kolumn na szachownicy (

Kompletne deski

Dla prostokątnych tablic m × n B _{m , n} piszemy R _m,n := R _{B m , n} i jeśli m = n , R _n := R _{m , n} .

Kilka pierwszych wielomianów wieżowych na kwadratowych tablicach n × n to:

${\ Displaystyle {\ początek {wyrównane} R_ {1} (x) i = x + 1 \\ R_ {2} (x) i = 2x ^ {2} + 4x +1\\R_{3}(x)&=6x^{3}+18x^{2}+9x+1\\R_{4}(x)&=24x^{4}+96x^{3} +72x^{2}+16x+1.\end{aligned}}}$

Krótko mówiąc, oznacza to, że na planszy 1 × 1 1 wieżę można ułożyć w 1 sposób, a wieże zerowe można również ułożyć w 1 sposób (pusta plansza); na kompletnej planszy 2×2 2 wieże można ułożyć na 2 sposoby (na przekątnych), 1 wieżę można ułożyć na 4 sposoby, a zero wież można ułożyć na 1 sposób; i tak dalej dla większych desek.

Wielomian wieży prostokątnej szachownicy jest ściśle powiązany z uogólnionym wielomianem Laguerre'a L _n ^α ( x ) przez tożsamość

${\ Displaystyle R_ {m, n} (x) = n! x ^ {n} L_ {n} ^ {(mn)} (-x ^ {- 1}).}$

Dopasowywanie wielomianów

Wielomian Rooka jest szczególnym przypadkiem jednego rodzaju wielomianu pasującego , który jest funkcją generującą liczbę k dopasowań krawędzi na wykresie.

  Wielomian wieży R _{m , n} ( x ) odpowiada pełnemu grafowi dwudzielnemu K _{m , n} . Wielomian wieży ogólnej planszy B ⊆ B _{m , n} odpowiada grafowi dwudzielnemu z lewymi wierzchołkami v ₁ , v ₂ , ..., v _m i prawymi wierzchołkami w ₁ , w ₂ , ..., w _n i krawędź v _i w _j , ilekroć kwadrat ( i , j ) jest dozwolony, tj. należy do B . Zatem teoria wielomianów wieżowych jest w pewnym sensie zawarta w teorii pasujących wielomianów.

Wyprowadzamy ważny fakt dotyczący współczynników r _k , który pamiętamy, biorąc pod uwagę liczbę nieatakujących rozmieszczeń wież k w B : liczby te są jednomodalne , tj. rosną do maksimum, a następnie maleją. Wynika to (w drodze standardowego argumentu) z twierdzenia Heilmanna i Lieba o zerach pasującego wielomianu (innego niż ten, który odpowiada wielomianowi wieży, ale równoważnego mu przy zmianie zmiennych), co implikuje, że wszystkie zera wielomianu wieżowego są ujemnymi liczbami rzeczywistymi.

Podłączenie do stałych matryc

W przypadku niekompletnych plansz n × n (tj. wieżami nie można grać na dowolnym podzbiorze pól szachownicy) obliczenie liczby sposobów umieszczenia n wież na planszy jest równoznaczne z obliczeniem stałej macierzy 0–1 .

Kompletne deski prostokątne

Problemy Rooksa

	A	B	C	D	mi	F	G	H
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	B	C	D	mi	F	G	H

Ryc. 1. Maksymalna liczba nieatakujących wież na szachownicy 8×8 wynosi 8. Wieża + kropki oznaczają liczbę pól w szeregu, dostępnych dla każdej wieży po ustawieniu wież na niższych szeregach.

Prekursorem wielomianu wieży jest klasyczny „Problem ośmiu wież” HE Dudeneya, w którym pokazuje on, że maksymalna liczba nieatakujących wież na szachownicy wynosi osiem, umieszczając je na jednej z głównych przekątnych (ryc. 1). Pytanie brzmi: „Na ile sposobów można ustawić osiem wież na szachownicy 8 × 8 tak, aby żadna z nich nie atakowała drugiej?” Odpowiedź brzmi: „Oczywiście w każdym rzędzie i w każdej kolumnie musi znajdować się wieża. Zaczynając od dolnego rzędu, jasne jest, że pierwszą wieżę można postawić na dowolnym z ośmiu różnych pól (ryc. 1). Gdziekolwiek się znajduje ułożone, istnieje możliwość wyboru siedmiu pól dla drugiej wieży w drugim rzędzie. Następnie jest sześć pól, z których można wybrać trzeci rząd, pięć w czwartym itd. Dlatego liczba różnych sposobów musi wynosić 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40 320” (czyli 8!, gdzie „!” to silnia ).

Ten sam wynik można uzyskać w nieco inny sposób. Każdej wieży nadamy numer pozycyjny odpowiadający numerowi jej rangi i przypiszemy jej nazwę odpowiadającą nazwie jej pliku. Zatem wieża a1 ma pozycję 1 i nazwę „a”, wieża b2 ma pozycję 2 i nazwę „b” itd. Następnie uporządkujmy wieże w uporządkowaną listę ( kolejność ) według ich pozycji. Diagram na ryc. 1 zostanie wówczas przekształcony w sekwencję (a, b, c, d, e, f, g, h). Umieszczenie dowolnej wieży na innym pliku wiązałoby się z przeniesieniem wieży, która dotychczas zajmowała drugi plik, do pliku, opuszczonego przez pierwszą wieżę. Na przykład, jeśli wieża a1 zostanie przeniesiona do pliku „b”, wieża b2 musi zostać przeniesiona do pliku „a” i teraz staną się wieżami b1 i wieżami a2. Nowa sekwencja będzie miała postać (b,a,c,d,e,f,g,h). W kombinatoryce operacja ta nazywa się permutacja , a sekwencje otrzymane w wyniku permutacji są permutacjami danej sekwencji. Całkowita liczba permutacji zawierających 8 elementów z ciągu 8 elementów wynosi 8! ( silnia 8).

Aby ocenić wpływ nałożonego ograniczenia „wieże nie mogą się atakować”, należy rozważyć problem bez takiego ograniczenia. Na ile sposobów można ustawić osiem wież na szachownicy 8×8? Będzie to łączna liczba kombinacji 8 wież na 64 polach:

${\ Displaystyle {64 \ wybierz 8} = {\ Frac {64!} {8! (64-8)!}} = 4 426$

Zatem ograniczenie „wieże nie mogą się atakować” zmniejsza całkowitą liczbę dopuszczalnych pozycji z kombinacji do permutacji, co stanowi współczynnik około 109 776.

Szereg problemów z różnych sfer ludzkiej działalności można sprowadzić do problemu wieży, nadając im „sformułowanie wieży”. Przykładowo: firma musi zatrudniać n pracowników na n różnych stanowiskach, a każde stanowisko musi być wykonywane tylko przez jednego pracownika. Na ile sposobów można dokonać tego spotkania?

Umieśćmy robotników na szeregach szachownicy n × n , a stanowiska pracy na kartotekach. Jeśli robotnik i zostanie wyznaczony do pracy j , wieża zostanie umieszczona na polu, w którym ranga i przecina linię j . Ponieważ każdą pracę wykonuje tylko jeden robotnik i każdy robotnik jest przydzielony tylko do jednej pracy, we wszystkich plikach i szeregach będzie znajdować się tylko jedna wieża w wyniku ułożenia n wież na szachownicy, czyli wieże nie atakują nawzajem.

Wielomian wieży jako uogólnienie problemu wież

Klasyczny problem wież natychmiast podaje wartość r ₈ , współczynnik stojący przed wyrazem najwyższego rzędu wielomianu wieży. Rzeczywiście, jego wynik jest taki, że 8 nieatakujących wież można ustawić na szachownicy 8 × 8 w r ₈ = 8! = 40320 sposobów.

Uogólnijmy ten problem, rozważając tablicę m × n , to znaczy tablicę z m rangami (wierszami) i n plikami (kolumnami). Pojawia się problem: na ile sposobów można ustawić k wież na planszy m × n tak, aby nie atakowały się nawzajem?

Jest oczywiste, że aby problem można było rozwiązać, k musi być mniejsze lub równe mniejszej z liczb m i n ; w przeciwnym razie nie można uniknąć umieszczenia pary wież w szeregu lub w pliku. Niech ten warunek zostanie spełniony. Następnie układanie wież można przeprowadzić w dwóch etapach. Najpierw wybierz zestaw k szeregów, na których chcesz umieścić wieże. Ponieważ liczba rang wynosi m , z czego k należy wybrać, wyboru tego można dokonać w ${\ displaystyle {\ binom {m} {k}}}$ sposoby. $,$ zbiór k plików można umieścić wieże, można wybrać na różne sposoby Ponieważ wybór plików nie zależy od wyboru rang, zgodnie z regułą iloczynów istnieją ${\ displaystyle {\ binom {m} {k}} {\ binom {n} {k }}}$ sposobów wyboru pola, na którym ma zostać umieszczona wieża.

Jednak zadanie nie jest jeszcze ukończone, ponieważ k szeregów i k plików przecina się w k ² kwadratach. Usuwając nieużywane rangi i pliki i kompaktując razem pozostałe rangi i pliki, uzyskuje się nową tablicę k rang i k plików. Pokazano już, że na takiej desce k wież można ustawić w k ! sposoby (aby się nie atakowały). Zatem łączna liczba możliwych ustawień wież nieatakujących wynosi:

${\ Displaystyle r_ {k} = {\ binom {m} {k}} {\ binom {n} {k}} k! = {\ frac {n! m!} !}}.}$

Na przykład 3 wieże można ustawić na konwencjonalnej szachownicy (8 × 8) w ${\ Displaystyle \ Textstyle {\ Frac {8!8!} = 18,816}$ sposobów. Dla k = m = n powyższy wzór daje r _k = n ! co odpowiada wynikowi uzyskanemu dla klasycznego problemu wież.

Wielomian wieży z jawnymi współczynnikami ma teraz postać:

${\ Displaystyle R_ {m, n} (x) = \ suma _ {k = 0} ^ {\ min (m, n)} {\ binom {m} {k}} {\ binom {n} {k} }k!x^{k}=\suma _{k=0}^{\min(m,n)}{\frac {n!m!}{k!(nk)!(mk)!}}x ^{k}.}$

Jeżeli ograniczenie „wieżowce nie mogą atakować się nawzajem” zostanie usunięte, należy wybrać dowolne k kwadratów z m × n kwadratów. Można to zrobić w:

${\ Displaystyle {\ binom {mn} {k}} = {\ Frac {(mn)!} {k! (mn-k)!}}}$ sposoby.

Jeżeli wieże k różnią się od siebie w jakiś sposób, np. są oznaczone lub ponumerowane, wszystkie dotychczas uzyskane wyniki należy pomnożyć przez k !, czyli liczbę permutacji wież k .

Układy symetryczne

Jako kolejną komplikację problemu wież wymagamy, aby wieże były nie tylko nieatakujące, ale także symetrycznie rozmieszczone na szachownicy. W zależności od rodzaju symetrii jest to równoznaczne z obróceniem lub odbiciem planszy. Układy symetryczne prowadzą do wielu problemów, w zależności od warunku symetrii.

	A	B	C	D	mi	F	G	H
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	B	C	D	mi	F	G	H

Ryc. 2. Symetryczny układ nieatakujących wież wokół środka szachownicy 8 × 8. Ryc. Kropki zaznaczają 4 środkowe kwadraty otaczające środek symetrii.

Najprostszym z tych układów jest sytuacja, gdy wieże są symetryczne względem środka szachownicy. Oznaczmy G _n liczbę układów, w których n wież jest umieszczonych na szachownicy o n szeregach i n plikach. Teraz uczyńmy tablicę zawierającą 2 n rang i 2 n plików. Wieżę z pierwszego rzędu można umieścić na dowolnym z 2 n pól tego pola. Zgodnie z warunkiem symetrii położenie tej wieży określa położenie wieży stojącej na ostatniej rzędzie – musi być ona ustawiona symetrycznie do pierwszej wieży względem środka szachownicy. Usuńmy pierwszy i ostatni plik oraz szeregi zajęte przez wieże (ponieważ liczba szeregów jest parzysta, usunięte wieże nie mogą stać na tym samym szeregu). To da planszę złożoną z 2 osób n - 2 pliki i 2 n - 2 szeregi. Jest oczywiste, że każdemu symetrycznemu rozmieszczeniu wież na nowej szachownicy odpowiada symetryczne rozmieszczenie wież na pierwotnej szachownicy. Zatem G _{2 n} = 2 nG _{2 n − 2} (współczynnik 2 n w tym wyrażeniu wynika z możliwości, że pierwsza wieża zajmie dowolne z 2 n kwadraty na pierwszym pliku). Iterując powyższą formułę dochodzimy do przypadku planszy 2×2, na której znajdują się 2 układy symetryczne (na przekątnych). W wyniku tej iteracji ostatecznym wyrażeniem jest G _{2 n} = 2 ⁿ n ! Dla zwykłej szachownicy (8 × 8) G ₈ = 2 ⁴ × 4! = 16 × 24 = 384 centralnie symetryczne układy 8 wież. Jeden z takich układów pokazano na ryc. 2.

W przypadku plansz o nieparzystych rozmiarach (zawierających 2 n + 1 szeregów i 2 n + 1 plików) zawsze istnieje kwadrat, który nie ma swojego symetrycznego dubletu – jest to centralny kwadrat planszy. Na tym polu zawsze musi znajdować się wieża. Usuwając centralny plik i rangę, otrzymujemy symetryczny układ 2 n wież na planszy 2 n × 2 n . Dlatego dla takiej tablicy jeszcze raz G _{2 n + 1} = G _{2 n} = 2 ⁿ n !.

Nieco bardziej skomplikowanym problemem jest znalezienie liczby nieatakujących układów, które nie zmieniają się po obrocie planszy o 90°. Niech szachownica będzie miała 4 n rzędów i 4 n szeregów, a liczba wież również będzie wynosić 4 n . W tym przypadku wieża znajdująca się w pierwszym szeregu może zajmować dowolne pole tego rzędu, z wyjątkiem pól narożnych (wieża nie może znajdować się na polu narożnym, ponieważ po obrocie o 90° 2 wieże atakują się nawzajem). Istnieją jeszcze 3 wieże, które odpowiadają tej wieży i stoją one odpowiednio na ostatnim rzędzie, ostatnim rzędzie i pierwszym rzędzie (uzyskuje się je z pierwszej wieży o 90°, 180° i 270°). Usuwając pliki i szeregi tych wież, otrzymujemy układ wież dla szachownicy (4 n - 4) × (4 n - 4) o wymaganej symetrii. Zatem następująca relacja nawrotu otrzymujemy: R _{4 n} = (4 n − 2) R _{4 n − 4} , gdzie R _n jest liczbą układów dla n × n planszy. Iterując, wynika, że ​​R _{4 n} = 2 n (2 n - 1) (2 n - 3)...1. Liczba układów dla planszy (4 n + 1) × (4 n + 1) jest taka sama, jak dla planszy 4 n × 4 n tablica; dzieje się tak, ponieważ na szachownicy (4 n + 1) × (4 n + 1) jedna wieża musi koniecznie stać pośrodku, w ten sposób można usunąć centralny rząd i linię. Dlatego R _{4 n + 1} = R _{4 n} . Dla tradycyjnej szachownicy ( n = 2) R ₈ = 4 × 3 × 1 = 12 możliwych układów z symetrią obrotową.

Dla tablic (4 n + 2) × (4 n + 2) i (4 n + 3) × (4 n + 3) liczba rozwiązań wynosi zero. Dla każdej wieży możliwe są dwa przypadki: albo stoi pośrodku, albo nie stoi pośrodku. W drugim przypadku wieża ta wchodzi w skład kwartetu wież, który wymienia pola przy obróceniu szachownicy o 90°. Zatem całkowita liczba wież musi wynosić albo 4 n (gdy na planszy nie ma centralnego pola), albo 4 n + 1. Dowodzi to, że R _{4 n + 2} = R _{4 n + 3} = 0.

Liczbę ułożeń n wież nieatakujących symetrycznych do jednej z przekątnych (dla ustalenia przekątna odpowiadająca a1–h8 na szachownicy) na szachownicy n × n jest dana numerami telefonów określonymi przez powtarzalność Q _n = Q _{n - 1} + ( n - 1) Q _{n - 2} . Powtarzalność tę wyprowadza się w następujący sposób. Zwróć uwagę, że wieża w pierwszym rzędzie stoi albo na dolnym narożniku, albo na innym polu. W pierwszym przypadku usunięcie pierwszego pliku i pierwszego rzędu prowadzi do ułożenia symetrycznego n - 1 wież na planszy ( n - 1) × ( n - 1). Liczba takich układów wynosi Q _{n - 1} . W drugim przypadku dla pierwotnej wieży przypada inna wieża, symetryczna do pierwszej o wybranej przekątnej. Usunięcie plików i szeregów tych wież prowadzi do symetrycznego ułożenia n - 2 wież na planszy ( n - 2) × ( n - 2). Ponieważ liczba takich układów wynosi Q _{n - 2} , a wieżę można postawić na n − 1 kwadrat pierwszego pliku, istnieją ( n − 1) Q _{n − 2} sposoby na zrobienie tego, co natychmiast daje powyższą powtarzalność. Liczbę układów diagonalno-symetrycznych wyraża się wówczas wzorem:

${\ Displaystyle Q_ {n} = 1 + {\ binom {n} {2}} + {\ Frac {1} {1 \ razy 2}} {\ binom {n}} 2} -4}{2}}+\cdots .}$

Wyrażenie to wywodzi się z podziału wszystkich układów wież na klasy; w klasie s są takie układy, w których s par wież nie stoi na przekątnej. Dokładnie w ten sam sposób można wykazać, że liczbę n -układów wież na planszy n × n , takich, które nie atakują się nawzajem i są symetryczne do obu przekątnych, wyznaczają równania powtarzalności B _{2 n} = 2 B _{2 n - 2} + (2 n - 2) B _{2 n - 4} i b. _{2 n + 1} = b. _{2 n} .

Układy liczone według klas symetrii

Innym rodzajem uogólnienia jest to, w którym układy wież uzyskane od siebie poprzez symetrie szachownicy są liczone jako jedno. Na przykład, jeśli obrót deski o 90 stopni jest dozwolony jako symetria, wówczas każdy układ uzyskany przez obrót o 90, 180 lub 270 stopni jest uważany za „taki sam” jak oryginalny wzór, nawet jeśli te układy są liczone osobno w pierwotnym problemie, w którym płyta jest naprawiona. W przypadku takich problemów Dudeney zauważa: „Nie ustalono jeszcze, ile jest sposobów, w których zwykłe odwrócenie i odbicia nie są liczone jako różne; jest to trudny problem”. Problem sprowadza się do liczenia układów symetrycznych przez Lemat Burnside’a .