Problema 9

Pentru mulțimea $\{1, 2, 3, \ldots, n\}$ se generează printr-un program toate permutările în care nu există numere vecine alăturate. Două numere $a$ și $b$ sunt vecine dacă $|a-b|=1$ (de exemplu 3 și 4 sunt vecine, 2 și 1 sunt vecine). Știind că pentru $n=5$ au fost generate 14 permutări distincte în care nu există numere vecine, câte permutări se vor genera pentru $n=6$?

a) 72; b) 56; c) 144; d) 90; e) 89; f) 120.