Question 100
A sequence of $2n + 1$ non-negative integers $a_1, a_2, \dots, a_{2n+1}$ is given. There's also a sequence of $2n + 1$ consecutive cells enumerated from $1$ to $2n + 1$ from left to right, such that initially the number $a_i$ is written on the $i$-th cell, for $i = 1, 2, \dots, 2n + 1$. Starting from this initial position, we repeat the following sequence of steps, as long as it's possible:
*Step 1:* Add up the numbers written on all the cells, denote the sum as $s$.
*Step 2:* If $s$ is equal to $0$ or if it is larger than the current number of cells, the process terminates. Otherwise, remove the $s$-th cell, and shift all cells that are to the right of it one position to the left. Then go to Step 1.
Example: $(1, 0, 1, \underline{2}, 0) \to (1, \underline{0}, 1, 0) \to (1, \underline{1}, 0) \to (\underline{1}, 0) \to (0)$.
A sequence $a_1, a_2, \dots, a_{2n+1}$ of non-negative integers is called balanced, if at the end of this process there's exactly one cell left, and it's the cell that was initially enumerated by $(n+1)$, i.e. the cell that was initially in the middle.
Find the total number of balanced sequences as a function of $n$.
*Step 1:* Add up the numbers written on all the cells, denote the sum as $s$.
*Step 2:* If $s$ is equal to $0$ or if it is larger than the current number of cells, the process terminates. Otherwise, remove the $s$-th cell, and shift all cells that are to the right of it one position to the left. Then go to Step 1.
Example: $(1, 0, 1, \underline{2}, 0) \to (1, \underline{0}, 1, 0) \to (1, \underline{1}, 0) \to (\underline{1}, 0) \to (0)$.
A sequence $a_1, a_2, \dots, a_{2n+1}$ of non-negative integers is called balanced, if at the end of this process there's exactly one cell left, and it's the cell that was initially enumerated by $(n+1)$, i.e. the cell that was initially in the middle.
Find the total number of balanced sequences as a function of $n$.