Rekurrenzformel für k-Partition der natürlichen Zahl n

13.04.2019, 14:55	MaPalui	Auf diesen Beitrag antworten »
Rekurrenzformel für k-Partition der natürlichen Zahl n Hallo Leute, ich beschäftige mich nach wie vor mit Diskreter Mathematik und habe gerade dieses vor mir: [attach]49117[/attach] Das wollte ich über vollständige Induktion über k machen. Der erste Teil ist trivial, denn $\begin{eqnarray} n = n = 1 + 1 + \dots +1 \Rightarrow P_{n,1}=P_{n,n}=1 \end{eqnarray}$ Zu zeigen ist also: $\begin{eqnarray} P_{n,k} = \sum\limits_{i=1}^{k}P_{n-k,i} \end{eqnarray}$ IA) k=1: $\begin{eqnarray} P_{n,1} = \sum\limits_{i=1}^{1}P_{n-1,1} = P_{n-1,1} = 1 \end{eqnarray}$ IS) k->k+1: $\begin{eqnarray} P_{n,k+1} = \sum\limits_{i=1}^{k+1}P_{n-k-1,i} = \sum\limits_{i=1}^{k}P_{n-k-1,i}+P_{n-k-1,k+1} \end{eqnarray}$ Aber jetzt weiß ich nicht mehr weiter. Habe ich vielleicht schon den falschen Weg eingeschlagen? Ich müsste ja die (IV) noch benutzen, aber ich sehe es gerade nicht
13.04.2019, 18:20	HAL 9000	Auf diesen Beitrag antworten »
Ich wüsste eigentlich gar nicht, wieso man hier Vollständige Induktion brauchen sollte: Wir wollen im Fall $\begin{eqnarray} n>k \end{eqnarray}$ die Anzahl der $\begin{eqnarray} k \end{eqnarray}$ -Tupel zählen mit Summe $\begin{eqnarray} n \end{eqnarray}$ . Diese Tupel teilen wir in Fälle nach der Anzahl $\begin{eqnarray} j \end{eqnarray}$ Summanden in dieser Summe, die größer als 1 sind, d.h., es sei $\begin{eqnarray} n_1\geq n_2\geq \ldots n_j\geq 2 > n_{j+1}=\ldots=n_k = 1 \end{eqnarray}$ . Für festes $\begin{eqnarray} j \end{eqnarray}$ ist deren Anzahl wegen $\begin{eqnarray} (n_1-1)+(n_2-1)+\ldots+(n_j-1) = n-k \end{eqnarray}$ gleich $\begin{eqnarray} P_{n-k,j} \end{eqnarray}$ . Nun kann $\begin{eqnarray} j \end{eqnarray}$ die Werte $\begin{eqnarray} 1,\ldots,k \end{eqnarray}$ annehmen, daher ist $\begin{eqnarray} P_{n,k} = \sum_{j=1}^k P_{n-k,j} \end{eqnarray}$ .
14.04.2019, 09:57	MaPalui	Auf diesen Beitrag antworten »
Hallo HAL 9000 und wieder mal Danke für deine Antwort Diese kann ich auch nachvollziehen und verstehe sie auch. Diesen Ansatz hätte ich selber nicht erkannt. Von daher sehr gut dass ich ihn kenne. Ist es denn trotzdem mit induktion überhaupt möglich? Ich frage mich nämlich ob es Aussagen in den natürlichen Zahlen gibt, die man nicht damit beweisen kann?
14.04.2019, 10:23	HAL 9000	Auf diesen Beitrag antworten »
Derartige Rekursionsformeln sind etwas, was man vielleicht in einem Induktionsschritt eines Induktionsbeweises (z.B. für eine explite Darstellung) brauchen könnte. Aber diese Rekursionsformel selbst braucht doch zu ihrer Begründung keinen Rückgriff auf dieselbe Rekursionsformel für $\begin{eqnarray} n-1 \end{eqnarray}$ oder kleiner, insofern ist Induktion unnötig.
14.04.2019, 10:38	MaPalui	Auf diesen Beitrag antworten »
Ok, wieder was gelernt. Vielen Dank

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »