Anzahl Involutionen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:31 Di 07.06.2005 | | Autor: | MrPink |
Hallo, ich habe hier den Beweiss für die Rekusrsionformel die die Anzahl der Involutionen auf n Elementen berechnet. Die Formel lautet
I(n) = I(n -1) + (n -1)*I(n -2); n >=3 und I(1) = 1; I(2) = 2:
Ich verstehe nur den Teil des Beweises mit der Bijektion nicht.
Kann mir das jemand erklären, oder habt ihr den Beweiss vielleicht noch mal in ausführlich.
Hier ist der Beweiss:
Permutation auf 1 Element -> id einzige Involution. Bei 2 Elementen gibt es id sowie
den 2er Zykel.
Involutionen auf n Elementen teilen sich auf in Involutionen mit 1 in einem 1-Zykel (A)
und in Involutionen mit 1 in einem 2-Zykel (B). Bijektion der 1-Zykel auf Involutionen
auf n - 1 Elementen: (1) weglassen/hinzufÄugen -> Involution! Also gibt es I(n - 1) Involutionen der Sorte A. Sei x Element {2,...,n} das Element mit Zykel (1, x). Dann gibt
es fÄur jedes fesgehaltene x eine Bijektion auf Involutionen auf n - 2 Elementen
((1, x) weglassen/hinzufügen ) Involution!). Fü das x gibt es n -1
Mölichkeiten. Also gibt
es (n -1) *I(n -2) Involutionen der Sorte B. Addition aller Mölichkeiten ergibt die
Rekursionsformel.
|
|
| |
|
Hallo!
Naja, Bijektionen kommen ja in beiden Beweisteilen vor...
Also, wir nehmen an, dass $n [mm] \geq [/mm] 3$ ist und wir möchten die Anzahl der Involutionen in der Permutationsgruppe bestimmen.
Sei dazu also [mm] $\alpha \in S_n$ [/mm] eine Involution, also [mm] $\alpha \circ \alpha [/mm] = [mm] \id$.
[/mm]
Nun machen wir eine Fallunterscheidung:
Fall 1: [mm] $\alpha(1) [/mm] = 1$. Dann kann ich [mm] $\alpha$ [/mm] auf die Menge [mm] $\{2, \ldots, n\}$ [/mm] einschränken (die wird ja in sich abgebildet!) und die Einschränkung ist dort wieder eine Involution. Für diese gibt es $I(n-1)$ Möglichkeiten.
Fall 2: [mm] $\alpha(1) [/mm] = x [mm] \not= [/mm] 1$. Dann muss [mm] $\alpha(x) [/mm] = 1$ sein, da [mm] $\alpha \circ \alpha(1) [/mm] = 1$ gelten muss. Für das $x$ gibt es schon mal $n - 1$ Möglichkeiten. Und wieder wird die Menge [mm] $\{2, \ldots, n\} \backslash \{x \}$ [/mm] in sich abgebildet, also ist die Einschränkung von [mm] $\alpha$ [/mm] auf diese Menge eine Involution - dafür gibt es $I(n - 2)$ Möglichkeiten.
Insgesamt ergibt sich die gewünschte Formel: das $I(n-1)$ aus Fall 1 und für jede der $(n-1)$ Möglichkeiten für $x$ nochmal $I(n-2)$, also zusammen
$I(n) = I(n-1) + (n-1) [mm] \cdot [/mm] I(n-2)$
Alles klar? 
Lars
|
|
|
|
