Permutation und Fixpunkt

28.09.2008, 01:41

Ferdinand

Permutation und Fixpunkt

Servus an alle...

Folgende Aufgabe beschäftigt mich nun seit über einer Woche, und ich komme nicht weiter...
ich wäre froh, wenn sich das vielleicht mal jemand anschauen und lösen könnte..

Die Aufgabe lautet folgendermassen:
Eine Permutation von n Elementen ist eine bijektive Abbildung.
Die Fixpunkte einer Permutation Q sind die i, so dass Q(i) = i. Sei pn(k) die Anzahl der Permutationen mit genau k Fixpunkten. Zeigen Sie, dass $\begin{eqnarray*} \sum_{k=0}^n~k *pn(k) = n! \end{eqnarray*}$

Ich habe schon verschiedenes probiert und wie gesagt, bin schon seit über einer Woche daran...wo ich sicher bin und was ich sicher schon mal beitragen kann ist:

Die Fixpunkte von Q sind die i $\begin{eqnarray*} \in \end{eqnarray*}$ {1, 2, ..., n} so dass Q(n)=i.

Wie gesagt, viel ist es nicht, was ich da schon habe, darum wäre ich überüberglücklich, wenn mir jemand helfen könnte!
Vielen Dank!

28.09.2008, 09:36

Auf diesen Beitrag antworten »

Versuch's mal mit dem Prinzip des doppelten Abzählens, angewandt auf die Menge

$\begin{eqnarray*} \Big\{ (Q,i) \Bigm| i \;\mbox{ist Fixpunkt von Permutation}\; Q \Big\} \end{eqnarray*}$ .

28.09.2008, 15:55

Rebecca

Auf diesen Beitrag antworten »

oke, vielen Dank!
Ich habe jetzt den Induktionsanfang und die -Voraussetzung, komme aber nachher nicht zum Schluss...
folgendes habe ich:

Q: {1, 2, ...n} --> {Q(1); Q(2); ... Q(n)}

Q(1) --> n Möglichkeiten
Q(2) --> (n-1) Mögl.
Q(n) --> 1 Mögl.

alle zusammen ergäbe dann n! Möglichkeiten

P(n) : Es gibt n! Permutationen von n Elementen

IA: P(1) +(1) --> (1) wahr
P(n) --> P(n+1) : Sei M eine Menge von (n+1) Elementen
Sei x Element von M.

IV: M \ {x} hat n! Permutationen.

..richtig bis jetzt, oder? ..wie komme ich nun zum endgültigen Beweis?
Vielen Dank im Voraus!

28.09.2008, 16:19

Auf diesen Beitrag antworten »

Zitat:

Original von Rebecca
P(n) : Es gibt n! Permutationen von n Elementen

Das ist ja schön, dass du das beweisen willst - nur ist das nicht die Aufgabe hier.

Ich hab ja oben schon einen Tipp gegeben "Abzählen der geordneten Paare (Permutaion,Fixpunktposition)", ich wiederhole ihn hiermit.

28.09.2008, 17:10

Rebecca

Auf diesen Beitrag antworten »

ja, aber wie mache ich das :-S
also kannst du mir ein Beispiel geben?

28.09.2008, 17:28

Auf diesen Beitrag antworten »

Also nochmal ausführlicher:

$\begin{eqnarray*} S_n \end{eqnarray*}$ kennzeichne wie üblich die Symmetrische Gruppe aller Permutationen von $\begin{eqnarray*} 1,\ldots,n \end{eqnarray*}$ .

Dann wird

$\begin{eqnarray*} M := \Big\{ (Q,i) \Bigm| Q\in S_n,\,i=1,\ldots,n \;\mbox{mit}\; Q(i)=i \Big\} \end{eqnarray*}$

doppelt abgezählt: Einmal

(1) bei festem $\begin{eqnarray*} i \end{eqnarray*}$ :

$\begin{eqnarray*} |M| = \sum_{i=1}^n \left| \Big\{ (Q,i) \Bigm| Q\in S_n\;\mbox{mit}\; Q(i)=i \Big\} \right| \end{eqnarray*}$

und das andere mal

(2) bei festem $\begin{eqnarray*} Q \end{eqnarray*}$ :

$\begin{eqnarray*} |M| = \sum_{Q\in S_n} \left| \Big\{ (Q,i) \Bigm| i=1,\ldots,n\;\mbox{mit}\; Q(i)=i \Big\} \right| \end{eqnarray*}$

(1) ergibt $\begin{eqnarray*} |M| = n\cdot (n-1)! = n! \end{eqnarray*}$ , und (2) nach entsprechender Überlegung $\begin{eqnarray*} |M| = \sum_{k=0}^n k\cdot p_n(k) \end{eqnarray*}$ .

Das sind jetzt 90% der Lösung, die restlichen 10% machst du bitte selbst.

28.09.2008, 17:58

Rebecca

Auf diesen Beitrag antworten »

Wow super!
Vielen vielen Dank!

Neue Frage »

Antworten »

Permutation und Fixpunkt

Verwandte Themen