Kombinatorik-Werkbank

Kombinationen- und Permutationen-Rechner

Berechne nCr und nPr sowie Wiederholungen, Stars and Bars, Multimengen, Kugeln in Fächern, Inklusion-Exklusion, Derangements und Gitterwege.

Rechenbeispiel — Kombinatorik-Werkbank

Exakter Wert	120
Näherung	120
Ziffern	3
log10	2,0792

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Zähltheorie — Fall für Fall

Zwei Ja/Nein-Fragen ordnen jedes Abzählproblem ein

Auswahl (ohne Wiederholung) C(n,k) = n! / (k!(n − k)!)

Anordnung (ohne Wiederholung) P(n,k) = n! / (n − k)!

Geordnet mit Wiederholung n^k

Auswahl mit Wiederholung C(n + k − 1, k)

Auswahl (ohne Wiederholung)

Formel: C(n,k) = n! / (k!(n − k)!)

Durchgerechnetes Beispiel: Wähle 3 aus 10 Personen. Da die Reihenfolge egal ist, ergeben C(10,3) = 120 Komitees.

Öffne dieses Beispiel: Ausschussauswahl

Auswahl (ohne Wiederholung). Ungeordnete Auswahl: die gewählten Chips bilden eine Menge, keine Sequenz. 3 Personen aus 10 auswählen: Reihenfolge spielt keine Rolle. — Ungeordnete Auswahl: die gewählten Chips bilden eine Menge, keine Sequenz.

Anordnung (ohne Wiederholung)

Formel: P(n,k) = n! / (n − k)!

Durchgerechnetes Beispiel: Vergib Gold, Silber und Bronze unter 10 Finalisten. Da die Rollen verschieden sind, ergeben P(10,3) = 720 Podiumsbelegungen.

Öffne dieses Beispiel: Podiumsreihenfolge

Anordnung (ohne Wiederholung). Geordnete Plätze: Vertauschen der Positionen erzeugt ein neues Ergebnis. Top-3-Podium aus 10: Reihenfolge zählt. — Geordnete Plätze: Vertauschen der Positionen erzeugt ein neues Ergebnis.

Geordnet mit Wiederholung

Formel: n^k

Durchgerechnetes Beispiel: Bilde eine 4-stellige PIN aus 10 Ziffern. Die Reihenfolge zählt und Ziffern dürfen sich wiederholen: 10^4 = 10.000 PINs.

Öffne dieses Beispiel: PIN-Code

Geordnet mit Wiederholung. Jeder Platz wählt unabhängig aus demselben Pool. 4-stellige PIN: Wiederholung erlaubt. — Jeder Platz wählt unabhängig aus demselben Pool.

Auswahl mit Wiederholung

Formel: C(n + k − 1, k)

Durchgerechnetes Beispiel: Wähle 3 Kugeln aus 8 Sorten, ohne Kugelreihenfolge und mit erlaubter Wiederholung. C(10,3) = 120 Sortenkombinationen.

Öffne dieses Beispiel: Eiskugeln

Auswahl mit Wiederholung. Sterne und Balken: Trenner kodieren wiederholte Auswahlen. 3 Kugeln aus 8 Sorten: Reihenfolge egal, Wiederholung erlaubt. — Sterne und Balken: Trenner kodieren wiederholte Auswahlen.

Multimengen-Permutation

Formel: N! / (n₁! · n₂! · … · n_r!)

Durchgerechnetes Beispiel: MISSISSIPPI hat 11 Buchstaben mit I×4, S×4, P×2 und M×1. Nach Division der identischen Vertauschungen gilt 11!/(4!4!2!) = 34.650 Anordnungen.

Öffne dieses Beispiel: MISSISSIPPI

Multimengen-Permutation. Wiederholte Symbole teilen die Gesamtzahl der Permutationen durch Duplikat-Vertauschungen. Elf Buchstaben, vier S, vier I, zwei P: 11! durch 4!·4!·2! = 34.650. Ohne die Wiederholungen wären es 39.916.800. Die Duplikate entfernen demnach mehr als 99,9 % der Anordnungen.. — Wiederholte Symbole teilen die Gesamtzahl der Permutationen durch Duplikat-Vertauschungen.

Kugeln in Fächer

Formel: Σ_i=0^m (−1)ⁱC(m,i)(m − i)ⁿ

Durchgerechnetes Beispiel: Verteile 6 verschiedene Aufgaben auf 3 benannte Personen, ohne dass jemand leer ausgeht. Inklusion–Exklusion ergibt 3^6 − 3·2^6 + 3 = 540 Zuordnungen.

Öffne dieses Beispiel: verschiedene in Fächer (surjektiv)

Kugeln in Fächer. Kugeln-und-Fächer-Ansicht für Zuordnungs-/Verteilungsbedingungen. 6 unterschiedliche Aufgaben auf 3 Mitarbeiter verteilen, jeder bekommt mindestens eine. — Kugeln-und-Fächer-Ansicht für Zuordnungs-/Verteilungsbedingungen.

Inklusions-Exklusions-Prinzip

Formel: C(n,k) − C(b,k)

Durchgerechnetes Beispiel: Wähle eine ungeordnete 5-Karten-Hand mit mindestens einem Ass. C(52,5) − C(48,5) = 886.656 Hände.

Öffne dieses Beispiel: mindestens ein Ass

Inklusions-Exklusions-Prinzip. Mengenüberlappungs-Bild für das Addieren-Subtrahieren-Zählen. 5-Karten-Hand mit mindestens einem Ass über das Gegenereignis. — Mengenüberlappungs-Bild für das Addieren-Subtrahieren-Zählen.

Spezialfälle

Formel: !n = n! Σ_i=0ⁿ (−1)ⁱ / i!

Durchgerechnetes Beispiel: Ordne 8 Namen beim Wichteln ohne Selbstziehung zu. Die Anzahl fixpunktfreier Permutationen ist !8 = 14.833.

Öffne dieses Beispiel: Wichteln

Spezialfälle. Klassische eingeschränkte Zählungen: zirkulär, Derangements und Gitterwege. Acht Personen, niemand zieht den eigenen Namen: 14.833 Möglichkeiten. Das entspricht 8! geteilt durch e und gerundet. Die Anzahl der Derangements ist stets die nächste ganze Zahl an n!/e. Daher stammt auch der dritte Erkenntnisblock weiter unten.. — Klassische eingeschränkte Zählungen: zirkulär, Derangements und Gitterwege.

Quellen (1)

The last case in the guide above is Secret Santa, and insight block 3 finds e hiding in it. That is the matching problem, and it is three centuries old: P. Gorroochurn, "Rencontres with Montmort (1708)", chapter 7 of Classic Problems of Probability, 54–61. Wiley, 2012 — the probability that nobody draws their own name tends to 1/e.

Übung

Prüfe dich selbst

Sage die Antwort zuerst voraus und probiere es dann oben aus. Zeige die Lösung erst, wenn du dich entschieden hast — genau das macht es zur Übung.

Wähle 3 von 10 Personen für ein Komitee. Wähle dann aus denselben 10 den ersten, zweiten und dritten Platz. Gleiches n, gleiches k — unterscheiden sich die beiden Anzahlen, und wenn ja, um genau welchen Faktor? Prüfe es mit den ersten beiden Modellen.

Antwort anzeigen

120 gegen 720, ein Faktor von 6. Eine einzige Frage trennt sie, und es sind nicht die Zahlen: Kommt es auf die Reihenfolge an? Jedes ungeordnete Komitee aus 3 lässt sich zu 3! = 6 verschiedenen Podesten aufreihen, Anordnen ist also stets Auswählen mal k!. Der Faktor ist k! und nie etwas anderes — deshalb unterscheiden sich die beiden Formeln um genau diese eine Division.
Eine vierstellige PIN aus 10 Ziffern, und 4 Eiskugeln aus 10 Sorten, wobei eine Sorte mehrfach vorkommen darf. Beides erlaubt Wiederholung. Sage voraus, welche Anzahl größer ist, und prüfe es.

Antwort anzeigen

10,000 gegen 715. Wiederholung ist in beiden erlaubt, sie trennt die Fälle also nicht — die Reihenfolge tut es. Die PIN ist geordnet mit Wiederholung, n^k = 10⁴. Die Kugeln sind ungeordnet mit Wiederholung, C(n + k − 1, k) = C(13,4) = 715. Die beiden Modelle „mit Wiederholung“ liegen so weit auseinander wie die beiden ohne — deshalb genügt die Frage „darf sich etwas wiederholen?“ allein nie. Man braucht immer beide.
Sechs verschiedene Preise auf drei verschiedene Kisten ergeben 729. Stelle die Variante so um, dass jede Kiste mindestens einen Preis bekommen muss, und es sinkt auf 540. Wohin sind die fehlenden 189 Verteilungen verschwunden?

Antwort anzeigen

Es sind genau jene Verteilungen, die eine Kiste leer lassen, und sie zu zählen verlangt eine alternierende Summe statt einer Formel. Die leere Kiste lässt sich auf 3 Arten wählen, der Rest auf 2⁶ = 64 Arten füllen: 3 × 64 = 192. Doch die 3 Fälle, in denen alle sechs Preise in einer einzigen Kiste landen, wurden dort je doppelt gezählt, also 3 abziehen. Bleiben 192 − 3 = 189 Verteilungen mit leerer Kiste, und 729 − 189 = 540. Dies ist das einzige Modell der Werkbank, dessen Antwort eine alternierende Summe ist — deshalb rechnet es am längsten und geht von Hand am leichtesten schief.

Aufgaben vollständig gelöst

3 aus 10 auswählen und die Lösung für 7 5 Schritte
3 aus 10 auszuwählen ergibt 120 Möglichkeiten. Leite dies aus der geordneten Zählung ab und finde dann heraus, warum 120 auch die Antwort für die Auswahl von 7 ist.
1. Zähle zuerst geordnete Auswahlen, da diese einfacher sind: zehn Möglichkeiten, dann neun, dann acht.
  
  $P(10,3)=10\times9\times8=720=3!\binom{10}{3}$
2. Dabei wird jede Dreiergruppe mehrfach gezählt — einmal für jede Reihenfolge, in der dieselben drei auftreten können, was 3! = 6 entspricht.
3. Die Division ergibt 120, und das Teilen durch k! macht den gesamten Unterschied zwischen einer Permutation und einer Kombination aus.
  
  $\binom{10}{3}=\frac{10\times9\times8}{3\times2\times1}=\frac{720}{6}=120$
4. Die Symmetrie folgt aus der Bedeutung des Auswählens. 3 zum Mitnehmen auszuwählen ist derselbe Vorgang wie 7 zum Zurücklassen auszuwählen, sodass sich die beiden Anzahlen nicht unterscheiden können.
  
  $\binom{10}{3}=\binom{10}{7}=120\qquad(\text{choosing 3 is choosing which 7 to omit})$
5. Der log₁₀-Wert von 2,0792 im Bedienfeld ist die praktische Ergänzung: drei Stellen. Für große n übersteigt die Anzahl alles, was man speichern kann, und der Logarithmus bleibt das, was berechenbar ist.
  
  $\log_{10}120=2.0792\quad\Longrightarrow\quad 3\ \text{digits}$
Antwort

Das Werkzeug gibt 120, 3 Stellen und log₁₀ = 2,0792 aus. Es lohnt sich, die Symmetrie zu verinnerlichen, da sie die Arbeit halbiert: Niemand sollte C(10, 7) von Grund auf berechnen. Und die gesamte Zeile summiert sich auf 2¹⁰ = 1024 — jede Teilmenge von zehn Elementen, gezählt nach Größe —, was die schnellste Plausibilitätsprüfung für jede Binomialberechnung ist, die du jemals durchführen wirst. Der größte Eintrag ist C(10, 5) = 252, sodass die Mitte der Zeile etwa ein Viertel aller Teilmengen enthält, während die beiden Äußeren jeweils eine enthalten.

$\binom{n}{k}=\frac{P(n,k)}{k!}:\ \text{order costs a factor of}\ k!=6$
Die 2.598.960 Möglichkeiten, ein Fünf-Karten-Blatt für einen Flush zu geben 5 Schritte
Ein Blatt aus fünf Karten kann auf 2.598.960 Arten ausgeteilt werden. Leite dies aus dem geordneten Geben ab und verwende es anschließend, um einen Flush zu bewerten. Dies ist Auswählen (ohne Wiederholung) mit n = 52 und k = 5.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Teile zuerst geordnet aus. Die erste Karte hat 52 Möglichkeiten, die nächste 51 und so weiter bis hinab zu 48 — fünf Faktoren, noch keine Division.
  
  $P(52,5)=52\times51\times50\times49\times48=311\,875\,200$
2. Ein Blatt ist eine Menge, und die geordnete Zählung hat jede Menge 120-mal erfasst, einmal für jede Reihenfolge, in der dieselben fünf Karten hätten eintreffen können. Die Division durch 5! ist der einzige Schritt, der aus einem Geben ein Blatt macht.
  
  $\binom{52}{5}=\frac{311\,875\,200}{5!}=\frac{311\,875\,200}{120}=2\,598\,960$
3. Zähle nun die Flushes innerhalb dieses Raums: Wähle die Farbe auf vier Arten aus, dann fünf der dreizehn Karten dieser Farbe.
  
  $\text{flushes}=4\binom{13}{5}=4\times1287=5148$
4. Das klärt, was einen Flush selten macht. Es liegt nicht daran, dass 5.148 eine kleine Anzahl von Blättern ist — sondern daran, dass der Raum, in dem er liegt, fünfhundertmal größer ist.
  
  $P(\text{flush})=\frac{5148}{2\,598\,960}=0.00198\approx\frac{1}{505}$
5. Und dieser Raum ist immer noch klein genug, um greifbar zu sein. Ein Blatt jede Sekunde, ohne Unterbrechung, und jedes verschiedene Blatt wurde innerhalb eines Monats ausgeteilt.
  
  $\frac{2\,598\,960}{86\,400}=30.1\ \text{days, at one hand per second}$
Antwort

Das Werkzeug gibt 2.598.960, 7 Stellen und log₁₀ = 6,4148 aus. Die Rangfolge der Pokerhände beruht auf dieser Arithmetik und auf sonst nichts. Zähle die Straights auf dieselbe Weise — zehn Startränge, vier Farben für jede der fünf Karten, 10 × 4⁵ = 10.240 — und es gibt doppelt so viele Straights wie Flushes, was genau der Grund ist, warum ein Flush höher gewertet wird als eine Straight. Die Reihenfolge wurde nicht entworfen; sie wurde gezählt.

$\binom{52}{5}=2\,598\,960\qquad P(\text{flush})\approx\tfrac{1}{505}$
Die 62.990.928.000 Varianten eines achtstelligen Passworts ohne Buchstabenwiederholung 5 Schritte
Ein Passwort aus acht Buchstaben ohne sich wiederholende Buchstaben hat 62.990.928.000 Formen. Zähle es, zähle danach dasselbe Passwort ohne diese Regel und entscheide, welches davon du lieber verteidigen würdest. Dies ist Anordnen (ohne Wiederholung) mit n = 26 und k = 8.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Fülle die Stellen von links nach rechts. Die erste nimmt jeden der 26 Buchstaben; die zweite nimmt 25, weil der verbrauchte Buchstabe weg ist.
  
  $P(26,8)=\frac{26!}{18!}=26\times25\times24\times23\times22\times21\times20\times19$
2. Acht absteigende Faktoren, und dieses Produkt ist bereits die gesamte Antwort. Es handelt sich um eine Permutation und nicht um eine Kombination, da die Reihenfolge der Buchstaben das Passwort ist.
  
  $=62\,990\,928\,000$
3. Streiche nun die Regel. Jede Stelle ist wieder unabhängig und für jede Stelle stehen alle 26 Buchstaben zur Verfügung, sodass die Zählung eine einfache Potenz ist.
  
  $26^{8}=208\,827\,064\,576\qquad(\text{repeats allowed})$
4. Der Vergleich ist der entscheidende Punkt: Das Verbot von Wiederholungen behält 30,2 % der Zeichenketten übrig. Eine Regel, die nach einer Stärkung klingt, hat sieben von zehn Zeichenketten entfernt.
  
  $\frac{62\,990\,928\,000}{208\,827\,064\,576}=0.302$
5. In Angreiferzeit, bei einer Milliarde Rateversuchen pro Sekunde, entsprechen die beiden Räume einer Minute beziehungsweise dreieinhalb Minuten. Keiner von beiden bietet Schutz — und die Regel hat den kürzeren Raum noch kürzer gemacht.
  
  $10^{9}\ \text{guesses/s}:\quad 63\ \mathrm{s}\ \ \text{vs}\ \ 209\ \mathrm{s}$
Antwort

Mit n = 26, k = 8 und dem Modell auf Anordnen (ohne Wiederholung) eingestellt, gibt das Werkzeug 62.990.928.000, 11 Stellen und log₁₀ = 10,7993 aus. Jede Regel für die Zusammensetzung verkleinert den Raum, ohne Ausnahme, denn eine Regel kann nur verbieten. Ob sie ihre Berechtigung hat, hängt von etwas ab, das diese Arithmetik nicht sehen kann: ob die von ihr verbotenen Zeichenketten solche sind, die von Menschen weit häufiger gewählt werden als durch Zufall. Das Verbieten eines berüchtigten Passworts kostet eine Zeichenkette. Das Verbieten aller doppelten Buchstaben kostet 145.836.136.576 davon.

$P(26,8)=0.302\times26^{8}:\ \text{forbidding repeats deletes }69.8\%\ \text{of the strings}$
Drei Versuche am Geldautomaten für eine vierstellige PIN 5 Schritte
Eine vierstellige PIN hat 10.000 Werte. Ermittle, was drei Versuche an einem Geldautomaten wert sind und was der geläufige Ratschlag, sich wiederholende Ziffern zu vermeiden, tatsächlich kostet. Dies ist Geordnet mit Wiederholung mit n = 10 und k = 4.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Vier Stellen, zehn Ziffern in jeder, und nichts verbindet sie — die gerade verwendete Ziffer steht auch für die nächste Stelle weiterhin zur Verfügung.
  
  $10\times10\times10\times10=10^{4}=10\,000$
2. Drei Versuche bei einer gleichverteilt gewählten PIN entsprechen daher drei Chancen von zehntausend. Die Begrenzung auf drei Versuche ist keine bloße Verbesserung gegenüber unbegrenztem Raten; gegenüber diesem Raum ist sie der gesamte Schutz.
  
  $\text{3 attempts}:\quad \frac{3}{10\,000}=0.03\%$
3. Wende nun die Regel ohne doppelte Ziffern an: zehn Möglichkeiten, dann neun, dann acht, dann sieben.
  
  $\text{no repeated digit}:\quad 10\times9\times8\times7=5040$
4. Die Regel behält 5.040 PINs und vernichtet 4.960. Die Hälfte des Raums ist weg — und die Hälfte, die verloren ging, enthielt 1111 zusammen mit allem anderen.
  
  $\frac{5040}{10\,000}=0.504$
5. Zwei zusätzliche Ziffern bedeuten nicht zwei zusätzliche Rateversuche. Jede Ziffer vervielfacht mit zehn, sodass eine sechsstellige PIN den hundertfachen Raum darstellt.
  
  $\text{six digits}:\quad 10^{6}=1\,000\,000=100\times10^{4}$
Antwort

Das Werkzeug gibt 10.000 für n = 10, k = 4 aus. Beide Tatsachen gelten gleichzeitig: Der Raum ist winzig, und eine PIN ist normalerweise trotzdem ausreichend — weil die Begrenzung auf drei Versuche einem Angreifer 0,03 % davon überlässt statt des gesamten Raums. Ändert man die Bedrohung, kehrt sich die Antwort um. Eine gestohlene PIN-Datei hat keine Versuchsbegrenzung, und zehntausend Kandidaten sind die Arbeit eines Bruchteils einer Sekunde. Genau deshalb beruht die Sicherheit einer PIN niemals auf der PIN selbst.

$n^{k}=10^{4}=10\,000\qquad 10\times9\times8\times7=5040$
Drei Kugeln aus acht Sorten und drei Personen aus zehn 5 Schritte
Drei Kugeln aus acht Sorten, Wiederholungen erlaubt, ergibt 120 — dieselbe Anzahl wie die Auswahl von drei Personen aus zehn. Zeige, dass dies kein Zufall ist. Dies ist Kombination mit Wiederholung mit n = 8 und k = 3.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Schreibe die Bestellung als Reihe von Symbolen auf: ein Stern für jede Kugel, ein Strich für jeden Schritt weiter zur nächsten Sorte. Drei Kugeln unter acht Sorten erfordern drei Sterne und sieben Striche.
  
  $\underbrace{\star\star\star}_{3\ \text{scoops}}\ \text{and}\ \underbrace{|\,|\,|\,|\,|\,|\,|}_{7\ \text{bars}}$
2. Jede Anordnung dieser zehn Symbole ist eine Bestellung, und jede Bestellung ist eine Anordnung. Es geht also nur darum, welche 3 der 10 Positionen Sterne enthalten — was die Frage von Aufgabe 1 mit anderen Substantiven ist.
  
  $\binom{3+7}{3}=\binom{10}{3}=120$
3. Schließt man Wiederholungen aus, sinkt die Anzahl auf 56. Die Erlaubnis, eine Sorte zu wiederholen, bringt 64 zusätzliche Bestellungen ein und mehr als verdoppelt die Auswahl.
  
  $\binom{8}{3}=56\qquad(\text{no repeats allowed})$
4. Soll nun auch die Reihenfolge eine Rolle spielen, sodass sich Vanille-Vanille-Minze von Minze-Vanille-Vanille unterscheidet: acht unabhängige Entscheidungen, dreimal hintereinander.
  
  $8^{3}=512\qquad(\text{ordered, repeats allowed})$
5. Das Verhältnis zwischen den beiden beträgt 4,27, nicht 3! = 6. Eine Tüte mit einer doppelten Kugel hat weniger unterscheidbare Anordnungen als eine mit drei verschiedenen Kugeln; die Division durch 3! ist also genau der Schritt, den man hier nicht machen darf.
  
  $\frac{512}{120}=4.27\ \ne\ 3!=6$
Antwort

Das Werkzeug gibt 120, 3 Stellen und log₁₀ = 2,0792 aus — dieselbe Anzeige wie bei Aufgabe 1, aus einer anderen Fragestellung. Sterne und Striche ist eher eine Übersetzung als eine Formel: Es verwandelt Wiederholung in Position, wo du bereits weißt, was zu tun ist. Die Falle, die es stellt, ist Schritt 5. Sobald Wiederholungen erlaubt sind, sind die Anordnungen nicht mehr austauschbar, und kein einzelner Faktor rechnet zwischen der geordneten und der ungeordneten Anzahl um.

$\binom{n+k-1}{k}:\ k\ \text{stars},\ n-1\ \text{bars}$
Die 34.650 verschiedenen Wörter aus MISSISSIPPI mit vier S, die nicht nebeneinander stehen 5 Schritte
Die Buchstaben von MISSISSIPPI ergeben 34.650 unterscheidbare Wörter. Leite dies ab und beantworte dann eine schwierigere Frage, für die das Werkzeug kein Feld hat: Wie oft stehen die vier S getrennt voneinander? Dies ist Permutation einer Multimenge mit den Anzahlen 1, 4, 4, 2.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Tu zuerst so, als wäre jeder Buchstabe unterscheidbar — bezeichne die S mit S₁ bis S₄. Dann ist es eine gewöhnliche Permutation von elf Objekten.
  
  $11!=39\,916\,800$
2. Entferne nun die Bezeichnungen. Die vier S können auf 4! Arten permutiert werden, ohne dass sich das Geschriebene ändert, und dasselbe gilt für die vier I und die zwei P; jedes sichtbare Wort wurde also 1.152-mal gezählt.
  
  $\frac{11!}{1!\,4!\,4!\,2!}=\frac{39\,916\,800}{1152}=34\,650$
3. Was direkt eine Wahrscheinlichkeit ergibt: Mische die elf Plättchen, und eine von 34.650 Anordnungen ergibt den Namen des Bundesstaates.
  
  $P(\text{a shuffle spells MISSISSIPPI})=\frac{1}{34\,650}=0.0000289$
4. Für die schwierigere Frage platziere zuerst die anderen sieben Buchstaben — M, vier I, zwei P — und zähle deren Anordnungen. Das lässt acht Lücken einschließlich der beiden Enden, und jedes S muss eine andere Lücke einnehmen.
  
  $\frac{7!}{1!\,4!\,2!}=105,\qquad \binom{8}{4}=70$
5. Multipliziere und dividiere: 7.350 der 34.650 Wörter halten die S voneinander getrennt, was 21,2 % entspricht.
  
  $\frac{105\times70}{34\,650}=\frac{7350}{34\,650}=0.2121=\frac{7}{33}$
Antwort

Das Werkzeug gibt 34.650, 5 Stellen und log₁₀ = 4,5397 aus. Die Lückenmethode in den Schritten 4 und 5 ist wertvoller als die Antwort selbst. Sie ist das allgemeine Vorgehen für jede Bedingung des Typs keine zwei davon nebeneinander: Platziere die unbeschränkten Elemente und wähle dann Lücken für die beschränkten aus. Nachbarschaft ist eine Bedingung, die keine Fakultät ausdrücken kann, und die Lücken verwandeln sie in eine Auswahl von Positionen — was genau das Eine ist, das jede Formel auf dieser Seite bereits zu zählen weiß.

$\frac{n!}{n_1!\,n_2!\cdots}:\ \text{divide by the orderings you cannot see}$
Sechs verschiedene Aufgaben verteilt auf drei Arbeiter, wobei niemand leer ausgeht 5 Schritte
Sechs verschiedene Aufgaben, die an drei Arbeiter verteilt werden, ohne dass jemand untätig bleibt, ergeben 540 Zuordnungen. Leite dies ab, indem du die schlechten Fälle entfernst, anstatt die guten zu zählen. Dies ist Bälle in Fächer, unterscheidbare Objekte, jedes Fach belegt, mit n = 6 und m = 3.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Ignoriere zuerst die Anforderung. Jede Aufgabe wählt unabhängig einen von drei Arbeitern aus, sodass die uneingeschränkte Anzahl eine Potenz ist — und das ist weit einfacher als die eingeschränkte.
  
  $3^{6}=729\qquad(\text{no restriction})$
2. Subtrahiere nun die Zuordnungen, die jemanden ohne Aufgabe lassen: Wähle den untätigen Arbeiter auf drei Arten aus und gib dann alle sechs Aufgaben den anderen beiden.
  
  $\text{one worker idle}:\quad \binom{3}{1}2^{6}=3\times64=192$
3. Diese Subtraktion ging zu weit. Eine Zuordnung, die nur einen Arbeiter nutzt, wurde zweimal subtrahiert, einmal für jeden Kollegen, den sie untätig ließ; diese drei kommen also wieder hinzu.
  
  $\text{two idle, added back}:\quad \binom{3}{2}1^{6}=3$
4. Abwechselnde Subtraktion und Addition ist Inklusion–Exklusion, und die alternierende Summe ist das, was die Formelzeile des Werkzeugs anzeigt.
  
  $729-192+3=540$
5. Drei Viertel aller Zuordnungen nutzen also tatsächlich alle Personen. Teile durch 3!, um die Arbeiter austauschbar zu machen, und du erhältst S(6, 3) = 90, die Stirling-Zahl der zweiten Art — dieselben Partitionen, gezählt ohne Namen.
  
  $\frac{540}{729}=0.7407,\qquad S(6,3)=\frac{540}{3!}=90$
Antwort

Das Werkzeug gibt 540, 3 Stellen und log₁₀ = 2,7324 aus. In Schritt 3 geht diese Aufgabe gewöhnlich verloren. Der Instinkt sagt, dass das Subtrahieren der schlechten Fälle die Methode sei, aber das ist er nicht: Die Subtraktion über überlappende Mengen schießt immer über das Ziel hinaus, und die Korrekturterme sind keine Dekoration. Die 90 in Schritt 5 ist dasselbe Objekt aus einem anderen Blickwinkel — mit benannten Arbeitern gibt es 540 Zuordnungen, ohne Namen 90 Partitionen, und der Abstand zwischen ihnen ist genau die 3! Möglichkeiten, die Namen zu vergeben.

$\sum_{i=0}^{m}(-1)^i\binom{m}{i}(m-i)^n=540=3!\,S(6,3)$
Zwölf gleiche Spielsteine in vier markierte Boxen, wobei keine leer bleibt 5 Schritte
Zwölf identische Spielsteine auf vier beschriftete Fächer ohne leeres Fach ergibt 165. Man gelangt dorthin, indem man die Bedingung vorab erfüllt. Dies ist Kugeln in Fächer, identische Objekte, kein Fach leer, mit n = 12 und m = 4.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Die Anforderung verlangt, dass jedes Fach mindestens einen Spielstein erhält; man erfüllt sie also sofort: In jedes Fach wird ein Spielstein gelegt, womit diese Bedingung erledigt ist. Acht Spielsteine bleiben übrig, für die nun keinerlei Regeln mehr gelten.
  
  $\text{pay the floor first}:\quad 12-4=8\ \text{units still free}$
2. Die freie Verteilung identischer Objekte entspricht Sterne und Striche — acht Sterne, drei Striche zur Trennung von vier Fächern — und die Anzahl ergibt sich aus der Wahl der Positionen für die Striche.
  
  $\binom{8+4-1}{4-1}=\binom{11}{3}=165$
3. Verzichtet man auf die Bedingung, dass kein Fach leer bleibt, liefert dieselbe Methode 455, da nun alle zwölf Spielsteine frei verteilbar sind.
  
  $\text{without the floor}:\quad \binom{12+4-1}{3}=\binom{15}{3}=455$
4. Die Mindestanzahl von eins kostet also fast zwei Drittel der Verteilungen: 165 der 455 bleiben bestehen.
  
  $\frac{165}{455}=0.363$
5. Macht man die Spielsteine stattdessen unterscheidbar, springt die Anzahl auf 16.777.216. Ununterscheidbarkeit ist teuer — fünf Größenordnungen bei zwölf Objekten.
  
  $\text{distinct units instead}:\quad 4^{12}=16\,777\,216$
Antwort

Das Werkzeug gibt 165, 3 Stellen und log₁₀ = 2,2175 aus. Schritt 1 ist der übertragbare Kniff: Eine untere Schranke für jeden Teil kann im Voraus erbracht werden, weil dadurch ein Problem gleicher Struktur mit kleinerem n verbleibt. Erhöht man die Mindestanzahl auf jeweils drei, verbleiben zwölf minus zwölf, sodass das Ergebnis eins ist. Nach oben funktioniert dies nicht, und genau diese Asymmetrie ist der eigentliche Grund, warum höchstens zwei pro Fach eine schwierigere Frage ist als mindestens eins.

$\binom{n-1}{m-1}:\ \text{a floor of one is a constant, not a new formula}$
Die 886.656 Fünf-Karten-Blätter, die mindestens ein Ass enthalten 5 Schritte
886.656 Fünf-Karten-Hände enthalten mindestens ein Ass. Man zählt die Hände ohne Ass und subtrahiert — zur Kontrolle berechnet man dieselbe Zahl anschließend auf dem langen Weg neu. Dies ist Inklusion-Exklusion, Mindestens-eins, mit n = 52, k = 5 und 48 Karten, die keine Asse sind.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Das direkte Zählen von Händen mit mindestens einem Ass bedeutet eine Aufteilung nach ein, zwei, drei und vier Assen. Das Zählen des Komplements erfordert nur eine einzige Berechnung, daher beginnt man dort.
  
  $\binom{52}{5}=2\,598\,960$
2. Eine Hand ohne Ass besteht aus fünf Karten, die aus den 48 Nicht-Assen gezogen werden.
  
  $\binom{48}{5}=1\,712\,304\qquad(\text{not one ace})$
3. Subtrahiert man diesen Wert, enthält jede verbleibende Hand mindestens ein Ass — denn eine Hand enthält entweder keines oder welche, etwas Drittes gibt es nicht.
  
  $2\,598\,960-1\,712\,304=886\,656$
4. Ein Drittel aller Hände enthält also mindestens ein Ass, was weit mehr ist, als die Formulierung vier Asse in zweiundfünfzig Karten vermuten lässt.
  
  $P=\frac{886\,656}{2\,598\,960}=0.3412$
5. Nun die Kontrolle: Man zählt genau ein Ass, genau zwei, genau drei und genau vier, und addiert die Ergebnisse. Vier getrennte Rechnungen, und die Gesamtsumme stimmt bis auf die letzte Ziffer überein.
  
  $4\binom{48}{4}+6\binom{48}{3}+4\binom{48}{2}+\binom{48}{1} =778\,320+103\,776+4512+48=886\,656$
Antwort

Das Werkzeug gibt 886.656, 6 Stellen und log₁₀ = 5,9478 aus. Schritt 5 ist keine bloße Zierde. Mindestens eins ist die Formulierung, die am häufigsten als 4 × C(48, 4) = 778.320 berechnet wird — man wählt ein Ass und füllt den Rest auf — und diese Zahl ist falsch, weil eine Hand mit zwei Assen von diesem Rezept zweimal erzeugt wird, einmal von jedem ihrer Asse. Das Komplement kann diesen Fehler niemals machen; deshalb greift man als Erstes dazu, wann immer in einer Aufgabe mindestens eins steht.

$|A|=N-|A^{c}|:\ \text{count the easy side and subtract}$
Vierzig, fünfunddreißig und achtundzwanzig Mitglieder in drei Vereinen 5 Schritte
Vierzig, fünfunddreißig und achtundzwanzig Mitglieder in drei Vereinen ergeben nicht 103 Personen. Man ermittelt die tatsächliche Personenanzahl und teilt sie anschließend darin auf, wer einem, zwei oder allen drei Vereinen angehört. Dies ist Inklusion-Exklusion, Vereinigung von drei Mengen, mit paarweisen Schnittmengen von 12, 10 und 9 sowie einer dreifachen Schnittmenge von 4.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Addiert man die drei Mitgliederlisten, wurde jede Person in zwei Vereinen doppelt gezählt und jede Person in allen drei Vereinen dreifach; 103 ist somit eine obere Schranke und nicht mehr.
  
  $40+35+28=103$
2. Subtrahiert man jede paarweise Schnittmenge, wird jemand in genau zwei Vereinen nun korrekt gezählt — eine Person in allen drei Vereinen wurde jedoch dreimal gezählt und dreimal subtrahiert, sodass sie vollständig verschwunden ist.
  
  $103-(12+10+9)=103-31=72$
3. Addiert man die dreifache Schnittmenge wieder hinzu, stellt man sie wieder her. Das ist bereits das gesamte Prinzip von Inklusion und Exklusion für drei Mengen: Einzelmengen addieren, Paar-Schnittmengen subtrahieren, Dreifach-Schnittmenge addieren.
  
  $72+|A\cap B\cap C|=72+4=76$
4. Die Vereinigungsmenge verrät nicht, wie sich diese 76 Personen verteilen, doch dieselben drei Eingaben beantworten auch das. Man gewichtet die Paar-Schnittmengen mit zwei und die Dreifach-Schnittmenge mit drei, um alle Personen mit mehr als einer Mitgliedschaft herauszurechnen.
  
  $\text{exactly one}=103-2(31)+3(4)=53$
5. Der Rest ergibt sich daraus: 19 Personen gehören genau zwei Vereinen an, und die drei Gruppen summieren sich wieder zu 76.
  
  $\text{exactly two}=31-3(4)=19,\qquad 53+19+4=76$
Antwort

Das Werkzeug gibt 76, 2 Stellen und log₁₀ = 1,8808 aus. Die alternierenden Vorzeichen sind eine Korrektur und keine bloße Gedächtnisstütze: Jeder Term behebt die Übertreibung des vorherigen, und es alterniert, weil jede Korrektur in die entgegengesetzte Richtung übertreibt. Das ist auch der Grund, warum die Formel so schnell wächst — vier Mengen benötigen fünfzehn Terme und n Mengen benötigen 2ⁿ − 1. Lange bevor das praktikabel ist, erweist sich das Komplement aus Aufgabe 9 als das bessere Werkzeug.

$|A\cup B\cup C|=\Sigma_1-\Sigma_2+\Sigma_3=76$
Acht Personen ziehen Namen beim Wichteln, wobei niemand den eigenen Namen zieht 5 Schritte
Acht Personen ziehen beim Wichteln Namen, und bei 14.833 der 40.320 möglichen Ziehungen zieht niemand seinen eigenen Namen. Leite diese Anzahl her und frage dann, wie viele Personen sich gewöhnlich selbst ziehen. Dies ist Spezialfälle, Derangement, mit n = 8.

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Ein Derangement ist eine Permutation ohne Fixpunkt. Inklusion-Exklusion über die acht Ereignisse diese Person hat sich selbst gezogen ergibt eine alternierende Summe.
  
  $!n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$
2. Diese Summe entspricht den ersten neun Gliedern der Reihe für e⁻¹, und alles, was sie auslässt, ist kleiner als 1/9! = 2,8 × 10⁻⁶.
  
  $8!=40\,320,\qquad \sum_{i=0}^{8}\frac{(-1)^i}{i!}=0.367882$
3. Ausmultiplizieren und runden: 14.833 Ziehungen, bei denen niemand seinen eigenen Namen hält.
  
  $!8=40\,320\times0.367882=14\,833$
4. Als Anteil ausgedrückt ist das 0,36788 gegenüber e⁻¹ = 0,367879 — eine Übereinstimmung auf fünf Nachkommastellen bei acht Personen, und dieser Wert ändert sich für größere Gruppen kaum noch.
  
  $P=\frac{14\,833}{40\,320}=0.36788\approx e^{-1}=0.367879$
5. Nun eine andere und einfachere Frage. Jede Person zieht ihren eigenen Namen mit der Wahrscheinlichkeit 1/n, und Erwartungswerte addieren sich unabhängig davon, ob die Ereignisse unabhängig sind oder nicht; somit beträgt die erwartete Anzahl an Selbstziehungen genau 1 — für acht Personen ebenso wie für achthundert.
  
  $E[\text{self-draws}]=\sum_{i=1}^{n}\frac{1}{n}=n\times\frac{1}{n}=1$
Antwort

Das Werkzeug gibt 14.833, 5 Stellen und log₁₀ = 4,1712 aus. Schritt 5 erklärt Schritt 4. Wenn die durchschnittliche Anzahl an Selbstziehungen unabhängig von der Gruppengröße 1 beträgt, kann die Wahrscheinlichkeit, keine einzige zu erhalten, ebenfalls kaum von der Gruppengröße abhängen — und für die Anzahl seltener Ereignisse mit dem Mittelwert 1 beträgt diese Wahrscheinlichkeit e⁻¹. Die Konstante ist hier keine Kuriosität. Sie ist die Antwort darauf, wie wahrscheinlich Null ist, wenn der Mittelwert Eins beträgt, eine Frage, die außerhalb der Kombinatorik ständig auftaucht.

$\frac{!n}{n!}\to e^{-1},\qquad E[\text{self-draws}]=1\ \text{for every }n$
Kürzeste Routen über ein 7 × 5-Gitter mit einer blockierten Zelle 5 Schritte
442 kürzeste Wege kreuzen ein 7 × 5-Gitter, wenn ein Feld blockiert ist. Zähle alle Pfade, zähle diejenigen durch das blockierte Feld und subtrahiere. Finde dann das Feld, dessen Ausfall am meisten schaden würde. Dies ist Spezialfälle, Gitterpfad, mit 7 Ost-Schritten, 5 Nord-Schritten und der Blockierung bei (3, 2).

Öffne diese Aufgabe im Tool
Lösung anzeigen
1. Jeder kürzeste Weg ist zwölf Schritte lang, davon sieben nach Osten und fünf nach Norden in beliebiger Reihenfolge. Ein Weg ist also nichts weiter als die Auswahl, welche der Schritte nach Osten führen.
  
  $\binom{7+5}{7}=\binom{12}{7}=792$
2. Ein Weg durch das blockierte Feld besteht aus zwei unabhängigen Wegen, die an diesem Feld zusammengesetzt sind: von der Ecke zum Feld und vom Feld zur gegenüberliegenden Ecke. Multipliziere, da jede erste Hälfte mit jeder zweiten Hälfte kombiniert wird.
  
  $\text{through }(3,2):\quad \binom{5}{3}\binom{7}{4}=10\times35=350$
3. Subtrahiere, und was übrig bleibt, sind genau die Wege, die das Feld umgehen.
  
  $792-350=442$
4. Dieses einzelne Feld trug 44% des gesamten Verkehrs — eine einzige Blockierung nimmt fast die Hälfte aller Wege weg.
  
  $\frac{350}{792}=0.442$
5. Es ist jedoch nicht das schlimmste Feld, das ausfallen kann. Das Feld einen Schritt östlich des Startpunkts führt 462 Wege, das sind 58% davon, da jeder Weg, der mit einem Ost-Schritt beginnt, durch dieses Feld verlaufen muss.
  
  $\text{through }(1,0):\quad \binom{1}{1}\binom{11}{6}=462=0.583\ \text{of all paths}$
Antwort

Das Werkzeug gibt 442, 3 Stellen und log₁₀ = 2,6454 aus. Schritt 5 widerspricht dem visuellen Eindruck. Das blockierte Feld wirkt nahe der Mitte am schädlichsten, wo sich die Wege zu bündeln scheinen; die Arithmetik besagt jedoch, dass Felder nahe einer Ecke mehr Wege führen, da die Anzahl durch ein Feld das Produkt zweier Binomialkoeffizienten ist und nahe einer Ecke einer davon fast das gesamte Gitter abdeckt. Das Zählen von Pfaden durch jeden Knoten, statt nur auf die Karte zu schauen, ist auch die Art und Weise, wie Redundanz in einem realen Netzwerk gemessen wird.

$\binom{a+b}{a}-\binom{x+y}{x}\binom{(a-x)+(b-y)}{a-x}=442$

Vom 7-Raven-Room-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.