• Instalar e carregar o pacote gtools para aplicar as tarefas no R:
#install.packages("gtools") #se for instalar, retire o símbolo de "#"
require(gtools)

Análise Combinatória

A análise combinatória envolve cálculos relacionados à contagem, que envolve a análise das possibilidades e das combinações possíveis entre um conjunto de elementos. A análise combinatória é largamente utilizada nos cálculos de probabilidades.

Probabilidade

A Probabilidade é um campo da estatística e matemática que envolve calcular as chances de obter determinado resultado diante de um experimento aleatório. São exemplos um lançamento de dados ou a possibilidade de ganhar na loteria. A probabilidade (\(P\)) é igual à razão entre o número de eventos favoráveis (\(n_f\)) e o número de eventos possíveis (\(n\)): \[ P=\frac{n_f}{n}. \]

Princípio Fundamental da Contagem

Quando um evento é composto por \(2\) etapas sucessivas e independentes, de tal modo que o número de possibilidades na primeira etapa é igual a \(n_1\) e o número de possibilidades na segunda etapa é igual a \(n_2\), então o número total de possibilidades \((n)\) é dado pelo produto \(n_1 \times n_2\): \[ n=n_1 \times n_2. \] Este raciocínio se extende para várias etapas sucessivas independentes: \[ n=n_1 \times n_2 \times \ldots \times n_m. \] Em resumo, no princípio fundamental da contagem, multiplica-se o número de opções entre as escolhas que lhe são apresentadas.

Exemplo 1: Jeniffer irá participar da promoção de uma loja de roupas que está dando um vale compras no valor de \(1.000,00\) reais. Ganhará o desafio o primeiro participante que conseguir fazer o maior número de combinações com o kit de roupas cedido pela loja. No kit temos: seis camisetas, quatro saias e dois pares de sapatos. De quantas maneiras distintas Jeniffer poderá combinar todo o vestuário do kit de roupas?
Pelo princípio fundamental da contagem, o total de possibilidades é dado pelo produto:

\[\begin{eqnarray*} \text{ n } &=& \text{ Total de camisetas $\times$ Total de saias $\times$ Total de pares de sapatos}\\ &=& n_1 \times n_2 \times n_3 = 6 \times 4 \times 2 = 48. \end{eqnarray*}\]

Permutações

Permutações são agrupamentos ordenados em que o número de elementos do agrupamento (\(n\)) é igual ao número de elementos disponíveis (\(n\)). Além disso, cada elemento do agrupamento aparece somente uma vez. A contagem do número de permutações é dada pela fórmula: \[ \begin{array}{lcl} P_n=n! &&\text{ donde lê-se: "O número de permutações de $n$ elementos é igual a $n!$." } \end{array} \]

Exemplo 2: De quantas modos \(6\) carros podem estacionar em um pátio com \(6\) vagas de garagem?

  • Primeiro modo, sem usar fórmula de permutação: O primeiro carro tem \(6\) opções para estacionar, o segundo \(5\), o terceiro \(4\), o quarto \(3\), o quinto \(2\) e o sexto apenas \(1\). Logo o número de possibilidades é \(6! = 6. 5. 4. 3. 2. 1 = 720\).
  • Outro modo, com fórmula de permutação: O número de possibilidades é dado por \(P_6=6!=720\).

No software R:

  • utiliza-se o comando permutations, com n=6 (carros), r=6 (vagas), e guardando no objeto modos;
  • o comando head mostra as 10 primeiras permutações do objeto modos;
  • o comando nrow mostra o número de linhas do objeto modos, ou seja, o número total de permutações é igual a 720.
modos=permutations(n=6, r=6)
head(modos,10)
##       [,1] [,2] [,3] [,4] [,5] [,6]
##  [1,]    1    2    3    4    5    6
##  [2,]    1    2    3    4    6    5
##  [3,]    1    2    3    5    4    6
##  [4,]    1    2    3    5    6    4
##  [5,]    1    2    3    6    4    5
##  [6,]    1    2    3    6    5    4
##  [7,]    1    2    4    3    5    6
##  [8,]    1    2    4    3    6    5
##  [9,]    1    2    4    5    3    6
## [10,]    1    2    4    5    6    3
nrow(modos)
## [1] 720

Arranjo

Arranjos são agrupamentos ordenados em que os elementos são distintos e o número de elementos do agrupamento (\(p\)) é menor ou igual ao número de elementos disponíveis (\(n\)). A contagem do número de arranjos é dada pela fórmula: \[ A_{n,p}=\frac{n!}{(n-p)!} \text{ com $p \leq n$}, \] donde lê-se: “O número de arranjos de \(n\) elementos tomados \(p\) a \(p\) é igual a \(n!\) sobre \((n-p)!\)”

Exemplo 3: Um anagrama é uma combinação qualquer de letras. Quantos anagramas de \(4\) letras distintas podemos formar com um alfabeto de \(23\) letras?

  • Primeiro modo: sem usar fórmula de arranjo: Queremos formar anagramas do tipo: ABCD, ou COXU, DCBA entre outras possibilidades. Na primeira posição temos \(23\) opções de letras, na segunda \(22\), na terceira \(21\) e na quarta temos \(20\). Logo o número de possibilidades é \(23.22.21.20=212520\).

  • Outro modo:, com fórmula de arranjo: \[ A_{23,4}=\frac{23!}{19!} = 23.22.21.20=212520, \] donde lê-se: “O número de arranjos distintos de \(23\) elementos tomados \(4\) a \(4\) é igual a 212520.”

  • Logo o número de anagramas é igual a \(212520\).

No software R:

  • O comando LETTERS solta as letras do alfabeto em inglês, com 26 letras;
  • realiza-se um filtro para retirar as letras “K”, “Y” e “W”, resultando em 23 letras do nosso alfabeto;
  • utiliza-se o comando permutations, com n=23 (total de letras), r=4 (letras no anagrama), e guardando no objeto modos;
  • o comando head mostra as 10 primeiras permutações do objeto modos;
  • o comando nrow mostra o número de linhas do objeto modos, ou seja, o número total de arranjos é igual a 212520.
LETTERS
##  [1] "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" "L" "M" "N" "O" "P" "Q" "R" "S"
## [20] "T" "U" "V" "W" "X" "Y" "Z"
letras=LETTERS[!(LETTERS %in% c("K","Y","W"))]
modos=permutations(n=23, r=4,v=letras)
head(modos,10)
##       [,1] [,2] [,3] [,4]
##  [1,] "A"  "B"  "C"  "D" 
##  [2,] "A"  "B"  "C"  "E" 
##  [3,] "A"  "B"  "C"  "F" 
##  [4,] "A"  "B"  "C"  "G" 
##  [5,] "A"  "B"  "C"  "H" 
##  [6,] "A"  "B"  "C"  "I" 
##  [7,] "A"  "B"  "C"  "J" 
##  [8,] "A"  "B"  "C"  "L" 
##  [9,] "A"  "B"  "C"  "M" 
## [10,] "A"  "B"  "C"  "N"
nrow(modos)
## [1] 212520

Exemplo 4: Sendo as letras de A a Z sem considerar o K, Y e W, então temos \(23\) letras e os anagramas CALO, OLAC, PIRA, REZA, OLHA, OEMU são alguns dentre as \(212520\) opções disponíveis. Observe que não é sempre que um anagrama é uma palavra do dicionário em português.

Combinação

Combinações são agrupamentos em que a ordem dos elementos não é importante. O número de elementos do agrupamento (\(p\)) é menor ou igual ao número de elementos disponíveis (\(n\)). Além disso, cada elemento do agrupamento aparece somente uma vez. A contagem do número de combinações é dada pela fórmula: \[ C_{n,p}=\frac{n!}{p!(n-p)!}, \text{ com $p \leq n$}, \] donde lê-se: “O número de combinações de \(n\) elementos tomados \(p\) a \(p\) é igual a \(n!\) sobre \(p!(n-p)!\)”.

Interpretação:

  • Como a ordem dos elementos não é importante, então no denominador nós colocamos \(p!\);
  • \(p!\) é o número de permutações de \(p\) elementos;
  • significa que estamos descartando os agrupamentos que só diferem pela ordem dos elementos.

Exemplo 5: Quantos subconjuntos de \(3\) elementos possui o conjunto \(C=\{1,2,3,4,5\}\).

Resp.: Queremos subconjuntos do tipo: \(C_1=\{1,2,3\}\), \(C_2=\{1,2,4\}\), \(C_3=\{1,2,5\}\), entre outras possibilidades. Trata-se de combinação pois a ordem dos elementos não é importante, por exemplo \(\{1,2,3\}=\{1,3,2\}\). \[ C_{5,3}=\frac{5!}{3!(5-3)!}=\frac{5.4.3!}{3!2!}=\frac{5.4}{2.1}=10 \text{ subconjuntos. } \] Fazendo a listagem dos subconjuntos, temos: \(C_1=\{1,2,3\},C_2=\{1,2,4\},C_3=\{1,2,5\},C_4=\{2,3,4\},C_5=\{2,3,5\},\)
\(C_6=\{2,4,5\},C_7=\{1,3,4\},C_8=\{1,3,5\},C_9=\{1,4,5\},C_{10}=\{3,4,5\}\).

No software R:

  • utiliza-se o comando combinations, com n=5 (total de números), r=3 (números no conjunto), e guardando no objeto modos;
  • o comando nrow mostra o número de linhas do objeto modos, ou seja, o número total de combinações é igual a 10.
modos=combinations(n=5, r=3)
modos
##       [,1] [,2] [,3]
##  [1,]    1    2    3
##  [2,]    1    2    4
##  [3,]    1    2    5
##  [4,]    1    3    4
##  [5,]    1    3    5
##  [6,]    1    4    5
##  [7,]    2    3    4
##  [8,]    2    3    5
##  [9,]    2    4    5
## [10,]    3    4    5
nrow(modos)
## [1] 10

Exemplo 6: a) Em uma eleição para representante de turma, \(3\) alunos candidataram-se: Vanessa, Caio e Flávia. Quantos são os possíveis resultados dessa eleição?
Resp.: Trata-se de permutação pois a ordem (1º lugar, 2º lugar e 3º lugar) em que as pessoas aparecem é importante. \[ P_3=3!=6 \text{ resultados diferentes. } \]
b) Quantos números de \(3\) algarismos distintos podemos formar com os dígitos \(7\),\(8\) e \(9\)?
Resp.: Trata-se de permutação pois a ordem em que os números aparecem é importante. \[ P_3=3!=6 \text{ números de algarismos distintos. } \] Fazendo a listagem dos números, temos: \(789, 798, 879, 897, 978, 987\).
c) De quantas maneiras diferentes \(6\) pessoas podem se dispor em uma fila?
Resp.: Trata-se de permutação pois a ordem em que as pessoas aparecem é importante. \[ P_6=6!=720 \text{ maneiras diferentes. } \]
d) Considere a palavra LIVRO - Quantos anagramas são formados com as letras dessa palavra?
Resp.: Trata-se de permutação pois a ordem em que as letras aparecem é importante. \[ P_5=5!=120 \text{ anagramas. } \] Os anagramas LIRVO, IVRLO, VILRO são alguns dentre as \(120\) opções disponíveis.

  • Quantos anagramas começam com L e terminam com O?
    Resp.: Queremos anagramas do tipo: LVIRO. Então basta permutar as outras \(3\) letras nos três espaços disponíveis. \[ P_3=3!=6 \text{ anagramas. } \] Fazendo a listagem dos anagramas, temos: LIRVO, LIVRO, LRIVO, LRVIO, LVRIO, LVIRO.

  • Quantos anagramas contém as letras RO juntas e nesta ordem?
    Resp.: Queremos anagramas do tipo: VROLI. Então basta considerar RO como sendo uma única letra e permutar \(4\) letras em \(4\) espaços disponíveis. \[ P_4=4!=24 \text{ anagramas. } \] Os anagramas ROILV, IROLV , ILROV e ILVRO são alguns dentre as \(24\) opções disponíveis.

  1. Considere os algarismos \(1\), \(2\), \(3\), \(4\) e \(5\). Quantos números pares com algarismos distintos, maiores do que \(100\) e menores do que \(1000\) podemos formar?
    Resp.: Queremos números do tipo: 124, 342, 452, 514. Então podemos dividir o problema em:

  • Caso 1: Números de \(3\) algarismos que terminam com \(2\). Trata-se de arranjo pois a ordem dos algarismos é importante e devemos escolher \(2\) algarismos dentre \(4\) opções disponíveis (\(1\), \(3\), \(4\) e \(5\)). \[ A_{4,2}=\frac{4!}{2!} = 4.3 = 12 \text{ números}, \]

  • Caso 2: Números de \(3\) algarismos que terminam com \(4\): devemos escolher \(2\) algarismos dentre \(4\) opções disponíveis (\(1\), \(2\), \(3\) e \(5\)). \[ A_{4,2}=\frac{4!}{2!} = 4.3 = 12 \text{ números}. \] Então podemos formar \(24\) números diferentes. Os números \(1342\), \(1352\), \(3142\), \(3152\), \(1324\) e \(3124\) são alguns dentre as \(24\) opções disponíveis.

  1. A uma reunião compareceram \(10\) pessoas. Todos os presentes cumprimentaram-se com um aperto de mão. Qual foi o número de apertos de mãos?
    Resp. Trata-se de combinação pois a ordem em que as pessoas apertam as mãos (Fulano aperta a mão de Ciclano ou Ciclano aperta a mão de Fulano) não é importante. Assim, devemos formar vários pares de pessoas de um grupo com \(10\) pessoas. \[ C_{10,2}=\frac{10!}{2!(10-2)!}=\frac{10.9.8!}{8!2!}=\frac{10.9}{2.1}=45 \text{ apertos de mãos. } \]

Permutação com elementos repetidos

Permutações com elementos repetidos ocorrem quando alguns elementos que compõem o agrupamento aparecem de forma repetida. A contagem do número de permutações é dada pela fórmula: \[ \begin{array}{lcl} P_n(n_1,n_2,\ldots,n_k)=\frac{n!}{n_1! n_2! \ldots,n_k!} \end{array} \] donde lê-se: “O número de permutações de \(n\) elementos sendo \(n_1\), \(n_2\), ,\(n_k\) elementos repetidos é igual a \(n!\) sobre o produto dos fatoriais de \(n_1\) até \(n_k\)”.

Exemplo 6: Quantos anagramas são possíveis formar com a palavra CASA?
Resp. A palavra CASA possui: \(4\) letras \((n=4)\) e duas vogais que se repetem \((n_1=2)\). \[ P_4(2)=\frac{4!}{2!} = 4.3 = 12 \text{ permutações com 4 letras sendo 2 letras aparecendo de forma repetida }. \] Logo temos \(12\) anagramas possíveis. Fazendo a listagem dos anagramas, temos: CASA, ACSA, ASCA, ASAC, SCAA, CSAA, AASC, AACS, CAAS, SAAC, SACA e ACAS.

  • Interpretação:
    • Como há \(2\) A’s repetidos temos que dividir pelo número de permutações destes dois A’s;
    • significa que estamos descartando os anagramas em que as letras A e A se permutam.

Arranjo com repetição

Arranjos com repetição ocorrem quando a seleção dos elementos para compor o agrupamento é feita com reposição. Um exemplo clássico é o problema da urna com bolinhas numeradas, em que ao pegar uma bolinha nós anotamos o número e devolvemos a mesma para a urna, para que esta tenha a chance de ser selecionada novamente. A contagem do número de arranjos é dada pela fórmula: \[ AR_{n,p}=\underbrace{n.n \ldots n}_{\text{ p vezes } } = n^p, \] e lê-se: “O número de arranjos com repetição de \(n\) elementos tomados \(p\) a \(p\) é igual a \(n\) elevado a \(p\)”.

  • Qual é o número total de anagramas que podemos formar juntando três letras quaisquer de um alfabeto de \(23\) letras?
    Resp. O número total é \(23^3=12167\) anagramas, começando com AAA e terminando com ZZZ.

  • Em uma urna há \(9\) bolinhas numeradas de \(1\) a \(9\). Seleciona-se \(2\) bolinhas com reposição. Quantos números podemos formar com estas duas bolinhas?
    Resp. Queremos formar números do tipo: 12, 22, 35, 49, 88, 93, 99.

    • Primeiro modo: sem usar fórmula de arranjo com repetição Na primeira posição temos \(9\) possibilidades e na segunda posição temos \(9\) possibilidades pois podemos repetir os números. Logo o total de possibilidades será \(9.9=81\).
    • Outro modo com fórmula de arranjo com repetição \[ AR_{9,2}=9^2, \] e lê-se: “O número de arranjos com repetição de \(9\) elementos tomados \(2\) a \(2\) é igual a \(9\) elevado a \(2\)”.

Exercícios

  1. Resolva as equações:
  1. \((x+3)!+(x+2)! = 8(x+1)!\) Resp.: \(S=\{0\}\);
  2. \(\frac{x!}{(x-2)!} = 30.\) Resp.: \(S=\{6\}\);
  3. \(\frac{(x+1)!}{(x-1)!}=56.\) Resp.: \(S=\{7\}\) ;
  4. \((x+5)!+(x+4)! = 35(x+3)!\) Resp.: \(S=\{1\}\);

  1. De quantos modos diferentes posso sortear duas pessoas para ganhar uma viagem para a Disney, de uma urna com \(10\) nomes de pessoas? Resp. \(45\).

  2. De um baralho com \(52\) cartas, são extraídas \(4\) cartas sucessivamente e sem reposição. Qual é o número de resultados possíveis, sem levar em conta a ordem das cartas? Resp. \(270725\).

  3. A uma reunião compareceram exatamente \(10\) casais. Todos os presentes (exceto maridos e respectivas mulheres) cumprimentaram-se com um aperto de mão. Qual foi o número de apertos de mãos? Resp. \(180\).

  4. Em um baralho de 52 cartas, cinco cartas são escolhidas sucessivamente. Quantas são as seqüências de resultados possíveis (sendo a ordem importante):

  1. Se a escolha for feita sem reposição? Resp.: 311875200.
  2. Se a escolha for feita com reposição? Resp.: 380204032.