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