Zum Abendessen kamen nnn Leute und setzten sich willkürlich an einen runden Tisch. Wenn Ana, Ivan und Mark unter ihnen wären, auf wie viele Arten könnten sie so sitzen ...

Methode 1: Sitzmarke. Wir werden ihn als unseren Bezugspunkt verwenden.

Nur Ana sitzt neben Mark : Sie kann auf zwei Arten sitzen, links oder rechts von ihm. Das geht$n - 2$Sitze. Da Ivan nicht neben Ana oder Mark sitzen kann, darf er hineinsitzen$n - 4$Wege. Der Rest$n - 3$Personen können in den restlichen sitzen$n - 3$Sitze drin$(n - 3)!$Weisen, während wir relativ zu Mark im Uhrzeigersinn um den Tisch herumgehen. Daher gibt es$2(n - 4)(n - 3)!$solche Anordnungen.

Nur Ivan sitzt neben Mark : Aus Symmetriegründen gibt es sie$2(n - 4)(n - 3)!$solche Anordnungen.

Sowohl Ana als auch Ivan sitzen neben Mark : Es gibt zwei Möglichkeiten, Ana zu setzen, links oder rechts von Mark. Ivan muss auf der anderen Seite von Mark sitzen. Der Rest$n - 3$Personen können in den verbleibenden sitzen$n - 3$Sitze drin$(n - 3)!$Weisen, während wir relativ zu Mark im Uhrzeigersinn um den Tisch herumgehen. Daher gibt es$2(n - 3)!$solche Sitzgelegenheiten.

Gesamt: Da sich die drei Fälle gegenseitig ausschließen und erschöpfend sind, beträgt die Anzahl der zulässigen Sitzanordnungen

$$\begin{align*} 2(n - 4)(n - 3)! + 2(n - 4)(n - 3)! + 2(n - 3)! & = [4(n - 4) + 2](n - 3)!\\ & = (4n - 14)(n - 3)! \end{align*}$$

Methode 2: Sitzmarkierung. Wir werden ihn als unseren Bezugspunkt verwenden.

Wählen Sie, ob Ana oder Ivan neben ihm sitzen. Wähle aus, auf welcher Seite von Mark diese Person sitzt. Setzen Sie die restlichen$n - 2$Menschen, während wir uns relativ zu Markus im Uhrzeigersinn um den Kreis bewegen. Das gibt

$$2 \cdot 2 \cdot (n - 2)! = 4(n - 2)!$$ Sitzordnungen.

Davon müssen wir jene Arrangements abziehen, in denen Ana und Ivan nebeneinander sitzen. Dazu müssen sie beide auf derselben Seite von Mark sitzen. Wähle aus, wer von ihnen neben Mark sitzt. Wähle aus, auf welcher Seite von Mark diese Person sitzt. Wenn diese Person Ana ist, gibt es nur eine Möglichkeit, Ivan neben sie zu setzen, da Mark auf ihrer anderen Seite ist. Wenn Ivan neben Mark sitzt, gibt es nur eine Möglichkeit, Ana neben Ivan zu setzen, da Mark auf seiner anderen Seite sitzt. Sobald diese drei Sitze besetzt sind, setzen Sie die restlichen$n - 3$Menschen im Rest$n - 3$Sitze, während wir im Uhrzeigersinn um den Tisch herumgehen. Es gibt

$$2 \cdot 2 \cdot (n - 3)! = 4(n - 3)!$$ solche Sitzgelegenheiten.

Wir müssen auch die Sitzordnungen abziehen, bei denen sowohl Ana als auch Ivan neben Mark sitzen, da wir sie bei unserer anfänglichen Zählung zweimal gezählt haben, einmal, als wir Ana als die Person benannt haben, die neben Mark sitzt, und einmal, als wir Ivan als die Person gezählt haben der neben Markus sitzt. Wie wir oben gezeigt haben, gibt es sie

$$2(n - 3)!$$ Sitzordnungen, bei denen sowohl Ana als auch Ivan neben Mark sitzen.

Daher ist die Anzahl der zulässigen Sitzanordnungen

$$4(n - 2)! - 4(n - 3)! - 2(n - 3)! = [4(n - 2) - 4 - 2](n - 3)! = (4n - 14)(n - 3)!$$

Betrachten Sie zunächst nur die Anordnungen von A, M und I.

Es gibt$2$Vorkehrungen, dass alle drei zusammen sein müssen, da M in der Mitte sein muss.

Es gibt$4(n-4)$Vorkehrungen, dass nur zwei zusammen sind, da wir einen von A und I auf der einen oder anderen Seite von M wählen und dann den dritten von ihnen auf eine von setzen$n-4$Sitze.

Wir haben daher$4n-14$Vorkehrungen für die genannten Personen und für jede dieser Vorkehrungen gibt es$(n-3)!$Arrangements der restlichen Gäste; insgesamt$(4n-14)(n-3)!$Anordnungen.

Die Arten von Möglichkeiten für Ana, Mark, Ivan und$n-3$leere Stühle können geschrieben werden als

1. $AMI-$
2. $IMA-$
3. $AM-I-$
4. $MA-I-$
5. $IM-A-$
6. $MI-A-$,

Wo$-$bezeichnet eine Reihe mit mindestens einem Stuhl. Jede Konfiguration entspricht$(n-3)!$Sitzplätze, Berücksichtigung der Platzierung der restlichen$n-3$Menschen auf Stühlen. 1. und 2. sind einzigartige Konfigurationen (die Stuhlreihe hat Länge$n-3$); die restlichen Artikel entsprechen$n-4$Konfigurationen jeweils, da die Länge der ersten Stuhlreihe sein kann$1,2,\ldots,n-4$. Die Summe ist also

$$(n-3)!\cdot(2 + 4\cdot(n-4)) = (4n-14)(n-3)!$$

Lassen$A$stellen die Anzahl der Sitzordnungen dar, wenn entweder Ana neben Mark oder Ivan neben Mark ist, aber nicht beides. Wenn$n \ge 5$es ist nicht schwer, das zu zeigen

$\tag 1 A = 4 (n-3) (n-4) \,(n-4)!$

Der Faktor von$4 = 2 \times 2$wird durch Verdoppeln für den Ana/Ivan-Austausch und den Links/Rechts-Austausch erhalten. Der Rest$n - 2$Faktoren ergeben sich aus der Anwendung der Produktregel, während die restlichen platziert werden$n - 2$Personen (die letzte sitzende Person entspricht einem Faktor von$1$). Aber$A = 0$Wenn$n = 4$und so$\text{(1)}$liefert auch die richtige Anzahl für$n \ge 4$.

Lassen$B$stellen die Anzahl der Sitzordnungen dar, wenn sowohl Ana als auch Ivan neben Mark stehen. Es ist nicht schwer, das zu zeigen

$\tag 2 B = 2 \,(n-3)!$

Der Faktor von$2$erhält man durch Verdoppelung für den Ana/Ivan-Austausch, der gleichzeitig auch den Links/Rechts-Austausch enthält. Wieder setzen wir jede der verbleibenden Personen, während wir die Produktregel anwenden.

Wir rechnen mit Algebra

$\tag 3 A + B = (4n - 14) \, (n - 3)!$

Vergleichen Sie die obige Technik mit der Methode 1 von NF Taussig (ein kleiner Unterschied).

Wir können die Antwort auch mit rekursiven Techniken finden.

Dieses Problem hat nur dann Lösungen, wenn$n \ge 4$. Für$n \ge 4$definieren

$\quad A(n) = \text{the number of solutions where Mark IS NOT next to BOTH Ana and Ivan.}$

$\quad B(n) = \text{the number of solutions where Mark ---IS---- next to BOTH Ana and Ivan.}$

Wir wollen die Summe finden$C(n) = A(n) + B(n)$.

Wir können darauf bestehen, dass unser Zählalgorithmus für die Sitzplätze ausgeführt wird, indem jeweils eine einzelne Person in die bestehende Vielzahl von Sitzanordnungen gesetzt wird, wenn sie "ankommt". Außerdem sind die ersten drei Personen, die ankommen, Mark, Ana und Ivan.

Also, wenn die vierte Person ankommt, haben wir

$\quad A(4) = 0 \text{ and } B(4) = 2$

Sitzordnungen.

Angenommen, wir haben eine Liste aller Sitzordnungen für$n$Leute, und jetzt müssen wir den nächsten setzen$(n+1)^{\text{th}}$Person. Unter Verwendung von kombinatorischen/Zählargumenten kann dies demonstriert werden

$\tag A A(n+1) = (n-1)A(n) + 4B(n)$

Und

$\tag B B(n+1) = (n-2) B(n)$

---

Eine lustige Sache bei kombinatorischen Problemen ist, dass sie oft auf verschiedene Arten gelöst werden können und Sie die Antwort dann bestätigen können, wenn die verschiedenen Lösungen das gleiche Ergebnis liefern. Der interessierte Leser kann folgendes bearbeiten:

Übung: Zeigen Sie mit Hilfe von Inductin, dass das hier besprochene rekursive Modell die gleichen Ergebnisse liefert wie die in dieser Antwort gefundenen Sitzordnungsmethoden .

---

Es ist auch möglich, ausgehend von diesem Rekursionsmodell die geschlossene Formelantwort abzuleiten – siehe hier .