TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 201

Aus VoWi
Wechseln zu: Navigation, Suche

Auf wieviele Arten können 8 Türme auf ein Schachbrett gestellt werden, derart, daß sie einander nicht schlagen und die weiße Diagonale freibleibt? (Ein Turm schlägt eine andere Figur, die horizontal oder vertikal auf gleicher Höhe steht, sofern keine andere Figur dazwischen steht.

Veranschaulichung (von mnemetz[Bearbeiten]

Ein Beispiel (weiße Hauptdiagonale unbesetzt!):

Bsp163 1.JPG

Lösungsvorschlag von der Lerngruppe vom 28.12.2005[Bearbeiten]

Wir überlegten uns zuerst, wieviele Möglichkeiten es überhaupt gibt, die 8 Türme zu platzieren, so dass sie einander nicht schlagen können. (Die Einschränkung mit der Diagonale lassen wir mal beiseite!)

Möglichkeiten im Durchgang der einzelnen Reihen von 1-8 - zuerst ein grafisches Beispiel bei besetzter erster Reihe:

Bsp163 2.JPG

  1. 8 Möglichkeiten zur Auswahl
  2. 7 Möglichkeiten zur Auswahl
  3. 6 Möglichkeiten zur Auswahl
  4. 5 Möglichkeiten zur Auswahl
  5. 4 Möglichkeiten zur Auswahl
  6. 3 Möglichkeiten zur Auswahl
  7. 2 Möglichkeiten zur Auswahl
  8. 1 Möglichkeit zur Auswahl

Es handelt sich hier um eine Variation ohne Wiederholung, und für diese gilt die Formel: \frac{n!}{(n-k)!}. Da aber n und k gleich 8 sind (8 Türme, 8 Reihen), liegt ein Spezialfall vor: die Permutation. Die Anzahl der Möglichkeiten, 8 Türme zu platzieren, beträgt somit 8! = 40320

Nun gilt aber als Erschwernis, dass die weiße Diagonale zusätzlich nicht von Türmen besetzt werden darf - ein Beispiel:

Bsp163 3.JPG

Es handel sich hier um eine sog. fixpunktfreie Permutation, auch Derangement bezeichnet. Dies ist eine Permutation bei der kein einziges Element an seinem Platz bleibt.

Die Anzahl der möglichen Derangements einer Menge mit n Elementen entspricht der Subfakultät !n: d_n = !n = n! \cdot \sum_{i=0}^n {\left(-1\right)^i \over i!}.

Somit lautet unsere Formel: n!*\sum_{i=0}^{n=8} \frac{-1^i}{i!}

Wir berechnen also:

n!*(1-1+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}-\frac{1}{7!}+\frac{1}{8!}) = 40320 * \approx 0.37 = 14833

Es gibt somit 14.833 Möglichkeiten, die 8 Türme so zu platzieren, dass sie einander nicht schlagen können sowie die weiße Hauptdiagonale nicht betreten.

Anhang 1: Subfakultät (von mnemetz)[Bearbeiten]

Die Subfakultät ist eine vornehmlich in dem mathematischen Gebiet der Kombinatorik auftretende Funktion. Die Subfakultät gibt die Anzahl der fixpunktfreien Permutationen (auch Derangements) auf einer endlichen Menge an. Sie ist eng mit der Fakultät verwandt, welche die Gesamtzahl der Permutationen auf einer endlichen Menge angibt.

formale Definition[Bearbeiten]

Sei n\in\mathbb{N}_0 und M:=\{1,2,\ldots,n\}. Eine Abbildung \phi:M\rightarrow M heißt fixpunktfrei, wenn für alle m\in M die Beziehung \phi(m)\neq m gilt. Die Subfakultät von n ist definiert als

!n := |\{\phi:M\rightarrow M\mid\phi\mbox{ bijektiv und fixpunktfrei}\}|

Eine Formel für !n[Bearbeiten]

Die Subfakultät kann mit Hilfe der Fakultät explizit berechnet werden. Es gilt:

!n = n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+ ... +(-1)^n\frac{1}{n!}\right) = n!\sum_{k=0}^n\frac{(-1)^k}{k!}

Die ersten 11 Werte der Subfakultät sind !0 = 1, !1 = 0, !2 = 1, !3 = 2, !4 = 9, !5 = 44, !6 = 265, !7 = 1 854, !8 = 14.833, !9 = 133.496 und !10 = 1 334.961

Beispiel einer Anwendung[Bearbeiten]

Angenommen man hat 6 verschiedenfarbige Kugeln, und zu jeder Kugel ein Kästchen in der passenden Farbe. Zu bestimmen ist die Anzahl der Möglichkeiten, die Kugeln so auf die Kästchen zu verteilen, dass jedes Kästchen genau eine Kugel enthält, aber keine Kugel in einem gleichfarbigen Kästchen zu liegen kommt.

Nach der Definition der Subfakultät gibt es genau !6 Möglichkeiten. Mit Hilfe der obigen Formel berechnet man !6 = 6!\cdot\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}\right) = 265.

Anhang 2: Schachtürme und Mathematik (von mnemetz)[Bearbeiten]

Siehe PDF-Dokument (1,1MB) - einige Seiten aus J. Gik, Schach und Mathematik, Sportverlag Berlin 1986