Objetivos
- Definir combinação completa.
- Mostrar como obter a lista com todas as permutações com repetições de \(n\) elementos.
- Mostrar como calcular o número de permutações com repetições de \(n\) elementos.
- Exemplificar.
Seção 6.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 6.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, \tag{6.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 (6.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 (6.7.1) e que cada solução da Equação (6.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 (6.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 6.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*}
Nota 6.7.3.
As combinações completas dos objetos \(1, 2, 3, 4\) tomados 3 a 3 são:Teorema 6.7.4.
\begin{equation*}
CR_n^p = PR_{p+n-1}^{p, n-1} = C_{p+n-1}^p
\end{equation*}
Demonstraçã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 6.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 6.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 6.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*}
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}
\end{equation*}
Exemplo 6.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{?}\)
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*}
Substituindo, temos
\begin{equation*}
(x+1) + (y+2) + (z+4) = 15
\end{equation*}
ou seja
\begin{equation}
x + y + z = 8 \tag{6.7.2}
\end{equation}
Desta forma, o número de soluções de (6.7.2) será a solução do problema, pois, quando \(x=0\) teremos \(x_1=1\text{,}\) quando \(y=0\) teremos \(x_2=2\) e quando \(z=0\) teremos \(x_3=4\text{.}\) Portanto a resposta é
\begin{equation*}
CR_3^{8} = 45.
\end{equation*}
Exemplo 6.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?\tag{6.7.3}
\end{equation}
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}\tag{6.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 (6.7.3) com o conjunto das soluções da equação (6.7.5):
\begin{equation}
x_1 + x_2 + x_3 + x_4 + y = 50.\tag{6.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 (6.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{6.7.6}
\end{equation}
Cada solução da linha \(i\text{,}\) é uma solução de (6.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 (6.7.5) vai ser a solução da linha \(y\) de (6.7.4) .
Portanto a resposta é o número de solução da equação (6.7.5) que é dado por:
\begin{equation*}
CR_5^{50} = 316251.
\end{equation*}
Exemplo 6.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).
Quantas peças há no trominó, supondo n = 6?
Solução.Observe que os números estão em disposição circular, então vamos separar as peças em três tipos:
- Todos os lados com o mesmo valor. Cada peça pode ser formada de uma única forma.
- 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.
- 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 = 56+20 = 76.
\end{equation*}
Exercícios Exercícios
1.
Quantas são as soluções inteiras positivas de \(x+y+z+w = 15\text{?}\)
Resposta.
\(CR_{4}^{11} = 364.\)
2.
Quantas são as peças de um dominó comum?
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ó.
4.
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
5.
Quantos inteiros entre \(1\) e \(100.000.000\text{,}\) inclusive, possui a propriedade: "cada dígito é menor ou igual ao seu sucessor"?
Resposta.
24309
6.
De quantas maneiras é possível colocar 10 anéis diferentes em 8 dedos?
Resposta.
70572902400
