5. Let's call a cross a table composed of the union of one $a \times 1$ table and one $1 \times b$ table that have exactly one common field ($a, b \in \mathbb{N}$). A set of some fields of such a table is called a connected area if from any field in this set, one can reach any other field by moving only to adjacent fields within the observed set (adjacent fields are those that share a side). For a given natural number $n$, determine the number of ways in which the numbers $1,2, \ldots, n$ can be written into some cross with $n$ fields (the cross is not predefined), each number in exactly one field, under the condition that for each $k, k \in\{1,2, \ldots, n\}$, the fields in which the numbers $1,2, \ldots, k$ are written form a connected area.

## Third Grade - A Category
5. Note that tables $a \times 1$ and $1 \times b$ represent special cases of crosses; we will call such crosses umpani (vertical, respectively horizontal). For other crosses, the intersection of the two tables that form it will be called the center of the cross, and such crosses (after writing numbers according to the conditions of the problem) will be divided into horizontal, vertical, or central, depending on whether the number 1 is written somewhere in the horizontal component but outside the center, somewhere in the vertical component but outside the center, or precisely in the center.

For a given number $n$, consider all crosses filled with numbers according to the conditions of the problem, and let $A$ be the number of horizontal crosses among them, $B$ the number of central crosses, and $C$ the number of vertical crosses. Due to symmetry, the total number sought in the problem statement is $2A + B + 2C$.

First, let's determine the number $A$. Note that every number from 2 onwards is written in a cell either immediately to the left or immediately to the right of the block formed by the numbers preceding it. In this way, we can associate with each horizontally filled cross a sequence of letters $L$ and $R$ of length $n-1$, and it is clear that from any such sequence, we can uniquely reconstruct the original cross. Therefore, $A = 2^{n-1}$.

Similarly, we calculate the number $B$. The number 1 is written in the center, and each subsequent number is written either in the upper, right, lower, or left "arm" (in a uniquely determined cell). At the same time, we need to subtract those possibilities that result in a horizontal or vertical cross. Altogether, we get $B = 4^{n-1} - 2A = 4^{n-1} - 2^n$.

Finally, consider the horizontal crosses. Let the number in the center be $k, k \neq 1$. Then the numbers from 1 to $k$ are all on the horizontal line, and we calculate that there are $2^{k-1}$ possibilities for them; for the next $n-k$ numbers, similarly as before, we see that there are $4^{n-k}$ possibilities, from which we need to subtract those when all these numbers are arranged horizontally, which is $2^{n-k}$ arrangements. Altogether, if the number in the center is $k$, the total number of possibilities is $2^{k-1}(4^{n-k} - 2^{n-k})$.

Now we have everything necessary to complete the calculation:

$$
\begin{aligned}
2A + B + 2C & = 2^n + (4^{n-1} - 2^n) + 2\left(\sum_{k=2}^{n} 2^{k-1}(4^{n-k} - 2^{n-k})\right) \\
& = 4^{n-1} + 2^n\left(\sum_{k=2}^{n}(2^{n-k} - 1)\right) = 4^{n-1} + 2^n\left(\sum_{i=0}^{n-2} 2^i - (n-1)\right) \\
& = 4^{n-1} + 2^n\left(2^{n-1} - 1 - n + 1\right) = 4^{n-1} + 2^n\left(2^{n-1} - n\right)
\end{aligned}
$$

## Third Grade - A Category