2. Let $n$ be a natural number. Determine how many finite sequences $\left(a_{1}, a_{2}, \ldots, a_{t}\right)$ (where $t \in \mathbb{N}$ is not fixed in advance) exist that satisfy the following three conditions:

- $a_{1}, a_{2}, \ldots, a_{t} \in\{1,2, \ldots, n\}$
- for all $j, 1 \leqslant j \leqslant t-1$, $a_{j} \leqslant a_{j+1}+1$;
- there do not exist $j$ and $k, 1 \leqslant j \leqslant k \leqslant t-1$, such that $a_{k} \leqslant a_{j}=a_{k+1}$.
2. Answer: there are $(n+1)!-1$ such sequences.

We prove this by induction on $n$. For $n=1$, we have only one such sequence (a one-element sequence whose only element is 1). Now assume that the statement holds

![](https://cdn.mathpix.com/cropped/2024_06_04_adcebcbe7d41887b6eefg-55.jpg?height=344&width=394&top_left_y=191&top_left_x=1108)

Dr 20194 A 1 for $n-1$, and prove it for $n$.

Let $\left(a_{1}, a_{2}, \ldots, a_{t}\right)$ be one such sequence. By the problem's condition, each subsequent element is either not less than the previous one, or exactly 1 less. Divide the sequence into blocks of consecutive elements such that each block forms a decreasing sequence (and thus must consist of consecutive natural numbers) and that the blocks are as long as possible. We claim that the first element of each subsequent block is strictly greater than the first element of the previous block. Indeed, if this were not the case, then the first element of the subsequent block would also be in the previous block (since it would not be greater than the first element of the previous block, and due to the maximality of the blocks, it would not be less than the last element of the previous block, so the conclusion follows from the fact that the blocks are composed of consecutive numbers), leading to a contradiction with the third condition in the problem statement (where $k+1$ would be the position of the start of the subsequent block, and $k$ the position of the end of the previous block). Now let's count how many such sequences exist with elements from the set $\{1,2, \ldots, n\}$. If the element $n$ does not appear in them, there are, by the inductive hypothesis, $n!-1$ such sequences. If the element $n$ does appear, then it must be at the beginning of the last block, and that last block can be one of the following: $n, (n, n-1), (n, n-1, n-2), \ldots, (n, n-1, \ldots, 1)$, i.e., $n$ possibilities. If that block is the only one existing, it adds another $n$ desired sequences. If it is not, by removing that last block, we obtain one of the desired sequences with elements from the set $\{1,2, \ldots, n-1\}$, of which there are $n!-1$, and to each of these, we can append any of the $n$ mentioned blocks. Therefore, the final result is:

$$
(n!-1)+n+(n!-1) n=n!-1+n+n!\cdot n-n=n!(1+n)-1=(n+1)!-1
$$

which is what we needed to prove.