www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Wahrscheinlichkeitsrechnung" - Stichprobe, Permutation
Stichprobe, Permutation < Wahrscheinlichkeit < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Wahrscheinlichkeitsrechnung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Stichprobe, Permutation: Laplaceraum
Status: (Frage) beantwortet Status 
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.

        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
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]

Bezug
                                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
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]

Bezug
                                                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                                                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
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?

Bezug
                                                                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.


Bezug
                                                                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
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] 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. [ok]


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.

Bezug
                                                                                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                                                                                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
Datum: 19:27 Sa 01.11.2014
Autor: tobit09


> zu 1)
>  
> Eine n-elementige Menge hat [mm]\binom{n}{k}[/mm] k-elementige
> Teilmengen.

[ok]

> 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$.

Bezug
                                                                                                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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)

Bezug
                                                                                                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
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?

Bezug
                                                                                                                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                                                                                                                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
Datum: 21:21 Sa 01.11.2014
Autor: tobit09


> Ja, so müsste man dann auf insgesamt
>  
> [mm]\frac{n!}{k}[/mm] kommen.

[ok]


> 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. :)

Ehrlich gesagt geht es mir ein bisschen ähnlich... ;-)


> Dann wäre also die Anzahl der Möglichkeiten:
>  
> [mm]\sum_{k=[n/2]+1}^n \frac{n!}{k}[/mm]

[ok] Ja, das ist die Anzahl $|A|$ der Permutationen in [mm] $\Sigma_\Xi$, [/mm] die einen Zyklus einer Länge [mm] $>\frac{n}{2}$ [/mm] enthalten.


> Auf einer n-elementigen Menge einen Zyklus k>n/2 zu bilden.

Nein. Es geht nicht um eine Zahl von Zyklen, sondern um eine Zahl von Permutationen, die gewisse Zyklen enthalten!!!

Bezug
                                                                                                                                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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]



Bezug
                                                                                                                                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
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]

[ok] Genau, so lautet das Endergebnis beim zweiten Teil.

Bezug
                                                                                                                                                
Bezug
Stichprobe, Permutation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                                                                                                                        
Bezug
Stichprobe, Permutation: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                                                                                                                                
Bezug
Stichprobe, Permutation: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Wahrscheinlichkeitsrechnung"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de