Anzahl an Permutationen bestimmen

01.01.2015, 20:22

JayKay42

Auf diesen Beitrag antworten »

Anzahl an Permutationen bestimmen

Hallo,

ich habe folgende Aufgabe:

Ich soll die Anzahl der Permutationen aller Zahlen bis 2n bestimmen, bei der jede ungerade Zahl nicht auf ihrem eigenen Platz steht (also 3 nicht an 3. Stelle etc.).

Nun habe ich wie folgt angefangen, aber das scheint vom Ergebnis her totaler Käse zu sein:

Zuerst die Definition der Permutation: eine P. ist ein geordnetes k-Tupel verschiedener Elemente aus S, wobei S eine n-Menge ist (also eine Menge mit n Elementen).

Notation: P(n,k) = Anzahl k-Permutationen einer n-Menge.

Satz: P(n,k) = $\begin{eqnarray*} \frac{n!}{(n-k)!} \end{eqnarray*}$

Soweit zur Definition.

Meine Überlegungen:

Anzahl ungerader Zahlen ist also 2n-1, wenn ich annehme das 2n die "Grenze" der Zahlen ist. (In der Tat fällt mir aber gerade auf, dass die "letzte" Zahl ja auch ungerade sein, dann wäre 2n-1 die "Anzahl" an gerader Zahlen... 1. Problem).

Im nächsten Schritt habe ich also versucht, n aus k auszuwählen, also die ungeraden Zahlen aus den geraden bzw. deren Möglichkeiten. Somit ergab sich bei Annahme das 2n = gerade Zahlen sind und 2n-1 ungerade, der Binomialkoeffizient von

$\begin{eqnarray*} \binom{2n-1}{2n} \end{eqnarray*}$ .

Mein "Ausrechnen" was dann völlig vermurkst ist:

P(n,k) = $\begin{eqnarray*} \frac{n!}{(n-k)!} \end{eqnarray*}$
= $\begin{eqnarray*} \frac{(2n-1)!}{(2n)!} \end{eqnarray*}$
= $\begin{eqnarray*} \frac{(2n-1)*(2n-2)*(2n-3)*...*(2n-n)}{(2n)*(2n-1)*(2n-2)*...*(2n-n)} \end{eqnarray*}$

nach kürzen erhalte ich:

$\begin{eqnarray*} \frac{1}{2n} \end{eqnarray*}$

(oder hätte ich die ungeraden und geraden anders herum gewählt, 2n als Ergebnis. Allerdings scheint mir das nicht so ganz richtig zu sein. Wobei 2n noch besser klingt als der Kehrwert davon.

Wo liegen meine Fehler? Wie kann ich die Aufgabe besser angehen?

01.01.2015, 21:14

Another

Auf diesen Beitrag antworten »

Du kannst so vorgehen: Berechne die Anzahl der Permutationen, wenn jede ungerade Zahl auf ihrer Position bleibt, und ziehe diese von der Anzahl aller Permutationen ab. Ersteres ist leicht zu berechnen, da ja schon n Positionen der 2n Zahlen festgelegt sind, also effektiv nur n vertauscht werden können.

01.01.2015, 21:17

Another

Auf diesen Beitrag antworten »

Hab gerade Unsinn geschrieben. Bitte ignorieren:P vllt fällt mir noch was gescheites ein...

01.01.2015, 22:34

Magix

Auf diesen Beitrag antworten »

RE: Anzahl an Permutationen bestimmen
Zuerst eine kleine Anmerkung, ich habe auch keine gute Lösung für dieses Problem. Sollte also jemand mit mehr Ahnung einspringen wollen, dann soll er das tun! smile

smile

Zitat:

Original von JayKay42

Anzahl ungerader Zahlen ist also 2n-1, wenn ich annehme das 2n die "Grenze" der Zahlen ist. (In der Tat fällt mir aber gerade auf, dass die "letzte" Zahl ja auch ungerade sein, dann wäre 2n-1 die "Anzahl" an gerader Zahlen... 1. Problem).

JayKay42, überleg dir nochmal wieviele ungerade Zahlen es gibt, wenn ich von 1 bis 2n zähle.

1, 2, 3, 4, ... , 2n wieviele gerade Zahlen, und wieviele ungerade Zahlen haben wir?

01.01.2015, 22:43

Guppi12

Auf diesen Beitrag antworten »

Hallo,

definiere Mengen $\begin{eqnarray*} A_i := \{\sigma\in S_{2n}~\vert~ \sigma(i) = i\} \end{eqnarray*}$ .

Das Komplement der gesuchten Menge lässt sich nun als Vereinigung von bestimmten $\begin{eqnarray*} A_i \end{eqnarray*}$ schreiben. Weiteres Stichwort: Siebformel.

Edit: Habe gerade nochmal nachgelesen. Wenn es nicht um Wahrscheinlichkeiten geht, nennt man das nicht Siebformel, sondern Prinzip von Inklusion und Exklusion.

Edit2: Danke HAL für den Hinweis. Gut zu wissen Freude

Freude

01.01.2015, 23:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Guppi12
Wenn es nicht um Wahrscheinlichkeiten geht, nennt man das nicht Siebformel, sondern Prinzip von Inklusion und Exklusion.

Das würde ich nicht so eng sehen: Ich verwende beide Begriffe synonym. Augenzwinkern

Augenzwinkern

Auf alle Fälle ist das hier der Schlüssel zur Lösung.

Anzeige

05.01.2015, 09:47

JayKay42

Auf diesen Beitrag antworten »

Hallo Guppi (und auch alle anderen),

vielen Dank erstmal für die TIpps. In der Tat habe ich mir notiert, dass Inklusion und Exklusion zu nutzen sind. Wir bekommen immer Tipps was am sinnvollsten ist, oder was wir sogar nicht verwenden sollen, da sonst keine Punkte. Bei der Aufgabe wie gesagt Inklusion und Exklusion.

Bei Wikipedia habe ich schonmal gefunden, dass man bei Siebformel direkt auf "Inklusion und Exklusion" verwiesen wird. Scheinbar identisch (bitte nicht lünchen wenn es doch was anderes ist, sondern mir den Unterschied erklären).

Soweit ich das schonmal in einer anderen Aufgabe geübt habe, müsste das Prinzip ja folgendes sein: Ich "zähle erstmal alle Möglichkeiten, wie viele ungerade Zahlen es bei 2n gibt. Das wären meiner Meinung nach n (oder n+1) wenn die generelle Anzahl ungerade ist, z.B. bei 5. Da habe ich die 1, 3 und die 5, also 3 ungerade Zahlen. (Dabei fällt mir aber gerade auf, dass die Hälfte von 5 2,5 ist und man daher evtl mit oberen Schranken arbeiten sollte? Also obere Schranke von 2,5 dann. Ist das ein besserer Ansatz?

Davon müsste ich dann - und jetzt kommt meiner Meinung nach der schwierigere Teil - was abziehen. Eigentlich die Möglichkeiten, wo die ungeraden Zahlen alle an ihrem Platz stehen. Oder ich wähle den anderen Weg (für mich auch nicht einfacher), wo ich alle Möglichkeiten, wo ungerade Zahlen auf einem anderen Platz stehen, aufaddiere. Ich vermute dass der erste Weg (ungerade Zahlen insgesamt minus ungerade Zahlen, die an ihrem Platz stehen) sinnvoller ist. Begründen kann ich das aber nicht. Ist die Idee aber prinzipiell sinnvoll?

05.01.2015, 10:05

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von JayKay42
Ich "zähle erstmal alle Möglichkeiten, wie viele ungerade Zahlen es bei 2n gibt. Das wären meiner Meinung nach n (oder n+1) wenn die generelle Anzahl ungerade ist, z.B. bei 5. Da habe ich die 1, 3 und die 5, also 3 ungerade Zahlen. (Dabei fällt mir aber gerade auf, dass die Hälfte von 5 2,5 ist und man daher evtl mit oberen Schranken arbeiten sollte?

Du hast hier nicht die Zahlen $\begin{align*} 1\ldots n \end{align*}$ , sondern $\begin{align*} 1\ldots 2n \end{align*}$ , und in diesem Bereich gibt es genau $\begin{align*} n \end{align*}$ ungerade Zahlen (nicht "evtl." $\begin{align*} n+1 \end{align*}$ ). Bring mal Ordnung in deine wirren Gedanken über die inhaltliche Bedeutung von $\begin{align*} n \end{align*}$ hier. Augenzwinkern

Augenzwinkern

Es geht aber nicht darum, nur die Anzahl der ungeraden Zahlen zu zählen. Wie Guppi12 es bereits gesagt hat, es werden Teilmengen von Permutationen betrachten, und zwar

$\begin{eqnarray*} A_i := \{\sigma\in S_{2n}~\vert~ \sigma(i) = i\} \end{eqnarray*}$ .

Da sind alle Permutationen von $\begin{align*} 1\ldots 2n \end{align*}$ drin, die an Position $\begin{align*} i \end{align*}$ einen Fixpunkt haben, es ist also $\begin{align*} |A_i|=(2n-1)! \end{align*}$ , denn Position $\begin{align*} i \end{align*}$ ist fix, und alle anderen $\begin{align*} (2n-1) \end{align*}$ Stellen dürfen beliebig permutieren.

Betrachten wir nun

$\begin{align*} A_1 \cup A_3 \cup A_5\cup \ldots \cup A_{2n-3} \cup A_{2n-1} \end{align*}$ ,

so enthält diese Vereinigung alle diejenigen Permutationen, die an mindestens einer ungeraden Position einen Fixpunkt haben. Und das ist genau das, worauf Guppi12 hier

Zitat:

Original von Guppi12
Das Komplement der gesuchten Menge lässt sich nun als Vereinigung von bestimmten $\begin{eqnarray*} A_i \end{eqnarray*}$ schreiben.

hingewiesen hat.

05.01.2015, 10:34

JayKay42

Auf diesen Beitrag antworten »

Hallo HAL9000,

da n variabel ist, kann man annehmen, dass ich bei 2n zur einen Hälfte gerade Zahlen und zur anderen Hälfte ungerade Zahlen habe, also 2n / 2 teile, was n ergibt. Damit kann ich leben Augenzwinkern

Augenzwinkern

Freude

Zitat:

$\begin{eqnarray*} A_i := \{\sigma\in S_{2n}~\vert~ \sigma(i) = i\} \end{eqnarray*}$ .Da sind alle Permutationen von 1…2n drin, die an Position i einen Fixpunkt haben, es ist also |Ai|=(2n−1)!, denn Position i ist fix, und alle anderen (2n−1) Stellen dürfen beliebig permutieren.

Die Formel oben kenne ich zwar so nicht direkt, und ist auch nicht in unserem Skript, aber die Erklärung dazu ist plausibel - darauf will ich ja hinaus.

Mir stellt sich noch die Frage, ob ich mit den permutierenden ungeraden Zahlen und der Vereinigung definitiv ausschließen kann, dass sich doch eine ungerade Zahl auf ihren richtigen Platz verirrt. Denn wie du schriebst, dürfen ja die ungeraden Zahlen in ihrem ungeraden Bereich beliebig permutieren. Aber kann es auch vorkommen (und damit nicht die Aufgabe erfüllen), dass sich eine ungerade Zahl nicht auf den richtigen (falschen) Platz verirrt, und wenn nein, woran erkenne ich, dass dies explizit ausgeschlossen wird? Oder ist das so etwas, was man "aktzeptieren" muss, dass das schon nicht passieren wird? Das ist mir noch nicht ganz klar.

05.01.2015, 10:42

HAL 9000

Auf diesen Beitrag antworten »

Bist du dir sicher, dass du den Satz

Zitat:

Original von HAL 9000
Betrachten wir nun

$\begin{align*} A_1 \cup A_3 \cup A_5\cup \ldots \cup A_{2n-3} \cup A_{2n-1} \end{align*}$ ,

so enthält diese Vereinigung alle diejenigen Permutationen, die an mindestens einer ungeraden Position einen Fixpunkt haben.

wirklich inhaltlich voll verstanden hast? Macht nicht den Eindruck. unglücklich

unglücklich

Selbstverständlich ist diese Vereinigung nicht disjunkt, deshalb ja brauchen wir zur Berechnung von deren Mächtigkeit die Inklusion-Exklusion-Formel.

05.01.2015, 10:50

JayKay42

Auf diesen Beitrag antworten »

Ne, ich meinte auch den Satz den ich oben zitiert habe. Mit der Vereinigung versuche ich mich gerade nebenbei schriftlich auseinander zu setzen und mir das eben schriftlich irgendwie zu verdeutlichen dass es für mich klarer wird.

Die Aussage

Zitat:

Betrachten wir nunA1∪A3∪A5∪…∪A2n−3∪A2n−1,so enthält diese Vereinigung alle diejenigen Permutationen, die an mindestens einer ungeraden Position einen Fixpunkt haben.

deute ich wie folgt: Ich habe meine Anzahl an Permutationen und ich habe mir noch einmal angeschaut, wie das Prinzip der Inklusion und Exklusion funktioniert.

Zum Prinzip der I und E: Ich schätze erstmal nach oben hin ab, wie viele Möglichkeiten ich habe. Wenn ich diese allerdings alle aufaddieren würde, hätte ich doppelt, dreifach usw. gezählt. Das muss dann nochmal im nachhinein abgezogen werden.

Bei der Anzahl an Permutationen aus dem Zitat oben gehe ich - wenn ich es richtig verstanden habe - der Reihe nach alle Permutationen durch - angefangen von 1, über 3, 5, 7 .... bis 2n und gehe für jede ungerade Stelle n die Möglichkeiten durch, mit denen ich diesen Platz belegen kann, d.h. für die erste Stelle darf ich die 1 nicht wählen, also bleiben mir noch n-1 Möglichkeiten übrig. So verfahre ich mit allen n ungeraden Stellen. Wobei ich dann für die nächste Stelle n-2, dann für die wiederrum nächste n-3 Stellen zur Verfügung habe, da die Zahl die nicht dort stehen darf abgezogen wird, plus die Zahlen, die ich ja vorher schon "vergeben" habe an andere Plätze.

Das habe ich doch so richtig verstanden, oder? Dann macht es auch Sinn, dass WENN ich schon die Zahl ausnehme, die nicht an "ihrer" Stelle stehen darf, auch tatsächlich nicht mehr auftaucht oder auftauchen kann.

Ist dies so korrekt?

Mein nächster Schritt wäre dann, mich mit der Summe auseinander zu setzen bzw. mit der Vereinigung, um dies gescheit zu formulieren, wie ich es oben ausgeführt habe. (Wenn dies korrekt ist)

05.01.2015, 11:36

HAL 9000

Auf diesen Beitrag antworten »

Du machst dir Gedanken, die allesamt nicht nötig, wirr, und kontraproduktiv sind:

Ein letztes Mal: Wir haben die $\begin{align*} A_i \end{align*}$ definiert und den inhaltlichen Zusammenhang zur Fragestellung hergestellt. Alles, was nun noch bleibt ist die Inklusion-Exklusion-Formel anzuwenden, und für diese benötigen wir die Durchschnittsmächtigkeiten

$\begin{align*} \left|A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_m}\right| \end{align*}$

für unterschiedliche Indizes $\begin{align*} i_1,\ldots,i_m \end{align*}$ . D.h., wir brauchen uns gar keine Gedanken darüber zu machen, dass an bestimmten Positionen der Permutation ein Wert nicht vorkommen darf, sondern nur darüber, dass an bestimmten Stellen Fixpunkte sind (was an den anderen Stellen passiert - Fixpunkt oder nicht - ist da irrelevant), darin besteht ja gerade die Vereinfachung dieses Wegs über die Inklusion-Exklusion-Formel!!!

05.01.2015, 20:49

JayKay42

Auf diesen Beitrag antworten »

Ok. Ich versuche es nur wirklich zu verstehen, statt stumpf etwas anzuwenden, aber keine Ahnung zu haben, wieso ich das anwende und was es mir bringt. Daher frage ich da etwas genauer nach. Letzten Endes helfen mir solche Fehler ja auch endlich mal zu verstehen, worum es exakt geht.

Die Formel die ich für Inklusion und Exklusion finden kann, ist diese hier:
$\begin{eqnarray*} | A_1 \cup A_2 \cup ... \cup A_n | = \sum\limits_{1\leq i\leq n} | A_i | -\sum\limits_{1\leq i\leq j\leq n} | A_i \cap A_j | + \sum\limits_{1\leq i\leq j\leq k\leq n} | A_i \cap A_j \cap A_k | - ... + ... + (-1)^{n+1} |A_1 \cap A_2 \cap ... \cap A_n |. \end{eqnarray*}$

Sie gilt für A1, A2, ..., An endliche Mengen. Sozusagen wären meine Plätze ja die endlichen Mengen, oder nicht?

Es gibt noch eine andere Formel welche wir zur Verfügung haben, dort geht es aber um ein n0, was den Anzahl der Elemente in S entspricht, die in keiner Teilmenge liegen. Ich vermute aber das obige Formel die richtige ist, korrekt?

Allerdings ist es schwierig, die Formel auszurechnen oder zu einem Wert zu kommen, da sie relativ komplex ist und ja quasi bis n geht. Ich frage mich, wie ich "so viel" aufsummieren kann oder das gescheit umschreiben kann. Ich hätte da jetzt einfach die Formel hingeschrieben da ich nicht weiß wie es weitergeht oder ich gescheite Sachen einsetze.

Für unseren Fall, dass es sich um jede zweite Zahl handelt, muss ich, wie bereits erwähnt wurde, nur die ungeraden Stelle (A1, A3, A5) etc. nehmen. Da die Formel aber bis n geht, vereinfacht das für mich nichts. Mehr als " $\begin{eqnarray*} +(-1)^{n+1} | A_1 \cap A_3 \cap ... \cap A_n | \end{eqnarray*}$ " fällt mir dazu nicht ein, da ich nicht weiß was ich für i, n, j, k etc. einsetzen soll. Und selbst dann wird bei n Zahlen das ganze ja sehr groß und lang.

05.01.2015, 21:09

HAL 9000

Auf diesen Beitrag antworten »

Naja, dass wir nur die ungeraden Indizes nehmen, und du trotzdem die allgemeine Formel nehmen willst, dem kann man ja abhelfen:

Wir definieren $\begin{align*} B_i:=A_{2i-1} \end{align*}$ für $\begin{align*} i=1,2,\ldots,n \end{align*}$ , dann kannst du direkt

$\begin{align*} | B_1 \cup B_2 \cup \ldots \cup B_n | = \sum\limits_{1\leq i\leq n} | B_i | -\sum\limits_{1\leq i\leq j\leq n} | B_i \cap B_j | + \sum\limits_{1\leq i\leq j\leq k\leq n} | B_i \cap B_j \cap B_k | -+ \ldots + (-1)^{n+1} |B_1 \cap B_2 \cap \ldots \cap B_n | \end{align*}$

anwenden. Die Formel sieht schlimmer aus, als sie ist: Aus Symmetriegründen sollte im vorliegenden Fall klar sein, dass die Durchschnittsmächtigkeiten nur von der Anzahl der Mengen abhängt, die den Durchschnitt bilden. Damit reduziert sich der Aufwand schon enorm.

Zitat:

Original von JayKay42
Ok. Ich versuche es nur wirklich zu verstehen, statt stumpf etwas anzuwenden, aber keine Ahnung zu haben, wieso ich das anwende und was es mir bringt. Daher frage ich da etwas genauer nach. Letzten Endes helfen mir solche Fehler ja auch endlich mal zu verstehen, worum es exakt geht.

An sich lobenswert. Leider hast du am Thema vorbeidiskutiert, was den einmal angefangenen Weg mit der Siebformel betrifft, sondern hast wohl deinen alten Weg weitergeführst (oder was auch immer), jedenfalls nichts, was irgendwie erfolgversprechend aussieht.

Hier haben wir direkt (über das Komplement) die gesuchte Zielanzahl mit der Vereinigung der genannten Mengen verknüpfen können, wobei sich herausstellen wird (wenn du wenigstens etwas Geduld und Vertrauen hättest), dass die Mächtigkeiten der Durchschnitte sehr sehr einfach bestimmbar sind.

05.01.2015, 21:37

JayKay42

Auf diesen Beitrag antworten »

In der Tat ist es ein bekanntes und für mich sehr nachteiliges Problem, dass ich unterbewusst immer "meinen" Weg gehen will, auch wenn er total falsch ist. Wurde mir schon öfter gesagt, versuche ich zu ändern. Ist aber sehr schwer da sich das so eingebürgert hat im Hirn. Muss ich einfach öfter üben und lernen.

Die Formel war auch nur die allgemeine aus unserem Skript. Angepasst wähle ich dann A1, A3 oder eben die schönere Lösung mit B1, B2 wie im vorherigen Post.

Die Mengen versuche ich mir bildlich als Venn-Diagramm darzustellen. Mein Gehirn verknotet sich schon bei der Tatsache, dass ich n verschiedene Mengen habe und es geschätzt eine Fantastilliarde Schnittmengen gibt. Big Laugh

Big Laugh

Spaß beiseite. Daherhabe ich doch als "Anzahl der Mengen, die den Durchschnitt bilden", sehr viele. Zumindest n wegen der Symmetriegründe. Irgendwie versteh ichs trotzdem nicht. Ein Vergleich mit einer ähnlichen Formel und mein Versuch, das umzumünzen darauf, führt zum kläglichen Versuch, die Siebformel auf

$\begin{eqnarray*} n!- \binom{n}{1} (n-1)! + \binom{n}{2} * (n-2)! -\binom{n}{3}*(n-3)! + ... \end{eqnarray*}$ zu bringen. Aber das ist lediglich von einer anderen Aufgabe abgekupfert, verstanden habe ich es nicht wirklich. Bin langsam nur sehr frustriert weil ich so gar keinen Fortschritt mache, mich aber echt bemühe statt den Krempel in die Ecke zu schmeißen. Auch wenn Symmetrie und alles vorliegt - für mich sieht diese Formel oben (allgemein) einfach nur aus wie ein riesen, unbezwingbarer Wulst. Trotz Symmetrie.

05.01.2015, 21:41

HAL 9000

Auf diesen Beitrag antworten »

Ähnlich, aber nicht genau gleich. Ich bin jetzt auch langsam weichgekocht und gebe jetzt einfach mal das Endergebnis an, und du denkst darüber nach (oder auch nicht) wie das mit der Siebformel zustande gekommen ist:

$\begin{align*} \sum_{k=0}^n (-1)^k \binom{n}{k} (2n-k)! = (2n)! - \binom{n}{1}\cdot (2n-1)! + \binom{n}{2} \cdot (2n-2)! -+ \ldots + (-1)^n (2n-n)! \end{align*}$ .

05.01.2015, 22:32

JayKay42

Auf diesen Beitrag antworten »

Danke für deine Bemühungen. Ich wollte wirklich keinen ärgern, sondern ich verstehe es halt wirklich nicht. Ich werde die Lösung nutzen um zu sehen, wie ich ich mit der Siebformel dorthin gelange. Wenn ich die Lösung habe, werde ich mich nochmal melden. Vllt haben andere dann auch Lust zu antworten und es "lastet" quasi nicht auf einer Schulter alleine.

06.01.2015, 11:46

HAL 9000

Auf diesen Beitrag antworten »

Interessantes Detail noch am Rande: Betrachtet man nicht die Anzahl, sondern die Wahrscheinlichkeit, dass eine solche $\begin{align*} 2n \end{align*}$ -Permutation an den ungeraden Stellen fixpunktfrei ist, dann ergibt sich für $\begin{align*} n\to\infty \end{align*}$

$\begin{align*} \frac{1}{(2n)!} \sum_{k=0}^n (-1)^k \binom{n}{k} (2n-k)! \to e^{-\frac{1}{2}}\approx 0.60653 \end{align*}$ ,

was nicht so gar sehr verwundert wenn man weiß, dass bei komplett fixpunktfreien Permutationen der entsprechende Grenzwert $\begin{align*} e^{-1} \end{align*}$ ist.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »