Solution
The Hurried King
Show the problem again
A king stands at the lattice point (0, 0) and wants to reach (5, 5). Each move takes it one unit east (to (x + 1, y)), one unit north (to (x, y + 1)), or one unit diagonally northeast (to (x + 1, y + 1)). How many different sequences of moves take it from (0, 0) to (5, 5)? Give an integer.
Worked solution
**Answer: 1683.** Suppose the king makes exactly k diagonal moves. Then it also makes 5 − k east moves and 5 − k north moves, 10 − k moves in all, and these can be ordered in (10 − k)! / (k! (5 − k)! (5 − k)!) ways. Summing over k = 0, 1, ..., 5: 252 + 630 + 560 + 210 + 30 + 1 = 1683. These are the central Delannoy numbers, which also satisfy D(x, y) = D(x − 1, y) + D(x, y − 1) + D(x − 1, y − 1) and the neat closed form D(n, n) = Σ_k C(n, k)² 2^k = 1 + 50 + 400 + 800 + 400 + 32 = 1683.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.