Partitionen und Stirlingzahlen

18.10.2007, 21:30

Fletcher

Partitionen und Stirlingzahlen

Guten Abend,

wollte gerade folgendes zeigen:

$\begin{eqnarray*} S(n,2)=2^{n-1}-1 \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$

Denke mal das geht mit Induktion, aber der Induktionsschluss ist mir dann nicht so klar,
hat jemand eine Idee?

19.10.2007, 11:25

therisen

Auf diesen Beitrag antworten »

Man überlegt sich leicht, dass

$\begin{eqnarray*} S(n,2)=S(n-1,1)+2S(n-1,2) \end{eqnarray*}$

Jetzt kannst du deine Induktionsvoraussetzung benutzen.

Gruß, therisen

20.10.2007, 09:04

Fletcher

Auf diesen Beitrag antworten »

Für n=2 erhalte ich nach deiner Formel:

$\begin{eqnarray*} S(2,2)=S(1,1)+2 \cdot S(1,2) \end{eqnarray*}$

Der letzte Summand ist dann die leere Menge, oder?

Muss man diese Formel nicht auch irgendwie herleiten, weil die fällt ja anfangs schon vom Himmel! Aber mir ist klar, dass sie stimmt.

20.10.2007, 11:07

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von Fletcher
Der letzte Summand ist dann die leere Menge, oder?

Der letzte Summand ist dann Null.

Zitat:

Original von Fletcher
Muss man diese Formel nicht auch irgendwie herleiten, weil die fällt ja anfangs schon vom Himmel! Aber mir ist klar, dass sie stimmt.

Natürlich muss man diese Formel begründen.

Neue Frage »

Antworten »

Partitionen und Stirlingzahlen

Verwandte Themen