Permutationen! |
03.01.2010, 13:57 | Mäuschen1985 | Auf diesen Beitrag antworten » | ||
Permutationen! 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 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. 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! |
||||
Anzeige | ||||
|
||||
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: Beispiel: n=2 gibt 14. (Und für grosse n scheint die Zahl mit (2n)! ein Verhältnis zu bilden, das gegen strebt. Der Beweis müsste mit der Taylorreihe der Exp-Funktion gehen.) |
||||
03.01.2010, 18:27 | AD | Auf diesen Beitrag antworten » | ||
In der Tat. Das bringt mich auf eine interessante Verallgemeinerung: Betrachtet man den Anteil derjenigen Permutationen von , die an vorher festgelegten Positionen keine Fixpunkte aufweisen, wobei für ein gelten möge, dann gilt . P.S.: Die Formulierung dieser Aussage, sowie deren Analyse durch den geneigten Leser dauert fast genauso lange wie der Beweis dieser Aussage. |
||||
04.01.2010, 10:04 | Lapalie | Auf diesen Beitrag antworten » | ||
Was ist denn nun die Antwort hier? |
||||
04.01.2010, 10:22 | AD | Auf diesen Beitrag antworten » | ||
Wenn du mal aufmerksam lesen würdest, dann müsstest du diese Frage nicht stellen:
|
||||
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 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |