Anzahl der k-Permutationen über eine Multimenge

24.02.2013, 14:55

Aachener

Anzahl der k-Permutationen über eine Multimenge

Meine Frage:
Hallo,

ich rätsel und rätsel hier, aber ich komme nicht weiter - vielleicht gibt es hier ja ein paar Kombinatorik-Cracks, die mir helfen können Augenzwinkern

.

Ich habe eine Multimenge M mit $\begin{eqnarray*} | M | = n \end{eqnarray*}$ und m nicht unterscheidbaren Elementen in M, wobei $\begin{eqnarray*} m < n \end{eqnarray*}$ gilt. Nun suche ich die Anzahl der k-Permutationen bzw. Variationen über M, wobei allerdings wichtig ist, dass es tatsächlich n Elemente in der Multimenge bleiben. Einfach die doppelten rausstreichen funktioniert also leider nicht Augenzwinkern

- für die Gesamtzahl ist jedes Element verschieden, zur Unterscheidung der k-Permutationen aber nur tatsächlich verschiedene Elemente.

Man könnte auch als Beispiel zum Verständnis hinzufügen: Die Multimenge M ist ein Alphabet, aus dem ohne Zurücklegen gezogen wird, wobei die Reihenfolge ist für die entstehenden Wörter natürlich wesentlich ist, doppelte Buchstaben aus M aber nicht unterschieden werden können, und mich nur die Wörter mit k Buchstaben interessieren.

Für Hilfe wäre ich sehr dankbar - meine eigenen Lösungsansätze waren bisher wie folgt:

Meine Ideen:
Die Anzahl der k-Permutationen über eine Menge A beträgt bekanntlich $\begin{eqnarray*} \frac{n!}{(n-k)!} \end{eqnarray*}$ .

Im Sinne des Polynomialkoeffizienten hatte ich nun überlegt, dass $\begin{eqnarray*} \frac{n!}{(n-k)!*a_0!*...*a_m!} \end{eqnarray*}$ der richtige Weg zum Ziel sein könnte, wobei $\begin{eqnarray*} a_i \end{eqnarray*}$ die Anzahl des i-ten vorkommenden Elements bezeichnet. Also wollte ich die Gesamtzahl der k-Permutationen durch die durch Multiplikation verknüpften Fakultäten der Anzahlen der gleichen Elemente teilen. In meinem Beispiel (n=102, m=12, k=3) bekomme ich so allerdings einen Wert kleiner als eins heraus - kann also nicht sein.

Rechne ich nur $\begin{eqnarray*} \frac{n!}{a_0!*...*a_m!} \end{eqnarray*}$ , so erhalte ich ja die Anzahl der n-Permutationen, die mit meinem Beispielwerten ziemlich groß ist (~1,4*10^72). Wie berücksichtige ich am effektivsten, dass mich letztendlich nur die ersten k Elemente interessieren?

Für eure Hilfe bereits im Voraus vielen herzlichen Dank!

24.02.2013, 16:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Expandiere $\begin{eqnarray*} (x_1+x_2+\cdots+x_m)^k \end{eqnarray*}$ und betrachte dann nur die Monome $\begin{eqnarray*} x_1^{k_1}x_2^{k_2}\ldots x_m^{k_m} \end{eqnarray*}$ , für die $\begin{eqnarray*} k_1\leq a_1,\ldots k_m\leq a_m \end{eqnarray*}$ gilt. Deren Koeffizienten summiert ergibt die von dir gesuchte Anzahl.

So ähnlich würde Mystic wohl das Problem lösen, und mir fällt hier ehrlich gesagt auch nichts effizienteres ein. Wenn die Reihenfolge keine Rolle spielen würde (d.h. Kombinationen statt Variationen), dann kriegt man mit Siebformel noch eine halbwegs vernünftige Anzahlformel hin, aber das ist hier leider so nicht übertragbar.

EDIT: Wenn ich mir so dein (n=102, m=12, k=3) anschaue, dann würde sich als Rechenvereinfachung noch folgendes anbieten:

Für diejenigen $\begin{eqnarray*} i \end{eqnarray*}$ mit $\begin{eqnarray*} a_i\geq k \end{eqnarray*}$ gibt es ja keine Auswahlbeschränkung hinsichtlich der Anzahl ausgewählter Elemente vom Typ $\begin{eqnarray*} i \end{eqnarray*}$ - also nehmen wir die "aus dem Spiel":

O.b.d.A. ordnen wir die m verschiedenen Elemente so an, dass $\begin{eqnarray*} a_1<k,\ldots,a_r<k \end{eqnarray*}$ sowie $\begin{eqnarray*} a_{r+1}\geq k,\ldots,a_m\geq k \end{eqnarray*}$ gilt, dabei ist $\begin{eqnarray*} 0\leq r\leq m \end{eqnarray*}$ . Dann kann obiges Verfahren mit $\begin{eqnarray*} s:=m-r \end{eqnarray*}$ auch schlicht so modifiziert werden:

Zitat:

Expandiere $\begin{eqnarray*} (x_1+x_2+\cdots+x_r+s)^k \end{eqnarray*}$ und betrachte dann nur die Monome $\begin{eqnarray*} x_1^{k_1}x_2^{k_2}\ldots x_r^{k_r} \end{eqnarray*}$ , für die $\begin{eqnarray*} k_1\leq a_1,\ldots k_r\leq a_r \end{eqnarray*}$ gilt. Deren Koeffizienten summiert ergibt die von dir gesuchte Anzahl.

Zumindest im Fall $\begin{eqnarray*} s\gg r \end{eqnarray*}$ ergibt das eine ordentliche Rechenersparnis.

24.02.2013, 18:22

Aachener

Auf diesen Beitrag antworten »

Hallo,

das Rechnen mag zwar noch umständlich sein, das lässt sich aber mit ein bisschen Mathematica und Matlab sicher machen. Daher ist das genau der Lösungsansatz, der mir bisher gefehlt hat smile

.

Bzgl. der Monome - da betrachte ich aber auch die mit mehreren Variablen, wobei ich aber natürlich nur den Exponenten der $\begin{eqnarray*} x_i \end{eqnarray*}$ -Variable berücksichtige, die ich gerade untersuche - richtig?

Hast du zu diesem Lösungsansatz vielleicht noch ein Stichwort, sodass ich mich da selber nochmal etwas ausführlicher in die Materie einlesen kann?

Vielen Dank für deine Hilfe und noch einen schönen Sonntagabend!

24.02.2013, 19:23

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Aachener
Bzgl. der Monome - da betrachte ich aber auch die mit mehreren Variablen, wobei ich aber natürlich nur den Exponenten der $\begin{eqnarray*} x_i \end{eqnarray*}$ -Variable berücksichtige, die ich gerade untersuche - richtig?

Ja klar, Monome mit mehreren Variablen - aber die Exponentenbedingung ist für alle Faktoren des Monoms zu erfüllen!

24.02.2013, 20:04

Aachener

Auf diesen Beitrag antworten »

Ah, okay, dann versteh ich das jetzt auch richtig - ich hatte das vorher so gelesen gehabt, als sei die Darstellung des (einzigen) Monoms sei eine Aufzählung ... Augenzwinkern

.

Rechne ich also nachher mal damit aus. Danke dir! Freude

Neue Frage »

Antworten »

Anzahl der k-Permutationen über eine Multimenge

Verwandte Themen