A king is placed in the left bottom corner of the 6 by 6 chessboard. At each step it can either move one square up, or one square to the right, or diagonally - one up and one to the right. How many ways are there for the king to reach the top right corner of the board?
We shall make a $6 \times 6$ table. In each cell of the table we will write a number of ways in which the king can reach that cell. We will fill it out gradually starting with a row of ones at the bottom and a column of ones at the left. To fill out the rest we use the following rule: the number in each cell is equal to the sum of the numbers immediately below, to the left, and diagonally (to the left and below). The result is:

| 1 | 11 | 61 | 231 | 681 | 1683 |
| :---: | :---: | :---: | :---: | :---: | :---: |
| 1 | 9 | 41 | 129 | 321 | 681 |
| 1 | 7 | 25 | 63 | 129 | 231 |
| 1 | 5 | 13 | 25 | 41 | 61 |
| 1 | 3 | 5 | 7 | 9 | 11 |
| 1 | 1 | 1 | 1 | 1 | 1 |