www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Permutationen mit Einschränkun
Permutationen mit Einschränkun < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Permutationen mit Einschränkun: Aufgabe
Status: (Frage) überfällig Status 
Datum: 09:47 Di 21.12.2010
Autor: Profi_jdr_10

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.


        
Bezug
Permutationen mit Einschränkun: Antwort
Status: (Antwort) fertig Status 
Datum: 10:17 Di 21.12.2010
Autor: reverend

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



Bezug
                
Bezug
Permutationen mit Einschränkun: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:42 Di 21.12.2010
Autor: Profi_jdr_10

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.


Bezug
                        
Bezug
Permutationen mit Einschränkun: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:59 Di 21.12.2010
Autor: reverend

hm. Stimmt. [kopfkratz3]


Bezug
                                
Bezug
Permutationen mit Einschränkun: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:13 Di 21.12.2010
Autor: Profi_jdr_10

allerdings[happy]
ich habe mir auch schon etwas länger den kopf darüber zerbrochen[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.



Bezug
                        
Bezug
Permutationen mit Einschränkun: Antwort
Status: (Antwort) fertig Status 
Datum: 11:39 Di 21.12.2010
Autor: reverend

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


Bezug
                                
Bezug
Permutationen mit Einschränkun: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:01 Di 21.12.2010
Autor: Profi_jdr_10

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.


Bezug
                                        
Bezug
Permutationen mit Einschränkun: neue Abschätzung
Status: (Mitteilung) Reaktion unnötig Status 
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



Bezug
                                                
Bezug
Permutationen mit Einschränkun: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:13 Di 21.12.2010
Autor: Profi_jdr_10

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]



Bezug
                                                        
Bezug
Permutationen mit Einschränkun: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.[verlegen]

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



Bezug
                                                                
Bezug
Permutationen mit Einschränkun: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:14 Di 21.12.2010
Autor: Profi_jdr_10

Danke für die Erläuterungen, ich werde mir den Text wohl noch 1, 2 mal durchlesen müssen um ihn zu verstehen.[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.>

Bezug
        
Bezug
Permutationen mit Einschränkun: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:20 Mi 05.01.2011
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de