Variation mit Duplikaten

Neue Frage »

wubi Auf diesen Beitrag antworten »
Variation mit Duplikaten
Meine Frage:

Gegeben sind n Karten und k freie Plätze. Von den n Karten gibt es Klassen 1, ..., s von gleichen Karten mit Anzahl . Die Karten werden ohne Wiederholung auf die Plätze aufgeteilt. Gesucht ist die Anzahl unterschiedlicher Belegungen.

Beispiel. Vier Karten mit den Zahlen 1, 2, 3, 3 und zwei freie Plätze.

1| 12
2| 13
3| 21
4| 23
5| 31
6| 32
7| 33

Gibt es für die Anzahl der Möglichkeiten

eine Formel?

Spezialfälle sind





Meine Ideen:
Leider keine Idee.
Kasen75 Auf diesen Beitrag antworten »

Hallo,

um zu klären, ob ich das richtig verstanden habe mal ein Beispiel:

6 Karten mit den Zahlen: 1,2,3,3,4,4
Somit 4 Klassen. Jetzt werden 3 Plätze belegt.

Mögliche Belegungen mit der ersten Zahl 1:








Macht sechs Variationen mit der Zahl 1 auf Platz 1. Mit den Zahlen 2-4 auf Platz Eins ergibt das dann insgesamt 24 Variationen.

Ich würde die Formel für die Berechnung der Anzahl der Variationen nehmen.
Edit: Ist dir diese denn geläufig? Denn im Titel steht ja schon das Stichwort "Variation".

In deiner Aufzählung hätte ich die 7 Möglichkeit weggelassen, da keine Wiederholung zugelassen ist.

Grüße.
wubi Auf diesen Beitrag antworten »

Jede Karte soll höchstens einmal benutzt werden. Gibt es eine Zahl nun auf zwei Karten, so kann man diese Zahl zwei mal verwenden.

Würde man das, wie bei deinem Beispiel nicht zulassen, dann reduziert sich das Problem ja auf V(n,k).

Bei
6 Karten mit den Zahlen 1,2,3,3,4,4 und 3 Plätzen
sind also
133
144
auch erlaubt.

Ist z.B.
Karte K1=1, K2=2, K3=2, ...
so sind die Belegungen
K1|K2|K3 und K1|K3|K2
gleich. Es gibt also in diesem Ast eine Möglichkeit weniger, als wenn alle Karten unterschiedlich wären.
wubi Auf diesen Beitrag antworten »

Sorry, es reduziert sich auf V(|M/~|,k).
wubi Auf diesen Beitrag antworten »

Das Problem wird auch Anzahl der Variationen einer Multimenge genannt.
Im englisch-sprachigen Raum bezeichnet man Variationen auch mit permutations.

Ich habe im Internet Informationen dazu gefunden. Die Links sind

* mathoverflow.net/questions/75447/computing-permutations-with-partial-duplicates
* m-hikari.com/ams/ams-2011/ams-17-20-2011/siljakAMS17-20-2011.pdf

Dort stehen auch Formeln.
Kasen75 Auf diesen Beitrag antworten »

jetzt habe ich das Problem verstanden. Ich nun mir jetzt folgendes gedacht:

Man nimmt die Formel für die Variation ohne Wiederholung und koppelt sie mit dem Binomialkoeffizienten.
Diese Formel gilt allerdings nur für k<n. n sind hierbei die Anzahl der Karten. Bei n=k ist die Formel relativ klar.



m=Anzahl an unterscheidbaren Karten
k=Anzahl der Plätze
=Anzahl der gleichen Karten der Klasse i

Der zweite Teil der Formel, bzw. bestimmte Summanden, wird nur unter bestimmten Bedingungen wirksam.
1. Bedingung: Eine mathematische Bedingung
2. Bedingung: Diese ergibt sich aus aus der Definition von

Bei den Karten 1,2,3,3 und 2 Plätzen ergibt die Formel:



Das wäre meine Idee. smile

Grüße.
 
 
wubi Auf diesen Beitrag antworten »

Diese Formel ist doch bekannt:

mit und
Die Formel folgt direkt aus dem Multinomialsatz.

Wenn die in Siljak angegebene Formel stimmt, so muss

sein. Jeder Summand hat den Wert k!.
Die Anzahl der Summanden muss sein.
Das stimmt mit der Mengendarstellung für die Kombinationen überein.

In de.wikipedia.org/wiki/Kombination_%28Kombinatorik%29#Kombination_ohne_Wiederholung
stehen die beiden Mengendarstellungen wie sie als Bedingungen auch für die alte und die neue Formel in Siljak zu finden sind.
Kasen75 Auf diesen Beitrag antworten »

Hallo,

ich habe deinen Beitrag nicht gelesen. Ich dachte nicht, dass du noch wach bist. Jedenfalls ist meine Idee nicht richtig, das habe ich auch schon gemerkt. Für diese Problem habe ich im Moment keine Idee. Ich hatte die Aufgabe einfach komplett falsch verstanden. Insbesondere den Teil mit "Die Karten werden ohne Wiederholung auf die Plätze aufgeteilt"
Du scheinst auf dem richtigen Weg zu sein, obwohl ich es nicht wirklich beurteilen kann.
Da musst du wohl warten, bis die jemand online ist, der dieses Problem besser versteht.

Grüße.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »