Análise Combinatória e Princípios Matemáticos

Prévia do material em texto

*
Análise Combinatória
Slides
Xadrez - www.ser.com.br 
 Fatorial
 Permutação com repetição
 Princípio fundamental da contagem
 Permutação simples
 Arranjos simples
 Combinações simples
 Números binomiais
 Triângulo de Pascal
 Binômio de Newton
*
(n é o numerador e p é a classe do número binomial).
Números binomiais
Chama-se número binomial o número com tal que, 
Números binomiais iguais: Se, então:
*
É uma forma de dispor números binomiais. Observe a sequência:
Triângulo de Pascal
+
+
ou
onde
De modo geral:
*
Observe a soma dos elementos de uma mesma linha no triângulo de Pascal:
Triângulo de Pascal
:
*
Outras propriedades:
Triângulo de Pascal
+
+
+
+
*
Outras propriedades:
+
Triângulo de Pascal
+
+
+
*
Toda potência da forma (x+y)n, sendo n um número natural, é conhecido como binômio de Newton. Abaixo temos alguns casos comuns.
Para desenvolver estes binômios, podemos generalizar como segue:
Exemplo:
Binômio de Newton
*
Termo geral do binômio de Newton é o desenvolvimento de apenas um dos termos de todo o desenvolvimento. Assim...
Binômio de Newton
*
Chama-se fatorial de n ou n fatorial o número n!, tal que:
- Para n=0: 0!=1
- Para n=1: 1!=1
- Para n=2: 2!=21=2
- Para n=3: 3!=321=6
- Para n=4: 4!=4321=24
- Para n=5: 5!=54321=120
Generalizando:
n! = n  (n-1)  (n-2)  (n-3)  ...  2  1, sendo n pertencente ao conjunto dos números naturais {0, 1, 2, 3 ...}. 
Fatorial
*
Acompanhe o raciocínio da resolução do problema a seguir:
Uma pessoa vai a um restaurante e na promoção ela deve montar a sua refeição escolhendo uma entrada, um prato principal e uma sobremesa.
No cardápio constam 3 tipos de entradas, 5 tipos de pratos quentes e 4 tipos de sobremesa. De quantas formas diferentes essa pessoa pode montar a sua refeição? 
salada
sopa
patês
bife
massa
torta
frango
peixe
bolo
fruta
mousse
pudim
3 possibilidades 5 possibilidades 4 possibilidades
A quantidade de refeições é obtida multiplicando-se todas as possibilidades. Sendo assim: 
3  5  4 = 60 refeições
Princípio fundamental da contagem ou princípio da multiplicação
*
Permutar é o mesmo que trocar. Nos problemas de permutação simples, a ideia que fica é de trocar ou embaralhar as posições de todos os elementos.
Observe os exemplos:
Permutação simples
1) Quantos números de 3 algarismos distintos podemos formar utilizando os algarismos 3, 5 e 7? 
Note o uso da palavra “distintos”, ou 
seja, sem repetir o mesmo algarismo.
As possibilidades são:
357, 375, 537, 573, 735 e 753.
Podemos representar também em um “diagrama de árvore”:
		5		7
3		
		7		5
		3		7
5
		7		3
	
		3		5
7
		5		3
Utilizando o princípio fundamental da contagem, temos:
3  2  1 = 6 possibilidades
3 possibilidades	2 possibilidades	1 possibilidade
*
Permutação simples
2) Quantos anagramas existem da palavra azul?
Anagramas são todas as palavras formadas, com ou sem sentido, pelas letras da palavra dada, embaralhando a sua ordem.
A maneira mais fácil de construir todas as possibilidades é pelo “diagrama de árvores”. Observe:
				u		l
		z		l		u
				z		l
a		u		l		z
				z		u
		l		u		z
				u		l
		a		l		u
				a		l
z		u		l		a
				a		u
		l		u		a
				z		l
		a		l		z
				a		l
u		z		l		a
				a		z
		l		z		a
				u		z
		a		z		u
				a		u
l		z		u		a
				a		z
		u		z		a
Utilizando o princípio fundamental da contagem, temos:
4  3  2  1 = 24 possibilidades
Concluímos que para n termos a expressão ficaria:
Pn = n  (n – 1)  (n – 2)  ...  2  1 = n! 
*
Permutação com repetição
É a permutação onde aparecem elementos repetidos. Se trocarmos a ordem destes, não aparecerá mudanças na posição.
Exemplo: Os anagramas da palavra “matemática”.
Ao mudar as letras “m” com outra “m” aparentemente não houve mudança. O mesmo com as letras “a” ou “t” .
Assim, seguimos o raciocínio:
Onde Pn é a permutação das dez letras da palavra matemática,
P1 é o número de letras “m” que são repetidas, P2 é o número de letras “a” repetidas e P3 é o número de letras “t” repetidas.
Generalizando: 
*
Ocorre quando de n elementos desejamos pegar p, no qual a ordem destes importa. Assim temos a relação:
Exemplo: Com as letras da palavra “república”, quantas palavras, com ou sem sentido, podemos formar utilizando 5 destas letras? 
Arranjo simples
1º modo de resolver:
2º modo de resolver:
*
Ocorre quando de n elementos desejamos pegar p, no qual a ordem destes não importa. Assim temos a relação:
Exemplo: Em uma empresa com nove funcionários, cinco serão chamados para uma reunião. De quantas formas diferentes poderá ser formado o grupo para a reunião? 
Combinações simples
 Exerciciozinho...
	Em um país existem 8 deputados e 5 senadores de um partido político. Este partido precisa escolher uma equipe com 3 pessoas dentre os senadores e deputados deste partido político para representar o partido em um viagem internacional. O número de maneiras de se formar essa equipe de modo que a mesma não tenha mais do que dois senadores é igual a:
*
*
n
p
æö
ç÷
èø
np
³
n
n!
pp!(np)!
æö
=
ç÷
-
èø
99
5x
æöæö
=
ç÷ç÷
èøèø
x5
ou
x59x4
=
ì
ï
í
ï
+=Þ=
î
0
0
11
01
222
012
3333
0123
44444
01234
 ... ... ... ... ... ...
nnnnn
 ... 
0123n
æö
ç÷
èø
æöæö
ç÷ç÷
èøèø
æöæöæö
ç÷ç÷ç÷
èøèøèø
æöæöæöæö
ç÷ç÷ç÷ç÷
èøèøèøèø
æöæöæöæöæö
ç÷ç÷ç÷ç÷ç÷
èøèøèøèøèø
æöæöæöæöæ
ç÷ç÷ç÷ç÷
èøèøèøèøè
ö
ç÷
ø
1
11
121
1331
14641
15101051
1615201561
1
11
121
1331
14641
15101051
1615201561
n1n1n
p1pp
--
æöæöæö
+=
ç÷ç÷ç÷
-
èøèøèø
0
1
2
3
4
0
12
0
11
1122
01
222
12142
012
3333
133182
0123
44444
14641162
01234
De modo geral, t
æö
==
ç÷
èø
æöæö
+=+==
ç÷ç÷
èøèø
æöæöæö
++=++==
ç÷ç÷ç÷
èøèøèø
æöæöæöæö
+++=+++==
ç÷ç÷ç÷ç÷
èøèøèøèø
æöæöæöæöæö
++++=++++==
ç÷ç÷ç÷ç÷ç÷
èøèøèøèøèø
pn
n
p0
emos
nnnnnn
 ... 2
p0123n
=
=
æöæöæöæöæöæö
=+++++=
ç÷ç÷ç÷ç÷ç÷ç÷
èøèøèøèøèøèø
å
pp1p2nn1
ppppp1
+++
æöæöæöæöæö
++++=
ç÷ç÷ç÷ç÷ç÷
+
èøèøèøèøèø
K
0
0
11
01
222
012
3333
0123
44444
01234
 ... ... ... ... ... ...
nnnnn
 ... 
0123n
æö
ç÷
èø
æöæö
ç÷ç÷
èøèø
æöæöæö
ç÷ç÷ç÷
èøèøèø
æöæöæöæö
ç÷ç÷ç÷ç÷
èøèøèøèø
æöæöæöæöæö
ç÷ç÷ç÷ç÷ç÷
èøèøèøèøèø
æöæöæöæöæ
ç÷ç÷ç÷ç÷
èøèøèøèøè
ö
ç÷
ø
1
11
121
1331
14641
15101051
1615201561
nn1n2npnp1
012pp
+++++
æöæöæöæöæö
++++=
ç÷ç÷ç÷ç÷ç÷
èøèøèøèøèø
K
0
0
11
01
222
012
3333
0123
44444
01234
 ... ... ... ... ... ...
nnnnn
 ... 
0123n
æö
ç÷
èø
æöæö
ç÷ç÷
èøèø
æöæöæö
ç÷ç÷ç÷
èøèøèø
æöæöæöæö
ç÷ç÷ç÷ç÷
èøèøèøèø
æöæöæöæöæö
ç÷ç÷ç÷ç÷ç÷
èøèøèøèøèø
æöæöæöæöæ
ç÷ç÷ç÷ç÷
èøèøèøèøè
ö
ç÷
ø
1
11
121
1331
14641
15101051
1615201561
(
)
(
)
(
)
(
)
0
1
2
22
3
3223
4432234
xy1
xyxy
xyx2xyy
xyx3xy3xyy
(xy)x4xy6xy4xyy
+=
+=+
+=++
+=+++
+=++++
(
)
00112222110
01221
n
nnnnnn
nnnnnn
xyxyxyxyxyxyxy
nnn
-----
æöæöæöæöæöæö
+=++++++
ç÷ç÷ç÷ç÷ç÷ç÷
--
èøèøèøèøèøèø
K
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
012345
543210
25222222
255423426810
555555
(2x3y)2x3y2x3y2x3y2x3y2x3y2x3y
012345
(2x3y)32x240xy720xy1080xy810xy243y
æöæöæöæöæöæö
+=+++++
ç÷ç÷ç÷ç÷ç÷ç÷
èøèøèøèøèøèø
+=+++++
n
npp
p1
...para (xy), o desenvolvimento de apena
s um dos 
termos pode ser feito pelo termo geral a
 seguir...
n
T=xy 
p
-
+
+
æö
ç÷
èø
n
123
P
10!109876543!
151200
PPP2!3!2!23!2
×××××××
===
××××××
,,
n
n!
P
!!!
abg
=
abg
n,p
n!
A
(np)!
=
-
a
9876
a 1 casacomo foi usado um dois termos fo
ram usado
pode ter termo na primeiraforam usados,
nove termoscasa, sobraram oito restando 
sete 
para escolher na para escolher
segunda casaum para esta casa
×××
5
15120
squatro termos 
3 termos dos usados. Restaramnove, restando cinco nesta casa
seis para esta para selecionar
casa
×=
9,5
9!987654!
A15120
(95)!4!
×××××
===
-
n,p
n
n!
C
pp!(np)!
æö
==
ç÷
-
èø
9,5
9
9!98765!9876
C126
55!(95)!5!4!4321
æö
×××××××
=====
ç÷
-×××
èø