Kombinatorik

Die Kombinatorik ist ein Teilgebiet der Stochastik.

Es werden drei verschiedene Abzählmethoden unterschieden:

– Permutation
Eine Anordnung von n unterscheidbaren Elementen in einer bestimmten Reihenfolge.

– Kombination
ungeordnete Stichprobe
Eine Auswahl von k Objekten aus einer Menge von n Objekten. Die Reihenfolge spielt keine Rolle.

– Variation
Eine Auswahl von Objekten aus einer Menge in einer bestimmten Reihenfolge.

Bei allen Abzählmethoden muss noch unterschieden werden, ob sie mit oder ohne Wiederholung ist.

Fragen zur Abzählmethode
– Werden alle n Elemente aus einer Menge mit n Ob- jekten genutzt, oder nur eine Auswahl k?
– Ist die Reihenfolge von Bedeutung oder nicht?
– Darf ein Element mehrfach vorkommen oder nicht?

Permutation mit Wiederholung

Die Anzahl der Kombinationsmöglichkeiten von 𝑛 Objekten, von denen 𝑘 Objekte identisch sind

𝑛! / 𝑘!

sind mehrere Objekte identisch, gilt:

𝑛! / (𝑘1!⋅𝑘2!...)

Wie bei der Permutation ohne Wiederholung werden hier alle n Elemente aus einer Menge von n Elementen betrachtet.

Bei der Permutation mit Wiederholung können gleiche Elemente mehrfach vorhanden sein*.

Eine Permutation mit Wiederholung ist also eine möglich Anordnung von n Elementen einer Menge n, die auch eine Anzahl von k identischen Elementen aufweist.

Eine Vertauschung der k identischen Elementen untereinander führt zu keiner neuen Permutation.

*nicht zu verwechseln mit einem Zurücklegen

Berechnet wird dies mittels Multinomialkoeffizienten

Die Fakultät aller vorhandenen Elemente n! wird durch das Produkt der Fakultäten der unterschiedlichen Elemente k! geteilt

Formel:

Beispiele

Triotones
Diese sind eigentlich vierteilig aufgebaut mit abwechselnd jeweils 2 Farben / Fadenführern pro Durchgang, eine der Farben kommt jedoch in jedem Durchgang vor.

Wenn die Farben bereits gewählt sind berechnet man mittels Multinomialkoeffizienten die möglichen Anordnungen dieser Farben.

n = 4
k = 2

4 x 3 x 2 x 1 = 24
geteilt durch 2 x 1
= 12

Überprüfen ob dies stimmt wenn man die Rückseite berücksichtigt

Das Beispiel bei der Permutation ohne Wiederholung, aber die Farbe Mauve kommt zweimal vor und Blau dafür nicht (oder vier Plätze)

3 x 2 x 1 / 2 x 1 = 3

Permutation ohne Wiederholungen

n!
genannt n Fakultät
n! = n × (n – 1) × (n – 2) × ... × 1

Anordnung von n Objekten, die alle unterscheidbar sind.

Für das erste Objekt gibt es n Platzierungsmöglichkeiten. Für das zweite Objekt nur noch n – 1 Möglichkeiten, für das dritte Objekt nur noch n – 2 und so weiter bis zum letzten Objekt, für das es nur noch eine Platzierungsmöglichkeit gibt.

Beispiele

Wikipedia:
4! = 4 × 3 × 2 × 1 = 24 mögliche Anordnungen von vier verschiedenfarbigen Kugeln in einer Reihe.

Beispiel Quadcolor Tartan.
Die Auswahl der vier Farben hat bereits stattgefunden. Wieviele Möglichkeiten gibt es, diese Farben auf das Muster zu verteilen?
(Das entspricht dem Beispiel oben mit den Kugeln.)

Bei einem dreifarbigen Jacquard gibt es nur 3 × 2 × 1 = 6 Möglichkeiten der Anordnung.
Wirklich unterscheiden tun sich die Varianten nur, wenn das Muster unregelmässig ist (ja?)

Beispiel:
Die Auswahl der Farben hat bereits stattgefunden. Wieviele mögliche Anordnungen gibt es in einem Muster?
Interessant bei Mustern, die nicht gleichmässig sind.

Beispiel unten z.B. Intarsia oder dreifarbiger Jacquard

3! = 3 × 2 × 1 = 6

Weiteres Beispiel:
Die möglichen Fadenführerfolgen beim Stricken mit drei (n) Systemen / Fadenführern:

3! = 3 × 2 × 1 = 6

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Kombination mit Wiederholung

Bei einer Kombination mit Wiederholung werden k aus n Objekten aus der Menge gewählt, wobei die Reihenfolge nicht beachtet wird. Objekte können dabei mehrfach ausgewählt werden.

Formel

(n + k – 1)!
––––––––––––
(n – 1)! × k!

Die einzelnen Teile erklärt:
(n + k – 1)!
Die n möglichen Kombinationen werden um k – 1 erhöht, da für den Fall k = 1 die Kombination mit und ohne Wiederholung keinen Unterschied ergibt.

(n – 1)!
Keine Berücksichtigung weiterer Kombinationen: Es wird ein Objekt entnommen, also befinden sich noch n – 1 Objekte in der Gesamtmenge, was allerdings für diesen Fall unwichtig ist

k!
Ohne Reihenfolge: Die Formel für die Kombination mit Wiederholung wird für k! um die Objekte reduziert, die zu einer unterschiedlichen Reihenfolge führen würden. Dabei werden also die Kombination von Farben wie Mauve / Wassermelone und Wassermelone / Mauve als eine Kombination gewertet

Beispiele:

k = Anzahl verwendete Farben
n = Anzahl zur Verfügung stehende Farben / Farbpalette

Mouliné und Solid Rib Tartan 3ply
wenn alle Möglichkeiten gezählt werden, die mit drei Fäden gestrickt werden
– alle drei Fäden in der gleichen Farbe (=n)
plus
– alle drei Fäden in unterschiedlicher Farbe (= Kombination ohne Wiederholung)
plus
– zwei gleichfarbige und ein unterschiedlicher Faden

Kombination ohne Wiederholungen

Wähle k Elemente aus n ohne Reihenfolge ohne Zurücklegen

Die Formel für eine Variation ohne Wiederholung ist:

   n!
–––––––
(n – k)!

Da bei der Kombination ohne Wiederholung die verschiedenen Anordnungen keine Rolle spielen, wird das Ergebnis nochmals durch k! geteilt:

   n!
–––––––––––
(n – k)! × k!

Dies nennt man auch Binomialkoeffizient und wird wie folgt geschrieben:

5 × 4 × 3 × 2 × 1       120

––––––––––––––––– =    –––––   =  10

  2 × 3 × 2 × 1   12

Beispiele

k = Anzahl verwendete Farben
n = Anzahl zur Verfügung stehende Farben / Farbpalette

Dreifarbiger Interlock

Schlauchjacquard (Vor- und Rückseite gleich, deshalb Position egal)

Hue Beanie Mouliné (zwei verschiedenfarbige Fäden)

Variation mit Wiederholung

Als Variation wird in der Kombinatorik eine geordnete Stichprobe für die Auswahl von Objekten in einer festen Reihenfolge bezeichnet.

Somit werden bei einer Variation mit Wiederholung k aus n Objekten unter Beachtung der Reihenfolge ausgewählt. Die Objekte können hierbei mehrmals ausgewählt werden.

1. Alle Elemente n aus der angegebenen Menge sind unterscheidbar. So haben Kugeln unterschiedliche Zahlen oder verschiedene Schülerinnen oder Schüler sind im Experiment gegeben.

2. k Elemente werden ausgewählt.

3. Die Reihenfolge ist entscheidend. Für eine vierstellige PIN ist unbedingt die Reihenfolge der Zahlen ausschlaggebend.

4. Elemente sind mehrfach wählbar. Deine PIN am Smartphone oder am Fahrradschloss darf 0000 heißen.

Wähle k Elemente aus n mit Reihenfolge mit Zurücklegen

Beispiel: Eine PIN mit vier Zahlen

Zur Berechnung von Aufgaben mit einer Variation mit Wiederholung benötigst Du die folgende Formel:

N hoch k

wobei n für die Anzahl der Ausgangsmenge steht und k für die ausgewählten Elemente

Erklären lässt sich dieser Zusammenhang wieder sehr anschaulich mit den Kugeln aus dem Urnenmodell. Überlege Dir dabei, welche Bedingungen gelten: Du möchtest aus n Objekten k auswählen, wobei die Reihenfolge wichtig ist und mit Wiederholung (also mit Zurücklegen).

Für das erste Objekt hast Du n Möglichkeiten. Da Objekte wieder mehrfach gewählt werden dürfen, bzw. Du Kugeln in die Urne zurücklegen darfst, hast Du für das zweite Objekt auch n Möglichkeiten und für das k-te Objekt ebenso.

Beispiel

?

Variation ohne Wiederholung

Im Vergleich zur Variation mit Wiederholung ist es hier für jedes nachfolgende Objekt nicht mehr möglich, ebenso n Elemente auszuwählen.

Wähle k Elemente aus n mit Reihenfolge ohne Zurücklegen

Als Variation ohne Wiederholung wird in der Kombinatorik eine Stichprobe genannt, bei der k aus n Objekten ausgewählt werden, wobei die Reihenfolge entscheidend ist und Objekte nur einmal gewählt werden dürfen.

Für die Berechnung ist also eine Angabe von k und n Objekten entscheidend. Wichtig ist, wie in der Definition erwähnt, dass nur eine Auswahl verwendet wird und nicht die komplette Menge an Objekten. Ansonsten würde es sich um eine Permutation handeln.

Formel:

  n!
–––––––
(n – k)!

Das bedeutet, dass für das erste Objekt, das gewählt wird, n Möglichkeiten bestehen. Wird das Objekt nicht mehr in die Auswahlmenge zurückgelegt, gibt es für den nächsten Schritt...

(n – 1)

Möglichkeiten. Das ist deshalb der Fall, weil keine Wiederholung stattfindet. Eine Farbe darf nur einmal vorkommen und steht nicht mehr zur Auswahl.

Das geht weiter bis

(n – k + 1)

da nicht die ganze Farbpalette betrachtet werden, sondern nur eine Auswahl, gilt

(n – 1) x (n – 2) ... x 1 = n!

Für die schlussendliche Formel werden also alle Möglichkeiten, verwendet, die es geben würde, wenn die gesamte Farbpalette verwendet würde und diese werden durch die tatsächliche Anzahl geteilt.

Beispiele

Quadcolor Tartan
Die Gesamtmenge an an Farbkombinationen und Anordnungen der Farben
n = Farbpalette
k = Anzahl Farben im Design, hier 4

Grids unter die Beispiele nehmen