ANÁLISE COMBINATÓRIA II

Compartilhe:

PERMUTAÇÃO CIRCULAR

Imagine que devemos distribuir n objetos em volta de uma mesa circular por exemplo (em forma de círculo). Teríamos uma distribuição dessa maneira.

Teríamos Pn= n!, mas repare que podemos “girar” o círculo que a ordem dos objetos não muda.

No caso de n objetos podemos girar o círculo n vezes que não alteramos a ordem dos objetos. Então:

Exemplo: De quantos modos distintos podemos distribuir 5 crianças numa roda para se brincar de ciranda? Como vamos permutar objetos ao longo de um círculo devemos usar uma permutação circular. Vamos inicialmente permutar as 5 crianças.

Na figura abaixo temos uma das 5! Permutações.

Porém veja que podemos ter 5 “giros” que ainda sim temos a mesma configuração.

Por isso devemos dividir 5! Por 5, como é a ideia da permutação circular.

COMBINAÇÃO SIMPLES

Uma combinação simples de n objetos distintos tomados p a p (sendo p ≤ n), é um dos subconjuntos com p elementos em que podem ser colocados p objetos, selecionados entre os n objetos dados.

Vamos imaginar que temos os objetos A, B, C, D, E, F e G e que destes queremos escolher 4 objetos. Dentre as vária possibilidades vamos imaginar o seguinte cenário.

ESCOLHIDOS: {A, B, E, F}
NÃO ESCOLHIDOS: {C, D, G}

Podemos começar permutando todos os 7 objetos, ou seja 7!. Mas como queremos 2 grupos, onde não há distinção alguma entre a ordem de seus elementos, tanto que {A, B, E, F} = {B, A, F, E} = … tanto para o conjunto de escolhidos como o de não escolhidos devemos dividir 7! Pela quantidade de cada conjunto.

Daí temos a noção de combinação simples, de onde sempre que queremos formar um grupo de p objetos dentre n também formamos um outro grupo de (n – p) objetos, assim

E dessa ideia podemos perceber que escolher 4 dentre 7 é o mesmo que deixar de escolher 3 dentre 7. Isso se chama combinação complementar.

Escolher p dentre n é o mesmo que escolher (n – p) dentre n. Assim

Exemplo: Num restaurante há 8 tipos de saladas, de quantas maneiras distintas uma pessoa pode se servir de 4 saladas diferentes?

Nota: Ao somarmos as combinações de objetos para 0 espaço com a combinação de n objetos para 1 espaço e assim até a combinação de n objetos para n espaços teremos:

Exemplo: Uma pastelaria oferece uma promoção: Monte seu pastel com até 5 recheios, carne, queijo, frango, calabresa e pizza. Quantos pastéis diferentes podem ser feitos sabendo-se que um mesmo recheio não pode ser colocado mais de uma vez?

A resposta seria dentre 5 recheios escolhermos somente 1 ou de 5 recheios escolhermos 2 até que de 5 recheios escolhêssemos os 5.

COMBINAÇÃO COM REPETIÇÃO

Imagine que você vai a um supermercado e deseja comprar 8 refrigerantes tendo 3 marcas diferentes disponíveis. É fácil perceber que não há possibilidade de levar somente marcas distintas, logo alguma marca terá que se repetir, essa é a ideia da combinação com repetição.

Podemos fazer uma assimilação da combinação com repetição com a quantidade de soluções inteiras e não negativas da equação.

Onde x, y e z são as marcas de refrigerante que temos disponíveis e 8 é a quantidade total que queremos levar. Assim veja que se imaginarmos as soluções inteiras e não negativas dessa equação é algo interessante.

Solução {0, 3, 5} – não compramos nenhum refrigerante da marca 1, 3 refrigerantes da marca 2 e 5 refrigerantes da marca 3.

Solução {2, 2, 4} – compramos 2 refrigerantes da marca 1, 2 refrigerantes da marca 2 e 4 refrigerantes da marca 3.

Solução {0, 8, 0} – compramos todos os 8 refrigerantes da marca 2.

Então a quantidade soluções inteiras e não negativas dessa equação nos dá a quantidade de escolhas. Para criar um modo de calcular vamos imaginar cada sinal de + como uma “barra” e a quantidade total que se deseja a quantidade de “bolas” a se distribuir.

Então podemos pensar que temos 10 objetos no total (8 bolas e 2 barras), onde 8 são iguais entre si (8 bolas) e 2 são iguais entre si (2 bolas). Logo para se obter uma solução diferente basta permutar a
posição dos objetos, assim

Logo podemos escolher nossos 8 refrigerantes de 45 maneiras diferentes. Assim quando vamos escolher p objetos dentre n disponíveis mas desses p objetos podemos ter objetos repetidos teremos.