Combinações

Usamos combinações quando escolhemos certa quantidade de objetos de um conjunto e a ordem em que os escolhemos não importa. Um problema típico é o de uma loteria 6 de 49: temos 49 números no globo de sorteio e retiramos 6 deles, sem importar a ordem em que são retirados.

Dedução da fórmula

Roda da fortuna

Considere um conjunto M, por exemplo M = {a, b, c, d, e}. Então uma combinação de k elementos é um subconjunto K ⊆ M que contém exatamente k elementos. Como K é um conjunto, é claro que a ordem não importa. Assim, uma combinação de três elementos do conjunto M poderia ser {a, b, d} ou {b, c, d}.

A diferença em relação aos arranjos é que, nos arranjos, a ordem importava, então (a, b, e) e (e, b, a) são arranjos diferentes, mas são a mesma combinação, porque tanto (a, b, e) quanto (e, b, a) contêm os mesmos elementos; que estejam em outra ordem não nos interessa nas combinações.

Mas podemos usar os arranjos para obter a fórmula do número de todas as combinações diferentes. Sabemos que o número de arranjos de k elementos de um conjunto com n elementos é

$A_{n, k} = \frac{n!}{(n - k)!} .$

Se contássemos todos os arranjos de três elementos do conjunto anterior M = {a, b, c, d, e}, obteríamos A_5,3 = 60 arranjos diferentes. No entanto, para cada terna teríamos também todas as suas permutações. Ou seja, teríamos a terna abc, mas também as ternas acb, bac, bca, cab e cba. São seis arranjos diferentes, mas é uma só combinação, porque todos têm os mesmos elementos.

Se temos uma terna, quantas permutações diferentes dessa terna existem? Exatamente 3!. Em outras palavras, existem exatamente 3! vezes mais arranjos de três elementos do que combinações de três elementos. Em vez de contar uma combinação, contamos 3! arranjos a mais, um para cada permutação da terna dada. Portanto, se dividirmos o número de arranjos por 3!, obtemos o número de combinações.

Podemos generalizar o procedimento anterior e dizer que, se procuramos o número de todas as combinações diferentes de k elementos de um conjunto com n elementos, esse número, que denotamos por C_n,k, é igual a

$C_{n, k} = \frac{A_{n, k}}{k!},$

isto é, o número de arranjos dividido por k!, que é o número de permutações de cada k-upla. Podemos simplificar a fórmula escrevendo a fórmula do cálculo dos arranjos:

$C_{n, k} = \frac{A_{n, k}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Exemplo: o número de combinações de dois elementos do conjunto {a, b, c} é

$C_{3, 2} = \frac{3!}{1! \cdot 2!} = 3$

e essas combinações são: {a, b}, {a, c} e {b, c}. Para as combinações de três elementos do conjunto original M = {a, b, c, d, e} obteríamos o número

$C_{5, 3} = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

e essas combinações são: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Número binomial

A notação anterior da fórmula com C_n,k não é muito usada, e no lugar dela usamos o chamado número binomial. O número binomial tem esta forma

$(\binom{n}{k})$

É uma espécie de fração sem traço de fração (que você, por hábito, vai escrever mesmo assim), mas com parênteses (que não são opcionais, eles precisam estar lá). O número binomial se lê “n sobre k”. O valor do número binomial é igual a C_n,k.

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Assim, se temos um conjunto com 5 elementos e escolhemos quádruplas, o número total delas será

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Relações básicas

Para o número binomial e n ∈ ℕ^* vale:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Além disso, para n, k ∈ ℕ e k ≤ n vale

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

E para n, k ∈ ℕ e k < n vale

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Calculadora

A calculadora a seguir calcula o número binomial n sobre k.

Exercícios resolvidos

Vamos começar com a loteria já mencionada. Nela, são sorteadas 6 bolas de um globo que contém 49 bolas. Quantos resultados diferentes podem sair?

Em primeiro lugar: a ordem em que os números são sorteados importa? Não importa, apostamos apenas nos números, não na ordem deles. Vamos usar combinações. Temos 49 bolas ao todo, sorteamos 6 bolas e obtemos o número binomial

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13.983 .816$

Existem ao todo 13.983.816 resultados que podem ser sorteados. O que, aliás, nos dá a probabilidade de ganhar com uma aposta: 1/13.983.816, o que é 0,00000715112%.
Rafael, conhecido paquerador, está numa festa junina em que há 13 garotas lindas pelas quais ele se interessaria. Rafael sabe que consegue encantar 4 garotas diferentes por noite. Entre quantos quartetos diferentes ele pode escolher?

Esse é novamente um exemplo simples de combinações: a ordem não importa, o Rafael vai se sair tão bem com a primeira garota quanto com a última. Obtemos, assim, um conjunto de 13 garotas, do qual sempre escolhemos 4. Isso leva ao número binomial

$(\binom{13}{4}) = 715.$
Você tem um grupo de cinquenta pessoas, metade homens e metade mulheres. Quantas ternas diferentes de pessoas existem, se elas não podem ser formadas só por pessoas de um mesmo sexo (isto é, na terna não podem aparecer três homens nem três mulheres)?

Essa já é uma combinação um pouco mais complicada. Se excluirmos as ternas de um só sexo, sobram apenas duas possibilidades de composição da terna: dois homens e uma mulher ou um homem e duas mulheres, e o número de combinações do primeiro grupo (dois homens e uma mulher) será igual ao do segundo grupo. Basta, então, calcular o número de combinações do primeiro grupo e multiplicá-lo por dois. Agora é de novo uma moleza. Determinamos o número de combinações de pares de homens, que é vinte e cinco sobre dois, e multiplicamos pelo número de combinações de uma mulher (que é vinte e cinco, veja as relações básicas acima, mais precisamente a segunda linha). Esse resultado só precisa ser multiplicado por dois, e temos o resultado final.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
Em uma caixa há 15 produtos, dos quais 4 são defeituosos. De quantas maneiras é possível escolher 6 produtos de modo que
- nenhum seja defeituoso? Nesse caso escolhemos 6 produtos entre os 15 − 4 = 11 produtos que não são defeituosos. Obtemos, assim, o número binomial
  
  $(\binom{11}{6}) = 462.$
- exatamente um produto seja defeituoso? Escolhemos, então, um conjunto que contém 5 produtos bons e 1 defeituoso. Temos ao todo 11 produtos bons e 4 defeituosos. Usamos o princípio multiplicativo e obtemos o resultado:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- no máximo um seja defeituoso? Para resolver, usamos os resultados anteriores. Sabemos que temos 462 possibilidades de escolher exatamente 6 produtos bons e temos 1848 possibilidades de escolher cinco produtos bons e um defeituoso. Usamos, então, o princípio aditivo, somamos esses resultados e temos o resultado que queremos, isto é, no máximo um produto defeituoso (= nenhum defeituoso ou exatamente um). O resultado é: 462 + 1848 = 2310.

Capítulos: Análise combinatória, Arranjos, Permutações, Combinações, Arranjos com repetição, Combinações com repetição, Quantos PINs diferentes existem?

« Anterior: Permutações

Próximo: Arranjos com repetição »