Kombinatorik

KombinatorikIn diesem Unterprogramm können Sie Berechnungen zur Kombinatorik durchführen. Nach Festlegung der Anzahl N von Elementen einer Grundgesamtheit und der Anzahl K aus dieser Menge ausgewählter Elemente bestimmt das Programm die drei klassischen Arten kombinatorischer Operationen Permutationen, Variationen und Kombinationen.

n und k können im Intervall von 1 bis 99999 liegen und müssen ganzzahlig sein, wobei Sie beachten sollten, dass k stets kleiner gleich n sein muss.

Permutation, Variation, Kombination

Die Anzahl der Permutationen n! (n Fakultät) von n Elementen (Anzahl unterschiedlicher Reihenfolgen dieser Elemente) wird neben einer rein numerischen Berechnung auch mittels Stirlingscher Näherungsformel ermittelt.
Diese Näherungsgleichung ist für große n eine sehr gute Näherung des Wertes n!, was durch die Angabe der rozentualen Abweichung des tatsächlichen Wertes verdeutlicht wird. Für eine Eingabe von n ≤ 1000 wird die Ziffernfolge von n! exakt berechnet.
Beispiel: n = 56; n! = 710 998 587 804 863 451 854 045 647 463 724 949 736 497 978 881 168 458 687 447 040 000 000 000 000 bzw.
n = 99999; n! = 2.8241463805 * 10456568 (eine Zahl mit 456569 Stellen!!)

Unter einer Variation versteht man die Auswahl von k Elementen aus n Elementen, wobei die Anordnung der Elemente berücksichtigt wird. Zum einen fragt man nach Variationen ohne Wiederholungen, d.h., kein Element darf zweimal auftreten, zum anderen nach Variationen mit Wiederholungen von Elementen. Berechnet wird die Anzahl mit

  • Variation ohne Wiederholungen = \frac{n!}{(n-k)!}
  • Variation mit Wiederholungen = n^k

Für eine Eingabe von n <= 1000 werden die Variationen exakt berechnet.

Beispiel 1: n = 56, k = 14 ergibt für Variation ohne Wiederholung = 5.0604661348 * 1023 …, für Variation mit Wiederholung 2.9828566195 * 1024.

Beispiel 2: Die Blindenschrift besteht aus sechs Punkten, welche erhaben oder gelocht in Papier gedruckt werden. Mit den zwei variierenden Elementen „Buckel“ oder „Loch“ zur 6. Klasse mit Wiederholungen können auf diese Weise 26 = 64 verschiedene Zeichen dargestellt werden.

Eine Kombination ist eine Auswahl von k Elementen aus n Elementen ohne Berücksichtigung der Anordnung. Das Programm bestimmt deren Anzahl erneut, zum einen ohne Wiederholungen (nur verschiedene Elemente k), zum anderen mit Wiederholungen

  • Kombination ohne Wiederholungen = \frac{n!}{(n-k)!k!}
  • Kombination mit Wiederholungen = \frac{(n+k-1)!}{k!(n - 1)!}

Für eine Eingabe von n ≤ 1000 werden die Kombinationen exakt berechnet.

Beispiel: n = 56, k = 14 ergibt für eine Kombination ohne Wiederholung = 5 804 731 963 800, mit Wiederholung 1.5460300554 * 1014.

Eine Besonderheit stellt die Anzahl der Kombinationen ohne Wiederholung von Elementen dar. Dieser Wert entspricht dem in der Mathematik allgemein sehr wichtigen Binomialkoeffizienten (n k), der u.a. im Binomischen Satz oder im Pascalschen Dreieck auftritt. Der Wert des Binomialkoeffizienten wird hier bis etwa 1022 exakt angezeigt.

Permutationen mit Wiederholung

Treten in einer Menge von Elementen Gruppen gleicher Elemente auf, so ist die Anzahl der Permutationen kleiner als im Fall voneinander verschiedener Elemente. Geben Sie in die Eingabezeile Gruppen gleicher Elemente je Gruppe die Anzahl gleicher Elemente pi als Folge natürlicher Zahlen ein, ermittelt das Programm die Anzahl der Permutationen mit Wiederholungen von Elementen.

  • Permutation mit Wiederholungen = \frac{n!}{p_1! p_2! ... p_k!}

Die einzelnen Gruppen können dabei durch ein Leerzeichen, Komma usw. getrennt sein. Für eine Eingabe von n ≤ 200 werden diese Permutationen exakt berechnet.

Beispiel: Ein Skat-Kartenset enthält 32 Karten, das in Gruppen von 3 mal 10 Karten und 2 Karten für den „Skat“ ausgegeben wird. Da es gleichgültig ist, in welcher Reihenfolge ein Spieler seine Karten erhält (die Permutationen innerhalb der 10 Karten eines Spielers bedeuten dasselbe Spiel), ist die Anzahl aller möglichen Kartenverteilungen beim Skat eine Permutation von 32 Karten mit 10, 10, 10 und 2 gleichen Elementen.

Nach Eingabe von 10,10,10,2 in die Zeile Gruppen gleicher Elemente und 32 für n ermittelt das Programm 2.7532944082 * 1015 Kartenverteilungen. Schafft ein Spieler täglich 200 Spiele, so kann er in 100 Jahren jedoch nur 7,3 Millionen Möglichkeiten spielen.

Zu beachten ist, dass die Anzahl gleicher Elemente im Programm je Gruppe 32000 nicht überschreiten darf.

Permutationen mit Fixpunkt

Ist P eine Permutation von n Elementen {1,2, …, i, …, n}, so heißt jedes i aus dieser Menge Fixpunkt, wenn dieses Element innerhalb der Permutation an i-ter Stelle auftritt, d.h. zum Beispiel, dass sich bei der Permutation der Elemente 1, 2, 3 und 4 folgende Permutationen ergeben:

1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 (*) 1 4 2 3 (*)
1 4 3 2 2 1 3 4 2 3 1 4 (*) 2 4 3 1 (*) 3 1 2 4 (*)
3 2 1 4 3 2 4 1 (*) 4 1 3 2 (*) 4 2 1 3 (*) 4 2 3 1

Permutationen mit mindestens einem Fixpunkt sind (Anzahl 15). Bei den mit einem (*) markierten Permutationen gibt es jeweils genau einen Fixpunkt – im Beispiel acht. Das Programm ermittelt (bis n = 166) die Anzahl der Permutationen mit genau einem und mit mindestens einem Fixpunkt. Für eine Eingabe von n ≤ 120 werden diese Permutationen exakt berechnet.

Beispiel: Fünf Personen nehmen an einem Tisch Platz, ohne die aufgestellten Tischkarten zu beachten. Insgesamt gibt es 5! = 120 verschiedene Sitzanordnungen, darunter 76 mit mindestens einem Fixpunkt, d.h., mindestens eine Person sitzt auf dem richtigen Platz, sowie 45 mit genau einem Fixpunkt, d.h., genau eine Person sitzt richtig.

Beachten Sie bitte: Die Ermittlung von Permutation, Variation und Kombination erfordert bei großem n (n > 1000) etwas Zeit. Gedulden Sie sich bitte – ein Abbruch der Berechnung kann einige Sekunden verzögert sein.