Abzählverfahren/ Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:50 Di 17.12.2019 | | Autor: | Steve96 |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo, ich lese mir gerade einen Wikipedia - Beitrag zum Urnenmodell durch. Ich will endlich mal verstehen, wie diese Formeln für die verschiedenen Abzählverfahren zustande kommen und fange mit dem ersten Fall an.
ich zitiere aus Wikipedia:
Ziehen mit Zurücklegen unter Beachtung der Reihenfolge
______________________________________________
Beim Ziehen mehrerer Kugeln werden die Ergebnisse durch Tupel dargestellt, wobei die Länge des Tupels der Anzahl der Ziehungen entspricht. Werden von den $N$ Kugeln in der Urne $n$ Kugeln mit Zurücklegen gezogen, dann hat die Ergebnismenge die Form
$\Omega =\{(B_{i_{1}},\dotsc ,B_{i_{n}})\mid i_{1},\dotsc ,i_{n}\in \{1,\dotsc ,N\}\}}$
Die Ergebnismenge ist damit das $n$-fache kartesische Produkt der Ergebnismenge einer einfachen Ziehung. Man spricht hier auch von einer Variation mit Wiederholung. Nachdem es für jedes der $n$ Tupelelemente $N$ Möglichkeiten gibt, erhält man für die Anzahl der Elemente der Ergebnismenge
$|\Omega| = N^{n} $.
Fragen
_____
1.) Was sollen die Indizes $i_{i}$ bei der Menge $\Omega =\{(B_{i_{1}},\dotsc ,B_{i_{n}})\mid i_{1},\dotsc ,i_{n}\in \{1,\dotsc ,N\}\}}$ bedeuten ?
Was will man damit sagen, wenn man einem Index einen weiteren Index verpasst?
2.)
Warum ist $|\Omega| = N^{n} $ ?
Ich habe mir dazu schon ein Beispiel angeschaut, um das besser nachzuvollziehen.
Beispiel
______
Wir haben eine Menge von Kugeln $T := \{rot, blau, gelb \}$.
Wir haben $N = 3$ Kugeln und wir ziehen $ n = 2 $ Kugeln.
Die Möglichkeiten, die auftreten können, sind:
$(rot, rot), (rot, blau), (blau, rot), (rot, gelb), (gelb, rot) $
$(blau, blau), (blau, gelb), (gelb, blau)
$(gelb, gelb)$
Wir haben also $9$ Möglichkeiten. Und es ist ja $9 = 3^{2} = N^{n}$. Die Formel passt also.
Aber mit nur einem Beispiel bin ich nicht zufrieden. Ich möchte mir diese Formel gerne allgemein herleiten. Das habe ich heute eine Weile versucht, aber immer wieder habe ich den Überblick verloren. Ich suche also keinen Beweis (da diese nicht immer dem Verständnis dienen), sondern eine Herleitung.
Auf Wikipedia ist sozusagen die "Herleitung" der Formel in einem Satz begründet:
"Nachdem es für jedes der $n$ Tupelelemente $N$ Möglichkeiten gibt, erhält man für die Anzahl der Elemente der Ergebnismenge $|\Omega| = N^{n} $".
Ich weiß nun nicht, ob ich dafür zu hohl bin, dass ich das nicht nachvollziehen kann, oder ob ich nicht einfach nur zu kompliziert denke.
Mit meiner Herleitung bin ich so weit:
Herleitung
________
Wir haben eine Menge von Kugeln $B:= \{B_{1}, B_{2}, B_{3}, \ldots, B_{N} \}$. Wir haben also $N$ Kugeln.
Ich ziehe nun $n$ Kugel heraus.
Dann hätte ich erst mal die Möglichkeiten:
$(B_{1}, B_{1}, \ldots, B_{1})$
$(B_{1}, B_{1}, \ldots, B_{2})$
$\vdots$
$(B_{1}, B_{2}, \ldots, B_{2})$
$(B_{1}, B_{1}, \ldots, B_{3})$
$\vdots$
$(B_{1}, B_{3}, \ldots, B_{3})$
\vdots
\vdots
$(B_{1}, B_{1}, \ldots, B_{N})$
$\vdots$
$(B_{1}, B_{N}, \ldots, B_{N})$
Damit hätten wir schon einmal $N \cdot (N - 1) + 1$ Möglichkeiten.
Aber es bleiben noch so viele Kombinationen übrig und ich weiß gar nicht, wie ich sie alle abzählen soll...
Kann mir jemand hierbei helfen?
Wäre euch dankbar.
lg, Steve
|
|
| |
|
Hiho,
> Hallo, ich lese mir gerade einen Wikipedia - Beitrag zum
> Urnenmodell durch. Ich will endlich mal verstehen, wie
> diese Formeln für die verschiedenen Abzählverfahren
> zustande kommen und fange mit dem ersten Fall an.
Sehr löblich.
Passend dazu ein paar ![[]](/images/popup.gif) Abzählreime
> 1.) Was sollen die Indizes [mm]i_{i}[/mm] bei der Menge [mm]\Omega =\{(B_{i_{1}},\dotsc ,B_{i_{n}})\mid i_{1},\dotsc ,i_{n}\in \{1,\dotsc ,N\}\}}[/mm]
> bedeuten ?
>
> Was will man damit sagen, wenn man einem Index einen
> weiteren Index verpasst?
Nehmen wir mal an wir haben zwei Ziehenungen, A und B. Diese Ziehungen bestehen jeweils (nach obigem) aus n Zügen, d.h. als Ergebnis erhalten wir:
$A = [mm] (a_1,a_2,\ldots, a_n)$ [/mm] und $B = [mm] (b_1,b_2,\ldots, b_n)$
[/mm]
Da uns aber bei ausreichend großen N irgendwann die Buchstaben ausgehen, nummeriert man die Züge einfach durch, wir erhalten dann also statt A und B einfach [mm] B_1 [/mm] und [mm] B_2 [/mm] und das sieht dann könnte man das ja erst mal wie folgt notieren:
[mm] $B_1 [/mm] = [mm] (b_1,b_2,\ldots, b_n)_1$ [/mm] und [mm] $B_2 [/mm] = [mm] (b_1,b_2,\ldots, b_n)_2$
[/mm]
Wenn man sich das aber nun genauer anschaut, sieht man schon, dass die Notation nicht so ganz glücklich ist, denn das erste Ergebnis in jeder Ziehung, [mm] $b_1$, [/mm] muss ja bei beiden nicht dasselbe Element sein. Das könnte man nach obiger Notation aber vermuten.
Insbesondere ist nun gar nicht klar, wenn ich schreibe [mm] "$b_1$ [/mm] hat diese und jene Eigenschaft", von welchem Zug ich spreche. Aus diesem Grund zieht man den Index in den Tupel rein und erhält:
[mm] $B_1 [/mm] = [mm] (b_{1_1},b_{2_1},\ldots, b_{n_1})$ [/mm] und [mm] $B_2 [/mm] = [mm] (b_{1_2},b_{2_2},\ldots, b_{n_2})$
[/mm]
ganz allgemein also (um wieder zur Notation aus der Wikipedia zurückzukommen): [mm] $B_{i_j}$ [/mm] ist also das Ergebnis des i-ten Zugs im j-ten Tupel.
Man kann das "Subindizieren" auch sein lassen, wenn man klar ist, dass man nicht [mm] $i\cdot [/mm] j$ meint und einfach nur [mm] $B_{ij}$ [/mm] schreiben.
Ich tausche jetzt mal die Reihenfolge deiner Fragen zum Besseren Verständnis:
> Mit meiner Herleitung bin ich so weit:
Variiere zum Verständnis mal nicht alle bis auf den ersten, sondern nur den ersten,
Du hast irgendein Tupel, sagen wir mal wie du
$ [mm] (B_{1}, B_{1}, \ldots, B_{1}) [/mm] $
Nun ändern wir aber mal nur den ersten Eintrag, d.h. wir bekommen die Tupel:
$ [mm] (B_{2}, B_{1}, \ldots, B_{1}) [/mm] $
$ [mm] (B_{3}, B_{1}, \ldots, B_{1}) [/mm] $
.
.
.
$ [mm] (B_{N}, B_{1}, \ldots, B_{1}) [/mm] $
Wie viele Tupel bekommen wir, wenn wir nur den ersten Eintrag ändern? N Stück!
Für jeden anderen Eintrag ist das analog, und daher können wir deine Frag wie folgt beantworten:
> Warum ist [mm]|\Omega| = N^{n}[/mm] ?
Wir haben [mm]N[/mm] Kugeln und wir ziehen [mm]n[/mm] Kugeln.
Zählen wir doch nun mal alle Möglichkeiten für ein bestimmtes Tupel mit obiger Erkenntnis ab:
1: Wie viele Möglichkeiten gibt es, eine bestimmte Kugel im 1. Zug zu ziehen? N
2: Wie viele Möglichkeiten gibt es, eine bestimmte Kugel im 2. Zug zu ziehen? N
.
.
.
n: Wie viele Möglichkeiten gibt es, eine bestimmte Kugel im n. Zug zu ziehen? N
Wie viele Möglichkeiten gibt es also insgesamt eine bestimmte Kombination von Kugeln zu ziehen? Nach obigem eben:
[mm] $\underbrace{N \cdot N \cdot \ldots \cdot N}_{n-\text{mal}} [/mm] = [mm] N^n$
[/mm]
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:01 Di 17.12.2019 | | Autor: | Steve96 |
Soo, bin wieder da. Hatte ein paar Veranstaltungen, daher die Verspätung. Nicht, dass du jetzt denkst, du hättest umsonst geantwortet.
> Nehmen wir mal an wir haben zwei Ziehenungen, A und B.
> Diese Ziehungen bestehen jeweils (nach obigem) aus n
> Zügen, d.h. als Ergebnis erhalten wir:
>
> [mm]A = (a_1,a_2,\ldots, a_n)[/mm] und [mm]B = (b_1,b_2,\ldots, b_n)[/mm]
>
> Da uns aber bei ausreichend großen N irgendwann die
> Buchstaben ausgehen, nummeriert man die Züge einfach
> durch, wir erhalten dann also statt A und B einfach [mm]B_1[/mm] und
> [mm]B_2[/mm] und das sieht dann könnte man das ja erst mal wie
> folgt notieren:
>
> [mm]B_1 = (b_1,b_2,\ldots, b_n)_1[/mm] und [mm]B_2 = (b_1,b_2,\ldots, b_n)_2[/mm]
>
> Wenn man sich das aber nun genauer anschaut, sieht man
> schon, dass die Notation nicht so ganz glücklich ist, denn
> das erste Ergebnis in jeder Ziehung, [mm]b_1[/mm], muss ja bei
> beiden nicht dasselbe Element sein. Das könnte man nach
> obiger Notation aber vermuten.
> Insbesondere ist nun gar nicht klar, wenn ich schreibe
> "[mm]b_1[/mm] hat diese und jene Eigenschaft", von welchem Zug ich
> spreche. Aus diesem Grund zieht man den Index in den Tupel
> rein und erhält:
>
> [mm]B_1 = (b_{1_1},b_{2_1},\ldots, b_{n_1})[/mm] und [mm]B_2 = (b_{1_2},b_{2_2},\ldots, b_{n_2})[/mm]
>
> ganz allgemein also (um wieder zur Notation aus der
> Wikipedia zurückzukommen): [mm]B_{i_j}[/mm] ist also das Ergebnis
> des i-ten Zugs im j-ten Tupel.
> Man kann das "Subindizieren" auch sein lassen, wenn man
> klar ist, dass man nicht [mm]i\cdot j[/mm] meint und einfach nur
> [mm]B_{ij}[/mm] schreiben.
Ach so ist das gemeint! Aber warum betrachtet man mehrere Ziehungen?
Ich dachte man betrachtet immer nur eine Ziehung mit $n$ Zügen.
>
> Ich tausche jetzt mal die Reihenfolge deiner Fragen zum
> Besseren Verständnis:
>
> > Mit meiner Herleitung bin ich so weit:
> Variiere zum Verständnis mal nicht alle bis auf den
> ersten, sondern nur den ersten,
> Du hast irgendein Tupel, sagen wir mal wie du
>
> [mm](B_{1}, B_{1}, \ldots, B_{1})[/mm]
>
> Nun ändern wir aber mal nur den ersten Eintrag, d.h. wir
> bekommen die Tupel:
>
> [mm](B_{2}, B_{1}, \ldots, B_{1})[/mm]
> [mm](B_{3}, B_{1}, \ldots, B_{1})[/mm]
>
> .
> .
> .
> [mm](B_{N}, B_{1}, \ldots, B_{1})[/mm]
>
> Wie viele Tupel bekommen wir, wenn wir nur den ersten
> Eintrag ändern? N Stück!
> Für jeden anderen Eintrag ist das analog, und daher
> können wir deine Frag wie folgt beantworten:
> 1: Wie viele Möglichkeiten gibt es, eine bestimmte Kugel
> im 1. Zug zu ziehen? N
> 2: Wie viele Möglichkeiten gibt es, eine bestimmte Kugel
> im 2. Zug zu ziehen? N
> .
> .
> .
> n: Wie viele Möglichkeiten gibt es, eine bestimmte Kugel
> im n. Zug zu ziehen? N
>
> Wie viele Möglichkeiten gibt es also insgesamt eine
> bestimmte Kombination von Kugeln zu ziehen? Nach obigem
> eben:
> [mm]\underbrace{N \cdot N \cdot \ldots \cdot N}_{n-\text{mal}} = N^n[/mm]
>
>
> Gruß,
> Gono
Okay, ich denke, ich habe es verstanden.
Ich habe die Menge $B:= [mm] \{B_{1}, B_{2}, \ldots, B_{N} \}$ [/mm] an Kugeln.
Nun will ich nacheinander eine Kugel ziehen und wieder zurücklegen. Das mache ich $n$ - Mal.
Im ersten Zug habe ich nur $N$ Möglichkeiten zur Verfügung. Ich kann entweder [mm] $B_{1}$, [/mm] oder [mm] $B_{2}$, [/mm] oder [mm] $B_{3}$ [/mm] usw. ziehen.
Im zweiten Zug habe ich wieder $N$ Möglichkeiten, weil ich ja die Kugeln im ersten Zug wieder zurücklege.
Aber für jede der $N$ Möglichkeiten aus dem ersten Zug habe ich jetzt im zweiten Zug wieder $N$ Möglichkeiten!
Damit hätte ich dann schon einmal [mm] $N^{2}$ [/mm] Möglichkeiten insgesamt, wenn wir nach dem zweiten Zug aufhören, stimmt's?
Und wenn wir den dritten Zug betrachten, dann hätten wir für jede Möglichkeit aus dem zweiten Zug wieder $N$ Möglichkeiten und wir hätten dann schon insgesamt [mm] $N^{3}$ [/mm] Möglichkeiten.
Für Zug $4,5,6, [mm] \ldots, [/mm] n$ geht es dann analog.
Die Reihenfolge wird dann mit dieser Abzählung automatisch berücksichtigt.
Kann man sich dann eigentlich gut in einem Baumdiagramm veranschaulichen.
Ich beschäftige mich mal jetzt mit den restlichen Varianten und melde mich nochmal, falls ich nicht weiterkomme.
Liebe Grüße,
Steve
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:48 Di 17.12.2019 | | Autor: | Gonozal_IX |
Hiho,
eine wirkliche Frage war das ja nun nicht… melde dich, wenn du weitere Fragen hast.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:51 Do 19.12.2019 | | Autor: | Steve96 |
So, da melde ich mich wieder. Ich habe mir mal den Rest angeschaut.
"Ziehen mit Zurücklegen unter Beachtung der Reihenfolge" und "Ziehen ohne Zurücklegen unter Beachtung der Reihenfolge" habe ich verstanden.
Gestern habe ich mir "Ziehen ohne Zurücklegen ohne Beachtung der Reihenfolge" angeschaut und "Ziehen mit Zurücklegen ohne Beachtung der Reihenfolge".
"Ziehen ohne Zurücklegen ohne Beachtung der Reihenfolge" meine ich auch verstanden zu haben. Aber bin mir nicht so sicher, ob ich das korrekt erklären kann. Ich erkläre das mal, so wie ich es verstanden habe. Vielleicht verstecken sich da doch Verständnislücken, die ich nicht erkannt habe. Falls irgendwo Unsinn schreibe, korrigiere mich bitte.
Ziehen ohne Zurücklegen ohne Beachtung der Reihenfolge
_______________________________________________
Gegeben sei eine Menge $T := [mm] \{B_{1}, B_{2}, \ldots, B_{n} \}$. [/mm] Es ist also [mm] $\vert [/mm] T [mm] \vert [/mm] = n$.
"Ziehen ohne Zurücklegen unter Beachtung der Reihenfolge" heißt, dass nach jedem Zug, die aus der Urne zuvor gezogene Kugel nicht mehr in die Urne gelegt wird. Das heißt also, dass nach $k$ Zügen nur noch $n - k$ Kugeln in der Urne vorhanden sind.
Die Grundmenge lässt sich also wie folgt darstellen:
[mm] $\Omega [/mm] := [mm] \{ (a_{1}, a_{2}, \ldots, a_{k} ) \; \vert a_{i} \in \{ B_{1}, B_{2}, \ldots, B_{n} \}, $a_{i} \neq a_{j}$\; \text{für}\; i \neq j \}$
[/mm]
Die Mächtigkeit von [mm] $\Omega$ [/mm] würde ich so bestimmen:
"Ohne zurücklegen" bedeutet, dass jede Kugel höchstens einmal gezogen werden kann. Aus der Menge [mm] $\Omega$ [/mm] sind also schon mal alle $k$ - Tupeln ausgeschlossen, deren Tupelelemente nicht alle verschieden sind.
Dann bleiben natürlich also nur noch die $k$ - Tupeln, deren Elemente alle verschieden sind. Würden wir die Reihenfolge beachten würden, hätten wir [mm] $\frac{n!}{(n - k)!}$ [/mm] Möglichkeiten.
In [mm] $\Omega$ [/mm] gibt es $k!$ $k $ - Tupeln, die sich in ihrer Reihenfolge unterscheiden. Da wird die Reihenfolge nicht beachten, fassen wir diese $k!$ Möglichkeiten zu einer zusammen.
Das heißt, wir müssen [mm] $\frac{n!}{(n - k)!}$ [/mm] mit $k!$ teilen und wir erhalten [mm] $\binom{n}{k}$.
[/mm]
Ist die Erklärung korrekt ? Oder wie würdest du das erklären ? Tu mich unheimlich schwer damit, weil ich Zweifel daran habe, dass ich keine wichtigen Details vergessen habe.
Aber was ich noch gar nicht nachvollziehen konnte, ist "Ziehen mit Zurücklegen ohne Beachtung der Reihenfolge".
Ich habe gestern versucht, mir die Formel anschaulich irgendwie herzuleiten, aber ohne Erfolg. Mit einem Baumdiagramm scheint es auch nicht so zu klappen, da ich selbst da beim Abzählen die Übersicht verliere. Das war bei den anderen 3 nicht so.
Ich verstehe allein schon nicht, warum die Grundmenge hierfür [mm] $\Omega =\{S\subseteq \{1,\dotsc ,n+N-1\}\mid |S|=N-1\}$ [/mm] ist.
Und die Herleitung der Formel habe ich auch nicht geschafft. Die Anzahl der Möglichkeiten ist $ [mm] {\binom {n+N-1}{N-1}}$. [/mm] Aber ich komme einfach nicht darauf.
Durch ein Beispiel macht die Formel Sinn, aber für den allgemeinen Fall verliere ich den Überblick über die ganzen Möglichkeiten.
Freue mich auf eine Antwort.
lg, Steve
|
|
|
| |
|
Hiho,
dann wollen wir uns mal ans Unverstandene wagen.
> Aber was ich noch gar nicht nachvollziehen konnte, ist
> "Ziehen mit Zurücklegen ohne Beachtung der Reihenfolge".
Das ist auch kein Wunder bei dem Abschnitt in der Wikipedia… da fehlt ja jede Erklärung.
> Ich verstehe allein schon nicht, warum die Grundmenge
> hierfür [mm]\Omega =\{S\subseteq \{1,\dotsc ,n+N-1\}\mid |S|=N-1\}[/mm] ist.
Das ist auch ohne Erklärung nicht zu verstehen.
Dem widmen wir uns aber zum Schluss, weil es, denke ich, wie folgt besser zu verstehen ist:
Wir haben also erst mal N Kugel:
[mm] $K_1,K_2,K_3,\ldots, K_N$
[/mm]
Nun ziehen wir k mal mit Wiederholungen. Wir betrachten ja eine Ziehung ohne Berücksichtigung der Reihenfolge, d.h. oBdA können wir annehmen, dass unsere Ziehung sortiert ist und erhalten dann sortiert etwas in der Art:
[mm] $\underbrace{K_1,K_1,K_1,K_2,K_2,K_3,K_3,K_3,K_3,\ldots, K_N}_{n \text{ - mal}}$
[/mm]
Da wir aber nur sortierte Kugeln betrachten, können wir statt "Kugel 1","Kugel 2" etc. auch einfach zählen, wie oft eine Kugel da ist und dann "WEITER" (W) sagen, wenn wir die nächste Kugel zählen. Dann sähe das oben aus wie:
$K,K,K, W, K,K, W, K,K,K,K, W [mm] \ldots, [/mm] K$
Jedes solcher Tupel identifiziert damit eine Ziehung eindeutig und umgekehrt können wir jede Ziehzung als solches Tupel oben darstellen.
Wie lang ist so ein Tupel nun?
[mm] $n\cdot [/mm] K + [mm] (N-1)\cdot [/mm] W = n + N - 1$ Einträge.
Nun ist die größte Arbeit bereits getan und es wird alles ganz einfach: Das Tupel ist eindeutig bestimmt durch die Auswahl der Ws und wie viele Möglichkeiten gibt es nun die freien Plätze für die (N-1) Ws auszuwählen? $ [mm] \binom{n + N - 1}{N-1} [/mm] $.
Wenn du das verstanden hast, widmen wir uns dem Verständnis des [mm] $\Omega$ [/mm] in der Wikipedia 
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:33 Fr 20.12.2019 | | Autor: | Steve96 |
So, danke für die Antwort und habe mir mal die erste durchgelesen und versucht zu verstehen. (Die zweite habe ich grob überflogen, weil du ja meintest, ich soll mir die erste Antwort durchlesen.)
> Wir haben also erst mal N Kugel:
>
> [mm]K_1,K_2,K_3,\ldots, K_N[/mm]
>
> Nun ziehen wir k mal mit Wiederholungen. Wir betrachten ja
> eine Ziehung ohne Berücksichtigung der Reihenfolge, d.h.
> oBdA können wir annehmen, dass unsere Ziehung sortiert ist
> und erhalten dann sortiert etwas in der Art:
>
> [mm]\underbrace{K_1,K_1,K_1,K_2,K_2,K_3,K_3,K_3,K_3,\ldots, K_N}_{n \text{ - mal}}[/mm]
Ach so, weil wenn wir nur die sortierten Züge betrachten, fallen die anderen $k$ - Tupeln, die sich nur in ihrer Reihenfolge unterscheiden, raus.
> Da wir aber nur sortierte Kugeln betrachten, können wir
> statt "Kugel 1","Kugel 2" etc. auch einfach zählen, wie
> oft eine Kugel da ist und dann "WEITER" (W) sagen, wenn wir
> die nächste Kugel zählen. Dann sähe das oben aus wie:
>
> [mm]K,K,K, W, K,K, W, K,K,K,K, W \ldots, K[/mm]
>
> Jedes solcher Tupel identifiziert damit eine Ziehung
> eindeutig und umgekehrt können wir jede Ziehzung als
> solches Tupel oben darstellen.
Ich denke, so weit ist es klar. Aber habe dazu noch zwei kleine Fragen.
Betrachte das Beispiel
T:= [mm] $\{B_{1}, B_{2}, B_{3} \}$
[/mm]
Dann haben wir insgesamt [mm] $3^{3} [/mm] = 27$ Möglichkeiten, wenn wir erstmal die Reihenfolge berücksichtigen.
[mm] $(B_{1}, B_{1}, B_{1}), (B_{1}, B_{1}, B_{2}), (B_{1}, B_{1}, B_{3})$
[/mm]
[mm] $(B_{1}, B_{2}, B_{1}), (B_{1}, B_{2}, B_{2}), (B_{1}, B_{2}, B_{3})$
[/mm]
[mm] $(B_{1}, B_{3}, B_{1}), (B_{1}, B_{3}, B_{2}), (B_{1}, B_{3}, B_{3})$
[/mm]
[mm] $(B_{2}, B_{1}, B_{1}), (B_{2}, B_{1}, B_{2}), (B_{2}, B_{1}, B_{3})$
[/mm]
[mm] $(B_{2}, B_{2}, B_{1}), (B_{2}, B_{2}, B_{2}), (B_{2}, B_{2}, B_{3})$
[/mm]
[mm] $(B_{2}, B_{3}, B_{1}), (B_{2}, B_{3}, B_{2}), (B_{2}, B_{3}, B_{3})$
[/mm]
[mm] $(B_{3}, B_{1}, B_{1}), (B_{3}, B_{1}, B_{2}), (B_{3}, B_{1}, B_{3})$
[/mm]
[mm] $(B_{3}, B_{2}, B_{1}), (B_{3}, B_{2}, B_{2}), (B_{2}, B_{2}, B_{3})$
[/mm]
[mm] $(B_{3}, B_{3}, B_{1}), (B_{3}, B_{3}, B_{2}), (B_{3}, B_{3}, B_{3})$
[/mm]
Betrachten wir mal zum Beispiel das Tripel [mm] $(B_{3}, B_{3}, B_{2})$. [/mm] Das ist eine Permutation des sortierten Tripels [mm] $(B_{2}, B_{3}, B_{3})$. [/mm]
Sortiere ich hier immer der Größe nach bzg. dem Index? Also erst, wie oft Kugel 1 vorkommt, dann wie oft Kugel 2 usw.. ?
Und um alle Permutationen von [mm] $(B_{3}, B_{3}, B_{2})$ [/mm] zu umgehen, betrachte ich das sortierte Tripel [mm] $(B_{2}, B_{3}, B_{3})$.
[/mm]
Kodiert man das dann so?: $(K, W, K, K)$
Also, dass eben 1x [mm] $B_{2}$ [/mm] auftaucht und 2x [mm] $B_{3}$.
[/mm]
Aber wenn ich mein Tripel so codiere, dann kann ich ja nicht unterscheiden, ob ich mit $(K, W, K, K)$ das Tripel [mm] $(B_{2}, B_{3}, B_{3})$ [/mm] oder [mm] $(B_{1}, B_{2}, B_{2})$ [/mm] meine. Hat das überhaupt eine Relevanz ?
In der Hinsicht bin ich verwirrt.
> Wie lang ist so ein Tupel nun?
> [mm]n\cdot K + (N-1)\cdot W = n + N - 1[/mm] Einträge.
Diese Formel habe ich mit ein Paar Beispielen getestet und bei mir stimmt sie nur für $k$ - Tupeln, deren Elemente alle verschieden sind.
Die Länge von $(K, W, K, K)$ ist 4. Mit der Formel habe ich aber $n + N - 1 = 3 + 3 - 1 = 5$.
Oder habe ich etwas falsch verstanden?
> Nun ist die größte Arbeit bereits getan und es wird alles
> ganz einfach: Das Tupel ist eindeutig bestimmt durch die
> Auswahl der Ws und wie viele Möglichkeiten gibt es nun die
> freien Plätze für die (N-1) Ws auszuwählen? [mm]\binom{n + N - 1}{N-1} [/mm].
Hier verstehe ich noch nicht ganz, warum wir $N - 1$ Ws haben.
Beim Tripel $(K, W, K, K)$ haben wir nur ein $w$ und nicht N - 1 = 3 - 1 = 2$ Ws.
Aber kann sein, dass ich irgendwo etwas doch nicht richtig verstanden habe.
Und was genau meinst du mit " freie Plätze für die (N - 1) Ws auszuwählen" ?
>
> Wenn du das verstanden hast, widmen wir uns dem
> Verständnis des [mm]\Omega[/mm] in der Wikipedia
>
> Gruß,
> Gono
Liebe Grüße,
Steve
|
|
|
| |
|
Hiho,
> Ach so, weil wenn wir nur die sortierten Züge betrachten,
> fallen die anderen [mm]k[/mm] - Tupeln, die sich nur in ihrer
> Reihenfolge unterscheiden, raus.
Jein.
Genauer: Da wir ein Ziehen ohne Berücksichtigung der Reihenfolge betrachte, sind Tupel, die sich nur in Ihrer Reihenfolge unterschieden, identisch!
D.h. es gilt (um bei deinem späteren Beispiel zu bleiben): [mm] $(B_2,B_2,B_3) [/mm] = [mm] (B_3,B_2,B_2) [/mm] = [mm] (B_2, B_3, B_2)$
[/mm]
> Betrachten wir mal zum Beispiel das Tripel [mm](B_{3}, B_{3}, B_{2})[/mm].
> Das ist eine Permutation des sortierten Tripels [mm](B_{2}, B_{3}, B_{3})[/mm].
>
>
> Sortiere ich hier immer der Größe nach bzg. dem Index?
> Also erst, wie oft Kugel 1 vorkommt, dann wie oft Kugel 2
> usw.. ?
In meinem Modell oben: Ja.
> Kodiert man das dann so?: [mm](K, W, K, K)[/mm]
Nein, hier hast du einen Denkfehler, der auch dein Problem unten löst.
Du hast die Kugeln [mm] $B_1,B_2,B_3$ [/mm] und sortierst sie nach ihrem Auftreten durch "WEITER" getrennt und musst dabei immer alle Kugeln beachten!
D.h. da du keine [mm] B_1 [/mm] Kugel hast, beginnst du sofort mit "WEITER" (du überspringst also die Kugel [mm] $B_1$)
[/mm]
Die korrekte Codierung für dein Tupel wäre also: [mm](W,K, W, K, K)[/mm]
Gelesen als: WEITER (d.h. 0x [mm] B_1), [/mm] K WEITER (1x [mm] B_2), [/mm] KK (2x [mm] B_3)
[/mm]
Das Tupel [mm] $(B_1,B_1,B_3)$ [/mm] wäre dann bspw. KKWWK, gelesen als "KK WEITER" (2x [mm] B_1), [/mm] WEITER (0x [mm] B_2), [/mm] K (1x [mm] B_3)
[/mm]
> > Nun ist die größte Arbeit bereits getan und es wird alles
> > ganz einfach: Das Tupel ist eindeutig bestimmt durch die
> > Auswahl der Ws und wie viele Möglichkeiten gibt es nun die
> > freien Plätze für die (N-1) Ws auszuwählen? [mm]\binom{n + N - 1}{N-1} [/mm].
>
>
> Hier verstehe ich noch nicht ganz, warum wir [mm]N - 1[/mm] Ws
> haben.
Ist das nach obigem klar?
Wir haben N Kugeln und fangen mit der 1. Kugel [mm] B_1 [/mm] an. Um nun "von Kugel zu Kugel" zu springen, sagen wir "WEITER". Um von Kugel [mm] B_1 [/mm] bis zu Kugel [mm] B_N [/mm] zu kommen, müssen wir also N-1 mal WEITER sagen.
Gruß
Gono
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:27 Mo 23.12.2019 | | Autor: | Steve96 |
Hallo. Sorry für die verspätete Antwort, ich war mal wieder unterwegs und konnte daher nicht am PC.
> Hiho,
>
> > Ach so, weil wenn wir nur die sortierten Züge betrachten,
> > fallen die anderen [mm]k[/mm] - Tupeln, die sich nur in ihrer
> > Reihenfolge unterscheiden, raus.
> Jein.
> Genauer: Da wir ein Ziehen ohne Berücksichtigung der
> Reihenfolge betrachte, sind Tupel, die sich nur in Ihrer
> Reihenfolge unterschieden, identisch!
>
> D.h. es gilt (um bei deinem späteren Beispiel zu bleiben):
> [mm](B_2,B_2,B_3) = (B_3,B_2,B_2) = (B_2, B_3, B_2)[/mm]
>
>
> > Betrachten wir mal zum Beispiel das Tripel [mm](B_{3}, B_{3}, B_{2})[/mm].
> > Das ist eine Permutation des sortierten Tripels [mm](B_{2}, B_{3}, B_{3})[/mm].
> >
> >
> > Sortiere ich hier immer der Größe nach bzg. dem Index?
> > Also erst, wie oft Kugel 1 vorkommt, dann wie oft Kugel 2
> > usw.. ?
> In meinem Modell oben: Ja.
>
> > Kodiert man das dann so?: [mm](K, W, K, K)[/mm]
> Nein, hier hast
> du einen Denkfehler, der auch dein Problem unten löst.
> Du hast die Kugeln [mm]B_1,B_2,B_3[/mm] und sortierst sie nach
> ihrem Auftreten durch "WEITER" getrennt und musst dabei
> immer alle Kugeln beachten!
> D.h. da du keine [mm]B_1[/mm] Kugel hast, beginnst du sofort mit
> "WEITER" (du überspringst also die Kugel [mm]B_1[/mm])
> Die korrekte Codierung für dein Tupel wäre also: [mm](W,K, W, K, K)[/mm]
>
> Gelesen als: WEITER (d.h. 0x [mm]B_1),[/mm] K WEITER (1x [mm]B_2),[/mm] KK
> (2x [mm]B_3)[/mm]
>
> Das Tupel [mm](B_1,B_1,B_3)[/mm] wäre dann bspw. KKWWK, gelesen als
> "KK WEITER" (2x [mm]B_1),[/mm] WEITER (0x [mm]B_2),[/mm] K (1x [mm]B_3)[/mm]
Ah, perfekt. Jetzt habe ich die Codierung verstanden.
Das einzige, was ich noch nicht ganz herleiten kann, ist die Formel [mm] $\binom{n + N - 1}{N-1}$ [/mm] .
Ich habe einen kleinen Ansatz, aber der bringt mich nicht ganz weit.
Wir haben $N - 1$ W's. Diese ganzen W's schiebe ich alle ganz nach vorne, so dass ich erst einmal das $n$ - Tupel [mm] $(\underbrace{W, W, \ldots, W,}_{N - 1\; \text{mal}}\underbrace{ K, K, \ldots, K}_{n\; \text{mal}} [/mm] )$ betrachte.
Ich schiebe erstmal das erste $w$ nach vorne und zwar so lange, bis ich zum letzten $K$ angelangt bin. Dafür muss ich $N - 1$ mal das erste $w$ schieben. Also so:
[mm] $(\underbrace{W, W, \ldots, W,}_{N - 2\; \text{mal}}\underbrace{ K, K, \ldots, K}_{n - 1\; \text{mal}}, [/mm] W, K )$
Dann schiebe erstmal das zweite $w$ nach vorne und zwar so lange, bis ich zum letzten $K$ angelangt bin. Dafür muss ich auch $N - 1$ mal das zweite $w$ schieben. Also so:
[mm] $(\underbrace{W, W, \ldots, W,}_{N - 3\; \text{mal}}\underbrace{ K, K, \ldots, K}_{n - 2\; \text{mal}}, [/mm] W,W, K )$
Und das mache ich mit jedem $w$, so dass ich am Ende nur noch [mm] $(\underbrace{K, K, \ldots, K,}_{n - 1\; \text{mal}}\underbrace{ W, W, \ldots, W}_{N - 1\; \text{mal}}, [/mm] K )$ stehen habe.
Damit habe ich schon $(N - [mm] 1)^{2}$ [/mm] Möglichkeiten, da ich $N - 1$ W's habe und für jedes $W$ ich $ N - 1$ Möglichkeiten habe.
Jetzt verliere ich schon wieder den Überblick über die restlichen Möglichkeiten, da ich noch beachten muss, dass ich $2$ Kugeln nach vorne schieben kann (dafür hat man $N - 1$ Möglichkeiten), dann $3$ Kugeln (wieder $N - 1$ Möglichkeiten) usw.
Dann muss ich noch die restlichen Zwischenfälle beachten.
Gibt es da ein besseres Abzählverfahren dafür ?
Abgesehen von dieser Frage, müsste dann für's erste alles klar sein!
lg, Steve
|
|
|
| |
|
Hiho,
> Das einzige, was ich noch nicht ganz herleiten kann, ist
> die Formel [mm]\binom{n + N - 1}{N-1}[/mm] .
na die Formel kennst du doch schon: Ziehen aus einer Urne ohne Zurücklegen ohne Berücksichtigung der Reihenfolge.
Warum können wir das so modellieren?
Ganz einfach: Wir haben ein Tupel mit $n+N-1$ Positionen. Also:
die erste Position,
die zweite Position,
die dritte Position,
.
.
.
die $n+N-1$-ste Position
Die packen wir jetzt alle in eine Urne und ziehen die Positionen, die die Ws belegen sollen.
Da jede Position nur einmal belegt werden kann, ist das ziehen ohne Zurücklegen, da die Ws alle ununterscheidbar sind, ist es ohne Berücksichtigung der Reihenfolge.
Wie viele Positionen haben wir? $n+N-1$
Wie oft ziehen wir? $N-1$ mal (für jedes W einmal)
Ergo gibt es $ [mm] \binom{n + N - 1}{N-1} [/mm] $ Möglichkeiten dafuer.
Gruß,
Gono
|
|
|
| |
|
Vielleicht hilft dir der Anhang zum Verständnis. Wenn du dir besser die Typen wie Pferderennen, Commission, Zahlenschloss oder Cigaretten holen merkst, kannst du das Ganze viel schneller einordnen. Ich habe diese Bezeichnungen/Beispielstypen so gewählt, weils sie mit den entsprechenden Tasten auf einem normalen Taschenrechner korrespondieren (nPr, nCr und PotenZ). Deshalb habe ich Zigarette als Cigarette geschrieben.
Bei "mit und ohne Wiederholung" und "mit und ohne Reihenfolge" wirft man leicht ohne Tabelle die Formeln durcheinander.
![[a]](/images/paperclip.gif "Dateianhänge") k Ziehungen aus n Elementen
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
Anhang Nr. 2 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:31 Mo 23.12.2019 | | Autor: | Steve96 |
Hallo
Das ist sehr nett, die Anhänge schaue ich mir genauer an, wenn ich mehr Zeit habe. Habe sie bis jetzt nur überflogen.
Vielen Dank für die Hilfe.
Lg, Steve
|
|
|
| |
|
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hiho,
nun noch zur Klärung, wie die Modellierung in der Wikipedia zustande kommt: (aber bitte erst nach der anderen Antwort lesen)
Wie vorhin bezeichne K unsere Kugel und für jede gezogene Kugel dieser Art machen wir diesmal ein X.
Dann hat unser ursprüngliches Ausgangstupel $ \underbrace{K_1,K_1,K_1,K_2,K_2,K_3,K_3,K_3,K_3,\ldots, K_N}_{n \text{ - mal}} $ diesmal die Form:
$K, X,X,X, K, X,X, K, X,X,X,X, K, \ldots, X$
Wir haben also exakt N mal ein K in diesem Tupel (für jede unserer N Kugeln eins) und für jedes mal, wo diese Kugel gezogen wurde dahinter ein X, also so viele X wie Züge, also n mal ein X.
Insgesamt ist das oben also ein Tupel der Länge $N + n$
Damit umgekehrt ein beliebiges Tupel der Länge $N+n$ aber eine Ziehung nach unserem Modell repräsentiert, muss es mit einem K anfangen (denn wir haben immer das Muster: Kugel + Anzahl an X so oft wie gezogen, Kugel + Anzahl an X so oft wie gezogen, etc…)
Interessant wird es also immer erst ab dem zweiten Eintrag, d.h.:
$\underbrace{K}_{\text{immer da}}, \underbrace{X,X,X, K, X,X, K, X,X,X,X, K, \ldots, X}_{\text{interessant}}$
D.h. unserer Ziehung kann identifiziert werden durch K plus ein Tupel der Länge $N + n - 1$.
Wie viele Ks stecken nun im Interesssanten Teil? Na gerade nur noch $N-1$, weil ein K ja ganz vorne steht.
Nun sind die Tupel eindeutig identifiziert durch die Position der Ks in diesem Tupel (denn alle anderen Positionen sind dann mit Xen besetzt).
In unserem Beispiel wäre das also die Positionen: $\{4,7,12,\ldots\}$ und da wir die Positionen von $N-1$ Kugeln aufzählen müssen gilt eben: $|\{4,7,12,\ldots\}| = N-1$
Welche Positionen kommen nun für die $K$ infrage? Na alle von 1 bis $N+n-1$ (der Länge des interessanten Tupels), also haben wir als Ausgangsmenge $\{1,2,\ldots,N+n-1\}$
Unsere Ziehungen sind nach obigem also Identifizierbar durch alle N-1-Elementigen Teilmengen, nennen wir sie S, von $\{1,2,\ldots,N+n-1\}$.
Und das ist gerade kurz aufgeschrieben: $\{S\subseteq \{1,\dotsc ,n+N-1\}\mid |S|=N-1\}}$
wobei die Teilmenge S eben die Positionen der Ks in unserem interessanten Tupel enthält.
In diesem Sinne,
Gono
|
|
|
|
