Permutationen 

Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge. Sie gibt an, auf wie viele verschiedene Weisen eine gegebene Menge von Elementen geordnet werden kann.  

Eine Permutation ohne Wiederholung liegt vor, wenn alle Elemente der Reihenfolge paarweise verschieden sind.  Als Beispiel nimmt man 5 verschiedene Steine. Wenn man nun berechnen möchte, wie viele verschiedene Anordnungen man aus diesen 5 Steinen bilden kann, schaut man sich zunächst die erste Position an. Für die erste Position gibt es alle 5 Steine zur Auswahl. Danach hat man nur 4 für die zweite, da einer schon auf der ersten Position ist. Analog hat man 3 für die dritte und 2 für die vierte. Auf der fünften Position hat man den letzten Stein übrig. Multipliziert man alle diese Möglichkeiten für jeden Platz, bekommt man eine Antwort: 5! =120 Reihenfolgen. 

Diese Aufgabe kann man verallgemeinern, indem man n Steine anstatt 5 hat. Analog ist die Antwort n!  

Die Anzahl aller Permutationen ohne Wiederholung ist immer n!, wobei n die Anzahl der Elemente in der Reihenfolge ist. 

Im Vergleich zu dem letzten Beispiel hat man bei der Permutation mit Wiederholung Elemente, die gleich sind. Das heißt, dass man aus einem Beispiel mit verschiedenen Elementen alle Reihenfolgen weglassen sollte, die wegen einer Gleichheit der Elemente auch jetzt gleich sind. Man nimmt an, aus dem Beispiel mit den Steinen, man hat rote, schwarze, blaue, und 2 grüne, dann sind die Reihenfolgen: 

R, S, B, G1, G2 und R, S, B, G2, G1 genau gleich. Die Anzahl solcher wiederholten Reihenfolgen ist die Anzahl aller Permutationen der gleichen Elemente. Um dieses Problem zu lösen, berechnen wir erstmal alle Permutationen, und dann teilt man durch alle Permutationen der gleichen Elemente.  

Die Anzahl aller Permutationen mit Wiederholung ist immer $\frac{n!}{k!}$ , wobei n eine Anzahl der Elemente in der Reihenfolge ist und k die Anzahl der gleichen Elemente. 

Kombinationen 

Bei einer Kombination geht es um alle mögliche Auswahlen der k Elemente von n. Die Reihenfolge der ausgewählten Elemente ist dabei nicht wichtig.  

In der Kombination ohne Wiederholung kann man ein Element nur einmal zur Anordnung auswählen. Man nimmt an, man sollte aus 5 verschiedenen Steinen 2 auswählen. Für die Auswahl von dem ersten Stein hat man 5 Möglichkeiten und 4 für den zweiten. Da deren Reihenfolge nicht wichtig ist, sollte man durch die Anzahl aller Permutationen der ausgewählten Steine teilen. Dann ist die Antwort: $\frac{5\cdot 4}{2}=10$ Möglichkeiten 2 Steine aus 5 auszuwählen. 

Nimmt man an, man hat n Steine und sollte k auswählen dann gibt es n Möglichkeiten für den ersten, n-1 für den zweiten und so weiter, bis die Anzahl der Faktoren k erreicht. Das lässt sich wie folgt aufschreiben: $\frac{n!}{\left(n-k\right)!}$ . Aus der Regel der Fakultäten bekommt man somit im Zähler k Faktoren bei der Multiplikation. Am Ende sollte man durch die Anzahl aller k Permutationen teilen, da die Reihenfolge unwichtig ist. Dann gilt: 

Die Anzahl aller Kombinationen ohne Wiederholung ist immer $\frac{n!}{k!\cdot \left(n-k\right)!}$ , wobei n eine Anzahl der Elemente in der Menge ist und k die Anzahl der Elemente die zu auswählen sind. Diese Formel lässt sich kürzer als Binomialkoeffizient aufschreiben. Das wäre dann: $\binom{n}{k}$ (n über k)

Kombinationen mit Wiederholung sind dadurch gekennzeichnet, dass ein vorgegebenes Element in der Auswahl mehrmals auftreten kann. Es liegt eine “Auswahl mit Zurücklegen” vor. In diesem Fall kommen durch das Zurücklegen praktisch k-1 Elemente hinzu. Daher muss an Stelle des Binomialkoeffizienten “n über k” jetzt der Binomialkoeffizient “n+k-1 über k” berechnet werden: 

Die Anzahl aller Kombinationen mit Wiederholung ist immer $\binom{n+k-1}{k}=\frac{\left(n+k-1\right)!}{k!\cdot \left(n-1\right)!}$ , indem n eine Anzahl der Elemente in der Menge ist und k die Anzahl der Elemente die zu auswählen sind. Da die Elemente mehrmals auftreten können, muss man noch k-1 hinzufügen.

Variationen 

Eine Variation ist eine Kombination, bei der die Reihenfolge der ausgewählten Elemente auch wichtig ist. Das heißt, dass hier auch die Permutationen gebildet werden können. 

Bei einer Variation ohne Wiederholung kann man ein Element nur einmal zur Anordnung auswählen. Man nimmt an, man muss aus 5 verschiedenen Steinen 2 auswählen, von denen der erste verkauft und der andere verschenkt werden. Im Vergleich zum Beispiel mit Kombination, ist hier wichtig, welcher zu verkaufen und welcher zu verschenken ist. Das bedeutet, dass nach der Auswahl von den beiden die Anzahl der Permutationen auszurechnen ist. Das erste macht man mit einem normalen Binomialkoeffizienten $\binom{5}{2}$ , dann multipliziert man den mit der Anzahl der Permutationen 2!. Das kürzt sich dann mit einem Faktor im Nenner. 

Die Anzahl aller Variationen ohne Wiederholung ist immer $\frac{n!}{\left(n-k\right)!}$ , wobei n eine Anzahl der Elemente in der Menge ist und k die Anzahl der Elemente die zu auswählen sind. Die Reihenfolge der k Elemente ist hier berücksichtigt. 

Bei einer Variation mit Wiederholung kann man jedes Element mehrmals zur Anordnung auswählen. Man nimmt an, man hat unendlich viele Steinen der 5 Arten. Man soll 2 von ihnen auszuwählen, um sie zu verschenken und zu verkaufen. Dann hat man 5 Möglichkeiten für ersten Stein, aber auch 5 Möglichkeiten für den zweiten. Insgesamt sind das $5^2=25$ Möglichkeiten. Wenn man n Arten hat und k Steine für verschiedene Ziele braucht, somit gibt es $n^k$ Möglichkeiten.

Die Anzahl aller Variationen mit Wiederholung ist immer $n^k$, wobei n eine Anzahl der möglichen Elemente in der Menge ist und k die Anzahl der Elemente, die auszuwählen sind. Die Reihenfolge der k Elemente ist hier berücksichtigt. Dabei kann man gleiche Elemente auswählen. 

Permutation, Variation oder Kombination 

Die hier stehende Folge von Fragen hilft auf eine einfache Weise feststellen, ob man bei einer Aufgabe Permutation, Variation oder Kombination benutzt. 

1. Geht es um ein Anordnungsproblem einer Menge oder ein Auswahlsproblem 

• Anordnung -> Permutation -> Frage 2 

• Auswahl -> Variation oder Kombination -> Frage 3 

2. Sind alle Elemente der Reihenfolge unterschiedlich? 

• Ja -> Permutation ohne Wiederholung 

• Nein -> Permutation mit Wiederholung 

3. Braucht man nach der Auswahl die Anordnung zu berücksichtigen? 

• Ja -> Variation -> Frage 4 

• Nein -> Kombination -> Frage 5 

4. Kann ein Element mehrmals bei der Auswahl vorkommen? 

• Ja -> Variation mit Wiederholung 

• Nein -> Variation ohne Wiederholung 

5. Kann ein Element mehrmals bei der Auswahl vorkommen? 

• Ja -> Kombination mit Wiederholung 

• Nein -> Kombination ohne Wiederholung

Zusammenfassend wird das nochmal in Abbildung gezeigt:

(Universität Kassel. n.d.)

(Bourier, G. 2009)

(Doucet-Rosenstein, D. 1981)

Binomialkoeffizienten-Vertiefung. Es sei M eine Menge. Ist M endlich, so bezeichnen wir mit |M| die Anzahl der Elemente in M. Hat M die Länge n, so nennen wir M eine n-Menge. Mit P(M) bezeichnen wir die Menge aller Teilmengen von M, einschließlich der leeren Menge ∅ und M selbst. P(M) heißt die Potenzmenge von M. 

Ist M eine n-Menge, so ist |P(M)|=2ⁿ 

Über jedes Element von M kann man entscheiden, ob dieses bei einer Teilmenge dabei ist oder nicht. Solche Entscheidung bei der Auswahl allen Elementen führt zu allen entsprechenden Teilmengen. Daher ist |P(M)|=2ⁿ  

Ist X ∈ P(M) und ist |X| = k, so nennen wir X eine k-Teilmenge von M. Die Menge aller k-Teilmengen von M bezeichnen wir mit P_k(M). Ist M eine n-Menge, so setzen wir |P_k(M)|=$\ \binom{n}{k}$. Die Zahlen$\ \binom{n}{k}$heißen Binomialkoeffizienten. 

n und k seien nicht-negative ganzen Zahlen. Dann gilt: 

a) $\ \binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}$

b) $\binom{n}{k}=\binom{n}{n-k}$

c) $\binom{n}{0}=\binom{n}{n}=1\quad \mathrm{und}\quad \binom{n}{1}=\binom{n}{n-1}=n$

d) $\sum _{i=0}^n\binom{n}{i}=2^n$

e) $\binom{n}{k}\le \binom{n+1}{k}$

f) $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$

Alle Formeln lassen sich aus der Formel mit Fakultäten herausleiten (Lüneburg, H. 1971). 

Literaturverzeichnis 

• Universität Kassel. (n.d.). Dokument / Skript. Fachbereich 07 Wirtschaftswissenschaften. https://www.uni-kassel.de/fb07/index.php?eID=dumpFile&t=f&f=2915&token=5c343b5f2460dc1ce391f7766b0d01e7776bc73b 

• Lüneburg, H. (1971). Kombinatorik (Band 4). Birkhäuser. 

• Bourier, G. (2009). Wahrscheinlichkeitsrechnung und schließende Statistik: Praxisorientierte Einführung; mit Aufgaben und Lösungen (6. Aufl.). Gabler Verlag. 

• Doucet-Rosenstein, D. (1981). Die Kombinatorik als Methode der Wissenschaften bei Raimund Lull und G. W. Leibniz [Dissertation, Ludwig-Maximilians-Universität München]. 

Das Werwolf Spiel

Werwolf ist ein Spiel, bei dem die Spieler in Werwölfe und Dorfbewohner aufgeteilt werden. Die Werwölfe kennen sich gegenseitig und eliminieren nachts heimlich einen Dorfbewohner. Tagsüber diskutieren alle Spieler und stimmen darüber ab, wen sie für einen Dorfbewohner halten und aus dem Spiel wählen. Die Dorfbewohner gewinnen, wenn die gesamten Werwölfe ausgeschaltet sind; die Werwölfe gewinnen, sobald sie genauso viele oder mehr Spieler als die Dorfbewohner stellen. In der Regel haben verschiedene Dorfbewohner Sonderrollen, die es ihnen erlaubt Informationen über die Werwölfe zu sammeln oder das Spiel auf eine andere Art zu beeinflussen

Grundlegende Annahmen und Vereinfachungen

Um das Spiel einfacher mathematisch darzustellen, müssen wir einige Annahmen und Vereinfachungen machen. Nachts wählen die Werwölfe zufällig einen Dorfbewohner als Opfer aus, der in dieser Nacht ausscheidet. Am Tag wird per Zufall entschieden, wer nach der Abstimmungsphase ausscheidet. Die Werwölfe koordinieren sich nicht untereinander bei der Abstimmung. Gespielt wird, bis es gleich viele oder weniger Dorfbewohner als Werwölfe gibt oder alle Werwölfe ausgeschieden sind.

Funktionsweise des Programmes

Zu Beginn werden mehrere Packages importiert. Diese sind nötig, um zufällige Zahlen zu generieren oder die Ergebnisse in Diagrammform darzustellen. Die Genauigkeit gibt an, wie viele spiele pro Zustand (Anzahl von Werwölfen und Dorfbewohner) gespielt werden, um daraus später eine durchschnittliche Gewinnwahrscheinlichkeit zu berechnen.

Die darauffolgende Funktion berechnet aus zwei Eingabewerten (Anzahl der Spieler n und Anzahl der Werwölfe m) eine Gewinnwahrscheinlichkeit für die Werwölfe, den sie als Ausgabewert p ausgibt.

Der Folgende Graph gibt die Gewinnwahrscheinlichkeit für einen Werwolf bei variierender Spieleranzahl an. Dafür wird im Programm ein Höchstwert für die Spieleranzahl festgelegt und alle Situationen bis zum Höchstwert durch die oben erklärte Funktion berechnet. Im Diagramm dargestellt ergibt sich eine Funktion die näherungsweise durch 1/√x beschrieben werden kann. Um den Verlauf des Diagramms gleichmäßiger darzustellen, beschränken wir uns auf die Darstellung von geraden Spieleranzahl. Das geht darauf zurück, dass das Hinzufügen eines Dorfbewohners – also das Erhöhen der Spieleranzahl auf eine ungerade Menge – die Gewinnchance der Werwölfe erhöht. Die Gründe dafür sind mathematischer Natur (Migdał, 2010, S. 6–7).

Die Folgende Heatmap stellt die Gewinnwahrscheinlichkeit (Siegquote) der Werwölfe Abhängig vom Verhältnis von Werwölfen zu Spielern bis zu einer maximalen Spielerzahl (In diesem Fall ebenfalls 52) an. Das rote Dreieck in der oberen, linken Hälfte des Diagramms ist nicht definiert, da sonst die Anzahl der Werwölfe die Anzahl der Spieler übersteigen würde, was schlicht unmöglich ist. Ebenfalls ist die Gewinnwahrscheinlichkeit für die Werwölfe ab einem Verhältnis von 0,5 automatisch 100%. Interessant ist also nur der untere Teil, in dem die Gewinnwahrscheinlichkeit in etwas ausgeglichen ist.

Das Balkendiagramm vergleicht die Siegquote der Dorfbewohner mit der Spieleranzahl, wenn sich der Anteil der Wölfe an der Spieleranzahl aus der Wurzel der Spieleranzahl berechnet. Die Gewinnwahrscheinlichkeit der Werwölfe sinkt, solange mehr Dorfbewohner dazukommen. Das passiert so lange bis der Breaking Point erreicht ist und ein neuer Wolf dazukommt. Diese Mechanik liegt der logischen Annahme zugrunde keine nicht natürliche zahl an Wölfen hinzufügen zu können und ist für den stufenartigen Aufbau des Diagramms verantwortlich.

Letztendes sind diese Berechnungen und Modelle in ihrer Aussagekraft eingeschränkt und beruhen auf den Eingangs erwähnten Annahmen und Vereinfachungen. Die Diagramme dienen dazu, das grundlegende Prinzip zumindest annähernd zu beschreiben und nicht um Ereignisse im realen Leben akkurat vorherzusagen. Auch wenn diese Modelle die Realität nicht vollständig beschreiben, können sie Indizien oder Hinweise auf die Entscheidungsfindung im realen L eben liefern.

Literatur

Migdał, P. (2010). A mathematical model of the Mafia game, https://arxiv.org/pdf/1009.1031

Anhang (Code)

import matplotlib.pyplot as plt
import numpy as np
import random
from math import sqrt

genauigkeit = 50000
print("WERWOLFSIMULATION")
print("\n")

def simu(spieler: int, werwolf: int) -> float: 
    siege = 0
    for _ in range(genauigkeit):
        n = spieler 
        m = werwolf 

        while m > 0 and m <= n // 2:

            zufall = random.randint(1, n)
            if zufall <= m:
                m = m - 1  
            n = n - 1  

            if m >= n / 2:
                break  

            n = n - 1  
    
        if m > 0 and m >= n / 2:
            siege = siege + 1

    p = siege / genauigkeit
    return p




    
#maximaler wert von n
max: int = 52
#i ist spieler und g werwolf
array = [0.0 for _ in range(0, max - 1)]
for i in range(2,max,2):
        array[i-1] = simu(i, 1)
 
print("ein Werwolf:")
plt.figure(1)
plt.plot(range(2, max, 2), [array[x-1] for x in range(2, max, 2)])
plt.xlabel("Spieler*in")
plt.ylabel("Siegquote Werwölfe")
plt.show()

print("\n") #trennen

genauigkeit = 1000
array2 = [[0 for _ in range(0,10)] for _ in range(0,max-1)]
for i in range(1,max):
    for g in range(1,11):
        if i >= g:
            array2[i-1][g-1] = simu(i, g)

plt.figure(2)
plt.imshow(np.array(array2).T, cmap='Reds', origin='lower')
plt.ylabel("Werwölfe")
plt.xlabel("Spieler*in")
plt.colorbar(label='Siegquote Werwölfe')
plt.show()

print("\n") #trennen

genauigkeit = 50000
array3 = [0.0 for _ in range(0, max - 1)]
for i in range(2,max,2):
        array3[i-1] = 1-(simu(i, int(sqrt(i))))
    
print("Anzahl der Werwölfe = Wurzel aus Anzahl der Spielern:")
plt.figure(3)
plt.bar(range(2, max, 2), [array3[x-1] for x in range(2, max, 2)], width=1.2)
plt.xlabel("Spieler*in")
plt.ylabel("Siegquote Dorf")
plt.show()