Combinatória de Contagem

Prévia do material em texto

Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Combinato´ria Ba´sica de Contagem
Renata de Freitas Petrucio Viana
IM-UFF
Matema´tica Discreta
Novembro de 2010
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Pascal
Blaise Pascal
(1623 - 1662)
• Matema´tico franceˆs.
• Da´ nome ao
triaˆngulo de Pascal.
• Inventou a ma´quina de
calcular.
pascaline
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
A aula de hoje e´ sobre Combinato´ria de Contagem.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Pre´-requisitos
Na˜o assumimos pre´-requisitos matema´ticos, mas consideramos
que:
– Todos ja´ tentaram resolver exerc´ıcios que envolviam
contagem;
– Todos ja´ ouviram falar em permutac¸o˜es e combinac¸o˜es;
– Todos sabem calcular o nu´mero de permutac¸o˜es de n
objetos;
– Todos sabem calcular o nu´mero de combinac¸o˜es de n
objetos tomados k a k .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Pre´-requisitos
Na˜o assumimos pre´-requisitos matema´ticos, mas consideramos
que:
– Todos ja´ tentaram resolver exerc´ıcios que envolviam
contagem;
– Todos ja´ ouviram falar em permutac¸o˜es e combinac¸o˜es;
– Todos sabem calcular o nu´mero de permutac¸o˜es de n
objetos;
– Todos sabem calcular o nu´mero de combinac¸o˜es de n
objetos tomados k a k .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Pre´-requisitos
Na˜o assumimos pre´-requisitos matema´ticos, mas consideramos
que:
– Todos ja´ tentaram resolver exerc´ıcios que envolviam
contagem;
– Todos ja´ ouviram falar em permutac¸o˜es e combinac¸o˜es;
– Todos sabem calcular o nu´mero de permutac¸o˜es de n
objetos;
– Todos sabem calcular o nu´mero de combinac¸o˜es de n
objetos tomados k a k .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Pre´-requisitos
Na˜o assumimos pre´-requisitos matema´ticos, mas consideramos
que:
– Todos ja´ tentaram resolver exerc´ıcios que envolviam
contagem;
– Todos ja´ ouviram falar em permutac¸o˜es e combinac¸o˜es;
– Todos sabem calcular o nu´mero de permutac¸o˜es de n
objetos;
– Todos sabem calcular o nu´mero de combinac¸o˜es de n
objetos tomados k a k .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Pre´-requisitos
Na˜o assumimos pre´-requisitos matema´ticos, mas consideramos
que:
– Todos ja´ tentaram resolver exerc´ıcios que envolviam
contagem;
– Todos ja´ ouviram falar em permutac¸o˜es e combinac¸o˜es;
– Todos sabem calcular o nu´mero de permutac¸o˜es de n
objetos;
– Todos sabem calcular o nu´mero de combinac¸o˜es de n
objetos tomados k a k .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
So´ para recordar, 1
O nu´mero de permutac¸o˜es de 7 elementos e´ P(7) = 7!
O nu´mero de permutac¸o˜es de n elementos e´ P(n) = n!
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
So´ para recordar, 1
O nu´mero de permutac¸o˜es de 7 elementos e´ P(7) = 7!
O nu´mero de permutac¸o˜es de n elementos e´ P(n) = n!
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
So´ para recordar, 2
O nu´mero de combinac¸o˜es de 7 elementos tomados 5 a 5 e´
C (7, 5) =
5 fatores︷ ︸︸ ︷
7× 6× 5× 4× 3
5× 4× 3× 2× 1
O nu´mero de combinac¸o˜es de n elementos tomados k a k e´
C (n, k) =
k fatores︷ ︸︸ ︷
n × (n − 1)× (n − 2)× . . .× n − (k − 1)
k × (k − 1)× (k − 2)× . . .× 1
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
So´ para recordar, 2
O nu´mero de combinac¸o˜es de 7 elementos tomados 5 a 5 e´
C (7, 5) =
5 fatores︷ ︸︸ ︷
7× 6× 5× 4× 3
5× 4× 3× 2× 1
O nu´mero de combinac¸o˜es de n elementos tomados k a k e´
C (n, k) =
k fatores︷ ︸︸ ︷
n × (n − 1)× (n − 2)× . . .× n − (k − 1)
k × (k − 1)× (k − 2)× . . .× 1
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Primeira du´vida
Se eu ja´ sei tudo isso, para que servira´ essa aula?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Objetivo principal
Nosso objetivo, ale´m de revisar esses conteu´dos, e´ implantar
em voceˆs
um certo ha´bito,
uma certa atitude,
que voceˆs devem assumir sempre que tentarem resolver um
problema de contagem.
Isso sera´ feito atrave´s da abordagem dos conteu´dos a seguir.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Objetivo principal
Nosso objetivo, ale´m de revisar esses conteu´dos, e´ implantar
em voceˆs
um certo ha´bito,
uma certa atitude,
que voceˆs devem assumir sempre que tentarem resolver um
problema de contagem.
Isso sera´ feito atrave´s da abordagem dos conteu´dos a seguir.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Objetivo principal
Nosso objetivo, ale´m de revisar esses conteu´dos, e´ implantar
em voceˆs
um certo ha´bito,
uma certa atitude,
que voceˆs devem assumir sempre que tentarem resolver um
problema de contagem.
Isso sera´ feito atrave´s da abordagem dos conteu´dos a seguir.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Objetivo principal
Nosso objetivo, ale´m de revisar esses conteu´dos, e´ implantar
em voceˆs
um certo ha´bito,
uma certa atitude,
que voceˆs devem assumir sempre que tentarem resolver um
problema de contagem.
Isso sera´ feito atrave´s da abordagem dos conteu´dos a seguir.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Objetivo principal
Nosso objetivo, ale´m de revisar esses conteu´dos, e´ implantar
em voceˆs
um certo ha´bito,
uma certa atitude,
que voceˆs devem assumir sempre que tentarem resolver um
problema de contagem.
Isso sera´ feito atrave´s da abordagem dos conteu´dos a seguir.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜oContagem por
deciso˜es
Objetivo principal
Nosso objetivo, ale´m de revisar esses conteu´dos, e´ implantar
em voceˆs
um certo ha´bito,
uma certa atitude,
que voceˆs devem assumir sempre que tentarem resolver um
problema de contagem.
Isso sera´ feito atrave´s da abordagem dos conteu´dos a seguir.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Suma´rio
• Problemas de contagem
• Princ´ıpio da Multiplicac¸a˜o
• Contagem por deciso˜es
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Problemas de contagem
Um problema de contagem tem, usualmente, o seguinte
formato:
1 sa˜o dados:
– um ou mais conjunto de objetos;
– uma especificac¸a˜o de como outros objetos sa˜o fomados a
partir dos objetos dados;
2 e pergunta-se:
– quantos objetos e´ poss´ıvel formar a partir dos objetos
dados, de acordo com a especificac¸a˜o dada.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Problemas de contagem
Um problema de contagem tem, usualmente, o seguinte
formato:
1 sa˜o dados:
– um ou mais conjunto de objetos;
– uma especificac¸a˜o de como outros objetos sa˜o fomados a
partir dos objetos dados;
2 e pergunta-se:
– quantos objetos e´ poss´ıvel formar a partir dos objetos
dados, de acordo com a especificac¸a˜o dada.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Problemas de contagem
Um problema de contagem tem, usualmente, o seguinte
formato:
1 sa˜o dados:
– um ou mais conjunto de objetos;
– uma especificac¸a˜o de como outros objetos sa˜o fomados a
partir dos objetos dados;
2 e pergunta-se:
– quantos objetos e´ poss´ıvel formar a partir dos objetos
dados, de acordo com a especificac¸a˜o dada.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Configurac¸o˜es
Chamamos de configurac¸a˜o o objeto que esta´ sendo contado.
Chamamos de objetos ba´sicos os objetos que sa˜o usados para
formar as configurac¸o˜es.
Os primeiros passos na soluc¸a˜o de um problema de contagem
sa˜o:
1 Determinar os objetos ba´sicos.
2 Determinar a configurac¸a˜o.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Configurac¸o˜es
Chamamos de configurac¸a˜o o objeto que esta´ sendo contado.
Chamamos de objetos ba´sicos os objetos que sa˜o usados para
formar as configurac¸o˜es.
Os primeiros passos na soluc¸a˜o de um problema de contagem
sa˜o:
1 Determinar os objetos ba´sicos.
2 Determinar a configurac¸a˜o.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Configurac¸o˜es
Chamamos de configurac¸a˜o o objeto que esta´ sendo contado.
Chamamos de objetos ba´sicos os objetos que sa˜o usados para
formar as configurac¸o˜es.
Os primeiros passos na soluc¸a˜o de um problema de contagem
sa˜o:
1 Determinar os objetos ba´sicos.
2 Determinar a configurac¸a˜o.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Configurac¸o˜es
Chamamos de configurac¸a˜o o objeto que esta´ sendo contado.
Chamamos de objetos ba´sicos os objetos que sa˜o usados para
formar as configurac¸o˜es.
Os primeiros passos na soluc¸a˜o de um problema de contagem
sa˜o:
1 Determinar os objetos ba´sicos.
2 Determinar a configurac¸a˜o.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Configurac¸o˜es
Chamamos de configurac¸a˜o o objeto que esta´ sendo contado.
Chamamos de objetos ba´sicos os objetos que sa˜o usados para
formar as configurac¸o˜es.
Os primeiros passos na soluc¸a˜o de um problema de contagem
sa˜o:
1 Determinar os objetos ba´sicos.
2 Determinar a configurac¸a˜o.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Atividade 1
Vamos analisar os problemas abaixo e determinar quais sa˜o os
objetos ba´sicos e qual e´ a configurac¸a˜o.
Observe que ainda na˜o estamos contando o nu´mero de
configurac¸o˜es!
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Exemplos de problemas de
contagem, 1
(U.F. de Vic¸osa-MG) Para controlar o estoque de um produto,
uma empresa usa etiquetas formadas por uma parte literal e
outra nume´rica, nesta ordem.
A parte literal e´ formada de treˆs letras do nosso alfabeto,
incluindo y , k , w , e a parte nume´rica e´ formada por quatro
algarismos de 0 a 9.
Sabendo-se que pode haver repetic¸a˜o das letras e dos
algarismos, [determine] a quantidade do produto que pode ser
etiquetada sem que haja coincideˆncia de etiquetas.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Exemplos de problemas de
contagem, 2
(Unifesp-SP) Em um edif´ıcio residencial de Sa˜o Paulo, os
moradores foram convocados para uma reunia˜o, com a
finalidade de escolher um s´ındico e quatro membros do
conselho fiscal, sendo proibida a acumulac¸a˜o de cargos.
A escolha devera´ ser feita entre dez moradores.
De quantas maneiras diferentes sera´ poss´ıvel fazer estas
escolhas?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Etiquetas, de Vic¸osa
(U.F. de Vic¸osa-MG) Para controlar o estoque de um produto,
uma empresa usa etiquetas formadas por uma parte literal e
outra nume´rica, nesta ordem.
A parte literal e´ formada de treˆs letras do nosso alfabeto,
incluindo y , k , w , e a parte nume´rica e´ formada por quatro
algarismos de 0 a 9.
Sabendo-se que pode haver repetic¸a˜o das letras e dos
algarismos, [determine] a quantidade do produto que pode ser
etiquetada sem que haja coincideˆncia de etiquetas.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Etiquetas, de Vic¸osa
(U.F. de Vic¸osa-MG) Para controlar o estoque de um produto,
uma empresa usa etiquetas formadas por uma parte literal e
outra nume´rica, nesta ordem.
A parte literal e´ formada de treˆs letras do nosso alfabeto,
incluindo y , k , w , e a parte nume´rica e´ formada por quatro
algarismos de 0 a 9.
Sabendo-se que pode haver repetic¸a˜o das letras e dos
algarismos, [determine] a quantidade do produto que pode ser
etiquetada sem que haja coincideˆncia de etiquetas.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Etiquetas, de Vic¸osa
(U.F. de Vic¸osa-MG) Para controlar o estoque de um produto,
uma empresa usa etiquetas formadas por uma parteliteral e
outra nume´rica, nesta ordem.
A parte literal e´ formada de treˆs letras do nosso alfabeto,
incluindo y , k , w , e a parte nume´rica e´ formada por quatro
algarismos de 0 a 9.
Sabendo-se que pode haver repetic¸a˜o das letras e dos
algarismos, [determine] a quantidade do produto que pode ser
etiquetada sem que haja coincideˆncia de etiquetas.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Etiquetas, de Vic¸osa
(U.F. de Vic¸osa-MG) Para controlar o estoque de um produto,
uma empresa usa etiquetas formadas por uma parte literal e
outra nume´rica, nesta ordem.
A parte literal e´ formada de treˆs letras do nosso alfabeto,
incluindo y , k , w , e a parte nume´rica e´ formada por quatro
algarismos de 0 a 9.
Sabendo-se que pode haver repetic¸a˜o das letras e dos
algarismos, [determine] a quantidade do produto que pode ser
etiquetada sem que haja coincideˆncia de etiquetas.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Etiquetas, de Vic¸osa
(U.F. de Vic¸osa-MG) Para controlar o estoque de um produto,
uma empresa usa etiquetas formadas por uma parte literal e
outra nume´rica, nesta ordem.
A parte literal e´ formada de treˆs letras do nosso alfabeto,
incluindo y , k , w , e a parte nume´rica e´ formada por quatro
algarismos de 0 a 9.
Sabendo-se que pode haver repetic¸a˜o das letras e dos
algarismos, [determine] a quantidade do produto que pode ser
etiquetada sem que haja coincideˆncia de etiquetas.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Etiquetas, de Vic¸osa
(U.F. de Vic¸osa-MG) Para controlar o estoque de um produto,
uma empresa usa etiquetas formadas por uma parte literal e
outra nume´rica, nesta ordem.
A parte literal e´ formada de treˆs letras do nosso alfabeto,
incluindo y , k , w , e a parte nume´rica e´ formada por quatro
algarismos de 0 a 9.
Sabendo-se que pode haver repetic¸a˜o das letras e dos
algarismos, [determine] a quantidade do produto que pode ser
etiquetada sem que haja coincideˆncia de etiquetas.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 1
Etiquetas, de Vic¸osa
I.(a) Os objetos ba´sicos para a formac¸a˜o da configurac¸a˜o sa˜o
letras e algarismos.
Observe que dispomos de 26 letras e 10 algarismos.
I.(b) A configurac¸a˜o e´ etiqueta formada por treˆs letras e quatro
algarismos:
(l1, l2, l3, a1, a2, a3, a4)
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 1
Etiquetas, de Vic¸osa
I.(a) Os objetos ba´sicos para a formac¸a˜o da configurac¸a˜o sa˜o
letras e algarismos.
Observe que dispomos de 26 letras e 10 algarismos.
I.(b) A configurac¸a˜o e´ etiqueta formada por treˆs letras e quatro
algarismos:
(l1, l2, l3, a1, a2, a3, a4)
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
S´ındico e conselho fiscal, de Sa˜o
Paulo
(Unifesp-SP) Em um edif´ıcio residencial de Sa˜o Paulo, os
moradores foram convocados para uma reunia˜o, com a
finalidade de escolher um s´ındico e quatro membros do
conselho fiscal, sendo proibida a acumulac¸a˜o de cargos.
A escolha devera´ ser feita entre dez moradores.
De quantas maneiras diferentes sera´ poss´ıvel fazer estas
escolhas?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
S´ındico e conselho fiscal, de Sa˜o
Paulo
(Unifesp-SP) Em um edif´ıcio residencial de Sa˜o Paulo, os
moradores foram convocados para uma reunia˜o, com a
finalidade de escolher um s´ındico e quatro membros do
conselho fiscal, sendo proibida a acumulac¸a˜o de cargos.
A escolha devera´ ser feita entre dez moradores.
De quantas maneiras diferentes sera´ poss´ıvel fazer estas
escolhas?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
S´ındico e conselho fiscal, de Sa˜o
Paulo
(Unifesp-SP) Em um edif´ıcio residencial de Sa˜o Paulo, os
moradores foram convocados para uma reunia˜o, com a
finalidade de escolher um s´ındico e quatro membros do
conselho fiscal, sendo proibida a acumulac¸a˜o de cargos.
A escolha devera´ ser feita entre dez moradores.
De quantas maneiras diferentes sera´ poss´ıvel fazer estas
escolhas?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
S´ındico e conselho fiscal, de Sa˜o
Paulo
(Unifesp-SP) Em um edif´ıcio residencial de Sa˜o Paulo, os
moradores foram convocados para uma reunia˜o, com a
finalidade de escolher um s´ındico e quatro membros do
conselho fiscal, sendo proibida a acumulac¸a˜o de cargos.
A escolha devera´ ser feita entre dez moradores.
De quantas maneiras diferentes sera´ poss´ıvel fazer estas
escolhas?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 1
S´ındico e conselho fiscal, de Sa˜o Paulo
II.(a) Os objetos ba´sicos para a formac¸a˜o da configurac¸a˜o sa˜o
moradores.
Observe que dispomos de 10 moradores.
I.(b) A configurac¸a˜o e´ o grupo um s´ındico e quatro membros
do conselho fiscal:
(s,
m3
m1
m4
m2
)
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 1
S´ındico e conselho fiscal, de Sa˜o Paulo
II.(a) Os objetos ba´sicos para a formac¸a˜o da configurac¸a˜o sa˜o
moradores.
Observe que dispomos de 10 moradores.
I.(b) A configurac¸a˜o e´ o grupo um s´ındico e quatro membros
do conselho fiscal:
(s,
m3
m1
m4
m2
)
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
O ha´bito da contagem
Para resolver um problema de contagem, devemos efetuar 4
passos:
1 Determinar quais sa˜o os objetos ba´sicos que sa˜o usados na
formac¸a˜o das configurac¸o˜es.
2 Determinar a configurac¸a˜o em questa˜o.
3 Determinar e especificar exatamente como cada
configurac¸a˜o e´ formada a partir dos objetos ba´sicos.
4 Usar a especificac¸a˜o obtida para contar o nu´mero de
configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
O ha´bito da contagem
Para resolver um problema de contagem, devemos efetuar 4
passos:
1 Determinar quais sa˜o os objetos ba´sicos que sa˜o usados na
formac¸a˜o das configurac¸o˜es.
2 Determinar a configurac¸a˜o em questa˜o.
3 Determinar e especificar exatamente como cada
configurac¸a˜o e´ formada a partir dos objetos ba´sicos.
4 Usar a especificac¸a˜o obtida para contar o nu´mero de
configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagemPrinc´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
O ha´bito da contagem
Para resolver um problema de contagem, devemos efetuar 4
passos:
1 Determinar quais sa˜o os objetos ba´sicos que sa˜o usados na
formac¸a˜o das configurac¸o˜es.
2 Determinar a configurac¸a˜o em questa˜o.
3 Determinar e especificar exatamente como cada
configurac¸a˜o e´ formada a partir dos objetos ba´sicos.
4 Usar a especificac¸a˜o obtida para contar o nu´mero de
configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
O ha´bito da contagem
Para resolver um problema de contagem, devemos efetuar 4
passos:
1 Determinar quais sa˜o os objetos ba´sicos que sa˜o usados na
formac¸a˜o das configurac¸o˜es.
2 Determinar a configurac¸a˜o em questa˜o.
3 Determinar e especificar exatamente como cada
configurac¸a˜o e´ formada a partir dos objetos ba´sicos.
4 Usar a especificac¸a˜o obtida para contar o nu´mero de
configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
O ha´bito da contagem
Para resolver um problema de contagem, devemos efetuar 4
passos:
1 Determinar quais sa˜o os objetos ba´sicos que sa˜o usados na
formac¸a˜o das configurac¸o˜es.
2 Determinar a configurac¸a˜o em questa˜o.
3 Determinar e especificar exatamente como cada
configurac¸a˜o e´ formada a partir dos objetos ba´sicos.
4 Usar a especificac¸a˜o obtida para contar o nu´mero de
configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Aplicando o PM
O Princ´ıpio da Multiplicac¸a˜o (PM) e´ um me´todo de contagem
que pode ser aplicado na determinac¸a˜o da maneira como as
configurac¸o˜es sa˜o formadas
e nos ajuda a conta´-las.
1 Queremos determinar o nu´mero de configurac¸o˜es.
2 Observamos que as configurac¸o˜es sa˜o formadas se
tomamos k deciso˜es d1, d2, . . . , dk .
3 Determinamos que d1 pode ser tomada de n1 maneiras,
que d2 pode ser tomada de n2 maneiras, . . . , que dk pode
ser tomada de nk maneiras.
4 Aplicamos o PM e conclu´ımos que o nu´mero de
configurac¸o˜es e´ o produto n1 × n2 × . . .× nk .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Aplicando o PM
O Princ´ıpio da Multiplicac¸a˜o (PM) e´ um me´todo de contagem
que pode ser aplicado na determinac¸a˜o da maneira como as
configurac¸o˜es sa˜o formadas
e nos ajuda a conta´-las.
1 Queremos determinar o nu´mero de configurac¸o˜es.
2 Observamos que as configurac¸o˜es sa˜o formadas se
tomamos k deciso˜es d1, d2, . . . , dk .
3 Determinamos que d1 pode ser tomada de n1 maneiras,
que d2 pode ser tomada de n2 maneiras, . . . , que dk pode
ser tomada de nk maneiras.
4 Aplicamos o PM e conclu´ımos que o nu´mero de
configurac¸o˜es e´ o produto n1 × n2 × . . .× nk .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Aplicando o PM
O Princ´ıpio da Multiplicac¸a˜o (PM) e´ um me´todo de contagem
que pode ser aplicado na determinac¸a˜o da maneira como as
configurac¸o˜es sa˜o formadas
e nos ajuda a conta´-las.
1 Queremos determinar o nu´mero de configurac¸o˜es.
2 Observamos que as configurac¸o˜es sa˜o formadas se
tomamos k deciso˜es d1, d2, . . . , dk .
3 Determinamos que d1 pode ser tomada de n1 maneiras,
que d2 pode ser tomada de n2 maneiras, . . . , que dk pode
ser tomada de nk maneiras.
4 Aplicamos o PM e conclu´ımos que o nu´mero de
configurac¸o˜es e´ o produto n1 × n2 × . . .× nk .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Aplicando o PM
O Princ´ıpio da Multiplicac¸a˜o (PM) e´ um me´todo de contagem
que pode ser aplicado na determinac¸a˜o da maneira como as
configurac¸o˜es sa˜o formadas
e nos ajuda a conta´-las.
1 Queremos determinar o nu´mero de configurac¸o˜es.
2 Observamos que as configurac¸o˜es sa˜o formadas se
tomamos k deciso˜es d1, d2, . . . , dk .
3 Determinamos que d1 pode ser tomada de n1 maneiras,
que d2 pode ser tomada de n2 maneiras, . . . , que dk pode
ser tomada de nk maneiras.
4 Aplicamos o PM e conclu´ımos que o nu´mero de
configurac¸o˜es e´ o produto n1 × n2 × . . .× nk .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Aplicando o PM
O Princ´ıpio da Multiplicac¸a˜o (PM) e´ um me´todo de contagem
que pode ser aplicado na determinac¸a˜o da maneira como as
configurac¸o˜es sa˜o formadas
e nos ajuda a conta´-las.
1 Queremos determinar o nu´mero de configurac¸o˜es.
2 Observamos que as configurac¸o˜es sa˜o formadas se
tomamos k deciso˜es d1, d2, . . . , dk .
3 Determinamos que d1 pode ser tomada de n1 maneiras,
que d2 pode ser tomada de n2 maneiras, . . . , que dk pode
ser tomada de nk maneiras.
4 Aplicamos o PM e conclu´ımos que o nu´mero de
configurac¸o˜es e´ o produto n1 × n2 × . . .× nk .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Aplicando o PM
O Princ´ıpio da Multiplicac¸a˜o (PM) e´ um me´todo de contagem
que pode ser aplicado na determinac¸a˜o da maneira como as
configurac¸o˜es sa˜o formadas
e nos ajuda a conta´-las.
1 Queremos determinar o nu´mero de configurac¸o˜es.
2 Observamos que as configurac¸o˜es sa˜o formadas se
tomamos k deciso˜es d1, d2, . . . , dk .
3 Determinamos que d1 pode ser tomada de n1 maneiras,
que d2 pode ser tomada de n2 maneiras, . . . , que dk pode
ser tomada de nk maneiras.
4 Aplicamos o PM e conclu´ımos que o nu´mero de
configurac¸o˜es e´ o produto n1 × n2 × . . .× nk .
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Atividade 2
Vamos, agora, contar o nu´mero de Etiquetas de Vic¸osa e de
Conselhos Fiscais de Sa˜o Paulo.
Observe que so´ podemos aplicar o PM apo´s ter apresentado
uma lista de deciso˜es que descreve a formac¸a˜o da configurac¸a˜o
a partir dos objetos ba´sicos.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´riaBa´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(a) Para formar uma etiqueta podemos tomar as seguintes
deciso˜es:
d1 : escolher uma letra para ser l1;
d2 : escolher uma letra para ser l2;
d3 : escolher uma letra para ser l3;
d4 : escolher um algarismo para ser a1;
d5 : escolher um algarismo para ser a2;
d6 : escolher um algarismo para ser a3;
d7 : escolher um algarismo para ser a4.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26×26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
Etiquetas, de Vic¸osa
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 26 maneiras;
d2 : 26 maneiras;
d3 : 26 maneiras;
d4 : 10 maneiras;
d5 : 10 maneiras;
d6 : 10 maneiras;
d7 : 10 maneiras.
Assim, pelo PM, podemos formar
26× 26× 26× 10× 10× 10× 10 etiquetas, de Vic¸osa.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(a) Para formar um grupo s´ındico e conselho fiscal podemos
tomar as seguintes deciso˜es:
d1 : escolher um morador para ser o s´ındico;
d2 : escolher um grupo de 4 moradores ainda na˜o escolhidos
para formar o conselho fiscal.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(a) Para formar um grupo s´ındico e conselho fiscal podemos
tomar as seguintes deciso˜es:
d1 : escolher um morador para ser o s´ındico;
d2 : escolher um grupo de 4 moradores ainda na˜o escolhidos
para formar o conselho fiscal.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(a) Para formar um grupo s´ındico e conselho fiscal podemos
tomar as seguintes deciso˜es:
d1 : escolher um morador para ser o s´ındico;
d2 : escolher um grupo de 4 moradores ainda na˜o escolhidos
para formar o conselho fiscal.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(a) Para formar um grupo s´ındico e conselho fiscal podemos
tomar as seguintes deciso˜es:
d1 : escolher um morador para ser o s´ındico;
d2 : escolher um grupo de 4 moradores ainda na˜o escolhidos
para formar o conselho fiscal.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(a) Para formar um grupo s´ındico e conselho fiscal podemos
tomar as seguintes deciso˜es:
d1 : escolher um morador para ser o s´ındico;
d2 : escolher um grupo de 4 moradores ainda na˜o escolhidos
para formar o conselho fiscal.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(a) Para formar um grupo s´ındico e conselho fiscal podemos
tomar as seguintes deciso˜es:
d1 : escolher um morador para ser o s´ındico;
d2 : escolher um grupo de 4 moradores ainda na˜o escolhidos
para formar o conselho fiscal.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 10 maneiras;
d2 : C (9, 4) maneiras.
Assim, pelo PM, podemos formar 10× C (9, 4) grupos s´ındico e
conselho fiscal, de Sa˜o Paulo.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 10 maneiras;
d2 : C (9, 4) maneiras.
Assim, pelo PM, podemos formar 10× C (9, 4) grupos s´ındico e
conselho fiscal, de Sa˜o Paulo.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 10 maneiras;
d2 : C (9, 4) maneiras.
Assim, pelo PM, podemos formar 10× C (9, 4) grupos s´ındico e
conselho fiscal, de Sa˜o Paulo.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 10 maneiras;
d2 : C (9, 4) maneiras.
Assim, pelo PM, podemos formar 10× C (9, 4) grupos s´ındico e
conselho fiscal, de Sa˜o Paulo.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 10 maneiras;
d2 : C (9, 4) maneiras.
Assim, pelo PM, podemos formar 10× C (9, 4) grupos s´ındico e
conselho fiscal, de Sa˜o Paulo.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Soluc¸a˜o da Atividade 2
S´ındico e conselho fiscal, de Sa˜o Paulo
I.(b) O nu´mero de maneiras de tomar cada decisa˜o e´ o seguinte:
d1 : 10 maneiras;
d2 : C (9, 4) maneiras.
Assim, pelo PM, podemos formar 10× C (9, 4) grupos s´ındico e
conselho fiscal, de Sa˜o Paulo.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Em resumo
Para resolver um problema de contagem, voceˆ deve:
– Identificar a configurac¸a˜o;
– Descobrir como ela e´ formada;
– Fazer uma lista de deciso˜es especificando como ela e´
formada;
– Utilizar a lista de deciso˜es, em conjunto com o PM, para
contar o nu´mero de configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Em resumo
Para resolver um problema de contagem, voceˆ deve:
– Identificar a configurac¸a˜o;
– Descobrir como ela e´ formada;
– Fazer uma lista de deciso˜es especificando como ela e´
formada;
– Utilizar a lista de deciso˜es, em conjunto com o PM, para
contar o nu´mero de configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Em resumo
Para resolver um problema de contagem, voceˆ deve:
– Identificar a configurac¸a˜o;
– Descobrir como ela e´ formada;
– Fazer uma lista de deciso˜es especificando como ela e´
formada;
– Utilizar a lista de deciso˜es, em conjunto com o PM, para
contar o nu´mero de configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Em resumo
Para resolver um problema de contagem, voceˆ deve:
– Identificar a configurac¸a˜o;
– Descobrir como ela e´ formada;
– Fazer uma lista de deciso˜es especificando como ela e´
formada;
– Utilizar a lista de deciso˜es, em conjunto com o PM, para
contar o nu´mero de configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Em resumo
Para resolver um problema de contagem, voceˆ deve:
– Identificar a configurac¸a˜o;
– Descobrir como ela e´ formada;
– Fazer uma lista de deciso˜es especificando como ela e´
formada;
– Utilizar a lista de deciso˜es, em conjunto com o PM, para
contar o nu´mero de configurac¸o˜es.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
PetrucioViana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Atividade 3
Estamos prontos para fazer a Atividade 3.
Nela, voceˆ deve aplicar a metodologia descrita a alguns
problemas de contagem.
Na˜o tenha pressa em contar. Se esforce para entender o
problema e aplicar a metodologia acima.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Atividade 3
Para cada problema a seguir:
(a) Determine os objetos ba´sicos usados na formac¸a˜o das
configurac¸o˜es.
(b) Determine a configurac¸a˜o do problema.
(c) Especifique uma lista de deciso˜es que descreve como as
configurac¸o˜es sa˜o formadas a partir dos objetos ba´sicos.
(d) Resolva o problema, usando a lista de deciso˜es, por
aplicac¸a˜o do PM.
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Problema 3
Um comiteˆ consiste de 5 mulheres, das quais uma e´ a
presidente, outra e´ a secreta´ria e uma outra e´ a tesoureira.
Quantos comiteˆs sa˜o poss´ıveis, se dispomos de 12 mulheres?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Problema 4
Quantas palavras de 7 letras podem ser formadas com as letras
A e B, de modo que cada palavra possui exatamente 3
ocorreˆncias da letra A?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Problema 5
Um sala˜o tem 10 portas, tais que cada uma delas so´ pode ficar
aberta ou fechada. Uma abertura deste sala˜o consiste em
especificar, para cada porta, se ela fica aberta ou fechada.
Quantas aberturas sa˜o poss´ıveis?
Combinato´ria
Ba´sica de
Contagem
Renata de
Freitas,
Petrucio
Viana
IM-UFF
Problemas de
contagem
Princ´ıpio da
Multiplicac¸a˜o
Contagem por
deciso˜es
Exerc´ıcios
1. Exerc´ıcios do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo,
2006).
2. Exerc´ıcios da Lista 16.
	Problemas de contagem
	Princípio da Multiplicação
	Contagem por decisões