Recorrência

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

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: