Aula 09 - Triângulo de Pascal

Prévia do material em texto

1
 
 
 
Aula 9 
 
 
TRIÂNGULO DE PASCAL 
 
 
 
Objetivos 
Apresentar o Triângulo de Pascal e verificar algumas de suas propriedades. 
Aplicar as propriedades do Triângulo de Pascal em alguns problemas. 
 
 
 Chamamos de Triângulo de Pascal a tabela abaixo em forma de triângulo. 
 
 
 1 
 1 1 
 1 2 1 ← linha 
 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 
 ........................................................... 
 ↑ 
 coluna 
 
Essa tabela continua indefinidamente e cada elemento é da forma C(n, p), onde n é 
a linha e p a coluna, ambos começando por 0. 
 
Podemos também escrever o Triângulo de Pascal da seguinte forma 
 
 C(0, 0) 
 C(1, 0) C(1, 1) 
 C(2, 0) C(2, 1) C(2, 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) 
 ............................................................................ 
 
 
 Cada elemento da tabela é chamado de número binomial ou coeficiente 
binomial. 
 
 Analisemos, agora, as propriedades do Triângulo de Pascal. 
 
1ª Propriedade 
 O primeiro e o último elemento de qualquer linha é 1. 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 2
 
 
Demonstração: 
 Seja n uma linha qualquer. O primeiro elemento da linha é C(n, 0) e o último é 
C(n, n). Usando a fórmula do número de combinações simples segue que 
C(n, 0) = 
)!0!.(0
!
−n
n = 1 e C(n, n) = 
)!!.(
!
nnn
n
− = 1 
 
 
2ª Propriedade 
 A soma de dois coeficientes binomiais consecutivos de uma mesma linha é 
igual ao coeficiente situado imediatamente abaixo da última parcela. 
 
 Esta propriedade é conhecida como relação de Stifel e pode ser escrita em termos 
de coeficientes binomiais como 
 
C(n, p) + C(n, p + 1) = C(n + 1, p + 1) , se n ≥ 1 
 
 
 Antes de demonstrá-la, observemos essa propriedade no Triângulo de Pascal. 
 
 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 
 .................................................. 
 
 
 
Demonstração: 
 Utilizando a fórmula do cálculo do número de combinações simples temos 
C(n, p) + C(n, p + 1) = 
!.)!(
!
ppn
n
− + )!1(.)]!1([
!
++− ppn
n 
 
Calculando o m.m.c dos denominadores das frações e as substituindo por frações 
equivalentes encontramos 
 
C(n, p) + C(n, p + 1) = 
)!1(.)!(
!.)1(
+−
+
ppn
np + 
)!1(.)!(
!.)(
+−
−
ppn
npn = 
)!1(.)!(
!.!.!!.
+−
−++
ppn
npnnnnp = 
 
= 
)!1(.)!(
)!1(
+−
+
ppn
n = C(n + 1, p + 1), como queríamos demonstrar. 
 
 
Exemplo 1 
 
 Oito alunos (Tânia, ...) fazem parte de um grêmio estudantil do colégio em que 
estudam. Uma comissão formada por 3 alunos vai representar o grêmio num desfile. 
Fundação CECIERJ Maria de Fatima Soares da Silva
 3
 
 
 O número de comissões possíveis é C(8, 3) = 56. Tânia pode ou não estar em 
cada uma das 56 comissões possíveis. 
 O número de comissões em que Tânia sempre está presente é C(7, 2) = 21, pois 
só teremos que escolher 2 alunos dentre os 7 restantes. 
O número de comissões em que Tânia nunca está presente é C(7, 3) = 35, pois 
teremos que escolher 3 alunos dentre os 7 restantes. 
 Observe a interpretação combinatória da relação de Stifel e veja que 
C(7, 2) + C(7, 3) = C(8, 3) 
 
 
 
3ª Propriedade 
 A partir de n = 1, em uma mesma linha do Triângulo de Pascal, os elementos 
eqüidistantes dos extremos são iguais; ou seja, C(n, p) = C(n, n – p). 
 
Demonstração: 
 C(n, n – p) = 
)!(.)]!([
!
pnpnn
n
−−− = )!(.!
!
pnp
n
− = C(n, p) 
 
 
 
 Esta propriedade indica que há simetria nas linhas do Triângulo de Pascal. Na aula 
2, página 9, exemplo 14, temos uma interpretação combinatória de C(n, p) e C(n, n – p) e 
chamamos estas combinações de complementares. 
 
 Vejamos, por exemplo, a seguinte linha do Triângulo de Pascal 
 
 
 
6 = C(6, 1) = C(6, 5) e 15 = C(6, 2) = C(6, 4) 
 
 
Exemplo 2 
 
 Calcule x de modo que C(16, 5x ) = C(16, x + 4). 
 
 A equação C(16, 5x) = C(16, x + 4) tem solução se 5x = x + 4 ou se C(16, 5x ) e 
C(16, x + 4) forem combinações complementares. Logo 
 
5x = x + 4 ⇒ x = 1 
ou 
5x + x + 4 = 16 ⇒ x = 2 
 
Portanto, x = 1 e x = 2 são soluções da equação dada. 
 
 
1 6 15 20 15 6 1 
Fundação CECIERJ Maria de Fatima Soares da Silva
 4
 
 
 
4ª Propriedade 
 A soma dos elementos da linha n é igual a 2n, isto é, 
C(n,0) + C(n, 1) + C(n, 2) + ... + C(n,n) = 2n (1) 
 
 
Demonstração: 
 Na aula 1, no exemplo 7, já demonstramos que o número de subconjuntos de um 
conjunto A com n elementos é igual a 2n. 
 
 Por definição, uma combinação simples é um subconjunto e que C(n, p) é o 
número de subconjuntos de A com p elementos. Portanto, 
C(n,0) + C(n, 1) + C(n, 2) + ... + C(n,n) 
é também o número de subconjuntos de A; logo segue a igualdade (1). 
 
 
 
Exemplo 3 
 Calcule k, sabendo que 255),(
1
=∑
=
k
i
ikC . 
 
 
 Desenvolvendo o somatório encontramos 
∑
=
k
i
ikC
1
),( = C(k, 1) + C(k, 2) + C(k, 3) + ... + C(k, k) = 255 (2) 
 
Pela 4ª propriedade temos que 
C(k, 0) + C(k, 1) + C(k, 2) + C(k, 3) + ... + C(k, k) = 2k (3) 
 
Como C(k, 0) = 1, a igualdade (3) pode ser escrita como 
C(k, 1) + C(k, 2) + C(k, 3) + ... + C(k, k) = 2k - 1 (4) 
 
 Comparando (2) com (4), vem que 
2k - 1 = 255 ⇒ 2k = 256 ⇒ 2k = 28 ⇒ k = 8 
 
 
5ª Propriedade 
 A soma dos primeiros elementos de uma coluna p é igual ao elemento da 
linha seguinte na (p+1)-ésima coluna. 
 
 
 Esta propriedade é conhecida como teorema das colunas e pode ser escrita da 
seguinte forma 
 
C(p, p) + C(p + 1, p) + C(p + 2, p) + ... + C(p + n, p) = C(p + n + 1, p + 1) (5) 
 
Antes de demonstrarmos essa propriedade, vamos exemplificar para facilitar o seu 
entendimento. Observe que o 1º elemento de uma coluna qualquer é da forma C(p, p). 
 
Escolhamos p = 0. 
Fundação CECIERJ Maria de Fatima Soares da Silva
 5
 
 
 1 
 1 11 2 1 
 1 3 3 1 
 1 4 6 4 1 
 1 5 10 10 5 1 
 1 6 15 20 15 6 1 
 .................................................. 
 
C(0, 0) + C(1, 0) + C(2, 0) + C(3, 0) + C(4,0) = 1 + 1 + 1 + 1 + 1 = 5 = C(5, 1) 
 
 Se, escolhermos p = 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 
 .................................................. 
 
C(2, 2) + C(3, 2) + C(4, 2) + C(5, 2) = 1 + 3 + 6 + 10 = 20 = C(6, 3) 
 
Demonstração: 
 Vamos aplicar a 2ª propriedade (relação de Stifel) aos elementos da coluna p + 1. 
 C(p+1, p+1) = C(p, p+1) + C(p, p) 
C(p+2, p+1) = C(p+1, p+1) + C(p+1, p) 
. 
. 
. 
C(p+n, p+1) = C(p+n-1, p+1) +C(p+n-1, p) 
C(p+n+1,p+1) = C(p+n, p+1) + C(p+n, p) 
 
Somando membro a membro essas igualdades e simplificando as parcelas iguais 
que aparecem nos membros opostos obtemos 
 C(p+n+1, p+1) = C(p,p+1) + C(p, p) + C(p+1, p) + … +C(p+n-1, p) + C(p+n, p) (6) 
 
 Como não existem subconjuntos com p+1 elementos de um conjunto com p 
elementos, C(p, p+1) = 0. Podemos também concluir que C(p, p+1) = 0 usando a 
primeira igualdade da demonstração e a 1ª propriedade, ou seja, 
C(p+1, p+1) = C(p, p+1) + C(p, p) ⇒ 1 = C(p, p+1) + 1 ⇒ C(p, p + 1) = 0 
 
Logo, (6) se reduz à igualdade desejada. 
 
 
Exemplo 4 
 
 Usar a 5ª propriedade para mostrar que 
 1 + 2 + 3 + 4 + 5 + ... + n = 
2
)1( +nn (7) 
Fundação CECIERJ Maria de Fatima Soares da Silva
 6
 
 
 
Sabemos que 
1 + 2 + 3 + ... + n = C(1, 1) + C(2, 1) + C(3, 1) + ... + C(n, 1) 
 
 Pela 5ª propriedade temos que 
C(1, 1) + C(2, 1) + C(3, 1) + ... + C(n, 1) = C(n+1, 2) 
 
 Calculemos C(n+1, 2). 
C(n+1, 2) = 
!2)!21(
)!1(
−+
+
n
n = 
!2.)!1(
)!1(
−
+
n
n = 
!2.)!1(
)!1(..)1(
−
−+
n
nnn = 
2
)1( +nn 
 
Das igualdades acima, segue a relação (7). 
 
 
6ª Propriedade 
 A soma dos primeiros elementos de uma diagonal do Triângulo de Pascal é 
igual ao elemento que está imediatamente abaixo da última parcela, ou seja, 
C(n, 0) + C(n+1, 1) + C(n+2, 2) + ... + C(n+p, p) = C(n+p+1, p) 
 
Exemplificando para n = 3 e p = 3. 
 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 
 .................................................. 
 
Esta propriedade é conhecida como teorema das diagonais. 
 
Demonstração: 
 Usando a 3ª propriedade (combinações complementares) podemos escrever 
C(n, 0) = C(n, n) 
C(n+1, 1) = C(n+1,n) 
C(n+2, 2) = C(n+2, n) e assim por diante até a linha n + p.. 
 
Logo, 
C(n, 0) + C(n+1, 1) + C(n+2,2) + C(n+3, 3) + ... + C(n+p, p) = 
= C(n, n) + C(n+1,n) + C(n+2, n) + C(n+3,n) + ... + C(n+p, n) (8) 
 
 Utilizando a 5ª propriedade (teorema das colunas) no segundo membro da 
igualdade (8), obtemos 
C(n, 0) + C(n+1, 1) + C(n+2, 2) + C(n+3, 3) + ... + C(n+p, n) = C(n+ p + 1, n + 1) (9) 
 
 E, aplicando, novamente, a 3ª propriedade no segundo membro da igualdade (9) 
obtemos o que queríamos, isto é, 
C(n, 0) + C(n+1, 1) + C(n+2, 2) + C(n+3, 3) + ... + C(n+p, n) = C(n+p+1, p) 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 7
 
 
Exemplo 5 
 
 Usando as propriedades do Triângulo de Pascal mostre que 
∑
=
+
n
k
kk
1
)1(. = 
3
)2)(1( ++ nnn 
 
 Desenvolvendo o somatório encontramos 
 
 ∑
=
+
n
k
kk
1
)1(. = 1.2 + 2.3 + 3.4 + ... + n(n+1) (10) 
 
O artifício que vamos utilizar é dividir ambos os membros da igualdade (10) por 2! 
 
!2
1 ∑
=
+
n
k
kk
1
)1(. = 
!2
)1(...
!2
4.3
!2
3.2
!2
2.1 +++++ nn (11) 
 
Observando cada parcela do segundo membro da igualdade (11), vemos que se 
trata de um número de combinações simples, tomadas 2 a 2, ou seja, 
 
!2
)1(...
!2
4.3
!2
3.2
!2
2.1 +++++ nn = C(2, 2) + C(3, 2) + C(4, 2) + ... + C(n+1, 2) 
 
Pela 5ª propriedade (teorema das colunas), temos que 
C(2, 2) + C(3, 2) + C(4, 2) + ... + C(n+1, 2) = C(n+2, 3) 
 
 
Mas C(n+2, 3) = 
!3.)!32(
)!2(
−+
+
n
n = 
!3.)!1(
)!2(
−
+
n
n = 
!3
)1)(2( nnn ++ (12) 
 
 
Observando a seqüência de igualdades acima vem 
!2
1 ∑
=
+
n
k
kk
1
)1(. = 
!3
)1)(2( nnn ++ ⇒ ∑
=
+
n
k
kk
1
)1(. = 2!. 
!3
)1)(2( nnn ++ ⇒ 
 
∑
=
+
n
k
kk
1
)1(. = 
3
)2)(1( ++ nnn 
 
 
 
Exemplo 6 
 
Obtenha, de forma simplificada, o valor da soma 
C(n,1) + 2C(n,2) + 3C(n,3) + ... + nC(n,n) , com n inteiro positivo. 
 
Escrevendo em forma de somatório, usando a fórmula do número de combinações 
simples e com algumas simplificações, obtemos 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 8
 
 
C(n, 1) + 2C(n,2) + 3C(n, 3) + ... + nC(n, n) = 
1
( , )
n
i
iC n i
=
∑ = 
1
!.
!.( )!
n
i
ni
i n i= −∑ = 
 
= 
1
!.
( 1)!( )!
n
i
ni
i i n i= − −∑ = 1
!
( 1)!.( )!
n
i
n
i n i= − −∑ = 1
( 1)!.
( 1)!.( )!
n
i
nn
i n i=
−
− −∑ = 
 
= 
1
. ( 1, 1)
n
i
n C n i
=
− −∑ = n 1
1
( 1, 1)
n
i
C n i
−
=
− −∑ = 
 
= n.[C(n-1, 0) + C(n-1, 1) + C(n-1, 2) + ... + C(n –1, n-1) 
 
Usemos a 4ª propriedade para a linha (n – 1) na última expressão acima e 
obteremos 
 
C(n,1) + 2C(n,2) + 3C(n,3) + ... + nC(n,n) = 
 
= n.[C(n-1, 0) + C(n-1, 1) + C(n-1, 2) + ... + C(n –1, n-1) = 
 
= n.2n-1 
 
 
7ª Propriedade 
 Temos C(n, p) < C(n, p + 1) se p < 
2
1−n e 
 C(n, p) > C(n, p + 1) se p > 
2
1−n 
 
Se n (n ≥ 2) é par, os valores de C(n, p), para p = 0, 1, ..., n vão crescendo e 
atingem seu máximo para p = 
2
n e depois vão decrescendo. Se n é ímpar, os valores de 
C(n, p), para p = 0, 1, 2, ..., n vão crescendo e atingirão valor máximo para dois valores 
de p, p = 
2
1−n e p = 
2
1+n e, em seguida, vão decrescendo. 
 
 Veja, por exemplo, as seguintes linhas do Triângulo de Pascal 
 
n = 6 1 6 15 20 15 6 1 
 ↑ 
 valor máximo em p = 
2
n = 3 
 
 
n = 7 1 7 21 35 35 21 7 1↑ ↑ 
 valor máximo em p = 
2
1−n = 3 e p = 
2
1+n = 4 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 9
 
 
Demonstração: 
 Calculemos C(n, p+ 1) – C(n, p) e, a seguir, analisemos o sinal desta diferença. 
 
C(n, p+ 1) – C(n, p) = 
!.)!(
!
)!1(.)!1(
!
ppn
n
ppn
n
−−+−− = )!1()!.(
)1(!)(.!
+−
+−−
ppn
pnpnn = 
 
= 
)!(.)!1(
)21(.!
pnp
pnn
−+
−− 
 
 Os fatoriais n!, (p + 1)! e (n – p)! são números inteiros positivos e, portanto, o sinal 
da diferença C(n, p+ 1) – C(n, p) é o mesmo do número inteiro n – 1 – 2p. 
 
 Temos que 
C(n, p + 1) – C(n, p) > 0 se n – 1 – 2p > 0, isto é, se p < 
2
1−n e 
 
C(n, p + 1) – C(n, p) < 0 se n – 1 – 2p < 0, isto é, se p > 
2
1−n . 
 
Exemplo 7 
 
 Calcule o valor máximo de C(18, p). 
 
Como n = 18 é um número par, segue da 7ª propriedade que o valor máximo de 
C(18, p) se dará quando p = 
2
18
2
=n = 9. 
 
Logo, o valor máximo de C(18, p) é C(18, 9) = 48620. 
 
 
 
Exercícios propostos 
1) Quantos subconjuntos não vazios possui um conjunto A com k elementos? R.: 2k- 1 
 
2) Sabendo que C(n – 1, k – 1) = 18 e C(n, n-k) = 60, calcule C(n – 1, k). R.: 42 
 
3) Mostre que para todo n∈ N* vale a relação 
C(n, 0) – C(n, 1) + C(n, 2) – C(n,3) + C(n, 4) - ... + (-1)nC(n, n) = 0 
 
4) Calcule C(10, 1) + C(10, 2) + ... + C(10, 9) , sem fazer os cálculos de cada parcela. 
R.: 1022 
 
5) Mostre que 
∑
=
n
k
k
1
2 = 12 + 22 + 32 + ...+ n2 = 
6
)12)(1( ++ nnn 
Sugestão: escreva k2 = k(k + 1) – k e use os exemplos (4) e (5). 
 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 10
 
 
6) Calcule ∑
=
10
0
),11(
k
kC . R.: 2047 
 
7) Calcule k nas equações 
a) C(30, k2) = C(30, 4k - 4) R.: 2 
b) C(10, k+6) = C(10, k-6) R.: 5 
 
8) Calcule a soma )2(.)1(.
20
1
++∑
=
iii
i
 R.: 53130 
Sugestão: Analise o exemplo 5 e divida por 3!. 
 
 
9) Qual(is) o(s) maior(es) número(s) binomial(is) C(n. p) para 
a) n = 10? b) n = 11? R.: a) 252; b) 462 
Fundação CECIERJ Maria de Fatima Soares da Silva