Kombinatorischer Beweis für Zugmöglichkeiten auf Schachbrett

29.06.2018, 15:47	nist	Auf diesen Beitrag antworten »
Kombinatorischer Beweis für Zugmöglichkeiten auf Schachbrett Meine Frage: Hallo liebes Forum, ich habe Probleme bei der Beantwortung der zweiten Teilaufgabe. Für das Verstaendnis folgt die gesamte Aufgabenstellung: Gegeben sei ein (allgemeines) m × n Schachbrett, wobei m, n ? N mit m ? 1 und n ? 1. Ein Koenig soll vom Feld (1, 1) (links unten) zum Feld (m, n) (rechts oben) laufen. Dabei darf er in einem Schritt nur eine der drei folgenden Bewegungen ausfuhren: ? Ein Feld vertikal nach oben laufen. ? Ein Feld horizontal nach rechts laufen. ? Ein Feld diagonal nach rechts oben laufen. Sei f(m, n) die Anzahl moeglicher Pfade, die der Koenig auf einem m × n Schachbrett von links unten nach rechts oben laufen kann (z.B. gilt f(2, 2) = 3). 1. Geben Sie eine rekursive Darstellung fuer f an und begruenden Sie diese. ¨ 2. Zeigen Sie, dass $\begin{eqnarray} f(n,n) = \sum\limits_{i=0}^{n-1} \begin{pmatrix} n - 1 \\ i\end{pmatrix} \begin{pmatrix} n + i - 1 \\ i \end{pmatrix} \end{eqnarray}$ Meine Ideen: Für den ersten Teil habe ich folgende rekursive Darstellung gefunden: $\begin{eqnarray} f(n,m) = f(n-1,m) + f(n-1,m-1) + f(n,m-1) \end{eqnarray}$ Für den zweiten Teil habe ich eine vollständige Induktion angefangen, bei der ich die Darstellung aus Teil 1 mit der aus Teil 2 gleichgesetzt habe. Dabei bin ich jedoch in einer Sackgasse gelandet. Nun habe ich von einem WiMi gehört, dass ein kombinatorischer Beweis besser geeignet sei, habe allerdings keine Ahnung, wie ich diesen beginnen kann. Könnt ihr mir einen Hinweis dazu geben? Grüße und Dank im Voraus! Nist
29.06.2018, 16:10	Leopold	Auf diesen Beitrag antworten »
Beispiele mit meinem CAS zeigen: Gleichheit scheint nur zu bestehen, wenn man die Summation in 2. mit $\begin{align} i=0 \end{align}$ beginnt. EDIT Offenbar mittlerweile Korrekur erfolgt.
29.06.2018, 16:28	HAL 9000	Auf diesen Beitrag antworten »
nist = gast543 ? ------------------------------------------------ 2. geht kombinatorisch so: $\begin{eqnarray} n-i-1 \end{eqnarray}$ sei die Anzahl der Diagonalschritte. Da insgesamt $\begin{eqnarray} (n-1) \end{eqnarray}$ Positionswechsel nach oben und $\begin{eqnarray} (n-1) \end{eqnarray}$ Positionswechsel nach rechts gemacht werden müssen, verbleiben dann noch genau $\begin{eqnarray} i \end{eqnarray}$ Schritte nach oben sowie $\begin{eqnarray} i \end{eqnarray}$ Schritte nach rechts. Wie man diese insgesamt $\begin{eqnarray} (n-i-1)+i+i = n+i-1 \end{eqnarray}$ Schritte anordnet, ist wurst, die Anzahl derartiger Anordnungmöglichkeiten ergibt sich gemäß Permutationen mit Wiederholung als $\begin{eqnarray} \frac{(n+i-1)!}{(n-i-1)!i!^2} = \binom{n+i-1}{i}\binom{n-1}{i} \end{eqnarray}$ . Da man zudem $\begin{eqnarray} i \end{eqnarray}$ frei wählen kann von $\begin{eqnarray} 0 \end{eqnarray}$ bis $\begin{eqnarray} n-1 \end{eqnarray}$ , ist die Formel bewiesen. ------------------------------------------------ Im verlinkten Thread hatte ich bereits auf Folge http://oeis.org/A001850 verwiesen, um die es hier in 2) offenbar geht (nur um einen Index verschoben). Für $\begin{eqnarray} a_n=f(n,n) \end{eqnarray}$ scheint da die (nur eindimensionale) Rekursion $\begin{eqnarray} a_0=0,\; a_1 = 1,\; a_{n+1} = \frac{1}{n}\left( 3(2n-1)a_n-(n-1)a_{n-1}\right) \end{eqnarray}$ zu gelten. Interessant ist auch das Auftreten dieser $\begin{eqnarray} a_n \end{eqnarray}$ in der Potenzreihenentwicklung $\begin{eqnarray} \frac{x}{\sqrt{1-6x+x^2}} = \sum_{n=1}^{\infty} a_nx^n \end{eqnarray}$ .
29.06.2018, 16:59	nist	Auf diesen Beitrag antworten »
Danke für die schnelle Antwort! Auf die Idee, dass mit den Binomialkoeffizienten die Diagonalschritte gemeint sind, wäre ich wohl nie gekommen ><

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »