Question 78
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(2^n)$, from left to right.
* 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(2^n)$, from left to right.