Frage von Naydoult, 58

Fakultät n! für n Objekte Beweis?

Ich habe mich mit dem Thema noch nicht wirklich beschäftigt und wollte diese Gelegenheit einfach mal nutzen. Mir war/ist allerdings schon bekannt das die Möglichkeit n Objekte zu sortieren n! ist. Das habe ich jedoch nie intuitiv wie scheinbar andere verstanden, wieso weiß ich nicht, zu blöd? Also wollte ich mir das mal selbst logisch herleiten.

Definition/en:

n´m:= Möglichkeiten n Objekte auf n Plätze zu verteilen

n:= Anzahl der Objekte

Intuitive Äußerung: n´m = n´m+(n´m-1)+(n´m-2)+...1

Begründung: Da wenn ich n´m Plätze und Objekte habe, ich dass erste platziere ich dafür n´m Möglichkeiten habe. Dann für das nächst kleinere nur noch n´m-1. Das summiert sich dann schließlich auf.

Bei einem Beispiel stellt sich diese als falsch heraus. Da ich es verschiedene Möglichkeiten gibt für alle n´m-k (k > 0).

Mit Beispielen leitet man sich schließlich die Formel: n*(n-1´m) her.

Die ist bisher aber nicht bewiesen, wie sollte das denn auch gehen?

Schaut man sich die Folge einmal an, so schließt man auf:

n´m = (n´m-1)*(n´m-2)·...·1

Was ja gerade der Definiton von n! entspricht.

Nun stellt sich mir die Frage, wie man das ganze beweist? Oder kann man dies einfach als Axiom verstehen? Also gegeben ohne weitere Begründung.

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von Numberfocus, 3

Nach Deinen Schreiben denke ich das Du einen kleinen Denkfehler hast. Das was Du dazu addieren willst ist überflüssig, da Du lediglich zeigen willst was die Möglichkeiten n aus n zu ziehen sind.

Wie viele Möglichkeiten existieren genau n Objekte anzuordnen?

Antwort: n!

Wie Du richtig hergeleitet hast, ist n! durch n·(n-1)! definiert.

Aber, (n-1)! = (n-1)·(n-2)! und (n-2)! = (n-2)·(n-3)! u.s.w.

Das ganze geht bis 1, also bis (n-k)·1! kommt. Wobei 1! = 1 ist.

=> n! = (n-1)·(n-2)·...·1

Dann existiert noch die eigentlich übliche Begründung.

Du hast n Objekte, die Du in n Plätze anordnen willst.

Beispielsweise sei n = 4

{( ), ( ), ( ), ( )} für a, b, c, d

Wir wollen alle n-elementigen Teilmengen aus der n-elementigen Menge (B) finden, unter Beachtung der Reihenfolge.

B = {a, b, c, d}

1.) Für den ersten Platz sind 4 Möglichkeiten da.

A\{a} ∨ A\{b} ∨ A\{c} ∨ A\{d}

Entspricht dem Fall alle 1-elementigen Teilmengen aus der Menge B zu finden.

2.) Für den zweiten beliebigen Platz bleiben 4·3 Möglichkeiten.

A\{a, b} ∨ A\{a, c} ∨ A\{a, d} ∨ A\{b, c} ∨ A\{b, d}∨ A\{b, a} ∨ A\{c, d} ∨ A\{c, a} ∨ A\{c, b} ∨ A\{d, a} ∨ A\{d, b} ∨ A\{d, c}

Würde das erste mit dran addiert werden, schließe dies sozusagen Fälle wie {(a), (a), ( ),( )} ein. Dies wäre zwar dann wieder {(a), ( ), ( ), ( )}, bloß letztendlich rechnerisch überflüssig/falsch.

Entspricht dem Fall alle 2-elementigen Teilmengen aus der Menge B zu finden.

Stelle Dir das einfach sowie oben bei der Fakultät im allgemeinen vor.

Du multiplizierst 4 und 3, da Du am Anfang 4 Möglichkeiten hast, welches Dein erstes Element ist. Ins Gesamt sind nur 2 Plätze da, bei den letzten können dann also nur die anderen 3 sein.

3.) Für den dritten Platz gibt es 4·3·2 Möglichkeiten.

Entspricht dem Fall alle 3-elementigen Teilmengen aus der Menge B zu finden.

Jetzt diesen Gedankengang weiter verfolgen.

Du multiplizierst 4, 3 und 2, da Du am Anfang 4 Möglichkeiten hast, was Dein 1 Element ist. Dann 3 welches Dein zweites ist und zunächst 2 was Dein vorletztes ist.

4.) Für den letzten beliebigen Platz existieren 4·3·2·1 Möglichkeiten.

Entspricht dem Fall alle 4-elementigen Teilmengen aus der Menge B zu finden.

Du multiplizierst 4, 3, 2 und 1, die ersten 3 Faktoren lass ich jetzt mal weg.

Dasselbe wie gerade eben, nur das wir noch ein einziges Element übrig haben werden. Das spielt bloß keinerlei Rolle, wir brauchen ja die Möglichkeiten zu ordnen.

Das wären also insgesamt 24 Möglichkeiten zu sortieren.

Antwort
von varlog, 37

n´m:= Möglichkeiten n Objekte auf n Plätze zu verteilen

Wozu dann das m? Wenn das der Binomialkoeffizient sein soll sind es die Möglichkeiten m Objekte auf n Plätze zu verteilen (Reihenfolge egal)

Intuitive Äußerung: n´m = n´m+(n´m-1)+(n´m-2)+...1

Die Intuition verstehe ich nicht ganz, denn auf beiden Seiten hast du n'm, dass heißt damit das erfüllt wäre müssten irgendwelche deiner Summanden negativ sein. Da es sich um Möglichkeiten handeln soll geht das allerdings schlecht.

Ich glaube dein fundamentaler Denkfehler ist, dass n! nicht definiert ist als

n´m = (n´m-1)*(n´m-2)·...·1

Sonder als 0!=1 und n!=n*(n-1)!. Also z.B: 5!=5*4*3*2*1.

5! Sagt dir daher auf wie viel verschiedene Arten du 5 Objekte anordnen kannst. Stell dir vor du hast 5 Bücher im Regal und nimmst alle raus. Dann greifst du dir immer eins und stellst so nacheinander alle wieder zurück ins Regal. Beim ersten Buch hast du 5 Möglichkeiten, welches du dir greifst. Jetzt sind nur noch 4 Bücher nicht im Regal. Das heißt für das zweite Buch hast du nur 4 Möglichkeiten, für das dritte nur noch 3... Daher 5*4*3*2*1=5!.

Kommentar von Naydoult ,

Achso, dann ist meine Herleitung schon korrekt. Ich verstehe nicht ganz, wie Du im letzten Abschnitt äußerst weshalb die Möglichkeiten mit einander multipliziert werden, dass wollte ich verstehen. Intuitiv würde ich nämlich sagen, dass sie sich addieren. Denn am Anfang 5 Bücher, gibt 5 Möglichkeiten, ich platziere 1 und dann für das andere Buch 4 Möglichkeiten. Weshalb Multiplikation und nicht Addition? Noch nie dazu eine Begründung gelesen.

Kommentar von varlog ,

Male dir dazu mal einen Baum auf(vielleicht nicht für 5 Objekte, denn dann wärst du erst mal eine Weile beschäftigt^^).

Sagen wir für drei Objekte. Du startest an der Wurzel. Von der Wurzel gehen drei Verzweigungen ab, denn du hast drei Möglichkeiten ein Buch auszuwählen. Jetzt hast du aber drei Teilbäume, die du isoliert voneinander betrachten musst. Da jeder Teilbaum aber die gleiche Anzahl Blätter haben wird, kannst du auch einfach sagen es ist 3 mal dieser Teilbaum.

Das heißt wenn die Funktion f uns die Anzahl der Blätter(ein Blatt = eine Mögliche Konstellation der Bücher) eines Baumes gibt, kann man das rekursiv definieren. f(Baum)=Anzahl(Objekte)*f(Teilbaum).

Diese Teilbäume existieren wie gesagt dreimal, daher f(Baum)=3*f(Teilbaum)

Der Teilbaum splittet sich dann wieder in Teilbäume usw usf.

Mal dir das am besten mal auf dann wird es klarer.

Kommentar von Naydoult ,

Danke schon einmal. Lag daran weil ich mich beim Denken immer nur auf eines konzentriert hatte, und nicht das große ganze blickte. Beim Baumdiagramm verwirrt mich jetzt nur noch eines. Ich habe am Anfang also drei Bücher. Beim ersten Buch bleiben mir drei Möglichkeiten. Sobald ich es irgendwo platziert habe, bleiben mir noch jeweils 2. Dann aber noch jeweils "jeweils" 1 Möglichkeit. Heißt die eine Möglichkeit muss dann eigentlich noch mit drauf addiert werden, was dann bei 3, 6 im Überfluss bedeutet. Wie ist das dann rechnerisch zu vereinbaren?

Kommentar von varlog ,

Verstehe ich jetzt nicht so ganz. Auf jeden Fall addieren wir hier ja sowieso nichts und wenn du mit 1 multiplizierst verändert sich ja nichts.

Der Baum gliedert sich ja in drei Ebenen (hier meine ich nicht Teilbäume, sondern Ebenen von oben nach unten). Von der Wurzel gehen 3 Teilbäume ab, auf die 1.Ebene. Auf der 1. Ebene teilen sich die drei Teilbäume in jeweils 2 Teilbäume auf die 2. Ebene, sodass wir auf Ebene zwei 3*2 = 6 Teilbäume haben. Auf der letzten Ebene bekommt jeder Teilbaum nur noch einen weiteren Aus auf die dritte Ebene, also *1.

In unseren Buchbeispiel wäre das dann das letzte Buch. Beim letzten Buch hast du keine Entscheidungsmöglichkeiten mehr, daher gibt es bei Knotenpunkten auf Ebene 2 keine weiteren Pfade.

Kommentar von Naydoult ,

Ich meine das folgender maßen:

Das was Du geschrieben hast verstehe ich mit den Ebenen schon.

Also man kann ja auch ganz hinten/vorne anfangen. Sozusagen 1!. Ich habe also 1 Platz und 1 Stein, wie viele Möglichkeiten gibt es den Stein zu platzieren? Genau 1.

Irgendwann kommt es nun mal vor, dass ich noch 1 Objekt übrig habe. Außerdem kann ich ja auch einfach die ganzen "Teilbäume" addieren, will ja schließlich die Menge aller Möglichkeiten. Beispielsweise klappt das auch mit 3, mit 4 ebenfalls. Sobald man jedoch die 1er immer mit raufpackt, sind diese auf einmal überflüssig.

Kommentar von varlog ,

Ja, die Teilbäume kannst du addieren, da jeder Teilbaum aber genau gleich viele Blätter haben wird kannst du auch einfach die Anzahl der Teilbäume pro Ebene mit der Anzahl der Blätter eines Teilbaums multiplizieren.

Wenn du den Baum fertig gezeichnet hast repräsentiert ein Blatt eine Möglichkeit deine Bücher anzuordnen. D.h. die Anzahl der Blätter = die Anzahl der Möglichkeiten. Das Ding ist, dass die 1er die Anzahl der Blätter nicht vergrößern, sondern nur die Tiefe des Baumes. Dadurch, dass du an einen Blattknoten noch einen Zweig dran zeichnest, ist der ursprüngliche Blattknoten kein Blattknoten mehr, dafür kommt aber ein neuer hinzu also +1-1.

Mit anderen Worten bei so einem Baum kannst du so viele 1er an Blattknoten zeichnen wie du willst. Das ändert nichts an der Anzahl der Blattknoten.

Ich denke bei dir hat sich diese Intuition, dass du was addieren willst irgendwie etwas festgesetzt. Ich weiß ehrlich gesagt nicht wie ich das noch weiter ausführen soll. Sorry.

Rechne vielleicht ein paar Beispiele durch. Zeichne dir noch ein paar Bäume auf. Mehr Tipps habe ich sonst auch nicht.

---------------------------------------

Etwas ins blaue geraten, aber vielleicht hilft folgendes noch:

5!+4!+3!+2!+1!=153 wäre die Anzahl der Möglichkeiten 5,4,3,2 oder 1 Objekte unter Beachtung der Reihenfolge anzuordnen während

5!=120 die Anzahl der Möglichkeiten ist genau 5 Objekte unter Beachtung der Reihenfolge anzuordnen.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten