Anzahl der Partitionen für eine Menge mit n Elementen berechnen

05.11.2017, 19:06	Steffi92	Auf diesen Beitrag antworten »
Anzahl der Partitionen für eine Menge mit n Elementen berechnen Meine Frage: Die Aufgabe lautet berechnen Sie die Anzahl aller Partitionen für eine 5-elementige Menge. Die Aufgabe baut auf der Lösung(siehe Anhang) dieser(unten) Aufgabe auf. Geben Sie eine induktive Definition für die Anzahl der Partitionen einer n-elementigen Menge mit genau $\begin{eqnarray} 1\leq k \leq n \end{eqnarray}$ Partitionsklassen an. Erklären Sie Ihre Definition. Meine Ideen: Ich verstehe die Definition für den Fall k=1 oder k=n, denn wenn im Fall k=1 nur eine Partitionsklasse existiert dann ist diese gleich der Menge M und wenn k= n dann sind die Partionsklassen jeweils einelementig, so dass nur die Menge bestehend aus all diesen Partitionsklassen eine Partition von M ist. Allerdings verstehe ich nicht die Bedeutung und die genaue Funktionsweise für die Formel für denn Fall 'sonst'.
05.11.2017, 22:50	10001000Nick1	Auf diesen Beitrag antworten »
Jede Partition einer fünfelementigen Menge enthält mindestens eine und höchstens fünf Partitionsklassen. Die Anzahl der Partitionen ist also $\begin{eqnarray} \sum_{k=1}^5 \pi(5,k) \end{eqnarray}$ . Diese 5 Summanden rechnest du nacheinander aus. Für $\begin{eqnarray} k=1 \end{eqnarray}$ und $\begin{eqnarray} k=5 \end{eqnarray}$ steht das Ergebnis direkt in der Formel, die anderen berechnest du rekursiv: Z.B. ist $\begin{eqnarray} \pi(5,3)=\pi(5-1, 3-1)+3\cdot \pi(5-1, 3)=\pi(4,2)+3\cdot \pi(4,3) \end{eqnarray}$ Für diese beiden Summanden kannst du jetzt wieder die Rekursion einsetzen: $\begin{eqnarray} \pi(4,2)=\pi(3,1)+2\cdot \pi(3,2)=1+2\cdot\pi(3,2) \end{eqnarray}$ $\begin{eqnarray} \pi(4,3)=\pi(3,2)+3\cdot \pi(3,3)=\pi(3,2)+3 \end{eqnarray}$ usw.
09.11.2017, 03:01	Steffi92	Auf diesen Beitrag antworten »
Danke, das hat mir weitergeholfen .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »