König kreuzt Schachbrett (edit)

30.04.2019, 07:58	Mona Mona	Auf diesen Beitrag antworten »
König kreuzt Schachbrett (edit) Diese Aufgabe soll im Rahmen der Übung zur Vorlesung "Diskrete Mathematik" gelöst werden. Ein König soll von der linken unteren Ecke in die rechte obere Ecke bewegt werden. Er darf nur nach rechts (r) oder nach oben (o) oder diagonal nach rechts oben (d) gezogen werden. Wie viele Möglichkeiten gibt es ? Wenn man die diagonale Züge (d) außer Acht lässt, dann ist die Aufgabe sehr leicht lösbar. Man muss die Anordungen des Strings "7xr 7xo" multinominal berechnen: $\begin{eqnarray} \begin{pmatrix} 14! \\ 7! 7! \end{pmatrix} \end{eqnarray}$ Das ist Schulmathematik. Mit der Diagonalen wird das jetzt schwieriger, denn durch jeden Zug (d) verringert sich die Anzahl der gesamten Züge. Muss ich jetzt wirklich für (6xr 6xo 1xd), (5xr 5xo 2xd) usw. die Anzahl berechnen and dann aufaddieren ? Das scheint mir sehr umständlichzu sein ! Aber mir fehlt einfach die Idee zu einem besseren Ansatz ! Admin: Ich kann meinen ersten Beitrag leider nicht editieren. Bitte die vorangehende Version löschen !
30.04.2019, 08:59	Dopap	Auf diesen Beitrag antworten »
richtig, 14 über 7 sind Pfade ohne Diagonalschritte, d=0 aber, entweder einen Bruch schreiben oder 14 Über 7 schreiben.
30.04.2019, 09:18	Mona Mona	Auf diesen Beitrag antworten »
natürlich ... die Anzahl ohne diagonal Schritte ist: $\begin{eqnarray} \frac{14!}{7! 7!} = \begin{pmatrix} 14 \\ 7 \end{pmatrix} \end{eqnarray}$ Aber wie steht es denn jetzt um die Sache mit den diagonal Schritten. Es sind 1 - 7 diagonal Schritte möglich. Muss ich das jetzt wirklich für jeden Fall einzeln berechnen ? Das ist eine ganz schne Rechnerei. Oder gibt es da einen geschickteren Ansatz ?
30.04.2019, 11:55	HAL 9000	Auf diesen Beitrag antworten »
Sei $\begin{eqnarray} k \end{eqnarray}$ die Anzahl der Diagonalzüge mit $\begin{eqnarray} 0\leq k\leq 7 \end{eqnarray}$ , dann hat man genau $\begin{eqnarray} 14-k \end{eqnarray}$ Züge aufgeteilt in $\begin{eqnarray} k\times d,\; (7-k)\times r,\; (7-k)\times o \end{eqnarray}$ Diese Züge kann man auf $\begin{eqnarray} \frac{(14-k)!}{k!(7-k)!^2} \end{eqnarray}$ verschiedene Weisen permutieren, die gesuchte Gesamtanzahl ist damit $\begin{eqnarray} \sum_{k=0}^7 \frac{(14-k)!}{k!(7-k)!^2} \end{eqnarray}$ . Ich denke nicht, dass man diese Summe noch substanziell vereinfachen kann, man muss sie schlicht ausrechnen.
30.04.2019, 12:25	Dopap	Auf diesen Beitrag antworten »
na ja, soviel Rechnerei ist es auch nicht. $\begin{eqnarray} \sum_{d=0}^7 \frac {(d +2(7-d))!} {d!\cdot ((7-d)!)^2}=48639 \end{eqnarray}$ siehe oben!
30.04.2019, 13:21	Mona Mona	Auf diesen Beitrag antworten »
danke ihr beiden ! Da bin ich ja erleichtert. Ich dachte schon, ich hätte iwas ganz triviales übersehen. Viel zu rechnen ist da nicht. Wenn es sich nicht gerade um ein 800 x 800 großes Schachbrett handelt. ich hatte das schon für verschiedene Schachbretter ausgerechnet: 3 x 3 Schachbrett: 13 Möglichkeiten 4 x 4 Schachbrett: 63 Möglichkeiten 5 x 5 Schachbrett: 320 Möglichkeiten ... 8 x 8 Schachbrett: 48.639 Möglichkeiten (welche Koinzidenz mit @Dopap ) Nach einer "einfachen" Formel sieht mir das nicht gerade aus. Dann isses wohl so. Also vielen Dank für eure Hilfe ...
Anzeige

01.05.2019, 00:10	Dopap	Auf diesen Beitrag antworten »
wenn man am 1. Mai nix vorhat könnte man das ja noch auf die Anzahl der Wege im 8 x 8 x 8 Kubus ausweiten. Dabei sind 2^3-1=7 Zugtypen möglich z1=(1,0,0) z2=(0,1,0) z3=(0,0,1) z4=(1,1,0) z5=(1,0,1) z6=(0,1,1) z7=(1,1,1) Jedes Tupel aus den z1...z7 mit Summe jeder Koordinaten-Spalte = 7 beschreibt einen Weg von Ecke (1,1,1) zur Ecke (8,8,8) Nur eine formelmäßige Notation ist momentan nicht in Sicht

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »