Suponha que você tenha n tipos de itens e deseja selecionar uma coleção de r deles. Podemos querer esses itens em alguma ordem específica. Chamamos esses conjuntos de permutações de itens. Se a ordem não importa, chamamos o conjunto de combinações de coleções. Para combinações e permutações, você pode considerar o caso em que você escolhe alguns dos n tipos mais do que uma vez, que é chamado de 'com repetição', ou o caso em que você escolhe cada tipo apenas uma vez, que é chamado de 'não repetição'. O objetivo é ser capaz de contar o número de combinações ou permutações possíveis em uma dada situação.
Ordenações e fatoriais
A função fatorial é freqüentemente usada ao calcular combinações e permutações. N! significa N × (N – 1) ×... × 2 × 1. Por exemplo, 5! = 5×4×3×2×1 = 120. O número de maneiras de ordenar um conjunto de itens é um fatorial. Pegue as três letras a, be c. Você tem três opções para a primeira letra, duas para a segunda e apenas uma para a terceira. Em outras palavras, um total de 3 × 2 × 1 = 6 pedidos. Em geral, existem n! maneiras de pedir n itens.
Permutações com Repetição
Suponha que você tenha três quartos que vai pintar, e cada um será pintado em uma das cinco cores: vermelho (r), verde (g), azul (b), amarelo (y) ou laranja (o). Você pode escolher cada cor quantas vezes quiser. Você tem cinco cores para escolher para o primeiro cômodo, cinco para o segundo e cinco para o terceiro. Isso dá um total de 5 × 5 × 5 = 125 possibilidades. Em geral, o número de maneiras de escolher um grupo de r itens em uma ordem específica a partir de n escolhas repetíveis é n ^ r.
Permutações sem repetição
Agora, suponha que cada cômodo terá uma cor diferente. Você pode escolher entre cinco cores para o primeiro cômodo, quatro para o segundo e apenas três para o terceiro. Isso dá 5 × 4 × 3 = 60, que por acaso é 5! / 2!. Em geral, o número de maneiras independentes de selecionar r itens em uma ordem particular a partir de n escolhas não repetíveis é n! / (N – r) !.
Combinações sem repetição
Em seguida, esqueça qual é a cor do cômodo. Basta escolher três cores independentes para o esquema de cores. A ordem não importa aqui, então (vermelho, verde, azul) é o mesmo que (vermelho, azul, verde). Para qualquer escolha de três cores, existem 3! maneiras de encomendá-los. Então você reduz o número de permutações em 3! para obter 5! / (2! × 3!) = 10. Em geral, você pode escolher um grupo de r itens em qualquer ordem a partir de uma seleção de n escolhas não repetíveis de n! / [(N – r)! × r!] Maneiras.
Combinações com Repetição
Finalmente, você precisa criar um esquema de cores no qual possa usar qualquer cor quantas vezes quiser. Um código de contabilidade inteligente ajuda nessa tarefa de contagem. Use três Xs para representar os quartos. Sua lista de cores é representada por 'rgbyo'. Misture os Xs em sua lista de cores e associe cada X à primeira cor à esquerda dele. Por exemplo, rgXXbyXo significa que a primeira sala é verde, a segunda é verde e a terceira é amarela. Um X deve ter pelo menos uma cor à esquerda, portanto, há cinco slots disponíveis para o primeiro X. Como a lista agora inclui um X, há seis slots disponíveis para o segundo X e sete slots disponíveis para o terceiro X. Ao todo, são 5 × 6 × 7 = 7! / 4! maneiras de escrever o código. No entanto, a ordem dos quartos é arbitrária, portanto, existem apenas 7! / (4! × 3!) Arranjos exclusivos. Em geral, você pode escolher r itens em qualquer ordem a partir de n escolhas repetíveis em (n + r – 1)! / [(N – 1)! × r!] Maneiras.