Zahlpartitionen

23.02.2012, 18:27	keks89	Auf diesen Beitrag antworten »
Zahlpartitionen Meine Frage: Hallo zusammen, ich soll folgendes zeigen: Sei p(n,k) die Anzahl der Partitionen von n mit genau k Summanden, dann gilt: p(n,k) = p(n-1,k-1) + p(n-k,k), wobei p(n,n) = 1, p(n,1) = 1, p(n,k) = 0 (k>n). Meine Ideen: Bisher versuchte Lösungsansätze sind: - Induktion über n (schwierig, wegen dem k) - Logische Überlegungen wie: "Zunächst ist p(n,k) gleich p(n-1,k-1), wenn der (neu dazugekommene) n-te Summand einzeln steht..." Hoffe jemand hat eine Idee oder Lösung... Vielen Dank schonmal für Antworten!
24.02.2012, 12:59	Huggy	Auf diesen Beitrag antworten »
RE: Zahlpartitionen Die Menge $\begin{eqnarray} P \end{eqnarray}$ der Partitionen von n in genau k Summanden lässt sich aufteilen in 2 disjunkte Mengen $\begin{eqnarray} P_1 \end{eqnarray}$ und $\begin{eqnarray} P_2 \end{eqnarray}$ . $\begin{eqnarray} P_1 \end{eqnarray}$ enthalte die Partitionen, bei denen mindestens ein Summand = 1 ist. $\begin{eqnarray} P_2 \end{eqnarray}$ enthalte die Partitionen, bei denen kein Summand = 1 ist. Die Menge $\begin{eqnarray} P_1 \end{eqnarray}$ lässt sich bijektiv auf die Partitionen von n - 1 mit genau k - 1 Summanden abbilden, indem man aus jeder Partition einen der Summanden 1 entfernt. Die Menge $\begin{eqnarray} P_2 \end{eqnarray}$ lässt sich bijektiv auf die Partitionen von n - k mit genau k Summnaden abbilden, indem man jeden Summanden einer Partition um 1 vermindert. Daraus folgt die Behauptung.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »