Fatorial e permutação
Definições especiais
0! = 1 e 1! = 1
Esta é a expressão para n!(lê-se: n fatorial ou fatorial de n). É sempre o produto de todos os seus antecessores, incluindo ele próprio e excluindo o zero. n ∈ N e n > 1.
Exemplo 1
Calcule:
a) 4!
b) 7!
c) 8! – 5!
De acordo com a fórmula n! = n(n-1)(n-2) … 3 • 2 • 1, temos:
a) 4! = 4 • 3 • 2 • 1 = 24
b) 7! = 7 • 6 • 5 • 4 • 3 • 2 • 1 = 5.040
c) 8! – 5! = (8 • 7 • 6 • 5 • 4 • 3 • 2 • 1) – (5 • 4 • 3 • 2 • 1) = 40.320 – 120 = 40.200
Outra forma de solução seria:
8 • 7 • 6 • 5! – 5!
5!(8 • 7 • 6 – 1) = 5! • 335 = 120 • 335 = 40.200
Exemplo 2
Simplifique:
| a) |
|
| b) |
|
| a) |
|
= |
|
= n |
| b) |
|
|
|
|
(n + 2) + 1 = n + 3
Permutação
Em análise combinatória, permutações são arranjos ordenados de um conjunto finito de elementos. Uma permutação é uma disposição dos elementos de tal forma que a ordem em que esses elementos aparecem é importante. Em outras palavras, duas permutações são diferentes se a ordem dos elementos for diferente, mesmo que os elementos em si sejam os mesmos.
O número de permutações de um conjunto de elementos é frequentemente denotado por Pn e pode ser calculado usando a fórmula:
Você já conhece n!. n! = n(n-1)(n-2) … 3 • 2 • 1.
Exemplo 1
Em uma cesta, há 3 frutas: um mamão, uma laranja e um abacate. A primeira fruta que eu retirar da cesta será consumida imediatamente; a segunda será guardada dentro da bolsa para o lanche; e a terceira será colocada na geladeira. Quantas são as possibilidades de solução?
Veja que uma das soluções pode ser:
{mamão, laranja, abacate}
mamão – consumido imediatamente
laranja – guardada na bolsa
abacate – colocado na geladeira
A solução é encontrar todos os agrupamentos possíveis.
1ª posição → 3 (temos três opções)
2ª posição → 2 (temos duas opções, uma vez que uma fruta já foi escolhida para a primeira posição)
3ª posição → 1 (temos uma opção, uma vez que as etapas anteriores já foram preenchidas)
Portanto, chegamos a P3 = 3! = 3 • 2 • 1 = 6.
No total, temos 6 possibilidades ou agrupamentos.
Exemplo 2
Considere os números obtidos do número 12.345, efetuando-se todas as permutações de seus algarismos. Colocando esses números em ordem crescente, qual o lugar ocupado pelo número 43.521?
Esse problema exige um pouco mais de atenção e raciocínio.
| n! | Permutações | |||||
|---|---|---|---|---|---|---|
| 4! = 24 |
|
|||||
| 4! = 24 |
|
|||||
| 4! = 24 |
|
|||||
| 3! = 6 |
|
|||||
| 3! = 6 |
|
|||||
| 2! = 2 |
|
|||||
| 2! = 2 |
|
|||||
| 1! = 1 |
|
|||||
| 1 |
|
No total, temos 24 + 24 + 24 + 6 + 6 + 2 + 2 + 1 + 1 = 90. Logo, o número 43.521 ocupa a 90ª posição.
Em problemas envolvendo permutações, encontramos, na maioria das vezes, o termo anagrama. O que significa esta palavra? Anagrama é o resultado do rearranjo das letras de uma palavra com a finalidade de formar novas palavras, fazendo ou não sentido. Veja, por exemplo, que as palavras PEDRO e DEPOR são anagramas obtidos da palavra PODER. Isso foi feito simplesmente trocando a ordem das letras.
Exemplo 1
Quantos são os anagramas das palavras:
a) CAFÉ
b) BRASIL
a) A palavra CAFÉ possui 4 letras. De quantas maneiras podemos rearranjar as letras desta palavra e formar novas palavras, ainda que sem sentido?
P4 = 4! = 4 • 3 • 2 • 1 = 24
Portanto, é possível formar 24 anagramas com a palavra CAFÉ. Veja alguns exemplos: ACEF, CEFA, EFAC e muitas outras.
b) Seguindo o mesmo raciocínio do exercício anterior, temos:
P6 = 6! = 720
A palavra Brasil é formada por 6 letras; logo, são possíveis 720 anagramas.
Exemplo 2
Quantos anagramas da palavra PROBLEMA:
a) Começam por R?
b) Começam por P e terminam por M?
c) Começam por vogal?
d) Terminam por consoante?
a) A palavra PROBLEMA é composta por 8 letras. Logo, se quiséssemos saber quantos anagramas poderíamos formar com essas 8 letras, seria só encontrar o resultado de P8. Porém, nesta situação, o que se pede é quantos anagramas começam pela letra R. Veja abaixo que fixamos a letra R no início. Com a letra R fixada, todas as demais letras podem ser permutadas. Portanto, temos que permutar 7 letras. Então, temos:
P7 = 7! = 5.040
| R |
b) Nesta situação, temos duas posições fixadas; o início e o fim. Já que estas posições não irão permutar, restam apenas 6 letras para serem rearranjadas. Portanto, temos:
P6 = 6! = 720
| P | M |
c) Note que, para a primeira posição, podemos ter 3 opções: A, E ou O. As demais posições podem permutar sem problemas. Portanto, temos:
3 • P7 = 3 • 7! = 3 • 5.040 = 15.120
| A |
d) Note que, para a última posição, podemos ter 5 opções: P, R, B, L ou M. As demais posições podem permutar sem problemas. Portanto, temos:
5 • P7 = 5 • 7! = 5 • 5.040 = 25.200
| M |
Permutação com elementos repetidos
Vimos anteriormente que a permutação de 4, 5 ou n elementos distintos é dada por P4 = 4!, P5= 5! ou Pn = n!. Assim, o número de anagramas que podem ser formados a partir de CAFÉ e PODER são respectivamente, 24 e 120.
Considere agora a palavra BALA. Ao montar seus anagramas, percebemos que são 12 e não 24. Isso ocorre devido ao fato de que a letra A aparece repetida.
| Pn | = |
|
Os n1!n2! … nr! referem-se às letras que aparecem repetidas na palavra.
Exemplo 1
Determine o número de anagramas formados a partir de:
a) CORRER
b) TERRITÓRIO
c) ASSISTENTE
a) Na palavra CORRER, a letra R aparece 3 vezes.
| P6 | = |
|
| P6 | = |
|
= 120 |
b) Na palavra TERRITÓRIO, a letra T aparece 2 vezes, a letra R 3 vezes, a letra I 2 vezes e a letra O aparece 2 vezes.
| P10 | = |
|
= 75.600 |
c) Na palavra ASSISTENTE, a letra S aparece 3 vezes, a letra T 2 vezes e a letra E aparece 2 vezes.
| P10 | = |
|
= 151.200 |
Exemplo 2
Uma moeda é lançada 5 vezes. De quantos modos distintos podem ser obtidas 2 caras e 3 coroas?
Veja abaixo duas possíveis opções.
| K | C | K | C | C |
| C | C | C | K | K |
Das 5 posições, K aparece 2 vezes e C aparece 3 vezes.
| P5 | = |
|
= 10 |
Permutação circular
Para entendermos o conceito de permutação circular vamos imaginar a seguinte situação: de quantas formas distintas André, Bruno, Carlos e Daniel podem se sentar em volta de uma mesa circular?
Veja no desenho, que representamos uma das formas. Note que Daniel está à direita de André, Bruno está à esquerda e Carlos à sua frente. Perceba que, se girarmos suas posições, ainda assim a disposição deles na mesa permanecerá a mesma. Visto que o giro nas posições não conta como permutação, vamos fixar André e permutar os demais. Fixando André, teremos três pessoas para permutarmos; portanto, teremos P3 = 3! = 6. Outro método seria Pc,4 = 4! ÷ 4 (representa os 4 giros que podem ser realizados, mas que contam apenas como 1 permutação.).
| Pc,n | = |
|
= (n – 1)! |
Exemplo 1
Uma família é composta por seis pessoas: pai, mãe e quatro filhos. Num restaurante, essa família vai ocupar uma mesa redonda. Em quantas disposições diferentes essas pessoas podem se sentar em torno da mesa de modo que o pai e a mãe fiquem juntos?
No desenho acima, temos representada uma das posições. Note que temos 6 pessoas na mesa; porém, foi-nos dito que o pai e a mãe devem estar sempre juntos. Portanto, vamos tratar esses dois elementos como se fossem apenas um. Logo, teremos 5 elementos.
Usando a fórmula da permutação circular, temos:
| Pc,n | = |
|
= (n – 1)! |
Pc,5 = (5 – 1)! = 4! = 24
O pai e a mãe podem trocar de lugar entre si; portanto, temos P2 = 2! = 2.
Dessa forma, temos 2 • 24 = 48 maneiras.
Exemplo 2
Oito crianças formarão uma roda, entre elas Luiz e Júlia. De quantos modos diferentes poderá ser formada essa roda, sendo que Luiz e Júlia nunca poderão ficar juntos?
Vamos montar o esquema:
k = total de maneiras distintas de se formar uma roda com 8 crianças.
y = total de maneiras distintas de se formar uma roda em que Luiz e Júlia estão juntos.
w = total de maneiras distintas de se formar uma roda em que Luiz e Júlia NÃO estão juntos.
Podemos notar que w = k – y.
w = Pc,8 – (P2 • Pc,7)
w = (8 – 1)! – 2!(7 – 1)!
w = 7! – 2!6!
w = 5.040 – 2 • 720 = 3.600
Princípio de Dirichlet
O Princípio de Dirichlet, também conhecido como o Princípio das Gavetas de Dirichlet ou Princípio da caixa de pombos, é um conceito fundamental da teoria dos números e da teoria dos conjuntos. Foi nomeado em homenagem ao matemático alemão Johann Peter Gustav Lejeune Dirichlet, que contribuiu significativamente para a teoria dos números no século XIX.
O princípio pode ser enunciado da seguinte forma:
“Dada uma coleção finita de gavetas (ou caixas) e um número finito de pombos, se cada pombo for colocado em uma das gavetas, com mais pombos do que gavetas, então pelo menos uma gaveta conterá pelo menos dois pombos.”
Em outras palavras, se você tem um número limitado de recursos (as gavetas) e mais elementos para distribuir (os pombos) do que recursos disponíveis, pelo menos um dos recursos terá que acomodar mais de um elemento. Isso é uma consequência simples da contagem e da natureza finita das gavetas e dos pombos.
O Princípio de Dirichlet tem aplicações em várias áreas da matemática, da teoria dos números à teoria dos grafos, à análise combinatória e até mesmo à ciência da computação. É frequentemente usado para provar resultados relacionados à existência de soluções em problemas matemáticos e para mostrar que, em situações específicas, é impossível evitar a repetição ou a sobreposição de elementos.
Exemplo 1
Qual é o número mínimo de pessoas que deve haver em um grupo para que se possa garantir que, nesse grupo, existam pelo menos 5 pessoas nascidas no mesmo mês?
Para garantirmos que, no mínimo, 2 nasceram no mesmo mês, precisamos de 13 pessoas (exatamente 12 + 1). Para asseguramos que, pelo menos 3, nasceram no mesmo mês, precisamos de 25 pessoas (exatamente 2 x 12 + 1). Então, podemos inferir que para 5 pessoas no mesmo mês, temos: 4×12+1 = 49 pessoas.
Logo pra n pessoas, teremos (n-1) x 12 + 1
Exemplo 2
Uma caixa contém 100 bolas de cores distintas. Destas, 30 são vermelhas, 30 são verdes, 30 são azuis e 10 são pretas. Qual o menor número de bolas que devemos tirar da caixa, sem ver suas cores, para termos a certeza de que a caixa contém, pelo menos, 10 bolas da mesma cor?
Se tirarmos 5 bolas, pelos menos 2 terão a mesma cor, não? Claro que sim. E se tirarmos 9 bolas? Pelo menos 3 terão a mesma cor. Vamos fazer uma generalização? 5 = 4 x 1 + 1, 9 = 4 x 2 +1.
Então, para pelo menos n bolas, teremos: 4x (n-1)+1. Portanto, se estamos pedindo pelo menos 10, teremos como resposta: 4 x(10-1)+1=37 bolas.
O número 4 está relacionado às 4 categorias de cores. Se fossem 5 cores a fórmula geral seria 5 x (10 – 1) + 1 = 46.
Exemplo 3
Célia guarda suas blusas, em uma única gaveta, em seu quarto. Nela encontram-se 7 blusas azuis, 9 amarelas, 1 preta, 3 verdes e 3 vermelhas. Uma noite, no escuro, Célia abre a gaveta e pega algumas blusas. Qual o número mínimo de blusas que ela deve pegar para ter a certeza de ter, dentre as blusas, 2 da mesma cor?
Como são 5 opções de cores, teremos:
5 x (2 – 1) + 1 = 6 blusas
Exemplo 4
(RACIOCÍNIO LÓGICO E ESTATÍSTICA_SEPLAG – 2010) Em uma caixa há 12 bolas de mesmo tamanho: 3 brancas, 4 vermelhas e 5 pretas. Uma pessoa, no escuro, deve retirar n bolas da caixa e ter a certeza de que, entre elas, existem três da mesma cor. Qual deve ser o menor valor de n?
Dados do problema:
– Há 12 bolas na caixa
– Existem 3 categorias de cores: branca, vermelha e pretas
– Deseja-se saber qual o menor número de bolas que devem ser retiradas da caixa para se ter certeza de que foram retiradas 3 bolas da mesma cor.
3 x (3 – 1) + 1 = 7
Exemplo 5
Numa gaveta de meias pretas e marrons, há 4 pares de meia preta e 5 pares de marrons, todas misturadas. Quantas peças devo retirar para ter certeza que formei um par, sabendo-se que não consigo vê-las antes de retirá-las.
Dados do problema:
– 4 pares de meias pretas = 4 x 2 → 8 meias pretas
– 5 pares de meias marrons = 5 x 2 → 10 meias marrons
– 2 categorias de cor: preta e marrom
– Deseja-se saber quantas meias devem ser retiradas para se ter certeza de que foi formado um par.
2 x (2 -1) + 1 = 3
Exemplo 6
Uma empresa de desenvolvimento de sistemas é composta dos seguintes profissionais: 3 gerentes de projeto, 5 analistas de negócio e 7 especialistas em desenvolvimento web. Quantos profissionais, no mínimo, devemos escolher para termos certeza de que retiramos dois da mesma função?
Dados do problema:
– 3 categorias
– Deseja-se 2 da mesma função
3 x (2 – 1) + 1 = 4
Devemos escolher no mínimo 4 profissionais
Exemplo 7
Uma investigação da Polícia Federal é formada por 9 agentes da superintendência regional de Espirito Santo, 8 da regional de São Paulo, 12 da regional do Rio de janeiro e 5 da regional de Bahia. Quantos agentes, no mínimo, devemos escolher para termos certeza de que retiramos dois da mesma regional?
Dados do problema:
– 4 categorias
– Deseja-se 2 da mesma regional
4 x (2 – 1) + 1 = 5
Devemos escolher no mínimo 5 agentes