Permutações
De quantas formas 8 corredores podem cruzar a linha de chegada? Quantas senhas diferentes você consegue formar com 7 dígitos sem repetir nenhum? São perguntas de contagem: queremos saber quantas são as possibilidades sem precisar escrever a lista inteira. Vamos aprender a contar ordenações, a técnica mais básica da combinatória.
Contar com o princípio multiplicativo
Imagine que você vai sentar 3 amigos (Ana, Bruno e Carla) em 3 cadeiras enfileiradas. Para a primeira cadeira, há 3 opções. Escolhida essa pessoa, para a segunda cadeira sobram 2. Para a terceira, sobra apenas 1.
Cada caminho da árvore é uma forma diferente de sentá-los. Há $3 \cdot 2 \cdot 1 = 6$ caminhos da raiz até uma folha: 6 ordenações possíveis.
Note que, ao escolher uma pessoa para uma cadeira, ela deixa de estar disponível para as seguintes: o número de opções diminui de um em um. É isso que caracteriza uma permutação.
Um locutor de rádio local deve programar exatamente $5$ músicas diferentes durante a próxima hora de transmissão. De quantas formas ele pode estabelecer a ordem em que…
Um locutor de rádio local deve programar exatamente $5$ músicas diferentes durante a próxima hora de transmissão. De quantas formas ele pode estabelecer a ordem em que as músicas tocarão?
Permutações de n elementos distintos
Seguindo o mesmo raciocínio da árvore, mas com $n$ elementos: para o primeiro lugar há $n$ opções, para o segundo $n-1$, para o terceiro $n-2$, e assim por diante, até sobrar apenas $1$ opção para o último lugar.
$$P_n = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$$Esse produto é chamado de fatorial de $n$ e se escreve $n!$. Assim, $P_n = n!$. Você vai estudar o fatorial com detalhes no próximo apartado; por ora, basta saber que ele se calcula multiplicando todos os números naturais de $n$ até $1$.
Com $P_n = n!$, o mesmo vale: $P_n = n \cdot (n-1) \cdot P_{n-2}$, e o fatorial menor se cancela.
Em uma competição de atletismo participam $8$ corredores na final dos $100$ metros rasos. Assumindo que não pode haver empates, de quantas formas distintas eles podem…
Em uma competição de atletismo participam $8$ corredores na final dos $100$ metros rasos. Assumindo que não pode haver empates, de quantas formas distintas eles podem chegar à linha de chegada e se classificar?
Em uma galeria de arte contemporânea serão expostos em linha $6$ quadros de um mesmo pintor ao longo de uma parede. De quantas formas diferentes as obras podem ser…
Em uma galeria de arte contemporânea serão expostos em linha $6$ quadros de um mesmo pintor ao longo de uma parede. De quantas formas diferentes as obras podem ser ordenadas visualmente?
Às vezes convém fixar uma posição antes de contar as demais. Se uma senha com os dígitos de 1 a 7, sem repetir, deve começar sempre por 7, esse primeiro dígito já está decidido: restam 6 dígitos para ordenar nas 6 posições restantes, ou seja, $P_6 = 6! = 720$ senhas.
Uma senha de segurança é formada pelos dígitos $1, 2, 3, 4, 5, 6$ e $7$, sem repetir nenhum deles. Se a senha deve começar obrigatoriamente pelo dígito $7$, quantas…
Uma senha de segurança é formada pelos dígitos $1, 2, 3, 4, 5, 6$ e $7$, sem repetir nenhum deles. Se a senha deve começar obrigatoriamente pelo dígito $7$, quantas senhas distintas podem ser configuradas no sistema?
Simplifique a seguinte expressão com fatoriais sem usar calculadora: $\frac{12! \cdot 5!}{10! \cdot 7!}$.
Simplifique a seguinte expressão com fatoriais sem usar calculadora: $\frac{12! \cdot 5!}{10! \cdot 7!}$.
Outra estratégia útil é tratar um grupo que deve ficar junto como se fosse um único "bloco". Primeiro ordenamos os blocos; depois, ordenamos as pessoas dentro de cada bloco, e multiplicamos.
Quatro amigos e três amigas vão ao cinema e compram ingressos para sete poltronas consecutivas na mesma fileira. De quantas formas eles podem se sentar se os quatro…
Quatro amigos e três amigas vão ao cinema e compram ingressos para sete poltronas consecutivas na mesma fileira. De quantas formas eles podem se sentar se os quatro meninos querem ficar juntos e as três garotas também querem ficar juntas?
Em uma prateleira da biblioteca serão colocados $4$ livros de Matemática, $3$ de Física e $2$ de Biologia. De quantas formas eles podem ser ordenados se os livros de…
Em uma prateleira da biblioteca serão colocados $4$ livros de Matemática, $3$ de Física e $2$ de Biologia. De quantas formas eles podem ser ordenados se os livros de cada matéria devem ficar obrigatoriamente agrupados entre si?
Em uma urna há $4$ bolas vermelhas, $3$ bolas verdes e $2$ bolas azuis. Retiram-se todas as bolas uma a uma e elas são alinhadas sobre uma mesa. De quantas formas…
Em uma urna há $4$ bolas vermelhas, $3$ bolas verdes e $2$ bolas azuis. Retiram-se todas as bolas uma a uma e elas são alinhadas sobre uma mesa. De quantas formas distintas podem ficar alinhadas se as duas bolas azuis não puderem estar em posições adjacentes?
Permutações com elementos repetidos
Quantas palavras diferentes (anagramas) se formam trocando a ordem das letras de $SOL$? As três letras são distintas, então é $P_3 = 3! = 6$: SOL, SLO, OSL, OLS, LSO, LOS.
E com as letras de $ANA$? Aqui a letra $A$ aparece duas vezes. Se você tratasse os dois "A" como distintos ($A_1$ e $A_2$), teria $3! = 6$ ordenações, mas elas se repetem aos pares: $A_1NA_2$ e $A_2NA_1$ são, na leitura, a mesma palavra ANA.
Calcule quantas palavras distintas, tenham ou não sentido em português, podem ser formadas ordenando todas as letras da palavra $BIOLOGIA$.
Calcule quantas palavras distintas, tenham ou não sentido em português, podem ser formadas ordenando todas as letras da palavra $BIOLOGIA$.
No mastro de um barco a vela deseja-se hastear $7$ bandeiras para transmitir um sinal à costa. Dispõe-se de $3$ bandeiras vermelhas, $2$ azuis e $2$ amarelas, todas do…
No mastro de um barco a vela deseja-se hastear $7$ bandeiras para transmitir um sinal à costa. Dispõe-se de $3$ bandeiras vermelhas, $2$ azuis e $2$ amarelas, todas do mesmo tamanho. Quantos sinais diferentes podem ser enviados combinando todas as bandeiras?
Um hospital deve organizar os turnos de plantão de uma médica durante uma semana completa ($7$ dias). Devem ser atribuídos a ela exatamente $3$ turnos da manhã, $2$…
Um hospital deve organizar os turnos de plantão de uma médica durante uma semana completa ($7$ dias). Devem ser atribuídos a ela exatamente $3$ turnos da manhã, $2$ turnos da tarde e $2$ dias de folga. De quantas maneiras diferentes se pode planejar o horário semanal dela?
Quantos anagramas (tenham ou não sentido) podem ser formados com todas as letras da palavra $PARALELOGRAMO$ nos quais as três letras $A$ apareçam de forma consecutiva…
Quantos anagramas (tenham ou não sentido) podem ser formados com todas as letras da palavra $PARALELOGRAMO$ nos quais as três letras $A$ apareçam de forma consecutiva formando um único bloco?
Caminhos em uma malha
Um caminho na malha só com passos para a direita (D) e para cima (C) é uma sequência de letras. Com 5 passos D e 4 passos C, cada caminho é um anagrama de DDDDDCCCC. Logo, o número de caminhos é $\frac{9!}{5! \cdot 4!} = 126$.
Uma formiga robótica se move por uma malha quadriculada do nó $A$ até o nó $B$. Ela só pode se deslocar para a direita ou para cima seguindo as linhas da malha. Se para…
Uma formiga robótica se move por uma malha quadriculada do nó $A$ até o nó $B$. Ela só pode se deslocar para a direita ou para cima seguindo as linhas da malha. Se para ir de $A$ a $B$ deve dar exatamente $5$ passos para a direita e $4$ passos para cima, quantos caminhos distintos ela pode percorrer no total?
Deseja-se formar números de $6$ algarismos utilizando exclusivamente os dígitos $3, 5$ e $8$. Se o dígito $3$ deve aparecer exatamente três vezes, o dígito $5$ duas…
Deseja-se formar números de $6$ algarismos utilizando exclusivamente os dígitos $3, 5$ e $8$. Se o dígito $3$ deve aparecer exatamente três vezes, o dígito $5$ duas vezes e o dígito $8$ uma vez, quantos dos números formados são pares?
Na estação de esqui de Sierra Nevada (Granada), os funcionários das pistas publicam toda manhã o boletim de neve de um setor sinalizado com $6$ balizas consecutivas ao…
Na estação de esqui de Sierra Nevada (Granada), os funcionários das pistas publicam toda manhã o boletim de neve de um setor sinalizado com $6$ balizas consecutivas ao longo do percurso. Em um dia específico de fevereiro, colocam exatamente: $3$ balizas que indicam «neve em pó», $2$ balizas de «neve dura» e $1$ baliza de «neve úmida».
- a) Modele matematicamente a situação e calcule quantas sequências visuais diferentes de balizas podem ser formadas ao longo dessa descida.
- b) Explique por que, na fórmula, é necessário dividir por $3! \cdot 2! \cdot 1!$ em vez de calcular simplesmente $6!$.
Na estação de Atocha (Madri), um trem de Cercanías da Renfe é composto por $8$ vagões acoplados em linha. Em uma campanha especial de transporte sustentável, a Renfe…
Na estação de Atocha (Madri), um trem de Cercanías da Renfe é composto por $8$ vagões acoplados em linha. Em uma campanha especial de transporte sustentável, a Renfe dispõe de $4$ vagões padrão de passageiros, $2$ vagões adaptados para pessoas com mobilidade reduzida (PMR) e $2$ vagões com suporte para bicicletas. Os vagões do mesmo tipo são indistinguíveis entre si.
- a) Modele a situação e calcule quantas composições distintas podem ser formadas unindo os $8$ vagões em fila.
- b) Por motivos de operacionalidade nas plataformas, os técnicos da Renfe decidem que os dois vagões com suporte para bicicletas devem ser colocados obrigatoriamente um na primeira posição (frente do trem) e o outro na última posição (parte de trás do trem). Calcule quantas formações distintas de trem podem ser montadas com essa restrição.
- c) Suponha agora que o regulamento muda e exige que os dois vagões com suporte para bicicletas sejam acoplados sempre juntos, um imediatamente atrás do outro, em qualquer posição da formação. Raciocine, antes de calcular, se haverá mais ou menos possibilidades do que no item b) e determine depois o número exato de formações válidas sob essa nova condição.
Permutações circulares
Em uma fila, o primeiro e o último lugares são diferentes. Em uma mesa redonda não existe "primeiro lugar": só importa a ordem relativa entre as pessoas. Por isso, girar o grupo inteiro um assento não gera uma disposição nova.
Um grupo de $5$ amigos vai a uma pizzaria jantar e decide se sentar ao redor de uma mesa circular. De quantas maneiras diferentes eles podem se acomodar nos assentos?
Um grupo de $5$ amigos vai a uma pizzaria jantar e decide se sentar ao redor de uma mesa circular. De quantas maneiras diferentes eles podem se acomodar nos assentos?
No jantar de formatura do 4.º de ESO, cinco amigos vão sentar-se para jantar ao redor de uma mesa redonda de cinco lugares. Querem saber quantas formas distintas existem…
No jantar de formatura do 4.º de ESO, cinco amigos vão sentar-se para jantar ao redor de uma mesa redonda de cinco lugares. Querem saber quantas formas distintas existem de se posicionarem, tendo em conta unicamente quem se senta à esquerda e à direita de cada um (ou seja, a ordem relativa). Marcos calcula as possibilidades assim: «Por serem $5$ pessoas para $5$ lugares, são permutações ordinárias: $P_5 = 5! = 120$ formas distintas». Explica por que o raciocínio de Marcos não está correto para uma mesa redonda, que fenómeno geométrico ele não teve em conta e calcula a resposta correta.
Em uma festa de fim de ano letivo, $6$ amigos se sentam ao redor de uma mesa redonda. Dois deles, Lucas e Bruno, estão desentendidos e pediram expressamente para não se…
Em uma festa de fim de ano letivo, $6$ amigos se sentam ao redor de uma mesa redonda. Dois deles, Lucas e Bruno, estão desentendidos e pediram expressamente para não se sentarem juntos. De quantas formas distintas os $6$ convidados podem se distribuir cumprindo essa condição?
Deseja-se fabricar um colar montando $8$ contas esféricas de diferentes pedras preciosas. Como o colar pode ser afivelado, girar livremente pelo pescoço e inclusive ser…
Deseja-se fabricar um colar montando $8$ contas esféricas de diferentes pedras preciosas. Como o colar pode ser afivelado, girar livremente pelo pescoço e inclusive ser virado do avesso, quantos designs distintos de colares podem ser criados?
Voltando ao início: para formar uma senha reordenando 7 dígitos dados, sem repetir nenhum, você tem $P_7 = 7! = 5.040$ opções; e os 8 corredores podem chegar de $8! = 40.320$ formas.
Escolher sem importar a ordem
Alguns exercícios pedem escolher $k$ posições entre $n$, sem ordem. Isso é o mesmo que permutar com repetição: escolher 4 vitórias entre 9 partidas equivale a anagramas de 4 letras V e 5 letras D, ou seja, $\frac{9!}{4! \cdot 5!} = 126$.