Aula_013_Coeficientes binomiais e aplicações

Prévia do material em texto

Coeficientes binomiais
Binômio de Newton
Módulo: Coeficientes binomiais e aplicações
13.1
Apresentar identidades envolvendo coeficientes
binomiais.
Na análise de algoritmos aparece a necessidade de
manipular relações envolvendo coeficientes 
binomiais.
Objetivo:
Importância:
13.2Coeficientes binomiais e aplicações
Definição
Argumentos combinatório e algébrico
Identidades
Triângulo de Pascal
Teoremas das linhas, das colunas e das diagonais
13.3Coeficientes binomiais e aplicações
Aula 13: Coeficientes binomiais
Definição:
Chamamos C(n, r) de coeficiente binomial.
13.4Coeficientes binomiais
(0 ≤ r ≤ n)
Observação
C(n, r) =
n!_________
r! (n − r)!
expressão algébrica 
do coeficiente binomial
envolvendo fatoriais
número de possibilidades 
de escolher r objetos 
diferentes entre n objetos 
diferentes
O raciocínio combinatório está baseado na 
decomposição de um conjunto em subconjuntos 
adequados e na contagem de seus elementos 
aparecem as combinações simples.
O raciocínio algébrico está baseado na manipulação 
dos fatoriais.
13.5Coeficientes binomiais
• combinatórios
• algébricos
Argumentos combinatório e algébrico:
Dois tipos de argumentos podem ser usados na 
dedução de teoremas e identidades envolvendo
fatoriais ou coeficientes binomiais:
Observações:
13.6Coeficientes binomiais: Argumentos combinatório e algébrico
Na resolução de problemas combinatórios tem-se que:
• um raciocínio combinatório determina a 
 forma de uma expressão algébrica 
 
e vice-versa
uma forma da expressão algébrica sugere um 
raciocínio combinatório. 
• raciocínios combinatórios equivalentes geram
 identidades algébricas e vice-versa.
Exemplo 1: 
Considere três cidades A, B, C. Sejam nA, nB e nC os 
números de caminhos unindo diretamente A e B, B e C,
e A e C respectivamente. Quantos caminhos originados
em A, chegam a C e regressam a A passando pelo menos
uma vez por B? 
13.7Coeficientes binomiais: Argumentos combinatório e algébrico
 
1
2...
nB
1
2...
nA
1
2...
nC
Possibilidade 1:
Possibilidade 2:
Possibilidade 3:
• Ilustração
•
•
•A
B
C
Exemplo 1 (continuação): 
U1:= conjunto dos caminhos que partem de A, chegam a C passando
 por B e retornam diretamente a A (c1 ∈ U) 
U2:= conjunto dos caminhos que saem de A, chegam a C diretamente
 e voltam a A passando por B (c2 ∈ U2) 
V:= conjunto dos caminhos que se originam em A, chegam a C e 
 retornam a A passando as duas vezes por B (c3 ∈ V) 
13.8Coeficientes binomiais: Argumentos combinatório e algébrico
 
Resolução: 
Raciocínio 1
A•
•
B
•C
Possibilidade 1: caminho c1
Possibilidade 2: 
caminho c2
Possibilidade 3: 
caminho c3
(U1∩ U2 = ∅, U1∪ V = ∅, U2∩ V = ∅)
P.A.
W = U1 ∪ U2 ∪ V, |W| = |U1| + |U2| + |V|
Sejam
W:= conjunto de caminhos que partem de A, chegam a C e voltam a A
 passando pelo menos uma vez por B. 
Exemplo 1 (raciocínio 1): 
= C(nA, 1) C(nB, 1) C(nC, 1) = nAnBnC
= C(nC, 1) C(nB, 1) C(nA, 1) = nCnBnA 
13.9Coeficientes binomiais: Argumentos combinatório e algébrico
 
1
2...
1
2...
nA nB
nC
1
2...
•
•
•A
B
C
|W| = nAnBnC + nCnBnA + (nAnB)2 
Resposta 1:
possibilidades entre
A e C passando por B
possibilidades entre
C e A passando por B
= C(nA, 1) C(nB, 1) C(nB, 1) C(nA, 1) = (nAnB)
2
 
Calculamos
|U1| 
|U2| 
|V| 
W:= conjunto de caminhos que partem de A, chegam a C e voltam a A
 passando pelo menos uma vez por B. 
U:= conjunto universo:= conjunto de todos os caminhos que partem de A, 
 chegam a C e retornam a A.
13.10Coeficientes binomiais: Argumentos combinatório e algébrico
 
Y:= conjunto dos caminhos que partem de A, chegam a C e retornam a A
 sem passar por B.
1
2
nC
W = Y
__
 = U − Y , |W| = |U| − |Y|P.A.
Possibilidade
|Y| = C(nC, 1) C(nC, 1) = nC2
caminhos que unem
diretamente A e C
caminhos que unem
diretamente C e A
Exemplo 1 (continuação): 
Raciocínio 2 (baseado em complemento de um conjunto)
A• C•
B•
Exemplo 1 (raciocínio 2) 
= N = nAnB + nC
13.11Coeficientes binomiais: Argumentos combinatório e algébrico
 
Possibilidade de 
caminho entre A e C 
passando por B
Possibilidade de 
caminho direto 
entre A e C
número de caminhos que unem A e C passando por B +
número de caminhos que unem A e C diretamente
N = C(nA, 1)C(nB, 1) + C(nC, 1) = nAnB + nC
caminhos que
unem A e B
caminhos que
unem B e C
caminhos que unem
diretamente A e C
name=clic4
• |U| = N × N = (nAnB + nC)2
caminhos
que unem 
C e A
caminhos
que unem 
A e C
Cálculo de |U|:
• N:= número de caminhos que unem A e C =
• Número de caminhos que unem C e A 
•A
•
B
•C
= (nAnB)
2
 + 2nAnBnC
13.12Coeficientes binomiais: Argumentos combinatório e algébrico 
 
|W| = (nAnB + nC)2 − nC2 
Resposta 2:
Exemplo 1 (continuação raciocínio 2) 
Resumindo:
|W| = |U| − |Y| , |Y| = nC2 , |U| = (nAnB + nC)2 
Resposta do problema:
O número de caminhos que partem de A, chegam a C 
e retornam a A passando pelo menos uma vez por B é
(nAnB + nC)
2
 − nC
2
 = nAnBnC + nCnBnA + (nAnB)
2
.
Observação
2nAnBnC + (nAnB)
2
 = (nAnB + nC)
2
 − nC
2
 = 
= (nAnB + nC) (nAnB + nC) − nC
2
 =
= nAnB(nAnB + nC) + nC(nAnB + nC) − nC
2
 = 
= nAnB(nC + nBnA) + nCnAnB
13.13Coeficientes binomiais: Argumentos combinatório e algébrico
 
Exemplo 2: 
Determine o raciocínio combinatório no exemplo 1 
motivado pela expressão nAnB(nC + nBnA) + nCnAnB ?
caminhos que
unem A e C
passando por B
caminhos
que unem 
C e A
caminhos que unem 
A e C e retornam a A
passando 1 vez por B
13.14Coeficientes binomiais: Argumentos combinatório e algébrico
 
M := nAnB(nC + nBnA) + nCnAnB 
Resolução: 
•
•
•
1
2...
1
2...
nA nB
nC
A
B
C
1
2...
M:= número de caminhos que unem A e C passando por B e retornam a A
 por qualquer caminho + número de caminhos que unem A e C sem
 passar por B e retornam a A passando por B.
S:= conjunto de caminhos que unem A e C passando por B e retornam a A.
T:= conjunto de caminhos que unem diretamente A e C e retornam a A 
 passando por B.
13.15Coeficientes binomiais: Argumentos combinatório e algébrico
 
Resposta: O raciocínio combinatório motivado por
 nAnB(nC + nBnA) + nCnAnB corresponde a considerar
W = S ∪ T , |S| = nAnB(nC + nBnA) , |T| = nCnAnB ,
|W| = |S| + |T| = M (S ∩ T = ∅) P.A.
13.16Coeficientes binomiais 
Desafio Voltar
C(n, r) =
n!________
r! (n − r)!
Prova: Argumento algébrico 
=
n!
= C(n, n − r) __________________
(n − r)! (n − (n − r))!
Conclusão: 
 Tem-se o mesmo número de combinações de r elementos escolhidos 
 entre n e de combinações de (n − r) elementos escolhidos entre n, 
 ou seja, C(n, r) = C(n, n − r).
Fixada uma combinação der elementos entre n
definida uma combinação de (n − r) elementos entre n 
automaticamente está
⇑
( __ __ __ __ __ )x x
r
( __ __ __ __ __ )x x x
Identidades:
(1) Combinação complementar (ou de simetria)
C(n, r) = C(n, n − r)
Argumento combinatório (desafio)
n − r
n
(2) Relação de Stifel (1486 - 1567) ou Fórmula de Pascal (1623 - 1662)
C(n, r) + C(n, r + 1) = C(n + 1, r + 1)
Desafio Voltar
= C(n + 1, r + 1)
(n + 1)!________________________
(r + 1)! ((n + 1) − (r + 1))! 
=
_____________
 (r + 1)! (n − r)! 
n!
[(r + 1) + (n − r)] 
n! (n + 1)_____________
 (r + 1)! (n − r)! 
==
=
(k+1)k! = (k+1)!
(k = r; k = n−r+1)
+ =_____________
 (r + 1)! (n − r)! 
n! (n − r)_____________
 (r + 1)! (n − r)! 
n! (r + 1)
13.17Coeficientes binomiais: Identidades 
Prova: Argumento algébrico (desafio!) 
n!
C(n, r) + C(n, r + 1) = +________
r! (n − r)! 
__________________
 (r + 1)! (n − (r + 1))! 
n!
Prova (continuação):
(por exemplo, n homens, 1 mulher).
As diferentes maneiras de selecionar nesse grupo 
um subgrupo de r + 1 elementos (por exemplo, 
r + 1 pessoas entre os n homens e 1 mulher) podem
ser decompostos em 2 classes disjuntas:
• os que têm r do mesmo tipo e 1 do outro tipo
(por exemplo, r homens e 1 mulher)
• os que têm r + 1 do mesmo tipo
(por exemplo, r + 1 homens)
Seja um grupo (conjunto) formado por n + 1 elementos,
onde n são do mesmo tipo e 1 é de outro tipo
13.18Coeficientes binomiais: Identidades 
Argumento combinatório 
Logo, pelo princípio da adição, resulta: 
Prova (continuação argumento combinatório):
O número de modos de selecionar nesse grupo r + 1
elementos entre n + 1 é igual a
13.19Coeficientes binomiais: Identidades
Ou seja,
C(n + 1, r + 1) = C(n, r) + C(n, r + 1)
+
O número de modos de selecionar r elementos entre n
O número de modos de selecionar r + 1 elementos entre n
C(n, r + 1)
C(n + 1, r + 1)
C(n, r)
Observação
Relação de Stifel
C(n + 1, r + 1) = C(n, r) + C(n, r + 1) n = 1, 2, ...
r = 0, 1, ... , n−1
13.20Coeficientes binomiais: Identidades 
é equivalente a:
C(n, r) n = 2, ...
r = 1, 2, ... , n−1
= C(n − 1, r − 1 ) + C(n − 1, r)
(3) Condições de fronteira
C(n, 0) = C(n, n) = 1 , n = 0, 1, ...
(é a condição de simetria para r = 0)
(é a condição de simetria para r = 1)
13.21Coeficientes binomiais: Identidades
(4) Condições secundárias
C(n, 1) = C(n, n − 1) = n , n = 1, 2, ...
Triângulo de Pascal:
C(2, 0) C(2, 1) C(2, 2)n = 2
C(3, 0) C(3, 1) C(3, 2) C(3, 3)
C(4, 0) C(4, 1) C(4, 2) C(4, 3) C(4, 4)
C(5, 0) C(5, 1) C(5, 2) C(5, 3) C(5, 4) C(5, 5)
n = 3
n = 4
n = 5
13.22Coeficientes binomiais
Gráfico 1
• Ilustração:
linhas
C(0, 0)
C(1, 0) C(1, 1)
n = 0
n = 1
C(4, 2) = C(3, 1) + C(3, 2) = 3 + 3 = 6 (n = 4, r = 2)
Observação: C(n, r) está na linha n e na diagonal r
Relação C(n, r) = C(n − 1, r − 1 ) + C(n − 1, r) 
13.23Coeficientes binomiais: Triângulo de Pascal
Notação: C(n, r) = C
r
n
Gráfico 2
6
10 10
• Ilustração: C00
C
0
1
C
0
2
C
0
3
C
0
4
C
0
5
C
1
1
C
1
2
C
1
3
C
1
4
C
1
5
C
2
2
C
2
3
C
2
4
C
2
5
C
3
3
C
3
4
C
3
5
C
4
4
C
4
5 C
5
5
• C
r
n = C
r−1
n−1 + C
r
n−1 (relação de Stifel) n = 2, 3,... , r = 1, 2,...
• C
1
n = C
n−1
n = n (condições secundárias) n = 2, 3, ...
3
2
3
4 4
5 5
1
1 1
1 1
1 1
1 1
11
• C
0
n = C
n
n = 1 (condições de fronteira) n = 0, 1, 2, ...
Propriedades consideradas:
Observação: C
r
n está na linha n e na coluna r
Resolução: (desafio)
13.24Coeficientes binomiais: Triângulo de Pascal
Desafio Voltar
Resposta: A linha 7 do triângulo de Pascal está dada por:
 1 7 21 35 35 21 7
n = 6
1+6 = 7 6+15 = 21 15+20 = 35 20+15 = 35 15+6 = 21 6 + 1 = 7
n = 7
relações de Stifel
condições de fronteira
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
Exemplo 3:
Dada a linha 6 do triângulo de Pascal:
1 6 15 20 15 6 1
Calcule a linha 7 usando as condições de fronteira e
as relações de Stifel (fórmula de Pascal).
• Ilustração:
Motivação do teorema das linhas
Teorema das linhas, das colunas e das diagonais:
13.25Coeficientes binomiais
n Soma da linha nObservações:
1 + 3 + 3 + 1 = 83
1 + 7 + 21 + 35 + 35 + 21 + 7 + 1 = 1287
1 + 4 + 6 + 4 + 1 = 164
= 2
3
= 2
4
= 2
7
Gráfico 1 Gráfico 2 
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
1
1
1
1
1
1
1
1
1
2
3
4
5
6
7
1
3
6
10
15
21
1
4
10
20
35
1
5
15
35
1
6
21
1
7 1
n
0
1
2
3
4
5
6
7
13.26Coeficientes binomiais: Teorema das linhas
• Ilustração:
A soma dos elementos da linha 8 do triângulo de
Pascal é igual a 2
8
 = 256.
Observação:
Pelo teorema das linhas, podemos calcular a soma
dos elementos de uma linha n sem necessidade de 
conhecer seus elementos.
Teorema das linhas
n = 0, 1, 2, ...C
0
n + C
1
n + C
2
n + ... + C
n
n = 2
n
 
13.27Coeficientes binomiais: Teorema das colunas
r Soma da coluna rObservações:
0 2 4
1 + 1 + 1 + 1 + 1 + 1 + 1 = 70
1 + 3 + 6 + 10 + 15 = 352
1 + 5 + 15 = 214
= C(7, 1) = C(6 + 1, 0 + 1) 
= C(7, 3) = C(6 + 1, 2 + 1) 
= C(7, 5) = C(6 + 1, 4 + 1) 
C
4
4
C
4
5
C
4
6
C
5
7
7 1 7 21 35 35 21 7 1
Motivação do teorema das colunas
• Ilustração:
n
0
1
2
3
4
5
6
1
1
1
1
1
1
1
1
2
3
4
5
6
1
3
6
10
15
1
4
10
20
1
5
15
1
6 1
r
0 1 2 3 4 5 6
13.28Coeficientes binomiais: Teorema das colunas
• Ilustração:
A soma da coluna associada a r = 1 do triângulo de
Pascal com o número de linhas n = 6 é C
1+1
6+1 = C
2
7 = 21.
Teorema das colunas
C
r
r + C
r
r+1 + C
r
r+2 + ... + C
r
n = C
r+1
n+1 
0 ≤ r ≤ n
n = 0, 1, 2, ...
(k + 2)!_______
(k − 1)!
= Σ
50
k = 1
= Σ
50
k = 1
 
1.2 ... (k − 1) k(k + 1)(k + 2)__________________________
1.2 ... (k − 1)
13.29Coeficientes binomiais: Teorema das colunas
=
= 3! Σ
50
k = 1
(k + 2)!______________
3! ((k + 2) − 3)!
= Σ
50
k = 1
 
3! (k + 2)!__________
3! (k − 1)!
Resolução:
S = Σ
50
k = 1
k(k + 1)(k + 2) =
Exemplo 4:
Determine o valor da soma
S = 1.2.3 + 2.3.4 + 3.4.5 + ... + 50.51.52
= 3! Σ
50
k = 1
coluna do triângulo de 
Pascal, r = 3, n = 52
=
C
3
k+2 = 3! (C
3
3 + C
3
4 + ... + C
3
52) = 6 . C
4
53 = 1.756.950
T.C.
Exemplo 5:
Usando as condições secundárias e o teorema das
colunas obtenha a identidade
Resolução: (desafio) Desafio Voltar
13.30Coeficientes binomiais: Teorema das colunas
n = 1, 2, ...1 + 2 + 3 + ... + n = 
n(n + 1)_______
2
= 
(n + 1)!__________
2! (n − 1)!
= 
n(n + 1)________
2
= = 
(n + 1) n(n − 1)!________________
2! (n − 1)!
= C
2
n+1 = 
(n + 1)!_____________
2! (n + 1 − 2)!
=
T.C.
C.S.
1 + 2 + 3 + ... + n = C
1
1 + C
1
2 + C
1
3 + ... C
1
n =
13.31Coeficientes binomiais: Teorema das diagonais
7 1 7 21 35 35 21 7 1 1 7 21 35 35 21 7 1
= C
2
7
 = C
4
7 
• Ilustração:
Motivação do teorema das diagonais
Gráfico 1 Gráfico 2 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 11 6 15 20 15 6 1
1
1
1
1
1
1
1
1
2
3
4
5
6
1
3
6
10
15
1
4
10
20
1
5
15
1
6 1
n
0
1
2
3
4
5
6
C
0
4 + C
1
5 + C
2
6 = 1 + 5 + 15 = 21
1
5
15
1
5
15
1
3
6
10
15
C
0
2 + C
1
3 + C
2
4 + C
3
5 + C
4
6 = 1 + 3 + 6 + 10 + 15 = 35 
Observações:
1
3
6
10
15
• Ilustração:
n = 2, r = 4, n + r = 6
C
0
2 + C
1
3 + C
2
4 + C
3
5 + C
4
6 = C
4
7 = 35 
13.32Coeficientes binomiais: Teorema das diagonais
n = 0, 1, 2, ...
r = 0, 1, 2, ...
Teorema das diagonais
C
0
n + C
1
n+1 + C
2
n+2 + ... + C
r
n+r = C
r
n+r+1 
13.33Coeficientes binomiais
Resumo:
Definição:
Coeficiente binomial: (0 ≤ r ≤ n)C(n, r) =
n!_________
r! (n − r)!
Argumentos:
Na dedução de propriedades envolvendo coeficientes 
binomiais
• combinatórios • algébricos
Observação:
Raciocínios combinatórios equivalentes geram 
identidades algébricas e vice-versa.
13.34Coeficientes binomiais: Resumo
Identidades:
(1) Combinação complementar : C(n, r) = C(n, n − r)
(3) Condições de fronteira : C(n, 0) = C(n, n) = 1
(4) Condições secundárias : C(n, 1) = C(n, n − 1) = n
(2) Relação de Stifel : 
 C(n, r) = C(n − 1, r − 1) + C(n − 1, r)
n = 2, ...
r = 0, 1, ... , n−1
13.35Coeficientes binomiais: Resumo
Triângulo de Pascal:
C
0
0
C
0
1
C
0
2
C
0
3
C
1
1
C
1
2
C
1
3
C
2
2
C
2
3 C
3
3
1
1
1
1
1
2
3
1
3 1
. . .
. . .
. . .
C(2, 0) C(2, 1) C(2, 2)
C(0, 0)
C(1, 0) C(1, 1)
C(3, 0) C(3, 1) C(3, 2) C(3, 3)
Teoremas:
• das colunas: C
r
r + C
r
r+1 + ... + C
r
n = C
r+1
n+1 
• das diagonais: C
0
n + C
1
n+1+ C
2
n+2+ ... + C
r
n+r= C
r
n+r+1 
(linha n)
(coluna r)
(diagonal n)
• das linhas: C
0
n + C
1
n + ... + C
n
n = 2
n