Seja Dn o número permutações caóticas de 1,2,3,….,n, isto é, o número de permutações simples de 1,2,3…,n, nas quais nenhum elemento ocupa seu lugar primitivo. Mostre que, se n => 1, então:
Dn+2 = (n + 1)(Dn+1 + Dn)
Primeiramente vamos ver do que se trata essas permutações caóticas.aso pequeno para uma sequencia de quatro termos {1,2,3,4} teremos as permutações:
{2,1,4,3} {3,4,1,2} {4,3,2,1} {2,4,1,3}{2,3,4,1}….
Vamos separar em casos, o primeiro deles será quando 1 troca de lugar com o número que oculpa a primeira posição.
As permutações de Dn+2 serão em relação á sequencia 1,2,3,….,n+2 e para o caso em que o 1 troca de lugar com o número que ocupa a primeira posição teremos n + 1 modos de escolher os números para trocar com ele.
Voltando no exemplo acima {1,2,3,4} teremos ai uma sequencia que tem n + 2 termos, sendo n = 2, então teremos n + 1 modos de trocar o 1 pelo número que ocupa a primeira casa, Let us try do that:
{2,1,4,3} {3,4,1,2} {4,3,2,1} <– done 🙂
Porque podemos afirmar que não tem como ter outro? Obviamente, porque só existem 3 termos, nesse caso, diferentes de 1, então só poderiamos formar 3 permutações.
Generalizando, em Dn+2 temos n + 1 modos de escolher com quem o 1 trocará, porém ainda restam n lugares, e devemos ter que esses n números não sentem em seus lugares primitivos, ou seja para o primeiro grupo teremos (n + 1).Dn permutações.
Para o segundo caso, em que o 1 não troca de lugar com o número que ocupa a primeira posição teremos que escolher um lugar pra ele, que pode ser feito de n + 1 modos, correto? Seila, vamos ver se é!!
{1,2,3,4} teoricamente o 1 tem n + 1 lugares ou seja 3 locais. Considerando está sequencia formada por n + 2 números.
{2,4,1,3}{4,1,2,3}{3,1,4,2}
Os outros termos, n + 1 , devem ser permutados de modo a não coincidir com as posições primitivas, então temos Dn+1.
Com isso o segundo grupo fica descrito como (n + 1)(Dn+1) permutações.
Portanto,
Dn+2 = (n + 1)Dn + (n + 1)Dn+1
Dn+2 = (n + 1)(Dn + Dn+1)
c.q.d
_______________________________________________________________________________________________________________________________-
Resolvendo algumas recorrência lineares homogenas:
Resolva xn+1 = nxn sabendo que x1 = 1
x2 = 1×1
x3 = 2×2
x4 = 3×3
x5 = 4×4
x6 = 5×5
x7 = 6×6
..
xn = (n – 1)xn-1
Multiplicando tudo teremos:
x2.x3.x4.x5……xn-1. xn = 1×1.2×2.3×3.4×4……….(n – 1)xn-1
cancelando:
xn = 1.2.3.4.5.6……(n – 1)
xn = (n – 1)!
Resolva xn+1 = 2xn
x2 = 2×1
x3= 2×2
x4 = 2×3
..
xn = 2xn-1
Multiplicando os 2 lados:
x2.x3.x4.x5.x6……xn-1 . xn = 2×1 . 2×2. 2×3 . 2×4………2xn-1
cancelando:
xn = 2.×12.2.2.2.2.2.2.2…….2
xn = 2^(n – 1)x1
Ciências Exatas 