Beweis, das die Anzahl a(n) aller Anordnungen von n verschiedenen Objekten n! ist.

Question

Hallo, ich verstehe diesen Beweis nicht. Kann mir vielleicht jemand helfen?

1. Warum taucht da auf einmal ein i auf, was hat das zu bedeuten?

2. Warum ist in der geschweiften Klammer auf einmal kein j mehr?

3. Und wie genau hängen die beiden Mengen zusammen?

4. Warum ist da nicht Oj geschrieben?

Danke für die Hilfe

Text erkannt:

Definition 1.1. Sei \( n \in \mathbb{N} \). Die Zahl
\( n !:=\prod \limits_{j=1}^{n} j=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n \)
heißt \( n-F a k u l t ä t \). Des Weiteren setzen wir \( 0 !:=1 \).
Satz 1.2 Die Anzahl \( a_{n} \) aller Anordnungen von \( n \) verschiedenen Objekten ist \( n ! \).
Beweis. Wir führen den Beweis durch vollständige Induktion.
Induktionsanfang: Für \( n=1 \) gilt \( a_{1}=1 \) und \( 1 !=1 \), also ist \( a_{1}=1 ! \).
Induktionsschritt:
Induktionsvoraussetzung: Für eine natürliche Zahl \( n \in \mathbb{N} \) gelte \( a_{n}=n ! \) !
Induktionsbehauptung: Es gilt \( a_{n+1}=(n+1) ! \).
Induktionsbeweis: Wir betrachten \( (n+1) \) Objekte \( O_{1}, \ldots, O_{n+1} \). Die möglichen Anordnungen dieser Objekte kann man in \( (n+1) \) Klassen \( K_{j} \) mit \( j \in\{1, \ldots, n+1\} \) unterteilen: \( K_{j} \) sei die Menge derjenigen Anordnungen, in denen \( O_{j} \) als erstes Element steht, das heißt
\( Z_{j} \) sei die Anzahl der Elemente in \( K_{j} \). Folglich ist \( Z_{j} \) gleich der Anzahl der Anordnungen der \( n \) Objekte \( \underbrace{O_{1}, \ldots, O_{j-1}, O_{j+1}, \ldots, O_{n+1}}_{1} \). Nach Induktionsvoraussetzung ist aber die Anzahl der Anordnungen von \( n \) Objekten gleich \( a_{n}=n ! \). Also gilt
\( a_{n+1}=\sum \limits_{j=1}^{n+1} Z_{j}=\sum \limits_{j=1}^{n+1} a_{n}=\sum \limits_{j=1}^{n+1} n !=(n+1) \cdot n !=(n+1) ! \)

Answer 1

Hallo

man weiss ja über n Objekte was rauskommt, deshalb lässt man Oj raus um nur n -Elemente zu haben. das ist über der Klammer geschehen

Gruß lul

Answer 2

Man kan sich das ja auch einfacher vorstellen. Wenn man \( n \) Objekte auf \( n! \) Weisen anordnen kann und es kommt jetzt noch ein Objekt dazu, dann kann man in jeder solcher Anordnung das zuätzliche Element an \( n+1 \) verschiedenen Stellen positionieren. Damit ergebn sich insgesamt \( n! \cdot (n+1) = (n+1)! \) Anordnungen.

Answer 3

Hallo

Kann man sich einfacher vorstellen.

Du hast n Objekte.

Am Anfang kannst du n verschiedene Objekte auswählen. Danach kannst du nur noch (n-1) Objekte auswählen, bis du noch 2 und schliesslich noch 1 Objekt auswählen kannst. Also hast du n * (n-1) * (n-2) … * 1 Möglichkeiten wie du sie anordnen kannst.

Warum man mal rechnet:

Du hast n Objekte. Für jedes n aus {1,2...n} kannst du (n-1) Objekte auswählen weil du schon ein Objekt verbraucht hast. Das heisst auf jedes verschiedene n kannst du (n-1) Objekte hinzufügen und alle Anordnungen sind verschieden.

Beispiel:

{1,2,3,4,5} → Anz. Objekte = 5, also n = 5

Wähle ein Objekt, zum Beispiel Objekt "2":

Du kannst nun (n-1) also 4 Objekte hinzufügen:

{2,1}, {2,3}, {2,4}, {2,5}

Diesen Prozess kannst du für alle Objekte in {1,2,3,4,5} machen.

Also bekommt man 5 * 4 oder n*(n-1) Möglichkeiten die ersten beiden Objekte anzuordnen.

Um ein drittes, ein viertes und ein fünftes Objekt anzuordnen, nimmst du die bereits erhaltenen Anordnungen für 2 Objekte und fügst bei jeder Anordnung 3 also (n-2) Objekte hinzu. Was neu 5*4*3 oder n*(n-1)*(n-2) Anordnungen gibt. Jetzt fügst du bei den neuen Anordnungen noch die verbleibenden 2 Objekte hinzu also bekommst du 5*4*3*2 oder n*(n-1)*(n-2)*(n-3) neue Anordnungen. Jetzt müsstest du noch das letzte Objekt da nur noch eines übrig bleibt anordnen. Aber hier gibt es nur noch eine Möglichkeit dies anzuordnen also musst du noch *1 rechnen.

Also bleiben am Schluss 5*4*3*2*1 Anordnungsmöglichkeiten oder n! Anordnungsmöglichkeiten.

Dies Klappt bei jeder Anzahl an Objekten denn der Weg die Anordnungen zu berechnen ist immer der selbe.