Análise Combinatória para
professores do Ensino Médio
José Plı́nio de O. Santos1
Instituto de Matemática, Estatı́stica e Comp. Cientı́fica - IMECC
Universidade Estadual de Campinas - UNICAMP
Robson da Silva2
Centro de Matemática, Computação e Cognição - CMCC
Universidade Federal do ABC - UFABC
1
2
[email protected]
[email protected]
Conteúdo
1 Permutação, Arranjo e Combinação
5
2 Permutação com repetições
11
3 Permutações circulares
15
4 Exercı́cios
17
5 Respostas dos exercı́cios
19
Bibliografia
20
2
Apresentação
Nosso objetivo ao escrever este texto é o de apresentar o que consta do programa de Análise Combinatória do segundo grau em uma linguagem informal
mas sem deixar a precisão em segundo plano. Acreditamos que esta abordagem ajudará bastante os professores de matemática na tarefa de ensinar
esta disciplina que, infelizmente, não tem sido dada ou, quando ministrada,
reduz-se a algumas fórmulas decoradas sem o devido entendimento.
Utilizaremos um grande número de exemplos concretos na introdução de
cada conceito novo.
3
4
1
Permutação, Arranjo e Combinação
Nosso primeiro problema será o de calcularmos o número de diferentes
maneiras que podemos colocar n pessoas em fila. Claramente estamos considerando as pessoas como diferentes objetos. Vamos, inicialmente, tomar
n = 3 e listar todas as possı́veis filas que podemos formar com estas três
pessoas, que vamos chamar de a, b e c. A tabela abaixo apresenta as seis
diferentes filas que podemos formar neste caso.
abc
acb
bac
bca
cab
cba
Tabela 1: Possı́veis filas com três pessoas
Veja que, ao falarmos em filas, a pergunta “em que posição uma dada
pessoa se encontra?” faz sentido. Observe que a pessoa a é a primeira
em duas filas, é a segunda em duas filas e é a terceira, também, em duas
filas. Estas afirmações valem também para as outras duas letras (pessoas).
Aqui estamos em uma democracia plena. Todos têm exatamente os mesmos
direitos.
É claro que tendo apenas uma pessoa o número de filas é igual a 1 e,
ainda, no caso de duas pessoas este número é igual a 2. Listamos abaixo
estes dois casos.
a
ab
ba
Tabela 2: Possı́veis filas com uma e com duas pessoas
O número de filas com três pessoas é 3 vezes o número de filas com duas
pessoas. Isto é verdade pelo simples fato de que a terceira pessoa, c, pode ser
5
introduzida na fila ab em três posições distintas: depois de ab, isto é, no final
da fila, gerando abc; entre as duas, resultando em acb; como primeira da fila,
gerando cab. Ao introduzirmos a nova pessoa c na outra fila ba vamos obter,
pelas mesmas razões, três novas filas que são: bac, bca, cba.
O número de diferentes filas com quatro pessoas é igual a 24 que é 4 vezes
o número de filas com três pessoas, que já vimos ser igual a 6 = 3 × 2. A
justificativa é a mesma usada na mudança de duas para três pessoas. Agora
como estamos introduzindo uma quarta pessoa, denotada por d, esta pode
ser colocada, em cada fila com três pessoas, em quatro posições diferentes:
em primeiro lugar, em segundo, em terceiro ou em último. Na tabela abaixo
temos as 24 filas distintas.
abcd
abdc
adbc
dabc
acbd
acdb
adcb
dacb
bacd
badc
bdac
dbac
bcad
bcda
bdca
dbca
cabd
cadb
cdab
dcab
cbad
cbda
cdba
dcba
Tabela 3: Possı́veis filas com quatro pessoas
Este simples argumento nos permite concluir que, no caso de n pessoas,
o total de diferentes filas é igual a n! (lê-se n fatorial) que é a notação usada
para o produto dos primeiros n inteiros positivos, isto é,
n! = n × (n − 1) × (n − 2) × · · · × 3 × 2 × 1.
Dizemos que n! é o número de permutações de n objetos distintos, isto
é, o número de filas distintas que podemos formar com n objetos diferentes.
Vamos denotar este número por Pn , ou seja, Pn = n!.
Estas diferentes filas que chamamos de permutações podem ser vistas
como funções. Vejamos como. Consideremos o caso n = 4, isto é, quatro
pessoas a, b, c e d. Na fila bacd temos que a primeira letra é b, a segunda a,
a terceira c e a última d. Podemos escrever isto da seguinte forma
6
1 2 3 4
↓ ↓ ↓ ↓
b a c d
aqui como o c é a imagem do 3, isto significa que ele é o terceiro da fila.
Observações semelhantes valem, claramente, para as demais letras (pessoas).
Agora que sabemos contar de quantas maneiras diferentes podemos ordenar (colocar em fila) n objetos distintos (que é n!), vamos responder a
uma outra pergunta, cuja resposta inclui, como caso particular, a questão
resolvida acima.
Consideremos o seguinte conjunto com quatro objetos distintos {a, b, c, d}.
A pergunta agora é a seguinte: de quantas maneiras diferentes podemos
retirar dois objetos colocando-os em fila? Como para o primeiro da fila temos
4 condidatos, restam apenas 3 possı́veis ocupantes para a segunda posição.
Logo, 4 × 3 = 12 é a resposta à nossa pergunta. Listamos a seguir todas
estas doze filas.
ab
ba
ac
ca
ad
da
bc
cb
bd
db
cd
dc
Tabela 4: As doze possı́veis filas
Se o número total de objetos for n e desejarmos retirar r (r ≤ n) objetos
para formarmos filas, temos que escolher um objeto para ocupar o primeiro
lugar (são n possibilidades), para o segundo lugar nos restam n−1 candidatos,
n − 2 para o terceiro, ..., e finalmente n − (r − 1) = n − r + 1 para a r-ésima
posição. Assim, temos n × (n − 1) × (n − 2) × · · · × (n − r + 1) possı́veis filas
diferentes contendo r elementos escolhidos dentre os n do nosso conjunto.
A este número chamamos arranjo de n objetos r a r, o qual vamos denotar
por Arn . Como
n × (n − 1) × (n − 2) × · · · × (n − (r − 1))
n × (n − 1) × · · · × (n − (r − 1)) × (n − r) × · · · × 3 × 2 × 1
=
(n − r) × (n − r − 1) × · · · × 3 × 2 × 1
n × (n − 1) × (n − 2) × · · · × (n − (r − 1)) × (n − r)!
=
(n − r)!
n!
=
,
(n − r)!
7
então
n!
(1)
(n − r)!
Observemos que no caso r = n, ou seja, se desejamos tomar todas os
indivı́duos para formarmos filas, a resposta será Ann = n!. Portanto, a permutação é um caso particular de arranjo.
n!
= Pn , donde conAo substituirmos r por n em (1), obtemos Ann =
0!
cluı́mos ser conveniente definir 0! = 1.
Arn =
Vamos agora responder algumas simples questões que ilustram os conceitos de permutação e arranjo vistos até aqui.
Numa prateleira de uma estante onde cabem pelo menos 20 livros
gostarı́amos de colocar 15 livros, todos distintos, sendo 6 de Matemática,
6 de Fı́sica e 3 de Português. Não havendo nenhuma restrição a resposta
seria simplesmente 15!. Caso os livros de mesma disciplina devam estar juntos a resposta seria 6!6!3!3!. Se apenas os de Matemática tivessem que estar
juntos, terı́amos 6!10! possibilidades. Se os 3 livros de português ocupassem os primeiros 3 lugares, estando os de Matemática e Fı́sica intercalados,
terı́amos 3!6!6!2!. Caso queiramos escolher 3 livros de Matemática dentre os
6 e 3 livros de Fı́sica dentre os 6 para colocarmos todos em fila juntamente
com os 3 de português a resposta não seria A36 A36 3!. Procure justificar onde
esta o erro. Qual seria a pergunta que teria como resposta correta o número
dado acima?3
Tendo visto as definições de Arranjo e de Permutação, vamos introduzir
o conceito de Combinação que, como veremos, pode ser expresso em termos
dos dois primeiros.
Gostarı́amos de contar quantos são os subconjuntos de {a, b, c, d} contendo exatamente 2 elementos. Vamos chamar este número de combinação
de 4 objetos tomados 2 a 2 e o denotaremos por 42 . A lista de todos estes
conjuntos é apresentada na Tabela 5 abaixo.
{a, b}
{a, c}
{a, d}
{b, c}
{b, d}
{c, d}
Tabela 5: Os 6 possı́veis conjuntos
3
resposta na Seção Respostas dos Exercı́cios ao final deste texto
8
No caso geral, nr denota, portanto, o número de subconjuntos contendo
r elementos que um conjunto com n elementos possui.
Sabemos que o arranjo de n objetos r a r conta todas as maneiras de
tirarmos r elementos colocando-os em fila e que combinação de n objetos
r a r não leva em consideração a ordem mas apenas a natureza dos elementos retirados. Logo (veja a Tabela 6 a seguir) para obtermos Arn basta
multiplicarmos nr por r!, isto é,
n
n!
r! = Arn =
,
r
(n − r)!
donde obtemos
n
Ar
n!
= n =
.
r
r!
r!(n − r)!
4
2
4
2
(2)
=6
ab
ac
ad
bc
bd
cd
2! = A24
ab, ba
ac, ca
ad, da
bc, cb
bd, db
cd, dc
Tabela 6: Um exemplo de que
n
r
r! = Arn
Uma propriedade importante verificada pela fórmula de combinação,
supondo r ≤ n, é a seguinte:
n
n
=
.
(3)
r
n−r
Uma maneira de se provar (3) é pela simples substituição na fórmula dada
por (2):
n!
n!
n
n
n!
=
=
=
.
=
r!(n − r)!
(n − r)!(n − (n − r))!
(n − r)!r!
n−r
r
Esta demonstração, embora correta, não requer o uso da definição de
combinação como sendo o número de subconjuntos contendo r elementos
que um conjunto com n elementos possui. Vamos, pois, demonstrar (3)
9
novamente, mas agora sem fazer uso da fórmula dada por (2). Cada vez que
retiramos r elementos, n − r são deixados e, portanto, (3) está provada. A
tabela abaixo ilustra isto no caso n = 5 e r = 2. A mesma tabela ilustra,
também, o caso n = 5 e r = 3 (basta trocar “retirar” por “deixar”). É,
portanto, apenas uma questão de referencial.
retirar deixar
ab
cde
ac
bde
ad
bce
ae
bcd
bc
ade
bd
ace
be
acd
cd
abe
ce
abd
de
abc
Tabela 7: Um exemplo de que
n
r
=
n
n−r
Vamos resumir o que foi feito até agora:
Pn = n!
n!
,r ≤ n
Arn =
(n −r r)!
n!
n
A
= n =
, r ≤ n.
r!
r!(n − r)!
r
Antes de considerarmos coleções de objetos onde repetições são permitidas, vamos demonstrar uma importante e conhecida relação utilizando apenas argumentos combinatórios:
n
n−1
n−1
=
+
.
r
r
r−1
Sabemos que nr conta quantos são os subconjuntos com r elementos que
um conjunto com n elementos possui. Como cada elementos do conjunto
aparece exatamente o mesmo número de vezes na tabela das combinações de
n objetos r a r, podemos escolher um elemento qualquer e contar o número
10
de subconjuntos nos quais ele não está presente, que é n−1
, e somar
com o
r
n−1
número daqueles em que este elementos está presente, que é r−1 .
Consideremos o conjunto {a, b, c, d, e}. As combinações destas cinco letras
três a três estão listadas abaixo.
cde
bde
bce
bcd
ade
ace
acd
abe
abd
abc
Tabela 8: Combinações de a, b, c, d e e três a três
Como sabemos, cada letra aparece exatamente o mesmo número de vezes
na tabela acima. Consideremos a letra d. Claramente, dado um subconjunto
ou d pertence a este subconjunto ou não pertence. Vamos contar, primeiramente, a quantos subconjuntos a letra d não pertence.
Como
o subconjunto
5−1
4
deve ter três elementos (r no caso geral), então 3 = 3 = 4 ( n−1
no caso
r
geral) é o número de subconjuntos nos quais
a letra d não aparece. Aque5−1
les em que d esta presente são 3−1
= 42 = 6 ( n−1
no caso geral), pois
r−1
devemos retirar dois (r − 1 no caso geral) elementos para completarmos, juntamente com o elemento d os três (r no caso geral) elementos
do
subconjunto
5
4
4
considerado. Neste caso particular temos 10 = 3 = 3 + 2 = 4 + 6.
2
Permutação com repetições
Vamos estudar agora as permutações com repetições. Isto significa que
queremos colocar em fila objetos que não são necessariamente todos distintos. Para ilustrarmos a idéia, consideremos um exemplo com apenas quatro
elementos aabc, isto é, duas cópias da letra a, uma da letra b e uma da letra c.
Sabemos que o total de filas distintas com quatro objetos distintos é igual a
4! = 24. Inicialmente, vamos supor que as duas letras a são distintas. Vamos
chamá-las de a1 e a2 . Assim, temos quatro objetos distintos: a1 , a2 , b e c.
Na Tabela 9 estão listadas as 24 permutações (filas) que podemos construir com estes quatro (temporariamente distintos) objetos.
11
a1 a2 bc
a1 a2 cb
a1 ba2 c
a1 bca2
a1 cba2
a1 ca2 b
ca1 a2 b
ba1 a2 c
ba1 ca2
ca1 ba2
cba1 a2
bca1 a2
a2 a1 bc
a2 a1 cb
a2 ba1 c
a2 bca1
a2 cba1
a2 ca1 b
ca2 a1 b
ba2 a1 c
ba2 ca1
ca2 ba1
cba2 a1
bca2 a1
Tabela 9: As 24 possı́veis filas
Listamos a tabela de forma a destacar o fato de que a diferença entre a
primeira e a segunda colunas é apenas pela troca (permutação) das letras
a1 e a2 . Como, na realidade, a1 = a2 , as filas a1 a2 bc e a2 a1 bc são iguais.
Isto se aplica a todas as outras linhas da Tabela 9, o que nos mostra que a
resposta correta é 12, que é igual a 24 = 4! dividido por 2!. Logo, o número
4!
= 24
= 12.
de permutações das quatro letras aabc é igual a 2!
2
Se tivéssemos com as seis letras aaabbc, o total de filas distintas seria
6!
= 60, pelo mesmo argumento apresentado acima, isto é, poderı́amos
3!2!1!
supor serem todas distintas a1 a2 a3 b1 b2 c e terı́amos, por exemplo, do total de
6! = 720, as seguintes filas onde apenas as letras a1 a2 a3 são permutadas:
a1 a2 b1 cb2 a3
a1 a3 b1 cb2 a2
a2 a1 b1 cb2 a3
a2 a3 b1 cb2 a1
a3 a1 b1 cb2 a2
a3 a2 b1 cb2 a1
Tabela 10: 6 das 720 filas possı́veis
Como a1 = a2 = a3 = a, todas estas filas são iguais, o que mostra a
necessidade de dividir 6! por 3!. De forma análoga, temos que dividir por 2!
devido as duas cópias da letra b.
12
No caso geral, em que se tem n1 cópias de a1 , n2 cópias de a2 , ..., nr
cópias de ar , o total de permutações com repetições é dado por
n!
,
n1 !n2 ! · · · nr !
(4)
onde n1 + n2 + · · · + nr = n.
Observe que permutação simples, isto é, sem repetição, é um caso particular da fórmula (4) acima onde n1 = n2 = · · · = nr = 1.
Algo já visto anteriormente também é caso particular da fórmula (4)
acima. Trata-se de combinação simples. Como demonstramos, o número de
combinações de n objetos tomados r a r é dado por
n
n!
=
r
r!(n − r)!
e isto é, claramente, um caso particular de (4) ao tomarmos n1 = r e n2 =
n − r.
Vejamos um exemplo numérico simples para ilustrar este importante fato.
Gostarı́amos de escolher dentre cinco pessoas (distintas, é claro) duas para
participarem de um comissão. Sabemos que este número é dado por 52 =
5!
5!
= 2!3!
= 10. Este é, também, o número de filas distintas que podemos
2!(5−2)!
formar com as letras aaabb. Na Tabela 11 listamos todas estas filas.
aaabb
aabab
abaab
baaab
aabba
ababa
baaba
abbaa
babaa
bbaaa
Tabela 11: As 10 filas distintas com as letras aaabb
Observe que para caracterizarmos uma fila basta que escolhamos
as posições
5
5
das duas letras b. Ou as posições das letras a, afinal 2 = 3 , como já foi
visto. Disto concluı́mos que combinação simples é um caso particular muito
especial das permutação com repetições.
13
Vamos discutir agora problemas que podem ser resolvidos com o que
vimos até aqui.
Consideremos duas salas distintas, Sala 1 e Sala 2, e quatro pessoas a, b, c
e d. De quantas maneiras diferentes podemos colocar duas pessoas em cada
sala? Quando escolhemos duas pessoas para colocarmos na Sala 1, as duas
restantes necessariamente irão para a Sala 2. Na Tabela 12 abaixo temos
listadas todas as possibilidades.
Sala 1
ab
ac
ad
bc
bd
cd
Sala 2
cd
bd
bc
ad
ac
ab
Tabela 12: As possı́veis ocupações das duas salas
Como pode ser visto, na coluna da Sala 1 estão todas as combinações
de 4, 2 a 2. Na segunda coluna, temos exatamente a mesma
lista na ordem
4
inversa. A resposta para nossa questão é, portanto, 6 = 2 .
Vejamos agora uma outra questão relativa a estas mesmas quatro pessoas a, b, c e d. De quantas maneiras distintas podemos separá-las em dois
conjuntos com duas pessoas em cada?
Uma simples observação na Tabela 12 nos permite concluir que a resposta
agora é 3, pois a diferença entre a primeira e a última linhas é apenas na
ordem dos conjuntos {a, b} e {c, d}. A mesma observação é válida para as
linhas 2 e 5 e, ainda, para as linhas 3 e 4. Disto podemos concluir que a
4!
= 21 6 = 3.
resposta é 12 42 = 21 2!2!
4
Assim, 2 é o número de subconjuntos formados por dois elementos que
um conjunto com quatro elementos possui e é, também, o número de maneiras
de separarmos estes quatro elementos em dois grupos, com dois em cada
um, onde a ordem destes grupos importa. Caso as salas sejam idênticas, a
resposta, como vimos, é 3, pois neste caso estamos interessados em saber
“quem está junto com quem” e não onde um par de elementos está.
Continuando com esta mesma linha de raciocı́nio, vamos resolver outra
questão semelhante. Considerando agora três salas distintas e as seis pessoas
14
a, b, c, d, e e f , de quantas maneiras diferentes podemos colocar duas em cada
sala?
Temos 62 maneiras para a escolha das duas que irão para a Sala 1.
Devemos agora escolher duas
dentre as quatra restantes para ocupar a Sala
2, o que pode ser feito de 42 maneiras. Logo, a resposta correta é
6
4
2
6! 4! 2!
6!
×
×
=
=
= 90.
(5)
2
2
2
2!4! 2!2! 2!0!
2!2!2!
Note que, também neste caso, temos uma permutação com repetições.
Considere agora a seguinte questão envolvendo as mesmas seis pessoas
a, b, c, d, e e f acima: de quantas maneiras podemos separá-las em três pares,
isto é, em duplas para disputarem a primeira rodada de um torneio de tênis?
A resposta agora é o número dado por (5) dividido por 3! = 6.
Observe as seguintes distribuições em salas distintas das pessoas a, b, c, d, e
e f na Tabela 13.
Sala 1
ac
ac
ef
ef
bd
bd
Sala 2
ef
bd
ac
bd
ef
ac
Sala 3
bd
ef
bd
ac
ac
ef
Tabela 13: Seis possı́veis ocupações das salas por a, b, c, d, e, f
Claramente, as seis ocupações listadas na Tabela 13 são todas distintas. Caso
estejamos interessados apenas na formação de pares, cada uma das linhas
desta tabela fornecerá exatamente a mesma configuração, isto é, que os pares
são ac, bd e ef . Por isto a necessidade de dividirmos por 3!.
3
Permutações circulares
Inicialmente vamos falar a respeito da diferença entre as permutações já
vistas e as que chamamos permutações circulares. Vimos que a número de
maneiras de colocarmos em fila n pessoas (n objetos distintos) é igual a Pn =
15
n!. Vamos tomar n = 4 para ilustrarmos, não apenas a diferença entre os dois
conceitos, mas também como se calcula o número de permutações circulares
de n. Na Tabela 4 listamos as 24 = 4! filas distintas que podemos formar
com 4 pessoas a, b, c, d. Quando temos pessoas em fila podemos perguntar
quem ocupa o primeiro lugar, quem ocupa o segundo e assim por diante. Já
no caso em que as pessoas estão de mãos dadas, formando uma roda, esta
mesma pergunta não faz sentido. Vamos explicar uma forma de se contar o
total das permutações circulares a partir das filas, isto é, das permutações
não circulares. Claramente se tomarmos uma fila e pedirmos para que a
primeira pessoa da fila dê a mão à última formaremos uma roda que estamos
considerando como permutação circular. Quando as pessoas estão de mãos
dadas o que se pode perguntar sobre uma dada pessoa é, por exemplo, quem
são seus vizinhos mas não se ela ocupa uma dada posição no sentido de ser
a primeira ou a segunda, etc.
Vamos, agora, iniciar a formação de rodas transformando uma fila em
uma roda pedindo para que o primeiro da fila dê a mão ao último. Como
estamos lidando com pessoas e devemos ser precisos vamos convencionar que
todos deverão ficar “olhando” para o interior da roda. Iniciemos com a fila
abcd.
a
b
a
c
d
d
c
d
c
b
c
a
b
b
d
a
Consideramos iguais duas rodas quando elas diferem apenas por uma
rotação. Com esta convenção as quatro rodas da figura acima são idênticas.
É fácil observar que nenhuma outra fila, além destas quatro, dará origem a
esta roda com a operação que realizamos (ligação do primeiro com o último).
Mantendo nossa preocupação com a precisão não estamos esperando que as
pessoas brinquem de roda de cabeça para baixo.4
As quatro filas que originam esta mesma roda são: abcd, dabc, cdab e
bcda. Vejamos o que elas têm em comum. O que se observa é que cada
uma pode ser obtida da anterior ao se retirar o último elemento e colocá-lo
no inı́cio da fila. Logo estas quatro diferentes filas nos fornecem a mesma
roda. Se tomarmos qualquer fila fora do conjunto formado por estas quatro
poderemos repetir o que fizemos obtendo outro conjunto de quatro filas que
irá gerar uma roda diferente da anterior. Procedendo desta maneira iremos
4
isto é importante porque não precisamos considerar, em cada roda, duas possı́veis
posições para cada pessoa
16
separar o conjunto das 24 filas em 6 grupos de 4 filas, cada um dos quais,
gerando uma roda. Logo o 6 foi obtido da divisão de 24 por 4. Isto é de 4!
por 4. Este simples argumento nos permite dizer que, no caso geral, teremos
(n − 1)! rodas (permutações circulares distintas) com os n objetos distintos.
Este número, que denotamos por (P C)n , é, pois, dado por:
(P C)n =
4
n!
n(n − 1)!
Pn
=
=
= (n − 1)!.
n
n
n
Exercı́cios
1. De quantas maneiras podemos colocar em fila 10 homens e 10 mulheres
sendo que os homens devem estar juntos numa ordem qualquer?
2. De quantas maneiras podemos formar comissões com 5 homens e 3
mulheres de um total de 8 homens e 12 mulheres?
3. Uma comissão julgadora é formada por 4 matemáticos e 3 fı́sicos. De
quantas maneiras eles podem sentar-se em fila, se:
(a) os matemáticos sentam-se juntos e os fı́sicos também?
(b) somente os matemáticos sentam-se juntos?
4. De quantas maneiras podemos separar 12 pessoas em dois grupos de 6
pessoas cada?
5. De quantas maneiras podemos separar 12 pessoas em três grupos de 4
pessoas cada?
6. De quantas maneiras podemos separar 12 pessoas em dois grupos de 2
pessoas e dois grupos de 4?
7. De quantas maneiras podemos separar 12 pessoas em dois grupos sendo
um de 7 pessoas e o outro de 5?
8. No Problema 1 quantas são as filas nas quais não existam duas mulheres
vizinhas?
9. No Problema 2, considerando-se que João é um dos homens e Maria
uma das mulheres, quantas são as comissões das quais Maria faz parte
sem o João?
17
10. De quantas maneiras distintas podemos distribuir 18 objetos distintos
em três caixas distintas com a restrição de que cada caixa tenha 6
objetos?
11. Considere 4 bolas vermelhas idênticas, 4 bolas verdes idênticas e 4 bolas
amarelas idênticas. De quantas maneiras podemos coloca-las em fila?
12. Que relação existe entre os Problemas 5 e 11?
13. Considere um grupo de 8 casais. De quantas maneiras podemos colocar
estas 16 pessoas em fila de forma que marido e mulher estejam juntos?
14. Qual a resposta ao problema anterior caso os casais sejam colocados ao
redor de uma mesa circular com exatamente 16 cadeiras idênticas?
15. E se as cadeiras no problema anterior forem distintas?
16. Considere dois dados de cores distintas. Quando jogamos os dois quantos são os possı́veis resultados?
17. No problema anterior quantas são as possibilidades de se obter soma
9?
18. De quantas maneiras podemos colocar 8 torres idênticas em um tabuleiro de xadrez de modo que elas estejam em linhas distintas e colunas
distintas?
19. 12 pessoas vão disputar um campeonato de xadrez. De quantas maneiras podemos separá-las em seis duplas para a primeira rodada?
20. Sendo João e Maria duas dentre as 12 pessoas do problema anterior
qual a probabilidade de que eles formem um par na primeira rodada?
21. De quantas maneiras podemos distribuir 24 livros diferentes entre 5
alunos se 2 deles recebem 6 livros e os outros 3 recebem 4 livros cada?
22. De quantas maneiras podemos retirar sucessivamente 2 cartas de um
baralho de 52 cartas de modo que:
(a) a primeira carta é um ás e a segunda carta não é uma rainda?
(b) a primeira carta é de espadas e a segunda não é uma rainda?
23. Quantos são os jogos de um campeonato disputado por 16 equipes de
vôlei se todas se enfrentam 2 vezes?
24. De quantas maneiras podemos comprar 18 sorvetes, cada um de um
único sabor, numa sorveteria que tem apenas 4 sabores distintos?
18
5
Respostas dos exercı́cios
8 12
1. 11!10! 2.
= 12320 3. (a) 4!3!2! = 288 (b) 4!4! = 576
5
3
12!
12!
12!
12!
4.
= 792
= 462 5.
= 5775 6. 4
= 51975 7.
2
3
2
2(6!)
2 (4!)
7!5!
3!(4!)
11 7
18!
12!
8. 2(10!)2 9.
= 1155 10.
=
17153136
11.
= 34650
2
5
(6!)3
(4!)3
13. 28 8! = 10321920 14. 28 7! = 1290240 15. 28 8! = 10321920 16. 36 17.
12!
12
24!
4 18. 8! = 40320 19. 6 = 46080 20.
21.
22. (a) 188
2 6!
132
(6!)2 (4!)3
(b) 612 23. 240 24. 1330
Resposta a pergunta deixada na página 7: Uma possı́vel pergunta seria: De
quantas maneiras podemos escolher 3 livros de Matemática dentre os 6, 3 de
Fı́sica dentre os 6 para colocarmos em fila, juntamente com os 3 de Português,
sendo que os 3 primeiros seriam de Matemática, os 3 seguintes de Fı́sica e os
3 últimos de Português?
19
Referências
[1] Andrews, G. E., Erikson, K.; Integer Partition, Cambridge University
Press. Cambridge, 2004.
[2] Andrews, G. E.; The theory of partitions, Encyclopedia of Mathematics and Its Applications (Rota Editor), Vol. 2, G.-C., Addison-Wesley,
Reading, 1976.
[3] Andrews, G. E., Askey, R., Roy, R.; Special Functions, Vol. 71, Cambridge University Press, 1999.
[4] Loher, N. A.; Bijective Combinatorics, Discrete Mathematics and its
applications, CRC Press, 2011.
[5] MacMahon, P. A.; Combinatorial Analysis, 2 v., Chelsea Publisinhg,
1960.
[6] Niven, I.; Formal Power Series, The American Mathematical Monthly,
Vol. 76, No 8, p. 871-889, 1969.
[7] Santos, J. P. O.; Introdução à Teoria dos Números, Coleção Matemática
Universitária, IMPA, Rio de Janeiro, 2009.
[8] Santos, J. P. O., Estrada, E.L.; Problemas Resolvidos de Combinatória,
Segunda Ed., Editora Ciência Moderna, Rio de Janeiro, 2011.
[9] Santos, J. P. O., Mello, M.P., Murari, I.T.C.; Introdução à Análise Combinatória, Editora Ciência Moderna, Rio de Janeiro, 2007.
[10] Slomson, A.; An Introduction to Combinatorics, Chapman and Hall,
London, 1991.
[11] Stanley, R. P.; Enumerative Combinatorics, Cambridge University
Press, Cambridge, Vol. 1, 1997.
[12] Stanley, R. P.; Enumerative Combinatorics, Cambridge University
Press, Cambridge, Vol. 2, 1999.
20