PRINCÍPIOS DE CONTAGEM
INTRODUÇÃO
Frequentemente, no nosso dia a dia, precisamos enumerar “eventos” tais como, arrumação de objetos de certa maneira, particionar coisas sob uma certa condição, distribuições para certos
ns etc. Para fazermos isto, antes de tudo, precisamos enunciar dois teoremas que são fundamentais em todos os problemas de contagem.
O PRINCÍPIO ADITIVO (AP)
Suponha que existam n1 maneiras para o evento E1 ocorrer, n2 maneiras para o evento E2
ocorrer, nk maneiras para o evento Ek ocorrer, onde k ≥ 1. Se estas maneiras para as ocorrências dos eventos distintos forem disjuntas duas a duas então o número de maneiras nas quais pelo menos um dos eventos E1 ,E2 , …, ou Ek pode ocorrer é
Assim, por exemplo, se podemos ir de uma cidade P a uma cidade Q por vias aérea, marítima e rodoviária, e supondo que existam 2 companhias marítimas, 3 companhias aéreas e 2 companhias rodoviárias que fazem o trajeto entre P e Q, então pelo AP o número
total de se fazer o trajeto de P a Q pelo mar, pelo ar ou por rodovia é 2 + 3 + 2 = 7.
Uma forma equivalente do AP usando a terminologia dos conjuntos onde |X| representa o número de elementos do conjunto X é o seguinte:
Sejam A1 , A2 , …, Ak conjuntos nitos quaisquer onde k ≥ 1. Se os conjuntos dados são distintos dois a dois, então
O PRINCÍPIO MULTIPLICATIVO (MP)
Supondo que um evento E possa ser decomposto em r eventos ordenados E1 , E2 , …, Er e que existam.
n1
maneiras para o evento E1 ocorrer n2 maneiras para o evento E2 ocorrer nr maneiras para o evento Er ocorrer Então o número de maneiras do evento E ocorrer é dado por
Assim, por exemplo, se para irmos de uma cidade A até uma cidade D devemos passar pelas cidades B e C, nesta ordem, e supondo que existam duas maneiras distintas de ir de A até B, 5 maneiras distintas de se ir de B até C e 3 maneiras distintas de se ir de C até D então, pelo MP, o número de maneiras de se ir de A até D passando por B e C é dado por 2 × 5 × 3 = 30.
ARRUMAÇÕES E ESCOLHAS SIMPLES
DEFINIÇÕES
Uma permutação de n objetos distintos é qualquer agrupamento ordenado desses n objetos isto é, uma arrumação em ordenação dos n objetos.
Uma k-permutação ou uma permutação de classe k dos n objetos distintos é uma arrumação utilizando k dos n objetos (uma k-permutação é o que os livros tradicionais chamam de “arranjo de k coisas dentre n”). Usaremos P (n, k) · A (n, k) ou An k para denotar o
número de k-permutações de um conjunto de n objetos.
Do princípio multiplicativo obtemos:
