Stichprobe, Permutation < Wahrscheinlichkeit < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 06:12 Sa 01.11.2014 | | Autor: | YuSul |
| Aufgabe | Sei [mm] $\Xi=\{1,...,n\}$ [/mm] mit [mm] $n\in\mathbb{N}$ [/mm] und es bezeichne [mm] $\Sigma_\Xi$ [/mm] die Menge der Permutationen auf [mm] $\Xi$.
[/mm]
I) Wie viele Permutationen gibt es auf [mm] $\Xi$ [/mm] die einen Zykel länger als [mm] $k>\frac{n}{2}$ [/mm] haben. k ist auch eine natürliche Zahl.
II) Man berechne im Laplaceraum über [mm] $\Sigma_\Xi$ [/mm] die Wahrscheinlichkeit für das Ereignis [mm] $A=\{\sigma\in\Sigma_\Xi|\sigma\text{hat einen Zykel strikt länger als} \frac{n}{2}\}$.
[/mm]
(P.S. Ich hatte schon einmal hier einen Thread eröffnet zum ersten Teil der Aufgabe, darin ging es aber erstmal um die Begrifflichkeit) |
Hi, ich hätte ein Problem mit dieser Aufgabe.
Denn ich weiß nicht wirklich wie ich hier eine Wahrscheinlichkeit berechnen soll.
Wenn ich die Permutationen bilde betrachte ich ja ein "Ziehen ohne zurücklegen mit Beachtung der Reihenfolge".
Für die Anzahl der Permutationen würde ich folgendes anbieten:
[mm] $\sum_{k=[\frac{n}{2}]+1}^n \frac{n!}{(n-k)!}$
[/mm]
Wobei [...] hier die Abrundungsfunktion (Gaußklammer) beschreiben soll.
Wenn euch unklar ist wie ich darauf komme, dann kann ich meine Rechung/Gedanken dazu noch nachtragen, aber eigentlich bin ich mir recht sicher, dass dies korrekt sein sollte.
Mein Problem ist eher im zweiten Aufgabenteil:
Hier soll ich über dem Laplaceraum, daher jedes Ereignis hat die gleiche Wahrscheinlichkeit, eine Wahrscheinlichkeit berechnen.
Ich würde über das Komplement rechnen, aber wirklich ausrechnen kann ich nichts...
Zu erst einmal sollte es ja n! mögliche Permutationen geben. Dann ist die Wahrscheinlichkeit für eine Permutation mit Zykel k>n/2
[mm] $\frac{\sum_{k=[\frac{n}{2}]+1}^n \frac{n!}{(n-k)!}}{n!}$
[/mm]
Wenn ich nun [mm] $P(A^c)$ [/mm] angebe, dann erhalte ich lediglich:
[mm] $P(A^c)=1-\frac{\sum_{k=[\frac{n}{2}]}^n \frac{n!}{(n-k)!}}{n!}\stackrel{?}{=}1-\sum_{k=[\frac{n}{2}]}^n \frac{1}{(n-k)!}$
[/mm]
Naja, und das war es dann eigentlich auch schon...
Im letzten Schritt (wo ich mir etwas unsicher bin) habe ich das n! gekürzt.
Im Laufindex verschwindet das +1, weil im Gegenereignis ja nun [mm] $k\leq [/mm] n/2$ gesucht ist.
Verstehe ich die Aufgabe falsch?
Kann jemand meine Rechnung bestätigen, oder Fehler aufzeigen?
Danke.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:19 Sa 01.11.2014 | | Autor: | tobit09 |
Hallo YuSul!
> Sei [mm]\Xi=\{1,...,n\}[/mm] mit [mm]n\in\mathbb{N}[/mm] und es bezeichne
> [mm]\Sigma_\Xi[/mm] die Menge der Permutationen auf [mm]\Xi[/mm].
>
> I) Wie viele Permutationen gibt es auf [mm]\Xi[/mm] die einen Zykel
> länger als [mm]k>\frac{n}{2}[/mm] haben. k ist auch eine
> natürliche Zahl.
Hier soll es wohl "mit Länge [mm] $k>\frac{n}{2}$" [/mm] statt "länger als [mm] $k>\frac{n}{2}$" [/mm] heißen.
> II) Man berechne im Laplaceraum über [mm]\Sigma_\Xi[/mm] die
> Wahrscheinlichkeit für das Ereignis
> [mm]A=\{\sigma\in\Sigma_\Xi|\sigma\text{hat einen Zykel strikt länger als} \frac{n}{2}\}[/mm].
> Wenn ich die Permutationen bilde betrachte ich ja ein
> "Ziehen ohne zurücklegen mit Beachtung der Reihenfolge".
Welche Menge möchtest du gerade abzählen?
Die Menge [mm] $\Sigma_\Xi$, [/mm] die Menge $A$ oder die Menge
[mm] $A_k:=\{\sigma\in\Sigma_\Xi\;|\;\sigma\text{ hat einen Zykel der Länge} k\}$
[/mm]
für festes [mm] $k>\frac{n}{2}$?
[/mm]
> Für die Anzahl der Permutationen würde ich folgendes
> anbieten:
>
> [mm]\sum_{k=[\frac{n}{2}]+1}^n \frac{n!}{(n-k)!}[/mm]
>
> Wobei [...] hier die Abrundungsfunktion (Gaußklammer)
> beschreiben soll.
>
> Wenn euch unklar ist wie ich darauf komme, dann kann ich
> meine Rechung/Gedanken dazu noch nachtragen, aber
> eigentlich bin ich mir recht sicher, dass dies korrekt sein
> sollte.
Überprüfen wir mal am Beispiel $n=3$:
[mm] $\sum_{k=[\frac{n}{2}]+1}^n \frac{n!}{(n-k)!}=\sum_{k=[\frac{3}{2}]+1}^3 \frac{3!}{(3-k)!}=\sum_{k=2}^3\frac{6}{(3-k)!}=\frac{6}{(3-2)!}+\frac{6}{(3-3)!}=\frac{6}{1}+\frac{6}{1}=12$.
[/mm]
Es gäbe nach deiner Formel also 12 Permutationen in [mm] $\Sigma_{\{1,2,3\}}$ [/mm] mit einem Zykel einer Länge [mm] $>\frac{3}{2}$.
[/mm]
[mm] $\Sigma_{\{1,2,3\}}$ [/mm] hat aber überhaupt nur $3!=6$ Elemente.
Deine Formel kann also nicht stimmen.
Korrekt ist die Idee, für jedes [mm] $k>\frac{n}{2}$ [/mm] (also für jedes [mm] $k\ge[\frac{n}{2}]+1$) [/mm] die Mächtigkeit von [mm] $A_k$ [/mm] zu bestimmen.
Es gilt in der Tat
[mm] $|A|=\sum_{k\ge[\frac{n}{2}]+1}^n|A_k|$,
[/mm]
da die [mm] $A_k$ [/mm] für [mm] $k>\frac{n}{2}$ [/mm] paarweise disjunkt sind.
Zur Bestimmung von [mm] $|A_k|$ [/mm] für [mm] $k>\frac{n}{2}$:
[/mm]
Man erhält jede Permutation [mm] $\sigma\in A_k$ [/mm] nach der folgenden Methode auf genau eine Weise:
1. Man wählt eine $k$-elementige Teilmenge [mm] $I\subseteq\{1,\ldots,n\}$.
[/mm]
$I$ soll gerade die [mm] $x\in\{1,\ldots,n\}$ [/mm] enthalten, die "am Zykel der Länge $k$ beteiligt" sein sollen.
2. Man legt [mm] $\sigma(x)$ [/mm] für alle [mm] $x\in [/mm] I$ fest, so dass diese $x$ tatsächlich "einen Zykel (der Länge $k$) bilden".
3. Man legt [mm] $\sigma(x)$ [/mm] für alle [mm] $x\in\{1,\ldots,n\}\setminus [/mm] I$ fest, so dass [mm] $\sigma$ [/mm] injektiv wird.
Bestimme zu 1., 2. und 3. jeweils die Anzahl der möglichen Wahlen.
[mm] $|A_k|$ [/mm] erhältst du dann als Produkt dieser Anzahlen.
> Mein Problem ist eher im zweiten Aufgabenteil:
>
> Hier soll ich über dem Laplaceraum, daher jedes Ereignis
> hat die gleiche Wahrscheinlichkeit, eine Wahrscheinlichkeit
> berechnen.
Jedes ERGEBNIS hat die gleiche Wahrscheinlichkeit, nicht jedes EREIGNIS.
> Ich würde über das Komplement rechnen, aber wirklich
> ausrechnen kann ich nichts...
>
> Zu erst einmal sollte es ja n! mögliche Permutationen
> geben.
Ja.
> Dann ist die Wahrscheinlichkeit für eine
> Permutation mit Zykel
der Länge
> k>n/2
>
> [mm]\frac{\sum_{k=[\frac{n}{2}]+1}^n \frac{n!}{(n-k)!}}{n!}[/mm]
Folgerichtig.
> Wenn ich nun [mm]P(A^c)[/mm] angebe,
Warum das?
Gefragt ist $P(A)$, nicht [mm] $P(A^c)$.
[/mm]
> dann erhalte ich lediglich:
>
> [mm]P(A^c)=1-\frac{\sum_{k=[\frac{n}{2}]}^n \frac{n!}{(n-k)!}}{n!}\stackrel{?}{=}1-\sum_{k=[\frac{n}{2}]}^n \frac{1}{(n-k)!}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>
> Naja, und das war es dann eigentlich auch schon...
>
> Im letzten Schritt (wo ich mir etwas unsicher bin) habe ich
> das n! gekürzt.
Dieser Schritt ist korrekt:
Es gilt
$\frac{\sum_{k=[\frac{n}{2}]}^n \frac{n!}{(n-k)!}}{n!}=\frac{\sum_{k=[\frac{n}{2}]}^nn!\frac{1}{(n-k)!}}{n!}=\frac{n!*\sum_{k=[\frac{n}{2}]}^n \frac{1}{(n-k)!}}{n!}=\sum_{k=[\frac{n}{2}]}^n \frac{1}{(n-k)!}}$.
> Im Laufindex verschwindet das +1, weil im Gegenereignis ja
> nun [mm]k\leq n/2[/mm] gesucht ist.
Das ist falsch.
Es gilt
[mm] $P(A^c)=1-P(A)=1-\frac{\sum_{k=[\frac{n}{2}]\red{+1}}^n |A_k|}{n!}$.
[/mm]
Zum Berechnen einer Wahrscheinlichkeit $P(A)$ über die Gegenwahrscheinlichkeit [mm] $P(A^c)$:
[/mm]
Das ist immer dann sinnvoll, wenn [mm] $P(A^c)$ [/mm] leichter zu bestimmen ist als $P(A)$.
Das erscheint mir hier nicht der Fall zu sein.
Ich habe (auch mit den korrekten Werten für [mm] $|A_k|$) [/mm] keine Möglichkeit gefunden, $|A|$ ohne Summe darzustellen.
Daher würde ich die Summe am Ende stehen lassen.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:42 Sa 01.11.2014 | | Autor: | YuSul |
Danke für die ausführliche Antwort.
Ich hatte mir meine Formel so überlegt:
Am Beispiel [mm] $\{1,2,3\}$ [/mm]
Dann muss ich die Möglichkeiten eine Permutation der Länge 2 und der Länge 3 zu bilden addieren. Aber das wären dann doch:
1,2 1,2,3
1,3 1,3,2
2,1 2,1,3
2,3 2,3,1
3,1 3,2,1
3,2 3,1,2
Ich verstehe zwar deinen Einwand, aber ich sehe gerade nicht so recht wieso ich hier falsch gedacht habe...
Das [mm] $\Sigma_{\{1,2,3\}}$ [/mm] 6 Elemente hat wäre mir zwar von der symmetrischen Gruppe bekannt, aber ich sehe trotzdem nicht wieso meine "Abzählung" oben nicht den Kern der Aufgabe trifft.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:33 Sa 01.11.2014 | | Autor: | tobit09 |
> Ich hatte mir meine Formel so überlegt:
>
> Am Beispiel [mm]\{1,2,3\}[/mm]
> Dann muss ich die Möglichkeiten eine Permutation der
> Länge 2 und der Länge 3 zu bilden addieren.
Nein.
Du musst die Anzahl der Permutationen in [mm] $\Sigma_{\{1,2,3\}}$ [/mm] mit einem Zykel der Länge 2 (mit meinen Bezeichnungen: [mm] $|A_2|$) [/mm] und die Anzahl der Permutationen in [mm] $\Sigma_{\{1,2,3\}}$ [/mm] mit einem Zykel der Länge 3 [mm] ($|A_3|$) [/mm] addieren.
> Aber das
> wären dann doch:
>
> 1,2 1,2,3
> 1,3 1,3,2
> 2,1 2,1,3
> 2,3 2,3,1
> 3,1 3,2,1
> 3,2 3,1,2
Welche Permutationen meinst du mit dieser Schreibweise?
Was bedeutet z.B. "1,2"?
Wie lauten [mm] $\sigma(1)$, $\sigma(2)$ [/mm] und [mm] $\sigma(3)$ [/mm] für [mm] $\sigma=$"1,2"?
[/mm]
Du hast offenbar Permutationen mehrfach aufgezählt.
(Oder aber die von dir verwandte Schreibweise steht überhaupt nicht für Permutationen aus [mm] $\Sigma_{\{1,2,3\}}$.)
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:42 Sa 01.11.2014 | | Autor: | YuSul |
Also ich denke mir das so, dass ich eben eine Menge habe, {1,2,3} mit wobei ich zum Beispiel jetzt drei Kugeln habe die eben mit der entsprechenden Zahl beschriftet sind.
Und jetzt suche ich die Anzahl der Möglichkeiten diese Kugeln jeweils in einem Zyklus der Länge zwei anzuordnen.
Dann habe ich für die erste Kugel
3 Möglichkeiten sie hinzulegen. Für die nächste (3-1)
Ich kann die Kugeln ja unterscheiden und kriege so dann auch andere Permutationen
Für einen Zyklus der Länge 2 hätte ich also
3(3-1) Möglichkeiten
Für einen Zyklus der Länge 3 entsprechend 3(3-1)(3-2)
Mit meiner Schreibweise meinte ich jeweils den Zyklus
1,2,1,2,1,2 usw.
bzw.
1,2,3,1,2,3 usw.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:21 Sa 01.11.2014 | | Autor: | tobit09 |
Wir suchen die Anzahl von Permutationen aus [mm] $\Sigma_{\{1,2,3\}}$ [/mm] mit einem Zykel der Länge 2 (bzw. 3).
(Es geht NICHT um eine Anzahl von Zykeln!)
Wie lauten denn die 6 Permutationen aus [mm] $\Sigma_{\{1,2,3\}}$, [/mm] also die bijektiven Abbildungen [mm] $\sigma\colon\{1,2,3\}\to\{1,2,3\}$?
[/mm]
> Also ich denke mir das so, dass ich eben eine Menge habe,
> {1,2,3} mit wobei ich zum Beispiel jetzt drei Kugeln habe
> die eben mit der entsprechenden Zahl beschriftet sind.
Zusätzlich hast du drei mit 1,2 bzw. 3 beschriftete Plätze für die Kugeln, so dass auf jeden Platz genau eine Kugel passt?
Dann entspricht jede Permutation [mm] $\sigma$ [/mm] einer Anordnung der drei (!) Kugeln auf die drei Plätze: [mm] $\sigma(x)$ [/mm] (für [mm] $x\in\{1,2,3\}$) [/mm] gibt an, auf welchem Platz die Kugel mit der Nummer $x$ landet.
> Und jetzt suche ich die Anzahl der Möglichkeiten diese
> Kugeln jeweils in einem Zyklus der Länge zwei anzuordnen.
Genauer: Du suchst die Anzahl der Möglichkeiten, die drei Kugeln so auf die drei Plätze anzuordnen, dass ein Zyklus der Länge 2 enthalten ist.
Ein Beispiel für eine solche Möglichkeit: Die Kugel 1 platzieren wir auf Platz 3, die Kugel 3 auf Platz 1 und die Kugel 2 auf Platz 2.
Das entspricht der Permutation [mm] $\sigma\colon\{1,2,3\}\to\{1,2,3\}$ [/mm] mit [mm] $\sigma(1)=3$, $\sigma(3)=1$ [/mm] und [mm] $\sigma(2)=2$.
[/mm]
> Dann habe ich für die erste Kugel
> 3 Möglichkeiten sie hinzulegen.
Ja. (Die erste Kugel sei dabei der Übersichtlichkeit halber die Kugel mit der 1.)
> Für die nächste (3-1)
Wenn du die Kugeln irgendwie platzieren willst, ja.
Wenn jedoch ein Zyklus der Länge 2 in der fertigen Permutation enthalten sein soll, gibt es nur stets nur noch eine Möglichkeit die übrigen Kugeln zu platzieren:
1. Fall: Wir haben die Kugel 1 auf Platz 1 gelegt.
Dann müssen wir Kugel 2 auf Platz 3 und Kugel 3 auf Platz 2 legen, damit die fertige Permutation einen Zyklus der Länge 2 enthält (nämlich bestehend aus 2 und 3).
2. Fall: Wir haben die Kugel 1 auf Platz [mm] $y\in\{2,3\}$ [/mm] gelegt.
Dann muss die Kugel $y$ auf Platz 1 landen, damit innerhalb der fertigen Permutation ein Zyklus der Länge 2 entsteht.
(Die dritte Kugel neben Kugel 1 und Kugel y landet dann auf dem Platz mit ihrer eigenen Nummer.)
> Mit meiner Schreibweise meinte ich jeweils den Zyklus
>
> 1,2,1,2,1,2 usw.
>
> bzw.
>
> 1,2,3,1,2,3 usw.
Wie gesagt: Es geht nicht um Zyklen an sich, sondern um Permutationen, die gewisse Zykel haben.
(Wenn eine Permutation (in deiner Sprechweise) den Zykel [mm] $1,2,1,2,\ldots$ [/mm] hat, so hat sie automatisch auch den Zykel [mm] $2,1,2,1,\ldots$.)
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:03 Sa 01.11.2014 | | Autor: | YuSul |
"(Wenn eine Permutation (in deiner Sprechweise) den Zykel $ [mm] 1,2,1,2,\ldots [/mm] $ hat, so hat sie automatisch auch den Zykel $ [mm] 2,1,2,1,\ldots [/mm] $.) "
Ah, ok. Das macht Sinn.
Also die 6 Permutationen von [mm] $\Sigma_{\{1,2,3\}}$ [/mm] wären
(1,2)
(1,3)
(2,3)
(1,2,3)
(1,3,2)
Also 3!-1 weil man die Identität nicht zählen würde.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:22 Sa 01.11.2014 | | Autor: | tobit09 |
> Also die 6 Permutationen von [mm]\Sigma_{\{1,2,3\}}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
wären
>
> (1,2)
> (1,3)
> (2,3)
> (1,2,3)
> (1,3,2)
Ich zähle hier nur 5 Permutationen... 
> Also 3!-1 weil man die Identität nicht zählen würde.
(Die Identität auf $\{1,2,3\}$ ist schon eine Permutation aus $\Sigma_{\{1,2,3\}$, aber sie hat keinen Zykel der Länge $\ge 2$.)
Mir ist noch nicht klar, ob dir bewusst ist, welche Permutation du z.B. mit $\sigma=(1,3)$ eigentlich meinst.
Wie lauten also $\sigma(1)$, $\sigma(2)$ und $\sigma(3)$ in diesem Beispiel?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:26 Sa 01.11.2014 | | Autor: | YuSul |
"Mir ist noch nicht klar, ob dir bewusst ist, welche Permutation du z.B. mit $ [mm] \sigma=(1,3) [/mm] $ eigentlich meinst.
Wie lauten also $ [mm] \sigma(1) [/mm] $, $ [mm] \sigma(2) [/mm] $ und $ [mm] \sigma(3) [/mm] $ in diesem Beispiel?"
[mm] $\sigma=(1,3)$ [/mm] ist ja die Permutation die 1 und 3 vertauscht und 2 fest lässt.
[mm] $\sigma(1)=3$
[/mm]
[mm] $\sigma(2)=2$
[/mm]
[mm] $\sigma(3)=1$
[/mm]
Und würde eine Permutation mit einem Zyklus der Länge 2 bezeichnen.
1,3,1,3 usw.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:35 Sa 01.11.2014 | | Autor: | tobit09 |
> "Mir ist noch nicht klar, ob dir bewusst ist, welche
> Permutation du z.B. mit [mm]\sigma=(1,3)[/mm] eigentlich meinst.
>
> Wie lauten also [mm]\sigma(1) [/mm], [mm]\sigma(2)[/mm] und [mm]\sigma(3)[/mm] in
> diesem Beispiel?"
>
> [mm]\sigma=(1,3)[/mm] ist ja die Permutation die 1 und 3 vertauscht
> und 2 fest lässt.
>
> [mm]\sigma(1)=3[/mm]
> [mm]\sigma(2)=2[/mm]
> [mm]\sigma(3)=1[/mm]
>
> Und würde eine Permutation mit einem Zyklus der Länge 2
> bezeichnen.
>
> 1,3,1,3 usw.
![[ok]](/images/smileys/ok.gif "[ok]") Schön! Dann war meine Skepsis unberechtigt.
Deine Aufzählung der Elemente von [mm] $\Sigma_{\{1,2,3\}}$ [/mm] ist dann (wenn man die Identität auf [mm] $\{1,2,3\}$ [/mm] noch hinzunimmt) auch völlig richtig.
Ich glaube, du hast nun verstanden worum es geht.
Jetzt kannst du dich daher wieder dem Abzählproblem widmen, die Anzahl [mm] $|A_k|$ [/mm] der Permutationen aus [mm] $\Sigma_\Xi$, [/mm] die einen Zykel der Länge $k$ haben, zu bestimmen (wobei [mm] $k>\frac{n}{2}$).
[/mm]
Ich wiederhole dazu einen Teil aus meiner ersten Antwort:
Man erhält jede Permutation $ [mm] \sigma\in A_k [/mm] $ nach der folgenden Methode auf genau eine Weise:
1. Man wählt eine $ k $-elementige Teilmenge $ [mm] I\subseteq\{1,\ldots,n\} [/mm] $.
$ I $ soll gerade die $ [mm] x\in\{1,\ldots,n\} [/mm] $ enthalten, die "am Zykel der Länge $ k $ beteiligt" sein sollen.
2. Man legt $ [mm] \sigma(x) [/mm] $ für alle $ [mm] x\in [/mm] I $ fest, so dass diese $ x $ tatsächlich "einen Zykel (der Länge $ k $) bilden".
3. Man legt $ [mm] \sigma(x) [/mm] $ für alle $ [mm] x\in\{1,\ldots,n\}\setminus [/mm] I $ fest, so dass $ [mm] \sigma [/mm] $ injektiv wird.
Bestimme zu 1., 2. und 3. jeweils die Anzahl der möglichen Wahlen.
$ [mm] |A_k| [/mm] $ erhältst du dann als Produkt dieser Anzahlen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:48 Sa 01.11.2014 | | Autor: | YuSul |
zu 1)
Eine n-elementige Menge hat [mm] $\binom{n}{k}$ [/mm] k-elementige Teilmengen.
Hierbei wäre wieder zu beachten, dass [mm] $k\geq [/mm] [n/2]+1$
zu 2)
Das müssten hier dann $n-[n/2]$ Mögliche Zyklen sein.
Am Beispiel der 3 elementigen Menge:
Gesucht sind die Zyklen mit Länge 2 und 3. Das sind zwei verschiedene, bzw. alle die nicht einen Zyklus kleiner als 2 haben.
zu 3)
Das müssten [mm] $n(n-1)\cdot\cdot\cdot(n-[n/2])$ [/mm] sein.
Das Produkt wäre aber sehr unhandlich...
Bei 2) und 3) bin ich mir aber auch nicht wirklich sicher.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:27 Sa 01.11.2014 | | Autor: | tobit09 |
> zu 1)
>
> Eine n-elementige Menge hat [mm]\binom{n}{k}[/mm] k-elementige
> Teilmengen.
> Hierbei wäre wieder zu beachten, dass [mm]k\geq [n/2]+1[/mm]
(Eine $n$-elementige Menge hat auch für [mm] $0\le [/mm] k<[n/2]+1$ genau [mm] $\binom{n}{k}$ [/mm] viele $k$-elementige Teilmengen.)
> zu 2)
>
> Das müssten hier dann [mm]n-[n/2][/mm] Mögliche Zyklen sein.
Nein, z.B. für $n=4$ und $k=4$ stimmt das nicht.
Die korrekte Zahl wird von $k$ abhängen.
> Am Beispiel der 3 elementigen Menge:
>
> Gesucht sind die Zyklen mit Länge 2 und 3.
Nein, wir suchen gerade für festes $k$-elementiges [mm] $I\subseteq\{1,\ldots,n\}$ [/mm] die Anzahl der Möglichkeiten, die [mm] $\sigma(x)$ [/mm] für [mm] $x\in [/mm] I$ so festzulegen, dass "diese $x$ einen Zykel der Länge $k$ bilden".
Beispiel: $n=5$, $k=4$, [mm] $I=\{2,3,4,5\}$
[/mm]
Dann wären die Möglichkeiten:
$(2,3,4,5)$
$(2,3,5,4)$
$(2,4,3,5)$
$(2,4,5,3)$
$(2,5,3,4)$
$(2,5,4,3)$
Dabei meine ich z.B. mit $(2,3,5,4)$ die Festsetzung [mm] $\sigma(2)=3$, $\sigma(3)=5$, $\sigma(5)=4$ [/mm] und [mm] $\sigma(4)=2$.
[/mm]
Wir erhalten jede dieser 6 "Festsetzungenskombinationen" folgendermaßen auf genau eine Weise:
Wir starten (etwas willkürlich) mit [mm] $x_1:=2$.
[/mm]
Dann wählen wir [mm] $x_2=\sigma(x_1)\in\{2,3,4,5\}\setminus\{x_1\}$ [/mm] beliebig. (3 Möglichkeiten).
Dann wählen wir [mm] $x_3=\sigma(x_2)\in\{2,3,4,5\}\setminus\{x_1,x_2\}$ [/mm] beliebig. (2 Möglichkeiten)
Dann wählen wir [mm] $x_4=\sigma(x_2)\in\{2,3,4,5\}\setminus\{x_1,x_2,x_3\}$. [/mm] (1 Möglichkeit)
Schließlich "schließen" wir den Zyklus mit der Festsetzung [mm] $\sigma(x_4)=x_1$. [/mm] (1 Möglichkeit)
Also haben wir im Fall $n=5$ und $k=3$ bei 2. $3*2*1*1$ Möglichkeiten.
Versuche nun, diese Überlegung auf beliebiges $n$ und $k$ zu übertragen.
> Das sind zwei
> verschiedene,
Wovon genau gibt es genau zwei?
> bzw. alle die nicht einen Zyklus kleiner als
> 2 haben.
Was ist mit diesen?
(Im Beispiel $n=3$ haben alle Permutationen, die einen Zyklus der Länge 2 haben, auch einen Zyklus der Länge 1.)
> zu 3)
>
> Das müssten [mm]n(n-1)\cdot\cdot\cdot(n-[n/2])[/mm] sein.
Nein.
Auch hier ein Beispiel: $n=7$, $k=4$, [mm] $I=\{1,3,5,7\}$.
[/mm]
Gesucht sind die möglichen Wahlen für [mm] $\sigma(2)$, $\sigma(4)$ [/mm] und [mm] $\sigma(6)$, [/mm] so dass [mm] $\sigma$ [/mm] injektiv wird:
1,3,5 und 7 sind als Bilder unter [mm] $\sigma$ [/mm] nach 2. schon vergeben.
Als Bilder von 2, 4 und 6 unter [mm] $\sigma$ [/mm] kommen die Werte 2, 4 und 6 in Frage.
Keiner darf doppelt getroffen werden.
Macht für [mm] $\sigma(2)$ [/mm] 3 Möglichkeiten,
dann für [mm] $\sigma(4)$ [/mm] 2 Möglichkeiten
und dann für [mm] $\sigma(6)$ [/mm] 1 übrig bleibende Möglichkeit.
Macht $3*2*1$ Möglichkeiten, die [mm] $\sigma(x)$ [/mm] für die [mm] $x\in \{1,\ldots,n\}\setminus [/mm] I$ festzulegen.
Versuche du nun wieder die Verallgemeinerung auf beliebige $n$, $k$ und $I$.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:13 Sa 01.11.2014 | | Autor: | YuSul |
zu 2)
Dann würde ich hier auf [mm] $\frac{n!}{(n-k)!}$ [/mm] zurückgreifen.
Ah, das sollte dann doch so gesehen ein "ziehen ohne Wiederholung, mit Beachtung der Reihenfolge ohne zurücklegen" sein.
zu 3)
Hier müssten es dann einfach k! sein.
Ich habe eine k-elementige Menge und die möchte ich nun ohne Wiederholung und ohne zurücklegen anordnen.
Insgesamt also:
[mm] $\binom{n}{k}\cdot\frac{n!}{(n-k)!}\cdot k!=\left(\frac{n!}{(n-k)!}\right)^2$
[/mm]
Hmm, nein das wäre für n=3 schon zu groß...
Ich denke zu 2) müsste ich es nochmal überdenken.
Für 3) macht k! sinn (meiner Meinung nach)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:46 Sa 01.11.2014 | | Autor: | tobit09 |
> zu 2)
>
> Dann würde ich hier auf [mm]\frac{n!}{(n-k)!}[/mm] zurückgreifen.
>
> Ah, das sollte dann doch so gesehen ein "ziehen ohne
> Wiederholung, mit Beachtung der Reihenfolge ohne
> zurücklegen" sein.
Das passt nicht zu dem von mir genannten Beispiel $n=5$, $k=4$, in dem wir 6 Möglichkeiten hatten.
Guck dir am Besten nochmal mein Beispiel in der vorherigen Antwort an.
Wir fixieren für die Auflistung der gesuchten Möglichkeiten zunächst ein willkürliches festes Element [mm] $x_1\in [/mm] I$ (im Beispiel [mm] $x_1=2$).
[/mm]
Nun erhalten wir alle Möglichkeiten, die $ [mm] \sigma(x) [/mm] $ für $ [mm] x\in [/mm] I $ so festzulegen, dass "diese $ x $ einen Zykel der Länge $ k $ bilden" auf genau eine Weise, indem wir nacheinander:
[mm] $\sigma(x_1)=x_2\in I\setminus\{x_1\}$ [/mm] wählen (k-1 Möglichkeiten)
[mm] $\sigma(x_2)=x_3\in I\setminus\{x_1,x_2\}$ [/mm] wählen (k-2 Möglicheiten)
[mm] $\sigma(x_3)=x_4\in I\setminus\{x_1,x_2,x_3\}$ [/mm] wählen (k-3 Möglichkeiten)
...
[mm] $\sigma(x_{k-1})=x_k\in I\setminus\{x_1,x_2,x_3,\ldots,x_{k-1}\}$ [/mm] wählen (k-(k-1)=1 Möglichkeit)
[mm] $\sigma(x_k)=x_1$ [/mm] wählen (1 Möglichkeit)
Das macht also insgesamt
[mm] $((k-1)*(k-2)*(k-3)*\ldots*1)*1=\ldots$
[/mm]
Möglichkeiten.
> zu 3)
>
> Hier müssten es dann einfach k! sein.
> Ich habe eine k-elementige Menge
Nein, du hast mit [mm] $\{1,\ldots,n\}\setminus [/mm] I$ eine $(n-k)$-elementige Menge.
Entsprechend liegst du mit $(n-k)!$ richtig.
> Insgesamt also:
>
> [mm]\binom{n}{k}\cdot\frac{n!}{(n-k)!}\cdot k!=\left(\frac{n!}{(n-k)!}\right)^2[/mm]
Folgerichtig.
Kannst du nun alles zusammenfügen?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:54 Sa 01.11.2014 | | Autor: | YuSul |
Ja, so müsste man dann auf insgesamt
[mm] $\frac{n!}{k}$ [/mm] kommen.
Ich werde mir nochmal genau ansehen wie 2) zustande kommt, aber ich denke ich habe es nun begriffen. Was diese Aufgabe angeht, habe ich mittlerweile nen ziemlich Knoten im Kopf, weil ich schon so viele verschiedene Abzählungen "gebaut" habe.... Die schwirren da oben noch irgendwie rum und verwirren mich. :)
Dann wäre also die Anzahl der Möglichkeiten:
[mm] $\sum_{k=[n/2]+1}^n \frac{n!}{k}$
[/mm]
Auf einer n-elementigen Menge einen Zyklus k>n/2 zu bilden.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:30 Sa 01.11.2014 | | Autor: | YuSul |
Schön.
Und im zweiten Teil wäre die Lösung einfach
[mm] $P(A)=\sum_{[n/2]+1}^{n} \frac{1}{k}$
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:44 Sa 01.11.2014 | | Autor: | tobit09 |
> Und im zweiten Teil wäre die Lösung einfach
>
> [mm]P(A)=\sum_{[n/2]+1}^{n} \frac{1}{k}[/mm]
Genau, so lautet das Endergebnis beim zweiten Teil.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:25 Sa 01.11.2014 | | Autor: | YuSul |
Vielen Dank.
Wenn ich in der letzten Summe das n gegen unendlich laufen lasse, dann soll der Grenzwert ln(2) sein. Ich weiß nur, dass die alternierende harmonische Reihe diesen Grenzwert hat und sehe hier leider gerade nicht unbedingt einen Zusammenhang. Hättest du da eine Idee?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:01 So 02.11.2014 | | Autor: | tobit09 |
> Wenn ich in der letzten Summe das n gegen unendlich laufen
> lasse, dann soll der Grenzwert ln(2) sein.
Wir betrachten
[mm] $b_n:=\integral_{[\frac{n}{2}]}^n\frac{1}{x}\;dx$ [/mm] (für [mm] $n\ge [/mm] 2$)
und
[mm] $c_n:=\integral_{[\frac{n}{2}]+1}^{n+1}\frac{1}{x}\;dx$.
[/mm]
1. Bilde die Untersumme des Integrals aus der Definition von [mm] $b_n$ [/mm] bezüglich der Zerlegung des Intervalls [mm] $[[\frac{n}{2}],n]$ [/mm] gegeben durch
[mm] $[\frac{n}{2}]$, $[\frac{n}{2}]+1$, $[\frac{n}{2}]+2$, $\ldots$ [/mm] , $n$.
Ebenso bilde die Obersumme des Integrals aus der Definition von [mm] $c_n$ [/mm] bezüglich der Zerlegung des Intervalls [mm] $[[\frac{n}{2}]+1,n+1]$ [/mm] gegeben durch
[mm] $[\frac{n}{2}]+1$, $[\frac{n}{2}]+2$, $[\frac{n}{2}]+3$, $\ldots$ [/mm] , $n+1$.
In beiden Fällen solltest du [mm] $\sum_{k=[\frac{n}{2}]+1}^n\frac{1}{k}$ [/mm] erhalten.
Also folgt
[mm] $c_n\le\sum_{k=[\frac{n}{2}]+1}^n\frac{1}{k}\le b_n$.
[/mm]
2. Zeige [mm] $\lim_{n\to\infty}b_n=\ln [/mm] 2$ und [mm] $\lim_{n\to\infty}c_n=\ln [/mm] 2$.
Aus 1. und 2. folgt die Behauptung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:37 So 02.11.2014 | | Autor: | YuSul |
Vielen Dank für deine Hilfe. Ich denke das sollte ich nun alleine hinbekommen.
Schönes Rest Wochenende.
|
|
|
|
