Kombinatorik: Anzahl Kombinationen ohne Wiederholung

12.01.2016, 22:29

rth2

Kombinatorik: Anzahl Kombinationen ohne Wiederholung

Meine Frage:
Hallo,

ich sitze vor einer Aufgabe, bei der ich versuchen soll, aus einem gegebenen Alphabet {E, E, F, F, H, O, R, S, S, T, X} Buchstabenkombinationen zu bilden.

Möglich sind alle Kombinationen: Begonnen von $\begin{eqnarray*} \epsilon \end{eqnarray*}$ über EF, EHOT usw.

Kurzum: Es soll die Anzahl aller möglichen, unterscheidbaren Kombinationen mit den Längen 0 bis 11 ermittelt werden, wobei jeder Buchstabe nur so oft verwendet werden darf, wie er in dem Alphabet vorkommt.

Mein Problem ist, dass ich zwar alle möglichen Kombinationen berechnet kann (siehe meine Lösungs-Idee), aber ich weiß nicht, wie ich die nicht unterscheidbaren Kombinationen (z.B. " $\begin{eqnarray*} F_{1} F_{2} HO \end{eqnarray*}$ " ist als Buchstabenkombination nicht unterscheidbar von " $\begin{eqnarray*} F_{2} F_{1} HO \end{eqnarray*}$ ") ermitteln und damit abziehen kann (das Problem tritt ab der Länge 2 auf - wobei bei 2 ist es noch einfach, da einfach 3 abgezogen werden muss).

Ich bin über jeden Hinweis dankbar!

Lg

Meine Ideen:
Alle möglichen Kombinationen errechne ich über die Summe von "Ziehen ohne Zurücklegen unter Beachtung der Reihenfolge":
$\begin{eqnarray*} \sum\limits_{k=0}^{11} \frac{11!}{(11-k)!} \end{eqnarray*}$

12.01.2016, 23:19

HAL 9000

Auf diesen Beitrag antworten »

Tja, so einfach geht es offensichtlich nicht.

Erstmal zusammentragen: Zur Verfügung stehen 3 Buchstaben E,F,S je zweimal, und 5 Buchstaben H,O,R,T,X je einmal.

Wir zählen nun die Wörter mit folgender Eigenschaft:

1) $\begin{align*} i \end{align*}$ Buchstaben je zweimal,
2) $\begin{align*} k \end{align*}$ Buchstaben je einmal.

Offenbar ist $\begin{align*} 0\leq i\leq 3 \end{align*}$ sowie $\begin{align*} 0\leq k\leq 8-i \end{align*}$ . Zur Auswahl der Buchstaben aus den Kategorien gibt es zunächst $\begin{align*} \binom{3}{i}\cdot \binom{8-i}{k} \end{align*}$ Möglichkeiten. Für jede feste so gewählte Buchstabenauswahl gibt es nun genau $\begin{align*} \frac{(2i+k)!}{2^i} \end{align*}$ mögliche Permutationen mit Wiederholung.

Macht summa summarum $\begin{align*} \sum_{i=0}^3 \sum_{k=0}^{8-i} \binom{3}{i}\cdot \binom{8-i}{k}\cdot \frac{(2i+k)!}{2^i} = 13\,938\,221 \end{align*}$ .

13.01.2016, 14:29

rth2

Auf diesen Beitrag antworten »

Vielen dank HAL 9000 für deine Mühe.

Auf die Idee, die Buchstaben vorab zu klassifizieren bin ich nicht gekommen. Durch die Trennung erhält man auch die Möglichkeit, die Permutationen entsprechend zu beeinflussen sollten 2 oder mehr doppelte Buchstaben vorkommen (also sodass nur die Kombination $\begin{eqnarray*} E_{1} E_{2} \end{eqnarray*}$ und nicht auch die Kombination $\begin{eqnarray*} E_{2} E_{1} \end{eqnarray*}$ in den möglichen Permutationen mitgezählt werden).

Vielen Dank nochmal
LG

13.01.2016, 14:39

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von rth2
also sodass nur die Kombination $\begin{eqnarray*} E_{1} E_{2} \end{eqnarray*}$ und nicht auch die Kombination $\begin{eqnarray*} E_{2} E_{1} \end{eqnarray*}$ in den möglichen Permutationen mitgezählt werden

Genau das korrigiert ja der Nenner $\begin{align*} 2^i \end{align*}$ .

Neue Frage »

Antworten »

Kombinatorik: Anzahl Kombinationen ohne Wiederholung

Verwandte Themen