Kombinatorischer Beweis einer Gleichung (u.a. summe von Einsen und k Zweien)

31.05.2005, 00:03	Asgaroth	Auf diesen Beitrag antworten »
Kombinatorischer Beweis einer Gleichung (u.a. summe von Einsen und k Zweien) 3.Wir wollen die Gleichung $\begin{eqnarray} \sum_{k=0}^{[\frac {n}{2}]}~ \begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray}$ (das $\begin{eqnarray} \frac{n}{2} \end{eqnarray}$ soll abgerundet sein, keine ahnung wie man die Gaussklammern in latex macht...) kombinatorisch beweisen. Dazu betrachten wir das Problem, auf wieviele Arten man eine natürliche Zahl n geordnet und ohne Klammern als Summe von Einsen und Zweien schreiben kann (also z.B. 9 = 2+1+1+2+1+2). Diese Anzahl bezeichnen wir mit f(n). 1. Auf wieviele Arten kann man n geordnet und ohne Klammern als Summe von Einsen und genau k Zweien schreiben? Welche Formel ergibt sich daraus für f(n)? 2. Man beweise f(n) = f(n-1)+f(n-2) für n > 2, indem man die beiden Möglichkeiten für den letzten Summanden untertscheidet. Man folgere die obige Gleichung. (Hinweis: Beachte die Anfangswerte f(0) = f(1) = 1.) Sorry war wohl etwas übereifrig, hab grad mit einem Freund nr. 1) gelöst: $\begin{eqnarray} f(n) = \begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray}$ die Formel ergibt sich daraus das: n-2k die anzahl der einsen, k die anzahl der zweien, n-2k + k = n-k die anzahl der Elemente der Zahlpartition von n und daraus folgt aus der allgemeinen Formel für Permutationen von 2 Gruppen nicht unterscheidbarer Elemente = $\begin{eqnarray} \frac{(n-k)!}{((n-2k)!k!)} \end{eqnarray}$ was $\begin{eqnarray} f(n) = \begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray*}$ entspricht. Falls jemand darin einen Fehler sieht, bitte sagen... MfG Asgaroth
31.05.2005, 13:50	Asgaroth	Auf diesen Beitrag antworten »
So jetzt hab ich nachdem ich ja gestern noch rausgefunden hatte das $\begin{eqnarray} f(n) = \begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray}$ das mal in die rekursion eingesetzt. Ich hab die Induktion dafür schon angefangen: Induktionsanfang (n=2): $\begin{eqnarray} f(2)=f(1)+f(0)=1+1 = 0 \end{eqnarray}$ (Laut Aufgabe: f(1)=f(0)=1) $\begin{eqnarray} \sum_{k=0}^\infty~\begin{pmatrix} 2-k \\ k \end{pmatrix} \end{eqnarray}$ da jedoch für $\begin{eqnarray} k>1 , k>2-k \end{eqnarray}$ folgt somit $\begin{eqnarray} \begin{pmatrix} 2-k \\ k \end{pmatrix} = 0 \end{eqnarray}$ für $\begin{eqnarray} k>1 \end{eqnarray}$ da das ganze eine Summe ist können also die Werte $\begin{eqnarray} k>1 \end{eqnarray}$ vernachlässigt werden (nur für n=2). daraus folgt: $\begin{eqnarray} \sum_{k=0}^1~\begin{pmatrix} 2-k \\ k \end{pmatrix}= 1+1 = 2 \end{eqnarray}$ . Soweit so gut, jetzt weiß ich aber leider nicht wie ich den Induktionsbeweis weitermachen soll. Induktionsschritt (n\Rightarrow n+1): $\begin{eqnarray} f(n+1) = f(n) + f(n-1) \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} n-k+1 \\ k \end{pmatrix} = \begin{pmatrix} n-k \\ k \end{pmatrix} + \begin{pmatrix} n-k-1 \\ k \end{pmatrix} \end{eqnarray}$ wenn man jetzt m=n-k setzt bekommt man: $\begin{eqnarray} \begin{pmatrix} m+1 \\ k \end{pmatrix} = \begin{pmatrix} m \\ k \end{pmatrix} + \begin{pmatrix} m-1 \\ k \end{pmatrix} \end{eqnarray}$ was ja fast der rekursionsgleichung für binome entspricht: $\begin{eqnarray} \begin{pmatrix} m+1 \\ k \end{pmatrix} = \begin{pmatrix} m \\ k \end{pmatrix} + \begin{pmatrix} m \\ k-1 \end{pmatrix} \end{eqnarray}$ Vielleicht hat ja jemand ne idee... Achja, ich weiß inzwischen auch wie man auf die ursprüngliche Formel $\begin{eqnarray} \sum_{k=0}^{\frac{n}{2}}~\begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray}$ (ich weiß immernoch nicht wie man Gaussklammern in LaTeX macht G) kommt: $\begin{eqnarray} f(n)=\begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray}$ gilt für ein bestimmtes k. also gilt für ein unbestimmtes k: $\begin{eqnarray} f(n)=\sum_{k=0}^{\infty}~\begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray}$ und nun kann man wieder wie oben folgern: Da für $\begin{eqnarray} k>\frac{n}{2} , k>n-k \end{eqnarray}$ folgt somit $\begin{eqnarray} \begin{pmatrix} n-k \\ k \end{pmatrix} = 0 \end{eqnarray}$ für $\begin{eqnarray} k>\frac{n}{2} \end{eqnarray}$ da das ganze eine Summe ist können also die Werte $\begin{eqnarray} k>\frac{n}{2} \end{eqnarray}$ vernachlässigt werden (für alle $\begin{eqnarray} n \in \mathbb N \end{eqnarray}$ ). Hoffe jemand hat jetzt noch ne idee zu der Rekursionsgleichung, dann hab ich die Aufgabe ja... MfG Asgaroth
29.05.2009, 13:08	yalli	Auf diesen Beitrag antworten »
F(n)= $\begin{eqnarray} \sum_{k=0}^{[\frac {n}{2}]}~ \begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray}$ kann jemand für n=1,2,...,7 berechnen? und welches Bildugsgesetztz erfüllen di F(n) vermutlich?Beweis? Vielen Dank

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »