Auf wie viele verschiedene Arten können wir N identische Türme auf einem Schachbrett OHNE ECKEN platzieren, sodass sich keine zwei von ihnen gegenseitig angreifen (für N > 3)?

Die erste Beobachtung ist, dass in jeder Reihe genau ein Turm steht. Lassen Sie uns also zählen, wie viele Möglichkeiten es gibt, Türme in der ersten und letzten Reihe zu platzieren. Es gibt$N-2$Felder zur Auswahl und sobald wir den ersten Turm gesetzt haben, wird genau eine Option für die Platzierung des zweiten Turms weggenommen, also gibt es$(N-2)(N-3)$Auswahlmöglichkeiten. Löschen Sie nun die Zeilen und Spalten, die diese Türme belegen, und wir müssen platzieren$N-2$Türme auf einem quadratischen Brett der Größe$N-2$. Es gibt$(N-2)!$Möglichkeiten, dies zu tun (begründen Sie dies, indem Sie Türme Reihe für Reihe platzieren). Insgesamt gibt es also$(N-2)(N-3)[(N-2)!]$Möglichkeiten, die Türme zu platzieren.

Bei N=8 ergibt dies 6*5*(6!) = 21600 Wege.

Lassen$A_{(x,y)}$sei die Anzahl der Platzierungen von$N$Türme auf einem$M\times M$Schachbrett mit einem Turm im Quadrat$(x,y)$dann wollen wir Turmstellungen zählen, die keiner von gehören$A_{(1,1)}$,$A_{(1,M)}$,$A_{(M,1)}$oder$A_{(M,M)}$damit wir es verwenden können$\xi$um die Menge aller Platzierungen von darzustellen$N$Türme auf unserem$M\times M$Brett dann

$$|\xi|= \binom{M}{N}^2N!$$

weil wir wählen$N$Reihen ab$M$in die wir unsere Türme setzen$\binom{M}{N}$dann treffen Sie eine geordnete Auswahl von$N$Spalten aus$M$In$\binom{M}{N}N!$Wege.

Als nächstes haben wir

$$|A_{(x,y)}|=\binom{M-1}{N-1}^2(N-1)!$$

mit dem gleichen Argument, nur dass wir dieses Mal einen Turm in die Zelle gesetzt haben$(x,y)$was geht$M-1$Zeilen und Spalten, in denen die restlichen platziert werden$N-1$Türme. Es gibt$4$solche Sets, eines für jede Ecke des$M\times M$Planke.

Dann haben wir

$$|A_{(x_1,y_1)}\cap A_{(x_2,y_2)}|=\begin{cases}& 0\qquad &x_1= x_2,\, \text{or}\, y_1= y_2\\& \dbinom{M-2}{N-2}^2(N-2)!\qquad &\text{else}\end{cases}$$

Da gibt es nur$2$Schnittpunkte ungleich Null$A_{(1,1)}\cap A_{(M,M)}$Und$A_{(1,M)}\cap A_{(M,1)}$und es kann keine geben$3$-Schnittpunkte haben wir dann nach dem Inklusions-Exklusions-Prinzip

$$\begin{align}\text{Desired count}&=|\xi|-(|A_{(1,1)}|+|A_{(1,M)}|+|A_{(M,1)}|+|A_{(M,M)}|) + (|A_{(1,1)}\cap A_{(M,M)}|+|A_{(1,M)}\cap A_{(M,1)}|)\\ &=\binom{M}{N}^2N!-4\binom{M-1}{N-1}^2(N-1)!+2\binom{M-2}{N-2}^2(N-2)!\end{align}$$

Nach Bedarf.

Es ist auch möglich, Turmpolynome dafür zu verwenden, ist aber vielleicht vielen unbekannt, daher der obige Ansatz.

Dieses Problem kann bequem mit Turmpolynomen gelöst werden . Wir können Zeilen und Spalten paarweise vertauschen, ohne die Anzahl der möglichen Anordnungen nicht angreifender Türme zu ändern. Eine äquivalente Platine ist unten gezeigt.

                                                                

Das Turmpolynom der vier verbotenen Felder in der oberen linken Ecke ist

$$\begin{align*} 1+4x+2x^2\tag{1} \end{align*}$$ wo der Koeffizient von$x^k$gibt die Anzahl der Platzierungsmöglichkeiten an$k$nicht angreifende Türme auf den verbotenen Feldern. Die Anzahl der gültigen Anordnungen, um acht nicht angreifende Türme auf dem Feld zu platzieren$(8\times 8)$Board Respektierung der verbotenen Quadrate ist durch (1) unter Verwendung des Inklusions-Exklusions-Prinzips als gegeben $$\begin{align*} 1\cdot 8!-4\cdot 7!+2\cdot 6!\color{blue}{=21\,600} \end{align*}$$ Wir können acht nicht angreifende Türme einsetzen$8!$Wege, subtrahieren$4\cdot7!$Möglichkeiten, mindestens einen Turm auf einem der vier verbotenen Felder zu haben und als Ausgleich für Doppelzählungen hinzuzufügen$2\cdot6!$Möglichkeiten, zwei nicht angreifende Türme auf den vier verbotenen Feldern zu haben.