permutação caótica

Prévia do material em texto

Permutac¸a˜o Cao´tica (”Derangements”)
Considere o exemplo:
Determine o nu´mero de permutac¸o˜es simples dos elementos
distintos x1, x2, · · · , xn, nas quais x1 esta´ na primeira posic¸a˜o ou x2
esta´ na segunda posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento x1 estar na 1
a posic¸a˜o na
permutac¸a˜o.
1 / 12
Permutac¸a˜o Cao´tica (”Derangements”)
Considere o exemplo:
Determine o nu´mero de permutac¸o˜es simples dos elementos
distintos x1, x2, · · · , xn, nas quais x1 esta´ na primeira posic¸a˜o ou x2
esta´ na segunda posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento x1 estar na 1
a posic¸a˜o na
permutac¸a˜o.
◮ a2 : propriedade do elemento x2 estar na 2
a posic¸a˜o na
permutac¸a˜o.
1 / 12
Permutac¸a˜o Cao´tica (”Derangements”)
Considere o exemplo:
Determine o nu´mero de permutac¸o˜es simples dos elementos
distintos x1, x2, · · · , xn, nas quais x1 esta´ na primeira posic¸a˜o ou x2
esta´ na segunda posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento x1 estar na 1
a posic¸a˜o na
permutac¸a˜o.
◮ a2 : propriedade do elemento x2 estar na 2
a posic¸a˜o na
permutac¸a˜o.
◮ N(a1) = nu´mero de permutac¸o˜es de R = em que x1 esta´ na
1a posic¸a˜o.
1 / 12
Permutac¸a˜o Cao´tica (”Derangements”)
Considere o exemplo:
Determine o nu´mero de permutac¸o˜es simples dos elementos
distintos x1, x2, · · · , xn, nas quais x1 esta´ na primeira posic¸a˜o ou x2
esta´ na segunda posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento x1 estar na 1
a posic¸a˜o na
permutac¸a˜o.
◮ a2 : propriedade do elemento x2 estar na 2
a posic¸a˜o na
permutac¸a˜o.
◮ N(a1) = nu´mero de permutac¸o˜es de R = em que x1 esta´ na
1a posic¸a˜o.
◮ N(a2) = nu´mero de permutac¸o˜es de R = em que x2 esta´ na
2a posic¸a˜o.
1 / 12
continuac¸a˜o...
Procuramos N(a1 ∪ a2) = N(a1) + N(a2)− N(a1a2)
◮ N(a1) = N(a2) = (n − 1)!, pois fixamos um elemento e
permutamos os outros.
2 / 12
continuac¸a˜o...
Procuramos N(a1 ∪ a2) = N(a1) + N(a2)− N(a1a2)
◮ N(a1) = N(a2) = (n − 1)!, pois fixamos um elemento e
permutamos os outros.
◮ N(a1a2) = (n − 2)!, pois fixamos dois elementos e
permutamos os outros.
2 / 12
continuac¸a˜o...
Procuramos N(a1 ∪ a2) = N(a1) + N(a2)− N(a1a2)
◮ N(a1) = N(a2) = (n − 1)!, pois fixamos um elemento e
permutamos os outros.
◮ N(a1a2) = (n − 2)!, pois fixamos dois elementos e
permutamos os outros.
2 / 12
continuac¸a˜o...
Procuramos N(a1 ∪ a2) = N(a1) + N(a2)− N(a1a2)
◮ N(a1) = N(a2) = (n − 1)!, pois fixamos um elemento e
permutamos os outros.
◮ N(a1a2) = (n − 2)!, pois fixamos dois elementos e
permutamos os outros.
◮ Logo, N(a1 ∪ a2) = 2(n − 1)!− (n − 2)!
2 / 12
Exemplo 2
Dentre as permutac¸o˜es simples dos n elementos x1, x2, · · · , xn,
determine o nu´mero daquelas em que x1 na˜o esta´ na primeira
posic¸a˜o, x2 na˜o esta´ na segunda posic¸a˜o e nem x3 esta´ na terceira
posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento xi estar na i-e´sima posic¸a˜o na
permutac¸a˜o.
3 / 12
Exemplo 2
Dentre as permutac¸o˜es simples dos n elementos x1, x2, · · · , xn,
determine o nu´mero daquelas em que x1 na˜o esta´ na primeira
posic¸a˜o, x2 na˜o esta´ na segunda posic¸a˜o e nem x3 esta´ na terceira
posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento xi estar na i-e´sima posic¸a˜o na
permutac¸a˜o.
◮ Queremos calcular N(a1a2a3) =
N−N(a1)−N(a2)−N(a3)+N(a1a2)+N(a1a3)+N(a2a3)−N(a1a2a3)
3 / 12
Exemplo 2
Dentre as permutac¸o˜es simples dos n elementos x1, x2, · · · , xn,
determine o nu´mero daquelas em que x1 na˜o esta´ na primeira
posic¸a˜o, x2 na˜o esta´ na segunda posic¸a˜o e nem x3 esta´ na terceira
posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento xi estar na i-e´sima posic¸a˜o na
permutac¸a˜o.
◮ Queremos calcular N(a1a2a3) =
N−N(a1)−N(a2)−N(a3)+N(a1a2)+N(a1a3)+N(a2a3)−N(a1a2a3)
◮ N = |R| = Pn = n!.
3 / 12
Exemplo 2
Dentre as permutac¸o˜es simples dos n elementos x1, x2, · · · , xn,
determine o nu´mero daquelas em que x1 na˜o esta´ na primeira
posic¸a˜o, x2 na˜o esta´ na segunda posic¸a˜o e nem x3 esta´ na terceira
posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento xi estar na i-e´sima posic¸a˜o na
permutac¸a˜o.
◮ Queremos calcular N(a1a2a3) =
N−N(a1)−N(a2)−N(a3)+N(a1a2)+N(a1a3)+N(a2a3)−N(a1a2a3)
◮ N = |R| = Pn = n!.
◮ N(a1) = N(a2) = N(a3) = (n − 1)!
3 / 12
Exemplo 2
Dentre as permutac¸o˜es simples dos n elementos x1, x2, · · · , xn,
determine o nu´mero daquelas em que x1 na˜o esta´ na primeira
posic¸a˜o, x2 na˜o esta´ na segunda posic¸a˜o e nem x3 esta´ na terceira
posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento xi estar na i-e´sima posic¸a˜o na
permutac¸a˜o.
◮ Queremos calcular N(a1a2a3) =
N−N(a1)−N(a2)−N(a3)+N(a1a2)+N(a1a3)+N(a2a3)−N(a1a2a3)
◮ N = |R| = Pn = n!.
◮ N(a1) = N(a2) = N(a3) = (n − 1)!
◮ N(aiaj) = (n − 2)!
3 / 12
Exemplo 2
Dentre as permutac¸o˜es simples dos n elementos x1, x2, · · · , xn,
determine o nu´mero daquelas em que x1 na˜o esta´ na primeira
posic¸a˜o, x2 na˜o esta´ na segunda posic¸a˜o e nem x3 esta´ na terceira
posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento xi estar na i-e´sima posic¸a˜o na
permutac¸a˜o.
◮ Queremos calcular N(a1a2a3) =
N−N(a1)−N(a2)−N(a3)+N(a1a2)+N(a1a3)+N(a2a3)−N(a1a2a3)
◮ N = |R| = Pn = n!.
◮ N(a1) = N(a2) = N(a3) = (n − 1)!
◮ N(aiaj) = (n − 2)!
◮ N(aiajak) = (n − 3)!
3 / 12
Exemplo 2
Dentre as permutac¸o˜es simples dos n elementos x1, x2, · · · , xn,
determine o nu´mero daquelas em que x1 na˜o esta´ na primeira
posic¸a˜o, x2 na˜o esta´ na segunda posic¸a˜o e nem x3 esta´ na terceira
posic¸a˜o.
R = conjunto das permutac¸o˜es simples de x1, x2, · · · , xn.
◮ a1 : propriedade do elemento xi estar na i-e´sima posic¸a˜o na
permutac¸a˜o.
◮ Queremos calcular N(a1a2a3) =
N−N(a1)−N(a2)−N(a3)+N(a1a2)+N(a1a3)+N(a2a3)−N(a1a2a3)
◮ N = |R| = Pn = n!.
◮ N(a1) = N(a2) = N(a3) = (n − 1)!
◮ N(aiaj) = (n − 2)!
◮ N(aiajak) = (n − 3)!
◮ N(a1a2a3) = n!− C
1
3 (n − 1)! + C
2
3 (n − 2)!− C
3
3 (n − 3)! =
n!− 3(n − 1)! + 3(n − 2)!− (n − 3)!
3 / 12
Permutac¸a˜o Cao´tica
Definic¸a˜o Uma permutac¸a˜o de x1, x2, · · · , xn. e´ chamada de
cao´tica quando nenhum dos xi se encontra na posic¸a˜o original, isto
e´, na i-e´sima posic¸a˜o.
4 / 12
Permutac¸a˜o Cao´tica
Definic¸a˜o Uma permutac¸a˜o de x1, x2, · · · , xn. e´ chamada de
cao´tica quando nenhum dos xi se encontra na posic¸a˜o original, isto
e´, na i-e´sima posic¸a˜o.
◮ Exemplo: Tome os inteiros 1234
4 / 12
Permutac¸a˜o Cao´tica
Definic¸a˜o Uma permutac¸a˜o de x1, x2, · · · , xn. e´ chamada de
cao´tica quando nenhum dos xi se encontra na posic¸a˜o original, isto
e´, na i-e´sima posic¸a˜o.
◮ Exemplo: Tome os inteiros 1234
◮ 2143 e´ uma permutac¸a˜o cao´tica
4 / 12
Permutac¸a˜o Cao´tica
Definic¸a˜o Uma permutac¸a˜o de x1, x2, · · · , xn. e´ chamada de
cao´tica quando nenhum dos xi se encontra na posic¸a˜o original, isto
e´, na i-e´sima posic¸a˜o.
◮ Exemplo: Tome os inteiros 1234
◮ 2143 e´ uma permutac¸a˜o cao´tica
◮ 4321 e´ uma permutac¸a˜o cao´tica
4 / 12
Permutac¸a˜o Cao´tica
Definic¸a˜o Uma permutac¸a˜o de x1, x2, · · · , xn. e´ chamada de
cao´tica quando nenhum dos xi se encontra na posic¸a˜o original, isto
e´, na i-e´sima posic¸a˜o.
◮ Exemplo: Tome os inteiros1234
◮ 2143 e´ uma permutac¸a˜o cao´tica
◮ 4321 e´ uma permutac¸a˜o cao´tica
◮ 2431 na˜o e´ uma permutac¸a˜o cao´tica, pois o 3 esta´ no seu
lugar original.
4 / 12
Ca´lculo de Dn
Ca´lculo do nu´mero de permutac¸o˜es cao´ticas: seja R = conjunto
das permutac¸o˜es de x1, x2, · · · , xn. N = |R| = Pn = n!. Sejam
◮ ai : propriedade de xi estar no i-e´simo lugar nas permutac¸o˜es.
5 / 12
Ca´lculo de Dn
Ca´lculo do nu´mero de permutac¸o˜es cao´ticas: seja R = conjunto
das permutac¸o˜es de x1, x2, · · · , xn. N = |R| = Pn = n!. Sejam
◮ ai : propriedade de xi estar no i-e´simo lugar nas permutac¸o˜es.
◮ Para calcularmos o nu´mero de permutac¸o˜es cao´ticas,
denotado por Dn, devemos calcular o nu´mero de elementos
que na˜o satisfazem nenhum ai :
Dn = N(a1 · · · an) =
n!−
n∑
i=1
N(ai ) +
∑
1≤i≤j
N(aiaj) + · · ·+ (−1)
n
N(a1 · · · an)
5 / 12
Calculando Dn
◮ N(ai ) = (n − 1)!, no primeira somato´rio existem n = C
1
n
termos
6 / 12
Calculando Dn
◮ N(ai ) = (n − 1)!, no primeira somato´rio existem n = C
1
n
termos
◮ N(aiaj) = (n − 2)!, no segundo somato´rio existem C
2
n termos
6 / 12
Calculando Dn
◮ N(ai ) = (n − 1)!, no primeira somato´rio existem n = C
1
n
termos
◮ N(aiaj) = (n − 2)!, no segundo somato´rio existem C
2
n termos
◮ N(aiajak) = (n − 3)!, no terceiro somato´rio existem C
3
n
termos
6 / 12
Calculando Dn
◮ N(ai ) = (n − 1)!, no primeira somato´rio existem n = C
1
n
termos
◮ N(aiaj) = (n − 2)!, no segundo somato´rio existem C
2
n termos
◮ N(aiajak) = (n − 3)!, no terceiro somato´rio existem C
3
n
termos
◮ ...
6 / 12
Calculando Dn
◮ N(ai ) = (n − 1)!, no primeira somato´rio existem n = C
1
n
termos
◮ N(aiaj) = (n − 2)!, no segundo somato´rio existem C
2
n termos
◮ N(aiajak) = (n − 3)!, no terceiro somato´rio existem C
3
n
termos
◮ ...
◮ N(a1a2 · · · an) = 1, no n-e´simo somato´rio existem C
n
n = 1
termos
Como queremos calcular Dn = N(a1 · · · an), procedemos da
seguinte maneira:
6 / 12
Calculando Dn
Dn = N(a1 · · · an) = n!−C
1
n (n−1)!+C
2
n (n−1)!+· · ·+(−1)
n
C
n
n (n−1)!
Portanto,
Dn = n!−
n!
1!
+
n!
2!
+ · · · + (−1)n
n!
n!
Colocando n! em evideˆncia, temos:
Dn = n!
[
1−
1
1!
+
1
2!
+ · · ·+ (−1)n
1
n!
]
Obs.: A expressa˜o entre colchetes e´ a se´rie truncada da expansa˜o
de Taylor de e−1
7 / 12
Voltando ao exemplo 1
Calcular o nu´mero de permutac¸o˜es cao´ticas de 1234:
Soluc¸a˜o:
D4 = 4!
[
1−
1
1!
+
1
2!
−
1
3!
+
1
4!
]
= 9
8 / 12
Exemplo 2
Calcular o nu´mero de permutac¸o˜es cao´ticas de 3 elementos abc:
9 / 12
Exemplo 2
Calcular o nu´mero de permutac¸o˜es cao´ticas de 3 elementos abc:
◮ abc, acb, bac, cab, bca e cba
9 / 12
Exemplo 2
Calcular o nu´mero de permutac¸o˜es cao´ticas de 3 elementos abc:
◮ abc, acb, bac, cab, bca e cba
◮ Somente as sequeˆncias 4 e 5 na˜o possuem nenhum elemento
na posic¸a˜o original.
9 / 12
Exemplo 2
Calcular o nu´mero de permutac¸o˜es cao´ticas de 3 elementos abc:
◮ abc, acb, bac, cab, bca e cba
◮ Somente as sequeˆncias 4 e 5 na˜o possuem nenhum elemento
na posic¸a˜o original.
◮
D3 = 3!
[
1−
1
1!
+
1
2!
−
1
3!
]
= 2
9 / 12
Exemplo 4
Quantas permutac¸o˜es dos inteiros 1, 2, · · · , 9, 10 teˆm exatamente 4
dos nu´meros em suas posic¸o˜es originais?
Resposta:
10 / 12
Exemplo 4
Quantas permutac¸o˜es dos inteiros 1, 2, · · · , 9, 10 teˆm exatamente 4
dos nu´meros em suas posic¸o˜es originais?
Resposta:
◮ C 410 = nu´mero de maneiras de escolher os 4 nu´meros entre os
10 para ocuparem suas posic¸o˜es originais.
10 / 12
Exemplo 4
Quantas permutac¸o˜es dos inteiros 1, 2, · · · , 9, 10 teˆm exatamente 4
dos nu´meros em suas posic¸o˜es originais?
Resposta:
◮ C 410 = nu´mero de maneiras de escolher os 4 nu´meros entre os
10 para ocuparem suas posic¸o˜es originais.
◮ D6 = nu´mero de permutac¸o˜es cao´ticas dos 6 elementos
restantes.
10 / 12
Exemplo 4
Quantas permutac¸o˜es dos inteiros 1, 2, · · · , 9, 10 teˆm exatamente 4
dos nu´meros em suas posic¸o˜es originais?
Resposta:
◮ C 410 = nu´mero de maneiras de escolher os 4 nu´meros entre os
10 para ocuparem suas posic¸o˜es originais.
◮ D6 = nu´mero de permutac¸o˜es cao´ticas dos 6 elementos
restantes.
◮ Pelo princ´ıpio multiplicativo:
C
4
10×D6 =
10!
6!4!
·6!
[
1−
1
1!
+
1
2!
−
1
3!
+
1
4!
−
1
5!
+
1
6!
]
= 55.650
10 / 12
Exemplo 5
Ache o nu´mero de permutac¸o˜es cao´ticas dos inteiros de 1 a 10
inclusive, satisfazendo a condic¸a˜o de que o conjunto de elementos
nos 5 primeiros lugares e´:
11 / 12
Exemplo 5
Ache o nu´mero de permutac¸o˜es cao´ticas dos inteiros de 1 a 10
inclusive, satisfazendo a condic¸a˜o de que o conjunto de elementos
nos 5 primeiros lugares e´:
◮ 1, 2, 3, 4, 5 em alguma ordem.
Resposta: D5 × D5
11 / 12
Exemplo 5
Ache o nu´mero de permutac¸o˜es cao´ticas dos inteiros de 1 a 10
inclusive, satisfazendo a condic¸a˜o de que o conjunto de elementos
nos 5 primeiros lugares e´:
◮ 1, 2, 3, 4, 5 em alguma ordem.
Resposta: D5 × D5
◮ 6, 7, 8, 9, 10
Resposta: P5 × P5, pois eles na˜o ocupara˜o seus lugares
primitivos em hipo´tese alguma.
11 / 12
Exemplo 6
Sa˜o distribu´ıdos n livros para n estudantes. Suponha que os livros
sa˜o devolvidos e redistribu´ıdos no dia seguinte para os estudantes.
De quantas maneiras os livros podem ser distribu´ıdos de maneira
que nenhum estudante receba o mesmo livro 2 vezes?
12 / 12
Exemplo 6
Sa˜o distribu´ıdos n livros para n estudantes. Suponha que os livros
sa˜o devolvidos e redistribu´ıdos no dia seguinte para os estudantes.
De quantas maneiras os livros podem ser distribu´ıdos de maneira
que nenhum estudante receba o mesmo livro 2 vezes?
◮ A primeira vez, os livros podem ser distribu´ıdos de n!
maneiras.
12 / 12
Exemplo 6
Sa˜o distribu´ıdos n livros para n estudantes. Suponha que os livros
sa˜o devolvidos e redistribu´ıdos no dia seguinte para os estudantes.
De quantas maneiras os livros podem ser distribu´ıdos de maneira
que nenhum estudante receba o mesmo livro 2 vezes?
◮ A primeira vez, os livros podem ser distribu´ıdos de n!
maneiras.
◮ A segunda vez pode ser feita Dn maneiras.
Resposta: Pelo princ´ıpio multiplicativo: n!× Dn
12 / 12