Análise Combinatória – Permutação com repetição e combinações completas
Aprenda mais sobre Análise Combinatória.
PERMUTAÇÕES COM REPETIÇÕES
Uma permutação de n elementos, sendo n1 elementos iguais a a1, n2 elementos iguais a a2, …, nr elementos iguais a ar será dada por:
Exercício Resolvido
01. Quantos anagramas da palavra PALAVRA podem ser formados?
Resolução:
Se as letras fossem diferentes, a resposta seria 7!. Como as três letras A são iguais, quando as trocamos entre si, obtemos o mesmo anagrama e não um anagrama distinto, o que ocorreria se fossem diferentes. Isso faz com que, na nossa contagem 7!, tenhamos contado o mesmo anagrama 3! vezes, pois há 3! modos de trocar as letras A entre si.
Logo, a resposta é:
PERMUTAÇÕES CIRCULARES
Nosso objetivo agora é analisar as permutações quando os elementos estão dispostos de forma circular. Nesse caso, duas disposições serão consideradas iguais quando podem coincidir através de rotação. Dessa forma, o número de permutações circulares de n objetos distintos é dada por:
Exercício Resolvido
02. De quantos modos podemos formar uma mesa de buraco (jogo de cartas de baralho) com 4 jogadores?
Resolução:
Abaixo seguem todas as possibilidades de configurar dando destaque para àquelas que, pela definição, se tornam distintas entre si.
Temos, então:
COMBINAÇÕES COM REPETIÇÃO (OU COMBINAÇÕES COMPLETAS)
É número de maneiras de selecionarmos p objetos dentre n objetos distintos onde cada um deles poderá ser tomado até p vezes. Note que é um tipo de combinação, onde os objetos selecionados podem aparecer repetidos, mas como em toda combinação, a ordem dos objetos não importa.
Dizemos combinação com repetição de n elementos tomados p a p, e simbolizamos por CRn, p
Em alguns textos chama-se combinações completas.
Nosso objetivo agora será criar um método para calcular esse tipo de combinação.
Exercício resolvido
03. Considere a seguinte situação:
Uma pessoa quer comprar para sua família 10 sorvetes numa padaria. Há sorvetes de abacaxi, banana, creme e damasco. Sabendo-se que podem ser compradas de zero a 10 sorvetes de cada tipo, de quantas maneiras diferentes esta compra pode ser feita?
Resolução:
Repare inicialmente que como a ordem da compra não influencia nos sorvetes comprados, estamos em um problema de combinação. Além disso, repare que temos apenas 4 sabores de sorvete e precisamos comprar 10 sorvetes. Dessa forma, necessariamente teremos sabores repetidos. Logo estamos em um problema de combinação com repetição, onde temos n = 4 tipos de sorvetes, e desses sabores que estão à disposição, preciso formar grupos de p = 10 sorvetes.
Podemos resolver esse problema imaginando que x1, x2, x3 e x4 representam os tipos de sabores e que precisamos comprar 10 sorvetes da seguinte forma:
x1 + x2 + x3 + x4 = 10
Algumas soluções que satisfazem a solução acima seriam: (0, 0, 0, 10); (3, 0, 3, 4); (2, 1, 3, 4). Se observarmos as duas últimas soluções poderíamos chegar a seguinte conclusão:
Ou seja:
As representações ( … + + … + ….) e (.. + . + … + ….) podem ser analisadas como dois anagramas formadas por 13 elementos sendo 10 elementos do tipo “.” e três do tipo “+”. Portanto, podemos calcular o número de anagrama pela ferramenta da permutação com elementos repetidos.
Podemos agora seguir o mesmo raciocínio para uma generalização do problema. Suponha agora que temos n objetos distintos e quero formar subconjuntos com p elementos, podendo haver elementos repetidos no subconjunto. Nosso problema então é resolver a equação
Que será o mesmo que calcular o número de permutações de p elementos do tipo “.” e n – 1 elementos do tipo “+”, sendo um total de p + n –1 elementos.
Logo,
Isto é,
Podemos agora, resolver o problema anterior dos sorvetes usando essa fórmula. Temos 4 opções de sorvetes e vamos comprar 10 sorvetes, alguns sabores sendo repetidos. Assim temos n = 4 e p = 10
Logo, teremos 286 maneiras distintas.
Como foi visto no exemplo anterior, nas combinações com repetição podemos ter n menor do que p.
