Kombinatorik

Neue Frage »

sonja1893 Auf diesen Beitrag antworten »
Kombinatorik
Hallo zusammen!
Ich hänge mal wieder bei ein paar Aufgaben fest. Ich hoffe, ihr könnt mir helfen. Also:

1.
Wieviele 5-elementige Teilmengen von {0,...,9} gibt es, die
a) 0 enthalten?
b) 0 oder 1 enthalten, aber nicht beide?

2.
Das Pascalsche Dreieck hat eine Hexagon-Eigenschaft. Nehmen wir z.B. den Punkt = 21 und betrachten die 6 Eckpunkte des Hexagons mit 21 in der Mitte: 6, 15, 35, 56, 28, 7. Multipliziert man jeweils die Zahlen von jedem 2-ten Eckpunkt zusammen, so erhält man immer das gleiche Produkt: 6*35*28 = 15*56*7 = 5880. Zeigen Sie, dass dies allgemein richtig ist, d.h. es gilt
.

Hier ein Auszug aus dem Pascalschen Dreieck:
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

3.
Betrachten wir das n x n-Gitter {(i, j) | }. Wieviele Wege gibt es vom Punkt (0,0) nach (n,n), die nur nach rechts oder nach oben gehen?
Zum Beispiel für n=1 gibt es 2 Wege und für n=2 gibt es 6 Wege. Wieviele sind es für n=3 und n=4, bzw. allgemein für n?
Hinweis: Überlegen Sie zunächst, wieviele Schritte es auf jedem Weg von (0,0) bis (n,n) sind und wieviele davon nach oben bzw. nach rechts gehen.

4.
Wieviele perfekte Matchings hat der vollständige Graph mit 2n Knoten, ?
Hinweis: Ein perfektes Matching ist eine Menge von Kanten, so dass jedem Knoten auf der linken Seite genau ein Knoten auf der rechten Seite zugeordnet ist und umgekehrt. Jedes PM beschreibt eine Permutation auf {1,...,n}.

5.
Nach einem durchzechten Abend kehren 6 Seeleute sturzbetrunken auf ihr Schiff zurück. Dort legt sich jeder in das nächst beste freie Bett. Wieviele Möglichkeiten gibt es, dass keiner in seinem eigenen Bett schläft?
Hinweis: Bestimmen Sie mit der Inklusions-Exklusions-Methode die Anzahl der Möglichkeiten, dass mindestens einer in seinem Bett schläft.

traurig traurig traurig unglücklich unglücklich unglücklich X( X( X(
Steve_FL Auf diesen Beitrag antworten »

1.
a) also eine Teilmenge soll 5 Zahlen enthalten, und die 0 muss dabei sein. Das heisst es bleiben noch 4 weitere Zahlen und die 0 ist nicht mehr dabei. Also, wieviele Möglichkeiten gibt es, 4 Zahlen zwischen 1 und 9 auszuwählen, so dass keine doppelt vorkommt?

Stell dir das ganze mit einer Urne mit 9 Kugeln vor...klingelts?

bei b)
da nimmst du mal die 0 und die 1 fliegt aus der Menge raus...bleiben noch 8 Zahlen, von denen du 4 ziehen musst...wie könnts nun aussehen, wenn die 1 aber nicht die 0 dabei sein darf?

für die anderen Aufgaben hab ich momentan grad keine Zeit Augenzwinkern

mfg
 
 
sonja1893 Auf diesen Beitrag antworten »
zu 1
Also so:
a)
k=4 Stellen
n=9 Ziffern (1-9)
Fallende Faktorielle: 9*8*7*6 = 3024

b)
k=4 Stellen
n=8 Ziffern (2-9)
Fallende Faktorielle: 8*7*6*5 = 1680
Wie muss ich denn dann weitermachen? verwirrt
Steve_FL Auf diesen Beitrag antworten »

nicht ganz...du legst das ja nicht mehr zurück...

du musst die Binomialkoeffizienten nehmen...

also:
a) k = 4
n = 9
=>



und beim b) läufts dann ähnlich...

2.
wenn diese Gleichung stimmt, dann ist die nicht so schwierig zu beweisen...
schreibe die Binomialkoeffizienten aus und multiplizier sie aus...
dann sollt das schon gehen Augenzwinkern

3. Da müsst ich mich länger eindenken... 4. und 5. auch...

mfg
sonja1893 Auf diesen Beitrag antworten »

Ok. Schon mal vielen Dank für deine Hilfe.
Muss ich die Ergebnisse von 1a und b noch irgendwie miteinander verrechnen? (Ich hab kein Plan von dem Ganzen. :P)
Und bei 2: das hab ich gestern schon mal versucht, wie du's gesagt hast, es kam aber bei beiden Seiten immer was anderes raus.
Jetzt hab ich's gerade nochmal versucht und es hat geklappt. Muss mich wohl verrechnet haben... Augenzwinkern
Steve_FL Auf diesen Beitrag antworten »

nee...bei 1a) sollte das schon die Lösung sein...
bei 1b) gibts halt soviele Möglichkeitn, wie du da errechnest hast, sowohl für die 0 ohne 1 und genausoviele für die 1 ohne 0 Augenzwinkern

mfg
sonja1893 Auf diesen Beitrag antworten »

Ok. Dann passt das wohl, wie ich's jetzt hab. Augenzwinkern
Wie ich das bei den restlichen Aufgaben machen muss, weiß ich aber immer noch nicht. traurig
m00xi Auf diesen Beitrag antworten »

Hi Sonja.
Also Aufgabe 5 wird durch die sogenannten Derangement Zahlen leicht gemacht.
Die Derangement zahlen geben einfach an, wie viele fixpunktfreie bijktive Abbildungen auf der Menge [n] es gibt ( wobei n die Anzahl deiner "Seemänner" beschreibt. Fixpunktfrei heißt nichts weiter, als dass es niemals ein gibt, für das gilt: . ).
Wenn du die Derangementzahlen *verstehen* willst, lies ein paar Artikel, die Lösung kann ich dir allerdings schon hier geben:


Was der Hinweis auf die Inklusion/Exklusionsmethode soll, das kannst du dir in einigen Erklärungen zu Derangementzahlen im Netz durchlesen, du machst also nichts falsches durch die Derangementzahlen, der Hinweis ist nur wichtig zur Herleitung, da man die Derangementzahlen grob gesagt ja auch als Alle_Abbildungen - Abbildungen_mit_mindestens_einem_fixpunkt ausdrücken kann, was du auch oben siehst. stellt die Zahl aller Abbildungen dar und der zweite Teil die Anzahl der Abbildungen mit wenigstens einem Fixpunkt.

Ich hoffe ich habe dir trotz meiner komischen Art zu erklären ein wenig geholfen.

Ciao.
Hanno
m00xi Auf diesen Beitrag antworten »

Die Lösung für Problem nummer 4 lautet:



Warum, das weiß ich leider noch nicht, ich versuche es gerade zu verstehen :/

Gruß
Hanno
sonja1893 Auf diesen Beitrag antworten »

Erklärst du es mir dann, wenn du's verstanden hast? Augenzwinkern
Ich hab im Netz nachgeschaut wegen der Derangement-Zahlen, konnte aber keine Verbindung zu Inklusion-Exklusion finden. Könntest du mir das mal erklären oder einen Link geben, wo das erklärt wird?
m00xi Auf diesen Beitrag antworten »

Zuerst einmal, falls du den Satz der Inklusion/Exklusion noch nicht kennst, ich habe vor Kurzem einen Artikel auf meiner Homepage ( hier ) veröffentlicht ( unter Artikel & Schnipsel ).

Das Problem an der Sache ist, dass ich selber nur meine Bücher eingesetzt habe, um dir zu helfen, selber aber auch nicht genau sagen kann, wieso am Ende das Resultat herauskommt. Ich kann aber mal mit dem Teil beginnen, den ich verstehe, und dannden Rest der Erklärung meinem Buch entnehmen:

Also, wir möchten die Anzahl aller fixpunktfreier Abbildungen finden. Für bijektive Abbildungen ( Abbildungen N->N bei denen jedem Element auf der linken Seite genau 1 Element auf der rechten Seite zugewiesen wird und gilt: ) gibt es somit verschiedene Abbildungen ( Seemann 1 hat noch n Kajüten zur Verfügung, Seemann 2 nur noch n-1, ... , Seeman n nur noch 1 ).
Die Derangement-Zahlen ( Unordnungszahlen -> Unordnung = Kein Seemann in seiner eigentlichen Koje ) sind nun die Differenz aller Abbildungen und der Anzahl der Abbildungen, die wenigstens einen Fixpunkt haben. Diesen Wert bezeichne ich nun mal mit . Somit ergibt sich für die Derangement-Zahlen

Um die Anzahl der Abbildungen mit FIxpunkten zu finden, bedienen wir uns dem Prinzip der Inklusion und Exklusion. Dafür bezeichnen wir mit die Menge der Abbildungen, für die gilt: .
Um die Anzahl der gesuchten Abbildungen zu finden, müssen wir also die Mengen vereinen. Und genau dazu benötigen wir das Prinzip der In- und Exklusion, um doppelte Einträge ( wenn für eine Abbildung gilt: und dann ist sie ja sowohl in als auch in enthalten. ) nicht mitzuzählen. In Formelschreibweise sieht es so aus:



So, bis hier verstehe ich den ganzen Kram auch noch:
Jetzt kommt ein Schritt, den ich nicht ganz nachvollziehen kann:
Es heißt, man könne die Summe

Auch als

schreiben. Dies würde dann durch Umformen zu dem Ergebnis der Derangement-Zahlen führen, welches ich dir zuvor gepostet habe.
Den Binomialkoeffizient kann ich dir eklären, er gibt die Anzahl aller Kombinationen mit r Mengen aus den kompletten n Mengen an, jedoch wie der Faktor dorthin kommt, das kann ichdir nicht wirklcih erklären, tut mir leid unglücklich

Hast du es denn bis dahin verstanden?

Gruß
Hanno
Leopold Auf diesen Beitrag antworten »

seien die sechs Seeleute. Eine Permutation dieser Elemente gibt eine mögliche Bettenbelegung an. Die Stelle, von links gesehen, an der die jeweilige Ziffer steht, bezeichne das belegte Bett.
So bedeutet etwa , daß jeder Seemann in seinem eigenen Bett liegt, bei liegt Seemann im ersten Bett, Seemann im zweiten Bett usw.

Mit bezeichne ich das Ereignis, daß der -te Seemann in seinem eigenen Bett liegt. sei die Vereinigung aller , also das Ereignis, daß mindestens ein Seemann in seinem eigenen Bett liegt. Das Gegenereignis hiervon ist, daß kein Seemann in seinem eigenen Bett liegt. Die Mächtigkeit von kann nach der Siebformel ermittelt werden. Dazu muß man alle möglichen Einer-, Zweier-, Dreier- , ... , Sechser-Schnitte betrachten.

Einerschnitte
Es gilt , denn die verbleibenden Seeleute außer dem -ten können sich auf Arten auf die restlichen Betten verteilen.
Anzahl der Einerschnitte:

Zweierschnitte
Es gilt für paarweise verschieden: , denn die verbleibenden Seeleute außer dem -ten und -ten können sich auf Arten auf die restlichen Betten verteilen.
Anzahl der Zweierschnitte:

Dreierschnitte
Es gilt für paarweise verschieden: , denn die verbleibenden Seeleute außer dem -ten, -ten und -ten können sich auf Arten auf die restlichen Betten verteilen.
Anzahl der Dreierschnitte:

Und so geht das weiter. Man erhält nach der Siebformel:



Da es insgesamt Permutationen gibt, ergibt sich für die gesuchte Restmenge die Anzahl








EDIT (4.10.2011)
Altes Mimetex durch Latex ersetzt.
sonja1893 Auf diesen Beitrag antworten »

Vielen Dank. Das hab ich jetzt kapiert.
Wie muss ich das nun bei Aufgabe 3 rechnen?
Und warum ist die Lösung von Nr. 4 die oben genannte?
verwirrt
schmitt Auf diesen Beitrag antworten »

zu Aufgabe 1:
Zitat:
Original von Steve_FL
also:
a) k = 4
n = 9
=>



und beim b) läufts dann ähnlich...


Wie kommst Du darauf?

Ereignis A:
Enthält eine 0
Ereignis B:
Enthält eine 1

Nicht eher so?:
a)
k=5
n=10

Insgesamt Möglichkeiten : = 252

Ohne die 0 nur noch für n=9 sind es Möglichkeiten:
|A| = |B|= 126



252 - 126 = 126

Ergebnis für a) lautet also 126

b)
Möglichkeiten ohne 1 und ohne 0
sind Möglichkeiten = 56

Also für nur 1, nur 0 oder 1 und 0:
entspricht oder eben
252 - 56 = 196

Das Ergebnis für b) imüsste also

sein.


126 + 126 - 196 = 56


126-56=70; => A \ B = B \ A = 70;


=>

196 - 56 = 140

Ergebnis für b) lautet also 140

Kann das jemand bestätigen oder widerlegen
oder vielleicht elegantener lösen?
quarague Auf diesen Beitrag antworten »

man kann die 3. ein bisschen uminterpretieren, bis man eine Frage aus der Wahrscheinlichkeitsrechnung hat. Man läuft genau n mal nach rechts und n mal noch oben. Man fixiert jetzt die n mal nach rechts laufen und guckt, wann man noch oben geht. Wenn man nur ein einziges Mal nach oben geht, gibt es dafür n+1 Möglichkeiten, von vor dem ersten Mal nach rechts bis nach dem letzten Mal nach rechts gehen. Das ist die Frage
Wie viele Möglichkeiten gibt es 1 Perle in n+1 Schubladen zu legen. Dementsprechend ist dein Problem hier die Frage
Wie viele Möglichkeiten gibt es n (nicht unterscheidbare) Perlen in n+1 Schubfächer zu legen. Es gibt dafür bestimmt auch eine schöne Formel aber ich kenne sie leider nicht, ich hoffe, dass hilft trotzdem.
Leopold Auf diesen Beitrag antworten »

EDIT
Der folgende Beitrag ist die Wiederaufnahme meines in diesem Strang vorhergehenden Beitrags. Der nicht mehr lesbare Mimetex-Code wurde durch Latex-Code ersetzt.


1,2,3,4,5,6 seien die sechs Seeleute. Eine Permutation dieser Elemente gibt eine mögliche Bettenbelegung an. Die Stelle, von links gesehen, an der die jeweilige Ziffer steht, bezeichne das belegte Bett.
So bedeutet etwa 123456, daß jeder Seemann in seinem eigenen Bett liegt, bei 361245 liegt Seemann 3 im ersten Bett, Seemann 6 im zweiten Bett usw.

Mit bezeichne ich das Ereignis, daß der i-te Seemann in seinem eigenen Bett liegt. sei die Vereinigung aller , also das Ereignis, daß mindestens ein Seemann in seinem eigenen Bett liegt. Das Gegenereignis hiervon ist, daß kein Seemann in seinem eigenen Bett liegt. Die Mächtigkeit von A kann nach der Siebformel ermittelt werden. Dazu muß man alle möglichen Einer-, Zweier-, Dreier- , ... , Sechser-Schnitte betrachten.

Einerschnitte
Es gilt , denn die 5 verbleibenden Seeleute außer dem i-ten können sich auf 5! Arten auf die restlichen Betten verteilen.
Anzahl der Einerschnitte:

Zweierschnitte
Es gilt für i,j paarweise verschieden: , denn die 4 verbleibenden Seeleute außer dem i-ten und j-ten können sich auf 4! Arten auf die restlichen Betten verteilen.
Anzahl der Zweierschnitte:

Dreierschnitte
Es gilt für i,j,k paarweise verschieden: , denn die 3 verbleibenden Seeleute außer dem i-ten, j-ten und k-ten können sich auf 3! Arten auf die restlichen Betten verteilen.
Anzahl der Dreierschnitte:

Und so geht das weiter. Man erhält nach der Siebformel:



Das es insgesamt 6! Permutationen gibt, ergibt sich für die gesuchte Restmenge die Anzahl





Neue Frage »
Antworten »



Verwandte Themen

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