Permutationen mit Einschränkun < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Aufgabe | | Wir befinden uns am Theater. Es gibt x Rollen von x Schauspielern zu besetzen. Allerdings kann jeder einzelne Schauspieler nur y Rollen spielen. Für y gilt: y < x. Wie viele verschiedene Kombinationen von Schauspielern und Rollen gibt es? |
Ich habe keine Ahnung wie ich das y einbringen kann. Ich weiß nur, wenn y=x, dann ist die Lösung x!, da y aber kleiner sein muss kann diese Lösung nicht mehr hinkommen.
|
|
| |
|
Hallo Profi,
Erst einmal muss man voraussetzen, dass auch alle Rollen besetzt werden können. Das nehme ich im folgenden mal an.
Dann ist der Fall y=1 einfach. Es gibt genau eine Besetzung.
Auch der Fall y=x ist zu erledigen, das hast Du ja schon getan. x! Besetzungen.
Hier mal ein Beispiel für y=2.
Nehmen wir mal ein Stück mit fünf Rollen:
Adliger, Bauer, Christine, Diener, Emil
(sorry, etwas männerlastig  )
- natürlich so gewählt, damit man sie A,B,C,D,E abkürzen kann.
Nun gebe es ein Ensemble aus fünf Schauspielern (an diesem Theater werden alle Frauenrollen von Männern gespielt).
Variante 1): Die Schauspieler beherrschen je zwei Rollen, nämlich folgende:
Mime 1: Adliger, Bauer
Mime 2: Bauer, Christine
Mime 3: Christine, Diener
Mime 4: Diener, Emil
Mime 5: Adliger, Christine
Wie man sieht, fällt Mime 5 aus der Reihe.
Wieviele Besetzungsmöglichkeiten gibt es nun?
Nur einer kann den Emil. Den muss er auch spielen.
Dann bleibt aber nur einer über, der den Diener kann.
Die übrigen drei können die verbleibenden Rollen auf zwei Weisen aufteilen.
Also: zwei Möglichkeiten.
Variante 2)
Mime 1: Adliger, Emil
Mime 2: Bauer, Emil
Mime 3: Christine, Emil
Mime 4: Diener, Emil
Mime 5: Adliger, Emil
Mimen 2,3,4 sind festgelegt, 1,5 können tauschen.
Also: wieder zwei Möglichkeiten.
Variante 3)
Mime 1: Adliger, Emil
Mime 2: Bauer, Emil
Mime 3: Christine, Emil
Mime 4: Diener, Emil
Mime 5: Adliger, Bauer
Schwieriger zu überblicken.
Aber auch wieder zwei Möglichkeiten.
Überleg mal, ob es immer genau zwei Möglichkeiten gibt.
Und dann versuch mal y=3. Du wirst 6 Möglichkeiten finden.
Die Vermutung liegt nahe, dass man auf y! verschiedene Weisen die Rollen verteilen kann.
Aber das wäre erst noch zu zeigen.
Grüße
reverend
|
|
|
| |
|
Hallo reverend,
wenn die Lösung y! ist, dann bedeutet dies, das sie unabhängig von x ist, was ich mir aber nicht vorstellen kann.
Hier ein paar Überlegungen: y=3, x ist variabel
Das Ergebnis muss immer 3!=6 lauten.
Zunächst wähle ich x=4
Ich knüpfe an deine Beispiele an:
M1: R1, R2, R3
M2: R2, R3, R4
M3: R3, R4, R1
M4: R4, R1, R2
Permutationen (an erster Stelle M1, an zweiter M2....):
R1 R2 R3 R4
R1 R3 R4 R2
R1 R4 R3 R2
R2 R3 R4 R1
R2 R3 R1 R4
R2 R4 R3 R1
R3 R2 R4 R1
R3 R2 R1 R4
R3 R4 R1 R2
das wären insgesamt 9 verschiedene Möglichkeiten, also kann die Lösung nicht y! sein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:59 Di 21.12.2010 | | Autor: | reverend |
hm. Stimmt. ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
|
|
|
| |
|
allerdings![[happy]](/images/smileys/happy.gif "[happy]")
ich habe mir auch schon etwas länger den kopf darüber zerbrochen![[konfus]](/images/smileys/konfus.gif "[konfus]")
hier noch ein paar beispiele:
Bleiben wir bei y=3
Bei x=5 bekommt man 13 Verteilungen.
Bei x=6 gibts 20.
Und bei x=7, 29.
Ich versteh nur nicht wie diese Zahlen in Relation stehen.
Ich habe es schon mit Fakultäten und Binomialkoeffizienten versucht aber nicht die richtigen Ergebnisse bekommen.
|
|
|
| |
|
Hallo nochmal,
ich übernehme Deine Notation.
Für folgende Rollenverteilung
M1: R1, R2, R3
M2: R1, R2, R3
M3: R1, R2, R3
M4: R1, R2, R4
gibt es sechs Möglichkeiten.
Für diese hier
M1: R1, R2, R3
M2: R1, R2, R3
M3: R1, R2, R4
M4: R1, R2, R4
gibt es acht.
In meinem ersten Post habe ich die erste Zeile wegeditiert, weil ich nicht mehr so sicher war, ob die Zahl tatsächlich von den Rollenmöglichkeiten der Schauspieler abhängt. Dies ist aber offensichtlich der Fall.
Die untere Schranke der Möglichkeiten ist definitiv y! und nicht schwer zu überlegen.
Als obere Schranke sehe ich im Moment nur [mm] y!*y^{x-y}
Wahrscheinlich fehlt da noch ein Nenner, aber außer mal eine 2 zu postulieren, wüsste ich gerade nicht, woraus der hervorgehen soll.
Immerhin ist schonmal klar, dass man nicht einfach eine Zahl in Abhängigkeit von x,y bestimmen kann, sondern nur einen Korridor, also zwei Zahlen: obere und untere Grenze.
Grüße
reverend
|
|
|
| |
|
Danke für die Antwort reverend,
das bringt mich der Lösung schonmal etwas näher
ich bin die ganze Zeit nur von einer Verteilung ausgegangen und dachte das trifft auch auf die anderen zu.
Ich werde noch ein paar Überlegungen zur Obergrenze anstellen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:34 Di 21.12.2010 | | Autor: | reverend |
Hallo Profi,
ich habe auch noch mal über die Obergrenze nachgedacht und kann sie auf folgendes senken:
[mm] y!^{\left\lfloor\bruch{x}{y}\right\rfloor}*y^{\left(x-y*\left\lfloor\bruch{x}{y}\right\rfloor\right)}
[/mm]
Dabei ist [mm] \lfloor\cdots\rfloor [/mm] die untere Gaußklammer.
Hier mal am Beispiel x=8, Werte dieser Funktion in blau, Werte der alten Funktion [mm] y!*y^{x-y} [/mm] in rot:
Für $ x=8, [mm] y=1:\quad 1!^8*1^0=\blue{1}=\red{1}=1!*1^7 [/mm] $
für $ x=8, [mm] y=2:\quad 2!^4*2^0=\blue{16}<\red{128}=2!*2^6 [/mm] $
für $ x=8, [mm] y=3:\quad 3!^2*3^2=\blue{324}<\red{1458}=3!*3^5 [/mm] $
für $ x=8, [mm] y=4:\quad 4!^2*4^0=\blue{576}<\red{6144}=4!*4^4 [/mm] $
für $ x=8, [mm] y=5:\quad 5!^1*5^3=\blue{15000}=\red{15000}=5!*5^3 [/mm] $
für $ x=8, [mm] y=6:\quad 6!^1*6^2=\blue{25920}=\red{25920}=6!*6^2 [/mm] $
für $ x=8, [mm] y=7:\quad 7!^1*7^1=\blue{35280}=\red{35280}=7!*7^1 [/mm] $
für $ x=8, [mm] y=8:\quad 8!^1*8^0=\blue{40320}=\red{40320}=8!*8^0 [/mm] $
Klar ist ja, dass für [mm] y>\bruch{x}{2} [/mm] beide Funktionen den gleichen Wert ergeben. Für [mm] y\le\bruch{x}{2} [/mm] ist das Ergebnis genauer und m.E. auch nicht mehr wesentlich zu unterbieten.
Um das zu zeigen, müsste man allerdings eine Rollenkenntnisverteilung entwerfen können, die genau diese Zahl möglicher Rollenzuweisungen zur Folge hat. Das gelingt mir im Moment nur für y=2.
Grüße
reverend
|
|
|
| |
|
nochmal danke für die ausführliche antwort
das einzige was ich in der zwischenzeit herausgefunden habe ist, dass jede rolle insgesamt gleich oft vorkommen muss um die maximalen permutationen zu erhalten.![[verlegen]](/images/smileys/verlegen.gif "[verlegen]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:40 Di 21.12.2010 | | Autor: | reverend |
Hallo nochmal,
> nochmal danke für die ausführliche antwort
> das einzige was ich in der zwischenzeit herausgefunden
> habe ist, dass jede rolle insgesamt gleich oft vorkommen
> muss um die maximalen permutationen zu erhalten.
Ja, bestimmt.
So bin ich auch auf meine neue Obergrenze gekommen.
Und wahrscheinlich kann man sie von da ausgehend doch noch um einige Faktoren senken.
Bei der Rollenvergabe gehe ich von einer Liste aus, die mir die maximalen Möglichkeiten eröffnet.
Wenn ich M1 eine Rolle gebe, dann möchte ich natürlich am liebsten, dass damit die nächsten Wahlen möglichst wenig beschränkt werden. Dazu sollten also die y Rollen, M2 übernehmen könnte, andere sein als die y Rollen von M1. Vielleicht muss ich nach M1 auch erst M5 eine Rolle geben etc. Jedenfalls mag es sein, dass ich [mm] n=\lfloor\bruch{x}{y}\rfloor [/mm] Mal hintereinander noch einen Mimen finde, der nur Rollen anzubieten hat, die die bisher bedachten nicht anzubieten hatten.
In den nächsten n Schritten habe ich höchstens jeweils die Wahl zwischen (y-1) verbleibenden Rollen, dann n Schritte mit (y-2) usw.
Bisher also mit obigem n:
[mm] y^n*(y-1)^n*...*2^n*1^n=y!^n
[/mm]
Trotzdem kommt mir hier schon etwas faul vor, was sich dann an den verbleibenden Leuten zeigt. Davon gibt es noch r=x-n*y<y.
Die dürften nach meiner Überlegung ja auch nur noch jeder 1 Rolle übrig haben. Oder haben sie jeder z.B. noch alle r Rollen?
Versuche mit kleinen Zahlen helfen da nicht viel weiter, weil man sich zu früh auf tatsächliche Repertoires festlegt.
Der eine Faktor der Obergrenze ist also klar.
Der zweite war mit [mm] y^{x-ny} [/mm] zu groß gewählt. Er kann höchstens (x-ny)! betragen. Tja, oder ist er 1? Das ist die Frage.
Am besten nähme man zur Kontrolle ein Beispiel, bei dem n>y gilt, also z.B. x=17, y=3, [mm] n=\lfloor 17/3\rfloor=5
[/mm]
Wenn man immer dem Schauspieler die nächste Rolle zuweist, der noch am meisten anzubieten hat, wieviele Rollen haben die beiden letzten dann noch? Jeder zwei? Oder jeder nur noch eine?
Aber selbst dieses Beispiel ist ja schon ein bisschen aufwändig...
Vielleicht hat ja noch jemand eine zündendere Idee. Diese hier ist mühsam.
Wie du merkst, finde ich die Aufgabe aber reizvoll.
Grüße
reverend
|
|
|
| |
|
Danke für die Erläuterungen, ich werde mir den Text wohl noch 1, 2 mal durchlesen müssen um ihn zu verstehen.![[read]](/images/smileys/read.gif "[read]")
Ich hätte nicht gedacht, dass diese Aufgabe tatsächlich so schwer ist.
An ein paar Beispielen habe ich gerade festgestellt, dass die Formel noch zu große Zahlen angibt, aber du hast mir auf jeden Fall schon mal sehr viel weiter geholfen.
Ich finde die Aufgabe auch sehr interessant, sonst würd ich mich auch gar nicht damit beschäftigen, ist nämlich ne Zusatzaufgabe von unserem Lehrer über die Ferien.
<y.>
</y.>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Mi 05.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
