Permutação simples

Quantas são as permutações simples dos números 1, 2, …, n nas quais o elemento que ocupa a k-ésima posição é inferior a K+4, para todo k?


Gabarito: 6.4^n-3

Primeiro uma pergunta boa. Digamos n = 6 (1, 2, 3, 4, 5, 6). Em que posição pode o n (6) ficar? 
Na 1 pode? Não, porque tenho de ter 6 < 1 + 4 = 5. Nem na 2, já que 6 não é menor que 6, só posso pôr a partir de 3 e acima. Se fosse n = 8, de 5 e acima, claro, porque n < k + 4 -> n - 4 < k -> k >= n - 3, logo há 4 possibilidades ao n: n, n-1, n-2 e n-3.
Ok, tudo muito bom, tudo muito bem, ponho lá o n em alguma dessas 4 posições. Agora o n-1. Analogamente, k >= (n-1)-3 = n-4, então eu teria a princípio 5 posições. Teria mesmo se o n não ocupasse uma delas rs. Eu liberei pra usar o n-4, mas consumi algum de n-3 acima, então pro n-1 eu TAMBÉM tenho 4 possibilidades.
De forma geral, eu vou repetir isso pra todos os números até chegar ao 4. Dele e abaixo, pode ficar em qualquer casa, mas só há 4 casas a posicionar, então são 4 novamente. Pro 3, restam três casas -> 3 opções. Pro 2, só duas e pro 1 só uma.
Conclusão: de 4 a n (n-3 números) há 4 opções, depois 3, 2 e 1 => S = 6 . 4^(n-3).