Permutation m. Wiederholung und Nebenbedingung

Neue Frage »

heinzzz Auf diesen Beitrag antworten »
Permutation m. Wiederholung und Nebenbedingung
Hi,
Ich moechte die Anzahl moeglicher Permutationen berechnen.

Ich habe n Objekte wobei jeweils k Objekte identisch sind. Laut wikipedia gibt es in diesem Fall n!/k! Permutationen. Ich habe nun eine weiter Nebenbedingung welche einige Permutationen ausschliesst welches ich an folgenden Beispiel erklaere.

Sei n=9 und k=3, dann gibt es die folgenden Permutationen

1. AAABBBCCC - Erlaubt
2. ABCABCABC - Erlaubt
3. AABBCCABC - Nicht erlaubt
...

Ich habe nun folgende Einschraenkung. Fuer alle paarweisen Permutationen muss gelten: Jedes Objekt darf nur eine uebereinstimmende Position haben. Dies ist z.b. fuer Permutation 1 und 2 gegeben hier stimmt z.b. Objekt A nur an Index 1 miteinander ueberein wohin gegen in 1 und 3 Index 1 und 2 uebereinstimmt.

Wie kann ich die Anzahl Permutationen unter dieser Nebenbedingung berechnen? Ein Suchbegriff, Buch, Papier als Hinweis waere grossartig.

Danke!
HAL 9000 Auf diesen Beitrag antworten »

Ich verstehe das so: Du betrachtest eine Teilmenge aller Permutationen mit folgender Eigenschaft:

Nimmt man beliebige zwei Permutationen aus dieser Menge und betrachtet alle Positionen, an denen diese zwei Permutationen übereinstimmen: Dann darf jedes der n Objekte höchstens einmal an diesen Übereinstimmungspositionen auftreten.

Du willst nun die maximale Mächtigkeit wissen, die eine solche Menge annehmen kann. Ich formuliere das so, denn diese Menge ist durchaus nicht eindeutig.

Insgesamt scheint das Problem ziemlich knifflig.
heinzzz Auf diesen Beitrag antworten »

Hallo Hal,

eigentlich korrekt formuliert, allerdings hat sich mein Problem mittlerweile verandert smile . Und zwar darf jedes Symbol max. einmal mit jedem anderen Symbol uebereinstimmen und dies fuer alle beliebigen permutationen.

Das folgende Beispiel sei also nicht erlaubt da das Paar A,B zweimal (an Stelle 4 und 5 auftaucht)

1. AAABBBCCC - Erlaubt
2. ABCAACBBC - Nicht erlaubt

Ich denke der erste Schritt zur Loesung waere das Problem korrekt zu Formulieren, bereits hier tue ich mich schwer.
Neue Frage »
Antworten »



Verwandte Themen

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