Combinações Completas ou com Repetição

Prévia do material em texto

1 
 
 
 
 
 
1. Introdução: 
Quatro amigos chegam a uma sorveteria para comprar, cada um deles, um único 
sorvete. 
De quantos modos é possível esses amigos comprar os quatro sorvetes, se a 
sorveteria os oferece em 7 sabores? 
É claro que dois ou mais amigos podem comprar sorvetes do mesmo sabor, portanto, este 
não é um problema de combinação simples cuja resposta seria 
( )
4
7
7! 7!
35
4! 7 4 ! 4!3!
C = = =
−
 
este seria o modo de escolher 4 sabores diferentes entre os 7 sabores oferecidos. 
A resposta deste problema é o número de combinações com repetições ou completas de 
classe 4 de 7 objetos distintos, isto é, o número de escolher 4 objetos entre os 7 objetos 
distintos, valendo escolher o mesmo objeto mais de uma vez. 
Seja as variáveis 1 2 3 4 5 6 7, , , , , ,x x x x x x x representando os 7 sabores de sorvetes oferecidos, 
onde 1x é a quantidade que eles vão comprar de sorvetes do 1º sabor, 2x é a quantidade 
que eles vão comprar de sorvetes do 2º sabor,..., 7x é a quantidade que eles vão comprar de 
sorvetes do 7º sabor. É claro que os valores das variáveis 1 2 3 4 5 6 7, , , , , ,x x x x x x x devem ser 
inteiros, não negativos e que, como são 4 amigos, 1 2 3 4 5 6 7, , , , , , 4x x x x x x x = . Cada modo de 
comprar os 4 sorvetes é uma solução em inteiros não negativos desta equação. 
Por exemplo: 
(i) A lista ( )0,1,0,1,1,0,1 significa comprar 1 sorvete do 2º sabor, comprar 1 sorvete do 
4º sabor, comprar 1 sorvete do 5º sabor e comprar 1 sorvete do 7º sabor. 
(ii) A lista ( )2,0,1,0,0,0,1 significa comprar 2 sorvetes do 1º sabor, comprar 1 sorvete 
do 3º sabor e comprar 1 sorvete do 7º sabor. 
(iii) A lista ( )0,0,3,1,0,0,0 significa comprar 3 sorvetes do 3º sabor e comprar 1 sorvete 
do 4º sabor. 
Portanto, para resolver problemas de combinações com repetições ou completas devemos 
saber calcular o número de soluções inteiras de equações com coeficientes unitários. 
 
2 
 
2. Equações com coeficientes unitários. 
Seja a equação 
1 2 3 1, , ,..., ,p px x x x x n− = 
sendo n natural não nulo. 
Chama-se solução inteira desta equação a toda lista de números inteiros 
( )1 2 3 1, , ,..., ,p p    − 
tal que 
1 2 3 1, , ,..., ,p p n    − = 
Por exemplo: 
São soluções inteiras da equação 10x y z w+ + + = as listas: 
( ) ( ) ( ) ( )2,5,1,2 , 0,5,1,3 , 2,4,1,7 , 0,10,0,0− , etc. 
Soluções em que o valor atribuído a cada incógnita é um número positivo, chama-se soluções 
inteiras positivas 
*
10,4CR e soluções em que o valor atribuído a cada incógnita é um número 
positivo ou nulo, chama-se soluções inteiras não negativas 10,4CR . 
Nosso objetivo nesta seção é apresentar um processo elementar para o cálculo do número de 
soluções inteiras positivas bem como do número de soluções inteiras não negativas de tais 
equações. 
 
2.1. Número de soluções inteiras positivas. 
Seja a equação: 
10x y z w+ + + = 
Podemos identificar o problema do cálculo do número de soluções inteiras positivas desta 
equação com o seguinte problema: 
Escrevendo-se em fila 10 algarismos iguais a 1, de quantos modos podemos separar esses 
algarismos em 4 grupos, onde cada grupo contém pelo menos um algarismo 1? 
1111111111 
Observe que entre os 10 algarismos há 9 espaços e se colocarmos elementos de separação 
(como barras inclinadas) em 3 destes espaços, obteremos uma disposição correspondente a 
uma solução da equação dada. Assim, por exemplo, a disposição: 
( )
( )
( )
1/1111/11/111 1,4,2,3
111111/1/11/1 6,1,2,1
1111111/1/1/1 7,1,1,1
→
→
→
 
Então, o número de soluções inteiras positivas da equação 10x y z w+ + + = é igual ao 
número de modos de escolher 3 dos 9 espaços para colocar as 3 barras, isto é: 
*
10,4 9,3 10 1,4 1CR C C − −= = 
Se um problema de combinação com repetição ou completa é representado por uma equação 
linear com coeficientes unitários: 
1 2 ... px x x n+ + + = 
O número de soluções inteiras positivas é determinado da seguinte forma: 
*
, 1, 1n p n pCR C − −= 
3 
 
2.2. Número de soluções inteiras não negativas. 
Seja a equação: 
10x y z w+ + + = 
Podemos identificar o problema do cálculo do número de soluções inteiras não negativas 
desta equação da seguinte forma: 
Suponhamos escritas todas estas soluções inteiras não negativas em uma mesma coluna, e 
somemos uma unidade a cada inteiro destas soluções, obtendo, assim, soluções inteiras e 
positivas de uma nova equação: 
14x y z w+ + + = 
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
5;1;4;0 5 1;1 1;4 1;0 1 6;2;5;1
9;0;1;0 9 1;0 1;1 1;0 1 10;1;2;1
2;2;5;1 2 1;2 1;5 1;1 1 3;3;6;2
0;0;10;0 0 1;0 1;10 1;0 1 1;1;11;1
 + + + + =
 + + + + =
 + + + + =
 + + + + =
 
Desse modo, a cada solução inteira não negativa da equação: 
10x y z w+ + + = 
Corresponde uma única solução inteira positiva da equação: 
14x y z w+ + + = 
e, reciprocamente, a cada solução inteira positiva da equação: 
14x y z w+ + + = 
Corresponde uma única solução não negativa da equação: 
10x y z w+ + + = 
Então, o número de soluções inteiras não negativas da equação 10x y z w+ + + = é igual 
ao número de soluções inteiras positivas da equação 14x y z w+ + + = , ou seja, número de 
modos de escolher 3 dos 13 espaços para colocar as 3 barras, isto é: 
*
10,4 10 4,4 14 1,4 1CR CR C+ − −= = 
Se um problema de combinação com repetição ou completa é representado por uma equação 
linear com coeficientes unitários: 
1 2 ... px x x n+ + + = 
O número de soluções inteiras não negativas é determinado da seguinte forma: 
*
, , 1, 1n p n p p n p pCR CR C+ + − −= = 
3. Conclusão. 
Se um problema de combinação com repetição ou completa é representado por uma equação 
linear com coeficientes unitários: 
1 2 ... px x x n+ + + =
 
a) O número de soluções inteiras positivas é determinado da seguinte forma: 
1, 1n pC − −
 
b) O número de soluções inteiras não negativas é determinado da seguinte forma: 
1, 1n p pC + − − 
4 
 
4. Exemplos. 
1) Quatro amigos chegam a uma sorveteria para comprar, cada um deles, um único 
sorvete. 
De quantos modos é possível esses amigos comprar os quatro sorvetes, se a 
sorveteria os oferece em 7 sabores? 
SOLUÇÃO 
O número de variáveis da equação é a quantidade de sabores dos sorvetes, sete. Como 
vão comprar 4 sorvetes podemos traduzir este problema na seguinte equação: 
1 2 3 4 5 6 7 4x x x x x x x+ + + + + + = 
Cada modo de comprar os 4 sorvetes é uma solução em inteiros não negativos desta 
equação. 
Neste caso 4n = e 7p = . 
Como vimos na conclusão esse número é: 
1, 1 10,6
10,6
10! 10 9 8 7 6! 10 9 8 7
6!4! 6! 4 3 2 4 3 2
10 3 7 210
n p pC C
C
+ − −
      
= = = =
    
=   =
 
Podemos, então, comprar de 210 maneiras quatro sorvetes, se a sorveteria os oferece em 
7 sabores. 
2) Dada a equação 
1 2 3 7x x x+ + = 
Determine: 
a) O número de soluções inteiras positivas; 
b) O número de soluções inteiras não negativas. 
SOLUÇÃO 
Neste caso 7n = e 3p = . 
a) Como vimos na conclusão esse número é: 
1, 1 6,2
6! 6 5 4! 6 5
15
2!4! 2 4! 2
n pC C− −
  
= = = = =

 
b) Como vimos na conclusão esse número é: 
1, 1 9,2
9! 9 8 7! 9 8
36
2!7! 2 7! 2
n p pC C+ − −
  
= = = = =

 
3) Quantas soluções inteiras positivas, maiores que 5, possui a equação: 
1 2 3 4 40x x x x+ + + = 
SOLUÇÃO 
Se em cada solução inteira positiva da equação 1 2 3 4 40x x x x+ + + = , satisfazendo as 
condições 1 2 3 45, 5, 5, 5x x x x    , subtrairmos 5 unidades de cada inteiro, obteremos 
uma solução positiva da equação: 
1 2 3 4
1 2 3 4
40 5 5 5 5
20
x x x x
x x x x
+ + + = − − − −
+ + + =
 
 
 
 
5 
 
Este número de soluções é dado por: 
1, 1 19,3n pC C− − = 
4) Quantas soluções inteiras possui a equação: 
1 2 3 4 40x x x x+ + + = 
a) Satisfazendo as condições 1 2 3 45, 6, 7, 8x x x x    , 
b) Satisfazendo as condições 1 2 3 45, 6, 7, 8x x x x    , 
SOLUÇÃO 
a) Fazendo um raciocínio análogo ao exemplo anterior, obteremos uma solução positiva 
da equação: 
1 2 34
1 2 3 4
40 5 6 7 8
14
x x x x
x x x x
+ + + = − − − −
+ + + =
 
Este número de soluções é dado por: 
1, 1 13,3n pC C− − = 
b) Notando que 1 2 3 45, 6, 7, 8x x x x    implica 1 2 3 44, 5, 6, 7x x x x    
obteremos uma solução positiva da equação: 
1 2 3 4
1 2 3 4
40 4 5 6 7
18
x x x x
x x x x
+ + + = − − − −
+ + + =
 
Este número de soluções é dado por: 
1, 1 17,3n pC C− − = 
5) Determine o número de soluções inteiras não negativas das inequações: 
1 2 32 6x x x + +  
SOLUÇÃO 
Notando que 1 2 32 6x x x + +  implica: 
1 2 3
1 2 3
1 2 3
1 2 3
3
4
5
6
x x x
x x x
x x x
x x x
+ + =
+ + =
+ + =
+ + =
 
Este número de soluções inteiras não negativas de cada uma destas equações é dado por: 
5,2
6,2
7,2
8,2
5! 5 4 3! 5 4
10
2!3! 2 3! 2
6! 6 5
15
2!4! 2
7! 7 6
21
2!5! 2
8! 8 7
28
2!6! 2
C
C
C
C
  
= = = =


= = =

= = =

= = =
 
6 
 
No total teremos, então, 10 15 21 28 74+ + + = soluções. 
6) Quantos inteiros entre 1 e 1 000 000 têm soma de seus algarismos igual a 13? 
SOLUÇÃO 
Não levando em conta o inteiro 1 000 000, por não ter soma dos algarismos iguais a 13, 
podemos pensar nos inteiros de 1 a 999 999 como tendo seis algarismos. 
Por exemplo, o número 4234 pode ser interpretado como a solução inteira não negativa, 
004 234, da equação: 
1 2 3 4 5 6 13x x x x x x+ + + + + = 
O problema consiste então em determinar o número de soluções inteiras não negativas, 
menores que 10, desta equação. 
Para isso devemos subtrair do número de soluções inteiras não negativas aquelas em que 
temos: 
1 2 3 4 5 69; 9; 9; 9; 9; 9x x x x x x      
O número de soluções inteiras não negativas da equação: 
1 2 3 4 5 6 13x x x x x x+ + + + + = 
É obtido assim: 
1, 1 18,5n p pC C+ − − = 
O número de soluções inteiras não negativas da equação com 1 9x  é: 
1 2 3 4 5 6
1 2 3 4 5 6
1, 1 9,5
13 9
4
n p p
x x x x x x
x x x x x x
C C+ − −
+ + + + + = −
+ + + + + =
=
 
Sendo análogo o raciocínio para 2 3 4 5 69; 9; 9; 9; 9x x x x x     concluímos que o 
número de inteiros entre 1 e 1 000 000 têm soma de seus algarismos igual a 13 é: 
18,5 9,56C C−