Upload
nandoruas
View
256
Download
0
Embed Size (px)
DESCRIPTION
materia de matematica discreta
Citation preview
Anlise Combinatria
Antonio Alfredo Ferreira [email protected]
http://www.dcc.ufmg.br/~loureiro
Olga Nikolaevna [email protected]
UFMG/ICEx/DCC MD Analise Combinatoria 1
Introduo
Ramo da matemtica que trata da contagem. Em geral, a dificuldade no est em como contar mas o que contar. Em Cincia da Computao, questes de contagem so importantes j que
temos uma quantidade finita de recursos. Exemplos:
Qual a quantidade de memria que ser utilizada por um determinado pro-grama que faz alocao dinmica de memria?
Quantos usurios um determinado sistema computacional tem capacidadede atender?
Quantas computaes um determinado algoritmo executa? (Qual o custocomputacional em termos de tempo e espao de um determinado algo-ritmo?)
Alm disso, contagem a base de probabilidade e estatstica. Contagem baseada em dois princpios:
Princpio da Multiplicao Princpio da Adio
UFMG/ICEx/DCC MD Analise Combinatoria 2
Trs portas, um prmio; Voc escolhe e troca?ou o Monty Hall Problem
In the September 9, 1990 issue of Parade magazine, the columnist Marilyn vos Savant respon-ded to this letter:
Suppose youre on a game show, and youre given the choice of three doors. Behindone door is a car, behind the others, goats. You pick a door, say number 1, and the host,who knows whats behind the doors, opens another door, say number 3, which has agoat. He says to you, Do you want to pick door number 2? Is it to your advantage toswitch your choice of doors? Craig F. Whitaker, Columbia, MD
The letter roughly describes a situation faced by contestants on the 1970s game show LetsMake a Deal, hosted by Monty Hall and Carol Merrill. Marilyn replied that the contestant shouldindeed switch. But she soon received a torrent of letters many from mathematicians tellingher that she was wrong. The problem generated thousands of hours of heated debate.
Was Marilyn right?
UFMG/ICEx/DCC MD Analise Combinatoria 3
Trs portas, um prmio; Voc escolhe uma porta edepois troca?
Suponha que voc esteja em um programa de televiso no qual voc pode ganhar umprmio. Existem trs portas (identificadas como A, B e C) e atrs de uma delas esto prmio e nas outras duas no h nada. Voc escolhe uma porta e o anfitrio, quesabe onde est o prmio, abre uma outra porta vazia. Ele lhe pergunta: Voc desejamudar de porta? O que voc faz e por que?
Problema que envolve probabilidade e, consequentemente, contagem!
Qualquer problema de probabilidade envolve algum tipo de experimento, pro-cesso ou jogo aleatrio (randmico).
Cada problema possui dois desafios distintos:1. Como modelar o problema matematicamente?2. Como resolver o problema matemtico resultante?
Estratgia a ser usada: Resolver o problema em quatro passos.
UFMG/ICEx/DCC MD Analise Combinatoria 4
Os quatro passos
1. Determine o espao de amostragem.
2. Defina o evento de interesse.
3. Determine as probabilidades dos resultados.
4. Determine a probabilidade do evento.
UFMG/ICEx/DCC MD Analise Combinatoria 5
Suposies para resolver o problema
1. O prmio igualmente provvel de estar em cada uma das trs portas.
2. O jogador igualmente provvel de escolher uma das trs portas.
3. Depois que o jogador escolhe uma porta, o anfitrio deve abrir uma outraporta vazia e lhe perguntar se deseja trocar ou no de porta.
4. O anfitrio tem a escolha de qual porta abrir e, assim, ele igualmenteprovvel de escolher uma porta dentre as restantes.
UFMG/ICEx/DCC MD Analise Combinatoria 6
Passo 1: Determine o espao de amostragem
O primeiro objetivo encontrar todas as possibilidades de um experimento, ouseja, tudo que deve ser contado.
Um experimento tpico envolve diferentes quantidades aleatrias.
No caso deste problema, temos:1. A porta na qual est o prmio;2. A porta escolhida inicialmente pelo jogador;3. A porta vazia escolhida pelo apresentador;
Cada possvel combinao destas quantidades aleatrias chamada de resul-tado (outcome).
O conjunto de todas resultados o espao de amostragem do experimento.
A questo seguinte : como representar essas possibilidades? rvore de possibilidades.
UFMG/ICEx/DCC MD Analise Combinatoria 7
rvore de possibilidades e Passo 1
rvore de possibilidades: Ferramenta grfica, que pode ser usada nas quatro etapas. Apropriada quando o nmero de resultados no muito grande ou o pro-
blema bem estruturado. Ajuda a compreender o espao de amostragem de um experimento.
Primeira quantidade aleatria: porta na qual o prmio est.
Possibilidades
Porta doprmio
A
B
C
UFMG/ICEx/DCC MD Analise Combinatoria 8
rvore de possibilidades e Passo 1
Segunda quantidade aleatria: porta escolhida inicialmente pelo jogador.
Para cada porta possvel onde est o prmio, o jogador pode escolher inicial-mente qualquer uma das trs portas. Isso representado acrescentando umasegunda ramificao rvore.
A
C
A
C
A
B
C
B
B
Porta doprmio
Escolha inicialdo jogador
A
B
C
Possibilidades
UFMG/ICEx/DCC MD Analise Combinatoria 9
rvore de possibilidades e Passo 1
Terceira quantidade aleatria: porta vazia escolhida pelo apresentador.
Finalmente, o anfitrio abre uma porta vazia.
Dependendo da escolha do jogador e da porta do prmio, o anfitrio tem umaou duas escolhas.
Todas essas possibilidades so apresentadas em uma terceira ramificao darvore.
UFMG/ICEx/DCC MD Analise Combinatoria 10
rvore de possibilidades e Passo 1
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
A,C,B
C,A,B
C,B,A
C,C,A
C,C,B
A,A,C
A,A,B
B,A,C
C
C
A
C
AB
A
B
B
C
C
B
A
B
B
C
A
A
Porta doprmio
Escolha inicialdo jogador
A
B
C
Portarevelada
Possibilidades
Resultado
A
C
B
B,B,C
B,B,A
B,C,A
A,B,C
UFMG/ICEx/DCC MD Analise Combinatoria 11
rvore de possibilidades e Passo 1
Veja que existe uma relao entre a rvore de possibilidades e o que foi ditoanteriormente: Cada folha da rvore representa um resultado do experimento. O conjunto de todas as folhas representa o espao de amostragem.
Neste problema, o espao de amostragem contm 12 resultados (folhas).
Para facilitar, cada folha foi identificada por uma tripla de portas que indica(porta onde est o prmio, porta escolhida inicialmente pelo jogador, portarevelada pelo anfitrio).
Desta forma, o espao de amostragem S representado por:
S =
{(A,A,B), (A,A,C), (A,B,C), (A,C,B), (B,A,C), (B,B,A),(B,B,C), (B,C,A), (C,A,B), (C,B,A), (C,C,A), (C,C,B)
}O diagrama tem uma interpretao mais ampla ainda: cada experimento podeser considerado um caminho entre a raiz da rvore e uma folha, onde o cami-nho tomado em cada passo determinado randomicamente.
UFMG/ICEx/DCC MD Analise Combinatoria 12
Passo 2: Defina os eventos de interesse
Nosso objetivo responder a perguntas do tipo:Qual a probabilidade de . . . ?,
onde . . . representa alguma frase como: o jogador ganhar o prmio se ele mudar a porta escolhida inicialmente, o jogador escolher inicialmente a porta do prmio, ou o prmio estar na porta C.
Praticamente qualquer pergunta desse tipo pode ser modelada matematica-mente como um evento, que definido como um subconjunto do espao deamostragem.
UFMG/ICEx/DCC MD Analise Combinatoria 13
Passo 2: Defina os eventos de interesse
Por exemplo, o evento que o prmio est na portaC o conjunto de resultados:
{(C,A,B), (C,B,A), (C,C,A), (C,C,B)}
O evento que o jogador escolhe inicialmente a porta do prmio o conjunto deresultados:
{(A,A,B), (A,A,C), (B,B,A), (B,B,C), (C,C,A), (C,C,B)}
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
A,C,B
C,A,B
C,B,A
C,C,A
C,C,B
A,A,C
A,A,B
B,A,C
C
C
A
C
AB
A
B
B
C
C
B
A
B
B
C
A
A
Porta doprmio
Escolha inicialdo jogador
A
B
C
Portarevelada
Possibilidades
Resultado
A
C
B
B,B,C
B,B,A
B,C,A
A,B,C
UFMG/ICEx/DCC MD Analise Combinatoria 14
Passo 2: Defina os eventos de interesse
Neste caso, estamos interessados no evento que o jogador ganha o prmio semudar a porta escolhida inicialmente, que tem como conjunto de resultados:{(A,B,C), (A,C,B), (B,A,C), (B,C,A), (C,A,B), (C,B,A)}.
Os resultados que definem este evento esto marcados com o smbolo .
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
A,C,B
C,A,B
C,B,A
C,C,A
C,C,B
A,A,C
A,A,B
B,A,C
C
C
A
C
AB
A
B
B
C
C
B
A
B
B
C
A
A
Porta doprmio
Escolha inicialdo jogador
A
B
C
Portarevelada
Possibilidades
ResultadoTrocarganha?
A
C
B
B,B,C
B,B,A
B,C,A
A,B,C
UFMG/ICEx/DCC MD Analise Combinatoria 15
Passo 2: Defina os eventos de interesse
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
A,C,B
C,A,B
C,B,A
C,C,A
C,C,B
A,A,C
A,A,B
B,A,C
C
C
A
C
AB
A
B
B
C
C
B
A
B
B
C
A
A
Porta doprmio
Escolha inicialdo jogador
A
B
C
Portarevelada
Possibilidades
ResultadoTrocarganha?
A
C
B
B,B,C
B,B,A
B,C,A
A,B,C
Observe que exatamente metade dos resultados est marcado. O jogador ganha em metade dos resultados.
Podemos concluir que o jogador que troca a porta ganha o prmio com probabilidade 12?
No! Cada resultado no igualmente provvel!
UFMG/ICEx/DCC MD Analise Combinatoria 16
Passo 3: Determine as probabilidades dosresultados
At agora temos todos os resultados do experimento.
Devemos determinar a probabilidade de cada resultado, que um nmero realentre 0 and 1. A soma das probabilidades de todos os resultados deve ser 1.
As probabilidades dos resultados so determinadas pelo fenmeno que esta-mos modelando e no so quantidades que podem ser derivadas matematica-mente.
No entanto, tcnicas matemticas podem nos ajudar a calcular a probabilidadede cada resultado baseado em decises de modelagem.
Vamos resolver este problema em dois estgios:1. Clculo da probabilidade de cada aresta do caminho, e2. Clculo da probabilidade de cada resultado.
UFMG/ICEx/DCC MD Analise Combinatoria 17
Clculo da probabilidade de cada aresta docaminho
Deve-se atribuir uma probabilidade a cada aresta de acordo com as suposiesfeitas.
No caso de haver uma nica opo, atribui-se a probabilidade 1.
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
1/3
1/3
1/3
1/3
1/3
1/21/2
1/21/2
1/21/2
1
1
1
1
1
B,B,C
B,B,A
B,C,A
A,B,C
A,C,B
C,A,B
C,B,A
C,C,A
C,C,B
A,A,C
A,A,B
B,A,C
C
C
A
C
AB
A
B
B
C
C
B
A
B
B
C
A
A
Porta doprmio
Escolha inicialdo jogador
A
B
C
1/3
1/3
1/3
1
Portarevelada
Possibilidades
ResultadoTrocarganha?
A
C
B
1/3
1/3
1/3
1/3
UFMG/ICEx/DCC MD Analise Combinatoria 18
Clculo da probabilidade de cada resultado
A probabilidade de cada resultado o produto de cada probabilidade no cami-nho entre a raiz da rvore e o resultado.
Por exemplo, a probabilidade para o resultado (A,A,B) 13 13 12 = 118.
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )
1/3
1/3
1/3
1/3
1/3
1/21/2
1/21/2
1/21/2
1
1
1
1
1
B,B,C
B,B,A
B,C,A
A,B,C
A,C,B
C,A,B
C,B,A
C,C,A
C,C,B
A,A,C
A,A,B
B,A,C
C
C
A
C
AB
A
B
B
C
C
B
A
B
B
C
A
A
Porta doprmio
Escolha inicialdo jogador
A
B
C
1/3
1/3
1/3
1
Portarevelada
Possibilidades
Probabilidade
1/18
1/18
1/18
1/18
1/18
1/18
1/9
1/9
1/9
1/9
1/9
1/9
ResultadoTrocarganha?
A
C
B
1/3
1/3
1/3
1/3
UFMG/ICEx/DCC MD Analise Combinatoria 19
Clculo da probabilidade de cada resultado
Especificar a probabilidade de cada resultado significa definir um funo queatribui a cada resultado uma probabilidade. Esta funo usualmente chamada de Pr.
Assim, neste problema temos:
Pr(A,A,B) = 118Pr(A,A,C) = 118Pr(A,B,C) = 19
...
Lembre-se que a soma de todas as probabilidades dos resultados dever ser 1,i.e.,
xSPr(x) = 1.
UFMG/ICEx/DCC MD Analise Combinatoria 20
Clculo da probabilidade de cada resultado
Espao de amostragem S+
Funo de probabilidade Pr: S [0,1]
Espao de probabilidade
Espao de probabilidade: Descreve todos os possveis resultados de um experimento e a probabili-
dade de cada um. Modelo matemtico completo de um experimento.
UFMG/ICEx/DCC MD Analise Combinatoria 21
Passo 4: Determine a probabilidade do evento
A partir da probabilidade de cada resultado, desejamos calcular a probabili-dade do evento (E) de interesse.
Probabilidade de um evento E: A soma das probabilidades dos resultados que o contm. A probabilidade de um evento E S escrita como Pr(E), que pode ser
representada como:
Pr(E) =xE
Pr(x)
Por exemplo, a probabilidade do evento E: o jogador ganhar o prmio casoele mude a porta escolhida inicialmente :
Pr(E) = Pr(A,B,C) + Pr(A,C,B) + Pr(B,A,C)+
Pr(B,C,A) + Pr(C,A,B) + Pr(C,B,A)
= 19 +19 +
19 +
19 +
19 +
19
= 23
UFMG/ICEx/DCC MD Analise Combinatoria 22
Revisitando o problema
Neste caso, o jogador: ganha o prmio com probabilidade 23, caso mude a porta.
perde o prmio com probabilidade 13, caso mantenha a porta. Soluo correta para as suposies apresentadas.
Vamos supor que o apresentador pode abrir ou no uma porta vazia e que eles faz isso caso o jogador tenha escolhido a porta com prmio. Nesse caso, se o jogador trocar de porta ele nunca ganha!
UFMG/ICEx/DCC MD Analise Combinatoria 23
rvore de possibilidades ePrincpio da multiplicao
Uma rvore um tipo particular de um grafo onde no existem ciclos.
uma estrutura muito til para registrar todas as possibilidades em situaesem que os eventos ocorrem em ordem.
UFMG/ICEx/DCC MD Analise Combinatoria 24
rvore de possibilidades ePrincpio da multiplicao
Exemplo 1 Regras para deciso de um torneiro entre os times A e B:
Cada jogo tem sempre um vencedor O time para ser campeo deve vencer dois jogos consecutivos ou um total de
trs jogos
De quantas formas diferentes o torneio pode ser jogado?
UFMG/ICEx/DCC MD Analise Combinatoria 25
rvore de possibilidades ePrincpio da multiplicao
A
A*A*
A*
A*
B*
B* B*
B*
A*
B*
AxB
A
B
AxB
AxB
A
B
A
B
AxB
AxB
B
A
B
A
AxB
AxB
B
A
B
A
AxB
AxB
B
A
B
Notao: X indica que o time X vencedor.
UFMG/ICEx/DCC MD Analise Combinatoria 26
rvore de possibilidades ePrincpio da multiplicao
Exemplo 1 (continuao) Formas diferentes de o torneio ser jogado:1. AA2. ABAA3. ABABA4. ABABB5. ABB6. BAA7. BABAA8. BABAB9. BABB
10. BBOu seja, 10 formasdiferentes.
A
A*A*
A*
A*
B*
B* B*
B*
A*
B*
AxB
A
B
AxB
AxB
A
B
A
B
AxB
AxB
B
A
B
A
AxB
AxB
B
A
B
A
AxB
AxB
B
A
B
UFMG/ICEx/DCC MD Analise Combinatoria 27
rvore de possibilidades ePrincpio da multiplicao
Exemplo 2 Considere um sistema computacional que possui quatro unidadesde Entrada/Sada A, B, C e D e trs processadores X, Y e Z. Qualquerunidade de E/S pode ser conectada a um processador. Quantas possibilidadesexistem de conectar uma unidade de E/S a um processador?
4 3 = 12ou seja, 12 configuraesdiferentes
Processador
BX
Y
Z
AX
Y
Z
X
Y
Z
DX
Y
Z
C
SistemaComputacional
E/S
UFMG/ICEx/DCC MD Analise Combinatoria 28
Princpio da multiplicao
Se uma operao consiste em k passos, sendo que o primeiro passo pode ser executado de n1 formas diferentes, ou seja, exis-
tem n1 possibilidades para o passo 1, o segundo passo pode ser executado de n2 formas diferentes, e assim, su-
cessivamente, at o k-simo passo que pode ser executado de nk formas diferentes
ento toda a operao pode ser executada de
n1 n2 . . . nkformas diferentes.
UFMG/ICEx/DCC MD Analise Combinatoria 29
Princpio da multiplicao
Exemplo 3 Um nmero de identificao formado por uma sequncia de qua-tro smbolos escolhidos de um conjunto formado pelas 26 letras do alfabeto eos 10 dgitos. Quantos nmeros de identificao diferentes existem se repetiode smbolos permitida?
Observe que: O conjunto de smbolos formado por 36 smbolos S = {A, . . . , Z,0, . . . ,9}. A ordem de ocorrncia dos smbolos importante. Para cada posio existem 36 possibilidades.
Assim, existem
36 36 36 36 = 364 = 1 679 616nmeros de identificao diferentes.
UFMG/ICEx/DCC MD Analise Combinatoria 30
Princpio da multiplicao
Exemplo 4 Suponha o mesmo cenrio anterior de nmero de identificao mascom a restrio que smbolos no podem ser repetidos. Neste caso, quantosnmeros de identificao existem?
Observe que: O conjunto de smbolos formado por 36 smbolos. A ordem de ocorrncia dos smbolos importante. Para a primeira posio existem 36 possibilidades. Para a segunda posio, pode-se escolher um smbolo do subconjunto S2
formado por S menos o smbolo escolhido para a primeira posio. Assim, osubconjunto S2 possui sempre 35 smbolos.
Da mesma forma, para a terceira posio, o subconjunto S3 possui 34 sm-bolos e, para a quarta posio, o subconjunto S4 possui 33 smbolos.
Assim, existem
36 35 34 33 = 1 413 720nmeros de identificao diferentes.
UFMG/ICEx/DCC MD Analise Combinatoria 31
Princpio da multiplicao
Exemplo 5 Suponha que A1, A2, A3, A4 so conjuntos com n1, n2, n3, n4elementos respectivamente. Mostre que o conjunto A1 A2 A3 A4 temn1 n2 n3 n4 elementos.
Cada elemento em A1 A2 A3 A4 uma tupla ordenada da forma(a1, a2, a3, a4), onde a1 A1, a2 A2, a3 A3, a4 A4. O processode construir estas tuplas ordenadas uma operao de quatro passos:
1. Selecione o primeiro elemento da tupla do conjunto A1.2. Selecione o segundo elemento da tupla do conjunto A2.3. Selecione o terceiro elemento da tupla do conjunto A3.4. Selecione o quarto elemento da tupla do conjunto A4.
Para cada um dos passos 1 a 4 acima, existem n1, n2, n3, n4 formas respecti-vamente. Assim, pela regra da multiplicao existem n1 n2 n3 n4 tuplasdistintas no conjunto A1 A2 A3 A4.
UFMG/ICEx/DCC MD Analise Combinatoria 32
Princpio da multiplicao
Exemplo 6 Considere o conjunto de todos os circuitos eletrnicos com duas en-tradas lgicas (P eQ) e uma sada lgica. Quantas tabelas da verdade distintas,considerando a entrada e sada, podem ser construdas para este cenrio?
Esquema de um circuito e uma possvel tabela de entrada e sada:
-
--
Q
PSada
CIRCUITO
ELETRNICO
P Q Sada1a linha 1 1 12a linha 1 0 03a linha 0 1 14a linha 0 0 0
Observe que: Cada linha de entrada corresponde a uma possvel entrada. Para cada linha existem duas possibilidades de sada. A ordem em que cada linha de entrada considerada importante.
UFMG/ICEx/DCC MD Analise Combinatoria 33
Princpio da multiplicao
Assim, existem
2 1a linha
2 2a linha
2 3a linha
2 4a linha
= 16
tabelas da verdade distintas.
UFMG/ICEx/DCC MD Analise Combinatoria 34
Princpio da multiplicao
Exemplo 7 Considere o mesmo problema do exemplo anterior mas um circuitoeletrnico com k entradas. Quantas tabelas distintas existem?
Observe que: As mesmas consideraes anteriores so vlidas. Existem 2k linhas de entrada diferentes.
Assim, existem
2 . . . 2 2k vezes
= 22k
tabelas da verdade distintas.
Note que para o exemplo anterior (k = 2), temos 222
= 24 = 16 tabelasdistintas.
UFMG/ICEx/DCC MD Analise Combinatoria 35
Princpio da multiplicao
Exemplo 8 Quantas vezes os comandos do trecho de programa abaixo soexecutados?for i 1 to 4 do
for j 1 to 3 doComandos a serem executados;
endfor;
endfor;
Observe que: Claramente existe uma ordem para execuo de cada comando. Veja que a combinao de variveis de controle pode ser representada por
um par ordenado (i, j) que tm os seguintes valores:
(1,1), . . . , (1,3), (2,1), . . . , (2,3), . . . , (4,1), . . . , (4,3).
Assim, os comandos so executados
(4 1) + 1 i
(3 1) + 1 j
= 4 3 = 12
vezes.UFMG/ICEx/DCC MD Analise Combinatoria 36
Princpio da multiplicao
Exemplo 9 Considere o mesmo problema do exemplo anterior com comandosde repetio aninhados. As variveis de controle so c1, c2, . . . , cn, que podemassumir valores nas faixas [Ic1, Sc1], [Ic2, Sc2], . . . , [Icn, Scn], respectivamente(I para inferior e S para superior). Quantas vezes os comandos presentes noloop mais interno controlado pela varivel cn so executados?
Observe que: As mesmas consideraes anteriores so vlidas.
Assim, os comandos presentes no loop mais interno controlado pela varivel cnso executados
((Sc1 Ic1) + 1) c1
((Sc2 Ic2) + 1) c2
. . . ((Scn Icn) + 1) cn
vezes.
UFMG/ICEx/DCC MD Analise Combinatoria 37
Princpio da multiplicao
Exemplo 10 Considere o seguinte problema: As posies de presidente, te-soureiro e secretrio tm que ser escolhidas entre quatro pessoas A, B, C e D.Alm disso, existem duas restries:
(a) A no pode ser presidente;(b) C ou D deve ser o secretrio.
Quantas escolhas distintas existem?
natural tentar resolver o problema usando o princpio de multiplicao. Umapossibilidade fazer o seguinte raciocnio: Existem trs escolhas para presidente j que A no pode ser; Existem trs escolhas para tesoureiro de um conjunto de quatro candidatos; Duas escolhas para secretrio.o que daria 3 3 2 = 18 possibilidades.
Observe que: O nmero de escolhas de secretrio depende de como o presidente e o te-
soureiro so escolhidos e o valor acima no correto.UFMG/ICEx/DCC MD Analise Combinatoria 38
Princpio da multiplicao
Exemplo 10 (continuao) A rvore abaixo mostra todas as possibilidades:
Secretrio
B
C
D
A
C
D
A
B
A
B
C
D
C
C
D
D
D
C
Chapa
Presidente Tesoureiro
Este problema ilustra a questo da rea de Combinatria: Em geral, a dificuldade no est em como contar mas o que contar.
UFMG/ICEx/DCC MD Analise Combinatoria 39
Princpio da multiplicao
Exemplo 10 (continuao) Estratgia para resoluo do problema usando oprincpio da multiplicao:(a) Escolha o secretrio, j que existem duas possibilidades apenas: C ou D;(b) Escolha o presidente. Neste caso, existem apenas duas possibilidades j
que A e a pessoa escolhida como secretrio no podem ser escolhidascomo presidente;
(c) Escolha o tesoureiro, que pode ser uma das duas pessoas restantes.o que d 2 2 2 = 8 possibilidades.
UFMG/ICEx/DCC MD Analise Combinatoria 40
Princpio da multiplicao
Exemplo 10 (continuao) A rvore abaixo mostra todas essas possibilidades:
Chapa
A
B
A
A
B
A
D
C
B
D
B
C
D
C
TesoureiroPresidenteSecretrio
UFMG/ICEx/DCC MD Analise Combinatoria 41
Princpio da multiplicao
Exemplo 11 Um estudante tem:
4 livros de sistemas operacionais; 7 livros de programao; e 3 livros de estruturas de dados.De quantas formas diferentes os livros podem ser colocados na prateleira deuma estante, dado que livros de um mesmo assunto devem ficar juntos?
Observe que: A ordem de ocorrncia dos conjuntos de livros na estante importante. Dentro de cada conjunto de livros a ordem tambm importante. O problema pode ser dividido em duas partes: nmero de ordenaes de
conjuntos e, dentro de cada conjunto, ordenao dos livros.
UFMG/ICEx/DCC MD Analise Combinatoria 42
Princpio da multiplicao
Exemplo 11 (continuao) A quantidade de ordenaes de conjuntos de livros dada por:
3 # possibilidades parao primeiro conjunto(esquerda)
2 # possibilidades parao segundo conjunto(meio)
1 # possibilidades parao terceiro conjunto(direita)
= 6
Para cada um dos conjuntos de livros, temos as seguintes possibilidades: Sistemas operacionais (4 livros): 4 3 2 1 = 4! Programao (7 livros): 7 6 . . . 1 = 7! Estruturas de dados (3 livros): 3 2 1 = 3!
Assim, temos
6 (4! 7! 3!) = 4 354 560possibilidades de colocar os livros na estante.
UFMG/ICEx/DCC MD Analise Combinatoria 43
Princpio da multiplicao
Exemplo 12 Quantos inteiros de trs dgitos so divisveis por 5?
Observe que: Os nmeros inteiros candidatos esto no intervalo [100,999]. Os nmeros candidatos terminam em 0 ou 5.
Primeira estratgia para resolver o problema: Os nmeros divisveis por 5 nesse intervalo podem ser criados a partir da
concatenao de dgitos provenientes dos seguintes conjuntos, nessa ordem:
{1,2,3,4,5,6,7,8,9}{0,1,2,3,4,5,6,7,8,9}{0,5}
Assim, essa quantidade dada por:
9 # possibilidades parao primeiro conjunto(centena)
10 # possibilidades parao segundo conjunto(dezena)
2 # possibilidades parao terceiro conjunto(unidade)
= 180
UFMG/ICEx/DCC MD Analise Combinatoria 44
Princpio da multiplicao
Exemplo 12 (continuao) Note que o mesmo problema pode ser resolvido poroutra estratgia que no envolve o princpio da multiplicao.
Segunda estratgia para resolver o problema: Enumere os nmeros divisveis por 5 nesse intervalo:
100 . . . 105 . . . 995 . . . 999l l l
5 20 5 21 5 199
Assim, os divisores por 5 dos inteiros no intervalo [100,999] so os nmeros20,21, . . . ,199.
A quantidade de divisores dada por (199 20) + 1 = 180.
UFMG/ICEx/DCC MD Analise Combinatoria 45
Princpio da multiplicao
Exemplo 13 Quantos inteiros no intervalo [1,1000] so divisveis por 3 ou divi-sveis por 5?
Vamos usar a segunda estratgia do problema anterior:
(a) Enumere os nmeros divisveis por 3 nesse intervalo;(b) Enumere os nmeros divisveis por 5 nesse intervalo;(c) Enumere os nmeros divisveis por 3 e 5 (ou seja, 15) nesse intervalo.
A soluo deste problema dado por (a) + (b) (c) = 333 + 200 66 =467.
(a) Nmeros divisveis por 3 nesse intervalo: 333. 3 1,3 2, . . . ,3 333.
(b) Nmeros divisveis por 5 nesse intervalo: 200. 5 1,5 2, . . . ,5 200.
(c) Nmeros divisveis por 15 nesse intervalo: 66. 15 1,15 2, . . . ,15 66.
UFMG/ICEx/DCC MD Analise Combinatoria 46
Princpio da multiplicao
Exemplo 14
Quantos nmeros palndromos existem que possuem cinco dgitos?
Um nmero palndromo tem a seguinte regra de formao de dgitos:
1 = d1 2 = d2 3 = d3 4 = d2 5 = d1
Ou seja, o primeiro dgito e o quinto dgito so idnticos, assim como o segundo e quarto dgitos.
Vamos usar o seguinte raciocnio:(a) Nmero de opes para o primeiro dgito (d1) = n 1.(b) Nmero de opes para o segundo dgito (d2) = n.(c) Nmero de opes para o terceiro dgito (d3) = n.(d) Nmero de opes para o quarto dgito (d2). o mesmo valor do segundo dgito e deve
ser considerado um nico elemento que j foi contado.(e) Nmero de opes para o quinto dgito (d1). o mesmo valor do primeiro dgito e deve
ser considerado um nico elemento que j foi contado. A soluo deste problema dado por (a) (b) (c) = (n 1) n n = n3 n2
UFMG/ICEx/DCC MD Analise Combinatoria 47
Princpio da multiplicao
Exemplo 15 Use o princpio da multiplicao para provar que o conjunto
X = {x1, x2, . . . , xn}com n elementos possui 2n subconjuntos (que a cardinalidade do conjunto P(X)).Prova. Um subconjunto qualquer de X pode ser construdo em n passos:
1. Inclua ou no o elemento x1;2. Inclua ou no o elemento x2;...n. Inclua ou no o elemento xn;
Em cada passo existem duas possibilidades. Assim, o nmero de subconjuntos de X dadopor:
2 2 . . . 2 n fatores
= 2n
Observe, por exemplo, que o conjunto obtido quando nenhum elemento de X escolhido.
UFMG/ICEx/DCC MD Analise Combinatoria 48
Permutao
Definio: um arranjo ordenado de objetos sem repetio. A ordem importante. Pode-se aplicar o princpio da multiplicao.
Exemplo 16 Seja o conjunto A = {a, b, c}.(a) Quantas permutaes existem?
3 # possibilidades parao primeiro elemento
2 # possibilidades parao segundo elemento
1 # possibilidades parao terceiro elemento
= 6
(b) Quais so elas?
1. abc 2. acb
3. bac 4. bca
5. cab 6. cba
UFMG/ICEx/DCC MD Analise Combinatoria 49
Permutao: Caso I
Seja um conjunto com n elementos. Quantas permutaes existem conside-rando todos os elementos e que no h repetio?
Observe que: A ordem de ocorrncia dos smbolos do conjunto importante.
Aplicando-se o princpio da multiplicao, temos:n
# possibilidades parao primeiro elemento
(n-1) # possibilidades parao segundo elemento
. . . . . . 1 # possibilidades parao n-simo elemento
= n!
UFMG/ICEx/DCC MD Analise Combinatoria 50
Permutao: Caso II
Seja um conjunto com n elementos. Quantas permutaes existem conside-rando r (1 r n) elementos desse conjunto e que no h repetio?
Observe que: A ordem de ocorrncia dos smbolos do conjunto importante.
Aplicando-se o princpio da multiplicao, temos:n
# possibilidades parao primeiro elemento
(n-1) # possibilidades parao segundo elemento
. . . . . . (n-r+1) # possibilidades parao r-simo elemento
=
ni=nr+1
i = (n r + 1) . . . (n 1) n =
n (n 1) . . . (n r + 1) (n r) (n r 1) . . . 2 1(n r) (n r 1) . . . 2 1 =
n!
(n r)!
UFMG/ICEx/DCC MD Analise Combinatoria 51
Permutao: Caso genrico
Dado um conjunto com n (n 1) elementos e um valor de r (1 r n),existem
P (n, r) =n!
(n r)!permutaes de elementos desse conjunto considerando que no h repetio.
Lembre-se que na Permutao: Elementos no so repetidos. A ordem em que esses elementos aparecem importante, ou seja, a permu-
tao pode ser representada por uma tupla ordenada.
UFMG/ICEx/DCC MD Analise Combinatoria 52
Permutao: Caso genrico
Exemplo 17 Avalie as seguintes permutaes:
(a) P (5,2).
P (5,2) =5!
(5 2)! =5 4 3!
3!= 20
(b) Quantidade de permutaes de tamanho 4 de um conjunto de 7 objetos.
P (7,4) =7!
(7 4)! =7 6 5 4 3!
3!= 840
UFMG/ICEx/DCC MD Analise Combinatoria 53
Permutao: Caso genrico
Exemplo 18 Avalie P (n,2) + P (n,1), para n 2.
P (n,2) + P (n,1) =n!
(n 2)! +n!
(n 1)!
=n (n 1) (n 2)!
(n 2)! +n (n 1)!
(n 1)!= n (n 1) + n= n2 n + n= n2
UFMG/ICEx/DCC MD Analise Combinatoria 54
Permutao
Exemplo 19 Permutaes de letras de uma palavra:
(a) De quantas formas diferentes as letras da palavra COMPUTER podem serarranjadas numa sequncia (fila)?Todas as letras na palavra COMPUTER so distintas. Assim, o nmero deformas distintas de arranjar as letras o nmero de permutaes de umconjunto de oito elementos, ou seja, 8! = 40 320.
(b) De quantas formas diferentes as letras da palavra COMPUTER podem serarranjadas se as letras CO devem permanecer unidas nesta ordem?Se as letras CO devem permanecer unidas existem efetivamente sete obje-tos a serem arranjados. Assim, o nmero de permutaes 7! = 5 040.
UFMG/ICEx/DCC MD Analise Combinatoria 55
Permutao
Exemplo 20 Permutaes de objetos ao redor de um crculo:
A Numa reunio, seis pessoas vo estar sentadas mesaque tem formato circular. De quantas formas diferentesessas pessoas podem se sentar?
Identifique as pessoas como A, B, C, D, E e F. Somente as posies relativasimportam j que no existe uma identificao de assento na mesa. Por exemplo,comece com A e considere todos os arranjos das outras pessoas em relaoa A. As pessoas B a F podem se sentar em volta de A de todas as formaspossveis. Assim, existem 5! = 120 formas de arranjar o grupo.
UFMG/ICEx/DCC MD Analise Combinatoria 56
Princpio da adio
Existem problemas de contagem que podem ser resolvidos contando o n-mero de elementos: na unio de dois conjuntos, na diferena entre dois conjuntos, e na interseco de dois conjuntos
O princpio a ser usado neste caso chamado de Princpio da Adio.
UFMG/ICEx/DCC MD Analise Combinatoria 57
Princpio da adio
Se uma operao consiste em k passos distintos, onde os passos so mutua-mente disjuntos, sendo que o primeiro passo pode ser executado de n1 formas diferentes, ou seja, exis-
tem n1 possibilidades para o passo 1, o segundo passo pode ser executado de n2 formas diferentes, e assim su-
cessivamente at o k-simo passo que pode ser executado de nk formas diferentes
ento toda a operao pode ser executada de
n1 + n2 + . . . + nk
formas diferentes.
UFMG/ICEx/DCC MD Analise Combinatoria 58
Princpio da adio
Exemplo 21 Uma senha de usurio de um sistema computacional pode serformada por sequncias de uma a trs letras maisculas, sendo que repetiesso permitidas. Quantas senhas diferentes existem?
Observe que: O conjunto de todas as senhas formada pelos subconjuntos de senhas de
uma, duas e trs letras.
Em cada um desses subconjuntos temos a seguinte quantidade de senhas: Uma letra: 26 Duas letras: 26 26 = 262 Trs letras: 26 26 26 = 263
Assim, pelo princpio da adio temos:
26 + 262 + 263 = 18 278
senhas de usurio diferentes.UFMG/ICEx/DCC MD Analise Combinatoria 59
Princpio da adio
Exemplo 22 Quantos nmeros inteiros mpares existem no intervalo [10,99]com dgitos distintos?
[Nmeros comdgitos distintos
]=[
Dgitos das dezenasI
][
Dgitos das unidadesII
] 5
Os cinco nmeros mpares com dgitos iguais so 11, 33, 55, 77 e 99. Logo,deve-se subtrair 5.
I |{1, 2, . . . , 9}| = 9
II |{1, 3, 5, 7, 9 }| = 5
Nmeros com dgitos distintos = 9 5 5 = 40
UFMG/ICEx/DCC MD Analise Combinatoria 60
Princpio da adio
Uma consequncia importante do princpio da adio que se o nmero deelementos de um conjunto A (n(A)) e de um subconjunto prprio B (n(B)) deA so ambos conhecidos, ento o nmero de elementos de A que no estoem B pode ser calculado:
n(AB) = n(A) n(B)
A expresso acima verdadeira j que se B um subconjunto de A, ento
B (AB) = Ae os dois conjuntos B e A B no possuem elementos em comum. Assim,pelo princpio da adio,
n(B) + n(AB) = n(A)n(AB) = n(A) n(B)
UFMG/ICEx/DCC MD Analise Combinatoria 61
Princpio da adio
Exemplo 23 No exemplo 3 vimos que existem 364 = 1 679 616 identificado-res formados por uma sequncia de quatro smbolos escolhidos de um conjuntoformado pelas 26 letras do alfabeto e os 10 dgitos, com repetio de smbolos.Dessa quantidade quantos identificadores possuem pelo menos um smbolo re-petido?
Observe que: A quantidade de identificadores com pelo menos um smbolo repetido dado
por:Total de identificadores de tamanho quatro com smbolos repetidos eno repetidos menos total de identificadores de tamanho quatro comsmbolos no repetidos.
Assim, o total de identificadores de tamanho quatro com pelo menos um smbolorepetido dado por
364 (36 35 34 33) = 1 679 616 1 413 720 = 265 896UFMG/ICEx/DCC MD Analise Combinatoria 62
Princpio da adio
Exemplo 24 Quantos nmeros inteiros existem no intervalo [1,100 000] quecontm o algarismo 6 exatamente uma nica vez?
O algarismo 6 pode aparecer exatamente uma nica vez nas seguintes posi-es:
6
6
6
6
6
Nas outras posies podemos escolher qualquer algarismo de 0 a 9, exceto o6, ou seja, nove possibilidades.
Assim, temos 5 94 = 32805 nmeros.
UFMG/ICEx/DCC MD Analise Combinatoria 63
Princpio da adio
Exemplo 25 Quantos nmeros inteiros existem no intervalo [1,100 000] quecontm pelo menos um algarismo 6?
Para resolver este problema, vamos calcular a quantidade de nmeros que no tem o algarismo6 no intervalo. Neste caso, o intervalo fica alterado para [1,99 999] j que 100 000 no contmo algarismo 6.
Temos cinco posies onde podemos preencher com os algarismos de 0 a 9, exceto o 6, ouseja, temos nove possibilidades, o que gera 95 = 59 049 nmeros sem o algarismo 6. Noentanto, uma dessas sequncias formada por cinco 0s, que est fora do intervalo pedidoe, assim, temos 59 049 1 = 59 048 nmeros no intervalo [1,99 999] que no contm oalgarismo 6.
Sabemos que no intervalo [1,99 999] temos 99 999 nmeros sendo que 59 048 deles nocontm o algarismo 6. Logo, temos
99 999 59 048 = 40 951
nmeros que contm pelo menos um algarismo 6.
UFMG/ICEx/DCC MD Analise Combinatoria 64
Princpio da adio
Exemplo 26 O segredo de um cofre requer trs nmeros no intervalo [1,39]. Suponhaque o segredo pode ser construdo de tal forma que o mesmo nmero no pode ser usadoem sequncia mas o mesmo nmero pode ser usado na primeira e terceira posies. Quantossegredos existem?
Podemos resolver este problema usando a seguinte estratgia:(a) Calcular a quantidade de segredos supondo que sequncias de nmeros idnticos so
permitidas; Isto dado por 393 = 59 319.
(b) Calcular a quantidade de segredos onde os trs nmeros so idnticos; Existem exatamente 39 segredos onde os trs nmeros so idnticos.
(c) Calcular a quantidade de segredos onde existem dois nmeros idnticos em sequncia; Existem (3938)2 = 2 964 segredos onde h dois nmeros idnticos em sequn-
cia. Estes dois cenrios podem ser representados por:
n1 n1 n2 6= n11 2 3
en2 6= n1 n1 n1
1 2 3.
sendo que n1 pode variar de 1 a 39 e n2 tambm, exceto que no pode ter o mesmovalor de n1.
Logo, o nmero de segredos que satisfazem o problema dado por
(a) (b) (c) = 59 319 39 2 964 = 56 316.
UFMG/ICEx/DCC MD Analise Combinatoria 65
Princpio da adio
Exemplo 26 (continuao)
De uma forma genrica, o segredo de um cofre que requer trs nmeros no intervalo [1, n],onde o mesmo nmero no pode ser usado em sequncia mas o mesmo nmero pode serusado na primeira e terceira posies tem a seguinte quantidade de segredos:(a) Quantidade de segredos supondo que sequncias de nmeros idnticos so permitidas:
Isto dado por n3.(b) Quantidade de segredos onde os trs nmeros so idnticos:
Existem exatamente n segredos onde os trs nmeros so idnticos.(c) Quantidade de segredos onde existem dois nmeros idnticos em sequncia:
Existem n (n 1) 2 segredos onde h dois nmeros idnticos em sequncia.
Logo, a quantidade de segredos que satisfazem o problema dado por
(a) (b) (c) = n3 n 2n(n 1) = n3 2n2 + n.
UFMG/ICEx/DCC MD Analise Combinatoria 66
Resolvendo o mesmo problema com o princpio damultiplicao
Exemplo 26 (continuao)
Este mesmo problema pode ser resolvido usando o princpio da multiplicao da seguinte forma:(a) Quantidade de nmeros que podem ser usados como primeiro nmero do segredo:
Isto dado por n.(b) Quantidade de nmeros que podem ser usados como segundo nmero do segredo:
Isto dado por n 1, j que o primeiro nmero do segredo no pode ser repetido nosegundo nmero.
(c) Quantidade de nmeros que podem ser usados como terceiro nmero do segredo: Isto tambm dado por n 1. Note que temos n opes de nmeros como terceira
opo, mas o segundo nmero no pode ser usado na terceira opo.
Logo, a quantidade de segredos que satisfazem o problema dado por
(a) (b) (c) = n(n 1)(n 1) = n(n2 2n + 1) = n3 2n2 + n.
UFMG/ICEx/DCC MD Analise Combinatoria 67
Combinao e Permutao
Para cada combinao C(n, r), existem r! formas de permutar os r objetos.
Ou ainda, para cada permutao P (n, r) existem r! arranjos com o mesmoconjunto de r objetos distintos.
Pelo Princpio da Multiplicao, o nmero de permutaes de r objetos distin-tos escolhidos de n objetos o produto da quantidade de formas de escolheros r objetos, C(n, r), pela quantidade de formas de arranjar os r objetos, r!,ou seja,
C(n, r) r! = P (n, r)Ou ainda
C(n, r) =P (n, r)
r!=
n!
r!(n r)!
UFMG/ICEx/DCC MD Analise Combinatoria 68
Combinao e Permutao
Exemplo 27
Enfileiramento: De quantas formas diferentes pode-se formar uma fila com sete marcianos ecinco jovianos, sendo que dois jovianos no podem ficar juntos?
Se dois jovianos no podem ficar juntos, a nica configurao possvel de lugares na fila dadapor:
M1 M2 M3 M4 M5 M6 M7
1 2 3 4 5 6 7 8
onde Mi, i = 1 . . .7, representam os marcianos e as posies vazias de 1 a 8 representam ospossveis lugares que os jovianos podem ocupar, sendo que trs delas estaro vazias j quetemos apenas cinco jovianos.
Assim, este enfileiramento pode ser feito em duas etapas:(a) Posies dos marcianos no cenrio acima:
Isto dado por 7! = 5 040.(b) Posies dos jovianos nos oito lugares acima:
Note que devemos escolher cinco posies e para cada conjunto de posies ter umapermutao. Isto dado por C(8,5) 5!, que exatamente P (8,5) = 6 720
A quantidade total de enfileiramentos dada por 5 040 6 720 = 33 868 800.UFMG/ICEx/DCC MD Analise Combinatoria 69
Combinao
Definio: Sejam n e r inteiros no negativos com r n. Uma combinaor de um conjunto de n elementos um subconjunto de r dos n elementos.
C(n, r) representa o nmero de subconjuntos de tamanho r que podem serobtidos de um conjunto de n elementos.
Formas para representao de uma combinao: C(n, r)
(nr
)
Cn,r
nCr
nCr
UFMG/ICEx/DCC MD Analise Combinatoria 70
Combinao e Permutao
Exemplo 28 Quantas combinaes de dois elementos podem ser obtidas doconjunto {0,1,2,3}?
C(n, r) =n!
r!(n r)! =4!
2! 2! = 6
Esses seis conjuntos so:{0,1}, {0,2}, {0,3} subconjuntos que contm 0.{1,2}, {1,3} subconjuntos que contm 1 mas que no foram listados.{2,3} subconjuntos que contm 2 mas que no foram listados.
UFMG/ICEx/DCC MD Analise Combinatoria 71
Combinao e Permutao
Exemplo 29 Quantos nmeros inteiros existem no intervalo [1,99 999] quecontm exatamente os dgitos 2, 3, 4 e 5?
Posies que os dgitos podem ser colocados:
1 2 3 4 5
Idia: Cada nmero ser representado com cinco dgitos. Assim, 1 ser escrito
como 00001.
UFMG/ICEx/DCC MD Analise Combinatoria 72
Combinao e Permutao
Exemplo 29 (continuao)
Devemos:(a) Calcular a quantidade de subconjuntos de quatro posies que iro ter os quatro dgitos
obrigatrios;
Isto dado por C(5,4) = 5. Existem cinco conjuntos de quatro posies onde osdgitos obrigatrios podem ser colocados.
(b) Calcular a quantidade de permutaes que podemos ter com os quatro dgitos obrigat-rios;
Isto dado por 4! = 24. Para cada conjunto de quatro posies existem 24 permuta-es para os quatro dgitos obrigatrios.
(c) Calcular a quantidade de nmeros no intervalo que podemos ter com os dgitos obrigat-rios.
Isto dado por 5 24 = 120.(d) Calcular a quantidade de nmeros no intervalo que podemos ter incluindo os dgitos res-
tantes, ou seja, {0, 1, 6, 7, 8, 9}.
Isto dado por 6120 = 720. Existem seis outros dgitos que podem ocupar a quintae ltima posio restante para cada permutao dos quatro dgitos obrigatrios.
UFMG/ICEx/DCC MD Analise Combinatoria 73
Combinao
Suponha que desejamos selecionar r objetos distintos de um conjunto de nelementos mas a ordem no importante.
Neste caso, estamos contando o nmero de combinaes de r (r n) obje-tos distintos escolhidos de um conjunto de n (n 1) elementos onde a ordemno importante.
UFMG/ICEx/DCC MD Analise Combinatoria 74
Combinao
Exemplo 30 Numa escola, h 10 professores de Matemtica e 15 de Portu-gus. Pretende-se formar, com esses professores, uma comisso de sete mem-bros. Quantas comisses distintas podem ser formadas?
Observe que: O conjunto possui 25 professores. A ordem no importante.
C(25,7) =25!
7! 18!
=25 24 23 22 21 20 19 18!
7 6 5 4 3 2 18!= 2 043 500
UFMG/ICEx/DCC MD Analise Combinatoria 75
Combinao
Exemplo 31 Suponha que times de 5 pessoas vo ser formados de um grupode 12 pessoas. Duas pessoas desse grupo (A e B) insistem em trabalhar con-juntamente. Assim, ao se formar um time, ou as duas pessoas esto presentesou no. Quantos times podem ser formados?
[No total de times
]=
[ No de times que contmA e BI
]+
[ No de times que no contmnem A nem BII
]
I C(10,3) = 10!3!7! = 120Os times que contm A e B devem ter mais 3 pessoas das 10 restantes do grupo.
II C(10,5) = 10!5!5! = 252Os times que no contm A e B devem ter 5 pessoas das 10 restantes do grupo.
No total de times = 120 + 252 = 372
UFMG/ICEx/DCC MD Analise Combinatoria 76
Combinao
Exemplo 32 Suponha o mesmo cenrio anterior mas agora A e B no podempertencer simultaneamente a um mesmo time. Quantos times podem ser for-mados?
[No total de times
]=
[ No de times comA e sem BI
]+
[ No de times comB e sem AII
]+
[ No de times semA e sem BIII
]
I C(10,4) = 10!4!6! = 210Os times com A e sem B devem ter mais 4 pessoas das 10 restantes do grupo (10 porque
A e B esto fora e 4 porque A uma das 5 pessoas).
II C(10,4) = 10!4!6! = 210Idem ao anterior.
III C(10,5) = 10!5!5! = 252Os times que no contm A e B devem ter 5 pessoas das 10 restantes do grupo.
No total de times = 210 + 210 + 252 = 672UFMG/ICEx/DCC MD Analise Combinatoria 77
Combinao
Exemplo 32 Este problema tambm pode ser resolvido de outra forma:
[No total de times
]=
No de times com5 pessoasI
[ No de times comA e com BII
]
I C(12,5) = 12!5!7! = 792Total de times com 5 pessoas.
II C(10,3) = 10!3!7! = 120Os times que contm A e B devem ter mais 3 pessoas das 10 restantes do grupo.
No total de times = 792 120 = 672
UFMG/ICEx/DCC MD Analise Combinatoria 78
Expresses pelo menos e no mximo
Seja um conjunto S com 5 elementos.
O que significa escolher subconjuntos com pelo menos 3 elementos de S, e no mximo 2 elementos de S?
Pelo menos 3 elementos de S: Significa escolher subconjuntos com 3, 4 ou 5 elementos.
No mximo 2 elementos de S: Significa escolher subconjuntos com 0, 1 ou 2 elementos.
UFMG/ICEx/DCC MD Analise Combinatoria 79
Combinao
Exemplo 33 Suponha que o grupo de 12 pessoas seja formado por 5 homense 7 mulheres. Quantos times de 5 pessoas podem ser formados com 3 homense 2 mulheres?
[No total de times
]=
[ No de times com3 homensI
][ No de times com
2 mulheresII
]
I C(5,3) = 5!2!3! = 10Total de times com 3 homens.
II C(7,2) = 7!2!5! = 21Total de times com 2 mulheres.
No total de times = 10 21 = 210Note que o princpio da multiplicao deve ser aplicado j que temos possibilidades diferentes
para formao dos times.
UFMG/ICEx/DCC MD Analise Combinatoria 80
Combinao
Exemplo 34 Suponha o mesmo grupo anterior. Quantos times de 5 pessoaspodem ser formados com pelo menos um homem?
[No total de times
]=
No de times com5 pessoasI
[ No de times comnenhum homemII
]
I C(12,5) = 12!5!7! = 792Total de times com 5 pessoas incluindo homens e mulheres.
II C(7,5) = 7!5!2! = 21O total de times com nenhum homem exatamente a quantidade de times formados ape-
nas por mulheres.
No total de times = 792 21 = 771
UFMG/ICEx/DCC MD Analise Combinatoria 81
Combinao
Exemplo 34 Este problema tambm pode ser resolvido de outra forma:(51
)(
74
)+ {Times com 1 homem e 4 mulheres}(
52
)(
73
)+ {Times com 2 homens e 3 mulheres}(
53
)(
72
)+ {Times com 3 homens e 2 mulheres}(
54
)(
71
)+ {Times com 4 homens e 1 mulher}(
55
)(
70
){Times com 5 homens e nenhuma mulher}
UFMG/ICEx/DCC MD Analise Combinatoria 82
Combinao
Exemplo 35 Suponha o mesmo grupo anterior. Quantos times de 5 pessoaspodem ser formados com no mximo um homem?
[No total de times
]=
[ No de times comnenhum homemI
]+
[ No de times comum homemII
]
I C(7,5) = 7!5!2! = 21O total de times com nenhum homem exatamente a quantidade de times formados ape-
nas por mulheres.
II C(5,1) C(7,4) = 5!1!4! 7!4!3! = 5 35 = 175O total de times com um homem e quatro mulheres.
No total de times = 21 + 175 = 196
UFMG/ICEx/DCC MD Analise Combinatoria 83
Combinao
Exemplo 36 Numa escola, h 10 professores de Matemtica e 15 de Portu-gus. Pretende-se formar, com esses professores, uma comisso de sete mem-bros. Quantas comisses distintas podem ser formadas com, pelo menos, umprofessor de Matemtica?
[No total de comisses
]=
No de comisses com7 pessoasI
N
o de comisses comnenhum professor deMatemticaII
I C(25,7) = 25!7!18! = 2 043 500
Total de comisses com 7 pessoas incluindo professores de Matemtica e Portugus.
II C(15,7) = 15!7!8! = 25 740O total de comisses com nenhum professor de Matemtica exatamente a quantidade
de comisses formadas apenas por professores de Portugus.
No total de comisses = 2 043 500 25 740 = 2 017 760
UFMG/ICEx/DCC MD Analise Combinatoria 84
Combinao
Exemplo 36 Este problema tambm pode ser resolvido de outra forma:(101
)(
156
)+ {Comisses com 1 professor de Matemtica e 6 professores de Portugus}(
102
)(
155
)+ {Comisses com 2 professores de Matemtica e 5 professores de Portugus}(
103
)(
154
)+ {Comisses com 3 professores de Matemtica e 4 professores de Portugus}(
104
)(
153
)+ {Comisses com 4 professores de Matemtica e 3 professores de Portugus}(
105
)(
152
)+ {Comisses com 5 professores de Matemtica e 2 professores de Portugus}(
106
)(
151
)+ {Comisses com 6 professores de Matemtica e 1 professor de Portugus}(
107
)(
150
){Comisses com 7 professores de Matemtica e nenhum professor de Portugus}
UFMG/ICEx/DCC MD Analise Combinatoria 85
Combinao
Exemplo 37 Suponha o mesmo grupo anterior. Quantas comisses distintas podem serformadas com, pelo menos, dois professores de Matemtica e, pelo menos, trs professores dePortugus?
Por que o raciocnio abaixo est errado? No de comisses com
2 professores de Ma-temticaI
No de comisses com3 professores de Por-tugusII
No de comisses com2 professores dentreos restantes de Ma-temtica e/ou Portu-gusIII
I C(10,2) = 10!
2!8! = 45No de comisses com 2 professores de Matemtica.
II C(15,3) = 15!3!12! = 455
No de comisses com 3 professores de Portugus.
III C(20,2) = 20!2!18! = 190
No de comisses com 2 professores dentre os restantes de Matemtica e/ou Portugus.Note que ficam 20 professores dos 25 do grupo, j que 5 foram escolhidos.
No total de comisses = 45 455 190 = 3 890 250
UFMG/ICEx/DCC MD Analise Combinatoria 86
Combinao
Exemplo 37 (continuao) O raciocnio foi:I No de comisses com 2 professores de Matemtica II No de comisses com 3 professores de Portugus III No de comisses com 2 professores dentre os restantes de Matemtica e/ou Portugus
Um cenrio da proposio anterior pode ser representado pelos seguintes conjuntos:
II
C D E
F G H I J
d e
f g h i j
k l m n oa b c
A B
Professores de MatemticaI
Professores de Matemtica eIII
Portugus
Professores de Portugus
Neste cenrio, temos no conjunto I os elemen-tos A e B, no conjunto II os elementos a, b e c,e no conjunto III os elementos restantes.
Note que podemos escolher os professores deMatemtica C e D como os elementos do con-junto III.
No entanto, existe outro cenrio onde teremosno conjunto I os professores C e D e os pro-fessores A e B como os outros dois elementosdo conjunto III. Se os elementos do conjunto IIno mudaram ento as comisses resultantesnos dois cenrios acima so idnticas e, assim,estamos contando duas vezes a mesma comis-so.
UFMG/ICEx/DCC MD Analise Combinatoria 87
Combinao
Exemplo 37 (continuao) Este problema pode ser resolvido da seguinteforma:
II
A B C D E
F G H I J
Professores de Matemtica
I
a b c d e
f g h i j
k l m n o
Professores de Portugus
{Comisses com 4 professores de Matemtica e3 professores de Portugus}(
104
)(
153
)+
{Comisses com 3 professores de Matemtica e4 professores de Portugus}(
103
)(
154
)+
{Comisses com 2 professores de Matemtica e5 professores de Portugus}(
102
)(
155
)No total de comisses = 95 550 + 163 800 + 135 135 = 394 485.
UFMG/ICEx/DCC MD Analise Combinatoria 88
Combinao
Exemplo 38 Seja um baralho comum de 52 cartas que possui quatro naipes (,,,)de 13 denominaes cada (A,2,3, . . . ,10, J,Q,K).
(a) De quantas formas diferentes pode-se ter uma mo de poker (cinco cartas) todas domesmo naipe? Uma mo de poker pode ser construda em dois passos sucessivos: selecione um
naipe e, em seguida, escolha cinco cartas desse naipe. Pelo princpio da multiplicaotemos:
4 C(13,5) = 5 148.(b) De quantas formas diferentes pode-se ter uma mo de poker contendo trs cartas de
uma denominao e duas cartas de uma outra denominao? Essa mo de poker pode ser construda em quatro passos sucessivos: selecione a
primeira denominao para as trs cartas, selecione os trs naipes dessa denominao,selecione a segunda denominao para as outras duas cartas, selecione os dois naipesdessa denominao. Pelo princpio da multiplicao temos:
13 C(4,3) 12 C(4,2) = 3 744.
UFMG/ICEx/DCC MD Analise Combinatoria 89
Combinao
Exemplo 39 Dado um grid n m, quantas rotas (caminhos) existem entre aposio (0,0) (canto inferior esquerdo) at a posio (n,m) (canto superiordireito) se os nicos movimentos possveis so mover para a direita (D) ou paracima (C)?
...
(0,0)
(n,m)
...
...
...
...
...
...
.....
.
.....
......
....
UFMG/ICEx/DCC MD Analise Combinatoria 90
Combinao
Exemplo 39 (continuao)
Cada rota pode ser expressa por uma sequncia de Ds e Cs, sendo que existem exatamenten Ds e m Cs, ou seja, cada rota possui n + m passos.
Posies dos movimentos:
. . .1 2 n + m
Observe que se escolhermos as posies para os movimentos Ds as outras posies devemser preenchidas com movimentos Cs e vice-versa. Assim, temos n + m posies a serempreenchidas sendo que n delas com movimentos Ds. Observe que no estamos interessadosnuma dada ordem mas sim no conjunto de posies que iro ter o movimento D. Logo, aquantidade de rotas que satisfaz as restries de movimentos dada por(
n + mn
)=
(n + m)!
n!m!,
que o mesmo valor de (n + mm
)=
(n + m)!
m!n!
se os movimentos Cs forem escolhidos.
UFMG/ICEx/DCC MD Analise Combinatoria 91
Combinao
Exemplo 40 Quantos strings de 8 bits existem que possuem exatamente trsbits 1s?
Posies que os bits 1s podem ser colocados:
1 2 3 4 5 6 7 8
Observe que: No estamos interessados numa ordem. Uma vez escolhido um subconjunto de trs posies contendo bits 1s de um
conjunto de oito posies, as posies restantes devem ter o bit 0. Logo, este problema equivalente a contar o nmero de subconjuntos de trs
posies escolhidos de um conjunto de oito posies.
(83
)=
8!
3! 5! = 56
UFMG/ICEx/DCC MD Analise Combinatoria 92
Combinao
Exemplo 41 Considere formas de ordenar as letras da palavra MISSISSIPPI.Por exemplo:
IIMSSPISSIP ISSSPMIIPIS PIMISSSSIIP
Quantos strings distintos existem?
Posies que as letras podem ser colocadas:
1 2 3 4 5 6 7 8 9 10 11
UFMG/ICEx/DCC MD Analise Combinatoria 93
Combinao
Exemplo 41 Observe que: Este exemplo generaliza o anterior. Cpias de uma mesma letra no podem ser distinguidas. Uma vez escolhidas as posies para uma certa letra, as cpias dessa letra
podem ir em qualquer posio.
Assim, construir uma ordem para as letras pode ser visto como um processoformado de quatro etapas: Escolher um subconjunto de quatro posies para a letra S. Escolher um subconjunto de quatro posies para a letra I. Escolher um subconjunto de duas posies para a letra P. Escolher um subconjunto de uma posio para a letra M.
UFMG/ICEx/DCC MD Analise Combinatoria 94
Combinao
Exemplo 41
Observe que: Existem 11 posies e C(11,4) subconjuntos de quatro posies para a letraS.
Existem sete posies restantes e C(7,4) subconjuntos de quatro posiespara a letra I.
Existem trs posies restantes e C(3,2) subconjuntos de duas posiespara a letra P.
Finalmente, existe apenas uma posio restante para a letra M.
Assim, pelo princpio da multiplicao temos:(114
)(
74
)(
32
)(
11
)=
11!
4!7! 7!4!3!
3!2!1!
1!1!0!
=11!
4! 4! 2! 1! = 34650
UFMG/ICEx/DCC MD Analise Combinatoria 95
Combinao: Teorema
Suponha uma coleo formada por n objetos dos quais: n1 so do tipo 1 e no podem ser distinguidos; n2 so do tipo 2 e no podem ser distinguidos; . . . nk so do tipo k e no podem ser distinguidos;sendo que n1 +n2 + . . .+nk = n. Assim, o nmero de permutaes distintasdos n objetos :(
nn1
)(n n1n2
)(n n1 n2
n3
) . . .
(n n1 n2 . . . nk1
nk
)=
n!
n1! n2! n3! . . . nk!
UFMG/ICEx/DCC MD Analise Combinatoria 96
Combinao com repetio
Quantas formas existem de escolher r elementos sem considerar a ordem deum conjunto de n elementos se repetio permitida?
Estratgia: Considere cada um dos n elementos como uma categoria de objeto do qual
vrias selees podem ser feitos.
Exemplo: suponha um conjunto com os elementos {1,2,3,4}. Se trs ele-mentos devem ser escolhidos, ento podemos ter: [3,3,1], [2,2,1], [1,2,4], . . .
Como a ordem no importa, temos que [3,3,1] = [3,1,3] = [1,3,3].
UFMG/ICEx/DCC MD Analise Combinatoria 97
Combinao com repetio
Definio: Uma combinao de r elementos com repetio permitida, ou mul-ticonjunto de tamanho r, escolhida de um conjunto X de n elementos umaseleo no ordenada de elementos de X com repetio permitida.
Se X = {x1, x2, . . . , xn}, escreve-se uma combinao de r elementos comrepetio permitida, ou multiconjunto de tamanho r, como
[xi1, xi2, . . . , xir]
tal que xij X e algum xij pode ser igual a um outro elemento.
UFMG/ICEx/DCC MD Analise Combinatoria 98
Combinao com repetio
Exemplo 42 Seja o conjunto X com os elementos {1,2,3,4}. Liste todas ascombinaes de 3 elementos com repetio permitida.
[1,1,1] [1,1,2] [1,1,3] [1,1,4] Todas as combinaes que incluem 1,1
[1,2,2] [1,2,3] [1,2,4] Todas as combinaes que incluem 1,2
[1,3,3] [1,3,4] Todas as combinaes que incluem 1,3
[1,4,4] Todas as combinaes que incluem 1,4
[2,2,2] [2,2,3] [2,2,4] Todas as combinaes que incluem 2,2
[2,3,3] [2,3,4] Todas as combinaes que incluem 2,3
[2,4,4] Todas as combinaes que incluem 2,4
[3,3,3] [3,3,4] Todas as combinaes que incluem 3,3
[3,4,4] Todas as combinaes que incluem 3,4
[4,4,4] Todas as combinaes que incluem 4,4
Ou seja, existem 20 combinaes de trs elementos com repetio permitida.
UFMG/ICEx/DCC MD Analise Combinatoria 99
Combinao com repetio
Codificando os resultados de uma combinao de r elementos com repetiopermitida de um conjunto de n elementos.
Algumas combinaes:
Categoria 1 Categoria 2 Categoria 3 Categoria 4 Resultado
| | | [2,4,4] | | | [1,3,4]
| | | [1,1,1]
UFMG/ICEx/DCC MD Analise Combinatoria 100
Combinao com repetio
Cada seleo de n elementos (categorias) pode ser representada por umstring formado pelos smbolos | e . Existem r smbolos e n 1 smbolos |. Resolver o problema de contar o nmero de combinaes de r elementos
com repetio permitida de um conjunto de n elementos equivalente adeterminar o nmero de combinaes de r elementos de um conjunto de(n 1) + r smbolos, ou seja, (
r + n 1r
)
UFMG/ICEx/DCC MD Analise Combinatoria 101
Combinao com repetio
Exemplo 43 Uma pessoa quer comprar 15 latas de refrigerante de cinco mar-cas diferentes. Quantas combinaes de latas podem ser feitas?
Neste caso temos r = 15 e n = 5. Assim temos(r + n 1
r
)=
(15 + 5 1
15
)=
(1915
)=
19!
15! 4! = 3876
UFMG/ICEx/DCC MD Analise Combinatoria 102
Combinao com repetio
Exemplo 44 Considere o mesmo exemplo anterior, mas a pessoa deseja levarpelo menos seis latas do refrigerante Guaran da Amaznia. Quantas combi-naes de latas podem ser feitas?
Observe que: A pessoa precisa escolher mais nove latas das cinco restantes. Em cada combinao, estaro presentes as seis latas de Guaran da Amaz-nia.
Assim, temos r = 9 e n = 5
(r + n 1
r
)=
(9 + 5 1
9
)=
(139
)=
13!
9! 4! = 715
UFMG/ICEx/DCC MD Analise Combinatoria 103
Combinao com repetio
Exemplo 45 Seja n um inteiro positivo. Quantas triplas de inteiros (i, j, k) exis-tem sendo que 1 i j k n?
Observe que: Qualquer tripla de inteiros (i, j, k) com 1 i j k n pode ser represen-
tada por um string de n1 smbolos | j que existem n categorias para seremescolhidas (n nmeros inteiros) e trs smbolos que so os trs nmerosda tripla, e as suas posies indicam quais so esses trs nmeros.
A garantia da restrio 1 i j k n obtida simplesmente fazendouma leitura da esquerda para a direita. Exemplo para n = 5:
Categoria
1 | 2 | 3 | 4 | 5 Resultado
| | | | (1,2,4)| | | | (3,3,5)
UFMG/ICEx/DCC MD Analise Combinatoria 104
Combinao com repetio
Exemplo 45 Assim, o nmero de triplas o mesmo nmero de strings de n1smbolos | e trs smbolos , e dado por:(
3 + (n 1)3
)=
(n + 2
3
)
=(n + 2)!
3! (n + 2 3)!
=(n + 2) (n + 1) n (n 1)!
3! (n 1)!
=n(n + 1)(n + 2)
6
UFMG/ICEx/DCC MD Analise Combinatoria 105
Sumrio
ORDEMSIM NO
SIM nr
n + r 1r
R
EP
ET
I
O
NO P (n, r)
nr
UFMG/ICEx/DCC MD Analise Combinatoria 106
lgebra de combinaes
(nn
)=
n!
n!(n n)! = 1
Um conjunto com n elementos s possui um subconjunto de tamanho n, que ele prprio.
(n0
)=
n!
0!(n 0)! = 1
Um conjunto com n elementos s possui um subconjunto de tamanho 0, que o conjunto vazio.
UFMG/ICEx/DCC MD Analise Combinatoria 107
lgebra de combinaes
(nr
)=
(n
n r), n, r|0 < r n
(nr
)=
n!
r!(n r)!(n
n r)
=n!
(n r)!r!
A quantidade de subconjuntos de tamanho r e de tamanho nr a mesma. Isto significa que cada subconjunto de C(n, r) pode ser associado a cada
subconjunto de C(n, n r). Raciocnio combinatorial onde o resultado obtido contando objetos que so
combinados de formas diferentes. Este raciocnio diferente de uma provaalgbrica.
UFMG/ICEx/DCC MD Analise Combinatoria 108
Frmula de Pascal
(n + 1r
)=
(n
r 1)
+
(nr
)onde, 0 < r n.
UFMG/ICEx/DCC MD Analise Combinatoria 109
Frmula de Pascal(
nr 1
)+
(nr
)=
n!
(r 1)!(n r + 1)! +n!
r!(n r)!
=n![r!(n r)!] + n![(r 1)!(n r + 1)!]
r!(n r + 1)!(r 1)!(n r)!
=n!r!(n r)! + n!(r 1)!(n r + 1)!
r!(n r + 1)!(r 1)!(n r)!
=n!r(r 1)!(n r)! + n!(r 1)!(n r + 1)(n r)!
r!(n r + 1)!(r 1)!(n r)!
=n!r + n!(n r + 1)
r!(n r + 1)!
=n!(r + n r + 1)r!(n r + 1)!
=n!(n + 1)
r!(n r + 1)!
=(n + 1)!
r!(n r + 1)!
=
(n + 1r
)UFMG/ICEx/DCC MD Analise Combinatoria 110
Frmula de PascalOutra estratgia de correo
Frmula de Pascal: (nr
)=
(n 1r
)+
(n 1r 1
).
Obviamente temos que(n 1r
)+
(n 1r 1
)=
(n 1)!(n 1 r)!r! +
(n 1)!(n 1 (r 1))!(r 1)!.
Ao invs de multiplicar cada frao pelo denominador da outra, existe um caminho mais fcil:
multiplicar o numerador e o denominador da primeira por (n r), e da segunda por r. Os doisdenominadores resultam em (n r)!r!, e a soma dos numeradores torna-se mais fcil.
UFMG/ICEx/DCC MD Analise Combinatoria 111