Bell Zahlen

10.05.2016, 13:58

Cyneon

Bell Zahlen

Meine Frage:
Ich habe dies vorgegeben:
$\begin{eqnarray*} B_{n} = \sum\limits_{k=0}^{n-1} \begin{pmatrix} n-1 \\ k \end{pmatrix} * B_{k} \end{eqnarray*}$

Ich soll eine vollständige Induktion für $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ machen.

PS: Aus irgendeinem Grund habe ich schon ein Beitrag verfasst, aber der war noch nicht vollständig.

Meine Ideen:
Meine Frage wäre ob ich dies so umschreiben darf:
$\begin{eqnarray*} B_{n} = \sum\limits_{k=1}^{n} \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} * B_{n-k} \end{eqnarray*}$
Wenn nein, wie kann ich vorgehen bei der vollständigen Induktion. Rein theoretisch ist ja $\begin{eqnarray*} n = 1 \end{eqnarray*}$ und somit wäre für den Induktionsanfang

$\begin{eqnarray*} B_{1} = \sum\limits_{k=0}^{1-1} \begin{pmatrix} 1-1 \\ k \end{pmatrix} * B_{k} \end{eqnarray*}$
Das wäre dann ja $\begin{eqnarray*} B_{1} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} * B_{0}= 1 \end{eqnarray*}$
Somit wäre die IV $\begin{eqnarray*} B_{n} \end{eqnarray*}$ erfüllt.
Wenn ich jetzt
$\begin{eqnarray*} B_{n+1} = \sum\limits_{k=0}^{n+1-1} \begin{pmatrix} n+1-1 \\ k \end{pmatrix} * B_{k} = B_{n+1} = \sum\limits_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} * B_{k} \end{eqnarray*}$ Dann weiß ich hier leider nicht weiter. Zumindest

10.05.2016, 14:07

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Cyneon
Ich soll eine vollständige Induktion für $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ machen.

Wofür? Bitte sauber trennen:

1.Was sollst du für die Bellschen Zahlen beweisen?
2.Was darfst du an Kenntnissen über die Bellschen Zahlen verwenden (d.h., wie sind sie definiert)?

Mir ist z.B. an deinem Text nicht klar geworden, ob die oben genannte Gleichung nun eine verwendbare Eigenschaft oder die Behauptung ist. unglücklich

10.05.2016, 14:18

Cyneon

Auf diesen Beitrag antworten »

Hallo HAL 9000,
ich soll eine vollständige Induktion auf $\begin{eqnarray*} B_{n} = \sum\limits_{k=0}^{n-1} \begin{pmatrix} n-1 \\ k \end{pmatrix} * B_{k} \end{eqnarray*}$ für $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ ausführen. Also meine Vorgabe im obigen Beitrag.
Definiert haben wir die Bellsche Zahl so:
$\begin{eqnarray*} B_{n} = \sum\limits_{k=0}^{n} S_{n,k} \end{eqnarray*}$

10.05.2016, 14:23

HAL 9000

Auf diesen Beitrag antworten »

Also gut: $\begin{eqnarray*} B_{n} = \sum\limits_{k=0}^{n-1} \begin{pmatrix} n-1 \\ k \end{pmatrix} * B_{k} \end{eqnarray*}$ ist damit deine Behauptung.

Klare deutliche Sprache ist wichtig: Wenn du sagst, du hast die Gleichung "vorgegeben", dann ist das für mich eher eine Voraussetzung. unglücklich

Zum Beweis selbst kann ich nichts sagen, da deine Definition der Bell-Zahlen neue Unbekannte $\begin{eqnarray*} S_{n,k} \end{eqnarray*}$ ins Spiel gebracht hat.

EDIT: Wenn man als Definition aber eher ansieht, dass $\begin{align*} B_n \end{align*}$ die Anzahl der Partitionen einer Menge der Mächtigkeit $\begin{align*} n \end{align*}$ ist, dann ist mir schon eher klar, wie man hier vorgehen kann.

10.05.2016, 14:41

Cyneon

Auf diesen Beitrag antworten »

Definition in Wikipedia:
Bellsche Zahlen:
Da die Stirling-Zahl S(n, k) zweiter Art die Anzahl der k-Partitionen einer n-elementigen Menge ist, gilt
$\begin{eqnarray*} B_{n} = \sum\limits_{k=0}^{n} S_{n,k} \end{eqnarray*}$

und
Bellsche Zahlen größer als $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$
$\begin{eqnarray*} B_{n} = \sum\limits_{k=0}^{n-1} \begin{pmatrix} n-1 \\ k \end{pmatrix} \end{eqnarray*}$
Also so wie ich das verstanden habe muss man die beiden Definitionen von der Bellschen Zahl miteinander Vergleichen und dies beweisen.

EDIT: Ja ich habe das in deinem Edit auch so verstanden aber weiß halt nicht wie ich da vorgehen soll. Daher habe ich gedacht, dass ich die beiden vergleichen soll.

10.05.2016, 14:50

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Cyneon
Also so wie ich das verstanden habe muss man die beiden Definitionen von der Bellschen Zahl miteinander Vergleichen und dies beweisen.

Vielleicht nennst du ja mal die Aufgabenstellung im Originalwortlaut. Ich habe irgendwie immer weniger Vertrauen in das, wie du es verstanden hast.

10.05.2016, 15:01

Cyneon

Auf diesen Beitrag antworten »

Ja vermutlich habe ich mit dem Edit mehr Verwirrung rein gebracht.

Es ist:

Die n-te Bell-Zahl $\begin{eqnarray*} B_{n} \end{eqnarray*}$ , gibt di Anzahl der Partitionen einer n-elementigen Grundmenge an. Des weiteren gil $\begin{eqnarray*} B_{n} =\sum\limits_{k=0}^{n} S_{n,k} \end{eqnarray*}$
Zeigen sie dass für $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ gilt:

$\begin{eqnarray*} B_{n} = \sum\limits_{k=0}^{n-1} \begin{pmatrix} n-1 \\ k \end{pmatrix} * B_{k} \end{eqnarray*}$

10.05.2016, 15:06

HAL 9000

Auf diesen Beitrag antworten »

Auf der englischen Wikipediaseite steht schon ein Hinweis, wie man das auf Basis der erstgenannten Partitionsanzahl-Definition nachweisen kann.

Aber ein Induktionsbeweis ist das nicht wirklich: An keiner Stelle wird die Induktionsvoraussetzung benötigt.

10.05.2016, 15:19

Cyneon

Auf diesen Beitrag antworten »

Wikipediausschnitt:
This formula can be derived by expanding the exponential generating function using the Taylor series for the exponential function, and then collecting terms with the same exponent.[8] It allows Bn to be interpreted as the nth moment of a Poisson distribution with expected value 1.

The nth Bell number is also the sum of the coefficients in the nth complete Bell polynomial, which expresses the nth moment of any probability distribution as a function of the first n cumulants.

Vermutlich meinst du diesen Absatz.

Also ein kombinatorischer Beweis? Aber ist es denn mit vollständiger Induktion überhaupt machbar?

10.05.2016, 15:25

HAL 9000

Auf diesen Beitrag antworten »

Wo schaust du denn da nach? unglücklich

Ich meine den Absatz direkt unter deiner nachzuweisenden Formel $\begin{align*} B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k \end{align*}$ :

Zitat:

Original von https://en.wikipedia.org/wiki/Bell_number

It can be explained by observing that, from an arbitrary partition of $\begin{align*} n+1 \end{align*}$ items, removing the set containing the first item leaves a partition of a smaller set of $\begin{align*} k \end{align*}$ items for some number $\begin{align*} k \end{align*}$ that may range from $\begin{align*} 0 \end{align*}$ to $\begin{align*} n \end{align*}$ . There are $\begin{align*} \tbinom{n}{k} \end{align*}$ choices for the $\begin{align*} k \end{align*}$ items that remain after one set is removed, and $\begin{align*} B_k \end{align*}$ choices of how to partition them.

10.05.2016, 15:38

Cyneon

Auf diesen Beitrag antworten »

Uups, da bin ich wohl verrutscht.

Mein Problem ist halt, wenn ich es mit vollständige Induktion mache, ist das dann machbar? Weil am Ende müsste ich ja trotz alledem auf meine ursprüngliche Formel zurückkommen.

10.05.2016, 15:43

HAL 9000

Auf diesen Beitrag antworten »

Man kann natürlich jeden Beweis, der ohne Induktion auskommt, künstlich zu einem Induktionsbeweis aufblasen - wenn's Spaß macht. Augenzwinkern

Im Ernst: Wo siehst du hier Potential für einen "echten" Induktionsbeweis, d.h., wo die nachzuweisende Formel für $\begin{align*} <n \end{align*}$ in einem Induktionsschritt einen substanziellen Beitrag zum Beweis der Formel für $\begin{align*} n \end{align*}$ leisten kann?

Neue Frage »

Antworten »

Bell Zahlen

Verwandte Themen