Grundbegriffe der Wahrscheinlichkeitsrechnung: Begriffsbildungen der Kombinatorik

Nachdem im letzten Kapitel Beispiele für einfache Abzählprobleme vorgestellt wurden, werden jetzt die Grundbegriffe der Kombinatorik, nämlich Variation, Permutation und Kombination eingeführt, systematisch untersucht und an weiteren einfachen Beispielen erläutert.

walter
Variation Abzählprobleme Kombination Binomialkoeffizient Fakultät fallende Faktorielle Permutation steigende Faktorielle Wahrscheinlichkeitsrechnung Kombinatorik
Inhaltsverzeichnis

Einordnung des Artikels

Einführung

In Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme wurde zwar die Vorgehensweise der Kombinatorik vorgestellt – also die Methoden, wie man an Abzählprobleme herangeht und löst –, es wurde aber noch nicht versucht systematisch die Begriffe einzuführen, die sich in der Kombinatorik etabliert haben, um die Abzählprobleme besser zu beschreiben und klassifizieren. Dies wird jetzt nachgeholt.

Mathematische Kenntnisse, die über die Anwendung der Formeln aus Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme hinausgehen, sind hier nicht nötig.

Fakultät, fallende und steigende Faktorielle und Binomialkoeffizient

Im Kapitel Grundbegriffe der Wahrscheinlichkeitsrechnung: einfache Abzählprobleme wurden bereits die Fakultät, die fallende Faktorielle und der Binomialkoeffizient eingeführt. Die Formeln sind in Abbildung 1 in Gleichung (1, 2, 4) nochmals gezeigt. Zusätzlich wird die steigende Faktorielle Q(n, k) definiert, siehe Gleichung (3). Bei der steigenden Faktoriellen werden beginnend mit n insgesamt k Faktoren, also n, n + 1, ..., n + k - 1 miteinander multipliziert; das Ergebnis kann dann auch als Quotient zweier Fakultäten geschrieben werden.

Eine Übersicht über die wichtigsten Abzählprobleme und die dazu benötigten Formeln zeigt die Tabelle in Abbildung 1; die Begriffe und Formeln werden in den folgenden Abschnitten erklärt.

Abbildung 1: Formeln zur Kombinatorik und Übersicht über einfache Abzählprobleme.Abbildung 1: Formeln zur Kombinatorik und Übersicht über einfache Abzählprobleme.

Klassifizierung der Abzählprobleme

Methodischer Hinweis

Die Formeln aus der Tabelle in Abbildung 1 finden sich zusammen mit den dort verwendeten Begriffen so – oder so ähnlich – in jeder mathematischen Formelsammlung und jedem Lehrbuch der Wahrscheinlichkeitsrechnung oder Kombinatorik.

Wer zunächst diese Begriffe kennenlernen möchte, sollte dieses Kapitel in der gegebenen Anordnung durcharbeiten.

Wer dagegen die Vorgehensweise der Kombinatorik verstehen und auf schwierigere Fragestellungen übertragen möchte, sollte sich nicht damit begnügen, die Begriffe zu kennen und zu wissen, wo man die entsprechenden Formeln nachschlagen kann.

Entscheidend ist vielmehr die Fähigkeit, aus einer Problemstellung heraus selbständig diese Formeln zu entwickeln. Dazu werden unten Beispiele angegeben, in denen die Formeln angewendet werden können. Wer seine Fähigkeiten testen möchte, sollte:

Variation, Permutation und Kombination

Gerade die Begriffe Variation und Kombination werden in der Umgangssprache mit einer sehr unscharfen Bedeutung verwendet; in der Kombinatorik werden sie – wie auch die Permutation – als scharf definierte Begriffe eingeführt. Diese Definitionen sollen hier angegeben werden. Dazu geht man stets von einer Menge M mit n Elementen aus, die der Einfachheit halber mit den Zahlen 1, 2, ..., n durchnumeriert werden. Es spielt daher keine Rolle, ob man die Elemente oder ihre Nummer angibt; so steht etwa (1, 2, 3) für die ersten drei Elemente der Menge M. Eine n-elementige Menge wird dann kurz als n-Menge bezeichnet.

Variation ohne Wiederholungen von k Elementen aus einer n-Menge

Aus einer n-Menge werden nacheinander k Elemente ausgewählt, wobei die Reihenfolge der Auswahl festgehalten wird und jedes Element der n-Menge nur einmal vorkommen kann. Man sagt jetzt auch ohne Zurücklegen, da man sich vorstellt, zur Auswahl eine von n Kugeln aus einer Urne zu ziehen und die Kugel anschließend nicht wieder in die Urne zurückzulegen, so dass sie beim nächsten Zug nicht mehr gewählt werden kann..

Da man höchstens n Elemente auswählen kann, muss man k ≤ n voraussetzen.

Für sie erste Stelle gibt es noch n Möglichkeiten, für die zweite n - 1 Möglichkeiten und so weiter. Für die k-te Stelle verbleiben n - k + 1 Möglichkeiten. Diese werden miteinander multipliziert und man erhält insgesamt P(n, k) Möglichkeiten.

Variation mit Wiederholungen von k Elementen aus einer n-Menge

Aus einer n-Menge werden nacheinander k Elemente ausgewählt, wobei die Reihenfolge der Auswahl festgehalten wird und jedes Element der n-Menge beliebig oft vorkommen kann. Dass ein Element beliebig oft vorkommen kann, wird auch durch den Ausdruck mit Zurücklegen beschrieben, da man zur Auswahl eine von n Kugeln aus einer Urne zieht und die Kugel anschließend wieder in die Urne legt, so dass sie auch beim nächsten Zug gewählt werden kann.

Die Anzahl der Variationen mit Wiederholungen von k Elementen aus einer n-Menge beträgt nk (siehe Tabelle in Abbildung 1). Der Grund ist einfach: Da man jede Stelle mit n Elementen besetzen kann (Wiederholungen sind möglich) und insgesamt k Stellen zu besetzen sind, wird n k-mal mit sich selbst multipliziert. Man zählt dabei auch keine Möglichkeit doppelt, da die Reihenfolge der Auswahl relevant ist – die Elemente werden nicht nachträglich umgeordnet (etwa der Größe nach sortiert oder Ähnliches).

Permutationen ohne Wiederholungen

Wenn nur von einer Permutation die Rede ist, ist damit meist die Permutation ohne Wiederholungen gemeint.

Bei einer Permutation werden alle Elemente einer n-Menge in einer beliebigen Reihenfolge angeordnet, so dass wieder eine Folge von n Elementen entsteht.

Da man für die erste Stelle n Möglichkeiten zur Auswahl hat, für die zweite Stelle n - 1 Möglichkeiten, und so weiter, ergeben sich n! Möglichkeiten, wie die n Elemente angeordnet werden können.

Permutationen mit Wiederholungen

Lassen sich die n Elemente in k Gruppen mit folgenden Eigenschaften einteilen:

und bildet man jetzt eine neue Anordnung der n Elemente, dann spricht man von einer Permutation mit Wiederholungen.

Da die Elemente der Gruppen nicht unterscheidbar sind, lassen sich für jede Gruppe ni! Anordnungen finden, die man bei unterscheidbaren Objekten zählen müsste, die jetzt aber zu einer Anordnung zusammenfallen. Um die Anzahl aller Permutationen mit Wiederholungen zu berechnen, muss also n! durch die Anzahlen der Anordnungen innerhalb der Gruppen geteilt werden; man erhält den Ausdruck aus der Tabelle in Abbildung 1 (zu Permutation mit Wiederholungen).

Kombinationen ohne Wiederholungen

Bei einer Kombination ohne Wiederholungen werden aus einer n-Menge nacheinander k Elemente ausgewählt, so dass in der Auswahl kein Element mehrfach vorkommen kann; es muss also k ≤ n gelten. Allerdings werden die Elemente anschließend sortiert, so dass nicht mehr erkennbar ist, in welcher Reihenfolge sie ausgewählt wurden.

Ohne die Sortierung hätte man P(n, k) Möglichkeiten für die Auswahl der k Elemente (n Möglichkeiten für das erste Element, n - 1 Möglichkeiten für das zweite Element und so weiter), wegen der anschließenden Sortierung muss diese Anzahl durch k! geteilt werden (k! Permutationen der k Elemente sind nicht unterscheidbar) und man erhält den Binomialkoeffizient (siehe Tabelle in Abbildung 1).

Das vermutlich bekannteste Beispiel von Kombinationen ohne Wiederholungen sind die Lottozahlen: Wer einen Lottoschein bei "6 aus 49" ausfüllt, muss 6 Zahlen ankreuzen. Bei der Ziehung fallen die Kugeln in einer gewissen Reihenfolge aus der Trommel; diese Reihenfolge muss man aber nicht vorhersagen. Denn die Kugeln werden anschließend aufsteigend sortiert und "6 Richtige" bedeutet, dass man die 6 Zahlen – nicht die Reihenfolge, in der sie gezogen wurden – vorhergesagt hat. Somit fallen 6! mögliche Ziehungen zu einem Ergebnis der Lotto-Ziehung zusammen.

Kombinationen mit Wiederholungen

Bei einer Kombination mit Wiederholungen werden aus der n-Menge nacheinander k Elemente ausgewählt, wobei jedes Element beliebig oft vorkommen kann (Ziehung mit Zurücklegen). Die anschließende Sortierung erfolgt wie bei der Kombination ohne Wiederholungen. Es gibt keine Einschränkung, welche der Zahlen k oder n größer sein muss.

Die Begründung, warum die Formel aus der Tabelle diese Ziehung richtig beschreibt, ist nicht einfach und wird in einem eigenen Kapitel nachgeholt, siehe Spezielle Abzählprobleme: Kombinationen mit Wiederholungen und die Beweismethode Stars and Bars.

Unterscheidungskriterien

In der Tabelle in Abbildung 1 sind die 6 grundlegenden Abzählprobleme dargestellt; wichtiger als ihre Namen zu kennen, ist es, sich die Kriterien klarzumachen, wie sie unterschieden werden und wie sich dies auf die Vorgehensweise beim Abzählen auswirkt. Die Unterscheidungskriterien sollen nochmals ausdrücklich genannt werden.

"Ohne Wiederholungen" oder "mit Wiederholungen"

Die Abzählprobleme wurden stets so beschrieben, dass k Elemente aus einer Menge mit n Elementen ausgewählt werden. Dabei muss festgelegt werden, ob

Alle Abzählprobleme können in beiden Varianten realisiert werden, allerdings muss sich dies dann im Zusammenhang zwischen k und n ausdrücken:

Realisiert wird eine Auswahl etwa durch das k-fache Ziehen einer Kugel aus einer Urne; die beiden Möglichkeiten ohne Wiederholungen und mit Wiederholungen entsprechen dann ohne Zurücklegen und mit Zurücklegen der jeweils gezogenen Kugel.

Reihenfolge

Die besprochenen Auswahlen unterscheiden sich darin, ob die Reihenfolge, in der die Auswahl getroffen wurde, später berücksichtigt wird (mit Reihenfolge) oder nicht (ohne Reihenfolge).

Im ersten Fall werden die Ergebnisse wie ein Vektor (oder Tupel) behandelt; durch Vertauschen seiner Komponenten entsteht ein neuer Vektor. Im zweiten Fall werden die Ergebnisse wie eine Menge behandelt, deren Elemente üblicherweise sortiert angegeben werden; durch die Angabe der Menge ist dann nicht mehr erkennbar, in welcher Reihenfolge die Elemente gezogen wurden.

Welche Auswahl berücksichtigt die Reihenfolge und welche nicht?

Beispiele

Bezeichnungen

Die Bezeichnungen aus der Tabelle in Abbildung 1 sind für den Neuling vermutlich eher verwirrend und dem Verständnis nicht förderlich. Daher sollen jetzt Zufallsexperimente vorgestellt werden, in denen die 6 Formeln aus der Tabelle tatsächlich vorkommen.

Es wird eine Tombola in 6 verschiedenen Variationen (hier wird der Begriff umgangssprachlich verwendet) vorgestellt, für die eine Liste der Gewinner erstellt wird. Die Anzahl der möglichen Listen wird durch die Formeln der Tabelle berechnet. Die unten folgenden 6 Abbildungen sollen die Regeln zur Durchführung der Tombola symbolisieren und werden sofort näher erklärt.

An der Tombola nehmen n Personen teil; in den Abbildungen ist stets n = 8 gewählt. Es gibt k Preise zu gewinnen; wie man sieht, ist die Anzahl der Preise unterschiedlich – dies wird noch näher erklärt.

Für jeden Teilnehmer wird eine Kugel in eine Urne gelegt, die seinen Namen trägt (oder eine Nummer, die den Teilnehmer eindeutig identifiziert). In den Abbildungen sind dies die roten Kugeln in den blauen Urnen.

Auf der jeweils linken Seite der Abbildungen ist die Urne im Anfangszustand gezeigt sowie eine vorbereitete Liste, in die dann die Gewinner eingetragen werden. Auf der rechten Seite ist jeweils der Zustand gezeigt, nachdem 3 Kugeln gezogen wurden. Man erkennt, dass bei einigen Abbildungen nur noch 5 Kugeln in der Urne sind: Dies sind die Ziehungen ohne Zurücklegen. Hier kann jeder Teilnehmer nur einen Preis (oder keinen Preis) gewinnen. Bei anderen Abbildungen sind immer noch 8 Kugeln in der Urne: Dies sind die Ziehungen mit Zurücklegen. Hier kann ein Teilnehmer beliebig oft gewinnen – eventuell kann ein Teilnehmer alle Preise gewinnen.

Abbildung 2: Variationen ohne Wiederholungen.Abbildung 2: Variationen ohne Wiederholungen.

Abbildung 3: Variationen mit Wiederholungen.Abbildung 3: Variationen mit Wiederholungen.

Abbildung 4: Permutationen ohne Wiederholungen.Abbildung 4: Permutationen ohne Wiederholungen.

Abbildung 5: Permutationen mit Wiederholungen.Abbildung 5: Permutationen mit Wiederholungen.

Abbildung 6: Kombinationen ohne Wiederholungen.Abbildung 6: Kombinationen ohne Wiederholungen.

Abbildung 7: Kombinationen mit Wiederholungen.Abbildung 7: Kombinationen mit Wiederholungen.

Komplizierter sind die vorbereiteten Listen, in die die Gewinner eingetragen werden. Denn es sind mehrere Szenarien möglich:

Unterscheidbare Preise sind in den Abbildungen durch Listen angedeutet, die von oben nach unten aufgefüllt werden (es wird etwa zuerst der Hauptpreis, dann der zweite Preis und so weiter gezogen, etwa in Abbildung 3). Gleiche Preise sind durch Listen angedeutet, die von links nach rechts aufgefüllt werden (etwa in Abbildung 6). In Abbildung 5 ist eine Liste zu sehen, in der die Preise in 3 Gruppen eingeteilt wurden (zwei Gruppen mit je zwei gleichen Preisen, eine Gruppe mit 4 gleichen Preisen).

Werden gleiche Preise vergeben, so werden die gezogenen Gewinner nicht sofort in die Liste eingetragen, sondern alle Gewinner des gleichen Preises werden zuerst alphabetisch sortiert und dann eingetragen – dies soll ausdrücken, dass die Preise nicht unterscheidbar sind.

Auf der rechten Seite ist dann zu sehen, wie die Listen mit den ersten 3 Gewinnern aufgefüllt wurden (immer beginnend mit dem wertvollsten Preis und so weiter).

Je nach Variation der Tombola kann es Einschränkungen an die Anzahl der Preise geben:

Nun endlich zu den verschiedenen Tombolas.

Variationen ohne Wiederholungen

Es nehmen n Personen an der Tombola teil, da aber kein Teilnehmer mehr als einen Preis erhalten kann, gibt es maximal n Preise, die alle unterschiedlich sind. Realisiert wird die Ziehung, indem eine gezogene Kugel nicht zurückgelegt wird. Die Preise werden gemäß ihrem Wert der Reihe nach gezogen (Hauptpreis zuerst und so weiter) und die Gewinner werden sofort in die Liste eingetragen.

Da für den Hauptpreis n Personen zur Auswahl stehen, für den zweiten Preis n - 1 Personen und so weiter, gibt es bei k Preisen P(n, k) verschiedene Möglichkeiten, wie die Liste der Gewinner ausgefüllt werden kann. Zur Veranschaulichung siehe Abbildung 2.

Variationen mit Wiederholungen

Jetzt nehmen wieder n Personen an einer Tombola teil, bei der es k unterschiedliche Preise zu gewinnen gibt. Die Preise werden der Reihe nach gezogen (Hauptpreis zuerst und so weiter) und der Name des Gewinners wird in die Liste eingetragen. Das Ziehen der Kugeln aus der Urne erfolgt mit Zurücklegen, das heißt jeder Gewinner hat weitere Gewinnchancen solange noch Preise zu vergeben sind. Die Anzahl der Preise kann kleiner oder gleich oder auch größer sein als die Anzahl der Teilnehmer.

Für die Anzahl der möglichen Preis-Listen, die bei dieser Durchführung der Tombola gebildet werden können, beträgt nk; zur Veranschaulichung siehe Abbildung 3.

Permutationen ohne Wiederholungen

Die Anzahl der Teilnehmer stimmt mit der Anzahl der Preise überein; die Kugeln werden ohne Zurücklegen gezogen.

Für den Hauptpreis gibt es n Möglichkeiten, für den zweiten Preis n - 1 Möglichkeiten und so weiter; insgesamt gibt es n! verschiedene Gewinner-Listen, siehe Abbildung 4.

Permutationen mit Wiederholungen

Es gibt insgesamt n Preise, innerhalb derer k Gruppen gebildet werden können; die Preise einer Gruppe sind ununterscheidbar. Es wird ohne Zurücklegen gezogen, so dass jeder Teilnehmer genau einen Preis erhält.

Die Gewinner der Preise einer Gruppe werden alphabetisch sortiert notiert, so dass deren Vertauschungen bei der Berechnung der möglichen Gewinner-Listen nicht berücksichtigt werden muss.

Besteht eine Gruppe von gleichen Preisen aus ni Objekten, so sind ni Reihenfolgen, in denen die entsprechenden Gewinner gezogen werden ununterscheidbar.

Ohne die Zusatzbedingung der Gruppen von Preisen gäbe es n! mögliche Gewinner-Listen, mit der Einschränkung muss durch n1 · ... · nk geteilt werden; es entsteht die Formel aus der Tabelle in Abbildung 1 zu Permutation mit Wiederholungen, siehe auch Abbildung 5.

Kombinationen ohne Wiederholungen

Auch jetzt sind alle k Preise gleichwertig und somit ununterscheidbar. Aber jetzt kann jeder Teilnehmer nur einen Preis erhalten (Ziehen ohne Zurücklegen), so dass k kleiner oder gleich n sein muss.

Die Anzahl der möglichen Gewinner-Listen erhält man aus der fallenden Faktoriellen (wie bei den Variationen ohne Wiederholungen), man muss aber zusätzlich durch k! teilen, da die Preise ununterscheidbar sind und erhält somit den Binomialkoeffizienten. Zur Veranschaulichung siehe Abbildung 6.

Kombinationen mit Wiederholungen

Es gibt k Preise, die alle gleichwertig sind. Jeder der n Teilnehmer kann beliebig viele Preise erhalten, was wieder durch Ziehen mit Zurücklegen realisiert wird. Wie bei den Variationen mit Wiederholungen gibt es daher keine Einschränkung an k. Die Gewinner-Liste wird erst ausgefüllt, wenn alle Gewinner gezogen sind und sie wird wieder alphabetisch sortiert erstellt. Da jetzt nicht klar ist, wie oft ein Gewinner in der Liste erscheint, ist es gar nicht so einfach abzuzählen, wie viele mögliche Gewinner-Listen es geben kann. Die Berechnung erfolgt später, die Veranschaulichung der Ziehung ist in Abbildung 7.

R-Skripte

Berechnung der Anzahl der Kombinationen

Unter ?Special im Paket base findet man die Funktionen

factorial(x)
choose(n, k)

zur Berechnung der Fakultät von x und des Binomialkoeffizienten "n über k".

Die folgenden Skripte zeigen kleine Anwendungen, die sich selbst erklären:

n <- 0
while(n < 20){
  cat(n, "! = ", factorial(x = n), "\n")
  n <- n + 1
}
# 0 ! =  1 
# 1 ! =  1 
# 2 ! =  2 
# 3 ! =  6 
# 4 ! =  24 
# 5 ! =  120 
# 6 ! =  720 
# 7 ! =  5040 
# 8 ! =  40320 
# 9 ! =  362880 
# 10 ! =  3628800 
# 11 ! =  39916800 
# 12 ! =  479001600 
# 13 ! =  6227020800 
# 14 ! =  87178291200 
# 15 ! =  1.307674e+12 
# 16 ! =  2.092279e+13 
# 17 ! =  3.556874e+14 
# 18 ! =  6.402374e+15 
# 19 ! =  1.216451e+17

Man sieht, dass die Fakultäten sehr schnell wachsen (ungefähr exponentiell) und dass selbst für kleine Eingaben von n das Ergebnis nicht mehr als ganze Zahl geschrieben werden kann, so dass die letzten Ziffern nicht mehr erkennbar sind.

choose(n = 49, k = 6)
# [1] 13983816

for(i in (0:10)){
  bn <- choose(n = 10, k = i)
  cat(i, "aus 10: ", bn, "\n")
}
# 0 aus 10:  1 
# 1 aus 10:  10 
# 2 aus 10:  45 
# 3 aus 10:  120 
# 4 aus 10:  210 
# 5 aus 10:  252 
# 6 aus 10:  210 
# 7 aus 10:  120 
# 8 aus 10:  45 
# 9 aus 10:  10 
# 10 aus 10:  1

In Zeile 1 wird berechnet, wie viele Möglichkeiten es gibt, einen Lottoschein bei "6 aus 49" auszufüllen.

Ab Zeile 4 wird eine Zeile des Pascalschen Dreiecks berechnet, nämlich alle Binomialkoeffizienten zu n = 10.

Ausgabe sämtlicher Teilmengen einer Menge

Einfache Verwendung der Funktion combn()

Nach den Ausführungen im Theorieteil ist es eine naheliegende Frage, zu einer gegebenen Menge alle Teilmengen einer gegebenen Mächtigkeit auszugeben. Der Algorithmus dazu ist sehr aufwendig und soll hier nicht besprochen werden.

Im Paket utils gibt es die Funktion combn(x, m) , die genau diese Aufgabe erledigt. Das folgende Skript zeigt die einfachste Verwendung von combn():

c.4.2 <- combn(x = 4, m = 2)

str(c.4.2)
# int [1:2, 1:6] 1 2 1 3 1 4 2 3 2 4 ...

c.4.2
# [,1] [,2] [,3] [,4] [,5] [,6]
# [1,]    1    1    1    2    2    3
# [2,]    2    3    4    3    4    4

Zur Erklärung:

Zeile 1:

Die Funktion combn() wird mit x = 4 aufgerufen. Eigentlich steht x für die Menge, von der die Teilmengen ausgewählt werden sollen, wobei x als Vektor eingegeben wird. Gibt man statt eines Vektors wie hier eine Zahl ein, so wird der Vektor seq_len(x) , also (1:x) gebildet.

Das Argument m = 2 besagt, dass alle Teilmengen mit 2 Elementen gebildet werden –, man sagt auch, dass m Elemente gleichzeitig ausgewählt werden.

Die durch combn() gebildeten Teilmengen werden in c.4.2 abgespeichert – vorerst ist noch nicht klar, welchen Datentyp dieses Objekt hat.

Zeile 3 und 4:

Es wird die Struktur von c.4.2 ausgegeben; man erkennt, dass es sich um eine Matrix mit 2 Zeilen und 6 Spalten handelt.

Da zwei-elementige Teilmengen gebildet wurden und "2 aus 4" gerade 6 ergibt, ist die Bedeutung der Zeilen und Spalten klar.

Zeile 6 bis 9:

Die Ausgabe von c.4.2 zeigt:

Bei der Verwendung der Funktion combn() muss auf eine Spitzfindigkeit hingewiesen werden, deren Nicht-Beachtung leicht zu unerwarteten Ergebnissen führen kann: Mathematisch gesehen wird eine Auswahl, die bei einer Kombination getroffen wird, wie eine Teilmenge behandelt. Aber was macht die Funktion combn(), wenn die Auswahl aus x = c(1, 2, 3, 1) getroffen werden soll? Ist insbesondere die Auswahl (1, 1) möglich, wenn eine Kombination der Länge m = 2 ausgewählt wird?

Das folgende Skript gibt die Antwort – die Komponenten des Vektors x werden tatsächlich wie unterschiedliche Objekte behandelt:

c.4.2 <- combn(x = c(1, 2, 3, 1), m = 2)

str(c.4.2)
# int [1:2, 1:6] 1 2 1 3 1 4 2 3 2 4 ...

c.4.2
# [,1] [,2] [,3] [,4] [,5] [,6]
# [1,]    1    1    1    2    2    3
# [2,]    2    3    1    3    1    1

Man beachte insbesondere die dritte Kombination! Als Menge interpretiert wäre x = c(1, 2, 3, 1) mit der Eingabe x = 3 gleichwertig und man könnte mit m = 2 lediglich 3 Teilmengen auswählen.

Das Argument FUN von combn()

Die Funktion combn() besitzt weitere Argumente, nämlich 

combn(x, m, FUN = NULL, simplify = TRUE, ...)

In vielen Anwendungen möchte man nicht die durch combn() bestimmten Teilmengen ausgeben, sondern diese Teilmengen sollen durch eine Funktion FUN weiterverarbeitet werden. Oft reicht eine vergröberte Information über die Teilmengen, wie etwa die Summe ihrer Elemente.

Für FUN kann jede beliebige Funktion eingegeben werden, die den in einer Auswahl gebildeten Vektor verarbeiten kann. Soll die Funktion FUN sehr spezielle Aufgaben erledigen, kann man ihr mit dem Argument ... weitere Argumente übergeben. Der Rückgabewert der Funktion FUN ist beliebig.

Als einfaches Beispiel wird zunächst für die 6-elementigen Teilmengen von (1:10) die Summe der Elemente berechnet; dies geschieht mit Hilfe der Funktion sum():

v <- combn(x = 10, m = 6, FUN = sum)

v
# [1] 21 22 23 24 25 23 24 25 26 25 26 27 27 28 29 24 25 26 27 26 27 28 28 29 30 27 28 29 29 30 31 30 31 32 33 25 26 27 28 27 28 29 29 30 31 28 29 30 30 31 32
# [52] 31 32 33 34 29 30 31 31 32 33 32 33 34 35 33 34 35 36 37 26 27 28 29 28 29 30 30 31 32 29 30 31 31 32 33 32 33 34 35 30 31 32 32 33 34 33 34 35 36 34 35
# [103] 36 37 38 31 32 33 33 34 35 34 35 36 37 35 36 37 38 39 36 37 38 39 40 41 27 28 29 30 29 30 31 31 32 33 30 31 32 32 33 34 33 34 35 36 31 32 33 33 34 35 34
# [154] 35 36 37 35 36 37 38 39 32 33 34 34 35 36 35 36 37 38 36 37 38 39 40 37 38 39 40 41 42 33 34 35 35 36 37 36 37 38 39 37 38 39 40 41 38 39 40 41 42 43 39
# [205] 40 41 42 43 44 45

Zeile 1:

Zu jeder der 6-elementigen Teilmengen von (1:10) wird die Summe der Komponenten gebildet.

Zeile 3 bis 10:

Die Ausgabe zeigt 210 (gleich "6 aus 10") Komponenten, die man leicht nachvollziehen kann.

1 + 2 + ... + 6 = 21

...

5 + 6 + ... + 10 = 45.

Den Einsatz von ... , womit man Argumente an die Funktion FUN weiterreichen kann, zeigt die folgende Variation des letzten Beispiels.

Es werden nur diejenigen Teilmengen berücksichtigt, deren Komponenten eine Summe besitzen, die kleiner als eine gegebene Schranke ist. Dazu wird eine Funktion sum.limit(v, limit) mit zwei Argumenten definiert:

Die Funktion sum.limit(v, limit) sorgt dafür, dass

sum.limit <- function(v, limit){
  s <- sum(v)
  if(s < limit) {
    cat(v, "; Summe: ", s, "\n")
    return(s)
  } 
  else return(NA)
}

combn(x = 10, m = 6, FUN = sum.limit, limit = 28 )
# 1 2 3 4 5 6 ; Summe:  21 
# 1 2 3 4 5 7 ; Summe:  22 
# 1 2 3 4 5 8 ; Summe:  23 
# 1 2 3 4 5 9 ; Summe:  24 
# 1 2 3 4 5 10 ; Summe:  25 
# 1 2 3 4 6 7 ; Summe:  23 
# 1 2 3 4 6 8 ; Summe:  24 
# 1 2 3 4 6 9 ; Summe:  25 
# 1 2 3 4 6 10 ; Summe:  26 
# 1 2 3 4 7 8 ; Summe:  25 
# 1 2 3 4 7 9 ; Summe:  26 
# 1 2 3 4 7 10 ; Summe:  27 
# 1 2 3 4 8 9 ; Summe:  27 
# 1 2 3 5 6 7 ; Summe:  24 
# 1 2 3 5 6 8 ; Summe:  25 
# 1 2 3 5 6 9 ; Summe:  26 
# 1 2 3 5 6 10 ; Summe:  27 
# 1 2 3 5 7 8 ; Summe:  26 
# 1 2 3 5 7 9 ; Summe:  27 
# 1 2 3 6 7 8 ; Summe:  27 
# 1 2 4 5 6 7 ; Summe:  25 
# 1 2 4 5 6 8 ; Summe:  26 
# 1 2 4 5 6 9 ; Summe:  27 
# 1 2 4 5 7 8 ; Summe:  27 
# 1 3 4 5 6 7 ; Summe:  26 
# 1 3 4 5 6 8 ; Summe:  27 
# 2 3 4 5 6 7 ; Summe:  27 
# [1] 21 22 23 24 25 23 24 25 26 25 26 27 27 NA NA 24 25 26 27 26 27 NA NA NA NA 27 NA NA NA NA NA NA NA NA NA 25 26 27 NA 27 NA NA NA NA NA NA NA NA NA NA NA
# [52] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 26 27 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA
# [103] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 27 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA
# [154] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA
# [205] NA NA NA NA NA NA

Zeile 10:

Die Funktion combn() wird jetzt mit FUN = sum.limit aufgerufen, das Argument limit = 28 wird an FUN weitergereicht.

Zeile 11 bis 37:

Die Ausgaben aus den cat()-Befehlen innerhalb der Funktion sum.limit(); es wird die jeweilige Teilmenge und die Summe ihrer Elemente ausgegeben – und zwar nur für Summen kleiner als 28.

Zeile 38 bis 42: Ausgabe des Rückgabewertes von combn(). Jetzt werden die berechneten Summen zu einem Vektor zusammengefasst, der insgesamt 210 Komponenten besitzt, von denen die meisten gleich NA sind.

Aufgabe:

Wie viele Möglichkeiten gibt es, einen Lottoschein auszufüllen, so dass die Summe der angekreuzten Zahlen größer als 256 ist?

Schreiben Sie ein R-Skript, das die entsprechenden Lottoscheine und die Summe der Zahlen ausgibt. Versuchen Sie eine Lösung zu finden, in der nicht alle 13 983 816 Kombinationen durchgespielt werden müssen.

♦ ♦ ♦ ♦ ♦

Wird innerhalb von combn() das Argument FUN nicht gesetzt, wird die Funktion identity() verwendet, die die jeweils ausgewählte Teilmenge zurückgibt. Dies war im allerersten Beispiel zu combn() zu sehen. Da das Argument simplify den default-Wert TRUE besitzt, werden diese Teilmengen zu einer Matrix zusammengefasst. Mit simplify = FALSE hätte man eine Liste erhalten.

Daran erkennt man, wie der Rückgabewert von FUN den Rückgabewert von combn() festlegt. Ist simplify = TRUE , dann gilt: