PERMUTAÇÃO COM REPETIÇÃO
Discutiremos agora arrumações de uma coleção de objetos com objetos repetidos, tais como a coleção {b, a, n, a, n, a} e escolhas de objetos de um conjunto onde um objeto pode ser selecionado mais de uma vez, tais como pedir seis cachorros quentes a serem escolhidos dentre três variedades. Determinaremos as fórmulas para esses problemas de contagem através de dois exemplos:
TEOREMA
Se existem n objetos dos quais k1 são do tipo 1, k2 são do tipo 2, …, e km são do tipo m onde k1 + k2 + … + kn = n então o número de arrumações destes n objetos denotado por P(n; k1
, k2 , …, km) é:
Prova com efeito, além do argumento utilizado no exemplo acima a saber, escolhendo as posições para um dos tipos dentre aquelas que vão restando, podemos provar o teorema acima da seguinte forma:
Suponhamos que para cada tipo dos ki objetos do tipo i sejam dados índices 1, 2, 3, …, m tornando-os distintos. Existem então n!
arrumações destes n objetos distintos. Enumeremos agora estas n!
arrumações de objetos distintos enumerando todas as P(n; k1 , k2 , …,
km) disposições (sem índices) dos objetos e então, para cada disposição colocando os índices de todos os modos possíveis. Por exemplo, da disposição banana os índices podem ser colocados nos a’s de 3! maneiras:
Para cada uma dessas 3! maneiras para indexar os a’s, existem 2! maneiras para indexar os n’s. Assim, em geral, uma disposição qualquer terá k1 ! maneiras de indexar os k1 objetos do tipo 1, k2! maneiras para o tipo 2, …, km! maneiras para o tipo m. Então:
COMBINAÇÕES COM REPETIÇÃO
Exemplo:
De quantos modos distintos podemos comprar seis cachorros quentes podendo escolher entre 3 variedades distintas?
Para resolver problemas de escolhas com repetição, precisamos fazer uma correspondência um a um com um problema relacionado a uma escolha sem repetição. Suponhamos que as três variedades sejam sem molho, com molho e completo e que a atendente tenha anotado
o seguinte pedido:
Se cada s representa um cachorro quente, então o pedido acima significa um sem molho, quatro com molho e um completo. Uma vez que todos os atendentes saibam que esta é a sequência dos pedidos de cachorros quentes (sem molho, com molho, completo) podemos
omitir os nomes das variedades escrevendo apenas x | xxxx | x. Assim, qualquer pedido de k cachorros quentes consiste numa sequência de k x1s e dois |’s. Reciprocamente, toda sequência de k x’s e dois |’s representa um pedido: os x’s antes do primeiro | representa o número
de cachorros sem molho: os x’s entre os dois |’s representa o número de cachorros com molho e os x’s nais representam o número de cachorros completos. Deste modo, existe uma correspondência um a um entre pedidos e tais sequências, mas o número de sequências
de seis x’s e dois |’s é simplesmente o número de escolhas de duas posições na sequência para os |’s. Assim, a resposta é 2 8 28.
TEOREMA
DISTRIBUIÇÕES
Geralmente um problema de distribuição é equivalente a um problema de arrumação ou de escolha com repetição. Problemas especializados de distribuição devem ser divididos em subcasos que possam ser contados por intermédio de permutações e combinações
simples. Um roteiro geral para modelar problemas de distribuição é, distribuições de objetos distintos correspondem a arrumações e distribuições de objetos idênticos correspondem a escolhas.
Assim, distribuir k objetos distintos em n urnas diferentes é equivalente a colocar os objetos em linha e atribuir o nome de cada uma das n diferentes urnas em cada objeto. Assim, existem
nnn n n k vezes k … … = distribuições.
Por outro lado, o processo de distribuir k objetos idênticos em n urnas distintas é equivalente a escolher um subconjunto (não ordenado) de k nomes de urnas, com repetição, entre as n escolhas de
PERMUTAÇÕES CIRCULARES
Consideremos n objetos distintos e disponhamos esses n objetos em torno de um círculo.
Se n > 3, podemos imaginar esses objetos situados nos vértices de um polígono, por exemplo, um polígono regular.
O quadro abaixo apresenta as disposições dos objetos A, B, C, D em torno de um círculo.
Observamos então que:
A 1a coluna do quadro foi obtida fixando-se o objeto A e permutando-se os objetos B, C, D de todos os modos possíveis, isto é, 3! = 6 modos. Em cada linha uma disposição pode ser obtida de outra por uma rotação conveniente e dadas duas disposições em linhas diferentes, nenhuma pode ser obtida da outra por qualquer rotação.
Assim, chama-se permutação circular de n objetos distintos qualquer disposição desses objetos em torno de um círculo e duas permutações circulares são indistinguíveis se, e somente se, uma pode ser obtida a partir da outra por uma rotação conveniente como,
por exemplo, duas permutações quaisquer de uma mesma linha do quadro acima. Diremos ainda que duas permutações circulares são distinguíveis se, e somente se, uma não pode ser obtida da outra por qualquer rotação como, por exemplo, duas permutações quaisquer
em linhas diferentes do quadro acima.
Portanto, no cálculo das permutações circulares interessa apenas a posição relativa dos objetos entre si, isto é, o número de permutações circulares distinguíveis. Generalizando temos que o número de permutações circulares de n objetos, denotado por (PC)n , é igual a n!/n, isto é:
