.Sala de Estudo: Combinação Completa

Link da Sala para dispositivos da Apple.

Combinação Completa


É extremamente comum nos depararmos com situações em que devemos tomar decisões para a escolha de alguns objetos e podemos optar por objetos de um mesmo tipo.
Por exemplo, imagine que você irá ao supermercado para comprar, digamos, sete refrigerantes para uma festa de aniversário e há apenas três opções de sabores disponíveis. De quantos modos essa compra pode ser feita?

Imagem extraída de Freepik

Para resolver esse, e outros problemas semelhantes, esta Sala de Estudo aborda uma técnica de contagem um pouco mais sofisticada e conhecida como Combinação Completa (ou Combinação com Repetição).




Provavelmente, você já deve ter estudado a Combinação Simples.
De modo geral, essa técnica expressa o número de maneiras de escolhermos [tex]p[/tex] objetos distintos entre [tex]n[/tex] objetos distintos disponíveis, com [tex]n\geq p.[/tex]
Grande parte dos livros didáticos representa esse número por [tex]~C_{n}^{p}~[/tex] ou [tex]\;C_{n,p}\;[/tex] ou ainda [tex]\,\left(\begin{array}{c}n\\p\end{array}\right)\,[/tex], e esta combinação é calculada por
[tex]\qquad \qquad C_{n}^{p}=C_{n,p}=\left(\begin{array}{c}n\\p\end{array}\right)=\dfrac{n!}{p!\cdot(n-p)!}[/tex].

Já a Combinação Completa expressa o número de modos de escolher [tex]p[/tex] objetos distintos ou não entre [tex]n[/tex] tipos de objetos distintos dados. Para usarmos uma notação diferente, representaremos esse número por [tex]CR\,_{n}^{p}[/tex].

E como vamos calcular esse número?

Voltemos ao nosso exemplo inicial…

De quantos modos podemos comprar [tex]7[/tex] refrigerantes com apenas [tex]3[/tex] sabores disponíveis?
Vamos interpretar esse problema da seguinte forma:
Chamemos de [tex]A[/tex], [tex]B[/tex] e [tex]C[/tex] as quantidades que iremos comprar do primeiro sabor, do segundo sabor e do terceiro sabor, respectivamente. Note que [tex]A[/tex], [tex]B[/tex] e [tex]C[/tex] devem ser números inteiros não negativos e que [tex]A+B+C=7[/tex].
Daí, comprar [tex]7[/tex] refrigerantes em um supermercado que oferece [tex]3[/tex] sabores diferentes é encontrar uma solução, com inteiros não negativos, para a equação [tex]\boxed{A+B+C=7}\,.[/tex]
Vamos listar algumas soluções para essa equação:

  • [tex]A=3[/tex], [tex]B=1[/tex] e [tex]C=3[/tex]
  • [tex]A=7[/tex], [tex]B=0[/tex] e [tex]C=0[/tex]
  • [tex]A=0[/tex], [tex]B=4[/tex] e [tex]C=3[/tex]
  • [tex]A=1[/tex], [tex]B=2[/tex] e [tex]C=4[/tex],

mas observamos que há várias outras.
Para que não haja a necessidade de enumerar exaustivamente todas as soluções dessa equação, ao imaginarmos uma possível solução iremos representá-la no esquema bola-traço.

No esquema bola-traço utilizaremos bolas e traços, como o próprio nome sugere.
A ideia é desenhar bolas idênticas (●), alinhadas horizontalmente, para representar os objetos que serão distribuídos, e separá-las em regiões, de acordo com a quantidade de incógnitas, utilizando traços ():
a quantidade de bolas será igual à soma das incógnitas, para que cada bola represente uma unidade no valor da incógnita;
a quantidade de traços será uma unidade a menos que a quantidade de incógnitas, para que cada traço separe duas incógnitas.

A próxima imagem mostra as quatro soluções anteriores no esquema bola-traço.

Assim, qualquer solução da equação [tex]\boxed{A+B+C=7}[/tex] nas condições do problema pode ser representada por uma fila com [tex]9[/tex] elementos: [tex]7[/tex] bolas (pois em cada solução devemos ter [tex]7[/tex] unidades distribuídas nas incógnitas) e [tex]2[/tex] traços (para separar três incógnitas usamos [tex]2[/tex] traços).

O total de filas com essa característica pode ser calculado utilizando a ideia de permutação com elementos repetidos.

Uma Permutação com Repetição consiste em todos os agrupamentos (filas, no nosso caso) ordenados que podemos formar com um conjunto finito de elementos, havendo dois ou mais que se repetem. Para calcular o número de permutações com repetição de [tex]n[/tex] objetos, calculamos a permutação de [tex]n[/tex], que é [tex]n![/tex], e dividimos pelo produto do fatorial de quantas vezes cada um dos objetos se repete.
Assim, o número de permutações de [tex]n[/tex] objetos dos quais um primeiro objeto se repete [tex]r_1[/tex] vezes; um segundo objeto se repete [tex]r_2[/tex] vezes; um terceiro, [tex]r_3[/tex] vezes; e assim sucessivamente até esgotar as repetições, com o objeto [tex]m[/tex] se repetindo [tex]r_m[/tex] vezes; é denotado por [tex]\,P_{n}^{r_1, \, r_2,\, r_3,\, \cdots, \, r_m}\,[/tex] e assim definido:
[tex] \boxed{P_{n}^{r_1, \, r_2,\, r_3,\, \cdots, \, r_m}=\dfrac{n!}{~r_1! \cdot r_2! \cdot r_3! \cdot \cdots \cdot r_m!~}}[/tex].

Logo, o número total de filas do nosso problema é dado por uma permutação com elementos repetidos; [tex]9[/tex] elementos, sendo [tex]7[/tex] bolas e [tex]2[/tex] barras:
[tex]\qquad P_{9}^{7,2}=\dfrac{9!}{7! \cdot 2!}=36.[/tex]
Observe que [tex]\, P_{9}^{7,2}=\dfrac{9!}{7! \cdot 2!}=C_{9}^{7}[/tex]; assim, de acordo com a notação definida para uma combinação completa, temos que:

[tex]\boxed{CR\,_{3}^{7}=P_{9}^{7,2}=C_{9}^{7}=\dfrac{9!}{7! \cdot 2!}=36}.[/tex]

Vejamos um outro exemplo de como encontrar o número de soluções inteiras não negativas de uma equação linear.

Quantas são as soluções inteiras não negativas da equação [tex]x_{1}+x_{2}+x_{3}+x_{4}=5[/tex]?
Aqui estão algumas soluções:

  • [tex]x_{1}=1[/tex], [tex]x_{2}=1[/tex], [tex]x_{3}=3[/tex] e [tex]x_{4}=0[/tex];
  • [tex]x_{1}=2[/tex], [tex]x_{2}=1[/tex], [tex]x_{3}=1[/tex] e [tex]x_{4}=1[/tex];
  • [tex]x_{1}=0[/tex], [tex]x_{2}=5[/tex], [tex]x_{3}=0[/tex] e [tex]x_{4}=0[/tex];

e suas respectivas representações no esquema bola-traço.

Dessa forma, qualquer solução da equação pode ser representada por uma fila com [tex]8[/tex] elementos: [tex]5[/tex] bolas e [tex]3[/tex] traços.


Logo, o número total de filas é:
[tex]\qquad \qquad P_{8}^{5,3}=\dfrac {8!}{5! \cdot 3!}=C_{8}^{5}=56[/tex],

número esse que representamos por: [tex]\boxed{CR\,_{4}^{5}=56}.[/tex]

O importante nesses dois exemplos é percebemos que podemos interpretar [tex]CR\,_{n}^{p}[/tex] de duas maneiras:

  • [tex]CR\,_{n}^{p}[/tex] é o número de modos de selecionar [tex]p[/tex] objetos, diferentes ou não, entre [tex]n[/tex] objetos distintos dados;
  • [tex]CR\,_{n}^{p}[/tex] é o número de soluções inteiras não negativas da equação [tex]x_{1}+x_{2}+\dots+x_{n}=p[/tex];

e que para calcular o número de soluções podemos utilizar o esquema bola-traço.

Generalizando, para calcular [tex]CR\,_{n}^{p}[/tex], ou seja, o número de soluções da equação [tex]x_{1}+x_{2}+\dots+x_{n}=p[/tex], necessitamos de [tex]p[/tex] bolas e [tex](n-1)[/tex] traços.
Portanto,
[tex]\qquad \qquad CR\,_{n}^{p}=P_{p+n-1}^{p, n-1}= \dfrac{(p+n-1)!}{p! \cdot (n-1)!}=C_{n+p-1}^{p}[/tex].

É importante observar que, quando utilizamos Combinações Simples de [tex]n[/tex] elementos tomados [tex]p[/tex] a [tex]p[/tex], devemos ter [tex]\boxed{~p \le n~}[/tex]. No entanto, tal restrição não se faz necessária no caso de Combinações com Repetição.
Vamos diferenciar as duas situações com um exemplo simples: a escolha de três letras dentre as letras A e B.

  • Não tem sentido usar combinação simples para determinar quantas escolhas são possíveis neste exemplo, já que nesse tipo de combinação não podemos repetir elementos. Dessa forma, não temos como apresentar escolhas com três elementos distintos, se só dispomos de dois tipos de letras.
  • No entanto, podemos utilizar combinação com repetição para quantificarmos as possíveis escolhas, uma vez que podemos repetir elementos na escolha de três letras dentre os dois tipos de letras apresentados:
      Cálculo: [tex]CR\,_{2}^{3}=P_{4}^{3, 1}= \dfrac{4!}{3! \cdot 1!}=4[/tex];
  •   Escolhas: AAA ; AAB ; ABB ; BBB.




Um vídeo para ajudar. . .


Assista ao vídeo abaixo para melhorar o seu entendimento e ampliar o seu conhecimento!
É só clicar na setinha.


Análise Combinatória – Combinação Completa
Vídeo extraído do Portal da Matemática – Professor Josimar Silva




O objetivo principal desta Sala não é a notação em si (mesmo sabendo de sua importância), mas sim resolver problemas de contagem utilizando essa nova técnica. Mas, antes, lembre-se de que:
[tex]~\boxed{C_{n}^{p}=\dfrac{n!}{p!\cdot(n-p)!}}~[/tex] é o número de maneiras de escolhermos [tex]p[/tex] objetos distintos em [tex]n[/tex] objetos distintos disponíveis. Aqui, necessariamente, [tex]p\leq n.[/tex]
[tex]~\boxed{CR\,_{n}^{p}=C_{n+p-1}^{p}= \dfrac{(p+n-1)!}{p! \cdot (n-1)!}}[/tex] é o número de maneiras de escolhermos [tex]p[/tex] objetos distintos ou não entre [tex]n[/tex] objetos distintos disponíveis. Aqui, a restrição de que [tex]\, p\leq n[/tex] não é necessária.
Particularmente, o número [tex]CR\,_{n}^{p}[/tex] corresponde à quantidade de soluções inteiras não negativas de uma equação da forma [tex]x_{1}+x_{2}+\dots +x_{n}=p\,.[/tex]

Agora, vamos aos problemas!

Boa diversão!!!

Problema 1 (Extraído da Apostila PIC- OBMEP)
Uma professora tem [tex]3[/tex] bolas de gude para distribuir para [tex]5[/tex] meninos (digamos, Alfredo, Bernardo, Carlos, Diogo e Eduardo).
De quantos modos ela pode fazer essa distribuição:
a) Supondo que ela dê as bolas para [tex]3[/tex] alunos distintos?
b) Supondo que os contemplados possam ganhar mais de uma bola?

Problema 2
Num restaurante, são oferecidos [tex]4[/tex] tipos de carne, [tex]5[/tex] tipos de massa, [tex]8[/tex] tipos de salada e [tex]6[/tex] tipos de sobremesa.
De quantas maneiras diferentes podemos escolher uma refeição composta por [tex]2[/tex] carnes (distintas ou não), [tex]1[/tex] massa, [tex]2[/tex] saladas (distintas ou não) e [tex]1[/tex] sobremesa?

Problema 3
Quantas são as soluções inteiras não negativas da inequação [tex]x+y+z \leq 4[/tex]?

Problema 4
Quantas são as soluções inteiras da equação [tex]A+B+C=10[/tex], sabendo que [tex]A \geq 1[/tex], [tex]B \geq 2[/tex] e [tex]C \geq 3[/tex]?

Problema 5
Quantos são os anagramas da palavra [tex]INSTITUTO[/tex] que não possuem duas letras [tex]T[/tex] juntas?
Observação: Anagrama é toda palavra formada com as mesmas letras de uma dada palavra, podendo ou não ter sentido na linguagem usual. Assim, os anagramas de uma dada palavra são as palavras obtidas pelo “embaralhamento” das letras da palavra original (manter as letras mudando ou não a ordem).

Problema 6
De quantas maneiras é possível colocar [tex]6[/tex] anéis diferentes em [tex]4[/tex] dedos da mão? (Considere apenas os casos em que haja pelo menos um anel em cada dedo.)

Para o próximo problema, talvez você precise relembrar um pouquinho de probabilidade. Se quiser, visite esta página do nosso Blog!

Problema 7 (PUC/RJ – 2015)
Eugênio tem três dados que são dodecaedros regulares, com os números inteiros de [tex]1[/tex] a [tex]12[/tex] escritos nas faces.

Eugênio sorteia um número inteiro jogando os três dados simultaneamente e somando os três números obtidos (ou seja, ele soma os três números que aparecem na face de cima de cada um dos dados).
a) Qual é a probabilidade de que o número sorteado seja igual a [tex]36[/tex]?
b) Qual é a probabilidade de que o número sorteado seja igual a [tex]30[/tex]?
c) Qual é a probabilidade de que o número sorteado seja maior ou igual a [tex]30[/tex]?




Agora é com vocês….
 
Que tal fazer alguns exercícios?

Exercício 1: (UERJ – 2017) Uma criança possui um cofre com [tex]45[/tex] moedas: [tex]15[/tex] de dez centavos, [tex]15[/tex] de cinquenta centavos e [tex]15[/tex] de um real. Ela vai retirar do cofre um grupo de [tex]12[/tex] moedas ao acaso. Há vários modos de ocorrer essa retirada. Admita que as retiradas são diferenciadas apenas pela quantidade de moedas de cada valor. Determine quantas retiradas distintas, desse grupo de [tex]12[/tex] moedas, a criança poderá realizar.

Exercício 2: (UDESC 2012 – Adaptada) As frutas são alimentos que não podem faltar na nossa alimentação, pelas suas vitaminas e pela energia que nos fornecem. Vera consultou um nutricionista que lhe sugeriu uma dieta que incluísse a ingestão de três frutas diariamente, dentre as seguintes opções: abacaxi, banana, caqui, laranja, maçã, pera e uva. Suponha que Vera siga rigorosamente a sugestão do nutricionista, ingerindo três frutas por dia. De quantos modos diferentes Vera pode montar sua dieta diária?

Exercício 3: (ENEM – 2017) Um brinquedo infantil caminhão-cegonha é formado por uma carreta e dez carrinhos nela transportados, conforme a figura.

No setor de produção da empresa que fabrica esse brinquedo, é feita a pintura de todos os carrinhos para que o aspecto do brinquedo fique mais atraente. São utilizadas as cores: amarelo, branco, laranja e verde, e cada carrinho é pintado apenas com uma cor. O caminhão-cegonha tem uma cor fixa. A empresa determinou que em todo caminhão-cegonha deve haver pelo menos um carrinho de cada uma das quatro cores disponíveis. Mudança de posição dos carrinhos no caminhão-cegonha não gera um novo modelo do brinquedo. Com base nessas informações, quantos são os modelos distintos do brinquedo caminhão-cegonha que essa empresa poderá produzir?
a) [tex]C_{6,4}[/tex]
b) [tex]C_{9,3}[/tex]
c) [tex]C_{10,4}[/tex]
d) [tex]6^{4}[/tex]
e) [tex]4^{6}[/tex]

Exercício 4: Quantos são os anagramas da palavra BÚLGARO que não possuem duas vogais adjacentes?

Exercício 5: (OBMEP – 2018) Helena tem três caixas com [tex]10[/tex] bolas em cada uma. As bolas dentro de uma mesma caixa são idênticas, e as bolas em caixas diferentes possuem cores distintas. De quantos modos ela pode escolher [tex]15[/tex] bolas dessas três caixas?

a) [tex]91[/tex]
b) [tex]136[/tex]
c) [tex]150[/tex]
d) [tex]200[/tex]
e) [tex]210[/tex]

Exercício 6: (IME – 2010) Um trem conduzindo [tex]4[/tex] homens e [tex]6[/tex] mulheres passa por seis estações. Considere que cada um destes passageiros irá desembarcar em qualquer uma das seis estações e que não existe distinção entre os passageiros de mesmo sexo. O número de possibilidades distintas de desembarque destes passageiros é:
a) [tex]1287[/tex]
b) [tex]14112[/tex]
c) [tex]44200[/tex]
d) [tex]58212[/tex]
e) [tex]62822[/tex]

Exercício 7: (XXV OBM) O tenista Berrando Gemigemi tem [tex]30[/tex] dias para preparar-se para um torneio. Se ele treina [tex]3[/tex] dias seguidos ele tem fadiga muscular. Ele, então, decide que, durante esses [tex]30[/tex] dias, irá treinar [tex]20[/tex] dias, sem nunca treinar [tex]3[/tex] dias seguidos, e descansar nos outros [tex]10[/tex] dias. De quantas maneiras diferentes ele pode escolher os [tex]10[/tex] dias de descanso?



Equipe COM – OBMEP

Referências:
[1] A Matemática do Ensino Médio (volume 2): Coleção do Professor de Matemática – Elon Lages Lima; Paulo Cesar Pinto Carvalho; Eduardo Wagner e Augusto César Morgado.
[2] A Matemática do Ensino Médio (volume 4): Coleção do Professor de Matemática – Elon Lages Lima; Paulo Cesar Pinto Carvalho; Eduardo Wagner e Augusto César Morgado.
[3] Matemática Discreta: Coleção Profmat – Augusto César Morgado; Paulo Cesar Pinto Carvalho.
[4] Análise Combinatória e Probabilidade – Augusto César Morgado; João Bosco Pitombeira de Carvalho; Paulo Cesar Pinto Carvalho e Pedro Fernandez.
[5] Círculo Matemático de Moscou: Problemas semana-a-semana – Sergey Dorichenko.
[6] Círculos Matemáticos: A Experiência Russa – Dimitri Fomin; Sergey Genkin e Ilia Itenberg.
[7] Notas de aulas do professor Cleber Gouvêa Fernandes (IFRJ).

Link permanente para este artigo: http://clubes.obmep.org.br/blog/sala-de-estudo-combinacao-completa/