Combinações Simples e com Repetição

Prévia do material em texto

Combinações simples e com repetição - Teoria 
 
Combinações simples - Definição 
 
Consideremos um conjunto X com m elementos distintos. No artigo “Princípios Multiplicativos e 
Arranjos - Teoria”, aprendemos a calcular o número de arranjos de p elementos deste conjunto. Ao 
calcularmos pmA , é levada em consideração a ordem dos elementos escolhidos. 
 
Uma combinação simples seria a escolha destes p elementos de X , onde a ordem dos termos 
escolhidos é irrelevante. Representemos por pmC a combinação de m elementos tomados p a p . 
 
Podemos escrever a seguinte equação: 
!
p
p m
m
AC
p
= (*) (a divisão por !p desconta todas as variações 
possíveis para uma dada escolha de p elementos). 
 
A partir de (*), podemos chegar à seguinte fórmula: 
( )
( )
!
! !
! ! !
p
m
m
m p mC
p m p p
⎡ ⎤⎢ ⎥−⎣ ⎦= = − . 
 
Exercícios Resolvidos 
 
Exercício Resolvido 01) Quantos grupos de 3 pessoas podem ser montados com 8 pessoas? 
 
Solução: 
 
Ora, queremos escolher 3 pessoas dentre 8 , sendo que a ordem da escolha é irrelevante. Temos, 
portanto ( )38
8! 8 7 6 56
8 3 !3! 3 2
C ⋅ ⋅= = =− ⋅ maneiras de escolhermos estes grupos. 
 
Exercício Resolvido 02) Resolva a seguinte equação 3 43n nA C= ⋅ . 
 
Solução: 
 
( ) ( )3 4
! ! 1 3 23 3 7
3 ! 4 ! 4! 3 4 3 2n n
n nA C n
n n n
⋅= ⋅ ⇔ = ⋅ ⇔ = ⇔ =− − ⋅ − ⋅ ⋅ . 
 
Exercício Resolvido 03) Dadas duas retas paralelas, tomam-se 8 pontos sobre uma delas e 5 sobre a 
outra. Quantos triângulos existem com vértices nos pontos considerados? 
 
Solução: 
 
Repare que contar o número de triângulos é, na realidade, escolher 3 pontos dentre todos os 13. 
 
 
 
 
 
 
 
Além do mais, como não importa a ordem dessa escolha, o número total de triângulos seria
3
13
13! 13 12 11 286
3! 10! 6
C ⋅ ⋅= = =⋅ . 
 
Porém, devemos notar que estamos também escolhendo pontos colineares, que logicamente não 
constituem um triângulo. Devemos, pois, retirar de 286 estas contagens. 
 
Teremos portanto: 3 35 8286 286 10 56 220C C− − = − − = triângulos. 
 
Exercício Resolvido 04) Uma empresa distribuiu um questionário com três perguntas a cada candidato 
a emprego. Na primeira, o candidato deve declarar sua escolaridade, escolhendo uma das cinco 
alternativas. Na segunda, deve escolher, com ordem de preferência, três de seis locais onde gostaria de 
trabalhar. Na última, deve escolher os dois dias da semana em que quer folgar. Quantos questionários 
pode o examinador encontrar? 
 
Solução: 
 
Reparemos que o número total de questionários é ( )1 3 15 6 5 5 6 5 4 21 12600C A C⋅ ⋅ = ⋅ ⋅ ⋅ ⋅ = . 
 
Exercício Resolvido 05) Resolva a seguinte equação 3 2 0n nC C− = . 
 
Solução: 
 ( ) ( ) ( )3 2 1 2 1 2 10 0 0, 1
6 2 6 2n n
n n n n n nC C n n
⋅ − ⋅ − ⋅ − −− = ⇔ − = ⇔ = = ∨ = . Como 3n ≥ , devemos 
necessariamente ter 5n = . 
 
Exercício Resolvido 06) Um salão tem seis portas. De quantos modos distintos esse salão pode estar 
aberto? 
 
Solução: 
 
i) considerando uma única porta aberta: 16C modos. 
ii) considerando duas portas abertas: 26C modos. 
iii) considerando três portas abertas: 36C modos. 
iv) considerando quatro portas abertas: 46C modos. 
v) considerando cinco portas abertas: 56C modos. 
vi) considerando todas as portas abertas: 66C modos. 
 
Logo teremos 
6 6
0 6
6 6 6
1 0
2 1 63k k
k k
C C C
= =
= − = − =∑ ∑ maneiras deste salão estar aberto. 
 
 
 
 
 
 
 
 
 
 
Podemos, inclusive, generalizar este problema. Se considerássemos que o salão possui n portas, 
teríamos o seguinte total: 06 6 6
1 0
2 1
n n
k k n
k k
C C C
= =
= − = −∑ ∑ . 
 
Exercício Resolvido 07) Calcular o número de diagonais de um polígono regular de n lados. 
 
Solução: 
 
Uma diagonal de um polígono é, na realidade, uma simples reta. Dados n pontos distribuídos em um 
plano, temos 2nC retas cujos extremos são estes pontos. Descontando os n lados do polígono, temos no 
total 
( ) ( )2 1 3
2 2n
n n n n
C n n
⋅ − ⋅ −− = − = diagonais. 
 
Exercícios Resolvido 08) (IME) Em cada uma das 6 (seis) faces de um cubo, construiu-se uma 
circunferência, onde foram marcados n pontos. Considerando que 4 (quatro) pontos não pertencentes à 
mesma face não sejam coplanares, quantas retas e triângulos, não contidos nas faces desse cubo, são 
determinados por estes pontos? 
 
Solução: 
 
Temos 26nC retas, sendo que 
26 nC⋅ pertencem às faces do cubo. Assim teremos 
( ) ( )2 2 2
6
6 6 1 6 1
6 15
2 2n n
n n n n
C C n
− −− ⋅ = − = retas não pertencentes às faces do cubo. 
Temos 36nC triângulos, sendo que 
36 nC⋅ pertencem às faces do cubo. Assim teremos 
( )3 3 26 6 5 7 3n nC C n n− ⋅ = − triângulos não pertencentes às faces do cubo. 
 
Combinações com repetição – Definição 
 
Consideremos ainda um conjunto X com m elementos distintos. Escolhamos agora p elementos não 
necessariamente distintos (repare que p pode ser superior a m ). Após esta escolha, reagrupemos estes 
p elementos seguindo a mesma ordem de X . 
 
Ao número de maneiras de reagruparmos tais elementos, denominamos combinação com repetição de 
m elementos tomados p a p , cuja notação é prepmC . 
 
Tomemos como exemplo { }, , ,X a b c d= e 6p = . Dentre todas as possibilidades de reagrupamento, 
destaquemos as seguintes: 
 
i) { }, , , , ,a a b b b c 
ii) { }, , , , ,a b b c c c 
iii) { }, , , , ,a a a a a a 
 
 
 
 
 
 
 
Podemos utilizar uma notação um pouco diferenciada agora. 
 
Representemos os elementos iguais por # e a cada mudança de elementos, podemos utilizar % como 
notação para essa transição. Teremos então: 
 
i) { } { }, , , , , #,#,%,#,#,#,%,#,%a a b b b c = 
ii) { } { }, , , , , #,%,#,#,%,#,#,#,%a b b c c c = 
iii) { } { }, , , , , #,#,#,#,#,#,%,%,%a a a a a a = 
 
Repare que, para contar o número total de combinações com repetição, basta escolhermos 6 espaços 
dentre os 9 ( )6 4 1+ − disponíveis. 
 
Através de um argumento semelhante, podemos demonstrar que 1
p p
repm m pC C + −= . (Prove essa assertiva!) 
 
Exercícios Resolvidos 
 
Exercício Resolvido 01) Quantas são as soluções positivas da equação 
5
1
9k
k
x
=
=∑ ? 
 
Solução: 
 
Ora, primeiramente, devemos notar que *kx +∈? . Podemos escrever o 9 da seguinte maneira: 
 
1__1__1__1__1__1__1__1__1. 
 
Devemos agora inserir 4 sinais de + a fim de obter soma igual a 9 . Duas possibilidades seriam: 
 
i) 1 1__1 1__1__1 1__1 1 1 2 3 2 1 9+ + + + = + + + + = . 
ii) 1__1 1__1__1__1 1 1 1 2 4 1 1 1 9+ + + + = + + + + = . 
 
Repare que contar o número de soluções inteiras positivas é, portanto, escolher, dentre 8 lacunas, 4 
para inserirmos o sinal de +. Portanto a resposta para o problema é 48 70C = . 
 
Extra: Generalização do Exercício Resolvido 01: Provar que o número de soluções inteiras positivas 
da equação 
1
n
k
k
x m
=
=∑ é 11nmC −− . (Prove essa assertiva utilizando argumento semelhante ao da solução 
acima!) 
 
Exercício Resolvido 02) Quantas são as soluções positivas ou nulas da equação 
1
n
k
k
x m
=
=∑ ? 
 
 
 
 
Solução: 
 
Devemos notar que kx +∈? . Assim, consideremos *ky +∈? tal que 1k ky x= + . Assim, teremos de 
analisar o número de soluções da seguinte equação: ( )
1 1
1
n n
k k
k k
y m y m n
= =
− = ⇒ = +∑ ∑ . Pelo exercício 
extra, podemos concluir que o número de soluções positivas ou nulas para esta equação é 1 1
n
m nC
−
+ − .