CONO-SUR 2024 Problem 5

Uma permutação de $\{1, 2, \ldots, n\}$ é mágica se cada termo $j$ dela tiver ao menos $\left\lfloor \frac{j}{2} \right\rfloor$ números menores que ele à sua esquerda.

Por exemplo: $(1, 3, 4, 2, 5)$ é mágica; $(1, 5, 2, 3, 4)$ não é mágica, já que o 5 não tem ao menos $\left\lfloor \frac{5}{2} \right\rfloor = 2$ números menores que ele à sua esquerda.

Para cada $n$ natural, determine o número de permutações mágicas de $\{1, 2, \ldots, n\}$.

Nota 1: $\lfloor x \rfloor$ denota o maior inteiro que é menor ou igual a $x$. Por exemplo, $\lfloor 3, 5 \rfloor = 3$ e $\lfloor 20 \rfloor = 20$.

Nota 2: uma permutação de $\{1, 2, \ldots, n\}$ é uma maneira de listar os elementos desse conjunto em uma certa ordem. Por exemplo, $(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)$ são todas as permutações do conjunto $\{1, 2, 3\}$.