WikiDer > Kombinatorik

Permutationen von drei Elementen (rot, grün und blau)

Kombinatorik oder Kombinationstheorie ist ein Zweig der Mathematik. In Kombinatorik studiert manStudent endliche Mengen von Objekte die bestimmte Eigenschaften erfüllen. Insbesondere beschäftigt man sich dabei mit dem „Zählen“ von Objekten Kollektionen und Bestimmen, ob es bestimmte "optimale" Objekte in einer Sammlung gibt. Da es in der Kombinatorik hauptsächlich um das Zählen geht, wird sie die „Kunst des Zählens“ genannt.

Vasenmodell

Mit einem Vasenmodell lassen sich eine Reihe von Zählproblemen lösen^[1]. Aus einer Vase mit ${displaystyle n}$ (verschiedene) Murmeln werden ${displaystyle k}$ Murmeln genommen (gezeichnet). Wir können die gezogene Murmel zurücklegen oder nicht und wir können die gezogene Murmel zurücknehmen ${displaystyle k}$ Murmeln erinnern sich an die Reihenfolge oder nicht. Wir sprechen von Ziehen mit oder ohne Ersatz und von geordnetem oder ungeordnetem Ergebnis (die Reihenfolge kann wichtig sein oder nicht).

Variation wir ziehen ${displaystyle k}$ mal aus einer Sammlung von ${displaystyle n}$ Elemente, ohne zurückzulegen und erinnere dich an die Auftrag. Für die erste Ziehung gibt es ${displaystyle n}$ Chancen. Für jede weitere Ziehung gibt es immer eine Möglichkeit weniger als für die vorherige. Eine gezeichnete Zeile heißt a Variation. Davon gibt es ${displaystyle V(n,k)={frac {n!}{(n-k)!}}}$ Beispiel: Vier Freunde haben etwas zu feiern und haben einen ganzen Saal gemietet. Es gibt 200 Sitzplätze und sie sitzen einfach überall. Wie viele Möglichkeiten gibt es? ${displaystyle {frac {200!}{(200-4)!}}=200 imes 199 imes 198 imes 197}$ Wenn wir alle ${displaystyle n}$ Elemente zeichnen, also wenn ${Anzeigestil k=n,}$ Wir bekommen eine Möglichkeit, die zu bekommen ${displaystyle n}$ Elemente des Sets auf Auftrag stellen. Eine solche Folge heißt a Permutation. Davon gibt es ${displaystyle ncdot (n-1)cdot punkte cdot 2cdot 1=n!}$ Beispiel: Wir sortieren ein Kartenspiel (ziehen Sie 52 Karten vom Stapel); es sind dann 52! Chancen

Wiederholungsvariation wir ziehen ${displaystyle k}$ mal aus einer Sammlung von ${displaystyle n}$ Elemente, mit zurücklegen und erinnere dich an die Auftrag. Für jeden der ${displaystyle k}$ Ziehungen sind da ${displaystyle n}$ Chancen. Eine gezeichnete Zeile heißt a Variation wiederholen. Davon gibt es ${displaystyle n^{k}}$ Beispiel: Wie viele PINs gibt es? Du wählst also 4 mal aus 10 Ziffern ${Displaystil 10^{4}=10.000}$

Kombination wir ziehen ${displaystyle k}$ mal aus einer Sammlung von ${displaystyle n}$ Elemente, ohne zurückzulegen und schau außer Betrieb. Einer gezogen ${displaystyle k}$-Nummer heißt a Kombination. Wir können erst auf die Reihenfolge achten und sie dann vergessen. Es gibt dann ${displaystyle k!}$ Variationen, die gleich sind ${displaystyle k}$Ertragsnummer. Die Anzahl der verschiedenen Kombinationen ist also: ${displaystyle {n wähle k}={n! über k!(n-k)!}}$ Beispiel: Wie viele verschiedene Teams mit 3 Teilnehmern können wir aus 10 Teilnehmern bilden. es gibt ${displaystyle { inom {10}{3}}={frac {10!}{3!7!}}=120}$.

Kombination wiederholen wir ziehen ${displaystyle k}$ mal aus einer Sammlung von ${displaystyle n}$ Elemente, mit zurücklegen und schau außer Betrieb. Einer gezogen ${displaystyle k}$-Nummer heißt a Kombination wiederholen. Wir können so etwas tun ${displaystyle k}$-Nummer von jedem der each beschreiben ${displaystyle n}$ Elemente geben an, wie oft es ausgewählt wurde. Dies kann grafisch erfolgen, indem für jedes Element so viele Nullen geschrieben werden, wie es gewählt wurde, und eine 1 zwischen den Nullen der verschiedenen Elemente als Trennzeichen schreiben. Die Anzahl der verschiedenen Wiederholungskombinationen ist dann die Anzahl der möglichen Sequenzen bestehend aus ${displaystyle k}$ mal eine 0 und ${Anzeigestil n-1}$ mal eine 1. Wir müssen aussteigen ${displaystyle kn-1}$ dort in die reihe stellen ${displaystyle k}$ Geben Sie an, wo eine 0 platziert wird. Die Zahl ist also gleich der Zahl der Kombinationen von ${displaystyle k}$ von ${displaystyle kn-1:}$ ${displaystyle {k n-1 wählen Sie k} = {(k n-1)! über k!(n-1)!}}$ Beispiel: Auf wie viele Arten kann man 5 Eier färben, wenn man 3 Farben hat. So ${Anzeigestil k=5}$ und ${Anzeigestil n=3.}$ Das ist also möglich ${displaystyle {5 3-1 wählen 5}={7! in 5!2!}=21}$ Wege.

Anwendung

Auf wie viele Arten kann ${displaystyle n}$ gleiche Murmeln werden verteilt unter ${displaystyle k}$ verschiedene Behälter, damit kein Behälter leer ist?

Legen Sie eine Murmel in jede Schüssel. es bleiben ${displaystyle n-k}$ Über. Diese werden noch über eine Rapportkombination auf die Trays verteilt, also ab so ${displaystyle n-k}$ von ${Anzeigestil k;}$ für jede der verbleibenden Murmeln wird bestimmt, in welchem ​​Behälter sie kommt. Es gibt also:

${displaystyle {n-1 wähle n-k}={n-1 wähle k-1}}$

Chancen.

Verweise

Siehe die Kategorie Kombinatorik von Wikimedia Commons für Mediendateien zu diesem Thema.