Q37 Matemática  (Tournament Of Towns 1988)

Os inteiros $1,2,...,n$ são rearranjados de tal forma que se o inteiro $k,1\le k\le n$, não for o primeiro termo, então um dos inteiros $k+1$ ou $k-1$ ocorre à esquerda de $k$ . Quantos arranjos dos inteiros $1,2,...,n$ satisfazem esta condição? (A. Andjans, Riga)