Aula 8-Combinação com Repetição

Prévia do material em texto

Combinações com repetição
Suponha que você quer selecionar p elementos à partir de n elementos distintos a1, a2, ..., an
de tal forma que cada elemento pode ser tomado até p vezes (ou seja, podemos selecionar um
elemento mais de uma vez). Seja x1 quantidade de vezes que o elemento a1 foi tomado na
seleção, x2 a quantidade de vezes o elemento a2 foi selecionado, ..., xn a quantidade de vezes
que o elemento an foi selecionado. Observe que devemos ter
x1 + x2 + ...+ xn = p
pois a quantidade de elementos selecionados deve ser p. Observe também que devemos ter
x1, x2, ..., xn ∈ N (uma vez que nada te impede de não selecionar nenhuma vez algum elemento)
e, portanto, (x1, x2, ..., xn) é uma solução não-negativa da equação x1 + x2 + ... + xn = p. A
quantidade de maneiras distintas com as quais podemos selecionar os p elementos é portanto,
Cn−1n+p−1
Chamamos esse tipo de situação de combinação com repetição de n elementos tomados p a p.
Exemplo 1. Suponha que uma pessoa está em um parque de diversões e ela tem dinheiro para
comprar 5 bilhetes. Se existem 3 atrações distintas, de quantas formas diferentes ela pode com-
prar os bilhetes?
Observe que nada impede a pessoa de repetir mais de uma vez uma atração e nada impede
ela de não ir em alguma atração (por exemplo, se a pessoa tem medo de trem fantasma, ela
não vai querer ir lá). Sejam x1 a quantidade de ingressos que ela vai comprar da atração 1, x2
a quantidade de ingressos que ela vai comprar da atração 2 e x3 a quantidade de ingressos que
ela vai comprar da atração 3. Como a pessoa pode comprar apenas 5 ingressos, então devemos
ter
x1 + x2 + x3 = 5
onde x1, x2 e x3 são números inteiros não negativos. Como a equação x1 + x2 + x3 = 5 possui
C3−15+3−1 = C
2
7 =
7!
(7− 2)! 2! =
7!
5! 2!
=
7 · 6 · 5!
5! 2!
=
7 · 6
2
= 21
soluções inteiras não negativas, então existem 21 formas diferentes dessa pessoa comprar os
bilhetes.
Exemplo 2. Suponha que uma pessoa está em um parque de diversões e ela tem dinheiro para
comprar 5 bilhetes. Se existem 7 atrações distintas, de quantas formas diferentes ela pode com-
prar os bilhetes?
Sejam x1 a quantidade de ingressos que essa pessoa vai comprar da atração 1, x2 a quanti-
dade de ingressos que ela vai comprar da atração 2, x3 a quantidade de ingressos que ela vai
comprar da atração 3, x4 a quantidade de ingressos que ela vai comprar da atração 4, x5 a
quantidade de ingressos que ela vai comprar da atração 5, x6 a quantidade de ingressos que
ela vai comprar da atração 6 e x7 a quantidade de ingressos que ela vai comprar da atração 7.
Como a pessoa pode comprar apenas 5 ingressos, então devemos ter
x1 + x2 + x3 + x4 + x5 + x6 + x7 = 5
onde x1, x2, x3, x4, x5, x6 e x7 são números inteiros não negativos (observe que como temos mais
atrações do que ingressoas, com certeza a pessoa não poderá ir em pelo menos 2 das atrações
1
e, portanto, pelo menos duas das variáveis serão zero em cada solução da equação). Como a
equação x1 + x2 + x3 + x4 + x5 + x6 + x7 = 5 possui
C7−15+7−1 = C
6
11 =
11!
(11− 6)! 6! =
11!
5! 6!
= 462
soluções inteiras não negativas, então existem 462 formas diferentes dessa pessoa comprar os
bilhetes.
Exemplo 3. Suponha que uma pessoa está em um parque de diversões e ela tem dinheiro para
comprar 9 bilhetes. Suponha que ela quer ir pelo menos uma vez em cada atração, ou seja,
que ela quer conhecer todas as atrações. Se existem 7 atrações distintas, de quantas formas
diferentes ela pode comprar os bilhetes?
Sejam x1 a quantidade de ingressos que essa pessoa vai comprar da atração 1, x2 a quanti-
dade de ingressos que ela vai comprar da atração 2, x3 a quantidade de ingressos que ela vai
comprar da atração 3, x4 a quantidade de ingressos que ela vai comprar da atração 4, x5 a
quantidade de ingressos que ela vai comprar da atração 5, x6 a quantidade de ingressos que
ela vai comprar da atração 6 e x7 a quantidade de ingressos que ela vai comprar da atração 7.
Como a pessoa pode comprar apenas 9 ingressos, então devemos ter
x1 + x2 + x3 + x4 + x5 + x6 + x7 = 9
onde x1, x2, x3, x4, x5, x6 e x7 são números inteiros positivos, uma vez que a pessoa quer ir pelo
menos uma vez em cada atração e, portanto, devemos ter x1, x2, x2, x3, x4, x5, x6, x7 ≥ 1. Como
a equação x1 + x2 + x3 + x4 + x5 + x6 + x7 = 9 possui
C7−19−1 = C
6
8 =
8!
(8− 6)! 6! =
8!
2! 6!
= 28
soluções inteiras positivas, então existem 28 formas diferentes dessa pessoa comprar os bilhetes.
Outra forma de resolver esse exercício seria pensar que 7 ingressos já estão predestinados (pois
ela terá que comprar pelo menos um ingresso de cada atração). Logo, a pessoa só tem opção
de escolha sobre os outros 2 ingressos restantes que podem ser escolhidos livremente. Como a
quantidade de modos diferentes que ela pode comprar os 2 ingressos restantes é a quantidade
de soluções inteiras não-negativas da equação
x1 + x2 + x3 + x4 + x5 + x6 + x7 = 2
então existem
C7−12+7−1 = C
6
8 = 28
formas diferentes da pessoa comprar os ingressos.
Exemplo 4. De quantos modos podemos comprar 4 refrigerantes em um bar que vende 2 tipos
de refrigerante?
Observe que nada nos impede de não querer comprar um dos tipos de refrigerante (uma vez
que podemos não gostar de um deles) ou de comprar os refrigerantes de forma variada. Sejam
x1 a quantidade de refrigerantes do primeiro tipo e x2 a quantidade de refrigerantes do segundo
tipo que nós vamos comprar. Como nós queremos comprar exatamente 4 refrigerantes, então
devemos ter
x1 + x2 = 4
2
onde x1 e x2 são números inteiros não negativos. Como a equação x1 + x2 = 4 possui
C2−14+2−1 = C
1
5 =
5!
(5− 1)! 1! =
5!
4! 1!
=
5 · 4!
4! 4!
= 5
soluções inteiras não-negativas, então podemos comprar os 4 refrigerantes de 5 formas distintas.
Exemplo 5. De quantos modos diferentes podemos distribuir 10 bombons idênticos em 4 caixas
diferentes?
Se x1 é a quantidade de bombons da caixa 1, x2 é a quantidade de bombons da caixa 2, x3
é a quantidade de bombons da caixa 3 e x4 é a quantidade de bombons da caixa 4, então a quan-
tidade de modos diferentes que podemos distribuir os 10 bombons é a quantidade de soluções
inteiras não-negativas da equação
x1 + x2 + x3 + x4 = 10
Logo, existem
C1010+4−1 = C
10
13 =
13!
10! 3!
=
13 · 12 · 11 · 10!
10! 3!
=
13 · 12 · 11
6
= 286
formas diferentes de distribuir os bombons nas caixas.
Exemplo 6. De quantos modos diferentes podemos distribuir 10 bombons idênticos em 4 caixas
diferentes de modo que cada caixa tenha pelo menos um bombom?
Se x1 é a quantidade de bombons da caixa 1, x2 é a quantidade de bombons da caixa 2, x3
é a quantidade de bombons da caixa 3 e x4 é a quantidade de bombons da caixa 4, então a quan-
tidade de modos diferentes que podemos distribuir os 10 bombons é a quantidade de soluções
inteiras positivas da equação
x1 + x2 + x3 + x4 = 10
Logo, existem
C4−110−1 = C
3
9 =
9!
6! 3!
=
9 · 8 · 7 · 6!
6! 3!
=
9 · 8 · 7
6
= 84
formas diferentes de distribuir os bombons nas caixas.
Outra forma de resolver esse exercício seria pensar que 4 bombons já estão predestinados (pois
cada um irá em uma caixa). Logo, só temos opções de escolha sobre os outros 6 bombons
restantes que podem ser distribuídos livremente. Como a quantidade de modos diferentes que
podemos distribuir os 6 bombons restantes nas 4 caixas é a quantidade de soluções inteiras
não-negativas da equação
x1 + x2 + x3 + x4 = 6
então existem
C4−16+4−1 = C
3
9 =
9!
6! 3!
=
9 · 8 · 7 · 6!
6! 3!
=
9 · 8 · 7
6
= 84
formas diferentes de distribuir os bombons nas caixas.
Exemplo 7. De quantos modos diferentes podemos distribuir 10 bombons idênticos em 4 caixas
diferentes de modo que cada caixa tenha pelo menos dois bombons?
Observe que 8 bombons já estão predestinados (pois cadacaixa receberá dois bombons pelo me-
nos). Logo, só temos opções de escolha sobre os outros 2 bombons restantes que podem ser
3
distribuídos livremente. Como a quantidade de modos diferentes que podemos distribuir os 2
bombons restantes nas 4 caixas é a quantidade de soluções inteiras não-negativas da equação
x1 + x2 + x3 + x4 = 2
então existem
C4−12+4−1 = C
3
5 =
5!
(5− 3)! 3! =
5!
2! 3!
=
5 · 4 · 3!
2! 3!
=
5 · 4
2
= 10
formas diferentes de distribuir os bombons nas caixas.
Permutações com repetição
Suponha que temos n elementos e queremos colocar esses elementos em n lugares distintos,
mas que esses n elementos não sejam distintos entre si. Como existem elementos repetidos
entre os n elementos, então dizemos que (nesse caso) temos uma permutação dos n elementos
com repetição. Suponha que existem k elementos distintos a1, a2, a3, ..., ak.
Se existem n1 elementos iguais a a1, n2 elementos iguais a a2, ..., nk elementos iguais a ak,
então existem
n!
n1! n2! n3! ... nk!
maneiras distintas de dispor os elementos nos n lugares. De fato, se trocamos dois elementos
iguais de lugar, continuamos com a mesma permutação inicial. Mas na quantidade n! cada
permutação entre os n1 elementos a1 estão sendo contados n1! vezes (mesmo não gerando
permutações distintas), cada permutação entre os n2 elementos a2 estão sendo contados n2!
vezes (mesmo não gerando permutações distintas), ..., cada permutação entre os nk elementos
ak estão sendo contados nk! vezes (mesmo não gerando permutações distintas). Por isso temos
que dividir n! por n1! n2! ... nk!
Exemplo 8. Se quisermos organizar três canetas distintas: uma vermelha e duas verdes, então
existem
3!
1! 2!
=
6
2
= 3
maneiras distintas de fazer essa organização. São elas: (vermelha, verde, verde), (verde, ver-
melha, verde) e (verde, verde, vermelha).
Exemplo 9. Quantos anagramas distintos existem da palavra ABACAXI?
Observe que a palavra ABACAXI tem 7 letras: 3 letras A, 1 letra B, uma letra C, 1 letra
X e uma letra I. Logo, existem
7!
3! 1! 1! 1! 1!
=
7!
3!
=
7 · 6 · 5 · 4 · 3!
3!
= 7 · 6 · 5 · 4 = 840
anagramas distintos da palavra ABACAXI.
Exemplo 10. Quantos anagramas distintos existem da palavra BANANA?
Observe que a palavra BANANA tem 6 letras das quais apenas duas são repetidas: o A e
o N. Existem 3 letras A e 2 letras N na palavra BANANA. Logo, existem
6!
3! 2!
=
6 · 5 · 4 · 3!
3! 2!
=
120
2
= 60
anagramas distintos da palavra BANANA.
4
Exemplo 11. Quantos anagramas distintos da palavra BATATA começam com a letra T?
Se fixarmos a primeira letra do anagrama como sendo T , então sobram 5 letras para com-
pletar o anagrama das quais: 3 letras são A, 1 letra é T e 1 letra é B. Logo, existem
5!
3!
=
5 · 4 · 3!
3!
= 5 · 4 = 20
anagramas distintos da palavra BATATA que começam com a letra T .
Exemplo 12. Quantos anagramas distintos possui a palavra OTORRINOLARINGOLOGISTA?
A palavra OTORRINOLARINGOLOGISTA possui
• 22 letras no total
• 5 letras O
• 2 letras T
• 3 letras R
• 3 letras I
• 2 letras N
• 2 letras L
• 2 letras A
• 2 letras G
• 1 letra S
Logo, ela possui
22!
5! (2!)5 (3!)2 1!
anagramas distintos.
Exemplo 13. Você tem 2 canetas vermelhas e 3 canetas azuis para distruibuir para 5 pessoas.
De quantas formas distintas você pode distribuir essas canetas de forma que cada pessoa ganhe
uma caneta?
Existem
5!
2! 3!
=
5 · 4 · 3!
2! 3!
=
20
2
= 10
formas distintas de distribuir as canetas.
Permutações circulares
Uma permutação circular de n elementos é uma organização desses n em torno de um círculo.
Podemos pensar nessas permutações como formas diferentes em que as pessoas podem se sentar
em uma mesa circular. Se duas permutações circulares dos mesmos objetos diferirem apenas
por uma rotação desses n objetos, então consideramos essas permutações circulares como sendo
iguais.
Por exemplo, as permutações circulares dos elementos a, b e c
dos elementos a, b e c são iguais.
5
Exemplo 14. Quantas permutações circulares distintas de 3 elementos distintos existem?
Observe que para cada permutação circular temos 3 rotações possíveis dela que geram no final
a mesma permutação circular. Observe que cada rotação equivale a uma permutação simples
distinta dos elementos a, b e c se considerarmos o elemento do topo do círculo como sendo o
primeiro elemento e considerarmos a ordem dos elementos tomados no sentido horário.
Como existem 3! = 6 permutações simples de 3 elementos e cada rotação circular equivale a 3
dessas permutações, então temos
3!
3
= 6
3
= 2 permutações circulares distintas. São elas
Observe que para cada permutação circular de n elementos temos n rotações possíveis delas
em torno do círculo que geram no final a mesma permutação circular. Observe que cada rotação
equivale a uma permutação simples distinta dos n elementos se considerarmos o elemento do
topo do círculo como sendo o primeiro elemento e tomarmos como sequência a ordem de aparição
dos elementos no sentido horário.
Como existem n! permutações simples de n elementos e cada permutação circular distinta
corresponde a n dessas permutações simples, então existem
n!
n
= (n− 1)!
permutações circulares distintas de n elementos.
Observe que as n permutações simples que correspondem à mesma permutação circular
podem ser obtidas apenas levando o elemento do último lugar de uma dessas permutações
simples para o primeiro lugar. Por exemplo, as 5 permutações simples
(A,B,C,D,E), (E,A,B,C,D), (D,E,A,B,C), (C,D,E,A,B), (B,C,D,E,A)
6
são as 5 permutações simples dos elementos A,B,C,D e E que correspondem à mesma permu-
tação circular (que é a permutação circular obtida fixando o elemento A no topo e posicionando
os elementos B,C,D,E nessa ordem no sentido horário).
Logo, podemos calcular a quantidade de permutações circulares distintas considerando ape-
nas a quantidade de permutações simples cujo primeiro elementos é fixo, o que equivale a
considerar o elemento que fica no topo do círculo como fixo e variar apenas as outras n − 1
posições (uma vez que as organizações nas quais o elemento do topo está em algum outro lugar
que não o topo equivale apenas a uma rotação de uma configuração na qual ele está no topo).
Observe que se fixarmos o elemento do topo do círculo e posicionarmos os elementos no
sentido horário, temos n − 1 opções de escolha para a primeira posição após o topo, n − 2
opções para a segunda posição após o topo, ..., 1 opção de escolha para a n− 1-ésima posição
após o topo (que é a posição logo antes desse topo). Por isso, existem (n − 1)! permutações
circulares distintas de n elementos.
Exemplo 15. De quantas maneiras distintas 8 pessoas podem sentar em roda?
Elas podem se sentar de 7! = 5040 formas distintas.
Exemplo 16. De quantas maneiras distintas 8 pessoas podem sentar em roda se duas dessas
pessoas (Pedro e Ana) quiserem se sentar juntos?
Vamos considerar o Pedro e a Ana como sendo uma única pessoa. Temos 6! = 720 formas
distintas de 7 pessoas se sentarem em círculo. Como o Pedro e a Ana podem trocar de lugar
um com o outro e com isso continuar juntos, então existem
2 · 720 = 1440
maneiras distintas das 8 pessoas se sentarem de forma que o Pedro e a Ana estejam juntos.
7
Exemplo 17. De quantas maneiras distintas 3 homens e 3 mulheres podem sentar em roda de
forma que os homens e as mulheres se alternem?
Vamos fixar a pessoa que está no topo do círculo (que vamos considerar como sendo o pri-
meiro lugar) como sendo o homem A. No sentido horário, temos que
• o segundo lugar deve ser ocupado por uma mulher e temos 3 opções de escolha para escolher
a mulher que sentará neste lugar
• o terceiro lugar deve ser ocupado por um homem e temos 2 opções restantes de escolha
para escolher o homem que sentaráneste lugar
• o quarto lugar deve ser ocupado por uma mulher e temos 2 opções restantes de escolha
para escolher a mulher que sentará neste lugar
• o quinto lugar deve ser ocupado por um homem e temos 1 opção restante de escolha para
escolher o homem que sentará neste lugar
• o sexto lugar deve ser ocupado por uma mulher e temos 1 opção de escolha restante para
escolher a mulher que sentará neste lugar
Logo, temos 3 · 2 · 2 · 1 · 1 = 3! 2! = 12 permutações circulares distintas com homens e mulheres
se alternando nas posições.
Exemplo 18. De quantas maneiras distintas 4 homens e 4 mulheres podem sentar em roda de
forma que os homens e as mulheres se alternem?
Vamos fixar a pessoa que está no topo do círculo (que vamos considerar como sendo o pri-
meiro lugar) como sendo o homem A. No sentido horário, temos que
• o segundo lugar deve ser ocupado por uma mulher e temos 4 opções de escolha para escolher
a mulher que sentará neste lugar
• o terceiro lugar deve ser ocupado por um homem e temos 3 opções restantes de escolha
para escolher o homem que sentará neste lugar
• o quarto lugar deve ser ocupado por uma mulher e temos 3 opções restantes de escolha
para escolher a mulher que sentará neste lugar
• o quinto lugar deve ser ocupado por um homem e temos 2 opções restantes de escolha para
escolher o homem que sentará neste lugar
• o sexto lugar deve ser ocupado por uma mulher e temos 2 opções de escolha restantes para
escolher a mulher que sentará neste lugar
8
• o sétimo lugar deve ser ocupado por um homem e temos 1 opção de escolha restante para
escolher o homem que sentará neste lugar
• o oitavo lugar deve ser ocupado por uma mulher e temos 1 opção de escolha restante para
escolher a mulher que sentará neste lugar
Logo, temos 4 · 3 · 3 · 2 · 2 · 1 · 1 = 4! 3! = 144 permutações circulares distintas com homens e
mulheres se alternando nas posições.
Exemplo 19. De quantas maneiras distintas n homens e n mulheres podem sentar em roda de
forma que os homens e as mulheres se alternem?
Existem n! (n − 1)! maneiras distintas de n homens e n mulheres se sentarem em círculo
de forma que os homens e as mulheres se alternem.
Exemplo 20. De quantas maneiras distintas 4 homens e 4 mulheres podem sentar em roda de
forma que os homens e as mulheres se alternem e de forma que João e Maria sentem juntos
(se João e Maria são duas das 8 pessoas)?
Vamos fixar a pessoa que está no topo do círculo como sendo o João. Temos duas opções
de lugares para Maria se sentar: no primeiro lugar depois de João no sentido horário ou no
primeiro lugar depois de João no sentido anti-horário. Observe que
• Existem 3 · 3 · 2 · 2 · 1 · 1 = 3! 3! = 36 permutações circulares onde Maria está sentada no
primeiro lugar depois de João no sentido horário.
• Existem 3 · 3 · 2 · 2 · 1 · 1 = 3! 3! = 36 permutações circulares onde Maria está sentada no
primeiro lugar depois de João no sentido anti-horário.
9
Logo, temos 2 · 36 = 72 permutações circulares distintas com homens e mulheres se alternando
nas posições nas quais João e Maria estão sentados um do lado do outro.
Coeficientes Binomiais
Observe que quando fazemos o produto de um binômio (a, b) por ele mesmo, isto é quando
calculamos
(a+ b)2 = (a+ b)(a+ b)
e fazemos a distribuição do produto, obtemos os 4 termos
(a+ b)(a+ b) = a2 + ab+ ba+ b2
Observe que quando estamos fazendo essa distributidade do produto, os termos obtidos
consistem no produto de um elemento do primeiro binômio a+ b com um elemento do segundo
binômio c+ d. Como existem C12 = 2 formas de selecionar um elemento do primeiro binômio e
C12 = 2 formas diferentes de selecionar um elemento do segundo binômio, então existem 2 ·2 = 4
formas diferentes de selecionar um elemento do primeiro binômio e um elemento do segundo
binômio. Por isso, existem 4 termos na distribuição binomial.
Entretanto, como o produto de números reais é comutativo, então ab = ba. Portanto, os
termos ab e ba são iguais e temos que
(a+ b)2 = a2 + 2ab+ b2
Observe que no final das contas, o que foi importante foi quantas vezes o número a foi
selecionado dos dois termos, quantas vezes o elemento a foi selecionado de um termo e o b do
outro termo e quantas vezes o número b foi selecionado dos dois termos.
Observe que quando calculamos
(a+ b)3 = (a+ b)(a+ b)(a+ b)
e fazemos a distribuição do produto, obtemos
(a+ b)3 = (a+ b)(a+ b)(a+ b)
= (a+ b)(a2 + ab+ ba+ b2)
= a3 + a2b+ ba2 + ab2 + ba2 + ab2 + b2a+ b3 = a3 + 3a2b+ 3ba2 + b3
Observe que quando estamos fazendo essa distributidade do produto, os termos obtidos
consistem no produto de um elemento do primeiro binômio a+ b com um elemento do segundo
binômio a+ b com um elemento do terceiro binômio a+ b.
10
• Como existe 1 forma de selecionar o elemento a dos três binômios, pois existem
3!
3!
permutações distintas de três letras a, então o coeficiente que multiplica o termo a3 é 1.
• Como existem 3 formas de selecionar dois a's e um b, pois existem
3!
2! 1!
permutações distintas de duas letras a com uma letra b (são elas aab, aba e baa), então o
coeficiente que multiplica o termo a2b é 3.
• Como existem 3 formas de selecionar dois b's e um a, pois existem
3!
2! 1!
permutações distintas de duas letras b com uma letra a (são elas bab, abb e bba), então o
coeficiente que multiplica o termo ab2 é 3.
• Como existe 1 forma de selecionar o elemento b dos três binômios, pois existem
3!
3!
permutações distintas de três letras b, então o coeficiente que multiplica o termo b3 é 1.
Vamos generalizar esse raciocínio para uma potência n ∈ N qualquer. Observe que na
expansão do produto binomial (a+ b)n aparecem os termos
an, an−1b, an−2b2, ..., an−1b, bn
e que a soma dos expoentes da potência de a e da potência de b de cada termo sempre somam
n (uma vez que os termos envolvem o produto da seleção de n elementos tomados um de cada
binômio a+ b). Existem
• n!
n! 0!
= 1
permutações de n elementos a's. Logo, existe só uma forma de selecionar a em todos
os binômios e, portanto, o coeficiente que multiplica o termo an na expansão binomial é
1.
• n!
(n− 1)! 1!
permutações de n − 1 elementos a's e 1 elemento b. Logo, existem n!
(n−1)! formas de
selecionar n−1 elementos a's e um elemento b nos binômios e, portanto, o coeficiente que
multiplica o termo an−1b na expansão binomial é n!
(n−1)! .
• n!
(n− 2)! 2!
permutações de n − 2 elementos a e 2 elementos b. Logo, existem n!
(n−2)! 2! formas de
selecionar n − 2 elementos a e dois elementos b nos binômios e, portanto, o coeficiente
que multiplica o termo an−2b2 na expansão binomial é n!
(n−2)! 2! .
11
• ...
• n!
(n− r)! r!
permutações de n − r elementos a e r elementos b. Logo, existem n!
(n−r)! r! formas de
selecionar n − r elementos a e r elementos b nos binômios e, portanto, o coeficiente que
multiplica o termo an−rbr na expansão binomial é n!
(n−r)! r! .
• ...
• n!
1! (n− 1)!
permutações de 1 elemento a e n − 1 elementos b's. Logo, existem n!
(n−1)! formas de
selecionar 1 elemento a e n− 1 elementos b's nos binômios e, portanto, o coeficiente que
multiplica o termo abn−1 na expansão binomial é n!
(n−1)! .
• n!
0! n!
= 1
permutações de n elementos b's. Logo, existe só uma forma de selecionar b em todos
os binômios e, portanto, o coeficiente que multiplica o termo bn na expansão binomial é
1.
Observe que
n!
(n− r)! r! = C
r
n
Logo, o coeficiente que multiplica o termo an−rbr é Crn. Ou seja,
(a+ b)n = C0n a
n b0 + C1n a
n−1 b1 + C2n a
n−2 b2 + ...+ Cn−2n a
2 bn−2 + Cn−1n a
1 bn−1 + Cnn a
0 bn
Podemos denotar essa expansão de forma mais concisa utilizando a notação de somatório:
(a+ b)n =
n∑
r=0
Crn a
n−r br
O somatório
n∑
r=0
Crn a
n−r br pode ser lido como somatório em r de 0 até n dos termos
Crn a
n−r br e ele quer dizer que devemos somartodos os termos da forma Crn a
n−r br com r
variando de 0 até n.
• Para r = 0, temos que Crn an−r br = C0n an−0 b0 = C0n an
• Para r = 1, temos que Crn an−r br = C1n an−1 b1 = C1n an−1 b
• Para r = 2, temos que Crn an−r br = C2n an−2 b2
• Para r = 3, temos que Crn an−r br = C3n an−3 b3
• ...
• Para r = n, temos que Crn an−r br = Cnn an−n bn = Cnn a0 bn = Cnn bn
12
Logo,
n∑
r=0
Crn a
n−r br = C0n a
n b0 + C1n a
n−1 b1 + C2n a
n−2 b2 + C3n a
n−3 b3 + ...+ Cnn a
0 bn
Exemplo 21.
(a+ b)5 =
5∑
r=0
Cr5 a
r b5−r
C05a
5b0 + C15a
4b1 + C25a
3b2 + C35a
2b3 + C45a
1b4 + C55a
0b5
=
5!
5! 0!
a5 +
5!
4! 1!
a4b+
5!
3! 2!
a3b2 +
5!
2! 3!
a2b3 +
5!
1! 4!
ab4 +
5!
0! 5!
b5
= a5 + 5a4b+ 10a3b2 + 10a2b3 + 5ab4 + b5
Exemplo 22.
(a− b)5 = (a+ (−b))5 =
5∑
r=0
Cr5 a
r (−b)5−r
= C05a
5(−b)0 + C15a4(−b)1 + C25a3(−b)2 + C35a2(−b)3 + C45a1(−b)4 + C55a0(−b)5
=
5!
5! 0!
a5 − 5!
4! 1!
a4b+
5!
3! 2!
a3b2 − 5!
2! 3!
a2b3 +
5!
1! 4!
ab4 − 5!
0! 5!
b5
= a5 − 5a4b+ 10a3b2 − 10a2b3 + 5ab4 − b5
Identidade de Pascal: Ckn+1 = C
k−1
n + C
k
n
Demonstração: Suponha que você tem um conjunto A com n + 1 elementos distintos e
que você deseja selecionar k elementos distintos de A. Sabemos que existem Ckn+1 formas dis-
tintas de selecionar esses k elementos.
Seja a ∈ A um dos elementos de A. Observe que um seleção de k elementos de A pode incluir
ou não o elemento a.
De quantas formas distintas podemos selecionar os k elementos de forma que um deles seja o
a?
Como o elemento a já foi pré-selecionado, então temos que selecionar k − 1 elementos à partir
dos n elementos restantes de A. Logo, existem Ck−1n formas distintas de selecionar k elementos
de A de forma que o elemento a esteja entre eles.
De quantas formas distintas podemos selecionar os k elementos de forma que o a não esteja
entre estes elementos?
Como o elemento a não pode ser selecionado, então temos que selecionar os k elementos à partir
dos n elementos restantes de A. Logo, existem Ckn formas distintas de selecionar k elementos
de A de forma que o elemento a não esteja entre eles.
Logo, existem Ck−1n +C
k
n formas distintas de selecionar k dos n+1 elementos de A. Como esse
número é dado também por Ckn+1, concluímos que
Ckn+1 = C
k−1
n + C
k
n
13
Considere o triângulo numérico cuja (n+1)-ésima linha é a linha composta pelas combina-
ções C0n, C
1
n, C
2
n, ..., C
n−1
n , C
n
n nessa ordem (ou seja, a (n+ 1)-ésima linha é composta por todas
as combinações de n elementos tomados em quantidade crescente de seleções).
C00
C01 C
1
1
C02 C
1
2 C
2
2
C03 C
1
3 C
2
3 C
3
3
C04 C
1
4 C
2
4 C
3
4 C
4
4
C05 C
1
5 C
2
5 C
3
5 C
4
5 C
5
5
C06 C
1
6 C
2
6 C
3
6 C
4
6 C
5
6 C
6
6
C07 C
1
7 C
2
7 C
3
7 C
4
7 C
5
7 C
6
7 C
7
7
Observe que todas as linhas começam e terminam com o número 1, pois C0n = 1 e C
n
n = 1 para
todo n ∈ {0, 1, 2, 3, 4, 5, 6, ...}. Ou seja, esse triângulo tem a forma
1
1 1
1 C12 1
1 C13 C
2
3 1
1 C14 C
2
4 C
3
4 1
1 C15 C
2
5 C
3
5 C
4
5 1
1 C16 C
2
6 C
3
6 C
4
6 C
5
6 1
1 C17 C
2
7 C
3
7 C
4
7 C
5
7 C
6
7 1
Além disso, pela identidade de Pascal Ckn+1 = C
k−1
n + C
k
n, temos que
• C12 = C01 + C11
• C13 = C02 + C12
• C23 = C12 + C22
• C14 = C03 + C13
• C24 = C13 + C23
• C34 = C23 + C33
14
• C15 = C04 + C14
• C25 = C14 + C24
• C35 = C24 + C34
• C45 = C34 + C44
• ...
Logo, as outras entradas do triângulo são sempre a soma das duas entradas logo acima dela
(em diagonal). Ou seja,
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
Esse triângulo é chamado de triângulo de Pascal. Observe que o triângulo de Pascal nos
fornece os coeficientes das expansões binomiais, pois as entradas da (n+ 1)-ésima linha são os
coeficientes da expansão binomial (a+ b)n.
Exemplo 23. Para determinar (a+ b)7 basta usar os números da oitava linha do triângulo de
Pascal como os coeficientes de an, an−1b, .... Ou seja,
(a+ b)7 = a7 + 7a6b+ 21a5b2 + 35a4b3 + 35a3b4 + 21a2b5 + 7ab6 + b7
Exemplo 24. Para determinar (x + 2)6 basta usar os números da sétima linha do triângulo
de Pascal como os coeficientes de xn, xn−1 · 2, .... Ou seja,
(x+ 2)6 = x6 + 6x5 · 2 + 15x4 · 22 + 20x3 · 23 + 15x2 · 24 + 6x · 25 + 26
= x6 + 12x5 + 60x4 + 160x3 + 240x2 + 192x+ 64
Exemplo 25. Para determinar (x− 3)4 basta usar os números da quinta linha do triângulo de
Pascal como os coeficientes de xn, xn−1 · (−3), .... Ou seja,
(x− 3)4 = x4 + 4x3 · (−3) + 6x2 · (−3)2 + 4x · (−3)3 + (−3)4
= x4 − 12x3 + 54x2 − 108x+ 81
15