RMM 2024 Problem 1

Let $n$ be a positive integer. Initially, a bishop is placed in each square of the top row of a $2^{n} \times 2^{n}$ chessboard; those bishops are numbered from 1 to $2^{n}$, from left to right. A jump is a simultaneous move made by all bishops such that the following conditions are satisfied:

• each bishop moves diagonally, in a straight line, some number of squares, and
• at the end of the jump, the bishops all stand in different squares of the same row.

Find the total number of permutations $\sigma$ of the numbers $1,2, \ldots, 2^{n}$ with the following property: There exists a sequence of jumps such that all bishops end up on the bottom row arranged in the order $\sigma(1), \sigma(2), \ldots, \sigma\left(2^{n}\right)$, from left to right.