Aula02_CoeficienteBinomial.pptx

Prévia do material em texto

10/29/13	
  
1	
  
Coe$icientes	
  Binomiais	
  
Matemá.ca	
  Discreta	
  II	
  
(Rosen	
  Cap.6)	
  
André	
  Câmara	
  
Coe$icientes	
  Binomiais	
  
•  O	
  símbolo	
  	
  	
  	
  	
  	
  	
  	
  	
  ,	
  lido	
  “n	
  sobre	
  r”	
  ,	
  onde	
  r	
  e	
  n	
  são	
  
inteiros	
  posi.vos	
  com	
  r	
  ≤	
  n,	
  é	
  dado	
  por:	
  
Ou,	
  	
  
n
r
!
"
#
$
%
&
Coe$icientes	
  Binomiais	
  
•  	
  	
  	
  	
  	
  	
  	
  	
  é	
  o	
  número	
  de	
  maneiras	
  de	
  escolher	
  r	
  saídas	
  
(não	
  ordenadas)	
  de	
  n	
  valores	
  possíveis,	
  também	
  
conhecida	
  como	
  combinação	
  ou	
  número	
  
combinatorial	
  
•  Ou	
  seja,	
  é	
  o	
  número	
  de	
  r	
  subconjuntos	
  possíveis	
  
de	
  um	
  conjunto	
  de	
  n	
  itens	
  dis.ntos.	
  
n
r
!
"
#
$
%
&
Coe$iciente	
  Binomial	
  Exemplo	
  1	
  
	
  
	
  
Note	
  que	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  tem	
  sempre	
  r	
  termos	
  em	
  ambos	
  o	
  numerador	
  e	
  denominador	
  	
  
	
  
Coe$icientes	
  Binomiais	
  Propriedades	
  
•  Dado	
  que	
  n	
  –	
  (n-­‐r)	
  =	
  r,	
  temos:	
  
•  Lemma	
  1:	
  
•  C(n,	
  r)	
  =	
  C(n,	
  n	
  −	
  r),	
  ou	
  seja:	
  	
  
•  Se	
  temos	
  a+b	
  =	
  n,	
  podemos	
  afirmar	
  que:	
  
Coe$icientes	
  Binomiais	
  Propriedades	
  
•  Mo.vado	
  pelo	
  fato	
  que	
  0!	
  =	
  1,	
  definimos:	
  
e	
  
10/29/13	
  
2	
  
Coe$iciente	
  Binomial	
  Exemplo	
  2	
  
•  Suponha	
  que	
  queremos	
  calcular	
  	
  	
  	
  	
  	
  	
  	
  .	
  Sabemos	
  
que	
  haverá	
  7	
  fatores	
  no	
  numerador	
  e	
  no	
  
denominador.	
  
•  Entretanto,	
  observe	
  que	
  10-­‐7	
  =	
  3.	
  Podemos	
  usar	
  
o	
  Lemma	
  1	
  para	
  reduzir	
  o	
  número	
  de	
  fatores:	
  
Teorema	
  Binomial	
  
•  Uma	
  expressão	
  binomial	
  é	
  simplesmente	
  a	
  soma	
  
de	
  dois	
  termos	
  (ex.:	
  x+y)	
  
•  Os	
  números	
  	
  	
  	
  	
  	
  	
  	
  	
  são	
  chamados	
  coeficientes	
  
binomiais,	
  dado	
  que	
  eles	
  aparecem	
  como	
  
coeficientes	
  na	
  expansão	
  de	
  (a+b)n	
  	
  
Podemos	
  calcular	
  os	
  coeficientes	
  ci	
  contando	
  os	
  argumentos.	
  
Expandir	
  selecionando	
  1	
  ou	
  x	
  em	
  cada	
  fator	
  e	
  mul.plicando.	
  
e.g. 
Neste	
  caso,	
  c0	
  =	
  1,	
  c1	
  =	
  3,	
  c2	
  =	
  3,	
  c3	
  =	
  1.	
  
Expressão	
  Binomial	
  Exemplo	
   Expressão	
  Binomial	
  
•  Podemos	
  u.lizar	
  raciocínio	
  combinatorial	
  ao	
  
invés	
  de	
  mul.plicar	
  
(x+y)3	
  =	
  (x+y)	
  (x+y)	
  (x+y)	
  
Como	
  podemos	
  combinar	
  esses	
  coeficientes?	
  
	
  
	
  
xxx	
  +	
  xxy	
  +	
  xyx	
  +	
  xyy	
  +	
  yxx	
  +	
  yxy	
  +	
  yyx	
  +	
  yyy	
  	
  
Apenas	
  uma	
  forma	
  de	
  	
  
Escolher	
  3	
  x	
  ou	
  3	
  y	
  
De	
  três	
  formas	
  
(escolher	
  2	
  x	
  dentre	
  3	
  termos)	
  
De	
  três	
  formas	
  (escolher	
  2	
  y	
  	
  
dentre	
  3	
  termos)	
  
	
  
n fatores 
Cada termo corresponde a selecionar 1 ou x de cada um dos n fatores. 
O Coeficiente ck é igual ao número de termos com exatamente k x’s. 
Cada termo com exatamente k x’s corresponde a escolher k posições de x. 
Dessa forma, 
Chamados de Coeficientes Binomiais 
Teorema	
  Binomial	
  -­‐	
  Exemplo	
  
(1+X)1 = 
(1+X)0 = 
(1+X)2 = 
(1+X)3 = 
1 
1 + 1X 
1 + 2X + 1X2 
1 + 3X + 3X2 + 1X3 
(1+X)4 = 1 + 4X + 6X2 + 4X3 + 1X4 
Teorema	
  Binomial	
  
Observe	
  que	
  o	
  coeficiente	
  é	
  a	
  soma	
  dos	
  dois	
  coeficientes	
  no	
  nível	
  anterior.	
  
Isto	
  é	
  chamado	
  de	
  fórmula	
  de	
  Pascal.	
  
10/29/13	
  
3	
  
Em geral, temos a seguinte identidade: 
Quando x=1, y=1 (1+1)n, implica que: 
Porque se escolhermos k x’s então existem n-k y’s. 
Corolário: 
A soma de coeficientes binomiais é igual a 2n. 
Teorema	
  Binomial	
  
Corolário: 
A soma de coeficientes binomiais “pares” é igual a 
Soma de coeficientes binomiais “ímpares”. 
Teorema	
  Binomial	
  
Em	
  geral,	
  temos	
  a	
  seguinte	
  iden.dade:	
  
Se	
  x	
  =	
  -­‐1,	
  y	
  =	
  1,	
  i.e.	
  (1	
  -­‐1)n,	
  	
  isso	
  implica	
  que	
  	
  
Teorema	
  Binomial	
  
	
  
•  Os	
  coeficientes	
  das	
  potências	
  sucessivas	
  de	
  (a+b)	
  
podem	
  ser	
  arranjados	
  em	
  uma	
  formação	
  
triangular	
  de	
  inteiros	
  
=	
  ?	
  
Triângulo	
  de	
  Pascal	
  
Triângulo	
  de	
  Pascal	
  
•  Propriedades:	
  
•  O	
  primeiro	
  e	
  o	
  úl.mo	
  número	
  em	
  cada	
  linha	
  é	
  
1	
  
•  Todos	
  os	
  outros	
  números	
  podem	
  ser	
  ob.dos	
  
somando-­‐se	
  os	
  dois	
  números	
  acima	
  dele.	
  
Exercício	
  
•  Qual	
  o	
  coeficiente	
  de	
  x12y13	
  na	
  expansão	
  de	
  	
  
(x+y)25?	
  
•  Qual	
  o	
  coeficiente	
  de	
  x12y13	
  na	
  expansão	
  de	
  	
  
(2x-­‐3y)25?	
  
25
13
!
"
#
$
%
&=
25!
13!(25−13)! = 5.200.300
25
13
!
"
#
$
%
&(2)25−13(−3)13 = − 25!13!12!(2)
12 (3)13
10/29/13	
  
4	
  
Identidades	
  úteis	
  
•  Algumas	
  iden.dades	
  são	
  bastante	
  úteis	
  e	
  podem	
  
ser	
  usadas	
  para	
  provar	
  outros	
  teoremas	
  
•  Corolário	
  1:	
  
•  	
  Seja	
  n	
  um	
  inteiro	
  não	
  nega.vo,	
  então:	
  
Corolário	
  1	
  -­‐	
  Prova	
  
•  Usar	
  o	
  teorema	
  binomial,	
  com	
  x=1	
  e	
  y=1	
  
Corolário	
  2	
  
•  Seja	
  n	
  um	
  inteiro	
  posi.vo.	
  Então	
  
•  Provar	
  
•  x=1	
  e	
  y=-­‐1	
  
Identidade de Pascal 
Prova Direta: 
Triângulo	
  de	
  Pascal	
  
Teorema