aula 02 Fatorial e Permutação

Prévia do material em texto

Fatotial e Permutação
Arlyson Nascimento
arlysonn@hotmail.com
Matemática Discreta
Sistemas de Informação
15 de agosto de 2019
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
arlysonn@hotmail.com
Motivação
Exemplo
De quantas maneiras seis membros da Equipe Olímpica de
Matemática do IFAL podem se organizar em uma sala de
computação com seis computadores?
Note que existem 6 possibilidades para escolhermos a pessoa que
utilizará o primeiro computador. Escolhida tal pessoa, há 5
possibilidades para aquela que ocupará o segundo computador.
Seguindo esse raciocínio, é muito simples perceber que, utilizando o
Princípio Multiplicativo, a resposta ao problema será:
6× 5× 4× 3× 2× 1 = 720.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Motivação
Exemplo
Imagine que o problema inicial se referisse a 100 funcionários do
Call Center de uma empresa que fossem fazer um treinamento em
uma sala com 100 computadores. Será que, para registrarmos a
solução, precisaríamos escrever o correspondente produto com cem
fatores?
Com certeza não precisaríamos escrever todos os cem fatores, por
exemplo, 100× 99× 98× · · · × 3× 2× 1. Explicitar produtos como
esse é algo desnecessário, já que o matemático francês Christian
Kramp decidiu adotar uma notação muito simples para produtos
desse tipo: ele decidiu representar o fatorial do número n por n!
(leia n fatorial).
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Fatorial
De uma maneira geral, se n é um inteiro não negativo, então
n! = n × (n − 1)× (n − 2)× · · · × 3× 2× 1.
Observe que 1! = 1 e, por definição, 0! = 1.
Agora que já estamos mais familiarizados com fatoriais, é hora de
introduzir o conceito de permutação simples. Em problemas de
combinatória, costuma-se indicar por permutações simples as
maneiras de se organizar n objetos distintos (pessoas, malas, livros,
etc.) em uma fila.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Permutação
Consideremos quatro objetos distintos a1, a2, a3 e a4. De quantas
maneiras podemos ordená-los? Vamos listar todas as possibilidades.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Permutação
Cada uma dessas ordenações é chamada uma permutação simples.
Podemos ver que o número de tais permutações é bem grande:
note que, para apenas 4 objetos, temos 24 permutações. O cálculo
do número de permutações é uma consequência direta do princípio
da multiplicação.
Consideremos, então, n objetos distintos a1, a2, . . . , an. Para a
primeira posição, temos n possibilidades. Para a segunda, escolhida
a primeira, sobram n − 1 objetos. Para a terceira, escolhidas a
primeira e a segunda posições, sobram n − 2 objetos. Continuando,
para a última posição, escolhidas as n − 1 anteriores, sobra apenas
1 objeto.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Permutação
Pelo princípio da multiplicação, o número total de permutações,
que denotaremos Pn, é n × (n − 1)× (n − 2)× · · · × 3× 2× 1, e
esse número, por definição, é o fatorial de n. Temos, assim, o
seguinte resultado.
Definição
Dados n objetos distintos, o número de permutações simples de
tais objetos é dado por Pn = n!.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Permutação
Exemplo
De quantos modos diferentes podemos dispor 5 pessoas em fila?
O primeiro lugar na fila pode ser ocupado por qualquer uma das 5
pessoas. O segundo lugar pode ser ocupado por qualquer uma das
4 pessoas restantes, e assim por diante. Portanto existem
P5 = 5! = 5× 4× 3× 2× 1 = 120 maneiras distintas para dispor
numa fila 5 pessoas.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
O que é um ANAGRAMA?
Anagrama é um substantivo que significa uma palavra ou frase
que é construída através da alteração das letras de uma outra
palavra ou frase.
Com origem no grego, o prefixo ana indica regressar ou repetir
e gramma significa palavra.
No âmbito da matemática, os anagramas estão relacionados
com a análise combinatória, e consistem na permutação das
letras de uma palavra.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Exemplo
Exemplo
A partir da palavra NÚMEROS (o acento sempre acompanhará a
letra U), responda:
(a) Quantos anagramas são possíveis de serem formados?
(b) Quantos anagramas têm como primeira letra uma vogal?
(c) Quantos anagramas começam e terminam em vogal?
(d) Quantos anagramas começam com N?
(e) Quantos anagramas são possíveis de serem formados com as
letras N e U juntas e nessa ordem?
(f) Quantos anagramas são possíveis de serem formados com as
letras U e N juntas?
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Exemplo
A partir da palavra NÚMEROS (o acento sempre acompanhará a
letra U), responda:
(a) Quantos anagramas são possíveis de serem formados?
A palavra NÚMEROS tem 7 letras, desse modo devemos formar
uma sequência com essas 7 letras, pode realizar esse processo de P7
maneiras distintas, que é igual a P7 = 7! anagramas distintos.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Exemplo
A partir da palavra NÚMEROS (o acento sempre acompanhará a
letra U), responda:
(b) Quantos anagramas têm como primeira letra uma vogal?
Nesse item devemos preencher sete posições com sete letras e
garantir que qualquer anagrama formado tenha uma vogal como
primeira letra.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Assim devemos começar pela primeira casa, onde há a restrição,
observe:
Desse modo nossa resposta será:
3× 6× 5× 4× 3× 2× 1 = 3× 6! = 3× P6 anagramas distintos.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Exemplo
A partir da palavra NÚMEROS (o acento sempre acompanhará a
letra U), responda:
(c) Quantos anagramas começam e terminam em vogal?
O raciocínio para resolver esse item é idêntico ao anterior, mas
nesse temos que garantir que a primeira e última casa contenham
vogais, assim primeiro preencheremos a primeira e última casa, em
seguida as demais, observe:
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Desse modo nossa resposta será:
3× 2× 5× 4× 3× 2× 1 = 3× 2× 5! = 6×P5 anagramas distintos.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Exemplo
A partir da palavra NÚMEROS (o acento sempre acompanhará a
letra U), responda:
(d) Quantos anagramas começam com N?
Devemos garantir que a primeira letra da palavra formada seja N,
assim primeiro preenchemos a primeira casa com o N e em seguida
as restantes com as seis que faltam, observe:
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Desse modo nossa resposta será:
1× 6× 5× 4× 3× 2× 1 = 6! = P6 anagramas distintos.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Exemplo
A partir da palavra NÚMEROS (o acento sempre acompanhará a
letra U), responda:
(e) Quantos anagramas são possíveis de serem formados com as
letras N e U juntas e nessa ordem?
Como as letras N e U devem aparecer juntas e nessa ordem,
trataremos de forma artificial as duas como uma só letra, assim NU
será uma única letra.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Já que a palavra NÚMEROS tem 7 letras com essa maquiagem
nas duas letras essa palavra passará a ter 6 letras e a quantidade de
anagramas de uma palavra de 6 letras é P6 = 6!.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Exemplo
A partir da palavra NÚMEROS (o acento sempre acompanhará a
letra U), responda:
(f) Quantos anagramas são possíveis de seremformados com as
letras U e N juntas?
Nesse item devemos proceder de forma idêntica ao anterior com a
diferença que agora U e N podem aparecer em qualquer ordem.
Assim primeiro contamos a quantidade de permutações com as 6
letras hipotéticas - temos 6! maneiras de fazer isso.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Resolução
Em seguida devemos ordenar U e N, podemos fazer isso de 2! = 2
maneiras diferentes, para finalizar devemos multiplicar os resultados
para obter:
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Exemplo
Exemplo
Uma biblioteca tem quatro livros sobre sistemas operacionais, sete
sobre programação e três sobre estrutura de dados. Vamos ver de
quantas maneiras esses livros podem ser arrumados em uma
prateleira, considerando que todos os livros de cada assunto
precisam estar juntos.
Podemos pensar neste problema como uma sequência de
subtarefas. Primeiro consideremos a subtarefa de arrumar os três
assuntos. Existem 3! maneiras de fazer isto, isto é, 3! maneiras de
ordenar os assuntos dos livros na prateleira.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com
Exemplo
As etapas seguintes são arranjar os livros sobre sistemas
operacionais (4! maneiras), arrumar os livros sobre programação (7!
maneiras) e, então, arrumar os livros sobre estrutura de dados (3!
maneiras).
Portanto, pelo Princípio da Multiplicação, o número final de
arranjos possíveis de todos os livros é
(3!)× (4!)× (7!)× (3!) = 4.354.560.
Arlyson Nascimento arlysonn@hotmail.com Fatotial e Permutação
arlysonn@hotmail.com