[skip-to-content]

Seção 1.7 Combinações Completas

Na combinação completa (ou combinação com repetição), contamos o número de maneiras de escolher elementos de um conjunto, sendo permitido escolher um elemento repetidamente. Antes de formalizar o conceito, começamos com um exemplo que ilustra bem essa noção.

Exemplo 1.7.1.

Em uma determinada sorveteria há 6 sabores disponíveis, de quantos modos pode ser feito um pedido de uma taça com 3 bolas de sorvete?

Solução

Denote cada sabor por um número entre \(1\) e \(6\text{.}\) Note que este problema é equivalente ao de encontrar o número de soluções inteiras da equação:

\begin{equation} x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3, ~~~ \text{ com } x_i \geq 0, \label{eq-comb-completa}\tag{1.7.1} \end{equation}

na qual, cada \(x_i, i\in\{1, 2, 3, 4, 5, 6\}\) representa a quantidade de bolas de sorvete com sabor \(i\text{.}\) Claramente, temos a restrição \(x_i\geq 0\text{,}\) pois não podemos pegar uma quantidade negativa de bolas de sorvete.

Vamos mostrar que o problema de encontrar o número de soluções (1.7.1) é equivalente a encontrar o número de permutações com repetições de uma sequência com \(3\) elementos de um tipo e \(5\) elementos de outro tipo.

Escreva de \(x_1\) até \(x_6\text{,}\) entre uma incógnita e outra coloque na linha de baixo um traço vertical. Para representar a quantidade bolas de sorvete com sabor \(1\) ou \(6\text{,}\) coloque a respectiva quantidade de bolas antes do primeiro traço ou depois do último traço, respectivamente. Para representar a quantidade de bolas de sorvete com sabor \(i\text{,}\) com \(i\in \{2, 3, 4, 5\}\text{,}\) coloque a quantidade de bolas abaixo de \(x_i\text{,}\) entre dois traços consecutivos. Assim, a solução

\begin{equation*} x_1=1, ~ x_5=2, ~ x_i=0, ~~ i\in \{2, 3, 4, 6\} \end{equation*}

é representada por:

Observe que cada permutação dessa representação de traços e bolas é uma solução da Equação (1.7.1) e que cada solução da Equação (1.7.1) pode ser representada com traços de bolas (Existe uma bijeção entre as duas coisas).

Portanto, para encontrar o número de soluções da Equação (1.7.1), basta calcular

\begin{equation*} PR_8^{5, 3} = 56, \end{equation*}

pois, temos 5 traços e 3 bolas, então estamos permutando um total de 8 elementos, sendo 5 de um tipo e 3 de outro tipo.

Definição 1.7.2.

O número de combinações completas de \(n\) elementos, tomados \(p\) a \(p\) é o número de formas de escolher \(p\) elementos dentre \(n\) disponíveis, podendo escolher repetidamente os objetos, até obter a quantidade \(p\text{.}\)

O número de combinações completas de \(n\) elementos, tomados \(p\) a \(p\) é denotado por:

\begin{equation*} CR_n^{p} \end{equation*}
Observação 1.7.3.
As combinações completas dos objetos \(1, 2, 3, 4\) tomados 3 a 3 são:
Calcular \(CR_n^p\) é o mesmo que encontrar o número de soluções da equação:
\begin{equation*} x_1 + x_2 + x_3 + \ldots + x_n = p, ~~~ \text{ com } x_i \geq 0 \end{equation*}
Usando a ideia da representação de "bolas e traços" da Solução do (Exemplo 1.7.1) vamos ficar com \(p\) bolas e \(n-1\) traços. O cálculo do número de permutações destes \(p+n-1\) objetos com \(p\) objetos de um tipo e \(n-1\) objetos de outro tipo é dado por:
\begin{equation*} PR_{p+n-1}^{p, n-1} = C_{p+n-1}^p \end{equation*}
Tecnologia 1.7.5.

Para obter o número de combinações completas de \(n\text{,}\)tomados \(p\) a \(p\text{,}\) usamos o código binomial(p+n-1, p).

Exemplo 1.7.6.

Quantas são as soluções inteiras e não negativas de

\begin{equation*} x_1 + x_2 + x_3 + \ldots + x_{10} = 20? \end{equation*}
Solução

O número de soluções desta equação, com \(x_i\in \mathbb{Z} \text{ e } x_i\geq 0, i\in\{1, 2, \ldots, 10\}\) é o número de combinações completas de 10 elementos, tomados 20 a 20:

\begin{equation*} CR_{10}^{20} = PR_{29}^{20,9}=10015005. \end{equation*}
Exemplo 1.7.7.

Quantas são as soluções inteiras da equação

\begin{equation*} x_1 + x_2 + x_3 = 15, \end{equation*}

com \(x_1>0\text{,}\) \(x_2\geq 2\) e \(x_3 \geq 4\text{?}\)

Solução

Defina

\begin{equation*} x_1 = x+1, \end{equation*}
\begin{equation*} x_2 = y+2 \end{equation*}
\begin{equation*} x_3 = z+4 \end{equation*}

Fazendo a substituição na equação do problema, temos

\begin{equation*} (x+1) + (y+2) + (z+4) = 15, \end{equation*}

ou seja,

\begin{equation} x + y + z = 8. \label{eq-exem-178}\tag{1.7.2} \end{equation}

Desta forma, o número de soluções interias e não negativas de (1.7.2) será o número de soluções da equação original, pois, quando \(x\geq0\) teremos \(x_1\geq1\text{,}\) quando \(y\geq0\) teremos \(x_2\geq2\) e quando \(z\geq0\) teremos \(x_3\geq4\text{.}\) Portanto, a resposta é

\begin{equation*} CR_3^{8} = PR_{10}^{8,2} = 45. \end{equation*}
Exemplo 1.7.8.

Quantas são as soluções inteiras e não negativas de

\begin{equation} x_1 + x_2 + x_3 + x_4 \leq 50?\label{sol-desi}\tag{1.7.3} \end{equation}
Solução

Observe que uma possibilidade seria calcular o número de soluções de cada um dos casos:

\begin{equation} \begin{cases} x_1 + x_2 + x_3 + x_4 = 0,\\ x_1 + x_2 + x_3 + x_4 = 1\\ \vdots \\ x_1 + x_2 + x_3 + x_4 = 50.\end{cases}\label{sol-igual}\tag{1.7.4} \end{equation}

A soma do número de soluções de cada um dos casos é a resposta, no entanto, é inviável fazer tal cálculo. Felizmente temos outra forma de resolver este problema.

Observe que existe uma bijeção entre o conjunto das soluções de (1.7.3) com o conjunto das soluções da equação (1.7.5):

\begin{equation} x_1 + x_2 + x_3 + x_4 + y = 50.\label{sol-desi2}\tag{1.7.5} \end{equation}

Para entender a bijeção, observe o seguinte. Somando \(50-i, i\in \{0, 1, 2, \ldots, 50\}\text{,}\) nos dois lados da igualdade, na linha \(i, i\in \{0, 1, 2, \ldots, 50\}\) de (1.7.4), não mudamos absolutamente nada e ficamos com:

\begin{equation} \begin{cases} x_1 + x_2 + x_3 + x_4 + 50 = 0 + 50,\\ x_1 + x_2 + x_3 + x_4 + 49 = 1 +49 \\ \vdots \\ x_1 + x_2 + x_3 + x_4 + 0 = 50+0.\end{cases}\tag{1.7.6} \end{equation}

Cada solução da linha \(i\text{,}\) é uma solução de (1.7.5) com o valor de \(y\) igual a \(50-i\text{.}\) E para cada \(y\in \{0, 1, 2, \ldots, 50\}\) a solução de (1.7.5) vai ser a solução da linha \(y\) de (1.7.4) .

Portanto a resposta é o número de solução da equação (1.7.5) que é dado por:

\begin{equation*} CR_5^{50} = PR_{54}^{50,4} =316251. \end{equation*}
Exemplo 1.7.9.
(VESTIBULAR UFPE – UFRPE / 1998 2ª ETAPA)

Semelhante ao dominó, mas feito de pedras triangulares equiláteras, o jogo de trominó apresenta na face triangular superior um certo número de pontos com repetições, escolhidos de 1 a n, dispostos ao longo de cada aresta (ver figura).

Figura 1.7.10. Uma das peças com os valores 1, 2 e 4.

Quantas peças há no trominó, supondo \(n = 6\text{?}\)

Solução

Observe que os números estão em disposição circular, então vamos separar as peças em três tipos:

  1. Todos os lados com o mesmo valor. Cada peça pode ser formada de uma única forma.
  2. Dois lados possuem um valor e o terceiro lado possui um valor diferente. Cada peça pode ser formada de uma única forma, pois o número de permutações circulares com 3 elementos é 2, mas como temos duas entradas iguais, precisamos dividir por 2.
  3. Cada lado possui um valor diferente. Cada peça pode ser formada de duas formas, pois o número de permutações circulares com 3 elementos é 2.

Inicialmente, vamos contar como se em cada tipo, as peças só pudessem ser formadas de uma forma, depois vamos acrescentar a quantidade de peças do terceiro tipo, que fica faltando nessa contagem inicial.

Temos que escolher os valores de cada um dos 3 lados de cada peça do trominó. Como os valores vão de 1 até 6 e são 3 lados, o número de peças do trominó (sem contar as permutações circulares) para \(n=6\) é o número de soluções inteiras não negativas da equação:

\begin{equation*} x_1 + x_2 + x_3 + x_4 + x_ 5 + x_ 6 = 3, \end{equation*}

que é dado por \(CR_6^3\text{.}\)

Agora precisamos contar as peças, do terceiro tipo, que estão faltando. Como os três valores são diferentes, temos 6 opções de valores para escolher 3 e para cada escolha, temos duas formas de organizar na peça do trominó, portanto o número de peças desse tipo é:

\begin{equation*} 2\times C_6^3 =40. \end{equation*}

Já que, a metade das peças do terceiro tipo foram contadas uma vez pela combinação completa, \(CR_6^3\text{,}\) a quantidade total de peças é:

\begin{equation*} CR_6^{3} + C_6^3= PR_{8}^{3,5} + C_6^3 = 56+20 = 76. \end{equation*}

Exercícios 1.7.1 Exercícios

1.

Quantas são as soluções inteiras positivas de \(x+y+z+w = 15\text{?}\)

Resposta

364

Solução

Como as soluções precisam ser positivas, precisamos fazer as seguintes mudanças de variáveis:

\begin{equation*} x = a+1,\quad y=b+1,\quad z=c+1,\quad w=d+1. \end{equation*}

Assim, a equação original se transforma em

\begin{equation*} a+b+c+d=11,\quad \text{com } a,b,c,d\geq 0. \end{equation*}

O número de soluções inteiras e não negativas da equação anterior é

\begin{equation*} CR_{4}^{11} = PR_{14}^{11, 3} = 364. \end{equation*}
2.

Quantas são as peças de um dominó comum?

Resposta

28

Solução

Sejam \(x_i, i\in\{0, 1, 2, \ldots, 6\}\) variáveis. Cada solução não negativa da equação:

\begin{equation*} x_0+x_1+x_2+\cdots+x_6 = 2, \end{equation*}

representa uma pedra do dominó. Portanto, o número de pedras do dominó é

\begin{equation*} CR_{7}^2 = 28. \end{equation*}
3.

(UFPE 2012) As pedras de um dominó usual são compostas por dois quadrados, com 7 possíveis marcas (de zero pontos até 6 pontos). Quantas pedras terá um dominó se cada quadrado puder ter até 9 pontos? Veja no desenho abaixo um exemplo de uma nova pedra do dominó.

Resposta

55

Solução

Sejam \(x_i, i\in\{0, 1, 2, \ldots, 9\}\) variáveis. Cada solução não negativa da equação:

\begin{equation*} x_0+x_1+x_2+\cdots+x_9 = 2, \end{equation*}

representa uma pedra do dominó. Portanto, o número de pedras do dominó é

\begin{equation*} CR_{10}^2 = 55. \end{equation*}
4.

(Enem 2017 - Modificado) 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 três carrinhos amarelos, dois laranjas e pelo menos um das outras 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?

Resposta

20

Solução

Denote as cores por \(x_1, x_2, x_3, x_4\text{,}\) então o número de modelos distintos é igual ao número de soluções da equação

\begin{equation*} x_1+x_2+x_3+x_4 = 10, \end{equation*}

com \(x_i\geq 1,~ i\in\{1,2,3,4\} \text{.}\) Vazendo uma mudança de variáveis, ficamos com

\begin{equation*} \overbrace{a+3}^{x_1}+\overbrace{b+2}^{x_2}+\overbrace{c+1}^{x_3}+\overbrace{d+1}^{x_4} = 10. \end{equation*}

Portanto, queremos calcular o número de soluções da equação

\begin{equation*} a+b+c+d = 3, \end{equation*}

com \(a,b,c,d\geq 0\text{,}\) que é dado por \(PR_{6}^{3,3} = 20.\)

5.

Um bar vende três tipos de cerveja: Heineken, Spaten e Budweiser. De quantos modos uma pessoa pode comprar 7 garrafas de cerveja?

Resposta

36

Solução

O número de soluções deste problema é o mesmo que o número de solução inteiras, não negativas da equação:

\begin{equation*} x_1 + x_2 + x_3 = 7. \end{equation*}

Portanto a resposta é

\begin{equation*} PR_9^{7, 2} = 36. \end{equation*}
6.

Quantas são as soluções inteiras não-negativas de \(x_1+x_2+x_3+x_4+x_5 = 8\) nas quais \(x_1>x_2\text{?}\)

Resposta

200

Solução

Precisamos separar em casos.

  • Caso \(x_2=0\text{,}\) \(x_1\geq 1\text{,}\) fazendo a mudança de variável \(x_1=a+1\text{,}\) ficamos com a equação: \((a+1) +0+ x_3+x_4+x_5 = 8\) que é equivalente a
    \begin{equation*} a+ x_3+x_4+x_5 = 7. \end{equation*}
    O número de soluções inteiras e não negativas é \(PR_{10}^{7, 3}.\)
  • Caso \(x_2=1\text{,}\) \(x_1\geq 2\text{,}\) fazendo a mudança de variável \(x_1=a+2\text{,}\) ficamos com a equação: \((a+2) +1+ x_3+x_4+x_5 = 8\) que é equivalente a
    \begin{equation*} a+ x_3+x_4+x_5 = 5. \end{equation*}
    O número de soluções inteiras e não negativas é \(PR_{8}^{5, 3}.\)
  • Caso \(x_2=2\text{,}\) \(x_1\geq 3\text{,}\) fazendo a mudança de variável \(x_1=a+3\text{,}\) ficamos com a equação: \((a+3) +2+ x_3+x_4+x_5 = 8\) que é equivalente a
    \begin{equation*} a+ x_3+x_4+x_5 = 3. \end{equation*}
    O número de soluções inteiras e não negativas é \(PR_{6}^{3, 3}.\)
  • Caso \(x_2=3\text{,}\) \(x_1\geq 4\text{,}\) fazendo a mudança de variável \(x_1=a+4\text{,}\) ficamos com a equação: \((a+4) +3+ x_3+x_4+x_5 = 8\) que é equivalente a
    \begin{equation*} a+ x_3+x_4+x_5 = 1. \end{equation*}
    O número de soluções inteiras e não negativas é \(PR_{4}^{3,1}.\)

Portanto, somando os resultados de cada caso obtemos:

\begin{equation*} PR_{10}^{7, 3} + PR_{8}^{5, 3} + PR_{6}^{3, 3} + PR_{4}^{3,1} = 200. \end{equation*}
7.

De quantos modos podem ser pintados 15 objetos iguais usando 6 cores diferentes?

Resposta

15504

Solução

Como as cores são diferentes, defina \(x_i,~ i\in {1, 2, \ldots, 6}\text{,}\) como a quantidade de objetos pintados na cor \(i\text{.}\) O número de modos de pintar os objetos é o número de soluções inteiras e não negativas da equação:

\begin{equation*} x_1+x_2+x_3+x_4+x_5+x_6 = 15. \end{equation*}

O número de soluções é \(PR_{20}^{15, 5} = 15504.\)

8.

Quantos inteiros entre \(1\) e \(100.000.000\text{,}\) inclusive, possui a propriedade: "cada dígito é menor ou igual ao seu sucessor"? (sucessor da esquerda para a direita)

Resposta

24309

Solução

Observe que o número \(100.000.000\) está fora, o maior número que deve ser levado em consideração é o \(99.999.999\text{.}\) Precisamos contar o número de dígitos \(i,~ i \in\{0, 1, 2, \ldots, 9\} \text{,}\) sendo que vamos sempre escolher 8 dígitos. Uma vez escolhido os dígitos, temos apenas uma maneira de ordená-los. Os números com menos que 8 dígitos são que o escolhemos pelo menos um zero, porém não podemos escolher todos os dígitos iguais a zero. O número total de maneiras de fazer isto é o número de soluções inteiras e não negativas da equação:

\begin{equation*} x_0+x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8+x_9 = 8, \end{equation*}

menos \(1\text{,}\) que é o número de maneiras de escolher todos os dígitos iguais a zero. A resposta é:

\begin{equation*} PR_{17}^{9,8} -1 = 24310-1=24309. \end{equation*}
9.

De quantas maneiras é possível colocar 4 anéis diferentes em 8 dedos?

Resposta

7920

Solução

Defina cada dedo como uma variável \(x_i\text{.}\) O número de soluções inteiras não negativas da equação

\begin{equation*} x_1+x_2+\cdots+x_8=4, \end{equation*}

é o número de maneiras de colocar os anéis nos 8 dedos, sem levar em considereção que os anéis são diferentes. Para contar o total de maneiras levando em considereção que os anéis são diferentes, multiplicamos pelo número de maneiras de ordenar os anéis. A resposta é

\begin{equation*} CR_8^4\times 4! = PR_{11}^{4, 7}\times 4! = 7920. \end{equation*}