Aula_013_Coeficientes binomiais e aplicações

Coeficientes binomiais

Binmio de Newton

Mdulo: Coeficientes binomiais e aplicaes

13.1

Apresentar identidades envolvendo coeficientes

binomiais.

Na anlise de algoritmos aparece a necessidade de

manipular relaes envolvendo coeficientes

binomiais.

Objetivo:

Importncia:

13.2Coeficientes binomiais e aplicaes

Definio

Argumentos combinatrio e algbrico

Identidades

Tringulo de Pascal

Teoremas das linhas, das colunas e das diagonais

13.3Coeficientes binomiais e aplicaes

Aula 13: Coeficientes binomiais

Definio:

Chamamos C(n, r) de coeficiente binomial.

13.4Coeficientes binomiais

(0 r n)

Observao

C(n, r) =n!_________

r! (n r)!

expresso algbrica

do coeficiente binomial

envolvendo fatoriais

nmero de possibilidades

de escolher r objetos

diferentes entre n objetos

diferentes

O raciocnio combinatrio est baseado na

decomposio de um conjunto em subconjuntos

adequados e na contagem de seus elementos

aparecem as combinaes simples.

O raciocnio algbrico est baseado na manipulao

dos fatoriais.


combinatrios

algbricos

Argumentos combinatrio e algbrico:

Dois tipos de argumentos podem ser usados na

deduo de teoremas e identidades envolvendo

fatoriais ou coeficientes binomiais:

Observaes:

13.6Coeficientes binomiais: Argumentos combinatrio e algbrico

Na resoluo de problemas combinatrios tem-se que:

um raciocnio combinatrio determina a

forma de uma expresso algbrica

e vice-versa

uma forma da expresso algbrica sugere um

raciocnio combinatrio.

raciocnios combinatrios equivalentes geram

identidades algbricas e vice-versa.

Exemplo 1:

Considere trs cidades A, B, C. Sejam nA, nB e nC os

nmeros 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?


1

2...

nB

1

2...

nA

1

2...

nC

Possibilidade 1:

Possibilidade 2:

Possibilidade 3:

Ilustrao

A

B

C

Exemplo 1 (continuao):

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)


Resoluo: Raciocnio 1

A

B

C

Possibilidade 1: caminho c1



(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 (raciocnio 1):

= C(nA, 1) C(nB, 1) C(nC, 1) = nAnBnC

= C(nC, 1) C(nB, 1) C(nA, 1) = nCnBnA


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.


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) = nC2caminhos que unem

diretamente A e C

caminhos que unem

diretamente C e A

Exemplo 1 (continuao):

Raciocnio 2 (baseado em complemento de um conjunto)

A C

B

Exemplo 1 (raciocnio 2)

= N = nAnB + nC


Possibilidade de caminho entre A e C

passando por B

Possibilidade de caminho direto

entre A e C

nmero de caminhos que unem A e C passando por B +

nmero 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)2caminhos

que unem

C e A

caminhos

que unem

A e C

Clculo de |U|: N:= nmero de caminhos que unem A e C =

Nmero de caminhos que unem C e A

A

B

C

= (nAnB)2 + 2nAnBnC


|W| = (nAnB + nC)2 nC2 Resposta 2:

Exemplo 1 (continuao raciocnio 2)

Resumindo:

|W| = |U| |Y| , |Y| = nC2 , |U| = (nAnB + nC)2

Resposta do problema:

O nmero 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.

Observao

2nAnBnC + (nAnB)2 = (nAnB + nC)

2 nC

2 =

= (nAnB + nC) (nAnB + nC) nC2 =

= nAnB(nAnB + nC) + nC(nAnB + nC) nC2 =

= nAnB(nC + nBnA) + nCnAnB


Exemplo 2:

Determine o raciocnio combinatrio no exemplo 1

motivado pela expresso 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


M := nAnB(nC + nBnA) + nCnAnB

Resoluo:

1

2...

1

2...nA nB

nC

A

B

C1

2...

M:= nmero de caminhos que unem A e C passando por B e retornam a A

por qualquer caminho + nmero 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.


Resposta: O raciocnio combinatrio 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.


Desafio Voltar

C(n, r) =n!________

r! (n r)!

Prova: Argumento algbrico

=n!

= C(n, n r) __________________(n r)! (n (n r))!

Concluso:

Tem-se o mesmo nmero de combinaes de r elementos escolhidos

entre n e de combinaes de (n r) elementos escolhidos entre n,

ou seja, C(n, r) = C(n, n r).

Fixada uma combinao de r elementos entre n

definida uma combinao de (n r) elementos entre n

automaticamente est

( __ __ __ __ __ )x xr

( __ __ __ __ __ )x x x

Identidades:

(1) Combinao complementar (ou de simetria)

C(n, r) = C(n, n r)

Argumento combinatrio (desafio)

n r

n

(2) Relao de Stifel (1486 - 1567) ou Frmula 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 = nr+1)+ =_____________

(r + 1)! (n r)!

n! (n r)_____________ (r + 1)! (n r)!

n! (r + 1)

13.17Coeficientes binomiais: Identidades

Prova: Argumento algbrico (desafio!)

n!C(n, r) + C(n, r + 1) = +________

r! (n r)! __________________ (r + 1)! (n (r + 1))!

n!

Prova (continuao):

(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) podemser decompostos em 2 classes disjuntas:

os que tm r do mesmo tipo e 1 do outro tipo(por exemplo, r homens e 1 mulher)

os que tm r + 1 do mesmo tipo(por exemplo, r + 1 homens)

Seja um grupo (conjunto) formado por n + 1 elementos,

onde n so do mesmo tipo e 1 de outro tipo


Argumento combinatrio

Logo, pelo princpio da adio, resulta:

Prova (continuao argumento combinatrio):

O nmero de modos de selecionar nesse grupo r + 1

elementos entre n + 1 igual a


Ou seja,

C(n + 1, r + 1) = C(n, r) + C(n, r + 1)

+

O nmero de modos de selecionar r elementos entre n

O nmero de modos de selecionar r + 1 elementos entre n

C(n, r + 1)

C(n + 1, r + 1)

C(n, r)

Observao

Relao de Stifel

C(n + 1, r + 1) = C(n, r) + C(n, r + 1) n = 1, 2, ...

r = 0, 1, ... , n1


equivalente a:

C(n, r) n = 2, ...

r = 1, 2, ... , n1

= C(n 1, r 1 ) + C(n 1, r)

(3) Condies de fronteira

C(n, 0) = C(n, n) = 1 , n = 0, 1, ...

( a condio de simetria para r = 0)

( a condio de simetria para r = 1)


(4) Condies secundrias

C(n, 1) = C(n, n 1) = n , n = 1, 2, ...

Tringulo 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


Grfico 1

Ilustrao: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)

Observao: C(n, r) est na linha n e na diagonal r

Relao C(n, r) = C(n 1, r 1 ) + C(n 1, r)

13.23Coeficientes binomiais: Tringulo de Pascal

Notao: C(n, r) = Cr

n

Grfico 2

6

10 10

Ilustrao: C00C

0

1

C0

2

C0

3

C0

4

C0

5

C1

1

C1

2

C1

3

C1

4

C1

5

C2

2

C2

3

C2

4

C2

5

C3

3

C3

4

C3

5

C4

4

C4

5 C5

5

Cr

n = Cr1

n1 + Cr

n1 (relao de Stifel) n = 2, 3,... , r = 1, 2,...

C1

n = Cn1

n = n (condies secundrias) n = 2, 3, ...

3

2

3

4 4

5 5

1

1 1

1 1

1 1

1 1

11

C0

n = Cn

n = 1 (condies de fronteira) n = 0, 1, 2, ...

Propriedades consideradas:

Observao: Cr

n est na linha n e na coluna r

Resoluo: (desafio)

13.24Coeficientes binomiais: Tringulo de Pascal

Desafio Voltar

Resposta: A linha 7 do tringulo 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

relaes de Stifel

condies de fronteira

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

Exemplo 3:

Dada a linha 6 do tringulo de Pascal:

1 6 15 20 15 6 1

Calcule a linha 7 usando as condies de fronteira eas relaes de Stifel (frmula de Pascal).

Ilustrao:

Motivao do teorema das linhas

Teorema das linhas, das colunas e das diagonais:


n Soma da linha nObservaes:

1 + 3 + 3 + 1 = 83

1 + 7 + 21 + 35 + 35 + 21 + 7 + 1 = 1287

1 + 4 + 6 + 4 + 1 = 164

= 23

= 24

= 27

Grfico 1 Grfico 2

1

1 1

1 2 11 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 11 7 21 35 35 21 7 1

1

1

111

1

11

1

234

5

67

136

10

1521

14

10

2035

1

5

1535

1

621

17 1

n

0

1

234

5

67

13.26Coeficientes binomiais: Teorema das linhas

Ilustrao:

A soma dos elementos da linha 8 do tringulo de

Pascal igual a 28 = 256.

Observao:

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, ...C0

n + C1

n + C2

n + ... + Cn

n = 2n

13.27Coeficientes binomiais: Teorema das colunas

r Soma da coluna rObservaes:

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)

C4

4

C4

5

C4

6

C5

7

7 1 7 21 35 35 21 7 1

Motivao do teorema das colunas

Ilustrao:

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

r0 1 2 3 4 5 6


Ilustrao:

A soma da coluna associada a r = 1 do tringulo de

Pascal com o nmero de linhas n = 6 C1+1

6+1 = C2

7 = 21.

Teorema das colunas

Cr

r + Cr

r+1 + Cr

r+2 + ... + Cr

n = Cr+1

n+1 0 r nn = 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)


=

= 3! 50

k = 1

(k + 2)!______________

3! ((k + 2) 3)!=

50

k = 1 3! (k + 2)!__________

3! (k 1)!

Resoluo:

S = 50

k = 1k(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 tringulo de

Pascal, r = 3, n = 52

=

C3

k+2 = 3! (C3

3 + C3

4 + ... + C3

52) = 6 . C4

53 = 1.756.950T.C.

Exemplo 5:

Usando as condies secundrias e o teorema dascolunas obtenha a identidade

Resoluo: (desafio) Desafio Voltar


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)!

= C2

n+1 = (n + 1)!_____________

2! (n + 1 2)!=

T.C.

C.S.1 + 2 + 3 + ... + n = C

1

1 + C1

2 + C1

3 + ... C1

n =

13.31Coeficientes binomiais: Teorema das diagonais

7 1 7 21 35 35 21 7 1 1 7 21 35 35 21 7 1

= C2

7

= C4

7

Ilustrao:

Motivao do teorema das diagonais

Grfico 1 Grfico 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

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

C0

4 + C1

5 + C2

6 = 1 + 5 + 15 = 21

1

5

15

1

5

15

1

3

6

10

15

C0

2 + C1

3 + C2

4 + C3

5 + C4

6 = 1 + 3 + 6 + 10 + 15 = 35

Observaes:

1

3

6

10

15

Ilustrao:

n = 2, r = 4, n + r = 6

C0

2 + C1

3 + C2

4 + C3

5 + C4

6 = C4

7 = 35

13.32Coeficientes binomiais: Teorema das diagonais

n = 0, 1, 2, ...

r = 0, 1, 2, ...

Teorema das diagonais

C0

n + C1

n+1 + C2

n+2 + ... + Cr

n+r = Cr

n+r+1


Resumo:

Definio:

Coeficiente binomial: (0 r n)C(n, r) =n!_________

r! (n r)!

Argumentos:

Na deduo de propriedades envolvendo coeficientes

binomiais

combinatrios algbricos

Observao:

Raciocnios combinatrios equivalentes geram

identidades algbricas e vice-versa.

13.34Coeficientes binomiais: Resumo

Identidades:

(1) Combinao complementar : C(n, r) = C(n, n r)

(3) Condies de fronteira : C(n, 0) = C(n, n) = 1

(4) Condies secundrias : C(n, 1) = C(n, n 1) = n

(2) Relao de Stifel :

C(n, r) = C(n 1, r 1) + C(n 1, r)n = 2, ...

r = 0, 1, ... , n1

13.35Coeficientes binomiais: Resumo

Tringulo de Pascal:

C0

0

C0

1

C0

2

C0

3

C1

1

C1

2

C1

3

C2

2

C2

3 C3

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: Cr

r + Cr

r+1 + ... + Cr

n = Cr+1

n+1

das diagonais: C0

n + C1

n+1+ C2

n+2+ ... + Cr

n+r= Cr

n+r+1

(linha n)

(coluna r)

(diagonal n)

das linhas: C0

n + C1

n + ... + Cn

n = 2n

Documents

Aula_013_Coeficientes binomiais e aplicações