Permutação Simples

Quantas são as permutações simples dos números 1,2,...,n nos quais o elemento que ocupa a k-ésima posição é maior que k-3, para todo k?
Gabarito: 2*3^{n-2}

Opa, bom dia! 

 Vamos montar o raciocínio devagarinho.

 O elemento que ocupa a Enésima posição, terá que ser maios que n-3. Pensando um pouco, verá que só tem 3 possibilidades pra isso, seria o n-2;n-1;n.
 Excelente, então temos 3 possibilidades pra colocar na enésima casa.
 Na n-1, o cenário muda um pouco; temos, pois, a seguinte relação: n-1 tem que ser maior que n-1-3=n-4. Usando raciocínio similar ao de cima, verá que temos 4 possibilidades: n-3;n-2;n-1;n. Mas um elemento foi utilizado pro enésimo elemento, logo, as possibilidades caem pra 3.
 Antes de generalizar, farei pra n-2: temos que n-2 tem que ser maior que n-2-3=n-5. isso nós dará 5 elementos(n-4;n-3;n-2;n-1;n). Porém dois já foram utilizados, logo, temos 3 possibilidades.

 OBS: Se a anotação tá estranha, tentarei simplificar aqui, como os números estão em ordem crescente, temos que o n é o maior de todos, Então pra ocupar a enésima posição, temos, por restrição, que o número seja maior que n-3 -Caso não houvesse essa restrição, qualquer número poderia entrar ali.- mas graças a ela, o nosso legue diminui pra 3, pois somente 3 números são maior que n-3(na ordem dada).

 Okay, agora vamos descer até a terceiro posição, temos que o número que ocupa lá tem que ser maior que 3-3=0. logo todos os números são possíveis, mas n-3 já foram usados, sobram, portanto, 3 elementos. 
 o da segunda posição, temos 2-3=-1. Mesma ideia, todos os números podem, mas só temos 2 para serem usados.
 primeira: 1-3=-2. temos somente um pra ser usado.

2.3^(n-2).

 Fiz essa questão pelo livro do morgado, muito bonita. Espero ter ajudado

Tua solução foi de uma beleza tão grandiosa. Somente quem é fascinado por esta ciência consegue ver. Parabéns! Belíssima solução!!!
Um grande abraço do professor Resende: https://twitter.com/resendeprof