Beweisführung zu Anordnungen < Sonstiges < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:30 Do 18.12.2008 | | Autor: | ZodiacXP |
| Aufgabe | Die Anzahl aller möglichen Anordnungen einer n-elementigen Menge [mm] \{ A_1, A_2, \ldots, A_{n+1} \} [/mm] ist gleich n!
Beweis durch Induktion! |
I-Anfang -> einelementige Menge (trivial)
Ich verstehe aber folgendes nicht:
Die möglichen Anordnungen der (n+1)-elementigen Menge zerfallen folgendermaßen in n+1 Klassen [mm] C_k, [/mm] k = 1, [mm] \ldots, [/mm] n+1 : Die Anordnungen der Klasse [mm] C_k [/mm] haben das Element [mm] A_k [/mm] an erster Stelle, bei beliebiger Anordnung der übrigen n Elemente. Nach I-Voraussetzung besteht jede Klasse aus n! Anordnungen. Die Gesamtzahl ist hier also gleich (n+1)n! = (n+1)!
Das es n! Anordnungen gibt glaube ich! Mit Fakultäten an sich kenne ich mich auch aus. Aber die Beweisführung verstehe ich nicht. Wer kann es mir erklären, was das heißen soll?
|
|
| |
|
Hallo ZodiacXP,
Ich zeig dir jetzt einfach mal praktisch, was da steht:
Um es zu vereinfachen, schreibe ich anstatt [mm] a_{1}...a_{n} [/mm] nur die Indizes, das Ergebnis ist das gleiche:
(1,2,3...,n) hat nach nach Voraussetztung n! (=n*(n-1)*...*2*1) Möglichkeiten diese Zeichen anzuordnen (bzw. Permutaionen dieser n Zahlen).
Jetzt nehmen wir uns noch ein Element (=n+1) hinzu, und schaunen wie viele Permutationen nun möglich sind.
[mm] ((n+1),1,2,3,...,n)\
[/mm]
[mm] (1,(n+1),2,3,...,n)\
[/mm]
[mm] (1,2,(n+1),3,...,n)\
[/mm]
[mm] (1,2,3,(n+1),...,n)\
[/mm]
...
[mm] (1,2,3...,(n+1),n)\
[/mm]
[mm] (1,2,3...,n,(n+1))\
[/mm]
Wie man sieht gibt es n+1 solche Zeilen, von denen [mm] \underline{jede} [/mm] Zeile nach Voraussetzung n! mögliche Anordnungen der Elemente 1 bis n zulässt (ohne das (n+1)-te Element zu verschieben). Es sind nicht n sondern (n+1), da ja auch nach dem n-ten Element das (n+1)-te plaziert werden kann.
Ich habe diesen Sachverhalt genau so bewiesen, und es war ok so.
lg Kai
|
|
|
|
