Análise combinatória – Permutação, arranjo e combinações simples

FATORIAL

Definimos como o fatorial de n (simbolizado por n!) ao produto do n primeiros números inteiros positivos. Caso n = 0, definiremos 0! =1. Dessa forma, teremos:

Exemplo:

PERMUTAÇÕES

Permutar elementos significa trocá-los de posição. A maneira de calcular as possibilidades de fazer isso, vai depender da natureza dos elementos que a serem permutados. E é isso o que faremos a seguir.

PERMUTAÇÕES SIMPLES

Uma permutação de n objetos distintos é qualquer agrupamento ordenados desses objetos, de modo que, se denominarmos P_n  o número das permutações simples dos n objetos, então:

P_n  = n!

De fato, imaginemos que dispomos de  n objetos distintos para serem colocados em fila, ocupando n posições. Pelo Princípio Multiplicativo, temos n objetos para ocupar a 1^a posição. Ocupada a 1^a posição com um objeto, a 2^a posição pode ser ocupada por qualquer um dos n – 1 objetos restantes. Daí, ocupada a 2^a posição, a terceira posição pode ser ocupada por qualquer um dos n – 2 objetos restantes. Repetindo esse raciocínio até o último objeto, restará para ele a última posição da fila. Logo, pelo Princípio Multiplicativo, teremos:

n . (n – 1) . (n – 2) . (n – 3) . … . 3 . 2 . 1 que é exatamente o mesmo que escrever  n!

Exercício Resolvido

01. De quantas maneiras pode-se colocar 4 pessoas em fila?  

Resolução:

Note que, temos 4 pessoas que podem ocupar o 1^o lugar da fila. Daí, colocada a primeira pessoa na fila, restam 3 pessoas que podem ocupar o 2^o lugar da fila. Em seguida, colocada a 2^a pessoa, agora restam duas pessoas que podem ocupar o 3^o lugar da fila. E por fim, colocada a segunda pessoa na fila, sobra uma pessoa para ocupar a última posição. Pelo Princípio Multiplicativo, teremos

ARRANJOS

No estudo das Permutações trabalhamos os casos em que trocamos de posição todos os elementos de uma sequência de objetos qualquer. Um Arranjo será, em geral, uma permutação de apenas uma parte dos objetos dados, onde a ordem dos mesmos também influencia na disposição dos elementos. Note que, quando temos um arranjo em que estamos interessados na troca de posição de todos os elementos, esse arranjo pode ser encarado como uma permutação. O que faremos a seguir, é analisar os diferentes tipos de arranjos.

ARRANJOS SIMPLES

Considere um conjunto com  n elementos distintos. Qualquer sequência de p desses elementos (todos distintos) é chamada de Arranjo Simples (0 ≤ p ≤ n, com n e p naturais). Dizemos arranjo simples de n elementos tomados  p a p, e simbolizamos por A_{n ,p}

Esse arranjo simples pode ser calculado da seguinte forma:

De fato, suponha que dispomos de n objetos distintos, e escolheremos p desses objetos para serem colocados em uma fila, com  p  posições. Dessa forma a fila terá p objetos. Pelo Princípio Multiplicativo, temos  n  objetos para ocupar a 1ª posição. Ocupada a 1ª posição com um objeto, a 2ª posição pode ser ocupada por qualquer um dos  n-1  objetos restantes. Daí, ocupada a 2ª posição, a terceira posição pode ser ocupada por qualquer um dos n-2 objetos restantes. Repetindo esse raciocínio até a posição de número p, teremos para ela n – p + 1objetos disponíveis para ocupá-la.

Pelo Princípio Multiplicativo teremos

Multiplicando e, ao mesmo tempo, dividindo o segundo membro dessa igualdade por (n – p)!, temos.

É importante enfatizar que nos problemas que envolvem a ferramenta do arranjo, a ordem dos termos agrupados importa, uma vez que uma sequência será diferente de uma outra se seus respectivos termos estiverem ordenados de forma distinta.

Exercício Resolvido 

02. Considere os algarismos 1,2,3,4 e 5. Quantos números com algarismos distintos, superiores a 100 e inferiores a 1.000, podemos formar?

Resolução:

O problema solicita que encontremos todos os números com três algarismos distintos uma vez que, todos os números maiores que 100 e menores que 1.000 têm três dígitos. Dessa forma, temos cinco algarismos disponíveis e usar três deles para formar números de três algarismos distintos. A solução do problema será o arranjo simples de 5 elementos tomados 3 a 3. Ou seja,

É muito importante notar que, todos os problemas de arranjo simples poderão ser resolvidos usando o Princípio Multiplicativo, e é o que sempre faremos aqui.

ARRANJOS COM REPETIÇÃO

Considere um conjunto com  n elementos distintos. Qualquer sequência de  p desses elementos é chamada de Arranjo com repetição (0 ≤ p ≤ n, com  n  e  p  naturais). Note que os  p  elementos podem ser distintos ou não, isto é, pode haver elementos repetidos. Daí o nome, arranjo com repetição.

Dizemos arranjo com repetição de n elementos tomados  p  a  p, e simbolizamos por AR_{n, p}.

Esse arranjo com repetição pode ser calculado da seguinte forma:

De fato, suponha que dispomos de n objetos distintos, e escolheremos p desses objetos para serem colocados em uma fila, com  p posições. Dessa forma a fila terá p objetos. Pelo Princípio Multiplicativo, temos n objetos para ocupar a 1^a posição. Ocupada a 1^a posição com um objeto, como os objetos na fila podem ser repetidos, para 2^a posição ainda temos n objetos disponíveis. Ocupada a 1^a posição com um objeto, como os objetos na fila podem ser repetidos, para 2^a posição ainda temos n objetos disponíveis. Repetindo esse raciocínio até a última posição, que é a posição de número p, como os objetos podem ser repetidos, ainda teremos n objetos disponíveis para essa posição. Assim, pelo Princípio Multiplicativo, teremos.

Exercício Resolvido 

03. Considere os algarismos 1,2,3,4 e 5. Quantos números, superiores a 100 e inferiores a 1.000, podemos formar?

Resolução:

O problema solicita que encontremos todos os números com três algarismos (distintos ou não) uma vez que, todos os números maiores que 100 e menores que 1.000 têm três dígitos. Assim, temos 5 elementos e precisamos escolher 3 para formar números, onde os algarismos podem ser repetidos ou não. Dessa forma, a solução do problema será o arranjo com repetição de 5 elementos tomados 3 a 3. Ou seja,

Note que, assim como foi feito no arranjo simples, podemos também no arranjo com repetição resolver qualquer problema usando o Princípio Multiplicativo, da seguinte forma:

Como foi dito no arranjo simples, é muito importante notar que, todos os problemas de arranjo com repetição também poderão ser resolvidos usando o Princípio Multiplicativo. Dessa forma, vale ressaltar que qualquer problema de arranjo, não importa se for simples ou com repetição, sempre é possível se resolver usando o Princípio Multiplicativo. E é o que sempre faremos aqui.

COMBINAÇÕES

Assim como foi feito no estudo dos arranjos, iremos separar as combinações em dois casos. As combinações simples e as combinações com repetição (também chamadas de combinações completas).

COMBINAÇÕES SIMPLES

Considere um conjunto com  n elementos distintos. Qualquer subconjunto formado por de p desses elementos (todos distintos) é chamado de Combinação Simples (0 ≤ p ≤ n, com n e p naturais).

Dizemos combinação simples de n elementos tomados p a p, e simbolizamos por C_n,p

Essa combinação simples pode ser calculada da seguinte forma:

De fato, considere um conjunto com n elementos distintos. Seja  C_{n, p}  é a quantidade de subconjuntos com p  elementos distintos que podemos formar. Note que, em cada subconjunto formado, a ordem não importa. Se a ordem importasse, teríamos um arranjo simples desses elementos, que é  A_n,p. Assim,

Aⁿ,ᵖ = p!. Cⁿ,ᵖ

É importante enfatizar que nos problemas que envolvem a ferramenta da combinação a ordem dos termos agrupados não importa, uma vez que um subconjunto  A será igual a um outro subconjunto B se seus respectivos elementos forem os mesmos.

Exercício Resolvido

04. Uma escola quer organizar um torneio esportivo com 10 equipes, de forma que cada equipe jogue exatamente uma vez com cada uma das outras.  Quantos jogos terá o torneio?

Resolução:

Considere E = {E₁, E₂, E₃, … , E₁₀} o conjunto dos times do referido torneio. Note que, resolver esse problema é determinar o número de subconjuntos com dois elementos que podemos formar, a partir dos elementos do conjunto E. Teremos, portanto:

Logo, teremos 45 subconjuntos, ou seja, 45 jogos nesse torneio.