P(n+1,r)=P(n,r)(n+1)/(n+1-r) - kombinatorischer Beweis

01.05.2009, 11:53	Michael007	Auf diesen Beitrag antworten »
P(n+1,r)=P(n,r)(n+1)/(n+1-r) - kombinatorischer Beweis Hallo zusammen! Wir müssen einen kombinatorischen Beweis für die folgende Gleichung finden: $\begin{eqnarray} P(n+1,r) = \frac{P(n,r)(n+1)}{(n+1-r)} \end{eqnarray}$ Ich habe mir nun folgende Überlegungen gemacht: P(n+1,r) heisst ja, dass ich aus einer Menge mit n+1 verschiedenenen Elementen r Elemente (mit Beachtung der Reihenfolge und ohne Wiederholung) auswähle und P(n+1,r) ist dann die Anzahl der verschiedenen Möglichkeiten die ich habe dies zu tun! Um das gleiche Ziel zu erreichen (also die Anzahl der verschiedenen Möglichkeiten, aus den n+1 Elementen eine Teilmenge von r Elementen zu wählen, zu ermitteln) kann ich nun n-elementige Teilmengen bilden indem ich genau 1 Element weglasse. Weil nun n+1 Elemente vorhanden sind, kann ich (n+1) verschiedene n-elementige Teilmengen bilden. Aus diesen (n+1)-elementigen Teilmengen kann ich dann jeweils P(n,r) Elemente wählen, darum (n+1)P(n,r). Leider geht es bei mir irgendwie nicht auf, aber ich sehe den Fehler einfach nicht, kann mir jemand auf die Sprünge helfen? Vielen Dank!
01.05.2009, 22:13	frank09	Auf diesen Beitrag antworten »
Der Ansatz ist schon ganz gut. Statt z.B. 2(=r) aus 6(=n+1) zu ziehen, könnte ich 6 Teilmengen mit je 5 Elem. erstellen, bei denen jeweils ein Element fehlt. Dann würde ich erst eine Teilmenge auswählen, und aus der dann 2 ziehen. In diesem Fall hätte ich $\begin{eqnarray} P(n,r)(n+1) = P(5,2)6 \end{eqnarray}$ Möglichkeiten. Das wären aber zuviel, weil ich nicht eine bestimmte Teilgruppe auswählen muss, um die entsprechenden 2 Elem. zu ziehen, sondern gleich die Wahl aus 4 hätte. Nämlich alle, in denen weder das erste zu ziehende noch das zweite zu ziehende Elem fehlt. Das wären 6-2 (=n+1-r) =4 "erlaubte" Teilmengen. Demnach muss ich $\begin{eqnarray} P(n,r)(n+1) \end{eqnarray}$ noch durch $\begin{eqnarray} (n+1-r) \end{eqnarray*}$ teilen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »