Kavics Kupa 2013 10. feladat
(Feladat azonosítója: kk_2013_10f )
Témakör: *Algebra (permutáció, rekurzív sorozat)

Az  $ 1, 2, \ldots , 16$  számoknak, hány olyan  $i_1, i_2, \ldots , i_k$  permutációja van, amelyben minden  $ 1\leq k\leq 16$  mellett teljesül az  $|i_k-k|\leq 1$  feltétel?



 

Végeredmény: 1597

 

Ha a kérdezett permutációk száma az  $ 1$  -től  $ 16$  terjedő számok helyett az  $ 1$  -től  $n$  -ig terjedő számokra  $p_n$  , akkor  $p_1=1$  ,  $p_2=2$  és  $p_{n+2}=p_{n+1}+p_n$  , így  $p_{16}=1597$  .