Kombinatorik

Neue Frage »

elena_mis Auf diesen Beitrag antworten »
Kombinatorik
Meine Frage:
Wenn ich eine Menge mit n Elementen habe z.B. 1,2,3,4,5
Wie viele Kombinationsmöglichkeiten habe ich? Es gelten
1
2
3
4
5
12
13
14
15
23
24
25
34
35
45
123
124
125
...
1245
12345

Meine Ideen:
es scheinen 2^n zu sein. Aber wieso? Kann das jemand herleiten?
MadCookieMonster Auf diesen Beitrag antworten »

Hallo,
ich bin mit Stochastik und Ähnlichem nicht mehr ganz so vertraut aber wenn mich nicht alles täuscht funktioniert das folgendermaßen.

Wenn jedes Element aus deiner Menge nur einmal vorkommen darf dann hast du am beim ersten "Ziehen" Möglichkeiten ein Element aus deiner Menge zu nehmen. Im nächsten Schritt dann noch Möglichkeiten.

Du siehst hier also, dass ohne Zurücklegen der Elemente die Menge aller Möglichkeiten = ist.

Ich hoffe, ich liege damit richtig =)

MCM
RavenOnJ Auf diesen Beitrag antworten »

Äquivalent ist die Frage nach der Menge der Teilmengen. Wobei die Frage ist, ob die leere Menge dazuzählt oder nicht. Ich denke, in deinem Fall nicht. Dann wäre deine Antwort nicht ganz korrekt. Versuch den Beweis mal über vollständige Induktion.

Gruß
Peter
RavenOnJ Auf diesen Beitrag antworten »

@MadCookieMonster

das ist leider falsch. elena lag fast richtig.

Gruß
Peter
elene_mis Auf diesen Beitrag antworten »
Kombinatorik
@ MadCookieMonster
Mit n! hättest du alle Kombinationsmöglichkeiten in denen jeder Wert einmal vorkommt und die Reihenfolge eine Rolle spielt. Also z.B.
12345
12354
12435
12453


In meinem Fall sollen aber auch 1-stellige 2-stellige bis n-stellige Kombinationen gelten. Und 12345 und 54321 ist bei mir "das gleiche". 2 Kombinationen mit gleichen Elementen, nur verschiedener Reihenfolge sind für mich also da Gleiche.

@ RavenOnJ
Wenn die leere Menge nicht dazuzählt, ist es dementsprechend (2^n) - 1.
Danke für deinen Hinweis. Ich google mal.
MadCookieMonster Auf diesen Beitrag antworten »

Ah okay dann habe ich das falsch verstanden, sorry traurig Wieder was gelernt Augenzwinkern Wie gesagt Stochastik/Kombinatorik hatte ich noch nicht so wirklich in der Uni das kommt bei mir erst im nächsten Semester. War mir nur irgendwie sicher, ich hätte das anders verstanden =)

MCM
 
 
RavenOnJ Auf diesen Beitrag antworten »

@elena
Überleg besser selber anstatt zu googlen, denn das ist ja nicht Sinn der Sache. Das ist sehr gut über vollständige Induktion zu lösen.

Gruß
Peter
elena_mis Auf diesen Beitrag antworten »
Kombinatorik
Hallo Peter,
klar denk ich selber drüber nach, ich muss aber erstmal das hier "vollständige Induktion" googlen. Das sagt mir nämlich gar nichts.
MadCookieMonster Auf diesen Beitrag antworten »

Bei der vollständigen Induktion geht es im Grunde genommen darum, eine Aussage zu beweisen.

Dafür zeigt man zunächst, dass die Aussage für zb n = 1 (Induktionsstart) stimmt. Anschließend nimmt man an, dass die Aussage für ein beliebiges n gültig ist. (Induktionsannahme). Nun versucht man aus der Induktionsannahme die Gültigkeit für n+1 zu zeigen (Induktionsschritt).

Ich versuche das an der Aufgabe auch gerade allerdings komme ich da nicht wirklich weiter.

für n = 1 ist

und das ist ja ganz offensichtlich richtig. (Wenn die leere Menge nicht mit gezählt wird)

Nun nehmen wir also an, n sei gültig.
Jetzt ist zu zeigen, dass aus dieser Annahme n+1 folgt.
Keine Ahnung, ob dir das hilft aber bei mir scheint irgendwas noch zu fehlen. verwirrt
Ich habe nun:

Aber irgendwie sehe ich den letzten Schritt momentan nicht.

MCM
lgrizu Auf diesen Beitrag antworten »

Der Induktionsbeweis dafür, dass es Teilmengen einer n-Elementigen Menge gibt steht öfter hier im Forum, zum Beispiel hier: noch eine ivollständige Induktion
RavenOnJ Auf diesen Beitrag antworten »

@MCM
Für den Fall n+1 kannst ja einerseits die Teilmengen betrachten, die das neue Element enthalten, andererseits die, die es nicht enthalten.

Gruß
Peter
elena_mis Auf diesen Beitrag antworten »
Kombinatorik
Aha, das hab ich noch nie gehört. Ich werde mir das heute Abend mal anschauen. Ich finde andere Formeln wie n! oder Binomialkoeffizient da kann man ja verstehen wieso das so ist. Aber in diesem Fall mit dem 2^n bzw. 2^n-1 da kann ich mir gar nicht erklären wie das zustande kommt. Aber ich werde später mir nochmal Zeit nehmen dafür.
Danke auf jeden Fall schonmal für die Hilfe :-)
MadCookieMonster Auf diesen Beitrag antworten »

Ah top vielen Dank smile
Jetzt hat es klick gemacht! Freude
Math1986 Auf diesen Beitrag antworten »
RE: Kombinatorik
Zitat:
Original von elena_mis
Aha, das hab ich noch nie gehört. Ich werde mir das heute Abend mal anschauen. Ich finde andere Formeln wie n! oder Binomialkoeffizient da kann man ja verstehen wieso das so ist. Aber in diesem Fall mit dem 2^n bzw. 2^n-1 da kann ich mir gar nicht erklären wie das zustande kommt. Aber ich werde später mir nochmal Zeit nehmen dafür.
Danke auf jeden Fall schonmal für die Hilfe :-)
Hinweis: Man kann die Induktion auch umgehen, wenn man über die Binomialkoeffizienten und den binomischen Lehrsatz geht Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

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