Exercícios Matemática Discreta Rosen Contagem

CAPÍTULO 5 Contagem Combinatória o estudo dos arranjos dos objetos é uma parte importante da matemática discreta Este assunto vem sendo estudado desde muitos anos antes do século XVII quando questões combinatórias apareceram no estudo de jogos A enumeração contagem de objetos com certas propriedades é uma parte importante da combinatória Devemos contar os objetos para resolver muitos tipos diferentes de problemas Por exemplo a contagem é usada para determinar a complexidade de algoritmos Ela também é exigida para determinar se há números de telefone ou endereços de protocolo da Internet suficientes para atender a demanda Além disso técnicas de contagem são extremamente usadas quando as probabilidades de eventos são computadas As regras básicas de contagem que serão estudadas na Seção 51 podem resolver diversos problemas Por exemplo podemos usar essas regras para enumerar os diferentes números de telefone possíveis nos Estados Unidos as senhas permitidas em um sistema computacional e as diferentes ordens nas quais os atletas podem terminar uma corrida Outro importante instrumento combinatório é o princípio da casa dos pombos que será estudado na Seção 52 Esse princípio afirma que quando os objetos são colocados em caixas e há mais objetos do que caixas então há uma caixa que terá pelo menos 2 objetos Por exemplo podemos usar esse princípio para mostrar que no meio de um grupo de 15 estudantes ou mais pelo menos 3 nasceram no mesmo dia da semana Podemos descrever muitos problemas de contagem em termos de arranjos com ou sem ordenação de objetos de um conjunto Esses arranjos chamados de permutação e combinação são usados em muitos problemas de contagem Por exemplo suponha que os 100 finalistas de uma competição com 2000 estudantes foram convidados para um jantar Podemos contar os grupos possíveis dos 100 estudantes que serão convidados assim como o modo como os 10 primeiros podem ser premiados Outro problema de contagem envolve a criação de todos os arranjos de um tipo específico Isto é freqüentemente usado em simulações computacionais Imaginaremos algoritmos para gerar arranjos de diferentes tipos 51 As Bases da Contagem Introdução Suponha que a senha de um sistema computacional possua seis sete ou oito caracteres Cada um desses caracteres deve ser um número ou uma letra do alfabeto Cada senha deve conter no mínimo um número Quantas senhas são possíveis As técnicas necessárias para responder a essa pergunta e a vários outros problemas de contagem serão introduzidas nesta seção Os problemas de contagem aparecem em matemática e ciência da computação Por exemplo devemos contar as possibilidades favoráveis de um experimento e o total de possibilidades desse experimento para determinar a probabilidade dos eventos discretos Precisamos contar o número de operações usado por um algoritmo para estudar seu tempo de complexidade Introduziremos as técnicas básicas de contagem nesta seção Estes métodos servem como base para quase todas as técnicas de contagem Princípios Básicos de Contagem Apresentaremos dois princípios básicos de contagem a regra do produto e a regra da soma Depois mostraremos como elas podem ser usadas para resolver diferentes problemas de contagem A regra do produto aplicase quando o procedimento é feito a partir de tarefas separadas REGRA DO PRODUTO Suponha que um procedimento possa ser dividido em uma sequência de duas tarefas Se houver n1 formas de fazer a primeira tarefa e para cada uma dessas formas de fazer a primeira tarefa há n2 formas de fazer a segunda tarefa então há n1n2 formas de concluir o procedimento Os exemplos de 1 a 10 mostram como a regra do produto é usada EXEMPLO 1 Uma nova companhia com apenas dois empregados Sanchez e Patel aluga um andar de um prédio com 12 salas Quantas formas diferentes há para designar as diferentes salas para esses dois empregados Solução O procedimento de distribuir as salas para os dois empregados consiste em atribuir uma sala para Sanchez o que pode ser feito de 12 formas e então atribuir uma sala a Patel diferente da de Sanchez o que pode ser feito de 11 formas Pela regra do produto há 12 11 132 formas de distribuir salas a esses dois empregados EXEMPLO 2 As cadeiras de um auditório devem ser etiquetadas com uma letra e um número inteiro positivo que não exceda a 100 Qual é o maior número de cadeiras que podem ser etiquetadas de maneira diferente Solução O procedimento de etiquetar uma cadeira consiste em duas tarefas atribuir uma das 26 letras e depois atribuir um dos 100 possíveis números inteiros A regra do produto mostra que há 26 100 2 600 formas diferentes de etiquetar as cadeiras Assim o maior número de cadeiras que podem ser etiquetadas é 2 600 EXEMPLO 3 Há 32 computadores em um centro computacional Cada computador tem 24 portas Quantas portas diferentes para um computador existem no centro Solução O procedimento de escolher uma porta consiste em duas tarefas primeiro escolher um computador e depois escolher a porta nesse computador Tendo 32 possibilidades para a escolha do computador e 24 possibilidades para a escolha da porta não importando qual computador foi escolhido a regra do produto mostra que há 32 24 768 portas Uma versão expandida da regra do produto é muito útil Suponha que um procedimento é desenvolvido a partir da realização das tarefas T1 T2 Tm em sequência Se cada tarefa Ti i 1 2 n pode ser feita de ni formas não importando como as tarefas anteriores tenham sido realizadas então há n1 n2 nm formas de realizar o procedimento Esta versão da regra do produto pode ser demonstrada pela indução matemática da regra do produto para duas tarefas veja o Exercício 60 no final da seção EXEMPLO 4 Quantas sequências de bits com comprimento sete existem Solução Cada um dos sete bits pode ser escolhido de duas formas porque cada bit equivale a 0 ou 1 Assim a regra do produto mostra que há no total 27 128 diferentes sequências de bits de comprimento sete EXEMPLO 5 Quantas placas de identificação estão disponíveis se cada placa contém uma sequência de três letras seguidas de três números e não são proibidas quaisquer sequências de letras mesmo se elas forem obscenas 26 escolhas para cada letra 10 escolhas para cada número Solução Há 26 escolhas para cada uma das três letras e 10 escolhas para cada um dos três números Pela regra do produto há um total de 26 26 26 10 10 10 17 576 000 possibilidades de placas de identificação EXEMPLO 6 Contando Funções Quantas funções existem partindose de um conjunto com m elementos para um conjunto com n elementos Solução Uma função corresponde a uma escolha de um dos n elementos no contradomínio para cada um dos m elementos no domínio Portanto pela regra do produto há n n n nm funções partindose de um conjunto com m elementos para um com n elementos Por exemplo há 53 funções diferentes partindose de um conjunto com três elementos para um conjunto com cinco elementos EXEMPLO 7 Contando Funções Injetoras Quantas funções injetoras há partindose de um conjunto com m elementos para um com n elementos Solução Primeiro note que quando m n não há funções injetoras ao se partir de um conjunto com m elementos para um com n elementos Agora considere que m n Suponha que os elementos no domínio são a1 a2 am Há n formas de escolher o valor da função em a1 Devido a função ser injetora o valor da função em a2 pode ser escolhido de n 1 formas porque o valor usado em a1 não pode ser usado novamente Geralmente o valor da função em ak pode ser escolhido de n k 1 formas Pela regra do produto há nn 1n 2 n m 1 funções injetoras partindose de um conjunto com m elementos para um com n elementos Por exemplo há 5 4 3 60 funções injetoras partindose de um conjunto com três elementos para um com cinco elementos EXEMPLO 8 Prefixos de Telefone O formato de números de telefone na América do Norte é especificado por um prefixo telefônico Um número telefônico consiste em 10 dígitos que são organizados em um código de área de três dígitos um código de função de três dígitos e um código de localização de quatro dígitos Por causa das considerações de sinal há algumas restrições em alguns desses dígitos Para especificar os formatos possíveis considere X como um dígito que pode ser um valor de 0 a 9 N como um dígito que pode ter valor de 2 a 9 e Y como um dígito que deve ter um valor 0 ou 1 Dois prefixos telefônicos que serão chamados de prefixo antigo e prefixo novo serão discutidos O prefixo antigo usado na década de 1960 foi substituído pelo novo mas o recente crescimento na demanda por novos números de telefones móveis tornaramno obsoleto Neste exemplo as letras usadas para representar os dígitos seguem as convenções do Prefixo Telefônico da América do Norte Como será mostrado o novo prefixo permite o uso de mais números No prefixo antigo os formatos de código de área código de função e código de localização são NYX NNX e XXXX respectivamente Assim os números de telefone tinham a forma NYXNNXXXXX No novo prefixo os formatos desses códigos são NXX NXX e XXXX respectivamente então os números de telefone têm a forma NXXNXXXXXX Quantos números diferentes no padrão norteamericano são possíveis no prefixo antigo e no prefixo novo Solução Pela regra do produto há 8 2 10 160 códigos de área no formato NYX e 8 10 10 800 códigos de área no formato NXX Do mesmo modo pela regra do produto há 8 8 10 640 códigos de função no formato NNX A regra do produto também mostra que há 10 10 10 10 10 000 códigos de localização no formato XXXX Conseqüentemente aplicando a regra novamente segue que no prefixo antigo há 160 640 10 000 1 024 000 000 números diferentes disponíveis na América do Norte No prefixo novo há 800 800 10 000 6 400 000 000 números diferentes disponíveis EXEMPLO 9 Qual o valor de k depois de o seguinte código ser executado k 0 for i1 1 to n1 for i2 1 to n2 for im 1 to nm k k 1 Solução O valor inicial de k é zero Cada vez que um laço é dado 1 é adicionado a k Considere Tj como tarefa de dar o jésimo laço Então o número de vezes que os laços são dados é o número de formas necessárias para realizar as tarefas T1T2 Tm O número de formas para executar a tarefa Tj j 12 m é nj porque jésimo laço é dado uma vez para cada inteiro ij com 1 ij nj Pela regra do produto segue que o laço é dado n1 n2 nm vezes Assim o valor final de k é n1n2 nm EXEMPLO 10 Contagem de Subconjuntos de um Conjunto Finito Use a regra do produto para mostrar que o número de subconjuntos diferentes de um conjunto finito S é 2S Solução Considere S como um conjunto finito Liste os elementos de S em ordem arbitrária Retome a Seção 22 que contém a correspondência um para um entre subconjuntos de S que é uma cadeia de bits de extensão S Isto é um subconjunto de S associase com a cadeia de bits com um 1 na posição i se o iésimo elemento na lista pertence ao subconjunto e um 0 caso contrário Pela regra do produto há 2S cadeias de bits de extensão S Assim PS 2S A regra do produto é freqüentemente usada com conjuntos desta forma Se A1A2 Am são conjuntos finitos então o número de elementos no produto cartesiano desses conjuntos é o produto do número de elementos em cada conjunto Relacionando isto à regra do produto note que a tarefa de escolher um elemento no produto cartesiano A1 x A2 x x Am é feita escolhendose um elemento em A1 um elemento em A2 e um elemento em Am Pela regra do produto segue que A1 x A2 x x Am A1 A2 Am Introduziremos agora a regra da soma REGRA DA SOMA Se uma tarefa puder ser realizada em uma das n1 formas ou em uma das n2 formas em que nenhum dos elementos do conjunto das n1 formas é o mesmo que algum elemento do conjunto das n2 formas então há n1 n2 formas de realizar a tarefa O Exemplo 11 ilustra como a regra da soma é usada EXEMPLO 11 Suponha que um membro da faculdade de matemática ou um estudante que tenha mestrado em matemática seja escolhido como representante para um comitê da Universidade Quantas escolhas diferentes podem ser feitas para esse representante se houver 37 membros da faculdade de matemática e 83 mestres em matemática e nenhum for ao mesmo tempo um membro da faculdade e um mestre matemática não é o mesmo que escolher um estudante que é mestre em matemática porque nenhum deles é ao mesmo tempo um membro da faculdade e um mestre Então pela regra da soma temos que há 37 83 120 maneiras possíveis de escolher esse representante Podemos estender a regra da soma a mais de duas tarefas Suponha que uma tarefa possa ser realizada de n1 maneiras de n2 maneiras ou de nm maneiras em que nenhuma das formas do grupo ni de realizar a tarefa é a mesma da do grupo de nj para todos os pares i e j com 1 i j m Então o número de maneiras de realizar a tarefa é n1 n2 nm Esta versão estendida da regra da soma é sempre útil em problemas de contagem como os exemplos 12 e 13 mostram Esta versão da regra pode ser demonstrada usandose a indução matemática a partir da regra da soma para dois conjuntos Isso é apresentado no Exercício 59 no final da seção EXEMPLO 12 Um estudante pode escolher um projeto de computação a partir de três listas As três listas contêm 23 15 e 19 projetos possíveis respectivamente Nenhum projeto está em mais de uma lista Quantos projetos possíveis existem para serem escolhidos Solução O estudante pode escolher um projeto da primeira lista um projeto da segunda lista ou um projeto da terceira lista Como todos os projetos estão em apenas uma lista pela regra da soma há 23 15 19 57 maneiras de escolher um projeto EXEMPLO 13 Qual o valor de k depois de o seguinte código ser executado k 0 for i1 1 to n1 k k 1 for i2 1 to n2 for im 1 to nm k k 1 Solução O valor inicial de k é zero Este conjunto de códigos é composto de m laços diferentes Cada vez que um laço é dado 1 é adicionado a k Para determinar o valor de k depois que esse código tiver sido executado precisamos determinar quantas vezes são dados os laços Note que há n1 maneiras de realizar o iésimo laço Como é dado apenas um laço por vez a regra da soma mostra que o valor final de k que é o número de maneiras de realizar m laços é n1 n2 nm A regra da soma pode ser escrita em termos de conjuntos por Se A1A2 Am são conjuntos finitos disjuntos então o número de elementos na união desses conjuntos é a soma dos números de elementos nos conjuntos Para relacionar isto à nossa proposição da regra da soma note que há Ai maneiras para escolher um elemento de Ai para i 12 m Sendo os conjuntos disjuntos quando selecionamos um elemento de um dos conjuntos Ai não podemos selecionar também um elemento de um conjunto diferente Aj Conseqüentemente pela regra da soma por não existir elementos comuns em dois desses conjuntos o número de maneiras de escolher um elemento de um dos conjuntos que é o número de elementos da união é A1 U A2 U U Am A1 A2 Am Esta igualdade apenas se aplica quando os conjuntos em questão são disjuntos A situação é muito mais complicada quando esses conjuntos têm elementos em comum Tal situação será brevemente discutida mais tarde nesta seção e mais profundamente no Capítulo 7 Problemas Mais Complexos de Contagem Muitos problemas de contagem não podem ser resolvidos usando apenas as regra de soma ou de produto Entretanto muitos problemas complicados de contagem podem ser resolvidos usandose as duas regras combinadas EXEMPLO 14 Em uma versão da linguagem computacional BASIC o nome de uma variável é uma sequência de um ou dois caracteres alfanuméricos em que letras maiúsculas e minúsculas não são distinguidas Um caractere alfanumérico é aquele que utiliza as 26 letras do alfabeto da língua inglesa ou um dos 10 dígitos Além disso um nome variável deve começar com uma letra e deve ser diferente das cinco sequências de dois caracteres que são reservadas para o uso em programação os comandos Quantos nomes diferentes de variáveis são possíveis nesta versão do BASIC Solução Considere V como o número de nomes de variáveis diferentes nesta versão do BASIC Considere V1 como o número de nomes com um caractere e V2 como o número de nomes com dois caracteres Então pela regra da soma V V1 V2 Note que V1 26 porque um caractere único deve ter uma letra Mais que isso pela regra do produto há 26 36 sequências de extensão dois que começam com um letra e terminam com um caractere alfanumérico Entretanto cinco dessas sequências devem ser excluídas então V2 26 36 5 931 Assim há V V1 V2 26 931 957 nomes diferentes para variáveis nesta versão do BASIC EXEMPLO 15 Cada usuário em um sistema computacional tem uma senha com seis a oito caracteres em que cada caractere é uma letra maiúscula ou um dígito numérico Cada senha contém pelo menos um dígito numérico Quantas senhas são possíveis Solução Considere P como o número total de senhas possíveis e P6 P7 e P8 como o número de senhas possíveis com 6 7 e 8 caracteres respectivamente Pela regra da soma P P6 P7 P8 Encontraremos agora P6 P7 e P8 Encontrar P6 diretamente é difícil Para descobrir P6 é mais fácil encontrar o número de sequência de letras maiúsculas e dígitos que formam a combinação com seis caracteres incluindo aqueles com nenhum dígito e subtrair do número de sequências sem dígitos Pela regra do produto o número de sequências de seis caracteres é 366 e o número de sequências sem dígitos é 266 Assim P6 366 266 2 176 782 336 308 915 776 1 867 866 560 Analogamente podemos mostrar que P7 367 267 78 364 164 096 8 031 810 176 70 332 353 920 e P8 368 268 2 821 109 907 456 208 827 064 576 2 612 282 842 880 Conseqüentemente P P6 P7 P8 2 684 483 063 360 Número de Bits 0 1 2 3 4 8 16 24 31 Classe A 0 netid hostid Classe B 1 0 netid hostid Classe C 1 1 0 netid hostid Classe D 1 1 1 0 Endereço Multicast Classe E 1 1 1 1 0 Endereço FIGURA 1 Endereços de Internet IPv4 EXEMPLO 16 Contagem de Endereços da Internet Na Internet que é construída a partir de redes de transmissão de computadores interconectadas fisicamente cada computador ou mais precisamente cada rede de transmissão conectada a um computador possui um endereço de Internet Na Versão 4 do Protocolo de Internet IPv4 agora em uso um endereço é uma cadeia de 32 bits Ele começa com um número de transmissão netid O netid é seguido de um número de hospedagem hostid que identifica um computador como um membro de uma determinada rede de transmissão Três formas de endereços são usadas com números diferentes de bits usados por netids e hostids Endereços Classe A usados pelas maiores redes de transmissão consistem em 0 seguido de um netid de 7 bits e um hostid de 24 bits Endereços Classe B usados por redes medianas consistem em 10 seguido por um netid de 14 bits e um hostid de 16 bits Endereços Classe C usados pelas redes menores consistem em 110 seguido por um netid de 21 bits e um hostid de 8 bits Há muitas restrições nos endereços para os usos especiais 11111111 não está disponível no netid de uma Classe A e os hostids de 0 e 1 não estão disponíveis para o uso em nenhuma rede Um computador na Internet tem o um endereço Classe A ou um Classe B ou um Classe C Além dos endereços de Classe A B e C há também os endereços de Classe D reservados para o uso em transmissão múltipla quando vários computadores são endereçados ao mesmo tempo que consistem em 1110 seguido de 28 bits e os endereços de Classe E reservados para uso futuro que consistem em 11110 seguido de 27 bits Nem os endereços de Classe D nem os de Classe E são considerados endereços de IP de um computador na Internet A Figura 1 mostra os endereços IPv4 Limitações no número de netids da Classe A e da Classe B tornaram os endereços IPv4 inadequados IPv6 uma nova versão de IP usa endereços de 128 bits para resolver este problema Quantos endereços IPv4 diferentes estão disponíveis para os computadores na Internet Solução Considere x como o número de endereços disponíveis para computadores na Internet e xA xB e xC como o número de endereços da Classe A Classe B e Classe C disponíveis respectivamente Pela regra da soma x xA xB xC Para encontrar xA note que há 27 1 127 netids de Classe A relembrando que o netid 1111111 não está disponível Para cada netid há 224 2 16 777 214 hostids relembrando que todos os hostids que tenham somente 0s e 1s não estão disponíveis Conseqüentemente xA 127 16 777 214 2 130 706 178 Para encontrar xB e xC note que há 214 16 384 netids de Classe B e 221 2 097 152 netids de Classe C Para cada netid de Classe B há 216 2 65 534 hostids e para cada netid de Classe C há 28 2 254 hostids relembrando que em cada rede de transmissão os hostids compostos somente de 0s e 1s não estão disponíveis Conseqüentemente xB 1 073 709 056 e xC 532 676 608 Concluímos que o número total de endereços IPv4 disponíveis é x xA xB xC 2 130 706 178 1 073 709 056 532 676 608 3 737 091 842 Princípio da InclusãoExclusão Suponha que uma tarefa possa ser realizada de n1 ou n2 maneiras mas que algumas das maneiras do conjunto n1 para realizar as tarefas são as mesmas de algumas das do n2 Neste caso não podemos usar a regra da soma para contar o número de maneiras de realizar a tarefa Adicionar o número de maneiras de realizar as tarefas nessas duas formas leva a uma contagem excessiva porque as maneiras de realizar a tarefa naquelas formas que são idênticas serão contadas duas vezes Para contar corretamente o número de maneiras para realizar as duas tarefas somamos o número total de maneiras para realizála e então subtraímos o número de maneiras de realizar a tarefa que pertence aos dois grupos Esta técnica é chamada de princípio da inclusãoexclusão Em alguns casos este princípio também pode ser chamado de princípio da subtração para contagem O Exemplo 17 ilustra como podemos resolver os problemas de contagem usando este princípio EXEMPLO 17 Quantas cadeias de bits de extensão oito começam com 1 bit ou terminam com dois bits 00 Solução Podemos construir uma cadeia de bits de extensão oito que ou começa com um 1 bit ou termina com dois bits 00 construindo uma cadeia de bits de extensão oito que começa com um 1 bit ou construindo uma cadeia de bits de extensão oito que termina com dois bits 00 Podemos construir uma cadeia de bits que começa com 1 de 27 128 maneiras seguindo a regra do produto pois o primeiro bit pode ser escolhido de uma única maneira e cada um dos outros sete bits podem ser escolhidos de duas formas Analogamente podemos construir uma cadeia de bits de extensão oito que termina com dois bits 00 de 26 64 maneiras Seguimos a regra do produto pois cada um dos primeiros seis bits pode ser escolhido de duas maneiras e os últimos dois bits podem ser escolhidos apenas de uma maneira Algumas maneiras de construir uma cadeia de bits de extensão oito que começa com 1 são as mesmas de construir uma cadeia de bits de extensão oito que termina com dois bits 00 Há 25 32 maneiras de construir tal cadeia seguindo a regra do produto porque o primeiro bit pode ser escolhido apenas de uma forma e do segundo até o sexto bit podem ser escolhidos de duas maneiras e os dois últimos bits podem ser escolhidos de uma única forma Conseqüentemente o número de cadeias de bits de extensão oito que começa com 1 ou termina com 00 que é igual ao número de maneiras de construir uma cadeia de bits de extensão oito que começa com 1 ou termina com 00 é 128 64 32 160 Podemos descrever este princípio de contagem em termos de conjuntos Considere A1 e A2 como conjuntos Há A1 maneiras de selecionar um elemento do conjunto A1 e A2 maneiras de selecionar um elemento do conjunto A2 O número de maneiras de escolher um elemento do conjunto A1 ou do conjunto A2 que é o número de maneiras de escolher um elemento da união desses conjuntos é a soma do número de maneiras de selecionar um elemento de A1 com o número de maneiras de selecionar um elemento de A2 menos o número de maneiras de selecionar um elemento que pertence aos dois conjuntos A1 e A2 Visto que existem A1 U A2 maneiras de escolher um elemento ou em A1 ou em A2 e A1 A2 maneiras de selecionar um elemento comum dos dois conjuntos temos que A1 U A2 A1 A2 A1 A2 Esta é a fórmula dada na Seção 22 para o número de elementos na união de dois conjuntos Apresentaremos um exemplo que ilustra como a formulação do princípio de inclusãoexclusão pode ser usado para resolver problemas de contagem EXEMPLO 18 Uma companhia de computadores recebe 350 currículos de graduados em computação para uma proposta de trabalho de planejamento de uma nova linha de servidores da Web Suponha que 220 dessas pessoas sejam da área de ciência da computação 147 de administração e 51 de ciência da computação e administração Quantos desses graduados não são da área de ciência da computação nem de administração Solução Para encontrar o número de candidatos que não são graduados nem em ciência da computação nem em administração podemos subtrair o número de estudantes que são graduados em ciência da computação ou em administração ou ambos do total de candidatos Considere A1 como o conjunto de estudantes graduados em ciência da computação e A2 o conjunto dos estudantes graduados em administração Então A1 U A2 é o conjunto dos graduandos em ciência da computação ou em administração ou ambos e A1 A2 é o conjunto de estudantes graduados em ciência da computação e em administração Pelo princípio da inclusãoexclusão o número de estudantes graduados em ciência da computação ou em administração ou ambos é igual a A1 U A2 A1 A2 A1 A2 220 147 51 316 Concluímos que 350 316 34 dos currículos recebidos não são de graduados nem em ciência da computação nem em administração O princípio da inclusãoexclusão pode ser generalizado para encontrar o número de maneiras de realizar n tarefas diferentes ou de modo equivalente encontrar o número de elementos da união de n conjuntos sempre que n for um número inteiro e positivo Estudaremos o princípio da inclusãoexclusão e algumas de suas aplicações no Capítulo 7 Diagramas de Árvore Problemas de contagem podem ser resolvidos usandose os diagramas de árvore Uma árvore consiste em uma raiz um número de galhos que partem da raiz e possíveis galhos adicionais no final de cada galho Estudaremos as árvores com detalhes no Capítulo 10 Para usar as árvores na contagem usamos um galho para representar cada escolha possível Representamos as possíveis saídas pelas folhas que são os finais dos galhos sem outros que comecem a partir deles Note que um diagrama de árvore é usado para resolver um problema de contagem sendo que o número de escolhas necessárias para alcançar uma folha pode variar veja o Exemplo 20 por exemplo EXEMPLO 19 Quantas cadeias de bits de comprimento quatro não possuem dois números 1s consecutivos Solução O diagrama de árvore da Figura 2 mostra todas as cadeias de bits de comprimento quatro sem dois números 1s consecutivos Vemos que há oito cadeias de bits de comprimento quatro sem dois números 1s consecutivos EXEMPLO 20 Uma eliminatória entre dois times é composta de no máximo cinco jogos O primeiro time que vence três jogos vence a eliminatória De quantas formas diferentes a eliminatória pode ocorrer Time ganhador está cinza FIGURA 2 Cadeia de Bits de Comprimento Quatro sem 1s Consecutivos FIGURA 3 Os três melhores jogos de uma eliminatória com cinco partidas W branco R vermelho G verde B preto FIGURA 4 Contando Variedades de Camisetas Solução O diagrama de árvore da Figura 3 mostra todas as formas de ocorrer a eliminatória apresentando o vencedor de cada partida Vemos que há 20 maneiras diferentes de a eliminatória acontecer EXEMPLO 21 Suponha que as camisetas Eu Amo Florianópolis tenham cinco tamanhos diferentes P M G XG e XXG Além disso cada tamanho vem em quatro cores branco vermelho verde e preto exceto para o tamanho XG que vem apenas em vermelho verde e preto e o tamanho XXG que vem apenas em verde e preto Quantas camisetas diferentes uma loja terá em estoque para ter ao menos uma camiseta de cada cor e tamanho disponível Solução O diagrama de árvore da Figura 4 mostra todos os tamanhos e cores disponíveis Partindo dele o dono da loja deve ter em estoque de 17 camisetas diferentes Exercícios 1 Em uma universidade há 18 graduados em matemática e 325 em ciência da computação a Há quantas maneiras de escolher dois representantes de modo que um seja matemático e o outro um cientista da computação b Há quantas maneiras de escolher um representante que seja ou matemático ou cientista da computação 2 Um edifício empresarial contém 27 andares com 37 escritórios em cada andar Quantos escritórios há no prédio 3 Um exame de múltipla escolha contém 10 questões Há quatro respostas possíveis para cada questão a De quantas maneiras um estudante pode responder às questões do exame se responder a todas as questões b De quantas maneiras um estudante pode responder às questões do exame se ele pode deixar respostas em branco 4 Uma determinada marca de camisetas vem em 12 cores tem modelos masculino e feminino e três tamanhos para cada sexo Quantos tipos diferentes de camisetas são fabricados 5 Seis companhias aéreas voam de Nova York a Denver e sete de Denver a São Francisco Quantos pares diferentes de companhias aéreas você pode escolher para fazer uma viagem de Nova York a São Francisco com conexão em Denver em que você escolhe uma companhia para viajar até Denver e outra para continuar o vôo a São Francisco Quantas dessas maneiras envolvem mais de uma companhia 6 Há quatro autoestradas principais de Boston a Detroit e seis de Detroit a Los Angeles Quantas autoestradas há para o percurso BostonLos Angeles via Detroit 7 Quantas iniciais diferentes com três letras uma pessoa pode ter 8 Quantas iniciais diferentes com três letras sem que nenhuma seja repetida uma pessoa pode ter 9 Quantas iniciais diferentes com três letras que comecem com a letra A são possíveis 10 Quantas cadeias de bits de comprimento oito são possíveis 11 Quantas cadeias de bits de comprimento 10 que comecem e terminem com um 1 são possíveis 12 Quantas cadeias de bits de comprimento seis ou menos são possíveis 13 Quantas cadeias de bits com comprimento não excedente a n em que n é um número inteiro positivo compostas apenas de 1s são possíveis 14 Quantas cadeias de bits com comprimento n em que n é um número inteiro positivo que começam e terminam com 1 são possíveis 15 Quantas sequências de letras minúsculas de extensão quatro ou menos são possíveis 16 Quantas sequências de quatro letras minúsculas que contenham a letra x são possíveis 17 Quantas sequências de cinco caracteres ASCII contêm o caractere arroba ao menos uma vez Nota Há 128 caracteres ASCII diferentes 18 Quantos números inteiros positivos entre 5 e 31 a são divisíveis por 3 Quais números inteiros são esses b são divisíveis por 4 Quais números inteiros são esses c são divisíveis por 3 e por 4 Quais números inteiros são esses 19 Quantos números inteiros positivos entre 50 e 100 a são divisíveis por 7 Quais números inteiros são esses b são divisíveis por 11 Quais números inteiros são esses c são divisíveis por 7 e por 11 Quais números inteiros são esses 20 Quantos números inteiros positivos menores que 1000 a são divisíveis por 7 b são divisíveis por 7 mas não por 11 c são divisíveis por 7 e por 11 d são divisíveis por 7 ou por 11 e são divisíveis exatamente por 7 e por 11 f não são divisíveis nem por 7 nem por 11 g têm dígitos distintos h têm dígitos distintos e são pares 21 Quantos números inteiros positivos entre 100 e 999 incluindo este último a são divisíveis por 7 b são ímpares c têm os três dígitos iguais d não são divisíveis por 4 e são divisíveis por 3 ou por 4 f não são divisíveis por 3 nem por 4 g são divisíveis por 3 mas não por 4 h são divisíveis por 3 e por 4 22 Quantos números inteiros positivos entre 1000 e 9999 incluindo este último a são divisíveis por 9 b são pares c têm dígitos distintos d não são divisíveis por 3 e são divisíveis por 5 ou por 7 f não são divisíveis por 5 nem por 7 g são divisíveis por 5 mas não por 7 h são divisíveis por 5 e por 7 23 Quantas sequências de três dígitos decimais a não são formadas pelo mesmo dígito três vezes b começam com um dígito ímpar c têm exatamente dois dígitos que são o número 4 24 Quantas sequências de quatro dígitos decimais a não contém o mesmo dígito duas vezes b terminam com um dígito par c têm exatamente três dígitos que são o número 9 25 Um comitê é formado por um representante de cada um dos 50 estados dos Estados Unidos no qual o representante do estado é ou o governador ou um dos dois senadores daquele determinado estado Quantas maneiras há para formar esse comitê 26 Quantas placas de identificação de veículos podem ser feitas usandose três dígitos seguidos de três letras ou três letras seguidas de três dígitos 27 Quantas placas de identificação de veículos podem ser feitas usandose duas letras seguidas de quatro dígitos ou dois dígitos seguidos de quatro letras 28 Quantas placas de identificação de veículos podem ser feitas usandose três letras seguidas de três dígitos ou quatro letras seguidas de dois dígitos 29 Quantas placas de identificação de veículos podem ser feitas usandose duas ou três letras seguidas de dois ou três dígitos 30 Quantas sequências de oito letras do alfabeto da língua inglesa são possíveis a se as letras puderem ser repetidas b se nenhuma letra puder ser repetida c que comecem com X se as letras puderem ser repetidas d que comecem com X se nenhuma letra puder ser repetida e que comecem e terminem com X se as letras puderem ser repetidas f que comecem com as letras BO nesta ordem se as letras puderem ser repetidas g que comecem e terminem com as letras BO nesta ordem se as letras puderem ser repetidas h que comecem ou terminem com as letras BO nesta ordem se as letras puderem ser repetidas 31 Quantas sequências de oito letras do alfabeto da língua inglesa são possíveis a que não contenham vogais se as letras puderem ser repetidas b que não contenham vogais se as letras não puderem ser repetidas c que comecem com uma vogal se as letras puderem ser repetidas d que comecem com uma vogal se as letras não puderem ser repetidas e que contenham pelo menos uma vogal se as letras puderem ser repetidas f que contenham exatamente uma vogal se as letras puderem ser repetidas g que comecem com X e que contenham pelo menos uma vogal se as letras puderem ser repetidas h que comecem e terminem com X e contenham pelo menos uma vogal se as letras puderem ser repetidas 32 Quantas funções diferentes são possíveis a partir de um conjunto de 10 elementos para os conjuntos com os seguintes números de elementos a 2 b 3 c 4 d 5 33 Quantas funções injetoras são possíveis a partir de um conjunto com cinco elementos para os conjuntos com os seguintes números de elementos a 4 b 5 c 6 d 7 34 Quantas funções são possíveis a partir do conjunto 1 2 n em que n é um número inteiro e positivo para o conjunto 0 1 35 Quantas funções são possíveis a partir do conjunto 1 2 n em que n é um número inteiro e positivo para o conjunto 0 1 a que são injetoras b que atribuam 0 aos valores 1 e n c que atribuam 1 a exatamente um dos números inteiros positivos menores que n 36 Quantas funções parciais veja o preâmbulo do Exercício 73 na Seção 23 são possíveis a partir de um conjunto com cinco elementos para um conjunto que tenha cada um dos números de elementos abaixo a 1 b 2 c 5 d 9 37 Quantas funções parciais veja o preâmbulo do Exercício 73 na Seção 23 são possíveis a partir de um conjunto com m elementos para um conjunto com n elementos em que m e n são números inteiros positivos 38 Quantos subconjuntos de um conjunto com 100 elementos têm mais de um elemento 39 Um palíndromo é uma sequência no qual o seu inverso é idêntico à sequência Quantas cadeias de bits de extensão n são palíndromos 40 De quantas maneiras um fotógrafo pode organizar 6 pessoas de um grupo de 10 em um casamento em que a noiva e o noivo estão entre estas 10 pessoas se a a noiva deve estar na foto b tanto a noiva quanto o noivo devem estar na foto c um dos dois noiva ou noivo deve estar na foto 41 De quantas maneiras um fotógrafo pode organizar seis pessoas em uma fila em um casamento incluindo a noiva e o noivo se a a noiva deve estar ao lado do noivo b a noiva não está ao lado do noivo c a noiva está posicionada à esquerda do noivo 42 Quantas cadeias de bits de comprimento sete começam com dois 0s ou terminam com três 1s 43 Quantas cadeias de bits de comprimento 10 começam com três 0s ou terminam com dois Os 44 Quantas cadeias de bits de comprimento 10 têm cinco 0s consecutivos ou cinco 1s consecutivos 45 Quantas cadeias de bits de comprimento oito têm três 0s consecutivos ou quatro 1s consecutivos 46 Todo estudante em uma aula de matemática discreta é ou da área de ciência da computação ou de matemática ou é das duas áreas Quantos estudantes há na sala se 38 são graduados em ciência da computação incluindo os que são das duas áreas 23 graduados em matemática incluindo os das duas áreas e 7 graduados nas duas áreas 47 Quantos números inteiros positivos menores ou iguais a 100 são divisíveis por 4 ou por 6 48 Quantas iniciais diferentes uma pessoa pode ter se ela tiver pelo menos duas mas no máximo cinco iniciais diferentes Suponha que cada inicial é uma das 26 letras do alfabeto da língua inglesa 49 Suponha que uma senha para um sistema computacional deva ter pelo menos 8 mas não mais de 12 caracteres em que cada caractere na senha é uma letra minúscula uma letra maiúscula um dígito ou um dos seis caracteres especiais e a Quantas senhas diferentes estão disponíveis para esse sistema b Quantas dessas senhas contêm pelo menos uma ocorrência de pelo menos um dos seis caracteres especiais c Se demora um nanossegundo para um hacker checar se cada senha possível é a sua senha quanto tempo demoraria para o hacker tentar todas as senhas possíveis 50 O nome de uma variável na linguagem de programação C é uma sequência que pode conter letras maiúsculas minúsculas dígitos ou negrito Além disso o primeiro caractere na sequência deve ser uma letra maiúscula ou minúscula ou um negrito Se o nome da variável é determinado pelos primeiros oito caracteres quantas variáveis diferentes podem ser nomeadas em C Note que o nome da variável pode conter menos que oito caracteres 51 Suponha que em um tempo futuro a todo telefone no mundo seja atribuído um número que contenha um código do país de 1 a 3 dígitos ou seja sob a forma X XX ou XXX seguido do número de telefone com 10 dígitos na forma de XXX NXXXXXX como descrito no Exemplo 8 Quantos números de telefone diferentes estariam disponíveis na rede mundial de acordo com este plano numérico 52 Use um diagrama de árvore para encontrar o número de cadeias de bits de comprimento quatro sem três zeros consecutivos 53 Quantas maneiras de organizar as letras a b c d e d tal que a não seja seguida imediatamente por b são possíveis 54 Use um diagrama de árvore para encontrar o número de maneiras para uma final de campeonato acontecer em que o primeiro time que vencer quatro jogos de sete vence o campeonato 55 Use um diagrama de árvore para determinar o número de subconjuntos de 3 7 9 11 24 com a propriedade de que a soma dos elementos no subconjunto seja menor que 28 56 a Suponha que uma loja venda seis variedades de refrigerantes coca guaraná laranja sucos limonada e citrus Use um diagrama de árvore para determinar o número de tipos diferentes de garrafas que a loja deve estocar para ter disponíveis todas as variedades em todos os tamanhos de garrafas considerandose que todas as variedades estão disponíveis em garrafas de 300 ml apenas a limonada está disponível em garrafa de 500 ml e apenas a coca e o guaraná em garrafas de 600 ml e todos menos a limonada e o citrus estão disponíveis em garrafas de 1 l b Responda à questão do item a usando as regras de contagem 57 a Suponha que um modelo popular de tênis de corrida esteja disponível tanto para homens quanto para mulheres O tênis feminino vem nos tamanhos 6 7 8 e 9 e o masculino nos tamanhos 8 9 10 11 e 12 O modelo masculino vem nas cores branco e preto e o feminino em branco vermelho e preto Use um diagrama de árvore para determinar o número de diferentes tênis que uma loja tem de estocar para ter pelo menos um par disponível de todas as cores e tamanhos para mulheres e para homens b Responda à questão do item a usando as regras de contagem 58 Use a regra do produto para mostrar que há 2k tabelas verdade diferentes para as proposições em r variáveis 59 Use a indução matemática para demonstrar a regra da soma para m tarefas a partir da regra da soma para duas tarefas 60 Use a indução matemática para demonstrar a regra do produto para m tarefas a partir da regra do produto para duas tarefas 61 Quantas diagonais tem um polígono convexo com n lados Lembrese de que um polígono é convexo se todos os segmentos de reta que unem dois pontos no interior ou na margem do polígono estiverem inteiramente dentro deste polígono e que uma diagonal de um polígono é um segmento de reta que liga dois vértices que não são adjacentes 62 Os dados são transmitidos pela Internet em datagramas que são estruturados em blocos de bits Cada datagrama contém informação de cabeçalho organizada em um máximo 37 Quantas funções parciais veja o preâmbulo do Exercício 73 na Seção 23 são possíveis a partir de um conjunto com m elementos para um conjunto com n elementos em que m e n são números inteiros positivos 38 Quantos subconjuntos de um conjunto com 100 elementos têm mais de um elemento 39 Um palíndromo é uma sequência no qual o seu inverso é idêntico à sequência Quantas cadeias de bits de extensão n são palíndromos 40 De quantas maneiras um fotógrafo pode organizar 6 pessoas de um grupo de 10 em um casamento em que a noiva e o noivo estão entre estas 10 pessoas se a a noiva deve estar na foto b tanto a noiva quanto o noivo devem estar na foto c um dos dois noiva ou noivo deve estar na foto 41 De quantas maneiras um fotógrafo pode organizar seis pessoas em uma fila em um casamento incluindo a noiva e o noivo se a a noiva deve estar ao lado do noivo b a noiva não está ao lado do noivo c a noiva está posicionada à esquerda do noivo 42 Quantas cadeias de bits de comprimento sete começam com dois 0s ou terminam com três 1s 43 Quantas cadeias de bits de comprimento 10 começam com três 0s ou terminam com dois Os 44 Quantas cadeias de bits de comprimento 10 têm cinco 0s consecutivos ou cinco 1s consecutivos 45 Quantas cadeias de bits de comprimento oito têm três 0s consecutivos ou quatro 1s consecutivos 46 Todo estudante em uma aula de matemática discreta é ou da área de ciência da computação ou de matemática ou é das duas áreas Quantos estudantes há na sala se 38 são graduados em ciência da computação incluindo os que são das duas áreas 23 graduados em matemática incluindo os das duas áreas e 7 graduados nas duas áreas 47 Quantos números inteiros positivos menores ou iguais a 100 são divisíveis por 4 ou por 6 48 Quantas iniciais diferentes uma pessoa pode ter se ela tiver pelo menos duas mas no máximo cinco iniciais diferentes Suponha que cada inicial é uma das 26 letras do alfabeto da língua inglesa 49 Suponha que uma senha para um sistema computacional deva ter pelo menos 8 mas não mais de 12 caracteres em que cada caractere na senha é uma letra minúscula uma letra maiúscula um dígito ou um dos seis caracteres especiais e a Quantas senhas diferentes estão disponíveis para esse sistema b Quantas dessas senhas contêm pelo menos uma ocorrência de pelo menos um dos seis caracteres especiais c Se demora um nanossegundo para um hacker checar se cada senha possível é a sua senha quanto tempo demoraria para o hacker tentar todas as senhas possíveis 50 O nome de uma variável na linguagem de programação C é uma sequência que pode conter letras maiúsculas minúsculas dígitos ou negrito Além disso o primeiro caractere na sequência deve ser uma letra maiúscula ou minúscula ou um negrito Se o nome da variável é determinado pelos primeiros oito caracteres quantas variáveis diferentes podem ser nomeadas em C Note que o nome da variável pode conter menos que oito caracteres 51 Suponha que em um tempo futuro a todo telefone no mundo seja atribuído um número que contenha um código do país de 1 a 3 dígitos ou seja sob a forma X XX ou XXX seguido do número de telefone com 10 dígitos na forma de XXX NXXXXXX como descrito no Exemplo 8 Quantos números de telefone diferentes estariam disponíveis na rede mundial de acordo com este plano numérico 52 Use um diagrama de árvore para encontrar o número de cadeias de bits de comprimento quatro sem três zeros consecutivos 53 Quantas maneiras de organizar as letras a b c d e d tal que a não seja seguida imediatamente por b são possíveis 54 Use um diagrama de árvore para encontrar o número de maneiras para uma final de campeonato acontecer em que o primeiro time que vencer quatro jogos de sete vence o campeonato 55 Use um diagrama de árvore para determinar o número de subconjuntos de 3 7 9 11 24 com a propriedade de que a soma dos elementos no subconjunto seja menor que 28 56 a Suponha que uma loja venda seis variedades de refrigerantes coca guaraná laranja sucos limonada e citrus Use um diagrama de árvore para determinar o número de tipos diferentes de garrafas que a loja deve estocar para ter disponíveis todas as variedades em todos os tamanhos de garrafas considerandose que todas as variedades estão disponíveis em garrafas de 300 ml apenas a limonada está disponível em garrafa de 500 ml e apenas a coca e o guaraná em garrafas de 600 ml e todos menos a limonada e o citrus estão disponíveis em garrafas de 1 l b Responda à questão do item a usando as regras de contagem 57 a Suponha que um modelo popular de tênis de corrida esteja disponível tanto para homens quanto para mulheres O tênis feminino vem nos tamanhos 6 7 8 e 9 e o masculino nos tamanhos 8 9 10 11 e 12 O modelo masculino vem nas cores branco e preto e o feminino em branco vermelho e preto Use um diagrama de árvore para determinar o número de diferentes tênis que uma loja tem de estocar para ter pelo menos um par disponível de todas as cores e tamanhos para mulheres e para homens b Responda à questão do item a usando as regras de contagem 58 Use a regra do produto para mostrar que há 2k tabelas verdade diferentes para as proposições em r variáveis 59 Use a indução matemática para demonstrar a regra da soma para m tarefas a partir da regra da soma para duas tarefas 60 Use a indução matemática para demonstrar a regra do produto para m tarefas a partir da regra do produto para duas tarefas 61 Quantas diagonais tem um polígono convexo com n lados Lembrese de que um polígono é convexo se todos os segmentos de reta que unem dois pontos no interior ou na margem do polígono estiverem inteiramente dentro deste polígono e que uma diagonal de um polígono é um segmento de reta que liga dois vértices que não são adjacentes 62 Os dados são transmitidos pela Internet em datagramas que são estruturados em blocos de bits Cada datagrama contém informação de cabeçalho organizada em um máximo de 14 campos diferentes especificando muitas coisas incluindo a fonte e os endereços de destinátario e a área de dados que contêm os dados atuais que são transmitidos Um dos 14 campos de cabeçalho é o campo de cabeçalho estendido indicado por HLEN que é caracterizado pelo protocolo por ter 4 bits e por especificar a extensão do cabeçalho em blocos de 32 bits Por exemplo se HLEN 0110 o cabeçalho é composto por seis blocos de 32 bits Outro componente dos 14 campos de cabeçalho é o campo de extensão total de 16 bits indicado por EXTENSÃO TOTAL que especifica a extensão em bits de todo o datagrama incluindo os campos de cabeçalho e a área de dados A extensão da área de dados é a extensão total do datagrama menos a extensão do cabeçalho a O maior valor possível para a EXTENSÃO TOTAL que é de 16 bits determina a extensão máxima total em octetos blocos de 8 bits de um datagrama da Internet Qual é esse valor b O maior valor possível para o HLEN que é de 4 bits determina a extensão máxima total de cabeçalho em blocos de 32 bits Qual é esse valor Qual é a extensão máxima total de cabeçalho em octetos c A extensão mínima e mais comum de cabeçalho é 20 octetos Qual é a extensão máxima total em octetos da área de dados de um datagrama da Internet d Quantas sequências diferentes de octetos na área de dados podem ser transmitidas se a extensão do cabeçalho for 20 octetos e a extensão total for a máxima possível 52 O Princípio da Casa dos Pombos Introdução Suponha que um grupo de 20 pombos voe para dentro de 19 casas para empoleiraremse Visto que há 20 pombos e 19 casas pelo menos uma dessas 19 casas deverão ter no mínimo dois pombos Para ver por que isso é verdadeiro note que se cada casa tiver no máximo um pombo no máximo 19 pombos um por casa poderão ser acomodados Isso ilustra um princípio geral chamado de princípio da casa dos pombos que afirma que se há mais pombos que casas então deverá ter pelo menos uma casa com pelo menos dois pombos veja a Figura 1 É claro que esse princípio se aplica a outros objetos além de pombos e casas TEOREMA 1 O PRINCÍPIO DA CASA DOS POMBOS Se k for um número inteiro positivo e k1 ou mais objetos são colocados dentro de k caixas então há uma caixa que terá dois ou mais objetos Demonstração Vamos demonstrar o princípio da casa dos pombos usando uma demonstração por contraposição Suponha que nenhuma das k caixas contenha mais de um objeto Então o número total de objetos seria no máximo k Esta é uma contradição porque há pelo menos k1 objetos FIGURA 1 Há mais Pombos que Casas O princípio da casa dos pombos é também chamado de Princípio das Gavetas de Dirichlet depois que o matemático alemão Dirichlet usou frequentemente este princípio em seu trabalho no século XIX O princípio da casa dos pombos podem ser usado para demonstrar diversas funções COROLÁRIO 1 Uma função f de um conjunto com k1 ou mais elementos para um conjunto com k elementos não é injetora Demonstração Suponha que para cada elemento y no contradomínio de f temos uma caixa que contém todos os elementos x do domínio de f tal que fx y Como o domínio contém k1 ou mais elementos e o contradomínio contém apenas k elementos o princípio da casa dos pombos nos diz que uma das caixas contém dois ou mais elementos x do domínio Isto significa que f não pode ser uma função injetora Os exemplos 1 a 3 mostram como o princípio da casa dos pombos é usado EXEMPLO 1 Entre qualquer grupo de 367 pessoas deverá existir ao menos duas com a mesma data de aniversário porque há apenas 366 possíveis datas EXEMPLO 2 Em qualquer grupo de 27 palavras em inglês deverá haver pelo menos duas que começam com a mesma letra pois há 26 letras no alfabeto da língua inglesa EXEMPLO 3 Quantos estudantes deve haver em uma classe para garantir que pelo menos dois estudantes tenham a mesma nota nas provas finais se a nota é graduada em uma escala de 0 a 100 Solução Há 101 notas possíveis no final O princípio da casa dos pombos mostra que entre quaisquer 102 estudantes há pelo menos dois com a mesma nota O princípio da casa dos pombos é um instrumento útil em muitas demonstrações incluindo as demonstrações de resultados surpreendentes como a do Exemplo 4 EXEMPLO 4 Mostre que para todo número inteiro n há um múltiplo de n que contêm apenas Os e 1s quando escrito na base decimal Solução Considere n como um número inteiro positivo Considere n1 números inteiros 1 11 111 11 1 em que o último número inteiro da lista é um número inteiro com n1 1s em sua expansão decimal Note que há n restos possíveis quando um número inteiro é dividido por n Como há n 1 números inteiros nesta lista Pelo princípio da casa dos pombos deverá haver dois com o mesmo resto quando for dividido por n O maior desses números inteiros menos o menor deles é um múltiplo de n que tem um expansão decimal de 0s e 1s G LEJEUNE DIRICHLET 18051859 G Lejeune Dirichlet nasceu em uma família francesa que morava perto de Colônia na Alemanha Estudou na Universidade de Paris e ocupou cargos na Universidade de Breslau e na Universidade de Berlim Em 1855 ele foi escolhido para ser o sucessor de Gauss na Universidade de Göttingen Dirichlet é considerado a primeira pessoa a estudar a fundo a obra Disquisitiones Arithmeticae de Gauss publicada 20 anos antes Ele mantinha uma cópia desse trabalho ao seu lado mesmo quando viajava Dirichlet fez importantes descobertas sobre a teoria dos números inclusive o teorema de que há números primos infinitos em progressões aritméticas an b quando a e b são primos entre si Ele demonstrou o caso de n 5 do último teorema de Fermat afirmando que não há soluções não triviais em números inteiros para x5 y5 z5 Dirichlet fez também muitas contribuições em análise A Generalização do Princípio da Casa dos Pombos O princípio da casa dos pombos afirma que deverá haver pelo menos dois objetos na mesma caixa quando houver mais objetos que caixas No entanto mais pode ser dito quando o número de objetos excede um múltiplo do número de caixas Por exemplo entre qualquer conjunto de 21 dígitos decimais deverá haver 3 que serão os mesmos Isto ocorre porque quando 21 objetos são distribuídos em 10 caixas uma caixa deverá conter mais que 2 objetos TEOREMA 2 A GENERALIZAÇÃO DO PRINCÍPIO DA CASA DOS POMBOS Se N objetos são colocados em k caixas então há pelo menos uma caixa com Nk objetos Demonstração Usaremos uma demonstração por contradição Suponha que nenhuma das caixas tenha mais que Nk 1 objetos Então o número total de objetos é no máximo kNk 1 kNk 1 N em que a inequação Nk Nk 1 foi usada Isto é uma contradição pois há um total de N objetos Um tipo comum de problema pede o número mínimo de objetos tal que pelo menos r desses objetos deverão estar em uma das k caixas quando esses objetos forem distribuídos entre as caixas Quando temos N objetos a generalização do princípio da casa dos pombos diz que deverá haver pelo menos r objetos em uma das caixas contanto que Nk r O menor número inteiro N com Nk r 1 ou seja N kr 1 1 é o menor número inteiro que satisfaz a inequação Nk r Um menor valor de N poderia ser suficiente A resposta é não porque se temos kr 1 objetos poderíamos colocar r 1 deles em cada uma das k caixas e nenhuma caixa teria pelo menos r objetos Quando pensamos em problemas desse tipo é útil considerar como você pode evitar ter pelo menos r objetos em uma das caixas quando você coloca objetos sucessivos Para evitar colocar um résimo objeto em qualquer caixa você deve eventualmente terminar com r 1 objetos em cada caixa Não há como adicionar o próximo objeto sem colocar um résimo objeto naquela caixa Os exemplos 5 a 8 ilustram como a generalização do princípio da casa dos pombos é aplicada EXEMPLO 5 Entre 100 pessoas há pelo menos 10012 9 que nasceram no mesmo mês EXEMPLO 6 Qual o menor número de estudantes necessário em uma sala de matemática discreta para se ter certeza de que pelo menos seis receberão a mesma nota se são possíveis cinco notas A B C D e F Solução O número mínimo de estudantes necessário para garantir que pelo menos seis estudantes tirem a mesma nota é o menor número inteiro N tal que N5 6 Assim o menor número inteiro é N 5 5 1 26 Se você tiver apenas 25 estudantes é possível que haja cinco que receberão cada nota e não seis Assim 26 é o menor número de estudantes necessário para assegurar que pelo menos seis alunos terão a mesma nota EXEMPLO 7 a Quantas cartas devem ser escolhidas de um baralho de 52 cartas para garantir que pelo menos três cartas do mesmo naipe sejam selecionadas b Quantas cartas devem ser escolhidas para garantir que pelo menos três copas sejam selecionadas Solução a Suponha que haja quatro caixas uma para cada naipe e assim que as cartas forem sendo selecionadas elas são colocadas na caixa reservada para cada naipe Usando a generalização do princípio da casa dos pombos vemos que se N cartas são selecionadas há pelo menos uma caixa com no mínimo N4 cartas Conseqüentemente sabemos que pelo menos três cartas de um naipe são selecionadas se N4 3 O menor número inteiro N tal que N4 3 é N 2 4 1 9 então nove cartas são suficientes Note que se oito cartas forem escolhidas é possível que haja duas cartas de cada naipe então são necessárias mais que oito Conseqüentemente nove cartas devem ser selecionadas para garantir que pelo menos três cartas de um naipe sejam escolhidas Uma boa forma de pensar nisso é notar que depois da oitava carta escolhida não há como evitar ter uma terceira carta de algum naipe b Não usaremos a generalização do princípio da casa dos pombos para responder a esta questão porque queremos ter certeza de que haja três copas não apenas três cartas de um naipe Note que no pior dos casos podemos selecionar todos os paus ouros e espadas 39 cartas no total antes de escolher um único copas As próximas três cartas serão todas copas então precisaremos escolher 42 cartas para chegar nos três copas EXEMPLO 8 Qual o menor número de códigos de área que são necessários para garantir que os 25 milhões de telefones em um estado possam ser determinados por números de telefones com 10 dígitos Considere que os números de telefone têm a forma NXXNXXXXXX em que os três primeiros dígitos são o código de área N representa um dígito entre 2 e 9 inclusive e X representa qualquer dígito Solução Há oito milhões de números de telefone diferentes na forma NXXXXXX como sabemos pelo Exemplo 8 da Seção 51 Portanto pela generalização do princípio da casa dos pombos entre 25 milhões de telefones pelo menos 25 000 0008 000 000 deles devem ter números idênticos Portanto pelo menos quatro códigos de área são necessários para assegurar que todos os números de 10 dígitos sejam diferentes O Exemplo 9 mesmo não sendo uma aplicação da generalização do princípio da casa dos pombos usa princípios semelhantes EXEMPLO 9 Suponha que um laboratório de ciência da computação tenha 15 estações de trabalho e 10 servidores Um cabo pode ser usado para conectar diretamente uma estação a um servidor Para cada servidor apenas uma conexão direta a este servidor pode ser ativada em qualquer hora Queremos garantir que a qualquer hora qualquer conjunto de 10 ou menos estações de trabalho possa simultaneamente acessar servidores diferentes por meio de conexões diretas Embora possamos fazer isto conectando cada estação diretamente a um servidor usando 150 conexões qual é o número mínimo de conexões diretas necessárias para alcançar este objetivo Solução Suponha que rotulemos as estações de trabalho como W1W2W15 e os servidores como S1 S2 S10 Além disso suponha que conectemos Wk a Sj para k 1 210 e cada um dos W11 W12 W13 W14 e W15 a todos os 10 servidores Teremos um total de 60 conexões diretas Claramente qualquer conjunto de 10 ou menos estações de trabalho pode acessar simultaneamente servidores diferentes Vemos isso a partir da observação de que se a estação de trabalho Wj estiver inclusa com 1 j 10 ela poderá acessar o servidor Sj e para cada estação Wk com k 11 incluso haverá uma estação correspondente Wj com 1 j 10 não incluso então Wk pode acessar o servidor Sj Isto é afirmado porque há pelo menos tantos servidores disponíveis Sj quanto estações Wj com 1 j 10 não incluso Agora suponha que há menos que 60 conexões diretas entre as estações e os servidores Então alguns servidores poderiam ser conectados a no máximo 5910 5 estações Se todos os servidores forem conectados a pelo menos seis estações então haveria no mínimo 6 10 60 conexões diretas Isto significa que os nove servidores restantes não são suficientes para permitir que as outras 10 estações acessem simultaneamente servidores diferentes Conseqüentemente pelo menos 60 conexões diretas são necessárias Seguese que a resposta é 60 Algumas Aplicações Distintas do Princípio da Casa dos Pombos Em muitas aplicações interessantes do princípio da casa dos pombos os objetos que são colocados em caixas devem ser escolhidos de maneira engenhosa Algumas dessas aplicações serão descritas aqui EXEMPLO 10 Durante um mês com 30 dias um time de beisebol joga pelo menos uma partida por dia mas não mais de 45 partidas Mostre que deverá haver um período com alguns dias consecutivos em que o time joga exatamente 14 partidas Solução Considere aj como o número de partidas jogadas até o jésimo dia do mês Então a1 a2 a30 é uma seqüência crescente de números inteiros positivos distintos com 1 aj 45 Além disso a1 14 a2 14 a30 14 é também uma seqüência crescente de números inteiros positivos distintos com 15 aj 14 59 Os 60 números inteiros positivos a1 a2 a30 a1 14 a2 14 a30 14 são todos menores ou iguais a 59 Assim pelo princípio da casa dos pombos dois desses números inteiros são iguais Visto que os números inteiros aj j 1 2 30 são todos distintos e os números inteiros aj 14 j 1 2 30 também são todos distintos deverá haver indícios de i e j com ai aj 14 Isto significa que exatamente 14 partidas foram jogadas do dia j 1 ao dia i EXEMPLO 11 Mostre que entre quaisquer n 1 números inteiros positivos não excedentes a 2n deverá haver um número inteiro que divide um dos outros inteiros Solução Escreva cada um dos n 1 números inteiros a1 a2 an1 como uma potência de 2 vezes um inteiro ímpar Em outras palavras considere aj 2 k j q j para j 1 2 n 1 em que kj é um número inteiro não negativo e qj é ímpar Os inteiros q1 q2 qn 1 são todos números inteiros positivos ímpares menores que 2n Visto que há apenas n inteiros positivos ímpares menores que 2n podemos afirmar que a partir do princípio da casa dos pombos dois dos inteiros q1 q2 qn 1 deverão ser iguais Então há números inteiros i e j tal que qi qj Considere q como o valor comum de qi e qj Assim ai 2 k i q e aj 2 k j q Concluímos que se k i kj então ai divide aj enquanto se k i kj então aj divide ai Uma aplicação engenhosa do princípio da casa dos pombos mostra a existência de uma subseqüência crescente ou decrescente de certa extensão em uma seqüência de números inteiros distintos Algumas definições serão revisadas antes de esta aplicação ser apresentada Suponha que a1 a2 aN seja uma seqüência de números reais Uma subseqüência desta seqüência é uma seqüência de forma ai1 ai2 aim em que 1 i1 i2 im N Assim uma subseqüência é uma seqüência obtida a partir da seqüência original pela inclusão de alguns dos termos da seqüência original em sua ordem original Uma seqüência é chamada de estritamente crescente se cada termo for maior que aquele que o precede e é chamada de estritamente decrescente se cada termo for menor que aquele que o precede TEOREMA 3 Toda seqüência de n2 1 números reais distintos contém uma subseqüência de extensão n 1 que é estritamente crescente ou estritamente decrescente Daremos um exemplo antes de apresentar a demonstração do Teorema 3 EXEMPLO 12 A seqüência 8 11 9 1 4 6 12 10 5 7 contém 10 termos Note que 10 32 1 Há quatro subseqüências crescentes de extensão quatro ou seja 1 4 6 12 1 4 6 7 1 4 6 10 e 1 4 5 7 Há também uma subseqüência decrescente de extensão quatro ou seja 11 9 6 5 A demonstração do teorema será agora apresentada Demonstração Considere a1 a2 an²1 como uma seqüência de n2 1 números reais distintos Associamos um par ordenado a cada termo da seqüência ou seja associamos ik dk ao termo ak em que ik é a extensão da maior subseqüência crescente começando em ak e dk é a extensão da maior subseqüência decrescente começando em ak Suponha que não haja subsequências crescentes ou decrescentes de extensão n 1 Então ik e dk são números inteiros positivos menores que ou iguais a n para k 1 2 n² 1 Assim pela regra do produto há n2 pares ordenados possíveis para ik dk Pelo princípio da casa dos pombos dois desses n2 1 pares ordenados são iguais Em outras palavras existem termos as e at com s t tal que is it e ds dt Mostraremos que isto é impossível Visto que os termos da seqüência são distintos ou as at ou as at Se as at então como is it pode ser construída uma subseqüência crescente de extensão it 1 que começa em as tomando as seguida por uma subseqüência crescente de extensão it que começa em at Isto é uma contradição Analogamente se as at pode ser mostrado que ds deve ser maior que dt o que é uma contradição O último exemplo mostra como a generalização do princípio da casa dos pombos pode ser aplicada a uma importante parte da análise combinatória chamada de teoria de Ramsey criada pela matemático inglês F P Ramsey Em geral a teoria de Ramsey trabalha com a distribuição de subconjuntos de elementos de conjuntos EXEMPLO 13 Suponha que em um grupo de seis pessoas cada par de indivíduos seja formado por dois amigos ou dois inimigos Mostre que há três amigos mútuos ou três inimigos mútuos no grupo Solução Considere A como uma das seis pessoas Das cinco outras pessoas no grupo há três ou mais que são amigos de A ou três ou mais que são inimigos de A Seguindo a generalização do princípio da casa dos pombos quando cinco objetos são divididos em dois conjuntos um dos conjuntos tem pelo menos 523 elementos Neste caso suponha que B C e D são amigos de A Se duas das três pessoas são amigas então esses dois e A formam um grupo de três amigos mútuos Por outro lado B C e D formam um conjunto de três inimigos mútuos A demonstração neste segundo caso quando há três ou mais inimigos de A procede da mesma maneira O número de Ramsey Rm n em que m e n são números inteiros positivos maiores que ou iguais a 2 indica o número mínimo de pessoas em uma festa em que há m amigos mútuos ou n inimigos mútuos supondo que todo par de pessoas na festa são amigos ou inimigos O Exemplo 13 mostra que R3 3 6 Concluímos que R3 3 6 porque em um grupo de cinco pessoas em que cada duas pessoas são amigos ou inimigos poderá não haver três amigos mútuos ou três inimigos mútuos veja o Exercício 24 É possível demonstrar algumas propriedades úteis sobre os números de Ramsey mas para a maior parte é difícil encontrar seus valores exatos Note que por simetria pode ser mostrado que Rm n Rn m veja o Exercício 28 Temos também que R2 n n para todo número inteiro positivo n 2 veja o Exercício 27 São conhecidos apenas nove valores exatos dos números de Ramsey Rm n com 3 m n incluindo R4 4 18 Apenas limites são conhecidos para muitos outros números de Ramsey incluindo R5 5 que é conhecido por satisfazer 43 R5 5 49 O leitor interessado em aprender mais sobre os números de Ramsey deverá consultar MiRo91 ou GrRoSp90 Exercícios 1 Mostre que em qualquer conjunto de seis aulas no qual cada encontro acontece regularmente uma vez na semana em um determinado dia da semana deve haver dois desses encontros no mesmo dia supondo que não haja aulas nos finais de semana 2 Mostre que se há 30 estudantes em uma sala então pelo menos dois têm sobrenomes que começam com a mesma letra 3 Uma gaveta contém doze meias marrons e doze meias pretas todas únicas Um homem pega as meias aleatoriamente no escuro a Quantas meias deverão ser pegas para se ter certeza de que pelo menos duas são da mesma cor b Quantas meias deverão ser pegas para se ter certeza de que pelo menos duas são pretas 4 Um boliche contém 10 bolas vermelhas e 10 bolas azuis Uma mulher escolhe as bolas aleatoriamente sem olhar para elas a Quantas bolas deverão ser pegas para se ter certeza de que pelo menos três bolas são da mesma cor b Quantas bolas deverão ser pegas para se ter certeza de que pelo menos três são azuis 5 Mostre que entre um grupo de cinco números inteiros não necessariamente consecutivos há dois com o mesmo resto quando divididos por 4 6 Considere d como um número inteiro positivo Mostre que entre um grupo de d 1 números inteiros não necessariamente consecutivos há dois com exatamente o mesmo resto quando divididos por d 7 Considere n como um número inteiro positivo Mostre que em um conjunto de n inteiros consecutivos há exatamente um número divisível por n 8 Mostre que se f for uma função de S para T em que S e T são conjuntos finitos com S T então há elementos s1 e s2 em S tal que f s1 f s2 ou em outras palavras f não é injetora 9 Qual é o número mínimo de estudantes vindos dos 50 estados americanos que devem ser inscritos em uma universidade para garantir que pelo menos 100 venham do mesmo estado 10 Considere xi yi i 1 2 3 4 5 como um conjunto de cinco pontos distintos com coordenadas inteiras no plano xy Mostre que o ponto médio da linha que junta pelo menos um par desses pontos tem coordenadas inteiras 11 Considere xi yi zi i 1 2 3 4 5 6 7 8 9 um conjunto de nove pontos distintos com coordenadas inteiras no espaço xyz Mostre que o ponto médio de pelo menos um par desses pontos tem coordenadas inteiras 12 Quantos pares ordenados de números inteiros a b são necessários para garantir que haja dois pares ordenados a1 b1 e a2 b2 tal que a1 mod 5 a2 mod 5 e b1 mod 5 b2 mod 5 13 a Mostre que se cinco números inteiros são selecionados a partir dos oito primeiros números inteiros positivos deverá haver um par desses inteiros cuja soma seja igual a 9 b A conclusão do item a será verdadeira se quatro inteiros em vez de cinco forem selecionados 14 a Mostre que se sete números inteiros são selecionados a partir dos 10 primeiros números inteiros positivos deverá haver pelo menos dois pares desses inteiros cuja soma seja igual a 11 b A conclusão do item a será verdadeira se seis inteiros em vez de sete forem selecionados 15 Quantos números devem ser selecionados a partir do conjunto 1 2 3 4 5 6 para garantir que pelo menos um par desses números some 7 16 Quantos números devem ser selecionados a partir do conjunto 1 3 5 7 9 11 13 15 para garantir que pelo menos um par desses números some 16 17 Uma companhia armazena os produtos em um depósito O armazenamento de caixas nesse depósito é especificado por seus corredores localização nos corredores e prateleiras Há 50 corredores 85 localizações horizontais em cada corredor e 5 prateleiras no depósito Qual é o menor número de produtos que a companhia pode ter para que pelo menos dois produtos sejam estocados na mesma caixa 18 Suponha que haja nove estudantes em uma classe de matemática discreta em uma pequena faculdade a Mostre que a classe deve ter pelo menos cinco homens ou pelo menos cinco mulheres b Mostre que a classe deve ter pelo menos três homens ou pelo menos sete mulheres 19 Suponha que todo estudante em uma classe de matemática discreta de 25 alunos seja um calouro um veterano ou um aluno júnior a Mostre que há pelo menos nove calouros nove veteranos ou nove juniores na sala b Mostre que há pelo menos três calouros 19 veteranos ou 5 juniores na sala 20 Encontre uma subsequência crescente de extensão máxima e uma subsequência decrescente de extensão máxima a partir da sequência 22 5 7 2 23 10 15 21 3 17 21 Construa uma sequência de 16 números inteiros positivos que não tenha subsequência crescente ou decrescente de cinco termos 22 Mostre que se houver 101 pessoas de alturas diferentes paradas em fila é possível encontrar 11 pessoas na ordem que estão paradas em uma sequência de alturas crescente ou decrescente 23 Descreva um algoritmo em pseudocódigo para produzir a maior subsequência crescente ou decrescente de uma sequência de números inteiros distintos 24 Mostre que em um grupo de cinco pessoas em que duas pessoas são amigas ou inimigas não há necessariamente três amigos mútuos ou três inimigos mútuos 25 Mostre que em um grupo de 10 pessoas em que duas pessoas são amigas ou inimigas há três amigos mútuos ou quatro inimigos mútuos e que há três inimigos mútuos ou quatro amigos mútuos 26 Use o Exercício 25 para mostrar que entre um grupo de 20 pessoas em que duas pessoas são amigas ou inimigas há quatro amigos mútuos ou quatro inimigos mútuos 27 Mostre que se n for um número inteiro positivo com n 2 então o número de Ramsey Rn 2 é igual a n 28 Mostre que se m e n forem números inteiros positivos com m 2 e n 2 então os números de Ramsey Rm n e Rn m são iguais 29 Mostre que há pelo menos seis pessoas na Califórnia população 36 milhões com as mesmas três iniciais que nasceram no mesmo dia do ano mas não necessariamente no mesmo ano Suponha que todos tenham três iniciais 30 Mostre que se houver 100 000 000 pessoas no Brasil que ganham salário menores que 1 000 000 reais então há duas pessoas que ganharam exatamente a mesma quantia incluindo os centavos no ano passado 31 Há 38 horários diferentes de aula em uma universidade Se há 677 classes diferentes quantas salas diferentes serão necessárias 32 Uma rede de computadores é formada por seis computadores Cada computador é conectado diretamente a pelo menos um dos outros computadores Mostre que há pelo menos dois computadores na rede que estão diretamente conectados ao mesmo número de outros computadores 33 Uma rede de computadores é formada por seis computadores Cada computador é conectado diretamente a zero ou mais outros computadores Mostre que há pelo menos dois computadores na rede que estão diretamente conectados ao mesmo número de outros computadores Dica É impossível ter um computador não ligado a nenhum dos outros e um computador ligado a todos os outros 34 Encontre o menor número de cabos que são necessários para conectar oito computadores a quatro impressoras a fim de garantir que quatro computadores estejam ligados diretamente a quatro impressoras diferentes Justifique sua resposta 35 Encontre o menor número de cabos que são necessários para conectar 100 computadores a 20 impressoras para garantir que 20 computadores possam acessar diretamente 20 impressoras diferentes Aqui as hipóteses sobre os cabos e computadores são as mesmas que as do Exemplo 9 Justifique sua resposta 36 Demonstre que em uma festa em que há pelo menos duas pessoas há duas pessoas que conhecem o mesmo número de pessoas na festa 37 Um campeonato de luta dura 75 horas Aqui por uma hora entendemos um período que começa em uma hora exata como 13h e vai até a próxima hora O lutador teve pelo menos uma competição por hora mas não mais que um total de 125 competições Mostre que há um período de horas consecutivas em que o lutador teve exatamente 24 competições 38 A proposição do Exercício 37 será verdadeira se 24 for substituído por a 2 b 23 c 25 d 30 39 Mostre que se f for uma função de S para T em que S e T são conjuntos finitos e m PlSTQ então pelo menos m elementos de S têm a mesma imagem em T Ou seja mostre que há elementos distintos s1 s2 sm de S tal que f s1 f s2 f sm 40 Há 51 casas em uma rua Cada casa tem um número entre 1000 e 1099 inclusive Mostre que pelo menos duas casas têm números que são inteiros consecutivos 41 Considere x como um número irracional Mostre que para um número inteiro positivo j não excedente a n o valor absoluto da diferença entre j x e o inteiro mais próximo a j x é menor que 1n 42 Considere n1 n2 nt como números inteiros positivos Mostre que se n1 n2 nt l 1 objetos forem colocados em t caixas então para i i 1 2 t a iésima caixa terá pelo menos ni objetos 43 Uma demonstração do Teorema 3 baseada na generalização do princípio da casa dos pombos é apresentada neste exercício A notação usada é a mesma da demonstração no texto a Suponha que ik n para k 1 2 n2 1 Use a generalização do princípio da casa dos pombos para mostrar que há n 1 termos ak1 ak2 akn1 com i k1 i k2 i kn1 em que 1 k1 k2 kn1 n2 b Mostre que ak1 ak2 para j 1 2 n Dica Suponha que akj akj1 e mostre que isto implica que i kj i kj1 o que é uma contradição c Use os itens a e b para mostrar que se não houver subsequência crescente de extensão n 1 então deverá haver uma subsequência decrescente com a mesma extensão 53 Permutações e Combinações Introdução Muitos problemas de contagem podem ser resolvidos encontrandose o número de maneiras de organizar um número específico de elementos distintos de um conjunto de determinado tamanho em que a ordem desses elementos é relevante Muitos outros problemas de contagem podem ser resolvidos encontrandose o número de maneiras para escolher um número determinado de elementos a partir de um conjunto de determinado tamanho em que a ordem dos elementos escolhidos não é relevante Por exemplo de quantas maneiras podemos escolher três alunos de um grupo de cinco estudantes para ficarem em fila para uma foto Quantos comitês diferentes de três estudantes podem ser formados a partir de um grupo com quatro estudantes Nesta seção desenvolveremos métodos para responder a tais questões Permutações Começaremos pela resolução da primeira questão proposta na introdução desta seção assim como das questões relacionadas a ela EXEMPLO 1 De quantas maneiras podemos escolher três alunos de um grupo de cinco estudantes para ficarem em fila para uma foto De quantas maneiras podemos organizar todos os cinco estudantes em fila para uma foto Solução Primeiro note que a ordem na qual selecionamos os estudantes é relevante Há cinco maneiras de escolher o primeiro estudante para ficar no começo da fila Uma vez escolhido este estudante há quatro maneiras de escolher o segundo da fila Depois do primeiro e do segundo estudante escolhidos há três maneiras de escolher o terceiro estudante na fila Pela regra do produto há 5 4 3 60 maneiras de escolher três estudantes de um grupo de cinco para ficarem em fila para uma foto Para organizar os cinco estudantes em uma fila para uma foto temos cinco formas para selecionar o primeiro quatro para o segundo três para o terceiro duas para o quarto e uma para o quinto Conseqüentemente temos 5 4 3 2 1 120 maneiras de organizar os cinco estudantes em uma fila para uma foto O Exemplo 1 mostra como arranjos ordenados de objetos distintos podem ser contados Isto nos conduz a algumas terminologias Uma permutação de um conjunto de objetos distintos é um arranjo ordenado desses objetos Interessamonos também por arranjos ordenados de alguns dos elementos de um conjunto Um arranjo ordenado de r elementos de um conjunto é chamado de rpermutação EXEMPLO 2 Considere S 1 2 3 O arranjo ordenado 3 1 2 é uma permutação de S O arranjo ordenado 3 2 é uma 2permutação de S O número de rpermutações de um conjunto com n elementos é indicado por Pn r Podemos encontrar Pn r usando a regra do produto EXEMPLO 3 Considere S a b c A 2permutação de S são arranjos ordenados a b a c b a b c c a e c b Conseqüentemente há seis 2permutações deste conjunto com três elementos Para ver que há sempre seis 2permutações de um conjunto com três elementos note que há três maneiras de escolher o primeiro elemento de um arranjo e duas maneiras de escolher o segundo elemento do arranjo porque este deve ser diferente do primeiro Pela regra do produto temos que P3 2 3 2 6 Usaremos agora a regra do produto para encontrar a fórmula para Pnr sempre que n e r forem números inteiros positivos com 1 r n TEOREMA 1 Se n for um número inteiro positivo e r um número inteiro com 1 r n então há Pnr nn 1n 2 n r 1 rpermutações de um conjunto com n elementos distintos Demonstração Usaremos a regra do produto para demonstrar que esta fórmula está correta O primeiro elemento da permutação pode ser escolhido de n maneiras porque há n elementos no conjunto Há n 1 maneiras de escolher o segundo elemento da permutação porque há n 1 elementos que sobraram no conjunto depois de utilizar o elemento da primeira posição Do mesmo modo há n 2 maneiras de escolher o terceiro elemento e assim por diante até que tenha exatamente n r 1 n r 1 maneiras de escolher o résimo elemento Conseqüentemente pela regra do produto há nn 1n 2 n r 1 r permutações do conjunto Note que Pn0 1 sempre que n for um número inteiro não negativo porque há exatamente uma maneira de ordenar zero elementos Isto é há exatamente uma lista sem elementos ou seja uma lista vazia Apresentaremos agora um corolário muito útil do Teorema 1 COROLÁRIO 1 Se n e r são números inteiros com 0 r n então Pnr nn r Demonstração Quando n e r são números inteiros com 1 r n pelo Teorema 1 temos Pnr nn 1n 2n r 1 nn r Como nn 0 nn 1 sempre que n for um número inteiro não negativo vemos que aquela fórmula Pnr nn r também é válida para quando r 0 Pelo Teorema 1 sabemos que se n for um número inteiro positivo então Pnn n Mostraremos este resultado com alguns exemplos EXEMPLO 4 Quantas maneiras há para selecionar o vencedor do primeiro do segundo e do terceiro lugar a partir de 100 pessoas diferentes que participaram de um concurso Solução Como a ordem é relevante já que cada pessoa ganha um prêmio o número de maneiras de selecionar os três vencedores é o número de escolhas ordenadas de três elementos de um grupo de 100 elementos isto é o número de 3permutações de um conjunto de 100 elementos Conseqüentemente a resposta será P1003 100 99 98 970 200 EXEMPLO 5 Suponha que haja oito atletas em uma corrida O vencedor recebe medalha de ouro o segundo lugar medalha de prata e o terceiro medalha de bronze Quantas maneiras diferentes há para ganhar essas medalhas se todos os resultados possíveis da corrida podem ocorrer e não há nenhum empate Solução O número de maneiras diferentes de distribuir as medalhas é o número de 3permutações de um conjunto com oito elementos Assim há P8 3 8 7 6 336 maneiras possíveis de ganhar as medalhas EXEMPLO 6 Suponha que uma vendedora tenha de visitar oito cidades diferentes Ela deve começar sua viagem por uma determinada cidade mas depois pode visitar as outras sete na ordem em que ela quiser Quantas ordens são possíveis para a vendedora visitar as cidades Solução O número de caminhos possíveis entre as cidades é o número de permutações de sete elementos porque a primeira cidade é determinada mas as sete restantes podem ser ordenadas arbitrariamente Conseqüentemente há 7 7 6 5 4 3 2 1 5040 maneiras para a vendedora escolher seu roteiro Se por exemplo ela desejar encontrar um caminho entre as cidades que tenha a menor distância deve tomar a distância total para cada caminho possível e deve considerar um total de 5040 caminhos EXEMPLO 7 Quantas permutações das letras ABCDEFGH contêm a seqüência ABC Solução Visto que as letras ABC devem ser consideradas como um bloco podemos resolver esta questão encontrando o número de permutações de seis objetos ou seja o bloco ABC e as letras individuais D E F G e H Como os seis objetos podem aparecer em qualquer ordem há 6 720 permutações das letras ABCDEFGH nas quais ABC aparecem como um bloco Combinações Agora estudaremos a seleção não ordenada de objetos Comecemos pela resolução de uma questão proposta na introdução desta seção EXEMPLO 8 Quantos comitês diferentes de três estudantes podem ser formados a partir de um grupo de quatro estudantes Solução Para responder a esta questão precisamos apenas encontrar o número de subconjuntos com três elementos a partir de um conjunto com os quatro estudantes Vemos que há quatro subconjuntos um para cada um dos quatro estudantes já que escolher quatro deles é o mesmo que escolher um para ser omitido do grupo Isto significa que há quatro maneiras de escolher três alunos para o comitê em que a ordem de escolha desses estudantes não é relevante O Exemplo 8 mostra que muitos problemas de contagem podem ser resolvidos encontrandose o número de subconjuntos de um determinado tamanho a partir de um conjunto com n elementos em que n é um número inteiro positivo Uma rcombinação de elementos de um conjunto é uma seleção não ordenada de r elementos a partir do conjunto Então uma rcombinação é simplesmente um subconjunto do conjunto com r elementos EXEMPLO 9 Considere S como o conjunto 1 2 3 4 Então 1 3 4 é uma 3combinação de S O número de rcombinações de um conjunto com n elementos distintos é representado por Cnr Note que Cnr é também representado por n r e é chamado de coeficiente binomial Aprenderemos a origem dessa terminologia na Seção 54 EXEMPLO 10 Vemos que C4 2 6 porque as 2combinações de a b c d são os seis subconjuntos ab a c a d b c b d e c d Podemos determinar o número de rcombinações de um conjunto com n elementos usando a fórmula para o número de rpermutações de um conjunto Para fazer isso note que as rpermutações de um conjunto podem ser obtidas a partir primeiramente da formação de rcombinações e depois pelo ordenamento dos elementos nessas combinações A demonstração do Teorema 2 que apresenta o valor de Cnr é baseada nesta observação TEOREMA 2 O número de rcombinações de um conjunto com n elementos em que n é um número inteiro não negativo e r é um inteiro com 0 r n é igual a Cnr n r n r Demonstração As rpermutações de um conjunto podem ser obtidas a partir da formação de rcombinações Cn r do conjunto e então pelo ordenamento desses elementos em cada rcombinação o que pode ser feito de Prr maneiras Conseqüentemente Pnr Cn r Pr r Isto implica que Cnr Pnr Prr nn r r n r n r A fórmula no Teorema 2 embora explícita não é útil quando Cnr é computado com valores altos para n e r A razão para tal afirmação é que computar valores exatos de fatoriais é interessante apenas em números inteiros pequenos e quando a aritmética de ponto flutuante é usada a fórmula do Teorema 2 pode produzir um valor que não é inteiro Ao computar Cnr primeiro note que quando eliminamos n r do numerador e do denominador da expressão para Cnr no Teorema 2 obtemos Cnr nn 1 n r 1 r Conseqüentemente para computar Cnr você pode eliminar todos os termos no fatorial maior no denominador a partir do numerador e do denominador então multiplicar todos os termos que não forem cancelados no numerador e por fim dividir pelo menor fatorial no denominador Quando fazemos este cálculo manualmente em vez de utilizar a calculadora vale a pena trabalhar com fatores comuns no numerador nn 1 n r 1 e no denominador r Note que muitas calculadoras têm uma função para Cnr que pode ser usada para valores relativamente pequenos de n e r e muitos programas computacionais podem ser usados para encontrar Cnr Tais funções podem ser chamadas de chosen k ou binomn k O Exemplo 11 mostra como Cn k é computado quando k é relativamente pequeno comparado a n e quando k é próxmo de n Mostra também uma identidadechave dos números Cn k EXEMPLO 11 Quantas mãos de pôquer de cinco cartas podem ser retiradas a partir de um baralho de 52 cartas Quantas formas de selecionar 47 cartas a partir de um baralho de 52 cartas são possíveis Solução Visto que a ordem com que as cinco cartas são retiradas de um baralho de 52 cartas não é relevante há C52 5 52 5 47 mãos diferentes de cinco cartas que podem ser tiradas Para computar o valor de C52 5 primeiro dividese o numerador e o denominador por 47 para obter C525525150494854321 Esta expressão pode ser simplificada dividindose 50 por 5 do denominador para obter um fator 10 no numerador então dividir 48 por 4 para obter um fator 12 no numerador depois dividir 51 por 3 e obter um fator 17 no numerador e finalmente dividir 52 por 2 para obter um fator 26 no numerador Encontramos C52 526171049122 598 960 Conseqüentemente há 2 598 960 mãos de pôquer diferentes de cinco cartas que podem ser tiradas a partir de um baralho com 52 cartas Note que há C52 4752475 maneiras diferentes de selecionar 47 cartas de um baralho com 52 Mas não precisamos computar esse valor porque C52 47C52 5 Apenas a ordem dos fatores 5 e 47 é diferente nos denominadores nas fórmulas para essas quantias Vemos que há também 2 598 960 maneiras diferentes de selecionar 47 cartas a partir de um baralho com 52 cartas No Exemplo 11 observamos que C52 5C52 47 Este caso especial de identidade útil para os números de rcombinações de um conjunto é dado no Corolário 2 COROLÁRIO 2 Considere n e r como números inteiros não negativos com r n Então Cn rCn nr Demonstração A partir do Teorema 2 temos que Cnrnrnr e Cnnrnnrnnrnnrr Assim CnrCnnr Podemo também demonstrar o Corolário 2 usando uma demonstração que mostra que os dois lados da equação no Corolário 2 fazem a contagem dos mesmos objetos usando razões diferentes Descreveremos este importante tipo de demonstração na Definição 1 DEFINIÇÃO 1 Uma demonstração combinatória de uma identidade é aquela que usa argumentos de contagem para demonstrar que os dois lados de uma identidade fazem a contagem dos mesmos objetos mas de maneiras diferentes Muitas identidades que envolvem coeficientes binomiais podem ser demonstradas por meio das demonstrações combinatórias ou combinatoriais Fornecemos agora uma demonstração combinatória do Corolário 2 Demonstração Suponha que S seja um conjunto com n elementos Cada subconjunto A de S com r elementos corresponde a um subconjunto de S com nr elementos ou seja A Conseqüentemente Cn rCn nr EXEMPLO 12 Quantas maneiras há para selecionar cinco jogadores de um time de basquete com 10 membros para disputar uma partida em outra escola Solução A resposta é dada pelo número de 5combinações de um conjunto com 10 elementos Pelo Teorema 2 o número de tais combinações é C10 51055252 EXEMPLO 13 Um grupo de 30 pessoas foi treinado a fim de serem formados astronautas para ir a uma primeira missão a Marte Quantas maneiras de selecionar uma tripulação de seis pessoas para embarcarem nessa missão são possíveis Suponha que todos os membros da tripulação têm a mesma função Solução O número de maneiras de selecionar uma tripulação de seis pessoas a partir de um grupo de 30 é o número de 6combinações de um conjunto de 30 elementos porque a ordem dessas pessoas escolhidas não é relevante Pelo Teorema 2 o número de tais combinações é C30 630624302928272625654321593 775 EXEMPLO 14 Quantas cadeias de bits de extensão n contêm exatamente r 1s Solução As posições de r 1s em uma cadeia de bits de extensão n formam uma rcombinação do conjunto com 1 2 3 n Assim há Cnr cadeias de bits de extensão n que contêm exatamente r 1s EXEMPLO 15 Suponha que haja 9 membros da faculdade no departamento de matemática e 11 no departamento de ciência da computação Quantas maneiras de selecionar um comitê para desenvolver um curso de matemática discreta na escola são possíveis se o comitê é formado por três membros do departamento de matemática e quatro do departamento de ciência da computação Solução Pela regra do produto a resposta é o produto dos números de 3combinações de um conjunto com nove elementos e o número de 4combinações de um conjunto com 11 elementos Pelo Teorema 2 o número de maneiras de selecionar o comitê é C9 3C11 493611478433027 720 Exercícios 1 Liste todas as permutações de a b c 2 Quantas permutações diferentes são possíveis a partir do conjunto a b c d e f g 3 Quantas permutações de a b c d e f g terminam com a 4 Considere S1 2 3 4 5 a Liste todas as 3permutações de S b Liste todas as 3combinações de S 5 Encontre o valor para cada uma das quantidades abaixo a P6 3 b P6 5 c P8 1 d P8 5 c pelo menos sete 1s d pelo menos três 1s f P10 9 6 Encontre o valor para cada uma das quantidades abaixo a C5 1 b C5 3 c C8 4 d C8 8 e C8 0 f C12 6 7 Encontre o número de 5permutações de um conjunto com nove elementos 8 Em quantas ordens diferentes cinco atletas podem terminar uma corrida sem empates 9 Quantas possibilidades há para as posições de primeiro segundo e terceiro lugares em uma corrida de cavalos com 12 cavalos se todas as ordens de término são possíveis 10 Há seis candidatos diferentes para governador de um estado De quantas maneiras diferentes os nomes dos candidatos podem ser impressos na cédula de voto 11 Quantas cadeias de bits de extensão 10 contêm a exatamente quatro 1s b no máximo quatro 1s c pelo menos quatro 1s d um número igual de 0s e 1s 12 Quantas cadeias de bits de extensão 12 contêm a exatamente três 1s b no máximo três 1s c pelo menos três 1s d um número igual de 0s e 1s 13 Um grupo contém n homens e n mulheres Há quantas maneiras possíveis de organizar essas pessoas em uma fila se os homens e as mulheres devem ficar alternados 14 De quantas maneiras um conjunto de dois números inteiros positivos menores que 100 podem ser escolhidos 15 De quantas maneiras um conjunto com cinco letras pode ser selecionado a partir do alfabeto da língua inglesa 16 Um conjunto de 10 elementos pode ter quantos subconjuntos com um número ímpar de elementos 17 Um conjunto com 100 elementos pode ter quantos subconjuntos com mais de dois elementos 18 Uma moeda é jogada oito vezes e em cada lançamento temse cara ou coroa Quantos resultados são possíveis a no total b com exatamente três caras c com pelo menos três caras d com o mesmo número de caras e coroas 19 Uma moeda é jogada 10 vezes e em cada lançamento temse cara ou coroa Quantos resultados são possíveis a no total b com exatamente duas caras c com no máximo três coroas d com o mesmo número de caras e coroas 20 Quantas cadeias de bits de extensão 10 têm a exatamente três 0s b mais 0s que 1s 21 Quantas permutações das letras ABCDEFG contêm a a sequência BCD b a sequência CFGA c as sequências BA e GF d as sequências ABC e DE e as sequências ABC e CDE f as sequências CBA e BED 22 Quantas permutações das letras ABCDEFGH contêm a a sequência ED b a sequência CDE c as sequências BA e FGH d as sequências AB DE e GH e as sequências CAB e BED f as sequências BCA e ABF 23 Há quantas maneiras possíveis para que oito homens e cinco mulheres fiquem em uma fila de modo que haja duas mulheres uma ao lado da outra Dica Primeiro posicione os homens e depois considere as posições possíveis para as mulheres 24 Há quantas maneiras possíveis para que 10 mulheres e seis homens fiquem em uma fila de forma que não haja dois homens um ao lado do outro Dica Primeiro posicione as mulheres e depois considere as posições possíveis para os homens 25 Cem bilhetes numerados de 1 2 3 100 são vendidos a 100 pessoas diferentes para uma atração Quatro prêmios diferentes são disputados inclusive o grande prêmio uma viagem para o Taiti Há quantas maneiras possíveis de ganhar os prêmios se a não há restrições b a pessoa com o bilhete 47 ganhar o grande prêmio c a pessoa com o bilhete 47 ganhar um dos prêmios d a pessoa com o bilhete 47 não ganhar um prêmio e as pessoas com os bilhetes 19 e 47 ganharem prêmios f as pessoas com os bilhetes 19 47 e 73 ganharem prêmios g as pessoas com os bilhetes 19 47 73 e 97 ganharem prêmios h nenhuma das pessoas com os bilhetes 19 47 73 e 97 ganharem prêmios i o vencedor do grande prêmio for uma pessoa com o bilhete 19 47 73 ou 97 j as pessoas com os bilhetes 19 e 47 ganharem prêmios mas as pessoas com os bilhetes 73 e 97 não ganharem 26 Treze pessoas de um time de softball aparecem para um jogo a Quantas maneiras de escolher 10 jogadores para entrar em campo são possíveis b Quantas maneiras de designar as 10 posições são possíveis selecionandose os jogadores a partir das 13 pessoas que apareceram c Das 13 pessoas que apareceram três são mulheres Há quantas maneiras possíveis de escolher os 10 jogadores se pelo menos um desses jogadores deve ser uma mulher 27 Um clube tem 25 membros a Quantas maneiras de escolher quatro membros do clube para servir no comitê executivo são possíveis b Quantas maneiras de escolher um presidente vicepresidente secretário e tesoureiro do clube em que nenhuma pessoa pode ter mais que uma função são possíveis 28 Um professor escreve 40 questões do tipo falsoverdadeiro de matemática discreta Das proposições dessas questões 17 são verdadeiras Se as questões podem ser organizadas em qualquer ordem quantos cadernos de respostas diferentes são possíveis 29 Quantas 4permutações de números inteiros positivos não excedentes a 100 contêm três números inteiros consecutivos k k1 k2 na ordem correta a em que esses números inteiros consecutivos podem talvez ser separados por outros inteiros na permutação b em que eles estão em posições consecutivas na permutação 30 Há sete mulheres e nove homens em uma faculdade no departamento de matemática a Quantas maneiras de selecionar um comitê de cinco membros do departamento são possíveis se pelo menos uma mulher deve estar no comitê b Quantas maneiras de selecionar um comitê de cinco membros do departamento são possíveis se pelo menos uma mulher e um homem devem estar no comitê 31 O alfabeto da língua inglesa contém 21 consoantes e cinco vogais Quantas sequências de seis letras minúsculas do alfabeto contêm a exatamente uma vogal b exatamente duas vogais c pelo menos uma vogal d pelo menos duas vogais 32 Quantas sequências de seis letras minúsculas do alfabeto da língua inglesa contêm a a letra a b as letras a e b c as letras a e b em posições consecutivas com a precedendo b com todas as letras distintas d as letras a e b em que a está à esquerda de b em uma sequência com todas as letras distintas 33 Suponha que um departamento tenha 10 homens e 15 mulheres Quantas maneiras de formar um comitê com seis membros são possíveis se ele deve ter o mesmo número de homens e mulheres 34 Suponha que um departamento tenha 10 homens e 15 mulheres Quantas maneiras de formar um comitê com seis membros são possíveis se ele deve ter mais mulheres que homens 35 Quantas cadeias de bits contêm exatamente oito 0s e dez 1s se todo 0 deve ser seguido imediatamente por um 1 36 Quantas cadeias de bits contêm exatamente cinco 0s e quatorze 1s se todo 0 deve ser seguido imediatamente por dois 1s 37 Quantas cadeias de bits de extensão 10 contêm pelo menos três 1s e três 0s 38 Quantas maneiras de selecionar 12 países na ONU para servir em um conselho são possíveis se 3 são selecionados a partir de um bloco de 45 4 são selecionados a partir de um bloco de 57 e os outros a partir dos 69 países restantes 39 Quantas placas de identificação de carro são possíveis considerandose que elas são compostas por três letras seguidas de três dígitos sendo que nenhuma letra ou dígito aparece duas vezes 40 Há quantas maneiras de seis pessoas sentaremse em uma mesa circular onde os assentos são considerados os mesmos se eles podem ser obtidos por uma rotação da mesa 41 Há quantas maneiras possíveis de terminar uma corrida de cavalos com três cavalos se podem ocorrer empates Nota Dois ou três cavalos podem empatar 42 Há quantas maneiras possíveis de terminar uma corrida de cavalos com quatro cavalos se podem ocorrer empates Nota Qualquer número de cavalos pode empatar 43 Há seis atletas em uma corrida de 100 metros Quantas maneiras de ganhar as três medalhas são possíveis se podem ocorrer empates O atleta ou os atletas que terminarem com o melhor tempo recebem a medalha de ouro o atleta ou os atletas que terminarem com um corredor à frente recebem medalha de prata e o atleta ou os atletas que terminarem com dois corredores à frente recebem a medalha de bronze 44 Este procedimento é usado para desempatar os jogos nos campeonatos da Copa do Mundo de Futebol Cada time escolhe cinco jogadores em uma ordem prescrita Cada um desses jogadores chuta um pênalti com um jogador do primeiro time seguido do jogador do segundo time e assim por diante seguindo a ordem especifica dos jogadores Se o placar continuar empatado no final da primeira rodada de 10 pênaltis o procedimento é repetido Se o placar continuar empatado na segunda rodada um lance de mortesúbita acontece sendo que o primeiro time que marcar sem ter um gol de resposta vence sem contestações a Quantos placares diferentes são possíveis se o jogo terminar na primeira rodada de 10 pênaltis sendo que quando a rodada termina é impossível para um time igualar o número de gols do outro time b Quantos placares diferentes são possíveis para a primeira e a segunda rodada se o jogo termina na segunda rodada c Quantos placares são possíveis para um conjunto completo de rodadas de pênaltis se o jogo termina com não mais de 10 chutes adicionais depois das duas rodadas de cinco chutes para cada time 54 Coeficientes Binomiais Como vimos na Seção 53 o número de rcombinações de um conjunto com n elementos é geralmente representado por n r Esse número também é chamado de coeficiente binomial porque esses números ocorrem como coeficientes na expansão das potências de expressões binomiais tais como abn Discutiremos o binômio de Newton que nos dá uma potência de uma expressão binomial como uma soma de termos que envolvem coeficientes binomiais Demonstraramos esse binômio por meio da demonstração combinatorial Mostraremos também como as demonstrações combinatoriais podem ser usadas para estabelecer algumas das mais diferentes identidades que expressam as relações entre os coeficientes binomiais O Binômio de Newton O binômio de Newton fornece os coeficientes da expansão de potência das expressões binomiais Uma expressão binomial é simplesmente a soma de dois termos tais como x y Os termos podem ser produtos de constantes e variáveis mas isso não vem ao acaso aqui O Exemplo 1 mostra por que esse teorema é aplicado EXEMPLO 1 A expansão de x y3 pode ser encontrada usandose a razão combinatória em vez de multiplicar os três termos Quando xy3 xyxyxy é expandido todos os produtos de um termo na primeira soma um termo na segunda soma e um termo na terceira soma são adicionados Termos da forma x3 x2y xy2 e y3 aparecem Para obter um termo na forma xr um x deve ser escolhido em cada uma das somas e isto pode ser feito de apenas uma maneira Então o termo x3 do produto tem um coeficiente 1 Para obter um termo na forma x2y um x deve ser escolhido em duas dessas três somas e consequentemente um y na outra soma Assim o número de tais termos é o número de 2combinações de três objetos ou seja 3 2 Analogamente o número de termos na forma xy2 é o número de maneiras de escolher uma das três somas para obter um x e consequentemente um y em cada uma das duas outras somas Isto pode ser feito de 3 1 maneiras Finalmente a única forma de obter um termo y3 é escolher o y para cada uma das três somas no produto e isso pode ser feito de uma maneira Consequentemente vemos que xy3 xyxyxy xx xy yx yyx y xxx xxy xyx xyy yxx yxy yyx yyy x3 3x2y 3xy2 y3 Podemos agora enunciar o binômio de Newton TEOREMA 1 O BINÔMIO DE NEWTON Considere x e y como variáveis e n como um número inteiro não negativo Então xyn j0n n j xnj yj n 0 xn n 1 xn1 y n 2 xn2 y2 n n1 xyn1 n n yn Demonstração Daremos uma demonstração combinatória desse teorema Os termos do produto quando expandido estão na forma xnj yj para j012n Para contar o número de termos da forma xnj yj é necessário escolher nj xs a partir de n somas assim os outros j termos no produto são ys Portanto o coeficiente de xnj yj é n nj que é igual a n j Isto demonstra o teorema O uso do binômio de Newton está ilustrado nos exemplos 2 a 4 EXEMPLO 2 Qual é o desenvolvimento de xy4 Solução A partir do binômio de Newton temos que xy4 j04 4 j x4j yj 4 0 x4 4 1 x3 y 4 2 x2 y2 4 3 xy3 4 4 y4 x4 4x3 y 6x2 y2 4xy3 y4 EXEMPLO 3 Qual é o coeficiente de x12 y13 no desenvolvimento de xy25 Solução A partir do binômio de Newton temos que o coeficiente é 25 13 25 13 12 5 200 300 EXEMPLO 4 Qual é o coeficiente de x12 y13 no desenvolvimento de 2x3y25 Solução Primeiro note que esta expressão é igual a 2x 3y25 Pelo binômio de Newton temos que 2x3y25 j025 25 j 2x25j 3yj Consequentemente o coeficiente de x12 y13 no desenvolvimento é obtido quando j13 ou seja 25 13 212 313 25 13 12 212 313 Usando o binômio de Newton podemos demonstrar algumas identidades úteis como podemos ver nos Corolários 1 2 e 3 COROLÁRIO 1 Considere n como um inteiro não negativo Então k0n n k 2n Demonstração Usando o binômio de Newton com x1 e y1 vemos que 2n 11n k0n n k 1k 1nk k0n n k Este é o resultado desejado Há também uma demonstração combinatorial interessante do Corolário 1 que apresentaremos agora Demonstração Um conjunto com n elementos tem um total de 2n subconjuntos diferentes Cada subconjunto tem zero elementos um elemento dois elementos ou n elementos Há 0 subconjuntos com nenhum elemento 1 subconjuntos com um elemento 2 subconjuntos com dois elementos e n subconjuntos com n elementos Portanto k0n nk é o número total de subconjuntos de um conjunto com n elementos Isto mostra que k0n nk 2n COROLÁRIO 2 Considere n como um número inteiro positivo Então k0n 1k nk 0 Demonstração Quando usamos o binômio de Newton com x 1 e y 1 vemos que 0 0n 1 1n k0n nk1nk k0n nk1k Isto demonstra o corolário Lembrese O Corolário 2 implica que n0 n2 n4 n1 n3 n5 COROLÁRIO 3 Considere n como um número inteiro não negativo Então k0n 2k nk 3n Demonstração Reconhecemos que o lado esquerdo dessa fórmula é o desenvolvimento de 1 2n fornecida pelo binômio de Newton Assim pelo binômio de Newton vemos que 1 2n k0n nk 1nk 2k k0n nk 2k Assim k0n 2k nk 3n Identidade de Pascal e Triângulo de Pascal Os coeficientes binomiais satisfazem muitas identidades Introduziremos agora uma das mais importantes TEOREMA 2 IDENTIDADE DE PASCAL Considere n e k como números inteiros positivos com n k Então n1k nk1 nk Demonstração Suponha que T seja um conjunto com n 1 elementos Considere a como um elemento de T e considere S T a Note que há n1k subconjuntos de T com k elementos Entretanto um subconjunto de T com k elementos contém o elemento a juntamente com k 1 elementos de S ou contém k elementos de S e não contém a Visto que há nk1 subconjuntos com k 1 elementos de S há nk1 subconjuntos de k elementos de T que contém a E há nk subconjuntos de k elementos de T que não contém a pois há nk subconjuntos de k elementos de S Conseqüentemente n1k nk1 nk Lembrese Mostramos uma demonstração combinatória da identidade de Pascal Também é possível demonstrar essa identidade pela manipulação algébrica a partir da fórmula para nr veja o Exercício 19 no final desta seção Lembrese A identidade de Pascal junto com as condições iniciais n0 nn 1 para todos os números inteiros n pode ser usada para definir recursivamente coeficientes binomiais Essa definição recursiva é útil ao computar coeficientes binomiais porque apenas a adição não a multiplicação de números inteiros é necessária para usar a definição recursiva A identidade de Pascal é a base para um arranjo geométrico de coeficientes binomiais em forma de triângulo como mostra a Figura 1 A nésima linha do triângulo consiste em coeficientes binomiais nk k 0 1 n Este triângulo é conhecido como triângulo de Pascal A identidade de Pascal mostra que quando dois coeficientes binomiais adjacentes são somados no triângulo é produzido um coeficiente binomial na próxima linha entre esses dois coeficientes Links BLAISE PASCAL 16231662 Blaise Pascal exibiu seus talentos muito jovem embora seu pai que fez descobertas em geometria analítica tenha mantido os livros de matemática longe dele para incitálhe outros interesses Aos 16 anos Pascal descobriu um importante resultado em seções cônicas Aos 18 anos ele criou uma máquina de calcular a qual ele mesmo construiu e vendeu Pascal junto com Fermat deixou os fundamentos da teoria moderna da probabilidade Em seu trabalho fez novas descobertas que agora são conhecidas como triângulo de Pascal Em 1654 Pascal abandonou suas buscas matemáticas para devotarse à teologia Depois disso retornou à matemática apenas uma vez Uma noite perturbado por uma severa dor de dente ele buscou conforto estudando as propriedades matemáticas do ciclóide Milagrosamente sua dor desapareceu o que ele sentiu como um sinal de aprovação divina do estudo da matemática 0 0 1 1 0 1 1 1 1 2 0 2 1 2 2 1 2 1 Pela identidade de Pascal 6 4 6 5 7 5 1 3 3 1 3 0 3 1 3 2 3 3 1 4 6 4 1 4 0 4 1 4 2 4 3 4 4 5 0 5 1 5 2 5 3 5 4 5 5 1 5 10 10 5 1 6 0 6 1 6 2 6 3 6 4 6 5 6 6 1 6 15 20 15 6 1 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 1 7 21 35 35 21 7 1 8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 1 8 28 56 70 56 28 8 1 a b FIGURA 1 Triângulo de Pascal Algumas Outras Identidades dos Coeficientes Binomiais Concluímos esta seção com demonstrações combinatórias de duas das muitas identidades dos coeficientes binomiais TEOREMA 3 IDENTIDADE DE VANDERMONDE Considere m n e r como números inteiros não negativos com r não excedente a m ou n Então m nr k0r mrk nk Lembrese Esta identidade foi descoberta pelo matemático AlexandreThéophile Vandermonde no século XVIII Demonstração Suponha que haja m itens em um conjunto e n itens em um segundo conjunto Então o número total de maneiras de escolher r elementos da união desses conjuntos é mnr Outra maneira de escolher r elementos da união é escolher k elementos do primeiro conjunto e então escolher r k elementos do segundo conjunto em que k é um número inteiro com 0 k r Isto pode ser feito de mk rk maneiras usandose a regra do produto Assim o número total de maneiras de escolher r elementos da união é também igual a mnr k0r mrk nk Isto demonstra a identidade de Vandermonde O Corolário 4 diz respeito à identidade de Vandermonde 100 50 20 10 5 2 1 FIGURA 1 Caixa de Dinheiro com Sete Tipos de Cédulas EXEMPLO 3 Há quantas maneiras de escolher cinco cédulas possíveis em uma caixa que contém cédulas de R 1 R 2 R 5 R 10 R 20 R 50 e R 100 Considere que a ordem na qual cada cédula é escolhida não é relevante que cada nota é idêntica e que há pelo menos cinco cédulas de cada valor Solução Como a ordem em que as cédulas são escolhidas não é relevante e sete tipos diferentes de cédula podem ser escolhidas cinco vezes este problema envolve a contagem de 5combinações com repetição de um conjunto com sete elementos Listar todas as possibilidades pode se tornar demorado e tedioso pois há um grande número de soluções Em vez disso mostraremos o uso de uma técnica de contagem de combinações com repetição Suponha que uma caixa tenha sete compartimentos uma para cada tipo de cédula como ilustrado na Figura 1 Esses compartimentos são separados por seis divisórias como mostrado na figura A escolha de cinco cédulas corresponde a colocar cinco marcadores nos compartimentos para cédulas diferentes A Figura 2 ilustra esta correspondência de três maneiras diferentes de escolher as cinco cédulas em que os seis divisores são representados por barras e as cinco cédulas por asteriscos O número de maneiras de escolher as cinco cédulas corresponde ao número de maneiras de organizar seis barras e cinco asteriscos Conseqüentemente o número de maneiras de escolher cinco cédulas é o número de maneiras de escolher as posições dos cinco asteriscos a partir de 11 posições possíveis Isto corresponde ao número de seleções não ordenadas de 5 objetos de um conjunto de 11 objetos o que pode se feito de C11 5 maneiras Conseqüentemente há FIGURA 2 Exemplos de Maneiras de Escolher Cinco Cédulas Utilizados concomitantemente os métodos descritos anteriormente neste capítulo e os métodos introduzidos nesta seção formam uma ferramenta muito útil para a resolução de uma grande variedade de problemas de contagem Quando os métodos adicionais discutidos no Capítulo 7 forem somados a estes você será capaz de resolver inúmeros problemas de contagem que aparecem em muitas áreas de estudo Permutações com Repetição As permutações com repetição podem ser facilmente realizadas com o uso da regra do produto como mostra o Exemplo 1 EXEMPLO 1 Quantas sequências de extensão r podem ser formadas com o alfabeto da língua inglesa Solução Usando a regra do produto temos como há 26 letras e como cada letra pode ser usada repetidamente vemos que são possíveis 26r sequências de extensão r O número de rpermutações de um conjunto com n elementos quando há repetição pode ser resolvido com o Teorema 1 TEOREMA 1 O número de rpermutações de um conjunto com n objetos com repetição é nr Demonstração Há n maneiras possíveis de escolher um elemento do conjunto para cada uma das r posições na rpermutação com repetição porque para cada escolha todos os n objetos estão disponíveis Assim pela regra do produto são possíveis nr rpermutações com repetição Combinações com Repetição Considere os exemplos abaixo de combinação com repetição de elementos EXEMPLO 2 Há quantas maneiras possíveis de escolher quatro pedaços de fruta a partir de uma tigela que contém maçãs laranjas e pêras se a ordem em que cada pedaço é escolhido não é relevante apenas o tipo de fruta e o pedaço individual não é relevante também sendo que há pelo menos quatro pedaços de cada tipo de fruta na tigela Solução Para resolver esse problema listamos todas as maneiras possíveis de escolher uma fruta Há 15 maneiras 4 maçãs 4 laranjas 4 pêras 3 maçãs 1 laranja 3 maçãs 1 pêra 3 laranjas 1 maçã 3 laranjas 1 pêra 3 pêras 1 maçã 3 pêras 1 laranja 2 maçãs 2 laranjas 2 maçãs 2 pêras 2 laranjas 2 pêras 2 maçãs 1 laranja 1 pêra 2 laranjas 1 maçã 1 pêra 2 pêras 1 maçã 1 laranja A solução é o número de 4combinações com repetição de um conjunto de três elementos maçã laranja pêra Para resolver problemas de contagem mais complexos desse tipo necessitamos de um método geral para a contagem de rcombinações de um conjunto com n elementos No Exemplo 3 mostraremos tal método C11 5 11 56 462 maneiras possíveis de escolher cinco cédulas em uma caixa com sete tipos de cédulas O Teorema 2 generaliza esta discussão TEOREMA 2 Há Cn r 1 r Cn r 1 n 1 rcombinações de um conjunto com n elementos quando a repetição dos elementos é permitida Demonstração Cada uma das rcombinações de um conjunto com n elementos quando a repetição é permitida pode ser representada por uma lista de n 1 barras e r asteriscos Então n 1 barras são usadas para representar n cédulas diferentes com a iésima cédula contendo um asterisco para toda vez que o iésimo elemento do conjunto aparecer na combinação Por exemplo uma 6combinação de um conjunto com quatro elementos é representada com três barras e seis asteriscos Aqui representa a combinação que contém exatamente duas vezes o primeiro elemento uma o segundo elemento nenhuma o terceiro elemento e três vezes o quarto elemento do conjunto Como vimos cada lista diferente contém n 1 barras e r asteriscos que correspondem a uma rcombinação do conjunto com n elementos com repetição O número de tais listas é Cn 1 r r pois cada lista corresponde a uma escolha de r posições para colocar os r asteriscos a partir de n 1 r posições que contêm r asteriscos e n 1 barras O número de tais listas é também igual a Cn 1 r n 1 pois cada lista corresponde a uma escolha de n 1 posições para colocar as n 1 barras Os exemplos 4 a 6 mostram como o Teorema 2 é aplicado EXEMPLO 4 Suponha que uma cafeteria tenha quatro tipos diferentes de biscoitos Há quantas maneiras diferentes possíveis de escolher seis biscoitos Suponha que apenas o tipo de biscoito seja relevante e não os biscoitos individualmente ou a ordem em que são escolhidos Solução O número de maneiras de escolher seis biscoitos é o número de 6combinações de um conjunto com quatro elementos Pelo Teorema 2 isto é igual a C4 6 1 6 C9 6 Como C9 6 C9 3 9 8 7 1 2 3 84 há 84 maneiras diferentes possíveis de escolher seis biscoitos O Teorema 2 também pode ser usado para encontrar o número de soluções para certas equações lineares em que as variáveis são números inteiros sujeitos a uma restrição Isto será mostrado no Exemplo 5 EXEMPLO 5 Quantas soluções à equação x1 x2 x3 11 pode ter em que x1 x2 e x3 são números inteiros não negativos Solução Para contar o número de soluções notamos que uma solução corresponde a uma maneira de selecionar 11 itens de um conjunto com três elementos tal que x1 itens do tipo um x2 itens do tipo dois e x₃ itens do tipo três sejam escolhidos Assim o número de soluções é igual ao número de 11combinações com repetição de um conjunto com três elementos Pelo Teorema 2 verificamos que há C3 11 1 11 C13 11 C13 2 1312 12 78 soluções O número de soluções desta equação pode também ser encontrado quando as variáveis estão sujeitas a restrição Por exemplo podemos encontrar o número de soluções em que as variáveis são números inteiros com x₁ 1 x₂ 2 e x₃ 3 Uma solução dessa equação sujeita a essas restrições corresponde a uma seleção de 11 itens com x₁ itens do tipo um x₂ itens do tipo dois e x₃ itens do tipo três em que há pelo menos um item do tipo um dois itens do tipo dois e três itens do tipo três Então escolhemos um item do tipo um dois do tipo dois e três do tipo três Depois selecionamos cinco itens adicionais Pelo Teorema 2 isto pode ser feito de C3 5 1 5 C7 5 C7 2 76 12 21 maneiras Portanto há 21 soluções possíveis para a equação sujeita às restrições dadas O Exemplo 6 mostra como contar o número de combinações com repetição que aparecem para determinar o valor de uma variável que está sendo incrementada cada vez que um certo tipo de laços agrupados é dado EXEMPLO 6 Qual o valor de k depois que o pseudocódigo abaixo for executado k 0 for i₁ 1 to n for i₂ 1 to i₁ for iₘ 1 to iₘ₁ k k 1 Solução Note que o valor inicial de k é 0 e que 1 é adicionado a k toda vez que o laço for dado com uma sequência de inteiros i₁ i₂ iₘ tal que 1 iₘ iₘ₁ i₁ n O número de tais sequências é o número de maneiras de escolher m números inteiros de 1 2 n com repetição Para verificar isso note que uma vez que a sequência for escolhida se a ordem dos números inteiros for uma ordem não decrescente esta unicidade define uma tarefa de iₘ iₘ₁ i₁ Contrariamente cada tarefa corresponde a um único conjunto não ordenado Assim pelo Teorema 2 temos que k Cn m 1 m depois que o código tiver sido executado As fórmulas para os números de seleções ordenadas e não ordenadas de r elementos com ou sem repetições de um conjunto com n elementos são apresentadas na Tabela 1 TABELA 1 Combinações e Permutações com e sem Repetição Tipo Com repetição Fórmula rpermutações Não n n r rcombinações Não n rn r rpermutações Sim nr rcombinações Sim n r 1 rn 1 Permutações com Objetos Idênticos Alguns elementos podem ser indistinguíveis em problemas de contagem Quando este é o caso alguns cuidados devem ser tomados para evitar a contagem de objetos mais de uma vez Considere o Exemplo 7 EXEMPLO 7 Quantas sequências diferentes podem ser obtidas reorganizandose as letras da palavra SUCCESS Solução Como algumas das letras de SUCCESS são idênticas não será considerado o número de permutações de sete letras Essa palavra contém três Ss dois Cs um U e um E Para determinar o número de sequências diferentes que podem ser obtidas reorganizandose as letras primeiro note que os três Ss podem ser colocados entre as sete posições de C7 3 maneiras diferentes deixando quatro posições livres Então os dois Cs podem ser colocados de C4 2 maneiras deixando três posições livres O U pode ser colocado de C2 1 maneiras deixando apenas uma posição livre Assim o E pode ser colocado de C1 1 maneira Conseqüentemente pela regra do produto o número de sequências diferentes que podem ser feitas é C7 3C4 2C2 1C1 1 7 34 4 22 2 11 1 10 7 3211 420 Podemos demonstrar o Teorema 3 usando o mesmo tipo de raciocínio do Exemplo 7 TEOREMA 3 O número de permutações diferentes de n objetos em que há n₁ objetos idênticos do tipo 1 n₂ objetos idênticos do tipo 2 e nₖ objetos idênticos do tipo k é n n₁ n₂ nₖ Demonstração Para determinar o número de permutações primeiro note que os n₁ objetos do tipo 1 podem ser colocados em n posições de Cn n₁ maneiras deixando n n₁ posições livres Então os objetos do tipo 2 podem ser colocados de Cn n₁ n₂ maneiras deixando n n₁ n₂ posições livres Continue a colocar os objetos do tipo 3 tipo k 1 até a última etapa em que nₖ objetos do tipo k podem ser colocados de Cn n₁ n₂ nₖ₁ nₖ maneiras Assim pela regra do produto o número total de permutações diferentes é Cn n₁Cn n₁ n₂ Cn n₁ nₖ₁ nₖ n n₁n n₁ n n₁ n₂n n₁ n₂ n n₁ nₖ₁ nₖ 0 n n₁ n₂ nₖ Distribuição de Objetos em Caixas Muitos problemas de contagem podem ser resolvidos enumerandose as maneiras como os objetos podem ser colocados em caixas em que a ordem desses objetos não é relevante Os objetos podem ser distintos ou seja diferentes uns dos outros ou idênticos Os objetos distintos são às vezes chamados de rotulados enquanto os objetos idênticos são chamados de não rotulados Do mesmo modo as caixas podem ser distintas ou seja diferentes ou idênticas Caixas distintas são geralmente chamadas de rotuladas enquanto as caixas idênticas de não rotuladas Quando você resolve um problema de contagem usando o modelo de distribuição de objetos em caixas precisa determinar se os objetos são distintos e se as caixas são distintas Embora o contexto do problema de contagem esclareça este ponto esse problemas são muitas vezes ambíguos e isto pode não deixar claro qual modelo aplicar Neste caso o melhor é estabelecer quais hipóteses você está fazendo e explicar o porquê da escolha de determinado modelo conforme suas hipóteses Veremos que há fórmulas fechadas para contar as maneiras de distribuir objetos distintos ou idênticos em caixas distintas Não teremos tanta sorte quando o problema for contar as maneiras de distribuir os objetos distintos ou idênticos em caixas idênticas não há fórmulas fechadas para usar nesses casos OBJETOS DISTINTOS E CAIXAS DISTINTAS Primeiro consideramos o caso quando objetos distintos são colocados em caixas distintas Considere o Exemplo 8 no qual os objetos são cartas e as caixas são as mãos de jogadores EXEMPLO 8 Quantas maneiras existem de distribuir mãos de 5 cartas para cada um dos quatro jogadores a partir de um baralho de 52 cartas Solução Usaremos a regra do produto para resolver este problema Para começar note que o primeiro jogador pode ter 5 cartas de C52 5 maneiras O segundo jogador pode ter 5 cartas de C47 5 maneiras porque sobraram apenas 47 cartas O terceiro jogador pode receber 5 cartas de C42 5 maneiras Finalmente o quarto jogador pode ter 5 cartas de C37 5 maneiras Assim o número total de maneiras de dar as cartas aos quatro jogadores com cinco cartas cada é C52 5C47 5C42 5C37 5 52 475 47 425 42 375 37 325 52 555532 Lembrese A solução do Exemplo 8 é igual ao número de permutações de 52 objetos com 5 objetos distintos de quatro tipos diferentes e 32 objetos de um quinto tipo Esta equação pode ser verificada definindose uma correspondência um para um uma função bijetora entre permutações deste tipo e distribuição de cartas aos jogadores Para definir essa correspondência primeiro ordene as cartas de 1 a 52 Então as cartas dadas ao primeiro jogador correspondem as cartas nas posições dos objetos do primeiro tipo na permutação Do mesmo modo as cartas dadas ao segundo terceiro e quarto jogadores respectivamente correspondem as cartas nas posições dos objetos do segundo terceiro e quarto tipo respectivamente As cartas não distribuídas correspondem às cartas na posição dos objetos do quinto tipo O leitor deverá verificar que esta é uma correspondência um para um O Exemplo 8 é um problema típico que envolve distribuição de objetos distintos em caixas distintas Os objetos distintos são as 52 cartas e as 5 caixas distintas são as mãos dos quatro jogadores e o resto do baralho Problemas de contagem que envolvam distribuição de objetos distintos em caixas podem ser resolvidos usandose o Teorema 4 TEOREMA 4 O número de maneiras de distribuir n objetos distintos em k caixas distintas para que os nᵢ objetos sejam colocados na caixa i i 1 2 k é igual a n n₁ n₂ nₖ O Teorema 4 pode ser demonstrado usandose a regra do produto Estudaremos os detalhes no Exercício 47 Ele também pode ser demonstrado pela correspondência um para um veja o Exercício 48 entre as permutações contadas pelo Teorema 3 e as maneiras de distribuir objetos contados pelo Teorema 4 OBJETOS IDÊNTICOS E CAIXAS DISTINTAS Contar o número de maneiras de colocar n objetos idênticos em k caixas distintas é o mesmo que contar o número de ncombinações de um conjunto com k elementos com repetição A razão disto é que há correspondência um para um entre as ncombinações de um conjunto com k elementos com repetição e as maneiras de colocar n bolas idênticas em k caixas distintas Para construir tal correspondência colocamos uma bola na iésima caixa cada vez que o iésimo elemento do conjunto estiver incluso na ncombinação EXEMPLO 9 Há quantas maneiras possíveis de colocar 10 bolas idênticas em oito caixas distintas Solução O número de maneiras de colocar 10 bolas idênticas em oito caixas é igual ao número de 10combinações de um conjunto com oito elementos com repetição Conseqüentemente há C8 10 1 10 C17 10 17 107 19 448 Isto significa que há Cn r 1 n 1 maneiras de colocar r objetos idênticos em n caixas distintas OBJETOS DISTINTOS E CAIXAS IDÊNTICAS Contar as maneiras de colocar n objetos distintos em k caixas idênticas é mais difícil que contar as maneiras de colocar objetos distintos ou idênticos em caixas distintas Mostraremos isto com um exemplo EXEMPLO 10 Há quantas maneiras possíveis de colocar quatro empregados diferentes em três escritórios idênticos em que cada escritório pode conter qualquer número de empregados Solução Resolveremos este problema enumerando as maneiras possíveis de os empregados serem colocados nos escritórios Representamos os quatro empregados por A B C e D Primeiro notamos que podemos distribuir os empregados para que todos fiquem em uma sala ou três fiquem em uma sala e um em uma segunda sala ou ainda dois empregados em cada sala e uma sala vazia e por fim dois fiquem em uma sala e cada um dos outros dois em uma das outras duas salas Cada maneira de distribuir os empregados nessas salas representa um maneira de repartir os elementos A B C e D em subconjuntos disjuntos Podemos colocar os quatro empregados em uma sala de uma maneira representada por A B C D Podemos colocar três empregados em uma sala e o quarto em outra de quatro maneiras representadas por A B C D A B D C A C D B e B C D A Podemos colocar dois empregados em cada sala de três maneiras representadas por A B C D A C B D e A D B C Por fim podemos colocar dois empregados em uma sala e cada um dos outros dois em salas diferentes de seis maneiras representadas por A B C D A C B D A D B C B C A D B D A C e C D A B Contando todas as possibilidades encontramos 14 maneiras de colocar quatro empregados diferentes em três salas iguais Outra forma de olhar para este problema é ver o número de salas nas quais se vão colocar os empregados Note que há seis maneiras de colocar quatro empregados diferentes em três salas idênticas para que nenhuma sala fique vazia sete maneiras de colocar os quatro empregados em duas salas iguais para que nenhuma sala fique vazia e uma maneira de colocar os quatro empregados em um única sala Não há uma fórmula fechada simples para o número de maneiras de distribuir n objetos distintos em j caixas idênticas Entretanto há uma fórmula particularmente complicada que descreveremos agora os leitores podem omitir a discussão desta fórmula se desejarem Considere Sn j como o número de maneiras de distribuir n objetos distintos em j caixas idênticas para que nenhuma caixa fique vazia Os números Sn j são chamados de números de Stirling de segunda ordem Por exemplo o Exemplo 10 mostra que S4 3 6 S4 2 7 e S4 1 1 Vemos que o número de maneiras de distribuir n objetos distintos em k caixas idênticas em que o número de caixas não vazias é igual a k k 1 2 ou 1 é igual a Σₗ₁k Sn j Por exemplo seguindo o raciocínio do Exemplo 10 o número de maneiras de distribuir quatro objetos distintos em três caixas idênticas é igual a S4 1 S4 2 S4 3 1 7 6 14 Usando o princípio da inclusãoexclusão veja a Seção 76 podemos mostrar que Sn j 1j Σi0j1 1i j choose i jin Conseqüentemente o número de maneiras de distribuir n objetos distintos em k caixas idênticas é igual a Σj1k Sn j Σj1k 1j Σi0j1 1i j choose i jin Para mais informações sobre os números de Stirling de segunda ordem veja os livros teóricos sobre análise combinatória como Bó07 Br99 e RoTe05 e o Capítulo 6 em MiRo91 OBJETOS IDÊNTICOS E CAIXAS IDÊNTICAS Alguns problemas de contagem podem ser resolvidos pela determinação do número de maneiras de distribuir objetos idênticos em caixas idênticas Mostraremos este princípio com um exemplo EXEMPLO 11 Há quantas maneiras possíveis de empacotar seis cópias do mesmo livro em quatro caixas idênticas em que cada caixa pode conter até seis livros Solução Vamos enumerar todas as maneiras de empacotar os livros Para cada maneira de embalar os livros listaremos o número de livros na caixa com mais livros seguido pelo número de livros em cada caixa que contém pelo menos um livro em ordem decrescente As maneiras de embalar os livros são 6 5 1 4 2 4 1 1 3 3 3 2 1 3 1 1 1 2 2 2 2 2 1 1 Por exemplo 4 1 1 indica que uma caixa contém quatro livros a segunda caixa contém um livro e a terceira um livro e a quarta caixa está vazia Como enumeramos todas as maneiras de empacotar os seis livros em quatro caixas vemos que há nove maneiras de embalálos Observe que a distribuição de n objetos idênticos em k caixas idênticas é o mesmo que escrever n como a soma de no máximo k números inteiros positivos em ordem não crescente Se a₁ a₂ aᵢ n em que a₁ a₂ aᵢ são números inteiros positivos com a₁ a₂ aⱼ dizemos que a₁ a₂ aⱼ é uma partição do número inteiro positivo n em j números inteiros positivos Vemos que se pₖn é o número de partições de n em no máximo k números inteiros positivos então há pₖn maneiras de distribuir n objetos idênticos em k caixas idênticas Não existe uma fórmula fechada simples para este número Exercícios 1 De quantas maneiras cinco elementos podem ser selecionados em ordem a partir de um conjunto com três elementos com repetição 2 De quantas maneiras cinco elementos podem ser selecionados em ordem a partir de um conjunto com cinco elementos com repetição 3 Quantas sequências de seis letras existem 4 Todo dia um estudante escolhe aleatoriamente um sanduíche de uma pilha de sanduiches Se há seis tipos de sanduiches há quantas maneiras possíveis de o estudante escolher os sanduíches para os sete dias da semana se a ordem em que os sanduíches são escolhidos é relevante 5 Há quantas maneiras possíveis de designar três empregos para cinco empregados se cada empregado pode receber mais de um emprego 6 Há quantas maneiras possíveis de selecionar cinco elementos não ordenados a partir de um conjunto com três elementos com repetição 7 Há quantas maneiras possíveis de selecionar três elementos não ordenados a partir de um conjunto com cinco elementos com repetição 8 Há quantas maneiras possíveis de escolher uma dúzia de rosquinhas em uma cafeteria com 21 variedades de rosquinhas 9 Uma loja de pães tem pães de cebola pães de semente de papoula pães de ovo pães de verduras pães de centeio pães de gergelim pães de uva passa e pães simples Há quantas maneiras possíveis de escolher a seis pães b uma dúzia de pães c duas dúzias de pães d uma dúzia de pães com pelo menos um de cada tipo e uma dúzia de pães com pelo menos três de ovo e não mais de dois de verdura 10 Uma padaria tem biscoito simples biscoito de cereja biscoito de chocolate biscoito de amêndoas biscoito de maçã e biscoito de brócolis Há quantas maneiras possíveis de escolher a uma dúzia de biscoitos b três dúzias de biscoitos c duas dúzias de biscoitos com pelo menos dois de cada tipo d duas dúzias de biscoitos com não mais de dois biscoitos de brócolis e duas dúzias de biscoitos com pelo menos cinco biscoitos de chocolate e pelo menos três biscoitos de amêndoas f duas dúzias de biscoitos com pelo menos um biscoito simples pelo menos dois biscoitos de cereja pelo menos três biscoitos de chocolate pelo menos um biscoito de amêndoa pelo menos dois biscoitos de maçã e não mais de três biscoitos de brócolis 11 Há quantas maneiras possíveis de escolher oito moedas de um cofrinho que contém 100 moedas de 10 centavos e 80 moedas de 5 centavos 12 Há quantas combinações diferentes de moedas de 1 5 10 25 e 50 centavos em um cofrinho se ele contém 20 moedas 13 Uma editora tem 3000 cópias de um livro de matemática discreta Há quantas maneiras possíveis de estocar livros se há três armazéns e as cópias do livro são idênticas 14 Há quantas soluções possíveis para a equação x1 x2 x3 x4 17 em que x1 x2 x3 e x4 são números inteiros não negativos 15 Há quantas soluções possíveis para a equação x1 x2 x3 x4 x5 21 se xi i 1 2 3 4 5 é um número inteiro não negativo tal que a x1 1 b xi 2 para i 1 2 3 4 5 c 0 x1 10 d x1 3 1 x2 4 e x3 15 16 Há quantas soluções possíveis para a equação x1 x2 x3 x4 x5 x6 29 em que xi i 1 2 3 4 5 6 é um número inteiro não negativo tal que a xi 1 para i 1 2 3 4 5 6 b x1 1 x2 2 x3 3 x4 4 x5 5 e x6 6 c x1 5 d x1 8 e x2 8 17 Há quantas sequências possíveis de 10 dígitos ternários 0 1 ou 2 que contêm dois 0s três 1s e cinco 2s 18 Há quantas sequências possíveis de 20 dígitos decimais que contêm dois 0s quatro 1s três 2s um 3 dois 4s três 5s dois 7s e três 9s 19 Suponha que uma família grande tenha 14 filhos incluindo uma dupla de trigêmeos três grupos de gêmeos e duas crianças Há quantas maneiras de colocar as crianças em uma fila de cadeiras se os trigêmeos e os gêmeos não podem ser distinguidos um do outro 20 Há quantas soluções possíveis para a inequação x1 x2 x3 11 em que x1 x2 e x3 são inteiros não negativos Dica Introduza uma variável auxiliar x4 tal que x1 x2 x3 x4 11 21 Há quantas maneiras possíveis de distribuir seis bolas idênticas em nove caixas distintas 22 Há quantas maneiras de distribuir 12 bolas idênticas em seis caixas distintas 23 Há quantas maneiras de distribuir 12 objetos distintos em seis caixas distintas tal que dois objetos sejam colocados em cada caixa 24 Há quantas maneiras de distribuir 15 objetos distintos em cinco caixas distintas para que as caixas tenham um dois três quatro e cinco objetos respectivamente 25 Quantos números inteiros positivos menores que 1 000 000 têm a soma de seus dígitos igual a 19 26 Quantos números inteiros positivos menores que 1 000 000 têm um dígito igual a 9 e têm a soma de dígitos igual a 13 27 Há 10 questões na prova final de matemática discreta Há quantas maneiras possíveis de distribuir as notas aos problemas se a soma das notas é 100 e cada questão vale pelo menos 5 pontos 28 Mostre que há Cn r q1 q2 qr 1 n q1 q2 qr diferentes seleções não ordenadas de n objetos de r tipos diferentes que incluem pelo menos q1 objetos do tipo um q2 objetos do tipo dois e qr objetos do tipo r 29 Quantas cadeias de bits diferentes podem ser transmitidas se a cadeia deve começar com um bit 1 deve incluir três bits 1 adicionais para que tenha quatro bits 1 enviados deve incluir um total de 12 bits 0 e deve ter pelo menos dois bits 0 depois de cada bit 1 30 Quantas sequências diferentes podem ser obtidas com as letras da palavra MISSISSIPPI usandose todas as letras 31 Quantas sequências diferentes podem ser obtidas com as letras da palavra ABRACADABRA usandose todas as letras 32 Quantas sequências diferentes podem ser obtidas com as letras de AARDVARK usandose todas as letras se todos os três As devem ser consecutivos 33 Quantas sequências diferentes podem ser obtidas com as letras de ORONO usandose até o total das cinco letras 34 Quantas sequências com cinco ou mais caracteres podem ser formadas com as letras de SEERESS 35 Quantas sequências com sete ou mais caracteres podem ser formadas com as letras de EVERGREEN 36 Quantas cadeias de bits diferentes podem ser formadas usandose seis 1s e oito 0s 37 Um estudante tem três mangas dois mamões e dois kiwis Se ele comer um pedaço de fruta por dia e apenas o tipo da fruta é relevante de quantas maneiras diferentes essas frutas podem ser consumidas 38 Uma professora embala sua coleção de 40 artigos de um periódico matemático em quatro caixas com 10 artigos por caixa De quantas maneiras ela pode distribuir os periódicos se a cada caixa é numerada para que elas sejam distintas b as caixas são idênticas de modo que elas não podem ser distinguidas 39 Há quantas maneiras possíveis de viajar em um espaço xyz com origem 0 0 0 ao ponto 4 3 5 por meio de passos de uma unidade na direção positiva x de uma unidade na direção positiva y ou de uma unidade na direção positiva z Moverse nas direções negativas x y ou z é proibido portanto os movimentos para trás não são permitidos 40 Há quantas maneiras possíveis de andar no espaço xyzw a partir da origem 0 0 0 0 ao ponto 4 3 5 4 por meio de passos de uma unidade na direção positiva x positiva y positiva z ou positiva w 41 Há quantas maneiras possíveis de dar sete cartas a cada um dos cinco jogadores de um baralho com 52 cartas 42 No bridge as 52 cartas de um baralho são distribuídas a quatro jogadores Há quantas maneiras diferentes de distribuir as mãos de bridge aos quatro jogadores 43 Há quantas maneiras de distribuir as mãos de cinco cartas para seis jogadores com um baralho de 48 cartas 44 De quantas maneiras uma dúzia de livros pode ser colocada em quatro prateleiras distintas a se os livros são cópias idênticas do mesmo título b se nenhum dos livros são iguais e as posições dos livros nas prateleiras são relevantes Dica Trabalhe como se fossem 12 tarefas colocando cada livro separadamente Comece com a sequência 1 2 3 4 para representar as prateleiras Represente os livros por bi i 1 2 12 Coloque bj à direita de um dos termos 1 2 3 4 que representam as prateleiras Então coloque sucessivamente b2 b3 e b12 45 De quantas maneiras podem ser colocados n livros em k prateleiras distintas a se os livros são cópias idênticas do mesmo título b se nenhum dos livros são iguais e as posições dos livros nas prateleiras são relevantes 46 Uma prateleira tem 12 livros em uma sequência Há quantas maneiras de escolher cinco livros para que dois livros adjacentes não sejam escolhidos Dica Represente os livros que são escolhidos por barras e os livros não escolhidos por asteriscos Conte o número de sequências de cinco barras e sete asteriscos sendo que as barras não podem ser adjacentes 47 Use a regra do produto para demonstrar o Teorema 4 primeiro colocando os objetos na primeira caixa em seguida colocandoos na segunda caixa e assim por diante 48 Demonstre o Teorema 4 fazendo uma correspondência um para um entre permutações de n objetos com ni objetos idênticos do tipo i i 1 2 3 k e as distribuições de n objetos em k caixas tal que ni objetos sejam colocados na caixa i i 1 2 3 k e então aplique o Teorema 3 49 Neste exercício demonstraremos o Teorema 2 fazendo uma correspondência um para um entre o conjunto de rcombinações com repetição de S 1 2 3 n e o conjunto de rcombinações do conjunto T 1 2 3 n r 1 a Arranje os elementos em rcombinações com repetição de S em uma sequência crescente x1 x2 xr Mostre que a sequência formada pela adição de k 1 ao késimo termo é estritamente crescente Conclua que essa sequência é feita de r elementos distintos de T b Mostre que o procedimento descrito em a define uma correspondência um para um entre o conjunto de rcombinações com repetição de S e o de rcombinações de T Dica Mostre que a correspondência pode ser reversa associando a rcombinação x1 x2 xr de T com 1 x1 x2 xr n r 1 à rcombinação com repetição de S formada pela subtração k 1 do késimo elemento c Conclua que há Cn r 1 r rcombinações com repetição de um conjunto com n elementos 50 Há quantas maneiras possíveis de distribuir cinco objetos distintos em três caixas idênticas 51 Há quantas maneiras possíveis de distribuir seis objetos distintos em quatro caixas idênticas para que cada uma das caixas tenha pelo menos um objeto 52 Há quantas maneiras possíveis de colocar cinco empregados temporários em quatro salas idênticas 53 Há quantas maneiras possíveis de colocar seis empregados temporários em quatro salas idênticas para que haja pelo menos um empregado em cada uma das salas 54 Há quantas maneiras possíveis de distribuir cinco objetos idênticos em três caixas idênticas 55 Há quantas maneiras possíveis de distribuir seis objetos idênticos em quatro caixas idênticas para que cada uma das caixas tenha pelo menos um objeto 56 Há quantas maneiras possíveis de embalar oito DVDs idênticos em cinco caixas idênticas para que cada caixa tenha pelo menos um DVD 57 Há quantas maneiras possíveis de embalar nove DVDs idênticos em três caixas idênticas para que cada caixa tenha pelo menos dois DVDs 58 Há quantas maneiras possíveis de distribuir cinco bolas em sete caixas se cada caixa deve ter no máximo uma bola e se a ambas bolas e caixas são distinguíveis b as bolas são distinguíveis mas as caixas indistinguíveis c as bolas são indistinguíveis mas as caixas distinguíveis d ambas bolas e caixas são indistinguíveis 59 Há quantas maneiras possíveis de distribuir cinco bolas em três caixas se cada caixa deve conter pelo menos uma bola e se a ambas bolas e caixas são distintas b as bolas são distintas mas as caixas idênticas c as bolas são idênticas mas as caixas distintas d ambas bolas e caixas são idênticas 60 Suponha que uma liga de basquete tenha 32 times divididos em duas delegações com 16 times cada Cada delegação é dividida em três divisões Suponha que a Divisão CentroNorte tenha cinco times Cada um dos times da Divisão CentroNorte joga quatro partidas contra cada um dos outros nesta divisão três partidas contra cada um dos 11 times restantes da delegação e duas partidas contra cada um dos 16 times da outra delegação Há quantas ordens de jogos diferentes possíveis para um dos times da Divisão CentroNorte 61 Suponha que um inspetor de armas deva inspecionar cada um dos cinco lugares diferentes duas vezes visitando um lugar por dia O inspetor tem permissão para escolher a ordem em que irá visitar esses lugares mas não pode visitar X o lugar mais suspeito em dois dias consecutivos Há quantas maneiras possíveis de o inspetor visitar tais lugares 62 Há quantos termos diferentes possíveis no desenvolvimento de x1 x2 xm n depois que todos os termos com conjuntos idênticos de expoentes são adicionados 63 Demonstre o Teorema Multinomial Se n é um número inteiro positivo então x1 x2 xm n Σ Cnn1n2nm x1n1x2n2xmnm n1n2nmn em que Cnn1n2nm n n1n2nm é um coeficiente multinomial 64 Encontre o desenvolvimento de x y z4 65 Encontre o coeficiente de x3y25 em x y z10 66 Quantos termos existem no desenvolvimento de x y z100 56 Gerando Permutações e Combinações Introdução Os métodos para contar vários tipos de permutações e combinações foram descritos nas seções anteriores deste capítulo mas algumas permutações ou combinações necessitam ser desenvolvidas não apenas contadas Considere os três problemas a seguir Primeiro suponha que um vendedor deva visitar seis cidades diferentes Em qual ordem essas cidades devem ser visitadas com o menor tempo de viagem possível Uma maneira de determinar a melhor ordem é determinar o tempo de viagem para cada uma das 6 720 ordens diferentes nas quais as cidades podem ser visitadas e escolher o menor tempo de viagem Segundo suponha que seja dado um conjunto de seis números inteiros positivos e que desejamos encontrar um subconjunto que tenha a soma de seus elementos igual a 100 se tal subconjunto existir Uma maneira de encontrar esses números é gerar todos os 26 64 subconjuntos e checar a soma de seus elementos Terceiro suponha que um laboratório tenha 95 empregados Um grupo de 12 desses empregados com um conjunto determinado de 25 habilidades é requisitado para um projeto Cada empregado pode ter uma ou mais dessas habilidades Uma forma de encontrar tal conjunto de empregados é gerar todos os conjuntos de 12 desses empregados e checar se eles têm as habilidades desejadas Esses exemplos mostram que geralmente é necessário gerar as permutações e combinações para resolver os problemas Gerando Permutações Qualquer conjunto com n elementos pode ser colocado em correspondência um para um com o conjunto 1 2 3 n Podemos listar as permutações de qualquer conjunto de n elementos ao gerar permutações dos n menores números inteiros positivos e então colocar novamente esses inteiros com os elementos correspondentes Muitos algoritmos diferentes têm sido desenvolvidos para a geração das n permutações deste conjunto Descreveremos uma delas que é baseada na ordem lexicográfica ou alfabética do conjunto de permutações de 1 2 3 n Nesta ordem a permutação a1a2ak precede a permutação b1b2bk para qualquer k com 1 k n a1 b1 a2 b2 ak1 bk1 e ak bk Em outras palavras uma permutação do conjunto dos n menores números inteiros positivos precede na ordem lexicográfica uma segunda permutação se o número nesta permutação na primeira posição em que as duas permutações discordam é menor que o número naquela posição da segunda permutação EXEMPLO 1 A permutação 23415 do conjunto 1 2 3 4 5 precede a permutação 23514 pois essas permutações coincidem nas primeiras duas posições mas o número na terceira posição da primeira permutação 4 é menor que o número na terceira posição da segunda permutação 5 De maneira análoga a permutação 41532 precede a 52143 Um algoritmo para gerar a permutação de 1 2 n pode ser baseado em um procedimento que constrói a próxima permutação na ordem lexicográfica seguindo uma dada permutação a₁a₂ aₙ Mostraremos como isso pode ser feito Primeiro suponha que aₙ₁ aₙ Trocando aₙ₁ por aₙ obtemos uma permutação maior Nenhuma outra permutação é maior que a permutação original e menor que a permutação obtida pela troca de aₙ₁ por aₙ ou seja não há permutações entre elas na ordem lexicográfica Por exemplo a próxima permutação maior que 234156 é 234165 Por outro lado se aₙ₁ aₙ então uma permutação maior não pode ser obtida pela troca desses dois últimos termos Então devemos verificar os três últimos números inteiros na permutação Se aₙ₂ aₙ₁ então os últimos três números inteiros da permutação podem ser rearranjados para obter a próxima permutação maior que a original Coloque o menor dos dois números inteiros aₙ₁ e aₙ que é maior que aₙ₂ na posição n 2 Então coloque o número restante e aₙ₂ nas duas últimas posições em ordem crescente Por exemplo a maior permutação depois de 234165 é 234516 Por outro lado se aₙ₂ aₙ₁ e aₙ₁ aₙ então a maior permutação não pode ser obtida pela troca dos três últimos termos na permutação Com base nessas observações um método geral pode ser descrito para produzir a próxima maior permutação em ordem crescente seguindo uma permutação dada a₁a₂ aₙ Primeiro encontre os números inteiros aⱼ e aⱼ₁ com aⱼ aⱼ₁ e aⱼ₁ aⱼ₂ aₙ ou seja o último par de números inteiros adjacentes da permutação em que o primeiro inteiro no par é menor que o segundo Então a próxima permutação maior em ordem lexicográfica é obtida colocandose na jésima posição o menor inteiro entre aⱼ₁ aⱼ₂ aₙ que é maior que aⱼ e listandose em ordem crescente o restante dos inteiros aⱼ aⱼ₁ aₙ nas posições de j 1 a n É fácil ver que não há outra permutação maior que a₁a₂ aₙ mas menor que a nova permutação produzida A verificação deste fato foi deixada como exercício para o leitor EXEMPLO 2 Qual é a próxima permutação em ordem lexicográfica depois de 362541 Solução O último par de números inteiros aⱼ e aⱼ₁ em que aⱼ aⱼ₁ é a₃ 2 e a₄ 5 O menor inteiro à direita de 2 que é maior que 2 na permutação é a₅ 4 Assim 4 é colocado na terceira posição Então os inteiros 2 5 e 1 são colocados em ordem crescente nas três últimas posições resultando 125 nas últimas três posições da permutação Assim a próxima permutação é 364125 Para produzir as n permutações dos números inteiros 1 2 3 n comece com a menor permutação em ordem lexicográfica ou seja 123 n e aplique sucessivamente o processo descrito para produzir a próxima maior permutação n 1 vezes Isto resulta em todas as permutações dos n menores números inteiros em ordem lexicográfica EXEMPLO 3 Construa as permutações dos números inteiros 1 2 3 em ordem lexicográfica Solução Comece com 123 A próxima permutação é obtida pela troca entre 3 e 2 para obter 132 Depois como 3 2 e 1 3 permute os três números inteiros em 132 Coloque o menor entre 3 e 2 na primeira posição e então coloque 1 e 3 em ordem crescente nas posições 2 e 3 para obter 213 Este é seguido por 231 obtido pela troca entre 1 e 3 porque 1 3 A próxima maior permu tação tem 3 na primeira posição seguido de 1 e 2 em ordem crescente ou seja 312 Por fim troque 1 com 2 para obter a última permutação 321 O Algoritmo 1 mostra o procedimento para encontrar a próxima permutação em ordem lexicográfica depois de uma permutação que não é n n 1 n 2 2 1 que é a maior permutação ALGORITMO 1 Geração da Próxima Permutação em Ordem Lexicográfica procedure proxima permutacaoa₁a₂ aₙ permutação de 1 2 n que não é igual a n n 1 2 1 j n 1 while aⱼ aⱼ₁ j j 1 j é o maior índice tal que aⱼ aⱼ₁ k n while aⱼ aₖ k k 1 aₖ é o menor número inteiro maior que aⱼ à direita de aⱼ troquemos aⱼ e aₖ r n s j 1 while r s begin troque aᵣ e aₛ r r 1 s s 1 end isto coloca a parte final da permutação depois da jésima posição em ordem crescente Gerando Combinações Como podemos gerar todas as combinações de elementos de um conjunto finito Como uma combinação é apenas um subconjunto podemos usar a correspondência entre subconjuntos de a₁ a₂ aₙ e cadeias de bits de extensão n Lembrese de que uma cadeia de bits corresponde a um subconjunto que tem um 1 na posição k se aₖ for elemento do subconjunto e tem um 0 nesta posição se aₖ não for um elemento do subconjunto Se todas as cadeias de bits de extensão n podem ser listadas então pela correspondência entre subconjuntos e cadeias de bits uma lista de todos os subconjuntos é obtida Lembrese de que uma cadeia de bits de extensão n é também uma expansão binária de um número inteiro entre 0 e 2ⁿ 1 As 2ⁿ cadeias de bits podem ser listadas em ordem crescente de tamanho assim como os inteiros em suas expansões binárias Para produzir todas as expansões binárias de extensão n comece com a sequência 000 00 com n zeros Então encontre sucessivamente a próxima expansão até que a cadeia 111 11 seja obtida Em cada etapa a próxima expansão binária é encontrada localizandose a primeira posição à direita que não seja 1 e em seguida mudando todos os 1s à direita desta posição para 0s e trocando o primeiro 0 da direita por 1 EXEMPLO 4 Encontre a próxima cadeia de bits depois de 10 0010 0111 Solução O primeiro bit da direita que não for um 1 é o quarto bit da direita Mudamos esse bit para 1 e todos os bits subsequêntes para 0 Isto produzirá a próxima cadeia de bits 10 0010 1000 O processo de produção da próxima maior cadeia de bits depois de bₙ₁bₙ₂ b₁b₀ é dado pelo Algoritmo 2 ALGORITMO 2 Geração da Maior Cadeia de Bits Subsequênte procedure proxima cadeia de bit bₙ₁bₙ₂ b₁b₀ cadeia diferente de 1111 i 0 while bᵢ 1 begin bᵢ 0 i i 1 end bᵢ 1 A seguir daremos um algoritmo para a geração de rcombinações do conjunto 1 2 3 n Uma rcombinação pode ser representada por uma sequência que contém os elementos no subconjunto em ordem crescente As rcombinações podem ser listadas usandose a ordem lexicográfica dessas sequências A próxima combinação depois de a₁a₂ aᵣ pode ser obtida da seguinte forma primeiro localize o último elemento aᵢ na sequência tal que aᵢ n r i Depois substitua aᵢ por aᵢ 1 e aⱼ por aⱼ j i 1 para j i 1 i 2 r Resta ao leitor mostrar que isto produz a maior combinação subseqüente em ordem lexicográfica Este procedimento é ilustrado com o Exemplo 5 EXEMPLO 5 Encontre a maior 4combinação subseqüente do conjunto 1 2 3 4 5 6 depois de 1 2 5 6 Solução O último termo entre os termos aᵢ com a₁ 1 a₂ 2 a₃ 5 e a₄ 6 tal que aᵢ 6 4 i é a₂ 2 Para obter a maior 4combinação subsequente adicione 1 a a₂ para obter a₂ 3 Então o conjunto a₃ 3 1 4 e a₄ 3 2 5 Assim a maior 4combinação subsequente é 1 3 4 5 O Algoritmo 3 mostra os pseudocódigos para esse procedimento ALGORITMO 3 Geração da Próxima rCombinação em Ordem Lexicográfica procedure proxima rcombinacaoa₁ a₂ aᵣ o subconjunto adequado de 1 2 n diferente de n r 1 n com a₁ a₂ aᵣ i r while aᵢ n r i i i 1 aᵢ aᵢ 1 for j i 1 to r aⱼ aᵢ j i Exercícios 1 Coloque as permutações de 1 2 3 4 5 em ordem lexicográfica 43521 15432 45321 23451 23514 14532 21345 45213 31452 31542 2 Coloque as permutações de123456 em ordem lexicográfica 234561 231456 165432 156423 543216 541236 231465 314562 432561 654321 654312 435612 3 Encontre a maior permutação subsequente em ordem lexicográfica das permutações abaixo a 1432 b 54123 c 12453 d 45231 e 6714235 f 31528764 4 Encontre a maior permutação subsequente em ordem lexicográfica das permutações abaixo a 1342 b 45321 c 13245 d 612345 e 1623547 f 23587416 5 Use o Algoritmo 1 para gerar as 24 permutações dos quatro primeiros números inteiros positivos em ordem lexicográfica 6 Use o Algoritmo 2 para listar todos os subconjuntos do conjunto 1 2 3 4 7 Use o Algoritmo 3 para listar todas as 3combinações de 1 2 3 4 5 8 Mostre que o Algoritmo 1 produz a maior permutação subsequente em ordem lexicográfica 9 Mostre que o Algoritmo 3 produz a maior rcombinação subsequente em ordem lexicográfica dada uma rcombinação 10 Desenvolva um algoritmo para a geração de rpermutações de um conjunto com n elementos 11 Liste todas as 3permutações de 1 2 3 4 5 Os exercícios restantes desta seção desenvolvem outro algoritmo para a geração de permutações de 1 2 3 n Esse algoritmo é baseado nas expansões de números inteiros de Cantor Todo inteiro não negativo menor que n tem uma única expansão de Cantor a1 a2 an1n1 em que ai é um número inteiro não negativo não excedente a i para i 1 2 n 1 Os números inteiros a1 a2 an1 são chamados de dígitos de Cantor desse inteiro Dada uma permutação de 1 2 n considere ai1 k 2 3 n como o número de inteiros menores que k que são seguidos por k na permutação Por exemplo na permutação 43215 a1 é o número de inteiros menores que 2 que o acompanha então a1 1 Do mesmo modo para este exemplo a2 2 a3 3 e a4 0 Considere a função do conjunto de permutações 1 2 3 n para o conjunto de inteiros não negativos menores que n que levam uma permutação a um inteiro que tenha a1 a2 an1 definido desta maneira como dígitos de Cantor 12 Encontre os números inteiros que correspondem às permutações abaixo a 246531 b 12345 c 654321 13 Mostre que a correspondência descrita aqui é uma bijeção entre o conjunto de permutações de 1 2 3 n e os números inteiros não negativos menores que n 14 Encontre a permutação de 1 2 3 4 5 que corresponde aos números inteiros abaixo respeitando a correspondência entre as expansões de Cantor e as permutações como descrito no preâmbulo do Exercício 12 a 3 b 89 c 111 15 Desenvolva um algoritmo para produzir todas as permutações de um conjunto de n elementos com base na correspondência descrita no preâmbulo do Exercício 12 Termoschave e Resultados TERMOS combinatória o estudo dos arranjos de objetos enumeração a contagem dos arranjos de objetos diagrama de árvore um diagrama composto por uma raiz galhos que saem dessa raiz e outros galhos que saem do final de alguns galhos permutação um arranjo ordenado de elementos de um conjunto rpermutação um arranjo ordenado de r elementos de um conjunto Pn r o número de rpermutações de um conjunto com n elementos rcombinação uma seleção não ordenada de r elementos de um conjunto Cnr o número de rcombinações de um conjunto com n elementos n r coeficiente binomial também o número de rcombinações de um conjunto com n elementos demonstração combinatorial ou combinatória de uma identidade uma demonstração que usa argumentos de contagem para demonstrar que os dois lados de uma identidade fazem a contagem dos mesmos objetos mas de formas diferentes triângulo de Pascal uma representação de coeficientes binomiais em que a iésima linha do triângulo contém j para j 0 1 2 i RESULTADOS a regra do produto uma técnica básica de contagem que estabelece que o número de maneiras de fazer um procedimento que consiste em duas subtarefas é o produto do número de maneiras de fazer a primeira tarefa e o número de maneiras de fazer a segunda tarefa depois que a primeira foi executada a regra da soma uma técnica básica de contagem que estabelece que o número de maneiras de realizar uma tarefa de uma ou duas formas é a soma do número de maneiras de realizar essas tarefas se elas não puderem ser feitas simultaneamente o principio da casa dos pombos Quando mais de k objetos são colocados em k caixas deverá haver uma caixa que tenha mais de um objeto a generalização do princípio da casa dos pombos Quando N objetos são colocados em k caixas deverá haver um caixa que tenha pelo menos N k objetos Pn r nn r Cn r n r nrn r identidade de Pascal n1 k n k1 n k o binômio de Newton xyn n k xnk yk Há nrpermutações de um conjunto com n elementos com repetição Há Cn r 1 r rcombinações de um conjunto com n elementos com repetição Há nn1 n2 nk permutações de n objetos em que há nᵢ objetos idênticos do tipo i para i 1 2 3 k O algoritmo para gerar as permutações do conjunto 1 2 n Questões de Revisão 1 Explique como as regras da soma e do produto podem ser usadas para encontrar o número de cadeias de bits com comprimento não excedente a 10 2 Explique como encontrar o número de cadeias de bits de extensão não excedente a 10 que tenham pelo menos um bit 0 3 a Como a regra do produto pode ser usada para encontrar o número de funções de um conjunto com m elementos para um conjunto com n elementos b Quantas funções existem de um conjunto com cinco elementos para um conjunto com 10 elementos c Como a regra do produto pode ser usada para encontrar o número de funções injetoras de um conjunto com m elementos para um conjunto com n elementos d Quantas funções injetoras existem de um conjunto com cinco elementos para um conjunto com 10 elementos e Quantas funções sobrejetivas existem de um conjunto com cinco elementos para um conjunto com 10 elementos 4 Como é possível encontrar o número de resultados de uma eliminatória entre dois times em que o primeiro que vencer quatro jogos vence a eliminatória 5 Como é possível encontrar o número da cadeia de bits de extensão 10 que começa com 101 ou termina com 010 6 a Descreva o princípio da casa dos pombos b Explique como o princípio da casa dos pombos pode ser usado para mostrar que entre 11 números inteiros quaisquer pelo menos dois devem ter o último dígito igual 7 a Estabeleça a generalização do princípio da casa dos pombos b Explique como a generalização do princípio da casa dos pombos pode ser usada para mostrar que entre 91 números inteiros quaisquer pelo menos 10 têm o mesmo dígito final 8 a Qual a diferença entre uma rcombinação e uma rpermutação de um conjunto com n elementos b Derive uma equação que relaciona o número de rcombinações e o número de rpermutações de um conjunto com n elementos c Há quantas maneiras possíveis de escolher seis estudantes a partir de uma classe com 25 para montar um comitê d Há quantas maneiras possíveis de escolher seis estudantes a partir de uma classe com 25 para ocuparem seis cargos executivos diferentes em um comitê 9 a O que é o triângulo de Pascal b Como uma linha do triângulo de Pascal pode ser produzida a partir de outra acima dela 10 Qual o significado de uma demonstração combinatorial de uma identidade Qual a diferença entre essa demonstração e a algébrica 11 Explique como demonstrar a identidade de Pascal usando um argumento combinatorial 12 a Descreva o binômio de Newton b Explique como demonstrar o binômio de Newton usando um argumento combinatorial c Encontre o coeficiente de x100 y101 na expansão de 2x 5y201 13 a Explique como encontrar a fórmula para o número de maneiras de escolher r objetos a partir de n objetos com repetição sendo a ordem não relevante b Há quantas maneiras possíveis de escolher uma dúzia de objetos a partir de cinco tipos diferentes de objetos se os objetos do mesmo tipo são idênticos c Há quantas maneiras possíveis de escolher uma dúzia de objetos a partir de cinco tipos diferentes de objetos se deve haver pelo menos três objetos do primeiro tipo d Há quantas maneiras possíveis de escolher uma dúzia de objetos a partir de cinco tipos diferentes de objetos se não pode haver mais de quatro objetos do primeiro tipo e Há quantas maneiras possíveis de escolher uma dúzia de objetos a partir de cinco tipos diferentes de objetos se deve haver pelo menos dois objetos do primeiro tipo mas não mais que três do segundo tipo 14 a Considere n e r como números inteiros positivos Explique por que o número de soluções da equação x1 x2 xn r em que xi é um número inteiro não negativo para i 1 2 3 n é igual ao número de rcombinações de um conjunto com n elementos b Há quantas soluções com números inteiros não negativos são possíveis para a equação x1 x2 x3 x4 17 c Quantas soluções com números inteiros positivos são possíveis para a equação do item b 15 a Derive uma fórmula para o número de permutações de n objetos de k tipos diferentes em que há n₁ objetos idênticos do tipo um n₂ objetos idênticos do tipo dois e nk objetos idênticos do tipo k b Há quantas maneiras possíveis de ordenar as letras da palavra INDISCREETNESS 16 Descreva um algoritmo para gerar todas as permutações do conjunto dos n menores números inteiros positivos 17 a Há quantas maneiras possíveis de distribuir cinco cartas para seis jogadores a partir de um baralho com 52 cartas b Há quantas maneiras possíveis de distribuir n objetos distintos em k caixas distintas para que nᵢ objetos sejam colocados na caixa i 18 Descreva um algoritmo para gerar todas as combinações do conjunto com os n menores números inteiros positivos Exercícios Complementares 1 Há quantas maneiras possíveis de escolher 6 itens de 10 itens distintos quando a os itens escolhidos são ordenados e não há repetição b os itens escolhidos são ordenados e há repetição c os itens escolhidos não são ordenados e não há repetição d os itens escolhidos não são ordenados e há repetição 2 Há quantas maneiras possíveis de escolher 10 itens de 6 itens distintos quando a os itens escolhidos são ordenados e não há repetição b os itens escolhidos são ordenados e há repetição c os itens escolhidos não são ordenados e não há repetição d os itens escolhidos não são ordenados e há repetição 3 Um teste contém 100 questões do tipo falsoverdadeiro De quantas maneiras um estudante pode responder às questões desse teste se nenhuma questão pode ficar em branco 4 Quantas cadeias de bits de extensão 10 ou começam com 000 ou terminam com 111 5 Quantas cadeias de bits de extensão 10 sobre o alfabeto a b c têm exatamente três as ou quatro bs 6 Os números de telefone internos em um sistema de um campus possuem cinco dígitos com o primeiro dígito diferente de zero Quantos números de telefone diferentes o sistema suporta 7 Uma sorveteria tem 28 sabores diferentes 8 coberturas diferentes e 12 acompanhamentos a De quantas maneiras uma taça com três bolas de sorvete pode ser montada em que cada sabor pode ser colocado mais de uma vez e a ordem das bolas não é relevante b Quantos tipos diferentes de sundaes pequenos podem ser montados se um sundae pequeno tem uma bola de sorvete uma cobertura e um acompanhamento c Quantos tipos diferentes de sundaes grandes podem ser montados se um sundae grande tem três bolas de sorvete em que cada sabor pode ser colocado mais de uma vez e a ordem das bolas não é relevante dois tipos de cobertura em que cada cobertura pode ser usada apenas uma vez e a ordem não é relevante e três acompanhamentos em que cada acompanhamento pode ser usado apenas uma vez e a ordem não é relevante 8 Quantos números inteiros positivos menores que 1000 a têm três dígitos decimais b têm um número ímpar de dígitos decimais c têm pelo menos um dígito decimal igual a 9 d não têm dígitos decimais ímpares e têm dois dígitos decimais consecutivos iguais a 5 f são palíndromos ou seja podem ser lidos de frente para trás e de trás para frente 9 Quando os números de 1 a 1000 são escritos em notação decimal quantos dos dígitos abaixo são usados a 0 b 1 c 2 d 9 10 Há 12 signos do zodíaco Quantas pessoas são necessárias para garantir que pelo menos seis delas tenham o mesmo signo 11 Uma empresa de biscoitos da sorte faz 213 biscoitos diferentes Um estudante almoça em um restaurante que compra biscoitos dessa empresa Qual o maior número de vezes possível que o estudante pode comer no restaurante sem pegar quatro vezes o mesmo tipo de biscoito 12 Quantas pessoas são necessárias para garantir que pelo menos duas tenham nascido no mesmo dia da semana e no mesmo mês talvez em anos diferentes 13 Mostre que dado qualquer conjunto de 10 números inteiros positivos não excedentes a 50 existem pelo menos dois subconjuntos diferentes com cinco elementos que têm a mesma soma 14 Uma embalagem com figurinhas de beisebol contém 20 figurinhas Quantas embalagens devem ser compradas para garantir que duas cartas nessas embalagens sejam idênticas se há no total 550 figurinhas diferentes 15 a Quantas cartas devem ser escolhidas de um baralho para garantir que pelo menos dois ases sejam escolhidos b Quantas cartas devem ser escolhidas de um baralho para garantir que pelo menos dois ases e dois naipes sejam escolhidos c Quantas cartas devem ser escolhidas de um baralho para garantir que pelo menos duas cartas do mesmo naipe sejam escolhidas d Quantas cartas devem ser escolhidas de um baralho para garantir que pelo menos duas cartas de dois naipes diferentes sejam escolhidas 16 Mostre que em qualquer conjunto de n 1 números inteiros positivos não excedentes a 2n deve haver dois números primos entre si 17 Mostre que em uma sequência com m números inteiros existe um ou mais termos consecutivos com a soma divisível por m 18 Mostre que se cinco pontos forem escolhidos em uma quadra com comprimento de lado 2 então pelo menos dois desses pontos estão distantes não mais que 2 19 Mostre que uma expansão decimal de um número racional deve ter uma sequência repetida infinitamente a partir de um ponto 20 Uma vez que um vírus infecta um computador pessoal via email ele manda uma cópia dele mesmo a 100 endereços que se encontram na caixa de entrada desse computador Qual o número máximo de computadores diferentes que este computador pode infectar no tempo que leva para a mensagem infectada ser reenviada cinco vezes 21 Há quantas maneiras possíveis de escolher doze rosquinhas a partir de 20 variedades a se não houver duas rosquinhas da mesma variedade b se todas as rosquinhas forem da mesma variedade c se não houver restrições d se houver pelo menos duas variedades e se deverá haver pelo menos seis rosquinhas de amora f se não puder haver mais que seis rosquinhas de amora 22 Encontre n se a Pn 2 110 b Pn n 5040 c Pn 4 12Pn 2 23 Encontre n se a Cn 2 45 b Cn 3 Pn 2 c Cn 5 Cn 2 24 Mostre que se n e r são números inteiros não negativos e n r então Pn 1 r Pn rn 1n 1 r 25 Suponha que S seja um conjunto com n elementos Quantos pares ordenados A B são possíveis considerandose que A e B são subconjuntos de S com A B Dica Mostre que cada elemento de S pertence a A B A ou S B 26 Dê uma demonstração combinatorial do Corolário 2 da Seção 54 a partir da correspondência entre os subconjuntos de um conjunto com um número par de elementos e os subconjuntos desse conjunto com um número impar de elementos Dica Pegue um elemento x no conjunto Faça a correspondência colocando a no subconjunto se ainda não estiver ou tirandoo se ele estiver no subconjunto 27 Considere n e r como números inteiros não negativos com r n Mostre que Cn r 1 Cn 2 r 1 2Cn 1 r 1 Cn r 1 28 Demonstre usando a indução matemática que j2Cj 2 Cn 1 3 sempre que n for um número inteiro maior que 1 29 Mostre que se n for um número inteiro então k03 n k 4n 30 Neste exercício vamos derivar uma fórmula para a soma dos quadrados dos n menores números inteiros positivos Contaremos o número de triplas i j k considerandose que i j e k são números inteiros sendo que 0 i k 0 j k e 1 k n de duas maneiras a Mostre que há k2 de tais triplas com base k Conclua que há k1n k2 triplas b Mostre que o número de triplas com 0 i j k e o número de triplas com 0 j i k é igual a Cn 1 3 c Mostre que o número de triplas com 0 i j k é igual a Cn 1 2 d Combine os itens a b e c e conclua que k1n k2 2Cn 1 3 Cn 1 2 nn 12n 16 31 Quantas sequências de bits de extensão n em que n 4 contêm duas ocorrências de 01 32 Considere S como um conjunto Dizemos que uma coleção de subconjuntos A1 A2 An cada um com d elementos em que d 2 é 2colorável se for possível designar a cada elemento de S uma de duas cores diferentes tal que cada subconjunto Ai tenha elementos que sejam coloridos com cada cor Considere md como o maior número inteiro tal que toda a coleção menor que md conjuntos com d elementos seja 2colorável a Mostre que a coleção de todos os subconjuntos com d elementos de um conjunto S com 2d 1 elementos não é 2colorável b Mostre que m2 3 c Mostre que m3 7 Dica Mostre que a coleção 1 3 5 1 2 6 1 4 7 2 3 4 2 5 7 3 6 7 4 5 6 não é 2colorável Então mostre que todas as coleções de seis conjuntos com três elementos cada são 2coloráveis 33 Um professor escreve 20 questões de múltipla escolha cada uma com as possíveis respostas a b c ou d para um teste de matemática discreta Se o número de questões com as alternativas a b c e d tiverem como resposta 8 3 4 e 5 respectivamente quantas respostas corretas diferentes são possíveis se as questões podem ser colocadas em qualquer ordem 34 Há quantos arranjos diferentes possíveis de oito pessoas sentaremse em uma mesa redonda em que dois arranjos são considerados os mesmos se um for obtido pelo outro a partir de uma rotação 35 Há quantas maneiras possíveis de distribuir 24 estudantes como cinco conselheiros da faculdade 36 Há quantas maneiras possíveis de escolher uma dúzia de maçãs de uma caixa que contém 20 maçãs idênticas Delicious 20 maçãs idênticas Macintosh e 20 maçãs idênticas Granny Smith se pelo menos três de cada tipo devem ser escolhidas 37 Quantas soluções são possíveis para a equação x1 x2 x3 17 em que x1 x2 e x3 são números inteiros não negativos com a x1 1 x2 2 e x3 3 b x1 6 e x3 5 c x1 4 x2 3 e x3 5 38 a Quantas sequências diferentes podem ser feitas com a palavra PEPPERCORN quando todas as letras forem usadas b Quantas dessas sequências começam e terminam com a letra P c Em quantas dessas sequências as três letras P aparecem em posição consecutiva 39 Quantos subconjuntos de um conjunto com 10 elementos a têm menos que cinco elementos b têm mais que sete elementos c têm um número ímpar de elementos 40 Uma testemunha de um acidente em que o motorista fugiu conta à polícia que a placa do carro que contém três letras seguidas de três números começa com as letras AS e contêm os números 1 e 2 Quantas placas diferentes cabem nesta descrição 41 Há quantas maneiras possíveis de colocar n objetos idênticos em m contêineres distintos para que nenhum contêiner fique vazio 42 Há quantas maneiras possíveis de sentar seis garotos e oito garotas em uma fila de cadeiras para que nenhum garoto sente ao lado de outro 43 Há quantas maneiras possíveis de distribuir seis objetos em cinco caixas se a os objetos e as caixas são distintos b os objetos são distintos mas as caixas idênticas c os objetos são idênticos mas as caixas distintas d os objetos e as caixas são idênticos 44 Há quantas maneiras possíveis de distribuir cinco objetos em seis caixas se a os objetos e as caixas são distintos b os objetos são distintos mas as caixas idênticas c os objetos são idênticos mas as caixas distintas d os objetos e as caixas são idênticos 45 Desenvolva um algoritmo para gerar todas as rpermutações de um conjunto finito com repetição 46 Desenvolva um algoritmo para gerar todas as rcombinações de um conjunto finito com repetição 47 Mostre que se m e n são números inteiros com m 3 e n 3 então Rm n Rm n 1 Rm 1 n 48 Mostre que R3 4 7 mostrando que em um grupo de seis pessoas em que duas pessoas são amigos ou inimigos não há necessariamente três amigos mútuos ou quatro inimigos mútuos Explorando a Computação Use um programa ou programas computacional que você escreveu para resolver estes exercícios 1 Encontre o número de possíveis resultados de uma eliminatória com dois times quando o vencedor é o primeiro time que vencer 5 de 9 6 de 11 7 de 13 e 8 de 15 partidas 2 Quais coeficientes binomiais são ímpares Você pode formular uma conjectura baseada em uma evidência numérica 3 Verifique que C2n n é divisível pelo quadrado de um primo quando n 1 2 ou 4 para tantos números inteiros positivos n quantos você puder O teorema que diz que C2n n é divisível pelo quadrado de um primo com n 1 2 ou 4 foi demonstrado em 1996 por Andrew Granville e Olivier Ramaré Essa demonstração foi baseada em uma conjectura feita em 1980 por Paul Erdős e Ron Graham 4 Encontre quantos números n você puder que sejam inteiros ímpares menores que 200 e para os quais Cn n2 não é divisível pelo quadrado de um número primo Formule uma conjectura baseada em sua evidência 5 Para cada número inteiro menor que 100 determine se C2n n é divisível por 3 Você pode formular uma conjectura que nos diga que para número inteiro n o coeficiente binomial C2n n é divisível por 3 baseado nos dígitos da expansão de n em base três 6 Gere todas as permutações de um conjunto com oito elementos 7 Gere todas as 6permutações de um conjunto com nove elementos 8 Gere todas as combinações de um conjunto com oito elementos 9 Gere todas as 5combinações com repetição de um conjunto com sete elementos Projetos Responda a estas questões com informações encontradas em outras fontes 1 Descreva os primeiros usos do princípio da casa dos pombos feitos por Dirichlet e outros matemáticos 2 Discuta qual plano telefônico atual pode ser expandido para acomodar a rápida demanda por mais números de telefone Veja se você pode encontrar algumas das propostas vindas da indústria de telecomunicações Para cada novo plano telefônico mostre como encontrar o número de diferentes números de telefone que ele suporta 3 Muitas identidades combinatórias são descritas neste livro Encontre algumas fontes de tais identidades e descreva identidades combinatórias importantes além das já introduzidas neste livro Dê algumas demonstrações representativas incluindo as combinatórias de algumas dessas identidades 4 Descreva os diferentes modelos utilizados na distribuição de partículas em mecânica estatística incluindo os modelos de MaxwellBoltzmann BoseEinstein e FermiDirac Em cada caso descreva as técnicas de contagem usadas no modelo 5 Defina os números de Stirling de primeira ordem e descreva algumas de suas propriedades e as identidades que eles satisfazem 6 Defina os números de Stirling de segunda ordem e descreva algumas de suas propriedades e as identidades que eles satisfazem 7 Descreva as últimas descobertas de valores e aproximações dos números de Ramsey 8 Descreva maneiras adicionais de gerar todas as permutações de um conjunto com n elementos entre aqueles encontrados na Seção 56 Compare esses algoritmos e os algoritmos descritos no texto e nos exercícios da Seção 56 em termos de sua complexidade computacional 9 Descreva pelo menos uma maneira de gerar todas as partículas de um número inteiro positivo n Veja o Exercício 47 da Seção 43 51 Questão 41 De quantas maneiras um fotografo pode organizar seis pessoas numa fila em um casamento incluindo a noiva e o noivo se a a noiva deve estar ao lado do noivo b a noiva não está ao lado do noivo c a noiva está posicionada à esquerda do noivo Resposta a Primeiro vamos tratar a noiva e noivo como uma pessoa só já que queremos que eles fiquem juntos Logo queremos colocar 5 pessoas em fila Para a 1ª posição são 5 opções para a 2ª restam 4 após escolher a primeira para a 3ª ficam 3 opções depois das anteriores para a 4ª posição 2 opções e para a 5ª apenas 1 opção sobra após as demais Pela regra do produto temos 54321 120 maneiras de fazer essa fila de 5 pessoas Só que uma dessas pessoas é na verdade o noivo e a noiva que podem trocar de posição entre si logo cada caso temos que contar 2 vezes Portanto pela regra do produto temos 2120 240 maneiras b Se sabemos que em 240 casos a noiva está do lado do noivo pelo item a então basta subtrair isso dos casos totais pois só existem duas possibilidades ou estão do lado ou não Para calcular os casos totais basta usar o pensamento análogo para arrumar 6 pessoas numa fila 1ª posição 6 opções 2ª posição 5 opções 3ª posição 4 opções 4ª posição 3 opções 5ª posição 2 opções e 6ª posição 1 opção Logo 654321 720 maneiras Dessas 720 em 240 a noiva está do lado do noivo logo em 720240 480 não está c Perceba que nas 720 maneiras totais de arrumar a fila a noiva sempre estará ou à esquerda ou à direita do noivo e essas duas possibilidades tem iguais chances de ocorrer pois não há nenhuma restrição ou caso especial Logo cada uma delas ocorre metade das vezes e portanto em 7202 360 maneiras da noiva está à esquerda do noivo 52 Questão 10 Considere xi yi i 1 2 3 4 5 como um conjunto de cinco pontos com coordenadas inteiras no plano xy Mostre que o ponto médio da linha que junta pelo menos um par desses pontos tem coordenadas inteiras Resposta Primeiro vejo que dados dois pontos diferentes desse conjunto xi yi e xj yj as coordenadas do ponto médio são xi xj 2 yi yj 2 logo serão inteiras se as duas primeiras coordenadas tiverem a mesma paridade e as duas segundas também pois assim a soma é divisível por 2 Ter a mesma paridade é ambas ímpares ou ambas pares par ou ímpar Temos 5 pontos e 2 possíveis paridades para 1ª coordenada logo pelo Princípio das Casas de Pombos pelo menos 3 desses pontos tem a 1ª coordenada com a mesma paridade