Variation mit Wiederholung und Bedingungen

23.01.2013, 11:21

Stochastikgeplagter

Variation mit Wiederholung und Bedingungen

Meine Frage:
Hallo liebe Matheboard-User,

ich wende mich mit einer Frage an Euch, an der ich schon ein Weilchen sitze, im Großen und Ganzen geht es um die Berechnung von Variationen mit Wiederholung, allerdings mit Bedingungen. Ich formuliere das Ganze mal zunächst allgemein, für Voraussetzungen und Ansätze siehe entsprechendes Feld:
Wie lautet die Formel zur Berechnung von Variationen mit Wiederholung, bei der gewisse Objekte an konkrete "Vorkommensbedingungen" gebunden sind? Es existiert dazu schon ein konkreter Ansatz, der bestätigt oder widerlegt werden kann.

Meine Ideen:
Es ist schwer für mich, mein Anliegen nur in einer einzigen Frage ohne vorige Definitionen auszudrücken.

Sei $\begin{eqnarray*} V_{n,k} = n^k \end{eqnarray*}$ Variation von $\begin{eqnarray*} n \end{eqnarray*}$ Objekten zur Klasse $\begin{eqnarray*} k \end{eqnarray*}$ mit Wiederholung. Als Anwendungsbeispiel kennen einige sicherlich das Ziehen von durchnummerierten, wohl unterscheidbaren Kugeln aus einer Urne mit Zurücklegen. Bis dahin ist alles nichts besonderes.

Ich möchte nun allerdings zu der Einhaltung der Reihenfolge, die die Variation von der Kombination unterscheidet, noch zusätzliche Bedingungen aufstellen:
Sei $\begin{eqnarray*} V_{n,k}^{c_1,\ldots ,c_m} \end{eqnarray*}$ Variation von $\begin{eqnarray*} n \end{eqnarray*}$ Objekten zur Klasse $\begin{eqnarray*} k \end{eqnarray*}$ mit den Bedingungen $\begin{eqnarray*} c_1,\ldots ,c_m \end{eqnarray*}$ .
Es gelte $\begin{eqnarray*} \forall i \in \mathbb N : c_i \in \mathbb N \cup \lbrace 0 \rbrace \end{eqnarray*}$ und $\begin{eqnarray*} \sum_{i=1}^m c_i \leq k \end{eqnarray*}$ .
Das $\begin{eqnarray*} c_i \end{eqnarray*}$ bedeutet hierbei, dass ein Objekt, welches (da es sich nur um Anzahlen handelt, nicht genauer beschrieben wird), genau $\begin{eqnarray*} c_i \end{eqnarray*}$ -mal vorkommt. Es gibt insgesamt $\begin{eqnarray*} m \end{eqnarray*}$ Stück davon, was bedeutet, dass $\begin{eqnarray*} m \end{eqnarray*}$ von den $\begin{eqnarray*} n \end{eqnarray*}$ Objekten in genau dieser Anzahl vorkommen. Alle Variationen, die diese Bedingungen nicht erfüllen, werden nicht hinzugezählt.

Praktisches Beispiel zur Veranschaulichung: Ich möchte mir nicht nur die Anzahl an Möglichkeiten ausrechnen, die es gibt, wenn ich aus einer Urne mit 10 nummerierten Kugeln 3 Stück mit Zurücklegen ziehe, sondern ich möchte wissen, wieviele Möglichkeiten es gibt, wenn ich schon weiß, dass eine (und nur eine!) der gezogenen Kugeln die '1' ist. Die gesuchte Zahl ist also $\begin{eqnarray*} V_{10,3}^{1} \end{eqnarray*}$

Man weiß also: $\begin{eqnarray*} V_{n,k} \geq V_{n,k}^{c_1,\ldots ,c_m} \end{eqnarray*}$ . Meine Formel, die ich bisher "entwickelt" habe (bei der ich mir allerdings sehr unsicher bin), lautet:
$\begin{eqnarray*} V_{n,k}^{c_1,\ldots ,c_m} = \frac{k!}{c_1!\cdots c_m!(k-\sum_{i=1}^m c_i)} (n-m)^{k-\sum_{i=1}^m c_i} \end{eqnarray*}$

Die Frage an die Matheprofis: Könnt ihr mir diese Formel beweisen? Oder könnt ihr sie widerlegen? Falls zweiteres, gibt es eine Alternative?

Hinweis zur besagten Formel: Es handelt sich hierbei um eine Art Verschmelzung der Formeln zur Berechnung von Permutationen mit Wiederholung sowie Variationen mit Wiederholung.

Ich bedanke mich schonmal für hilfreiche Antworten.

23.01.2013, 11:36

HAL 9000

Auf diesen Beitrag antworten »

Die Formel ist richtig (bis auf ein fehlendes Fakultätszeichen am Ende des Nenners), und dazu muss man keine neue kombinatorische Kategorie erfinden:

1.Sei $\begin{eqnarray*} c=\sum_{i=1}^m c_i \end{eqnarray*}$ , dann zählen wir erstmal die Möglichkeiten, die $\begin{eqnarray*} c \end{eqnarray*}$ aus $\begin{eqnarray*} k \end{eqnarray*}$ Positionen festzulegen, wo die Objekte mit den festgelegten Anzahlen landen sollen, das sind genau $\begin{eqnarray*} \binom{k}{c} \end{eqnarray*}$ Positionsauswahlen.

2.Auf diesen $\begin{eqnarray*} c \end{eqnarray*}$ Positionen sind nun die $\begin{eqnarray*} c \end{eqnarray*}$ Elemente genau festgelegt, nur ihre Reihenfolge noch nicht. Das geschieht mit Hilfe von Permutationen mit Wiederholung, deren Anzahl ist hier $\begin{eqnarray*} \frac{c!}{c_1!\cdot \ldots \cdot c_m!} \end{eqnarray*}$

3.Auf den $\begin{eqnarray*} (k-c) \end{eqnarray*}$ Restpositionen dürfen nun noch Elemente aus dem $\begin{eqnarray*} (n-m) \end{eqnarray*}$ -elementigen Rest der Grundmenge variiert werden (mit Wiederholung). Das macht $\begin{eqnarray*} (n-m)^{k-c} \end{eqnarray*}$ .

Das Produkt der drei Anzahlen ergibt die gesuchte Anzahl, die man mit $\begin{eqnarray*} \binom{k}{c} = \frac{k!}{c!(k-c)!} \end{eqnarray*}$ noch in deine Formel überführen kann:

$\begin{eqnarray*} \binom{k}{c}\cdot \frac{c!}{c_1!\cdot \ldots \cdot c_m!} \cdot (n-m)^{k-c} = \frac{k!}{c_1!\cdot \ldots \cdot c_m!(k-c)!} \cdot (n-m)^{k-c} \end{eqnarray*}$

25.01.2013, 10:24

Stochastikgeplagter

Auf diesen Beitrag antworten »

Vielen Dank für die schnelle und präzise Hilfe.

Leider muss ich mein Anliegen verallgemeinern. Es geht inzwischen um die Anzahl Variationen mit Wiederholung, bei der die Bedingungen sich auf ein maximales, minimales oder exaktes Vorkommen beziehen. Also:

$\begin{eqnarray*} V_{n,k}^{eq_1,\ldots,eq_a,min_1,\ldots,min_b,max_1,\ldots,max_c} = ? \end{eqnarray*}$

Analog zur obigen Aufführung bezeichne $\begin{eqnarray*} eq_i \end{eqnarray*}$ das $\begin{eqnarray*} eq_i \end{eqnarray*}$ -fache Vorkommen eines Objektes.
Dazu sei $\begin{eqnarray*} min_i \end{eqnarray*}$ die Bedingung, dass ein Objekt mindestens $\begin{eqnarray*} min_i \end{eqnarray*}$ -fach vorkommt, aber auch häufiger vorkommen darf.
Außerdem sei $\begin{eqnarray*} max_i \end{eqnarray*}$ die Bedingung, dass ein Objekt höchstens $\begin{eqnarray*} max_i \end{eqnarray*}$ -fach vorkommt, aber auch weniger oder gar nicht vorkommen darf.

Es gelte $\begin{eqnarray*} n \geq m=a+b+c \end{eqnarray*}$ , wobei $\begin{eqnarray*} n \end{eqnarray*}$ die Gesamtanzahl der Objekte, $\begin{eqnarray*} m \end{eqnarray*}$ die Gesamtanzahl der Bedingungen ungeachtet ihren Typs bezeichnen. Weiterhin gelten $\begin{eqnarray*} n\geq k \end{eqnarray*}$ und $\begin{eqnarray*} k \geq \left(\sum_{i=1}^{a}eq_i\right)+\left(\sum_{i=1}^{b}min_i\right) \end{eqnarray*}$ . Die Maximalbedingungen können $\begin{eqnarray*} k \end{eqnarray*}$ zunächst ruhig übersteigen, da sie dadurch ohnehin obsolet würden.

Ich hoffe, dass mir jemand von Euch helfen kann. Ich habe leider keine Ahnung, wie man die drei Geschichten unter einen Hut bringen kann und bin dankbar für jede hilfreiche Antwort.

28.01.2013, 12:38

Stochastikgeplagter

Auf diesen Beitrag antworten »

Also, bisher habe ich selbst diese Formel zur Abdeckung der Bedingungen minimales und exaktes Vorkommen, maximales ist nicht berücksichtigt bis jetzt.
Aber irgendwas mach ich falsch:

$\begin{eqnarray*} V^{min_1,\ldots,min_a,eq_1,\ldots,eq_b}_{n,k}=\frac{k!}{(k-min-eq)!min_1!\cdots min_a!eq_1!\cdots eq_b!}(n-b)^{k-min-eq} \end{eqnarray*}$

Dabei sei $\begin{eqnarray*} min=\sum_{i=1}^{a}min_i \end{eqnarray*}$ und $\begin{eqnarray*} eq=\sum_{i=1}^{b}eq_i \end{eqnarray*}$ .

Ich versuche noch weiter drauf zu kommen, falls ich es rausfinde, dann schreib ich es hier rein.

Ach, noch eine wichtige Voraussetzung: Es sei bekannt, dass eine Minimalbedingung nicht kleiner als 1 sein kann. Eine Maximalbedingung kann nicht größer als k sein und falls für ein gewisses Objekt eine Bedingung für das exakte Vorkommen existiert, dann existiert automatisch keine Minimal- oder Maximalbedingung für dasselbe Objekt.

28.01.2013, 18:57

HAL 9000

Auf diesen Beitrag antworten »

Dein Bestreben, alles und jedes in eine Formel zu packen, macht die Sache nicht gerade attraktiv für mögliche Helfer: So würde ich den ganzen Anteil der Objekte mit festen Anzahl schon mal vorab vom Problem abtrennen - der zugehörige Anzahlmultiplikationsfaktor kann genauso wie in den Punkten 1. und 2. meiner obigen Erklärung zum ersten Problem berechnet werden.

Also würde ich mich an deiner Stelle dann auf das Problem mit $\begin{eqnarray*} n \end{eqnarray*}$ Objekten konzentrieren, worunter genau $\begin{eqnarray*} k \end{eqnarray*}$ verschiedene sind mit den Anzahlbedingungen $\begin{eqnarray*} \geq min_i \end{eqnarray*}$ und $\begin{eqnarray*} \leq max_i \end{eqnarray*}$ für Objekt $\begin{eqnarray*} i \end{eqnarray*}$ , und das für $\begin{eqnarray*} i=1,\ldots,k \end{eqnarray*}$ .

Sollte für ein $\begin{eqnarray*} i \end{eqnarray*}$ keine Bedingung nach unten bestehen, dann kann man ja einfach $\begin{eqnarray*} min_i:=0 \end{eqnarray*}$ setzen, desgleichen kann man $\begin{eqnarray*} max_i:= n \end{eqnarray*}$ setzen, wenn keine Bedingung nach oben besteht.

Das wäre meine Vorstellung von einer übersichtlicheren Problemdarstellung - dein Wust mit unterschiedlichen Endindizes $\begin{eqnarray*} a,b,c \end{eqnarray*}$ , wo man am Ende überhaupt nicht mehr weiß, auf welche der $\begin{eqnarray*} k \end{eqnarray*}$ Objekte sich die einzelnen $\begin{eqnarray*} eq_i,min_i,max_i \end{eqnarray*}$ beziehen, finde ich extrem unübersichtlich. unglücklich

Was die eigentliche Anzahlberechnung dann betrifft: Da sehe ich eigentlich kaum eine einfachere Chance, als

$\begin{eqnarray*} \frac{n!}{n_1!\cdot \ldots n_k!} \end{eqnarray*}$

über alle Tupel $\begin{eqnarray*} (n_1,\ldots,n_k) \end{eqnarray*}$ mit $\begin{eqnarray*} n_1+\ldots,n_k=n \end{eqnarray*}$ sowie $\begin{eqnarray*} min_i \leq n_i \leq max_i \end{eqnarray*}$ für alle $\begin{eqnarray*} i=1,\ldots,k \end{eqnarray*}$ zu summieren.

29.01.2013, 09:20

Stochastikgeplagter

Auf diesen Beitrag antworten »

Ich würde auch gerne zumindest die Typen von Bedingungen voneinander trennen. Aber ich weiß vorher nicht, ob Bedingungen da sind und falls ja, welche und wieviele. Auch kann ich aus technischen Gründen z.B. nicht die Option wahrnehmen, erst ganz normal alle Variationen mit $\begin{eqnarray*} n^k \end{eqnarray*}$ zu berechnen und dann jene abzuziehen, die die Bedingungen nicht erfüllen.
Das liegt daran, dass die Variationen von einem C-Programm ausgerechnet werden sollen, dass einen eigenen improvisierten Zahlendatentyp dafür nimmt, da selbst der größte verfügbare Datentyp "unsigned long" mit einem Wertebereich etwas über 4 Milliarden von der kombinatorischen Explosion schnell gesprengt wird.

Der so selbst definierte Datentyp hat ein Wertebereich von 0 bis 999 Quintilliarden. Natürlich wird auch er irgendwann überlaufen, aber erst für weitaus größere Eingaben; und sein Überlauf ist zumindest so behandelt, dass er sich "weigert", weiterzuzählen und eine Meldung auswirft.

Wie dem auch sei, ich muss die Variationen direkt berechnen, denn mit einem $\begin{eqnarray*} n^k \end{eqnarray*}$ bin ich möglicherweise schon über die 999 Quintilliarden hinausgeschossen, und kann die Zahl wegen Überlauf dann wegwerfen.

Zunächst hatte ich vor, das pro Bedingungstyp zu tun, hatte mit gleichen Anzahlen begonnen, aber musste dann feststellen, dass der berechnete Wert zu hoch ist - Minimum und Maximum sind ja nicht mit drin bisher. Für die restlichen Zeichen müssen sie gleich mitbedacht werden, sonst kann das oben gennte Problem trotzdem auftreten.

Ich kann außerdem für die Minimalbedingungen nicht genau die gleiche Verfahrensweise anwenden wie für die Gleichheitsbedingungen: Permutationen mit Wiederholungen ausrechnen und mit der verbliebenen Objektanzahl, zu dem die Variationen berechnet wurden multiplizieren.
Lasse ich die Objektanzahl bei $\begin{eqnarray*} (n-b) \end{eqnarray*}$ , also allen Objekten außer jenen, die Gleichheitsbedingungen haben, so habe ich Duplikate enthalten, genau dann, wenn Zeichen die Restpositionen belegen, für die Minimalbedingungen gelten.
Entferne ich die betroffenen Objekte hingegen ganz, also $\begin{eqnarray*} (n-b-a) \end{eqnarray*}$ , dann unterschlage ich jene Variationen ganz, die bei vorheriger Option als Duplikate auftraten.

Ich verdeutliche das mal an einem einfachen Beispiel:
Ich ordne jeweils zwei Ziffern von 0 bis 9 an. Ohne Bedingungen ist offensichtlich, dass es 100 Variationen gibt. Nun setze ich die Bedingung, dass eine Ziffer (hier konkret die 0) mindestens einmal vorkommen muss.
Wenn ich die Permutationen mit Wiederholung ausrechne, berechne ich die Anzahl dieser "Masken":
$\begin{eqnarray*} \begin{vmatrix} 0 & \star \\ \star & 0 \end{vmatrix} \end{eqnarray*}$
Auf anderer Seite werden die Variationen für die restlichen Positionen berechnet:
$\begin{eqnarray*} \begin{vmatrix} 0 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \end{vmatrix} \end{eqnarray*}$ .
Beides wird normal multipliziert, welches diesen Möglichkeiten entspricht. Das Duplikat ist rot markiert:
$\begin{eqnarray*} \begin{vmatrix} 0 & 0\\ 0 & 1\\ 0 & 2\\ 0 & 3\\ 0 & 4\\ 0 & 5\\ 0 & 6\\ 0 & 7\\ 0 & 8\\ 0 & 9\\ \textcolor{red}0 & \textcolor{red}0\\ 1 & 0\\ 2 & 0\\ 3 & 0\\ 4 & 0\\ 5 & 0\\ 6 & 0\\ 7 & 0\\ 8 & 0\\ 9 & 0\\ \end{vmatrix} \end{eqnarray*}$

Die Formel ergibt je nach Vorgehensweise 18 (ohne beide Werte) oder 20 (mit beiden), die tatsächliche Anzahl ist jedoch 19.

Falls jemand noch eine Idee haben sollte, immer her damit. An der Darstellungsweise kann ich leider nichts ändern, das kommt nunmal nach dem Parsen der Eingabe raus.

30.01.2013, 20:35

Stochastikgeplagter

Auf diesen Beitrag antworten »

Ich bin mir ziemlich sicher, dass dieses Monstrum die Minimal- und Gleichheitsbedingungen unter einen Hut bringt. Da ich es nur sehr unzureichen überprüfen kann, sage ich aber, dass es den wirklichen Wert vermutlich nur approximiert.
Ich schreibe das jetzt auf, weil es ja vielleicht in Zukunft doch jemanden gibt, der das wissen muss und weil vielleicht auch jemand in der Lage ist, die Maximalbedingungen hier noch unterzubringen. Nicht zuletzt kann jemand diese Formel vielleicht auch doch komplett widerlegen.

$\begin{eqnarray*} V_{n,k}^{min_1,\ldots,min_a,eq_1,\ldots,eq_b}= \end{eqnarray*}$

$\begin{eqnarray*} \left\lfloor\frac{\frac{k!}{(k-min-eq)!min_1!\cdots min_a! eq_1!\cdots eq_b!}\left((n-b-a)^{k-min-eq}+(n-b)^{k-min-eq}\right)}{2}\right\rfloor \end{eqnarray*}$

30.01.2013, 20:57

HAL 9000

Auf diesen Beitrag antworten »

Nehmen wir nur zwei verschiedene Kugeln mit Mindestanzahlen 1, also $\begin{eqnarray*} n=2,min_1=min_2=1 \end{eqnarray*}$ . Wir ziehen nun $\begin{eqnarray*} k \end{eqnarray*}$ -mal, $\begin{eqnarray*} k \end{eqnarray*}$ bleibe dabei zunächst offen.

Offenbar gibt es dann $\begin{eqnarray*} 2^k-2 \end{eqnarray*}$ Ziehungsergebnisse, die der Bedingung "von jedem Typ mindestens eine Kugel" genügen.

Nach deiner Formel (korrigiere mich, wenn ich sie falsch lese) kommt hingegen

$\begin{eqnarray*} \frac{k!\cdot ((2-2)^{k-2}+2^{k-2})}{2(k-2)!1!1!} = k(k-1)2^{k-3} \end{eqnarray*}$

heraus - irgendwie sehr weit entfernt zur wirklichen Anzahl $\begin{eqnarray*} 2^k-2 \end{eqnarray*}$ . verwirrt

Zitat:

Original von Stochastikgeplagter
Ich schreibe das jetzt auf, weil es ja vielleicht in Zukunft doch jemanden gibt, der das wissen muss und weil vielleicht auch jemand in der Lage ist, die Maximalbedingungen hier noch unterzubringen.

Aha.

Neue Frage »

Antworten »

Variation mit Wiederholung und Bedingungen

Verwandte Themen