Mathematik

Kombinatorikrechner

Der Kombinatorikrechner deckt sieben Zähloperationen ab: Permutationen (mit und ohne Wiederholung), Kombinationen (mit und ohne Wiederholung / Sterne und Striche), Fakultät, fixpunktfreie Permutationen (Subfakultät) und Catalan-Zahlen. Gib n und r ein, wähle die Rechenart und sieh sofort das exakte Ergebnis mit LaTeX-Formel, Schritt-für-Schritt-Herleitung und interaktivem Pascalschem Dreieck.

Beispiel ausprobieren

Wähle ein Szenario, um zu sehen, wie der Rechner funktioniert, und passe dann die Werte an

Lottoziehung

Berechne die Anzahl möglicher 6-aus-49-Kombinationen.

Wichtige Werte: Kugeln gesamt: 49 · Gezogen: 6 · Kombinationsmodus

Siegertreppchen

Finde heraus, auf wie viele Arten Gold, Silber und Bronze unter 8 Läufern vergeben werden können.

Wichtige Werte: Läufer: 8 · Medaillen: 3 · Permutationsmodus

Wichteln

Berechne gültige Geschenkzuweisungen, bei denen niemand seinen eigenen Namen zieht.

Wichtige Werte: Teilnehmer: 8 · Fixpunktfreie Permutation

Passwort-Schlüsselraum

Schätze die Anzahl möglicher 8-Zeichen-Passwörter aus druckbaren ASCII-Zeichen.

Wichtige Werte: Zeichensatz: 94 · Länge: 8 · Wiederholung erlaubt

Dokumentation

Ueber diesen Rechner

Kombinatorik ist der Zweig der Mathematik, der sich mit dem Zaehlen, Anordnen und Auswaehlen von Objekten befasst. Die beiden grundlegenden Fragen sind: Auf wie viele Arten kannst du Elemente aus einer Menge waehlen, und spielt die Reihenfolge eine Rolle? Dieser Rechner beantwortet beides und deckt sieben verschiedene Zaehloperationen in einem einzigen Werkzeug ab.

Unterstuetzte Rechenarten umfassen Permutationen (geordnete Anordnungen), Kombinationen (ungeordnete Auswahlen), deren Varianten mit Wiederholung, Fakultaeten, fixpunktfreie Permutationen (Permutationen, bei denen kein Element an seiner urspruenglichen Position steht) und Catalan-Zahlen (die korrekte Klammerungen, Polygon-Triangulierungen und andere rekursive Strukturen zaehlen).

Der Rechner verwendet BigInt-Arithmetik fuer exakte Ergebnisse, wenn $n > 170$ (wo Standard-Gleitkommazahlen ueberlaufen), unterstuetzt Werte von $n$ bis 10.000 und liefert eine Stirling-Naeherung neben dem exakten Ergebnis fuer grosse Eingaben. Ein interaktives Pascalsches Dreieck ermoeglicht es dir, jede Zelle anzuklicken und sofort $C(n, r)$ zu berechnen, und das Schritt-fuer-Schritt-Panel zeigt jede Stufe der Formelauswertung.

Bedienungsanleitung

Waehle eine Rechenart aus den visuellen Auswahlkarten: Permutation, Kombination, Perm + Wdh, Sterne & Striche, Fakultaet, Fixpunktfreie Permutation oder Catalan.
Gib n ein — die Gesamtzahl der verschiedenen Elemente in deiner Menge (0 bis 10.000).
Gib r ein — die Anzahl der ausgewaehlten oder angeordneten Elemente. Dieses Feld ist bei Fakultaet, fixpunktfreier Permutation und Catalan ausgeblendet (diese haengen nur von $n$ ab).
Klicke auf Berechnen, um das exakte Ergebnis, eine Schritt-fuer-Schritt-Formelherleitung und (je nach Rechenart) ein P-vs-C-Vergleichspanel, ein Verteilungsbalkendiagramm, ein Konvergenzdiagramm fuer fixpunktfreie Permutationen oder ein interaktives Pascalsches Dreieck zu sehen.
Klicke auf Zellen im Pascalschen Dreieck (angezeigt fuer Kombinationen mit $n \leq 30$ ), um sofort $n$ und $r$ zu setzen und neu zu berechnen.

Formeln

Fakultaet

Die Fakultaet von $n$ ist das Produkt aller positiven ganzen Zahlen bis $n$ , mit der Konvention, dass $0! = 1$ :

n! = n \times (n-1) \times (n-2) \times \cdots \times 1

Fakultaeten wachsen extrem schnell — $20! \approx 2{,}43 \times 10^{18}$ , und $170!$ ist die groesste Fakultaet, die in Standard-Gleitkommazahlen darstellbar ist. Darueber hinaus verwendet dieser Rechner BigInt fuer exakte Berechnungen.

Permutationen (ohne Wiederholung)

Die Anzahl der Moeglichkeiten, $r$ Elemente aus $n$ verschiedenen Elementen anzuordnen, wobei die Reihenfolge zaehlt:

P(n, r) = \frac{n!}{(n-r)!}

Wenn $r > n$ , gilt $P(n, r) = 0$ per Konvention — du kannst nicht mehr Elemente anordnen, als in der Menge vorhanden sind.

Permutationen (mit Wiederholung)

Wenn die Reihenfolge zaehlt und jedes Element wiederverwendet werden kann (z. B. PIN-Codes, Passwoerter):

P_{\text{rep}}(n, r) = n^r

Kombinationen (ohne Wiederholung) — Binomialkoeffizient

Die Anzahl der Moeglichkeiten, $r$ Elemente aus $n$ Elementen auszuwaehlen, wobei die Reihenfolge keine Rolle spielt:

C(n, r) = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}

Wichtige Identitaet: $\binom{n}{r} = \binom{n}{n-r}$ — die Auswahl von $r$ Elementen ist identisch mit der Auswahl von $n - r$ Elementen zum Ausschliessen.

Kombinationen (mit Wiederholung) — Sterne und Striche

Wenn die Reihenfolge keine Rolle spielt, aber Elemente wiederholt werden koennen (z. B. Verteilung identischer Objekte auf verschiedene Behaelter):

C_{\text{rep}}(n, r) = \binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!\,(n - 1)!}

Dies zaehlt die Anzahl nichtnnegativer ganzzahliger Loesungen von $x_1 + x_2 + \cdots + x_n = r$ .

Fixpunktfreie Permutationen (Subfakultaet)

Eine fixpunktfreie Permutation ist eine Anordnung, bei der kein Element an seiner urspruenglichen Position verbleibt. Die Anzahl ergibt sich aus:

D(n) = !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}

Aequivalent dazu die Rekurrenz: $!n = (n-1)(!(n-1) + !(n-2))$ mit Basisfaellen $!0 = 1$ und $!1 = 0$ . Asymptotisch gilt $D(n)/n! \to 1/e \approx 0{,}3679$ .

Catalan-Zahlen

Die $n$ -te Catalan-Zahl zaehlt korrekte Klammerungen, Polygon-Triangulierungen, nichtkreuzende Partitionen und gueltige Push/Pop-Folgen auf einem Stack:

C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\, n!}

Erste Werte: 1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

Pascalsche Regel

Jeder Eintrag im Pascalschen Dreieck ist die Summe der beiden Eintraege direkt darueber:

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Stirling-Naeherung

Fuer grosse $n$ kann die Fakultaet logarithmisch angenaehert werden:

\ln(n!) \approx n\ln(n) - n + \tfrac{1}{2}\ln(2\pi n)

Dieser Rechner zeigt die Stirling-Naeherung neben dem exakten BigInt-Ergebnis fuer $n > 170$ , sodass du beide vergleichen kannst.

Zusammenhang zwischen P und C

Permutationen und Kombinationen stehen in folgender Beziehung:

P(n, r) = C(n, r) \times r!

Anders gesagt ist die Permutationsanzahl immer genau $r!$ mal die Kombinationsanzahl. Das P-vs-C-Vergleichspanel des Rechners zeigt dieses Verhaeltnis explizit.

Durchgerechnete Beispiele

Beispiel 1: Lottoziehung (6 aus 49)

Beim Standard-Lotto 6 aus 49 werden 6 Kugeln aus 49 nummerierten Kugeln gezogen. Die Reihenfolge spielt keine Rolle und keine Kugel kann zweimal gezogen werden — wir verwenden also Kombinationen.

Setze $n = 49$ , $r = 6$ , Rechenart = Kombination.
Wende die Formel an: $C(49, 6) = \frac{49!}{6! \cdot 43!}$ .
Ausmultiplizieren: $\frac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6!} = \frac{10{.}068{.}347{.}520}{720}$ .

C(49, 6) = 13{.}983{.}816

Es gibt 13.983.816 moegliche Lottoscheine. Die Wahrscheinlichkeit, den Jackpot zu gewinnen, betraegt $1/13{.}983{.}816 \approx 7{,}15 \times 10^{-8}$ — etwa 1 zu 14 Millionen.

Beispiel 2: Gremium mit Rollen

Ein Verein mit 20 Mitgliedern waehlt einen Vorsitzenden, einen Stellvertreter und einen Schatzmeister. Da jede Rolle verschieden ist, zaehlt die Reihenfolge — verwende Permutationen.

Setze $n = 20$ , $r = 3$ , Rechenart = Permutation.
Berechne: $P(20, 3) = \frac{20!}{17!} = 20 \times 19 \times 18 = 6{.}840$ .

P(20, 3) = 6{.}840

Zum Vergleich: Waeren alle drei gleichberechtigte Mitglieder (ohne Rollen), $C(20, 3) = 1{.}140$ . Das Verhaeltnis ist $6{.}840 / 1{.}140 = 6 = 3!$ , was $P(n, r) = C(n, r) \times r!$ bestaetigt.

Beispiel 3: Wichteln — fixpunktfreie Permutation

Acht Kollegen machen ein Wichteln. Jede Person zieht einen zufaelligen Namen. Eine gueltige Zuordnung erfordert, dass niemand seinen eigenen Namen zieht — das ist eine fixpunktfreie Permutation.

Setze $n = 8$ , Rechenart = Fixpunktfreie Permutation.
Mit der Rekurrenz $!n = (n-1)(!(n-1) + !(n-2))$ und $!0 = 1$ , $!1 = 0$ :

!8 = 14{.}833

Von $8! = 40{.}320$ moeglichen Anordnungen sind 14.833 gueltige Wichtel-Zuordnungen. Die Wahrscheinlichkeit, dass eine zufaellige Mischung funktioniert, betraegt $14{.}833 / 40{.}320 \approx 36{,}8\,\%$ , was bereits nahe am asymptotischen Grenzwert von $1/e \approx 36{,}79\,\%$ liegt.

Beispiel 4: Eiskugeln mit Wiederholung

Eine Eisdiele bietet 10 Sorten an. Ein Kunde moechte 3 Kugeln in einer Schale (Reihenfolge der Kugeln spielt keine Rolle, Wiederholungen sind erlaubt). Verwende Kombinationen mit Wiederholung.

Setze $n = 10$ , $r = 3$ , Rechenart = Sterne & Striche.
Wende die Formel an: $C_{\text{rep}}(10, 3) = \binom{10 + 3 - 1}{3} = \binom{12}{3}$ .
Berechne: $\frac{12!}{3! \cdot 9!} = \frac{12 \times 11 \times 10}{6} = 220$ .

C_{\text{rep}}(10, 3) = 220

Es gibt 220 verschiedene moegliche Eisbecher.

Beispiel 5: DNA-Codon-Zaehlung

DNA-Codons sind Sequenzen aus 3 Nukleotiden aus dem Alphabet { $A, T, C, G$ } — die Reihenfolge zaehlt und Wiederholung ist erlaubt.

Setze $n = 4$ , $r = 3$ , Rechenart = Perm + Wdh.
Berechne: $4^3 = 64$ .

P_{\text{rep}}(4, 3) = 4^3 = 64

Es gibt 64 moegliche Codons — 61 codieren Aminosaeuren und 3 sind Stopp-Codons, was mit dem Standard-Genetikcode uebereinstimmt.

Beispiel 6: Passwort-Schluesselraum

Wie viele 8-Zeichen-Passwoerter koennen aus 94 druckbaren ASCII-Zeichen gebildet werden? Die Reihenfolge zaehlt und Zeichen koennen wiederholt werden.

Setze $n = 94$ , $r = 8$ , Rechenart = Perm + Wdh.
Berechne: $94^8 = 6{.}095{.}689{.}385{.}410{.}816$ .

94^8 \approx 6{,}1 \times 10^{15}

Ungefaehr 6 Billiarden moegliche Passwoerter. Bei 1 Milliarde Versuchen pro Sekunde wuerde das Durchprobieren dieses Schluesselraums etwa 70 Tage dauern.

Welche Rechenart soll ich verwenden?

Die Wahl der Formel haengt von zwei Fragen ab: Spielt die Reihenfolge eine Rolle? Koennen Elemente wiederholt werden?

Reihenfolge wichtig?	Wiederholung?	Formel	Beispiel
Ja	Nein	$P(n, r) = \frac{n!}{(n-r)!}$	Siegertreppchen bei einem Rennen
Ja	Ja	$n^r$	PIN-Codes, Passwoerter
Nein	Nein	$C(n, r) = \frac{n!}{r!(n-r)!}$	Lottoziehungen, Gremien
Nein	Ja	$\binom{n+r-1}{r}$	Eiskugeln, Verteilung identischer Objekte

Faustregel: Wenn das Umordnen der Auswahl ein anderes Ergebnis liefert, verwende Permutationen. Wenn das Umordnen dasselbe Ergebnis liefert, verwende Kombinationen.

Haeufige Missverstaendnisse

Missverstaendnis	Warum es falsch ist
Ein „Kombinationsschloss" verwendet Kombinationen	Ein Kombinationsschloss ist eigentlich ein Permutationsschloss — die Folge 1-2-9 unterscheidet sich von 9-2-1. Die Reihenfolge zaehlt, also gelten Permutationen.
$P(n, r)$ und $C(n, r)$ liefern unabhaengige Werte	Sie stehen in direkter Beziehung: $P(n, r) = C(n, r) \times r!$ . Permutationen zaehlen jede Anordnung jeder Kombination.
$C(n, r)$ ist undefiniert fuer $r > n$	Per Konvention gilt $C(n, r) = 0$ fuer $r > n$ — es gibt null Moeglichkeiten, mehr Elemente auszuwaehlen, als in der Menge vorhanden sind. Die Formel ergibt das sauber.
Wiederholung macht die Anzahl immer groesser	Stimmt fuer Kombinationen mit vs. ohne Wiederholung, aber $n^r$ vs. $P(n, r)$ kann in beide Richtungen gehen, abhaengig von den relativen Groessen von $n$ und $r$ .
„Wenn die Reihenfolge zaehlt" ist immer offensichtlich	Der Kontext bestimmt das. Ein Gremium aus {Alice, Bob} ist dasselbe unabhaengig von der Reihenfolge (Kombination), aber Vorsitzende=Alice, Stellvertreter=Bob ist anders als Vorsitzender=Bob, Stellvertreterin=Alice (Permutation).
Fixpunktfreie Permutationen sind selten fuer grosse $n$	Das Verhaeltnis $D(n)/n!$ konvergiert schnell gegen $1/e \approx 36{,}8\,\%$ . Fuer $n \geq 5$ ist etwa ein Drittel aller Permutationen fixpunktfrei.

Historischer Kontext

Die Untersuchung von Zaehlproblemen hat tiefe Wurzeln in verschiedenen Kulturen. Das Pascalsche Dreieck — die wohl wichtigste Struktur der elementaren Kombinatorik — wurde Jahrhunderte vor Blaise Pascals Formalisierung unabhaengig entdeckt.

Indien (ca. 200 v. Chr.): Der Sanskrit-Gelehrte Pingala beschrieb binaere Muster in poetischen Versmassen in seinem Chandahsastra und erzeugte damit das, was wir heute als Binomialkoeffizienten erkennen. Kommentare von Halayudha (ca. 10. Jh.) konstruierten das Dreieck explizit.
China (1261–1303): Yang Hui beschrieb das Dreieck 1261. Chu Shi-Chieh nahm es in sein Buch von 1303 Kostbarer Spiegel der vier Elemente auf und merkte an, dass es bereits seit ueber 300 Jahren bekannt war.
Persien (11. Jahrhundert): Al-Karaji und Omar Khayyam arbeiteten unabhaengig mit Binomialkoeffizienten in algebraischen und geometrischen Kontexten.
Europa (17. Jahrhundert): Blaise Pascal systematisierte die Eigenschaften des Dreiecks in seinem Traite du Triangle Arithmetique von 1654. Seine Korrespondenz mit Fermat ueber das „Teilungsproblem" begruendete die mathematische Wahrscheinlichkeitstheorie, mit Kombinationen als zentralem Werkzeug.

Die Subfakultaet (Anzahl fixpunktfreier Permutationen) wurde erstmals von Pierre Remond de Montmort 1708 untersucht und spaeter von Leonhard Euler weiterentwickelt. Das „Hutproblem" — bei dem $n$ Gaeste ihre Huete abgeben und jeder einen zufaelligen Hut zurueckbekommt — wurde zur kanonischen Illustration. Catalan-Zahlen wurden nach Eugene Charles Catalan (1838) benannt, obwohl Euler bereits im 18. Jahrhundert Polygon-Triangulierungen gezaehlt hatte.

Pascalsches Dreieck

Das Pascalsche Dreieck ist eine dreieckige Anordnung, in der Zeile $n$ , Position $k$ den Wert $\binom{n}{k}$ enthaelt. Es kodiert Zeilensummen ( $2^n$ ), palindromische Symmetrie, diagonale Folgen (natuerliche Zahlen, Dreieckszahlen) und Binomialentwicklungskoeffizienten.

Fuer eine detaillierte Behandlung der Konstruktion, wichtiger Muster (Hockey-Stick-Identitaet, Diagonalen), der Verbindung zum Binomialsatz und Anwendungen in Wahrscheinlichkeitstheorie und Zahlentheorie, siehe den Pascalsches-Dreieck-Generator-Leitfaden.

Verbindungen zu anderen Fachgebieten

Wahrscheinlichkeitsrechnung: Die Binomialverteilung verwendet $\binom{n}{k}$ direkt: $P(X = k) = \binom{n}{k} p^k (1-p)^{n-k}$ .
Informatik: Kombinationen tauchen bei der Analyse von Algorithmen auf (Teilmengenaufzaehlung, Hash-Kollisionen), und die Anzahl der Kanten in einem vollstaendigen Graphen $K_n$ ist $\binom{n}{2}$ .
Kryptographie: Permutationszaehlung liegt der Berechnung von Schluesselraumgroessen und der Birthday-Attack-Analyse zugrunde.
Erzeugende Funktionen: Die gewoehnliche erzeugende Funktion fuer die $n$ -te Zeile des Pascalschen Dreiecks ist $(1 + x)^n$ , was sie direkt mit dem Binomialsatz verbindet.

Haeufig gestellte Fragen

Was ist der Unterschied zwischen einer Permutation und einer Kombination?

Eine Permutation zaehlt Anordnungen, bei denen die Reihenfolge wichtig ist (z. B. { $A, B$ } und { $B, A$ } sind verschieden). Eine Kombination zaehlt Auswahlen, bei denen die Reihenfolge keine Rolle spielt (z. B. { $A, B$ } und { $B, A$ } sind gleich). Sie sind durch $P(n, r) = C(n, r) \times r!$ miteinander verbunden.

Wann sollte ich Kombinationen mit Wiederholung (Sterne und Striche) verwenden?

Verwende diese Methode, wenn du identische Objekte auf verschiedene Kategorien verteilst, oder wenn du dasselbe Element mehrfach waehlen kannst und die Reihenfolge keine Rolle spielt. Klassische Beispiele sind die Auswahl von Eiskugeln (Wiederholungen erlaubt), die Verteilung identischer Muenzen auf Personen oder das Zaehlen nichtnnegativer ganzzahliger Loesungen einer Gleichung wie $x_1 + x_2 + x_3 = 10$ .

Was ist eine fixpunktfreie Permutation?

Eine fixpunktfreie Permutation ist eine Anordnung, bei der kein Element an seiner urspruenglichen Position erscheint. Das klassische „Hutproblem" fragt: Wenn $n$ Personen ihre Huete abgeben und jede einen zufaelligen Hut zurueckbekommt, wie viele Anordnungen lassen niemanden seinen eigenen Hut erhalten? Das ueberraschende Ergebnis ist, dass diese Wahrscheinlichkeit sehr schnell gegen $1/e \approx 36{,}8\,\%$ konvergiert — fuer $n \geq 5$ weicht sie bereits weniger als 0,3 % vom Grenzwert ab.

Wofuer werden Catalan-Zahlen verwendet?

Catalan-Zahlen tauchen in Dutzenden von Zaehlproblemen auf: die Anzahl der Moeglichkeiten, $n$ Klammerpaare korrekt zu setzen, die Anzahl der Triangulierungen eines Polygons mit $n + 2$ Seiten, die Anzahl gueltiger Push/Pop-Folgen auf einem Stack und die Anzahl vollstaendiger Binaerbaeume mit $n + 1$ Blaettern.

Wie geht der Rechner mit sehr grossen Zahlen um?

Fuer $n \leq 170$ verwendet der Rechner Standard-Gleitkommaarithmetik. Fuer $n > 170$ wechselt er zu JavaScripts BigInt fuer exakte Berechnungen. Ergebnisse werden mit Tausendertrennzeichen angezeigt, zusammen mit der Stellenzahl und einer Stirling-Naeherung als Referenz. $n$ -Werte bis 10.000 werden unterstuetzt.

Warum endet die Visualisierung des Pascalschen Dreiecks bei Zeile 30?

Ab Zeile 30 werden die Zahlen zu gross und die Zellen zu klein, um sinnvoll in einem interaktiven Gitter dargestellt zu werden. Der Rechner berechnet $C(n, r)$ weiterhin exakt fuer jedes $n \leq 10{.}000$ — die visuelle Begrenzung ist rein eine Frage der Benutzerfreundlichkeit.

Ist dieser Rechner kostenlos?

Ja, vollstaendig kostenlos und ohne Registrierung. Alle sieben Rechenarten, Schritt-fuer-Schritt-Loesungen, das interaktive Pascalsche Dreieck und alle Visualisierungen sind ohne Einschraenkungen verfuegbar.

Quellen

Rosen, Kenneth H. Discrete Mathematics and Its Applications, 8. Aufl. McGraw-Hill, 2019. Kapitel 6 und 8.
NIST Digital Library of Mathematical Functions, Abschnitte 5.9 und 26.1–26.4. https://dlmf.nist.gov/
Weisstein, Eric W. „Permutation", „S뾬torial", „Catalan Number." MathWorld — A Wolfram Web Resource. https://mathworld.wolfram.com/
Flajolet, Philippe und Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
Wikipedia. „Pascalsches Dreieck", „Fixpunktfreie Permutation", „Catalan-Zahl." https://de.wikipedia.org/

Haftungsausschluss

Dieser Rechner dient ausschliesslich zu Bildungs- und Informationszwecken. Obwohl die zugrunde liegenden Algorithmen exakte Ergebnisse mittels BigInt-Arithmetik fuer Eingaben bis $n = 10{.}000$ liefern, koennen sehr grosse Berechnungen einen Moment im Browser benoetigen. Die Stirling-Naeherung ist ergaenzend und kann in niedrigeren Stellen vom exakten Ergebnis abweichen. Ueberprüfe kritische Berechnungen — insbesondere fuer Schaetzungen kryptographischer Schluesselraeume, statistische Modellierung oder akademische Einreichungen — immer durch unabhaengige Mittel.