Permutationen!

03.01.2010, 13:57

Mäuschen1985

Permutationen!

Hallo!

Ich hab eibne Aufgabe, bei der ich nichtmal ansatzweise weiss wie ich da rangehen soll unglücklich

Bestimmen sie die Anzahl der permutationen der zahlen 1,2,...,2n, bei denen keine ungerade Zahl auf ihrem natürlichen Platz steht.

Kann mir da jemand eventuell weiterhelfen? Das wäre sehr nett!

lg

mäuschen

03.01.2010, 15:26

Cel

Auf diesen Beitrag antworten »

Sagt dir der Begriff "Derangement" bzw. "Derangementzahl" etwas?

03.01.2010, 15:33

Mäuschen1985

Auf diesen Beitrag antworten »

hi!

Ja das habe ich schonmal gehört, allerdings weiss ich nicht wie ich das jetzt explizit auf die aufgabe anwenden soll unglücklich

kannst du mir da eventuell einen einstieg geben?

03.01.2010, 15:39

Cel

Auf diesen Beitrag antworten »

Ich wollte nur mal erst gucken, ob wir mit den Derangements arbeiten können. Augenzwinkern

So, die ungeraden Zahlen sollen also durch eine Permutation auf einen anderen Platz kommen. Hört sich ja stark nach Derangements an. Wie viele ungerade Zahlen gibt es denn von 1, ..., 2n?

03.01.2010, 15:50

Mäuschen1985

Auf diesen Beitrag antworten »

okay, also ich würde sagen es gibt n ungerade zahlen von 1, ..., 2n

03.01.2010, 16:26

Cel

Auf diesen Beitrag antworten »

Gut, wir betrachten jetzt nur die n ungeraden Zahlen und deren Permutationen. Wie viele Derangements dieser Zahlen gibt es denn? Und wie viele Permutationen der restlichen n geraden Zahlen, die beliebig permutiert werden dürfen? Multiplizieren und fertig! smile

03.01.2010, 16:41

wisili

Auf diesen Beitrag antworten »

... und dann kommen noch all die vielen Mischsituationen vor, wo ungerade Zahlen
Plätze der geraden Zahlen einnehmen.

03.01.2010, 16:43

Cel

Auf diesen Beitrag antworten »

Tatsächlich ... das hab ich nicht bedacht. Die feheln auch noch ...

03.01.2010, 17:29

wisili

Auf diesen Beitrag antworten »

Bei den sogenannt «totalen» Permutationen darf kein Element auf dem natürlichen Platz sein.
Man kann ihre Anzahl mit dem Siebtheorem berechnen. Die entsprechende Formel findet man
oft in Formelsammlungen.

Und wer jene Herleitung kennt, kann das vorliegende, sehr ähnliche Problem auf dieselbe Art lösen.
Wer sie aber nicht kennt, wird hier eine schwierige Aufgabe vor sich haben ...

Ich nenne mal die Formel:
$\begin{eqnarray*} \sum _{k=0}^n (-1)^{k}(2n-k)!\begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

Beispiel: n=2 gibt 14.

(Und für grosse n scheint die Zahl mit (2n)! ein Verhältnis zu bilden, das gegen $\begin{eqnarray*} \frac{1}{e^{0.5}} = 0.6065... \end{eqnarray*}$ strebt. Der Beweis müsste mit der Taylorreihe der Exp-Funktion gehen.)

03.01.2010, 18:27

Auf diesen Beitrag antworten »

Zitat:

Original von wisili
(Und für grosse n scheint die Zahl mit (2n)! ein Verhältnis zu bilden, das gegen $\begin{eqnarray*} \frac{1}{e^{0.5}} = 0.6065... \end{eqnarray*}$ strebt. Der Beweis müsste mit der Taylorreihe der Exp-Funktion gehen.)

In der Tat. Das bringt mich auf eine interessante Verallgemeinerung:

Betrachtet man den Anteil $\begin{eqnarray*} p_n \end{eqnarray*}$ derjenigen Permutationen von $\begin{eqnarray*} \{1,\ldots,n\} \end{eqnarray*}$ , die an $\begin{eqnarray*} m_n \end{eqnarray*}$ vorher festgelegten Positionen keine Fixpunkte aufweisen, wobei $\begin{eqnarray*} \lim\limits_{n\to\infty} \frac{m_n}{n} = \lambda \end{eqnarray*}$ für ein $\begin{eqnarray*} \lambda\in(0,1) \end{eqnarray*}$ gelten möge, dann gilt

$\begin{eqnarray*} \lim\limits_{n\to\infty} p_n = e^{-\lambda} \end{eqnarray*}$ .

P.S.: Die Formulierung dieser Aussage, sowie deren Analyse durch den geneigten Leser dauert fast genauso lange wie der Beweis dieser Aussage. Big Laugh

04.01.2010, 10:04

Lapalie

Auf diesen Beitrag antworten »

Was ist denn nun die Antwort hier?

04.01.2010, 10:22

Auf diesen Beitrag antworten »

Wenn du mal aufmerksam lesen würdest, dann müsstest du diese Frage nicht stellen:

Zitat:

Original von wisili
Ich nenne mal die Formel:
$\begin{eqnarray*} \sum _{k=0}^n (-1)^{k}(2n-k)!\begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

Beispiel: n=2 gibt 14.

08.01.2011, 17:23

finchmeister

Auf diesen Beitrag antworten »

Moin,

auch wenn der Beitrag schon älter ist. Muss ich da mal noch was zu fragen.
Ich muss leider die gleiche Aufgabe bearbeiten. Und mit der bisher hier gezeigten Lösung kann ich nix anfangen. Meine Überlegungen dazu.

Wenn ich die Aufgabenstellung korrekt verstanden habe sollen alle Zahlen der Form:
Ziffer 1 auf 1. Stelle, Ziffer 3 auf 3. Stelle, Ziffer 5 auf 5. Stelle usw. ausgeschlossen werden.

Ich setze mal eine Inklusion/Exklusion an:

S = {alle Zahlen <= 2n}
|S| = 2n
A_i = {alle Zahlen mit Ziffer i an i. Stelle} i aus {1,3,5,7,9}

Wenn ich das jetzt für n=5 ansetze heißt das:
|S|=10
|A_1|=|{1,10}|=2
|A_i|=0 für i>1

n_0 = |S| - |A_1| = 10 - 2 = 8

Oder?

Mein Problem ist jetzt. Wie gebe ich die Mächtigkeiten der A_i an, wenn ich das n zwar fest lasse, aber nicht konkret wähle, bzw. n sehr groß wird?

Danke,
Finch

Neue Frage »

Antworten »

Permutationen!

Verwandte Themen