Combinatória
Márcio Antônio de Andrade Bortoloti
Departamento de Ciências Exatas e Tecnológicas - DCET
Universidade Estadual do Sudoeste da Bahia - UESB
Curso de Matemática - Programa Especial de Formação de Professores
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
1 / 18
Introdução
Princı́pios Básicos de Contagem
Princı́pio da Adição
Princı́pio da Multiplicação
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
2 / 18
Introdução
Princı́pio da Adição
Se A e B são dois conjuntos disjuntos, com p e q elementos,
respectivamente, então A ∪ B possui p + q elementos.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
3 / 18
Introdução
Princı́pio da Adição
Se A e B são dois conjuntos disjuntos, com p e q elementos,
respectivamente, então A ∪ B possui p + q elementos.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
3 / 18
Introdução
Problema
Numa sala há três homens e quatro mulheres. De quantos modos é
possı́vel selecionar um casal homem-mulher ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
4 / 18
Introdução
Problema
Numa sala há três homens e quatro mulheres. De quantos modos é
possı́vel selecionar um casal homem-mulher ?
Homens: h1 , h2 , h3
Mulheres: m1 , m2 , m3 , m4
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
4 / 18
Introdução
Problema
Numa sala há três homens e quatro mulheres. De quantos modos é
possı́vel selecionar um casal homem-mulher ?
Homens: h1 , h2 , h3
Mulheres: m1 , m2 , m3 , m4
Quatro casais com h1 =⇒ {(h1 , m1 ), (h1 , m2 ), (h1 , m3 ), (h1 , m4 )}
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
4 / 18
Introdução
Problema
Numa sala há três homens e quatro mulheres. De quantos modos é
possı́vel selecionar um casal homem-mulher ?
Homens: h1 , h2 , h3
Mulheres: m1 , m2 , m3 , m4
Quatro casais com h1 =⇒ {(h1 , m1 ), (h1 , m2 ), (h1 , m3 ), (h1 , m4 )}
Quatro casais com h2 =⇒ {(h2 , m1 ), (h2 , m2 ), (h2 , m3 ), (h2 , m4 )}
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
4 / 18
Introdução
Problema
Numa sala há três homens e quatro mulheres. De quantos modos é
possı́vel selecionar um casal homem-mulher ?
Homens: h1 , h2 , h3
Mulheres: m1 , m2 , m3 , m4
Quatro casais com h1 =⇒ {(h1 , m1 ), (h1 , m2 ), (h1 , m3 ), (h1 , m4 )}
Quatro casais com h2 =⇒ {(h2 , m1 ), (h2 , m2 ), (h2 , m3 ), (h2 , m4 )}
Quatro casais com h3 =⇒ {(h3 , m1 ), (h3 , m2 ), (h3 , m3 ), (h3 , m4 )}
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
4 / 18
Introdução
Problema
Numa sala há três homens e quatro mulheres. De quantos modos é
possı́vel selecionar um casal homem-mulher ?
Homens: h1 , h2 , h3
Mulheres: m1 , m2 , m3 , m4
Quatro casais com h1 =⇒ {(h1 , m1 ), (h1 , m2 ), (h1 , m3 ), (h1 , m4 )}
Quatro casais com h2 =⇒ {(h2 , m1 ), (h2 , m2 ), (h2 , m3 ), (h2 , m4 )}
Quatro casais com h3 =⇒ {(h3 , m1 ), (h3 , m2 ), (h3 , m3 ), (h3 , m4 )}
O número de casais é portanto 4 + 4 + 4 = 3 × 4 = 12
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
4 / 18
Introdução
Princı́pio da Multiplicação
Se uma decisão d1 pode ser tomada de x maneiras diferentes e se, uma
decisão d2 puder ser tomada de y maneiras então o número de maneiras
de se tomarem as decisões d1 e d2 é xy.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
5 / 18
Introdução
Princı́pio da Multiplicação
Se uma decisão d1 pode ser tomada de x maneiras diferentes e se, uma
decisão d2 puder ser tomada de y maneiras então o número de maneiras
de se tomarem as decisões d1 e d2 é xy.
No problema anterior, para formar um casal devemos tomar as decisões:
d1 : escolha do homem;
d2 : escolha da mulher.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
5 / 18
Introdução
Princı́pio da Multiplicação
Se uma decisão d1 pode ser tomada de x maneiras diferentes e se, uma
decisão d2 puder ser tomada de y maneiras então o número de maneiras
de se tomarem as decisões d1 e d2 é xy.
No problema anterior, para formar um casal devemos tomar as decisões:
d1 : escolha do homem;
d2 : escolha da mulher.
d1 pode ser tomada de três maneiras diferentes
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
5 / 18
Introdução
Princı́pio da Multiplicação
Se uma decisão d1 pode ser tomada de x maneiras diferentes e se, uma
decisão d2 puder ser tomada de y maneiras então o número de maneiras
de se tomarem as decisões d1 e d2 é xy.
No problema anterior, para formar um casal devemos tomar as decisões:
d1 : escolha do homem;
d2 : escolha da mulher.
d1 pode ser tomada de três maneiras diferentes
d2 pode ser tomada de quatro maneiras diferentes.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
5 / 18
Introdução
Princı́pio da Multiplicação
Se uma decisão d1 pode ser tomada de x maneiras diferentes e se, uma
decisão d2 puder ser tomada de y maneiras então o número de maneiras
de se tomarem as decisões d1 e d2 é xy.
No problema anterior, para formar um casal devemos tomar as decisões:
d1 : escolha do homem;
d2 : escolha da mulher.
d1 pode ser tomada de três maneiras diferentes
d2 pode ser tomada de quatro maneiras diferentes.
O número de maneiras de se formar um casal é 3 × 4 = 12.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
5 / 18
Introdução
Exemplo:
Para fazer uma viagem Rio-Recife-Rio, posso usar como transporte o
ônibus, o navio e o avião. De quantos modos posso escolher os transportes
se não desejo usar na volta o mesmo meio de transporte usado na ida?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
6 / 18
Introdução
Exemplo:
Para fazer uma viagem Rio-Recife-Rio, posso usar como transporte o
ônibus, o navio e o avião. De quantos modos posso escolher os transportes
se não desejo usar na volta o mesmo meio de transporte usado na ida?
Exemplo:
Uma bandeira é formada por quatro listras, que devem
ser coloridas usando-se apenas as cores amarelo, branco
e cinza, não devendo listras adjacentes ter a mesma
cor. De quantos modos pode ser colorida a bandeira?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
6 / 18
Introdução
Exemplo:
Quantos números naturais de três algarismos distintos (na base 10)
existem?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
7 / 18
Introdução
Exemplo:
Quantos números naturais de três algarismos distintos (na base 10)
existem?
Solução:
O primeiro algarismo pode ser escolhido de 9 modos diferentes (não
podemos usar o zero!).
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
7 / 18
Introdução
Exemplo:
Quantos números naturais de três algarismos distintos (na base 10)
existem?
Solução:
O primeiro algarismo pode ser escolhido de 9 modos diferentes (não
podemos usar o zero!). O segundo algarismo pode ser escolhido de 9
modos diferentes (não podemos usar o anterior!).
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
7 / 18
Introdução
Exemplo:
Quantos números naturais de três algarismos distintos (na base 10)
existem?
Solução:
O primeiro algarismo pode ser escolhido de 9 modos diferentes (não
podemos usar o zero!). O segundo algarismo pode ser escolhido de 9
modos diferentes (não podemos usar o anterior!). O terceiro de 8 modos
diferentes (não podemos usar os dois algarismos já empregados
anteriormente).
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
7 / 18
Introdução
Exemplo:
Quantos números naturais de três algarismos distintos (na base 10)
existem?
Solução:
O primeiro algarismo pode ser escolhido de 9 modos diferentes (não
podemos usar o zero!). O segundo algarismo pode ser escolhido de 9
modos diferentes (não podemos usar o anterior!). O terceiro de 8 modos
diferentes (não podemos usar os dois algarismos já empregados
anteriormente). Assim, a resposta é 9 × 9 × 8 = 648.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
7 / 18
Introdução
E se começássemos pelo terceiro algarismo?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
8 / 18
Introdução
E se começássemos pelo terceiro algarismo?
Terceiro Algarismo: Terı́amos 10 possibilidades de escolha
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
8 / 18
Introdução
E se começássemos pelo terceiro algarismo?
Terceiro Algarismo: Terı́amos 10 possibilidades de escolha
Segundo Algarismo: Terı́amos 9 possibilidades de escolha
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
8 / 18
Introdução
E se começássemos pelo terceiro algarismo?
Terceiro Algarismo: Terı́amos 10 possibilidades de escolha
Segundo Algarismo: Terı́amos 9 possibilidades de escolha
Primeiro Algarismo: Depende ...
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
8 / 18
Introdução
E se começássemos pelo terceiro algarismo?
Terceiro Algarismo: Terı́amos 10 possibilidades de escolha
Segundo Algarismo: Terı́amos 9 possibilidades de escolha
Primeiro Algarismo: Depende ...
Se o zero não foi escolhido
então terı́amos 8 possibilidades.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
8 / 18
Introdução
E se começássemos pelo terceiro algarismo?
Terceiro Algarismo: Terı́amos 10 possibilidades de escolha
Segundo Algarismo: Terı́amos 9 possibilidades de escolha
Primeiro Algarismo: Depende ...
Se o zero não foi escolhido
então terı́amos 8 possibilidades.
Se o zero tiver sido escolhido
então terı́amos 7 possibilidades.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
8 / 18
Introdução
E se começássemos pelo terceiro algarismo?
Terceiro Algarismo: Terı́amos 10 possibilidades de escolha
Segundo Algarismo: Terı́amos 9 possibilidades de escolha
Primeiro Algarismo: Depende ...
Se o zero não foi escolhido
então terı́amos 8 possibilidades.
Se o zero tiver sido escolhido
então terı́amos 7 possibilidades.
Como evitar essa dificuldade?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
8 / 18
Introdução
E se começássemos pelo terceiro algarismo?
Terceiro Algarismo: Terı́amos 10 possibilidades de escolha
Segundo Algarismo: Terı́amos 9 possibilidades de escolha
Primeiro Algarismo: Depende ...
Se o zero não foi escolhido
então terı́amos 8 possibilidades.
Se o zero tiver sido escolhido
então terı́amos 7 possibilidades.
Como evitar essa dificuldade?
Recomendação
“Pequenas dificuldades adiadas costumam transformar-se em
grandes dificuldades. Se alguma decisão for mais complicada
que as demais, ela deve ser tomada em primeiro lugar.”
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
8 / 18
Exercı́cios
1
Quantas palavras contendo 3 letras diferentes podem ser formadas com um
alfabeto de 26 letras?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
9 / 18
Exercı́cios
1
Quantas palavras contendo 3 letras diferentes podem ser formadas com um
alfabeto de 26 letras?
2
Um homem vai a um restaurante disposto a comer um só prato de carne e
uma só sobremesa. O cardápio oferece oito pratos distintos de carne e cinco
pratos diferentes de sobremesa. De quantas formas pode o homem fazer sua
refeição?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
9 / 18
Exercı́cios
1
Quantas palavras contendo 3 letras diferentes podem ser formadas com um
alfabeto de 26 letras?
2
Um homem vai a um restaurante disposto a comer um só prato de carne e
uma só sobremesa. O cardápio oferece oito pratos distintos de carne e cinco
pratos diferentes de sobremesa. De quantas formas pode o homem fazer sua
refeição?
3
Uma sala tem 10 portas. De quantas maneiras diferentes essa sala pode ser
aberta?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
9 / 18
Exercı́cios
1
Quantas palavras contendo 3 letras diferentes podem ser formadas com um
alfabeto de 26 letras?
2
Um homem vai a um restaurante disposto a comer um só prato de carne e
uma só sobremesa. O cardápio oferece oito pratos distintos de carne e cinco
pratos diferentes de sobremesa. De quantas formas pode o homem fazer sua
refeição?
3
Uma sala tem 10 portas. De quantas maneiras diferentes essa sala pode ser
aberta?
4
Seis dados são lançados simultaneamente. Quantas sequeências de
resultados são possı́veis’ se considerarmos cada elemento da sequência como
o número obtido em cada dado?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
9 / 18
Exercı́cios
1
Quantas palavras contendo 3 letras diferentes podem ser formadas com um
alfabeto de 26 letras?
2
Um homem vai a um restaurante disposto a comer um só prato de carne e
uma só sobremesa. O cardápio oferece oito pratos distintos de carne e cinco
pratos diferentes de sobremesa. De quantas formas pode o homem fazer sua
refeição?
3
Uma sala tem 10 portas. De quantas maneiras diferentes essa sala pode ser
aberta?
4
Seis dados são lançados simultaneamente. Quantas sequeências de
resultados são possı́veis’ se considerarmos cada elemento da sequência como
o número obtido em cada dado?
5
Quantos números telefônicos com 8 dı́gitos podem ser formados, se usarmos
os dı́gitos de 0 a 9?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
9 / 18
Exercı́cios
1
Quantas palavras contendo 3 letras diferentes podem ser formadas com um
alfabeto de 26 letras?
2
Um homem vai a um restaurante disposto a comer um só prato de carne e
uma só sobremesa. O cardápio oferece oito pratos distintos de carne e cinco
pratos diferentes de sobremesa. De quantas formas pode o homem fazer sua
refeição?
3
Uma sala tem 10 portas. De quantas maneiras diferentes essa sala pode ser
aberta?
4
Seis dados são lançados simultaneamente. Quantas sequeências de
resultados são possı́veis’ se considerarmos cada elemento da sequência como
o número obtido em cada dado?
5
Quantos números telefônicos com 8 dı́gitos podem ser formados, se usarmos
os dı́gitos de 0 a 9?
6
Quantos inteiros há entre 1000 e 9999 cujos algarismos são distitntos?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
9 / 18
Exercı́cios
1
Quantas palavras contendo 3 letras diferentes podem ser formadas com um
alfabeto de 26 letras?
2
Um homem vai a um restaurante disposto a comer um só prato de carne e
uma só sobremesa. O cardápio oferece oito pratos distintos de carne e cinco
pratos diferentes de sobremesa. De quantas formas pode o homem fazer sua
refeição?
3
Uma sala tem 10 portas. De quantas maneiras diferentes essa sala pode ser
aberta?
4
Seis dados são lançados simultaneamente. Quantas sequeências de
resultados são possı́veis’ se considerarmos cada elemento da sequência como
o número obtido em cada dado?
5
Quantos números telefônicos com 8 dı́gitos podem ser formados, se usarmos
os dı́gitos de 0 a 9?
6
Quantos inteiros há entre 1000 e 9999 cujos algarismos são distitntos?
7
O código Morse usa palavras contendo de 1 a 4 letras, as letras sendo
ponto e traço. Quantas palavras existem no código Morse?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
9 / 18
Permutação Simples
Dados n objetos distintos a1 , a2 , · · · , an , de quantos modos é
possı́vel ordená-los?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
10 / 18
Permutação Simples
Dados n objetos distintos a1 , a2 , · · · , an , de quantos modos é
possı́vel ordená-los?
Por exemplo:
Para os objetos 1,2,3 há 6 ordenações possı́veis: 123, 132,
231,213,312,321.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
10 / 18
Permutação Simples
Dados n objetos distintos a1 , a2 , · · · , an , de quantos modos é
possı́vel ordená-los?
Por exemplo:
Para os objetos 1,2,3 há 6 ordenações possı́veis: 123, 132,
231,213,312,321.
De uma forma geral temos n maneiras de escolher o objeto que ocupará o
primeiro lugar, n − 1 maneiras de escolher o objeto que ocupará o segundo
lugar e uma maneira de escolher aquele que ocupará o último lugar.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
10 / 18
Permutação Simples
Dados n objetos distintos a1 , a2 , · · · , an , de quantos modos é
possı́vel ordená-los?
Por exemplo:
Para os objetos 1,2,3 há 6 ordenações possı́veis: 123, 132,
231,213,312,321.
De uma forma geral temos n maneiras de escolher o objeto que ocupará o
primeiro lugar, n − 1 maneiras de escolher o objeto que ocupará o segundo
lugar e uma maneira de escolher aquele que ocupará o último lugar.
Assim ...
O número de modos de ordenar n objetos
distintos é
n(n − 1) · · · 1 = n! .
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
10 / 18
Permutação Simples
Exemplos:
Quantos são os anagramas da palavra PRÁTICO ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
11 / 18
Permutação Simples
Exemplos:
Quantos são os anagramas da palavra PRÁTICO ?
Quantos são os anagramas da palavra PRÁTICO que começam e
terminam com consoante?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
11 / 18
Permutação Simples
Exemplos:
Quantos são os anagramas da palavra PRÁTICO ?
Quantos são os anagramas da palavra PRÁTICO que começam e
terminam com consoante?
De quantos modos podemos formar uma roda com 5 crianças ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
11 / 18
Permutação Simples
Exemplos:
Quantos são os anagramas da palavra PRÁTICO ?
Quantos são os anagramas da palavra PRÁTICO que começam e
terminam com consoante?
De quantos modos podemos formar uma roda com 5 crianças ?
A princı́pio poderı́amos formar uma roda com 5 crianças de 5! = 120
modos.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
11 / 18
Permutação Simples
Exemplos:
Quantos são os anagramas da palavra PRÁTICO ?
Quantos são os anagramas da palavra PRÁTICO que começam e
terminam com consoante?
De quantos modos podemos formar uma roda com 5 crianças ?
A princı́pio poderı́amos formar uma roda com 5 crianças de 5! = 120
modos. Entretanto, as rodas ABCDE e EABCD são iguais.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
11 / 18
Permutação Simples
Exemplos:
Quantos são os anagramas da palavra PRÁTICO ?
Quantos são os anagramas da palavra PRÁTICO que começam e
terminam com consoante?
De quantos modos podemos formar uma roda com 5 crianças ?
A princı́pio poderı́amos formar uma roda com 5 crianças de 5! = 120
modos. Entretanto, as rodas ABCDE e EABCD são iguais.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
11 / 18
Permutação Simples
Exemplos:
Quantos são os anagramas da palavra PRÁTICO ?
Quantos são os anagramas da palavra PRÁTICO que começam e
terminam com consoante?
De quantos modos podemos formar uma roda com 5 crianças ?
A princı́pio poderı́amos formar uma roda com 5 crianças de 5! = 120
modos. Entretanto, as rodas ABCDE e EABCD são iguais.
Cada roda pode ser virada de 5 modos diferentes.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
11 / 18
Permutação Simples
Exemplos:
Quantos são os anagramas da palavra PRÁTICO ?
Quantos são os anagramas da palavra PRÁTICO que começam e
terminam com consoante?
De quantos modos podemos formar uma roda com 5 crianças ?
A princı́pio poderı́amos formar uma roda com 5 crianças de 5! = 120
modos. Entretanto, as rodas ABCDE e EABCD são iguais.
Cada roda pode ser virada de 5 modos diferentes.
Logo a resposta é 120/5.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
11 / 18
Permutação Simples
Exemplos:
De quantos modos podemos dividir 8 pessoas em dois grupos de 4
pessoas cada?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
12 / 18
Permutação Simples
Exemplos:
De quantos modos podemos dividir 8 pessoas em dois grupos de 4
pessoas cada?
Podemos enfileirar as 8 pessoas e separá-las em dois grupos as 4 primeiras
e as 4 últimas, dando um total de 8! possibilidades.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
12 / 18
Permutação Simples
Exemplos:
De quantos modos podemos dividir 8 pessoas em dois grupos de 4
pessoas cada?
Podemos enfileirar as 8 pessoas e separá-las em dois grupos as 4 primeiras
e as 4 últimas, dando um total de 8! possibilidades. No entanto, a divisão
adcd/ef gh é idêntica à divisão ef gh/abcd.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
12 / 18
Permutação Simples
Exemplos:
De quantos modos podemos dividir 8 pessoas em dois grupos de 4
pessoas cada?
Podemos enfileirar as 8 pessoas e separá-las em dois grupos as 4 primeiras
e as 4 últimas, dando um total de 8! possibilidades. No entanto, a divisão
adcd/ef gh é idêntica à divisão ef gh/abcd. Logo, dessa forma, cada
grupo é contado duas vezes. Devemos observar também que os grupos
abcd e bacd são idênticos.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
12 / 18
Permutação Simples
Exemplos:
De quantos modos podemos dividir 8 pessoas em dois grupos de 4
pessoas cada?
Podemos enfileirar as 8 pessoas e separá-las em dois grupos as 4 primeiras
e as 4 últimas, dando um total de 8! possibilidades. No entanto, a divisão
adcd/ef gh é idêntica à divisão ef gh/abcd. Logo, dessa forma, cada
grupo é contado duas vezes. Devemos observar também que os grupos
abcd e bacd são idênticos. O que ocorre no primeiro e no segundo grupo.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
12 / 18
Permutação Simples
Exemplos:
De quantos modos podemos dividir 8 pessoas em dois grupos de 4
pessoas cada?
Podemos enfileirar as 8 pessoas e separá-las em dois grupos as 4 primeiras
e as 4 últimas, dando um total de 8! possibilidades. No entanto, a divisão
adcd/ef gh é idêntica à divisão ef gh/abcd. Logo, dessa forma, cada
grupo é contado duas vezes. Devemos observar também que os grupos
abcd e bacd são idênticos. O que ocorre no primeiro e no segundo grupo.
Cada grupo deve ser contabilizado uma única vez.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
12 / 18
Permutação Simples
Exemplos:
De quantos modos podemos dividir 8 pessoas em dois grupos de 4
pessoas cada?
Podemos enfileirar as 8 pessoas e separá-las em dois grupos as 4 primeiras
e as 4 últimas, dando um total de 8! possibilidades. No entanto, a divisão
adcd/ef gh é idêntica à divisão ef gh/abcd. Logo, dessa forma, cada
grupo é contado duas vezes. Devemos observar também que os grupos
abcd e bacd são idênticos. O que ocorre no primeiro e no segundo grupo.
Cada grupo deve ser contabilizado uma única vez. Logo o número de
modos que ser pode dividir essas pessoas, em dois grupos, é
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
12 / 18
Permutação Simples
Exemplos:
De quantos modos podemos dividir 8 pessoas em dois grupos de 4
pessoas cada?
Podemos enfileirar as 8 pessoas e separá-las em dois grupos as 4 primeiras
e as 4 últimas, dando um total de 8! possibilidades. No entanto, a divisão
adcd/ef gh é idêntica à divisão ef gh/abcd. Logo, dessa forma, cada
grupo é contado duas vezes. Devemos observar também que os grupos
abcd e bacd são idênticos. O que ocorre no primeiro e no segundo grupo.
Cada grupo deve ser contabilizado uma única vez. Logo o número de
modos que ser pode dividir essas pessoas, em dois grupos, é
8!
= 35.
2 × 4! × 4!
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
12 / 18
Permutação Simples - Exercı́cios
1
Quantos são os anagramas da palavra CAPÍTULO:
1
Que começam por consoante e terminam por vogal?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
13 / 18
Permutação Simples - Exercı́cios
1
Quantos são os anagramas da palavra CAPÍTULO:
1
2
Que começam por consoante e terminam por vogal?
Que têm as letras C, A, P juntas nessa ordem ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
13 / 18
Permutação Simples - Exercı́cios
1
Quantos são os anagramas da palavra CAPÍTULO:
1
2
3
Que começam por consoante e terminam por vogal?
Que têm as letras C, A, P juntas nessa ordem ?
Que têm as letras C, A, P juntas em qualquer ordem ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
13 / 18
Permutação Simples - Exercı́cios
1
Quantos são os anagramas da palavra CAPÍTULO:
1
2
3
4
Que
Que
Que
Que
começam por consoante e terminam por vogal?
têm as letras C, A, P juntas nessa ordem ?
têm as letras C, A, P juntas em qualquer ordem ?
têm as vogais e as consoantes intercaladas ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
13 / 18
Permutação Simples - Exercı́cios
1
Quantos são os anagramas da palavra CAPÍTULO:
1
2
3
4
5
Que
Que
Que
Que
Que
começam por consoante e terminam por vogal?
têm as letras C, A, P juntas nessa ordem ?
têm as letras C, A, P juntas em qualquer ordem ?
têm as vogais e as consoantes intercaladas ?
têm a letra C no primeiro lugar e a letra A no segundo lugar?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
13 / 18
Permutação Simples - Exercı́cios
1
Quantos são os anagramas da palavra CAPÍTULO:
1
2
3
4
5
6
Que
Que
Que
Que
Que
Que
começam por consoante e terminam por vogal?
têm as letras C, A, P juntas nessa ordem ?
têm as letras C, A, P juntas em qualquer ordem ?
têm as vogais e as consoantes intercaladas ?
têm a letra C no primeiro lugar e a letra A no segundo lugar?
têm a letra C no primeiro lugar ou a letra A no segundo lugar?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
13 / 18
Permutação Simples - Exercı́cios
1
Quantos são os anagramas da palavra CAPÍTULO:
1
2
3
4
5
6
7
Que começam por consoante e terminam por vogal?
Que têm as letras C, A, P juntas nessa ordem ?
Que têm as letras C, A, P juntas em qualquer ordem ?
Que têm as vogais e as consoantes intercaladas ?
Que têm a letra C no primeiro lugar e a letra A no segundo lugar?
Que têm a letra C no primeiro lugar ou a letra A no segundo lugar?
Que tem a letra C no primeiro lugar ou a letra A no segundo lugar ou a
letra P no terceiro lugar?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
13 / 18
Permutação Simples - Exercı́cios
1
As finalistas do concurso para Miss Universo são: Miss Japão, Miss
Brasil, Miss Finln̂dia, Miss Argentina e Miss Noruega. De quantas
formas os juı́zes poderão escolher o primeiro, o segundo e o terceiro
lugares nesse concurso?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
14 / 18
Permutação Simples - Exercı́cios
1
As finalistas do concurso para Miss Universo são: Miss Japão, Miss
Brasil, Miss Finln̂dia, Miss Argentina e Miss Noruega. De quantas
formas os juı́zes poderão escolher o primeiro, o segundo e o terceiro
lugares nesse concurso?
2
Quantos números pares de três algarismos distintos podemos formar
com os algarismos 1, 3, 6, 7, 8,9?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
14 / 18
Permutação Simples - Exercı́cios
1
As finalistas do concurso para Miss Universo são: Miss Japão, Miss
Brasil, Miss Finln̂dia, Miss Argentina e Miss Noruega. De quantas
formas os juı́zes poderão escolher o primeiro, o segundo e o terceiro
lugares nesse concurso?
2
Quantos números pares de três algarismos distintos podemos formar
com os algarismos 1, 3, 6, 7, 8,9?
3
Formados e dispostos em ordem crescente todos os números que se
obtêm permutando os algarismos 1, 2, 4, 6, 8, que lugar ocupa o
número 68412 ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
14 / 18
Permutação Simples - Exercı́cios
1
As finalistas do concurso para Miss Universo são: Miss Japão, Miss
Brasil, Miss Finln̂dia, Miss Argentina e Miss Noruega. De quantas
formas os juı́zes poderão escolher o primeiro, o segundo e o terceiro
lugares nesse concurso?
2
Quantos números pares de três algarismos distintos podemos formar
com os algarismos 1, 3, 6, 7, 8,9?
3
Formados e dispostos em ordem crescente todos os números que se
obtêm permutando os algarismos 1, 2, 4, 6, 8, que lugar ocupa o
número 68412 ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
14 / 18
Combinações Simnples
Pergunta:
De quantos modos podemos escolher p objetos distintos entre n objetos
distintos dados?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
15 / 18
Combinações Simnples
Pergunta:
De quantos modos podemos escolher p objetos distintos entre n objetos
distintos dados?
Ou
Quantos são os subconjuntos com p elementos do conjunto
{a1 , a2 , · · · , an }?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
15 / 18
Combinações Simnples
Pergunta:
De quantos modos podemos escolher p objetos distintos entre n objetos
distintos dados?
Ou
Quantos são os subconjuntos com p elementos do conjunto
{a1 , a2 , · · · , an }?
Se considerarmos um conjunto {a1 , a2 , a3 , a4 , a5 }
então teremos as seguintes combinações
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
15 / 18
Combinações Simnples
Pergunta:
De quantos modos podemos escolher p objetos distintos entre n objetos
distintos dados?
Ou
Quantos são os subconjuntos com p elementos do conjunto
{a1 , a2 , · · · , an }?
Se considerarmos um conjunto {a1 , a2 , a3 , a4 , a5 }
então teremos as seguintes combinações
{a1 , a2 , a3 }, {a1 , a2 , a4 }, {a1 , a2 , a5 }, {a1 , a3 , a4 }, {a1 , a3 , a5 },
{a1 , a4 , a5 }, {a2 , a3 , a4 }, {a2 , a4 , a5 }, {a3 , a4 , a5 }, {a2 , a3 , a5 }
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
15 / 18
Combinações Simnples
Pergunta:
De quantos modos podemos escolher p objetos distintos entre n objetos
distintos dados?
Ou
Quantos são os subconjuntos com p elementos do conjunto
{a1 , a2 , · · · , an }?
Se considerarmos um conjunto {a1 , a2 , a3 , a4 , a5 }
então teremos as seguintes combinações
{a1 , a2 , a3 }, {a1 , a2 , a4 }, {a1 , a2 , a5 }, {a1 , a3 , a4 }, {a1 , a3 , a5 },
{a1 , a4 , a5 }, {a2 , a3 , a4 }, {a2 , a4 , a5 }, {a3 , a4 , a5 }, {a2 , a3 , a5 }
O número de combinações simples de classe p de n objetos é
representada por Cnp .
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
15 / 18
Combinações Simnples
Pergunta:
De quantos modos podemos escolher p objetos distintos entre n objetos
distintos dados?
Ou
Quantos são os subconjuntos com p elementos do conjunto
{a1 , a2 , · · · , an }?
Se considerarmos um conjunto {a1 , a2 , a3 , a4 , a5 }
então teremos as seguintes combinações
{a1 , a2 , a3 }, {a1 , a2 , a4 }, {a1 , a2 , a5 }, {a1 , a3 , a4 }, {a1 , a3 , a5 },
{a1 , a4 , a5 }, {a2 , a3 , a4 }, {a2 , a4 , a5 }, {a3 , a4 , a5 }, {a2 , a3 , a5 }
O número de combinações simples de classe p de n objetos é
representada por Cnp . Assim, em nosso exemplo C53 = 10.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
15 / 18
Combinações Simnples
Analisando a resposta ...
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
A escolha do segundo elemento da combinação pode ser feita de 4
modos.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
A escolha do segundo elemento da combinação pode ser feita de 4
modos.
A escolha do terceiro elemento da combinação pode ser feita de 3
modos.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
A escolha do segundo elemento da combinação pode ser feita de 4
modos.
A escolha do terceiro elemento da combinação pode ser feita de 3
modos.
Portanto a resposta parece ser 5 × 4 × 3 = 60.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
A escolha do segundo elemento da combinação pode ser feita de 4
modos.
A escolha do terceiro elemento da combinação pode ser feita de 3
modos.
Portanto a resposta parece ser 5 × 4 × 3 = 60.
Entretanto,
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
A escolha do segundo elemento da combinação pode ser feita de 4
modos.
A escolha do terceiro elemento da combinação pode ser feita de 3
modos.
Portanto a resposta parece ser 5 × 4 × 3 = 60.
Entretanto,
Se pensarmos na combinação {a1 , a2 , a3 }
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
A escolha do segundo elemento da combinação pode ser feita de 4
modos.
A escolha do terceiro elemento da combinação pode ser feita de 3
modos.
Portanto a resposta parece ser 5 × 4 × 3 = 60.
Entretanto,
Se pensarmos na combinação {a1 , a2 , a3 } verificamos que
{a1 , a2 , a3 }, {a1 , a3 , a2 }, {a2 , a1 , a3 }, · · · são idênticas. e foram contadas
como se fossem diferentes.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
A escolha do segundo elemento da combinação pode ser feita de 4
modos.
A escolha do terceiro elemento da combinação pode ser feita de 3
modos.
Portanto a resposta parece ser 5 × 4 × 3 = 60.
Entretanto,
Se pensarmos na combinação {a1 , a2 , a3 } verificamos que
{a1 , a2 , a3 }, {a1 , a3 , a2 }, {a2 , a1 , a3 }, · · · são idênticas. e foram contadas
como se fossem diferentes.
Em suma, na resposta 60 estamos contando cada combinação uma vez
para cada ordem de escrever seus elementos.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Analisando a resposta ...
A escolha do primeiro elemento da combinação pode ser feita de 5
modos.
A escolha do segundo elemento da combinação pode ser feita de 4
modos.
A escolha do terceiro elemento da combinação pode ser feita de 3
modos.
Portanto a resposta parece ser 5 × 4 × 3 = 60.
Entretanto,
Se pensarmos na combinação {a1 , a2 , a3 } verificamos que
{a1 , a2 , a3 }, {a1 , a3 , a2 }, {a2 , a1 , a3 }, · · · são idênticas. e foram contadas
como se fossem diferentes.
Em suma, na resposta 60 estamos contando cada combinação uma vez
para cada ordem de escrever seus elementos. Como em cada combinação
os elementos podem ser escritos em 3! ordens, cada combinação foi
contada 6 vezes. Logo a resposta é 60/6 = 10.
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
16 / 18
Combinações Simnples
Em geral
De uma forma geral temos
Cnp =
n(n − 1) · · · (n − p + 1)
,
p!
Márcio Bortoloti (DCET/UESB)
0<p<n
Combinatória
e C0n = 1.
Outubro de 2012
17 / 18
Combinações Simnples
Em geral
De uma forma geral temos
Cnp =
n(n − 1) · · · (n − p + 1)
,
p!
0<p<n
e C0n = 1.
Ou de modo alternativo
Cnp =
Márcio Bortoloti (DCET/UESB)
n!
,
p!(n − p)!
Combinatória
0 ≤ p ≤ n.
Outubro de 2012
17 / 18
Combinações Simnples
Exemplos:
Quantas saladas contendo exatamente 4 frutas podemos formar com
10 frutas diferentes?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
18 / 18
Combinações Simnples
Exemplos:
Quantas saladas contendo exatamente 4 frutas podemos formar com
10 frutas diferentes?
Marcam-se 5 pontos sobre uma reta r e 8 pontos sobre uma reta r0
paralela a r. Quantos triângulos existem com vértices em 3 desses 13
pontos ?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
18 / 18
Combinações Simnples
Exemplos:
Quantas saladas contendo exatamente 4 frutas podemos formar com
10 frutas diferentes?
Marcam-se 5 pontos sobre uma reta r e 8 pontos sobre uma reta r0
paralela a r. Quantos triângulos existem com vértices em 3 desses 13
pontos ?
De quantos modos podemos escolher 6 pessoas, incluindo pelo menos
duas mulheres, em um grupo de 7 homens e 4 mulheres?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
18 / 18
Combinações Simnples
Exemplos:
Quantas saladas contendo exatamente 4 frutas podemos formar com
10 frutas diferentes?
Marcam-se 5 pontos sobre uma reta r e 8 pontos sobre uma reta r0
paralela a r. Quantos triângulos existem com vértices em 3 desses 13
pontos ?
De quantos modos podemos escolher 6 pessoas, incluindo pelo menos
duas mulheres, em um grupo de 7 homens e 4 mulheres?
Uma prova consta de 15 questões, das quais o aluno deve resolver 10.
De quantas formas ele poderá escolher as 10 questões?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
18 / 18
Combinações Simnples
Exemplos:
Quantas saladas contendo exatamente 4 frutas podemos formar com
10 frutas diferentes?
Marcam-se 5 pontos sobre uma reta r e 8 pontos sobre uma reta r0
paralela a r. Quantos triângulos existem com vértices em 3 desses 13
pontos ?
De quantos modos podemos escolher 6 pessoas, incluindo pelo menos
duas mulheres, em um grupo de 7 homens e 4 mulheres?
Uma prova consta de 15 questões, das quais o aluno deve resolver 10.
De quantas formas ele poderá escolher as 10 questões?
Temos 10 homens e 10 mulheres. Quantas comissões de 5
pessoas podemos formar se em cada uma deve haver 3 homens
e 2 mulheres?
Márcio Bortoloti (DCET/UESB)
Combinatória
Outubro de 2012
18 / 18