Kombinatorik: 4. Grundaufgabe < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Aus der Menge [mm] \{a_{1}, a_{2}, ..., a_{n}\} [/mm] soll man k Elemente auswählen, wobei es nicht auf die Reihenfolge ankommt und gleiche Elemente auch mehrfach ausgewählt werde dürfen. Es entsteht eine k-Auswahl aus [mm] \{a_{1}, a_{2}, ..., a_{n}\} [/mm] ohne Berücksichtigung der Reihenfolge mit Wiederholungen. |
Hallo!
Ich bin neu hier und beschäftige mich hobbymäßig und für einen BWL-Fernkurs mit Mathematik.
Die Formel zur obigen Aufgabe (k-Kollektion aus einer n-Menge) ist
[mm] \bruch{(n+k-1)!}{k!(n-1)!}. [/mm]
Wie kann man diese Formel so herleiten, dass verständlich wird, warum es sich hier um eine (n-1)-Auswahl aus n+k-1 Elementen handelt (ein kurzer Tipp würde genügen)?
(Beispiel: Bei 3 Würfeln wäre das eine 5-Auswahl aus 8 Elementen.)
Die häufig gebrachte Erklärung hilft mir leider nicht weiter.
Sie lautet: Man soll sich n+k-1 (warum?) Plätze denken, von denen n-1 (warum?) ausgewählt und mit "0" besetzt werden, so dass es zwischen den Nullen k Lücken gibt, die wiederum mit Elementen der Menge besetzt werden, und zwar die i-te Lücke mit lauter Elementen [mm] a_{i}.
[/mm]
Danke für Eure Hilfe!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo fuzzy-bear!
> Aus der Menge [mm]\{a_{1}, a_{2}, ..., a_{n}\}[/mm] soll man k
> Elemente auswählen, wobei es nicht auf die Reihenfolge
> ankommt und gleiche Elemente auch mehrfach ausgewählt werde
> dürfen. Es entsteht eine k-Auswahl aus [mm]\{a_{1}, a_{2}, ..., a_{n}\}[/mm]
> ohne Berücksichtigung der Reihenfolge mit Wiederholungen.
> Hallo!
>
> Ich bin neu hier und beschäftige mich hobbymäßig und für
> einen BWL-Fernkurs mit Mathematik.
>
> Die Formel zur obigen Aufgabe (k-Kollektion aus einer
> n-Menge) ist
>
> [mm]\bruch{(n+k-1)!}{k!(n-1)!}.[/mm]
>
> Wie kann man diese Formel so herleiten, dass verständlich
> wird, warum es sich hier um eine (n-1)-Auswahl aus n+k-1
> Elementen handelt (ein kurzer Tipp würde genügen)?
Du kannst es sehen als (n-1)-Auswahl, oder auch als k-Auswahl, und da ja k Elemente gewählt werden sollen, wäre letzteres naheliegender. 
Ich würde es so betrachten, dass, wenn wir Elemente mehrfach auswählen dürfen, wir doch einfach sagen können, dass wir mehr Elemente haben. Wenn wir also k-mal dasselbe Element wählen, können wir sagen, dass ein Element nicht nur einmal in der Auswahlmenge vorkommt, sondern k-mal, womit wir k-1 Elemente mehr haben, als die Menge (wenn wir ausnahmsweise mal dasselbe Element in der Menge mehrfach mitzählen). Verstehst du, was ich meine? Also wenn die Menge die Elemente [mm] a_1 [/mm] bis [mm] a_n [/mm] enthält, und wir k-mal das Element [mm] a_n [/mm] auswählen, dann können wir die Auswahlmenge als [mm] \{\underbrace{a_1,...,a_n}_{\mbox{n Elemente}},\underbrace{a_n,...,a_n}_{\mbox{(k-1)-mal}}\} [/mm] betrachten. (Woher die -1 kommt, war mir zuerst nicht klar, aber einmal ist das Element [mm] a_n [/mm] ja schon bei den n Elementen dabei, es müssen also nur (k-1) davon "hinzugefügt" werden.)
Nun haben wir also insgesamt quasi n+k-1 Elemente, von denen wir k auswählen, damit erhalten wir: [mm] \vektor{n+k-1\\k}=\frac{(n+k-1)!}{(n-1)!k!}.
[/mm]
Alles klar?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:13 Di 25.09.2007 | | Autor: | fuzzy-bear |
Hallo Bastiane!
Herzlichen Dank für Deine Antwort! Ich denke, ich hab's gerafft :o)
Der Trick mit den mehr Elementen ist ja ganz einfach - aber man muss erst mal drauf kommen ;o)
Das ist dann also sozusagen die "Übersetzung" in das Lotto-Problem mit [mm] \vektor{n \\ k}.
[/mm]
Vielleicht kann man es auch so verstehen, dass man n Plätze hat und k Sternchen zu verteilen. Dann addiert man die Trennstriche zwischen den Plätzen (n-1) zu den Sternchen (k) und erhält ebenso n+k-1, woraus man entweder n-1 oder k Elemente auswählt.
Eigentlich ganz leicht....
Liebe Grüße
fuzzy-bear
> Hallo fuzzy-bear!
>
> > Aus der Menge [mm]\{a_{1}, a_{2}, ..., a_{n}\}[/mm] soll man k
> > Elemente auswählen, wobei es nicht auf die Reihenfolge
> > ankommt und gleiche Elemente auch mehrfach ausgewählt werde
> > dürfen. Es entsteht eine k-Auswahl aus [mm]\{a_{1}, a_{2}, ..., a_{n}\}[/mm]
> > ohne Berücksichtigung der Reihenfolge mit Wiederholungen.
> > Hallo!
> >
> > Ich bin neu hier und beschäftige mich hobbymäßig und für
> > einen BWL-Fernkurs mit Mathematik.
> >
> > Die Formel zur obigen Aufgabe (k-Kollektion aus einer
> > n-Menge) ist
> >
> > [mm]\bruch{(n+k-1)!}{k!(n-1)!}.[/mm]
> >
> > Wie kann man diese Formel so herleiten, dass verständlich
> > wird, warum es sich hier um eine (n-1)-Auswahl aus
> n+k-1
> > Elementen handelt (ein kurzer Tipp würde genügen)?
>
> Du kannst es sehen als (n-1)-Auswahl, oder auch als
> k-Auswahl, und da ja k Elemente gewählt werden sollen, wäre
> letzteres naheliegender.
>
> Ich würde es so betrachten, dass, wenn wir Elemente
> mehrfach auswählen dürfen, wir doch einfach sagen können,
> dass wir mehr Elemente haben. Wenn wir also k-mal dasselbe
> Element wählen, können wir sagen, dass ein Element nicht
> nur einmal in der Auswahlmenge vorkommt, sondern k-mal,
> womit wir k-1 Elemente mehr haben, als die Menge (wenn wir
> ausnahmsweise mal dasselbe Element in der Menge mehrfach
> mitzählen). Verstehst du, was ich meine? Also wenn die
> Menge die Elemente [mm]a_1[/mm] bis [mm]a_n[/mm] enthält, und wir k-mal das
> Element [mm]a_n[/mm] auswählen, dann können wir die Auswahlmenge als
> [mm]\{\underbrace{a_1,...,a_n}_{\mbox{n Elemente}},\underbrace{a_n,...,a_n}_{\mbox{(k-1)-mal}}\}[/mm]
> betrachten. (Woher die -1 kommt, war mir zuerst nicht klar,
> aber einmal ist das Element [mm]a_n[/mm] ja schon bei den n
> Elementen dabei, es müssen also nur (k-1) davon
> "hinzugefügt" werden.)
>
> Nun haben wir also insgesamt quasi n+k-1 Elemente, von
> denen wir k auswählen, damit erhalten wir:
> [mm]\vektor{n+k-1\\k}=\frac{(n+k-1)!}{(n-1)!k!}.[/mm]
>
> Alles klar?
>
> Viele Grüße
> Bastiane
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:28 Di 25.09.2007 | | Autor: | rabilein1 |
Ich habe mir die Aufgabe bestimmt 5 Mal durchgelesen- und nicht verstanden, weil:
Sie ist verwurschtelt ausgedrückt und sprachlich unverständlich .
> Bei 3 Würfeln wäre das eine 5-Auswahl aus 8 Elementen
Das ist doch schon mal ein Ansatz, um es eventuell verständlich zu formulieren. Wenn du an Stelle von "Würfeln", "Auswahl" und "Elementen" noch schreibst, was denn nun genau gemeint ist, dann wäre das Problem eventuell zu knacken.
By the way:
Die angegebene Formel erinnert irgendwie an die "Lotto-Formel" (wie viele Möglichkeiten es gibt, um eine Tippreihe beim Lotto auszufüllen) - aber da gibt es ja keine Wiederholungen der Zahlen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:46 Di 25.09.2007 | | Autor: | Bastiane |
Hallo rabilein1!
Ich weiß nicht, ob ich dich schon einmal darauf hingewiesen habe, aber "Rückfragen" bzgl. der Aufgabenstellung sollen hier bitte nicht als Fragen markiert werden. Schreibe also in Zukunft bitte nur eine Mitteilung.
> Ich habe mir die Aufgabe bestimmt 5 Mal durchgelesen- und
> nicht verstanden, weil:
Komisch, ich habe sie beim ersten Lesen verstanden.
> Sie ist verwurschtelt ausgedrückt und sprachlich
> unverständlich .
Was ist denn daran verwurschtelt und sprachlich unverständlich?
Und wenn schon eine Antwort geschrieben wurde und du die Aufgabe nicht verstehst, warum schreibst du überhaupt etwas dazu? Ist die vorhandene Antwort nicht korrekt? Dann schreibe bitte direkt dazu etwas, und was daran falsch oder unklar ist. Wenn du etwas ergänzen möchtest, kannst du das auch gerne tun - in einer separaten Antwort oder Mitteilung. Aber warum schreibst du etwas zu einer Frage, die schon beantwortet ist und du die Frage nicht mal verstehst? ![[kopfkratz]](/images/smileys/kopfkratz.gif "[kopfkratz]")
> By the way:
> Die angegebene Formel erinnert irgendwie an die
> "Lotto-Formel" (wie viele Möglichkeiten es gibt, um eine
> Tippreihe beim Lotto auszufüllen) - aber da gibt es ja
> keine Wiederholungen der Zahlen
Du meinst einfach die allgemeine Formel [mm] \vektor{n\\k}, [/mm] oder? Ich denke, die ist dem Fragesteller durchaus bekannt, aber sie ist es ja eben nicht, weil dort keine Wiederholungen zugelassen sind.
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:07 Di 25.09.2007 | | Autor: | rabilein1 |
Warum das als "Frage" formuliert hatte:
Weil meine Frage war: Wie lautet die Ursprungs-Aufgabe unter Verwendung der Zahlen 5 - 3 - 8 in verständlich formulierter Form ?
Der Fragesteller hatte ja irgend etwas hinsichtlich Kombinatorik nicht verstanden.
Eventuell (?) hätte ich ihm helfen können, wenn ich verstanden hätte, was er überhaupt meint.
Ob deine Antwort für den Fragesteller verständlich war und ihm weitergeholfen hat, das kann ich nicht beurteilen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:29 Di 25.09.2007 | | Autor: | Bastiane |
Hallo rabilein1!
> Warum das als "Frage" formuliert hatte:
>
> Weil meine Frage war: Wie lautet die Ursprungs-Aufgabe
> unter Verwendung der Zahlen 5 - 3 - 8 in verständlich
> formulierter Form ?
Ich glaube nicht, dass es ihm um diese Aufgabe ging, das war nur ein Beispiel, das er wohl schon verstanden hatte. Für die eigentliche Frage bzw. Aufgabe ist ja oben der Kasten da, und da stand ja auch genug drin.
Und solche Fragen sollen bitte trotzdem nicht als Fragen markiert werden!!! Fragen, die als solche markiert sind, sind Fragen, die ein Hilfsbereiter User beantworten kann. Und da außer dem Fragesteller selber wohl niemand von uns die eigentliche Frage kennt, können wir darauf nicht reagieren. Wenn der Fragesteller an einer Antwort interessiert ist (und das sollte er, warum sollte er sonst die Frage stellen), wird er auch deine Frage finden, wenn sie nur als Mitteilung markiert ist, und darauf reagieren. Dann haben sie aber nicht etliche hilfsbereite User gelesen, die damit doch nichts anfangen können!
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:48 Di 25.09.2007 | | Autor: | rabilein1 |
Okay, das leuchtet ein:
"Mitteilungen" sind Mitteilungen, Fragen etc. an den Fragesteller.
"Fragen" sind Fragen an alle anderen User.
Da sich der Fragesteller in diesem speziellen Fall nicht mehr gemeldet hat, nehme ich ohnehin an, dass ihm deine Antwort hilfreich war.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:36 Di 25.09.2007 | | Autor: | fuzzy-bear |
Hallo rabilein1,
Bastiane hat mir schon eine sehr gut verständliche Antwort geschrieben.
Das Problem mit den Würfeln ist folgendes:
Drei Würfel (mit je sechs verschiedenen Zahlen) werden geworfen. Wie viele Ausgänge gibt es, und zwar mit Wiederholungen (es kann ja z. B. zweimal die "3" fallen) und ohne Beachtung der Reihenfolge?
Dann ist n=6 und k=3.
Antwort: Es gibt [mm] \bruch{(n+k-1)!}{k!(n-1)!} [/mm] = [mm] \bruch{8!}{3!5!} [/mm] = [mm] \bruch{8*7*6*5*4*3*2*1}{3*2*1*5*4*3*2*1} [/mm] = [mm] \bruch{8*7*6}{3*2*1} [/mm] = 56 Möglichkeiten bzw. Ausgänge.
Erklärung siehe Bastianes Antwort (entscheidende Tricks:
1. statt Wiederholungsmöglichkeit mehr Elemente
2. Umwandlung ins Lotto-Problem = ohne Wiederholung, ohne Beachtung der Reihenfolge).
Viele Grüße
fuzzy-bear
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:12 Mi 26.09.2007 | | Autor: | rabilein1 |
> Drei Würfel (mit je sechs verschiedenen Zahlen) werden
> geworfen. Wie viele Ausgänge gibt es, und zwar mit
> Wiederholungen (es kann ja z. B. zweimal die "3" fallen)
> und ohne Beachtung der Reihenfolge?
>
> Dann ist n=6 und k=3.
Danke. Genau das meinte ich:
Die obige Formulierung ist sehr gut verständlich - unabhängig davon, ob und wie man die Aufgabe lösen kann.
|
|
|
|
