Beweis Permutation < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:13 Fr 26.09.2008 | | Autor: | Giorda_N |
| Aufgabe | Eine Permutation von n Elementen ist eine bijektive Abbildung
[mm] \varepsilon [/mm] : [mm] \{1,....,n \} \to \{1,....,n\}
[/mm]
Die Fixpunkte einer Permutation [mm] \varepsilon [/mm] sind die i, so dass [mm] \varepsilon [/mm] (i) = i. Sei [mm] p_{n} [/mm] (k) die Anzahl der Permutationen mit k Fixpunkten. Zeigen Sie, dass
[mm] \summe_{k=0}^{n} [/mm] k * [mm] p_{n} [/mm] (k) = n! |
Liebe Mathematiker,
da habe ich nicht einmal eine Idee wie das anzugehen.
Kann mir irgendjemand helfen?
Besten Dank
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:10 Fr 26.09.2008 | | Autor: | abakus |
> Eine Permutation von n Elementen ist eine bijektive
> Abbildung
>
> [mm]\varepsilon[/mm] : [mm]\{1,....,n \} \to \{1,....,n\}[/mm]
>
> Die Fixpunkte einer Permutation [mm]\varepsilon[/mm] sind die i, so
> dass [mm]\varepsilon[/mm] (i) = i. Sei [mm]p_{n}[/mm] (k) die Anzahl der
> Permutationen mit k Fixpunkten. Zeigen Sie, dass
>
> [mm]\summe_{k=0}^{n}[/mm] k * [mm]p_{n}[/mm] (k) = n!
> Liebe Mathematiker,
>
> da habe ich nicht einmal eine Idee wie das anzugehen.
>
> Kann mir irgendjemand helfen?
Das kommt auf deine Vorkenntnisse an.
Was sagt dir der Begriff "Permutation" im Zusammenhang mit dem Mathematikunterricht deiner Schulzeit? Welche Anzahl von Möglichkeiten wurde mit n! ausgerechnet?
Gruß Abakus
>
> Besten Dank
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
Tja, hier ist jemand auf eine ähnliche Idee gekommen wie ich ^^ Man sieht sich am Montag ;)
Interessant wäre eigentlich, die Funktion pn(k) ausfindig zu machen. Dann wäre der Rest nur noch eine Frage der vollständigen Induktion. Ich habe jedoch bislang noch keine entsprechende Formel gefunden.
|
|
|
| |
|
pssssst, überleg mal wer ich sein könnte, kennst mich besser als du denkst ;)
Natürlich ists eine tolle Sache, darum nutze ich sie auch. Mit vollständiger Induktion kann mans glaube ich effektiv nicht lösen, denn dazu müsstest du wissen was die Funktion pn(k) ist, und die konnte ich bislang nicht finden. Erst dann könnte man eine vollständige Induktion durchführen, wenn ich mich da nicht irre. Ich bin da auch noch dran.... Aber natürlich sage ichs dir, wenn ich mehr weiss ;)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:56 So 28.09.2008 | | Autor: | Giorda_N |
mhm habe wirklich keine ahnung....kleiner tipp???
in welcher übungsgruppe bist du?
ich bin am DO nachmittag bei michael bächtold und er hat uns gesagt, dass es eigentlich viel zu schwierig sei mit voll. induktion! d.h. er meinte wir sollen es anderst lösen....aber wie gesagt die frage ist wie....
ich hab mir folgendes überlegt:
ein beispiel: M = (1,2,3) mit n=3
es gibt 6 Permutation (k = anzahl fixpunkte), d.h.
1,2,3 k= 3
1,3,2 k= 1
2,1,3 k= 1
2,3,1 k= 0
3,1,2 k= 0
3,2,1 k= 1
also wir haben k = anzahl fixpunkte ; [mm] p_{n} [/mm] (k) = Anzahl Permutationen mit k Fixpunkten und k [mm] p_{n} [/mm] (k) = Anzahl aller Fixpunkte von allen Permutationen
Also:
[mm] \summe_{k=0}^{3} [/mm] k [mm] p_{3} [/mm] (k) = 0*2 + 1*3 + 3*1 = 6 = 3!
also n!
aber ob das zählt? hab es mal so auf mein blatt geschrieben!
grüessli
ps. verstehst du 4a) ?
|
|
|
| |
|
Jo, genau das ist auch meine bisherige Antwort :D Weiter bin ich auch noch nicht gekommen, also haben wir uns entschlossen einfach die Variante mit 3! zu zeigen (4 wäre ja schon etwas zu aufwändig und zeigt nicht mehr). Die Frage ist nun ob dies so schon zählt.... Also zumindest ist es ja "sinnvoll" bearbeitet, wo wie man es verlangt hat. Denn mit diesem Vorgehen hat man zumindest den Vorgang begriffen. Ich glaube kaum, dass irgend jemand anderes mehr hat bislang.
Zu Aufgabe 4 habe ich bislang ganz allgemein keine Ahnung. Auch zu Aufgabe a) nicht. Da bin ich gerade noch dran....
Doch, du kennst mich.... Hab dich sogar zum MSN geaddet ;)
|
|
|
| |
|
die anzahl der permutationen von n elementen mit genau k fixpunkten
ist die anzahl der moeglichkeiten k aus n elementen auszuwaehlen (die fixpunkte) bekanntlich n ueber k, n! /(k!(n-k)!) mal der anzahl der permutationen von n-k elementen ohne (!) fixpunkt, also [mm] p_{n-k}(0).
[/mm]
[mm] p_{n-k}(0) [/mm] kann man leicht rekursiv bestimmen. wenn man eine beliebige permutation ohne fixpunkt von n-k-1 elementen hat, so kann man das (n-k)-te element mit jedem anderen vertauschen und erhaelt wieder eine permutation ohne fixpunkt. also ist [mm] p_2(0) [/mm] = 1 (anfangswert) und [mm] p_{n-k}(0) [/mm] = (n-k-1) [mm] p_{n-k-1}(0)
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:42 Di 30.09.2008 | | Autor: | mathpfeife |
|
|
|
|
....Bis morgen, wer auch immer Du bist 