Slides 15 0607

Prévia do material em texto

Matemática Discreta
Aula nº 15
Francisco Restivo
2007-05-02
2
Técnicas de contagem:
Princípio da adição: 
Em geral
|A ∪ B| = |A| + |B| - |A ∩ B|
e no caso de os conjuntos A e B serem disjuntos
|A ∪ B| = |A| + |B|
Princípio da multiplicação:
|A × B| = |A| . |B|
Cardinal de P(A):
O conjunto das partes de A tem 2|A| elementos.
Problema:
Quantas relações binárias distintas se podem definir num conjunto 
A com N elementos? 2N2
3
Algumas relações úteis:
Arranjos, permutações e combinações:
Na contagem dos arranjos e das permutações, a ordem é
importante, enquanto que na contagem das combinações, não.
Arranjos, permutações e combinações:
( ) ( ) ( ) ( )
( ) ( ) ( )
( ) ( )( ) ( )!rnr!
n!
rP
rn,Arn,C
n!...2.11nnnn,AnP
!rn
n!1rn...1nnrn,A
−==
=−==
−=+−−=
( )
r)-nC(n,r)C(n,
1)r1).(nrA(n,rn,A
=
+−−=
4
Problema:
Num departamento trabalham 4 mulheres e 9 homens. Determinar:
(a) o número de comissões com 2 mulheres e 3 homens que se 
podem formar;
(b) o número de comissões de 5 elementos com, pelo menos, 2 
mulheres e 2 homens.
Resposta:
(a) C(4, 2) × C(9, 3) = (4×3/2)×(9×8×7/6) = 6×84 = 504
(b) C(4, 2) × C(9, 3) + C(4, 3) × C(9, 2) = 6×84 + 4×36 = 648. 
Outro problema:
Um código é constituído por seis símbolos: três letras (L) do 
alfabeto (de 26 letras) seguidas de três dígitos (D). Seja X o 
conjunto de todos os códigos possíveis (LLLDDD). Determinar 
o número de elementos de X nas seguintes condições:
(a) tanto as letras como os dígitos podem ser repetidos;
(b) os dígitos não podem ser repetidos;
(c) as letras não podem ser repetidas;
(d) nem as letras nem os dígitos podem ser repetidos.
5
Fórmula de Pascal:
C(n, r) = C(n – 1, r) + C(n – 1, r – 1), 1 ≤ r ≤ n – 1.
Triângulo de Pascal:
C(4,4)C(4,3)C(4,2)C(4,1)C(4,0)4
C(3,3)C(3,2)C(3,1)C(3,0)3
C(2,2)C(2,1)C(2,0)2
C(1,1)C(1,0)1
C(0,0)0
Preenche-se completamente a partir da fórmula de Pascal e de 
C(n, 0) = C(n, n) = 1
146414
13313
1212
111
10
6
A soma dos elementos da linha n vale 2n.
Os elementos da linha n são os coeficientes de (1 + x)n:
(1 + x)0 = 1
(1 + x)1 = 1 + x
(1 + x)2 = 1 + 2x + x2
(1 + x)3 = 1 + 3x + 3x2 + x3
...
Binómio de Newton:
( ) ( )
( ) ( ) rn
0r
r-nn
n
0r
rn
yxrn,Cyx
xrn,Cx1
∑
∑
=
=
=+
=+
7
A primeira expressão demonstra-se por indução e a segunda 
resulta facilmente da primeira.
Fazendo na primeira expressão x = 1, obtem-se
( ) nn
0r
2rn,C =∑
=
A soma dos elementos da linha n do triangulo de Pascal vale 2n.
Teorema binomial de Newton:
( ) ( )
( ) ( )( ) ( )
r!
1rα...2α1ααrα,C
1x/y,yxrα,Cyx r-α
0r
rα
+−−−=
<=+ ∑∞
=
Para α inteiro positivo, esta expressão reduz-se à do binómio de 
Newton, uma vez que C(n, r) = 0 para r > n.
8
O teorema binomial de Newton pode ser usado para a 
determinação de raízes quadradas com precisão arbitrariamente 
escolhida. Tomando α = 1/2, pode obter-se facilmente
( ) 1|z| ...,z4,2C
3.2
1C(2,1)z
2.2
1z
2
11z1 35
2
3 <−+−+=+
Se, por exemplo, se pretender calcular , aplicando este 
desenvolvimento, tem-se
4.472...20
...0.25
16
10.25
8
10.25
2
11420
0.251441620
32
≈
⎥⎦
⎤⎢⎣
⎡ −+−+=
+=+=
20
9
Problema:
Com as letras da palavra CONSENSOS, quantas permutações 
diferentes é possível construir:
( ) 15120
1!2!2!3!1!
9!19;1,2,2,3,P ==
Permutações generalizadas:
Caso de n objectos pertencentes a k grupos diferentes, sendo que
•Em cada grupo todos os objectos são idênticos,
•Objectos de grupos distintos são diferentes.
( )
!!...nn!n
n!n,...,n,nn;P
k21
k21 =
10
Combinações generalizadas:
Considere-se agora uma colecção de n objectos (não 
necessariamente distintos) pertencentes a k grupos (cada um
dos quais é constituído por objectos idênticos).
Cada um dos modos diferentes de colocar os n objectos nos n 
lugares disponíveis é designado por combinação generalizada de n 
objectos repartidos por k grupos de objectos idênticos, e vale
C(n; n1,n2,...,nk) = P(n; n1,n2,...,nk).
Teorema multinomial:
( ) ( ) k
k21
21 n
k
nn...nn
n
2
n
1k21
n
k21 ...xxxn,...,n,nn;Cx...xx ∑
=+++
=+++
Problema:
No desenvolvimento do multinómio (x1 + x2 + x3 + x4 + x5)7, qual é o 
coeficiente do termo x12x3x43x5? Resposta: 420.
11
Princípio da gaiola do pombo (pigeonhole):
Se temos n + 1 pombos e n gaiolas, então há pelo menos uma 
gaiola com dois ou mais pombos.
Parece óbvio, mas é muito útil. A dificuldade reside muitas vezes 
em saber onde estão os pombos e as gaiolas:
Mostrar que dados 12 números no intervalo [0, 1], haverá pelo 
menos dois deles cuja diferença é inferior a 0.1.
Pombos: os 12 números;
Gaiolas: [0, 0.1[, [0.1, 0.2[, ..., [0.8, 0.9[, [0.9, 1[, {1}.
Num grupo de duas ou mais pessoas, há pelo menos duas com o 
mesmo número de amigos no grupo.
Pombos: as n pessoas
Gaiolas: o número de amigos que cada pessoa tem (0, 1, ..., n – 1).
Notar que as gaiolas 0 e n – 1 não podem ter pombos simultâneamente. Porquê?
12
Generalização do princípio da gaiola do pombo:
Se temos N pombos e k gaiolas, então há pelo menos uma gaiola 
com pelo menos pombos.⎡ ⎤N/k
Suponhamos que em Portugal há 10 milhões de habitantes e que 
ninguém tem mais de 500000 cabelos na sua cabeça. Indique um 
número mínimo garantido de portugueses com exactamente o 
mesmo número de cabelos. R: 20
Para pensar:
Mostre que se S ⊆ {1,2,3,…,50} ∧ |S| > 9 então há pelo menos 2 
subconjuntos de S com 5 elementos com a mesma soma.
Quantas somas diferentes pode haver? De 1+2+3+4+5 até
46+47+48+49+50, ou seja de 15 a 240, 226 no total. (as gaiolas)
E quantos subconjuntos? C(10,5) = 10x9x8x7x6/5x4x3x2=252. (os
pombos)