10 Buchstaben aus doppeltem Alphabet

14.10.2020, 20:19

Hakteus

10 Buchstaben aus doppeltem Alphabet

Meine Frage:
Hey,
meine Frage ist:
Wie viele Möglichkeiten gibt es 10 Buchstaben aus einem doppelten Alphabet zu wählen? Also ich habe jeden Buchstaben doppelt und soll nun 10 ziehen.

Meine Ideen:
Also Permutation ist es schon mal nicht, da ich nur 10 Buchstaben aus 52 Möglichen ziehe.
D.h. es bleibt Variation und Kombination übrig. Welches es von beiden ist, hängt davon ab, ob ich die Buchstaben im Nachhinein vertauschen darf oder nicht.

Angenommen die Reihenfolge ist wichtig, dann ist es Variation. An der Stelle habe ich mir das ganze einmal vereinfacht und nur 3 Buchstaben gezogen.
Da kann ich ja die Formel der Variation mit Wdh. anwenden, also n^k, und die alle Ergebnisse, bei denen ein Buchstabe dreimal vorkommt, abziehen.

also: (3^26) - 26

Gibt es noch weitere Möglichkeiten, an die Anzahl der Möglichkeiten zu kommen?
Denn wenn ich wieder auf mein ursprüngliches Problem zurückkomme, wird der zu subtrahierende Teil ja immer komplizierter.
Das läuft dann ja darauf hinaus, dass man für den zweiten Part eine extra Formel braucht.

14.10.2020, 20:30

HAL 9000

Auf diesen Beitrag antworten »

Ok, dir scheint es auf Auswahlen MIT Berücksichtigung der Reihenfolge anzukommen.

Man könnte zunächst die Anzahlen $\begin{eqnarray*} N_k \end{eqnarray*}$ derjenigen 10er-Auswahlen bestimmen, wo GENAU $\begin{eqnarray*} k \end{eqnarray*}$ Buchstaben jeweils zweimal vorkommen, die anderen $\begin{eqnarray*} 10-2k \end{eqnarray*}$ Buchstaben nur jeweils einmal, logischerweise macht das nur für $\begin{eqnarray*} k=0,1,\ldots,5 \end{eqnarray*}$ Sinn.

$\begin{eqnarray*} \binom{26}{k} \end{eqnarray*}$ ist die Auswahl dieser Doppelbuchstaben, und $\begin{eqnarray*} \binom{26-k}{10-2k} \end{eqnarray*}$ die der Einzelbuchstaben. Zu jeder solchen Auswahl gehören genau $\begin{eqnarray*} \frac{10!}{2^k} \end{eqnarray*}$ Permutationen, damit ist $\begin{eqnarray*} N_k = \binom{26}{k}\cdot \binom{26-k}{10-2k}\cdot \frac{10!}{2^k} \end{eqnarray*}$ , und die gesuchte Anzahl ist

$\begin{eqnarray*} N = \sum_{k=0}^5 N_k = \sum_{k=0}^5 \binom{26}{k}\cdot \binom{26-k}{10-2k}\cdot \frac{10!}{2^k} = 121\,216\,095\,000\,000 \end{eqnarray*}$ .

Wenn es nur um die Auswahlen OHNE Reihenfolge geht, dann geht das analog, man muss nur den Faktor $\begin{eqnarray*} \frac{10!}{2^k} \end{eqnarray*}$ in der Summe weglassen.

Zitat:

Original von Hakteus
Da kann ich ja die Formel der Variation mit Wdh. anwenden, also n^k, und die alle Ergebnisse, bei denen ein Buchstabe dreimal vorkommt, abziehen.

also: (3^26) - 26

Schön erklärt, aber falsch berechnet: Für dein Beispiel mit 3 Buchstaben kommt $\begin{eqnarray*} 26^3-26 \end{eqnarray*}$ heraus.

15.10.2020, 07:48

Finn_

Auf diesen Beitrag antworten »

Alternativer Weg. Sei $\begin{eqnarray*} A \end{eqnarray*}$ das Alphabet und $\begin{eqnarray*} a:=|A|=26 \end{eqnarray*}$ . Sei $\begin{eqnarray*} M \end{eqnarray*}$ die Indexmenge der Ziehungen und $\begin{eqnarray*} m:=|M|=10 \end{eqnarray*}$ . Unterscheiden wir die beiden Alphabete zunächst als $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} A' \end{eqnarray*}$ . Dann ergäbe sich die Anzahl als $\begin{eqnarray*} |X| \end{eqnarray*}$ , wobei $\begin{eqnarray*} X \end{eqnarray*}$ die Menge der Injektionen $\begin{eqnarray*} M\to A\cup A' \end{eqnarray*}$ ist.

Um den Unterschied zwischen $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} A' \end{eqnarray*}$ zu vergessen, betrachten wir die Faktormenge $\begin{eqnarray*} X/G \end{eqnarray*}$ , wobei $\begin{eqnarray*} G \end{eqnarray*}$ die Gruppe der Permutationen

$\begin{eqnarray*} A\cup A'\to A\cup A' \end{eqnarray*}$

ist, die einige der Buchstaben mit ihren gestrichenen Partnern tauschen. Eine Permutation ist dadurch bestimmt, welche der Buchstaben aus dem Alphabet $\begin{eqnarray*} A \end{eqnarray*}$ getauscht werden; die Werte für $\begin{eqnarray*} A' \end{eqnarray*}$ sind dadurch automatisch festgelegt. Das macht $\begin{eqnarray*} |G|=2^a \end{eqnarray*}$ . Außerdem wird jede Permutation nun als Binärzahl der Läne $\begin{eqnarray*} a \end{eqnarray*}$ betrachtet.

Gemäß dem Lemma von Burnside gilt

$\begin{eqnarray*} |X/G| = \frac{1}{|G|}\sum_{g\in G}|X^g|. \end{eqnarray*}$

Folgende Idee: Die Einsen aufzählen von $\begin{eqnarray*} k=0 \end{eqnarray*}$ bis $\begin{eqnarray*} k=a \end{eqnarray*}$ . Zu $\begin{eqnarray*} k \end{eqnarray*}$ Einsen gibt es $\begin{eqnarray*} \binom{a}{k} \end{eqnarray*}$ mögliche Permutationen $\begin{eqnarray*} g \end{eqnarray*}$ , und diese besitzen die gleiche Zahl $\begin{eqnarray*} |X^g| \end{eqnarray*}$ . Jede dieser Permutationen besitzt $\begin{eqnarray*} 2a-2k \end{eqnarray*}$ Nullen. Damit $\begin{eqnarray*} f\in X \end{eqnarray*}$ ein Fixpunkt von $\begin{eqnarray*} g \end{eqnarray*}$ ist, also $\begin{eqnarray*} g\circ f=f \end{eqnarray*}$ , darf $\begin{eqnarray*} f \end{eqnarray*}$ nur die Nullen erreichen. Dafür gibt $\begin{eqnarray*} (2a-2k)^{\underline m} \end{eqnarray*}$ Möglichkeiten, wobei mit dem Unterstrich die fallende Faktorielle gemeint ist.

Das macht

$\begin{eqnarray*} |X/G| = \frac{1}{2^a}\sum_{k=0}^a \binom{a}{k}(2a-2k)^{\underline m}. \end{eqnarray*}$

Kommt auch 121 216 095 000 000 bei raus. Habe für kleinere $\begin{eqnarray*} a,m \end{eqnarray*}$ zur Probe Brute-Force rechnen lassen.

15.10.2020, 08:39

HAL 9000

Auf diesen Beitrag antworten »

Wenn man erstmal begriffen hat, was du mit mit diesen "Nullen und Einsen in Permutationen" überhaupt meinst, dann ist es eine schöne Lösung. Augenzwinkern

Einen Teil zur Verwirrung trägt bei, dass du von $\begin{eqnarray*} k \end{eqnarray*}$ Einsen und $\begin{eqnarray*} (2a-2k) \end{eqnarray*}$ Nullen sprichst: Konsequent wäre m.E. gewesen, von $\begin{eqnarray*} (a-k) \end{eqnarray*}$ Nullen zu sprechen, die dann $\begin{eqnarray*} (2a-2k) \end{eqnarray*}$ Positionen in der Permutation $\begin{eqnarray*} g \end{eqnarray*}$ repräsentieren.

Neue Frage »

Antworten »

10 Buchstaben aus doppeltem Alphabet

Verwandte Themen