5

Part of 2024 Cono Sur Olympiad

Problems(1)

Magical permututations!

Source: Cono Sur Olympiad 2024 P5

A permutation of

\{1, 2 \cdots, n \}

is magic if each element

k

of it has at least

\left\lfloor \frac{k}{2} \right\rfloor

numbers less to it at the left. For each

n

find the number of magical permutations.