Der Königsweg

Es gibt 48639 Wege.

Von Ortwin Gasper

Beschränken wir uns auf Züge nach rechts und oben, so erhält man von der linken unteren zur rechten oberen Ecke einem m*n-Schachbrettes

 

Wege. Ein Weg mit k diagonalen Zügen von der linken unteren zur rechten oberen Ecke eines n*n-Schachbrettes läßt sich zusammensetzen aus einem Weg ohne Diagonalzüge auf einem (n-k)*(n-k)-Schachbrett, und einer Aufteilung der k Diagonalzüge auf die 2(n-k)+1 'Zwischenräume' zwischen den 2(n-k) rechts- bzw. oben Zügen, dabei gilt vor dem ersten wie nach dem letzten dieser Züge auch als Zwischenraum. Geordnete Partitionen von k auf s Summanden gibt es

 

Also erhalten wir für ein n*n-Brett

 

Wege. Für die Anzahl der Wege erhält man:

 n   Wege
 2      3
 3     13
 4     63
 5    321
 6   1683
 7   8989
 8  48639,

Von Wolf W. Radzinski:

Ausgehend von linken unteren Feld führt ein Weg auf das Feld rechts daneben, ein Weg auf das Feld darüber und drei Wege auf das Feld Diagonal rechts oben (diagonal, erst nach rechts dann nach oben, erst nach oben dann nach rechts).

  1 3
  1 1

Weitere Überlegungen dieser Art ergeben, dass zu allen Randfeldern nur ein einziger Weg führt und zu alle anderen Feldern so viele Wege, wie zu den Feldern links, darunter und links darunter führen (weil das jeweilige Feld von jedem dieser Felder in genau einem Schritt erreicht werden kann):

  .  .  .  .  .
  1  7 25 68  .
  1  5 13 25  .
  1  3  5  7  .
  1  1  1  1  .