Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

$$(a_{11}, a_{12}, \dots, a_{1n}) \mapsto (a_{11}, a_{21}, \dots, a_{n1})$$
is bijective, on one hand, and that $(a_{11}, a_{12}, \dots, a_{1n})$ is fixed by $f$ if and only if $(a_{11}, a_{21}, \dots, a_{n1})$ is a palindrome $(a_{i1} = a_{n-i+1,1}, i = 1, \dots, n)$, on the other.
To begin with, notice that the definition of the $a_{ij}$ is equivalent to the Pascal-like relation in $\mathbb{Z}_2$:
$$a_{ij} + a_{i-1,j} + a_{i-1,j+1} = 0. \quad (1)$$
Henceforth, such a triangular array will be called a Pascal binary (or dyadic) array.
Clearly, each binary string a in S yields a unique Pascal binary array $\hat{\mathbf{a}}$.
For more convenience, view a triangular array as a function on the standard lattice triangle
$$\Delta_n = \{(i, j) : i, j \ge 1 \text{ and } 2 \le i + j \le n + 1\},$$
situated in the first quadrant; thus, the first index runs horizontally and corresponds to columns, and the second index runs vertically and corresponds to rows.
Further, use the symbols $\to$, $\leftarrow$, $\uparrow$, $\downarrow$, $\searrow$ and $\nwarrow$ to denote the oriented sides of $\Delta_n$; explicitly,
$$\begin{align*} \to &= \{(i, 1) : i = 1, \dots, n\}, & \leftarrow &= \{(n - i + 1, 1) : i = 1, \dots, n\}, \\ \uparrow &= \{(1, j) : j = 1, \dots, n\}, & \downarrow &= \{(1, n - j + 1) : j = 1, \dots, n\}, \\ \searrow &= \{(i, n - i + 1) : i = 1, \dots, n\}, & \nwarrow &= \{(n - j + 1, j) : j = 1, \dots, n\}. \end{align*}$$
To establish a bijection between the fixed points of $f$ and the binary palindromes of length $n$, consider the transformations $\varrho$ and $\sigma$ of $\Delta_n$ defined by
$$\varrho(i, j) = (n - i - j + 2, i) \quad \text{and} \quad \sigma(i, j) = (n - i - j + 2, j).$$
The former is a permutation of order $3$ ($\varrho^3$ is the identity), and the latter is an involution ($\sigma^2$ is the identity). It is easily seen that
$$\varrho(\rightarrow) = \nwarrow, \varrho(\uparrow) = \leftarrow, \varrho(\nwarrow) = \downarrow \quad \text{and} \quad \sigma(\rightarrow) = \leftarrow, \sigma(\uparrow) = \nwarrow, \sigma(\nwarrow) = \uparrow,$$
so $\sigma\varrho(\rightarrow) = \uparrow$, $\sigma\varrho(\uparrow) = \rightarrow$, and $\sigma\varrho(\nwarrow) = \nwarrow$. It is also readily checked by (1) that, if $\hat{\mathbf{a}} = (a_{ij})$ is a Pascal binary array, then so are both
$$\varrho\hat{\mathbf{a}} = (a_{\varrho(i,j)}) \quad \text{and} \quad \sigma\hat{\mathbf{a}} = (a_{\sigma(i,j)}).$$
We are now in a position to prove the desired results.
Since $\sigma\varrho$ exchanges $\rightarrow$ and $\uparrow$, the assignment $\hat{\mathbf{a}}_{\uparrow} \mapsto \hat{\mathbf{a}}_{\downarrow}$ is bijective.
Since $\sigma$ exchanges $\uparrow$ and $\nwarrow$, and reverses orientation on the bottom row of $\Delta_n$, if $\hat{\mathbf{a}}_{\uparrow}$ is fixed by $f$, then $\hat{\mathbf{a}}_{\uparrow} = f(\hat{\mathbf{a}}_{\uparrow}) = \hat{\mathbf{a}}_{\nwarrow} = (\sigma\hat{\mathbf{a}})_{\uparrow}$, so $\hat{\mathbf{a}} = \sigma\hat{\mathbf{a}}$ and consequently $\hat{\mathbf{a}}_{\rightarrow} = (\sigma\hat{\mathbf{a}})_{\rightarrow} = \hat{\mathbf{a}}_{\leftarrow}$; that is, the bottom row of $\hat{\mathbf{a}}$ is a palindrome.
Conversely, if the bottom row of $\hat{\mathbf{a}}$ is a palindrome, $\hat{\mathbf{a}}_{\rightarrow} = \hat{\mathbf{a}}_{\leftarrow}$, then $(\sigma\varrho\hat{\mathbf{a}})_{\uparrow} = (\varrho\hat{\mathbf{a}})_{\uparrow}$, so $\sigma\varrho\hat{\mathbf{a}} = \varrho\hat{\mathbf{a}}$ and consequently, $f(\hat{\mathbf{a}}_{\uparrow}) = \hat{\mathbf{a}}_{\nwarrow} = (\sigma\varrho\hat{\mathbf{a}})_{\downarrow} = (\varrho\hat{\mathbf{a}})_{\downarrow} = \hat{\mathbf{a}}_{\uparrow}$; that is, $\mathbf{a} = \hat{\mathbf{a}}_{\uparrow}$ is fixed by $f$. This ends the proof.

The required number is $2^{\lfloor(n+1)/2\rfloor}$.

For convenience, we denote $b_k = a_{1,n-k}$ and $c_k = a_{k+1,n-k}$ for every $k = 0, 1, \dots, n-1$. Our aim is to find the set of relations for $(b_k)$ which are equivalent to the relation $(b_k) = (c_k)$. All the calculations will be made in $\mathbb{Z}_2$.
The definition of $a_{ij}$ is equivalent to
$$a_{ij} = a_{i-1,j} + a_{i-1,j+1}.$$
A straightforward check shows then that
$$a_{ij} = \sum_{\ell=0}^{i-1} \binom{i-1}{\ell} a_{1,\ell+j}.$$
For two nonnegative integers $k$ and $\ell$, we will write $\ell \preceq k$ if the binary representation of $\ell$ can be obtained from that of $k$ by replacing some ones by zeroes (the leading zeroes are allowed; thus $0 \preceq k$ and $k \preceq k$ for every $k$). We write $\ell \prec k$ if $\ell < k$ and $\ell \preceq k$. Recall that by Lucas' theorem, $\binom{k}{\ell}$ is odd if and only if $\ell \preceq k$. Thus,
$$c_k = a_{k+1,n-k} = \sum_{\ell=0}^{k} \binom{k}{\ell} a_{1,\ell+n-k} = \sum_{\ell=0}^{k} \binom{k}{\ell} b_{k-\ell} = \sum_{\ell=0}^{k} \binom{k}{\ell} b_{\ell} = \sum_{\ell \preceq k} b_{\ell}.$$
Now, the conditions $(b_k) = (c_k)$ rewrite as the set of equations
$$0 = \sum_{\ell \prec k} b_{\ell} \qquad (*)_{k}$$
for all $k = 0, 1, \dots, n-1$.
Denote by $T$ the set of all strings $(b_k)$ such that $(*)_k$ are satisfied for all odd $k \le n-1$. Each string in this set is determined uniquely by the values of $b_{2i-1}$ ($2i < n$) and $b_{n-1}$: the values of $b_{2i}$ (for $2i < n-1$) are found inductively from $(*)_{2i+1}$. Thus
$$|T| = 2^{\lceil n/2 \rceil} = 2^{\lfloor (n+1)/2 \rfloor}.$$
Now we claim that $T$ is exactly the desired set of fixed points; in fact, we will prove that all the relations $(*)_d$ for even $d$ follow from the relations $(*)_k$ for odd $k$.
Consider any even $d \le n-1$. To establish $(*_d)$, we add up all the relations $(*_k)$, where $k \prec d$, obtaining a sum
$$\begin{aligned} 0 &= \sum_{k \prec d} \sum_{\ell \prec k+1} b_{\ell} = \sum_{k \prec d} \left( \sum_{\ell \preceq k} b_{\ell} + \sum_{\ell \prec k} b_{\ell+1} \right) \\ &= \sum_{\ell \prec d} b_{\ell} \cdot \left| \{k: \ell \preceq k \prec d\} \right| + \sum_{\ell \prec d} b_{\ell+1} \cdot \left| \{k: \ell \prec k \prec d\} \right|. \end{aligned}$$
But one can easily check that $|\{k: \ell \preceq k \prec d\}|$ is odd, and $|\{k: \ell \prec k \prec d\}|$ is even for all $\ell \prec d$. Thus our equality rewrites exactly as $(*_d)$.

Therefore, the number of fixed points is $2^{\lfloor(n+1)/2\rfloor}$.