On an $8 \times 8$ chessboard, a rook stands on the bottom left corner square. We want to move it to the upper right corner, subject to the following rules: we have to move the rook exactly $9$ times, such that the length of each move is either $3$ or $4$. (It is allowed to mix the two lengths throughout the "journey".) How many ways are there to do this? In each move, the rook moves horizontally or vertically.
Problem
Source: 2021 Dürer Math Competition Finals Day2 E9 https://artofproblemsolving.com/community/c2749870_
Tags: combinatorics, Chessboard