Nombre de permutacions emparellades P20410

Una permutació d’n elements {0,…,n−1} es diu emparellada si els elements a les posicions parells són tots parells o tots senars i, si els elements en posicions senars es troben en ordre creixent. Les posicions es comencen a comptar des de zero per l’esquerra.

Per exemple, aquestes són totes les permutacions emparellades per a n=5:

0 1 2 3 4
0 1 4 3 2
2 1 0 3 4
2 1 4 3 0
4 1 0 3 2
4 1 2 3 0

i aquestes són totes les permutacions emparellades per a n=6:

0 1 2 3 4 5
0 1 4 3 2 5
1 0 3 2 5 4
1 0 5 2 3 4
2 1 0 3 4 5
2 1 4 3 0 5
3 0 1 2 5 4
3 0 5 2 1 4
4 1 0 3 2 5
4 1 2 3 0 5
5 0 1 2 3 4
5 0 3 2 1 4

Feu un programa de generació exhaustiva que llegeixi una seqüència de nombre naturals n i que, per a cadascun d’ells, escrigui el nombre de permutacions emparellades d’n elements. Especifiqueu adientment el procediment recursiu.