Funções entre Conjuntos Finitos: Atividades e Problemas

J Atividade 1 a Quantas funcdes f A B e tem do conjunto Aaaa no conjunto Bbb b Quantas funcoes f B A existem do conjunto Bbb no conjunto Aaaa Resposta Comentada Como estamos trabalhando com conjuntos que possuem poucos elementos podemos enumerar efetivamente todas as possibilidades No item a podemos construir as seguintes funcdes ab b ah b ay by ako bb ah b ah b ap Fo by ah bb ah b ah b ak b ak b ako b ah b ak b ako b a3 by a3 bo a3 b az by a3 bb ah b a FD by az F bp No total sdo 23 8 funcdes diferentes No item b podemos construir as seguintes funcdes ba be a bre a baw b Fe a be aw bea ba b Fe a3 b FY a bY a bs FO a3 by FY a b FY a bY a bs FY a3 bs FY ay by FY a No total sao 3 9 funcoes diferentes A atividade anterior nos fornece um indicio de como contar quaisquer tipos de funcgdes entre dois conjuntos finitos Vamos agora estudar o caso geral f Caso geral Se 0 conjunto A tem n elementos e o conjunto B tem k elementos A yfx B quantas funcdes existem de A em B A dominio da funcao f B contradominio da funcao f 80 Modulo Il Matematica Discreta Etapa lll MatematicaDiscretaindd 80 150813 1745 Atividade 2 Focalizando na ideia de contar funções e não fazendo uma mera aplicação de fórmulas resolva os dois problemas a seguir Fazer diagramas e desenhos ajuda muito a resolver esse tipo de questão a De quantas maneiras distintas podemos colocar 7 cartas em 5 caixas de coleta do correio b Jorge tem 4 camisas para serem guardadas em 6 gavetas de seu guardaroupa De quantas maneiras ele pode guardar essas camisas Resposta comentada a Para simplificar vamos representar o conjunto de cartas por Aa1 a2 a7 e o conjunto de caixas do correio por Bb1 b2 b3 Seguiremos os passos anteriores a1 a2 a7 Escrever o número de caixas do correio que podem receber a carta a1 Escrever o número caixas do correio que podem receber a carta a2 Nesse caso é possível que uma caixa que tenha recebido a carta a1 possa em outra possibilidade também receber a carta a2 Escrever o número caixas do correio que podem receber a carta a7 Nesse caso é possível que uma caixa que tenha recebido a carta a1 ou a carta a2 ou a carta a6 possa em outra possibilidade também receber a carta a7 3 3 3 Nesse caso pode haver repetições pois uma caixa que recebe a carta a1 pode em outra possibilidade receber a carta a2 receber a carta a3 e receber a carta a7 Pelo Princípio Multiplicativo existem 3333 37 2187 maneiras de colocar 7 cartas em três caixas distintas do correio A situação pode ser vista do seguinte modo tenho três cartas em minhas mãos e coloqueias em uma determinada ordem Seleciono a primeira delas e decido em qual caixa de correio vou colocála 7 possibilidades A seguir seleciono a segunda carta e procedo da mesma forma Existem 7 possibilidades pois uma mesma caixa de coleta pode receber mais de uma carta Finalmente repito o procedimento com a última carta outras 7 possibilidades É cabível que as três cartas ocupem a mesma caixa e que as outras duas fiquem vazias No total há 777 2187 possibilidades Atividade 2 Sanja Gjenero SXC Adrian Gtz SXC 7 vezes 82 Módulo II Matemática Discreta Etapa III MatematicaDiscretaindd 82 150813 1745 J Atividade 3 a Conte quantas funcoes bijetoras f A B existem do conjunto A a a no conjunto B b b b Conte quantas funcées bijetoras f B A existem do conjunto A a a a no conjunto B b b b Resposta comentada Proceda como antes listando as fungdes e nado se esquecendo que numa bijecdo f entre dois conjuntos A e B nao sobram elementos em B que nao estejam associados a algum elemento de A Além disso cada elemento de B fica associado a apenas um elemento de A Assim no item a temos apenas duas possibilidades de funcées a Fe b a Fe b a Fe b a Fe b Ja no item b temos seis possibilidades de fungodes a Fb a b ar b a b D a F b a F Db a Fb ak b a b D a b a b D a b a D a b D a b D a b D a D a D Apos essa atividade podemos responder o caso geral de contagem de funcées bijetoras f Caso geral Se A tem n elementos e B também tem n elementos quantas fungdes bijetoras existem de A em B A B Ao primeiro elemento do dominio A podemos associar qualquer um dos n elementos de B Feito isto a escolha para a imagem do segundo elemento de A so pode ser feita de n1 ma neiras diferentes ja que todo elemento de B é associado apenas a um elemento de A e a escolha da imagem do primeiro elemento ja foi feita O terceiro elemento de A so pode ser associado a um dos n2 elementos restantes de B e assim sucessivamente até o Ultimo elemento de A 84 Modulo ll Matematica Discreta Etapa lll MatematicaDiscretaindd 84 150813 1745 Atividade 4 Resolva os problemas abaixo utilizando duas aborda gens primeiro a ideia de permutação e depois a ideia de contagem de funções a De quantos modos 7 pessoas podem sentar em uma fila de 7 cadeiras b Em uma festa com 10 homens e 10 mulheres de quantas maneiras podemos formar dez casais distin tos de um homem e uma mulher Resposta comentada a Primeira abordagem contar como 7 pessoas senta rão em 7 cadeiras é o mesmo que saber de quantas maneiras podemos permutar essas pessoas quando sentadas O problema portanto reduzse a contar o número de permutações de um conjunto com 7 elementos cuja resposta como já sabemos é 7 Segunda abordagem chamemos o conjunto de pessoas de Pp1 p2 p3 p4 p5 p6 p7 e o conjunto de cadeiras de Cc1 c2 c3 c4 c5 c6 c7 Associando cada pessoa à cadeira em que ela se sentará produzimos Atividade 4 Quando alcançarmos o último elemento de A só resta uma última opção entre os elementos de B já que A e B têm o mesmo número de elementos Esses procedimentos podem ser resumidos na tabela a seguir a1 a2 a3 an Escrever o número de opções dos elementos de B que podem ser associados ao elemento a1 Escrever o número restante de opções dos elementos de B que após associarmos um elemento a a1 podem ser associados ao elemento a2 Escrever o número restante de opções dos elementos de B que após associarmos um elemento a a1 e outro a a2 podem ser associados ao elemento a3 Escrever o número restante de opções dos elementos de B que após associarmos um elemento a a1 outro a a2 outro a a3 outro a an1 podem ser associados ao elemento an n elementos n1 n21 elementos n2 n31 elementos 1 nn1 Como não há repetições ao associarmos um elemento a outro esse elemento não pode mais ser associado a nenhum dos demais Pelo Princípio Multiplicativo há Pn nn 1n 2321 n funções bijetoras entre dois conjuntos com n elementos Observe que esse é o número de permutações sem repetição de um conjunto com elementos Esse fato simplesmente nos diz que uma função bijetora entre conjuntos finitos nada mais faz do que permutar os elementos do conjunto imagem É importante ressaltar que existem vários problemas que podem ter apresentações diferentes mas com soluções absolutamente iguais que recaem simplesmente em contar o número de funções bijetoras entre conjuntos 5 Cada chave uma função mas quantas 85 MatematicaDiscretaindd 85 150813 1745 uma função entre os conjuntos P e C Como duas pes soas distintas irão sentar em cadeiras distintas e como nenhuma cadeira sobrará sem que uma pessoa esteja sentada nela essa função deve ser bijetora Mudando a posição das pessoas sentadas mudamos a função bijetora e viceversa Daí saber de quantas maneiras sete pessoas se sentarão em sete cadeiras é contar o número de funções bijetoras entre os conjuntos P e C Vimos anteriormente que este número é 7 b Proceda como no item a associando agora homens com mulheres A resposta é 10 Atividade 5 Utilizando seus conhecimentos de contagem de funções adquiridos até aqui e a definição de função injetora responda às questões a seguir a Quantas funções injetoras f A B existem do conjunto Aa1 a2 no conjunto Bb1 b2 b3 b Quantas funções f C D existem do conjunto C c1 c2 no Dd1 d2 d3 d4 Resposta comentada Proceda novamente listando todas as funções injetoras e não se esqueça que em uma função injetora f entre dois con juntos A e B um elemento de B quando está associado a um elemento de A deve estar associado apenas àquele elemento Lembrese ainda que nas funções injetoras podem sobrar elementos no conjunto B que não estejam associados a qualquer elemento do conjunto A Atividade 5 Adam Ciesielski SXC 53 Contando funções injetoras entre conjuntos finitos f A B Lembremos que em uma função injetora elementos distintos do conjunto A são levados em imagens distintas no conjunto B Devido a esse fato se os conjuntos A e B forem finitos o número de elementos de A não pode exceder o número de elementos de B Ou seja o número de elementos de A é menor do que ou igual ao número de elementos de B assim quantas funções injetoras existem entre dois conjuntos A e B 86 Módulo II Matemática Discreta Etapa III MatematicaDiscretaindd 86 150813 1745 Atividade 6 Mais uma vez ressaltamos há também vários problemas que podem ter apresentações diferentes mas com a mesma solução que recai simplesmente em contar o número de funções injetoras entre conjuntos Resolva dois deles a seguir associando sua resolução à contagem de funções injetoras a De quantas maneiras podemos estacionar 4 carros em 7 garagens se em cada garagem pode ficar apenas um carro b Compare o problema anterior com o problema de se colocar 4 cartas em 7 caixas de coleta do correio Qual a diferença Atividade 6 Mais uma vez ressaltamos há também vários problemas que podem ter apresentações diferentes mas com a mesma solução que recai simplesmente em contar o número de funções injetoras entre conjuntos Michal Zacharzewski SXC Agora passemos ao caso geral Caso Geral Se A tem n elementos e B tem k elementos e n k quantas funções injetoras existem de A em B Vamos considerar os conjuntos A a1 a2 an e B b1 b2 bk em que n k a1 a2 a3 an Escrever o número de opções dos elementos de B que podem ser associados ao elemento a1 Escrever o número restante de opções dos elementos de B que após associarmos um elemento a a1 podem ser associados ao elemento a2 Escrever o número restante de opções dos elementos de B que após associarmos um elemento a a1 e outro a a2 podem ser associados ao elemento a3 Escrever o número restante de opções dos elementos de B que após associarmos um elemento a a1 outro a a2 outro a a3 outro a an1 podem ser associados ao elemento an k elementos k1k21 elementos k2k31 elementos kn1 Como não há repetições ao associarmos um elemento de A a um elemento de B esse elemento de B não pode mais ser associado a nenhum dos demais Pelo Princípio Multiplicativo há funções injetoras entre um conjunto com n elementos noutro conjunto com k elementos em que n k Observe que esse é o número de arranjos de n elementos tomados em um conjunto de k elementos sem repetições A B f 88 Módulo II Matemática Discreta Etapa III MatematicaDiscretaindd 88 150813 1746 Atividade 7 Na Etapa 2 resolvemos os seguintes exercícios usando combinação a Um grupo de cinco professores comporá uma comissão para falar com o Secretário de Educação do Estado Os cinco professores serão escolhidos dentre nove professores indicados por seus pares Quantas comissões poderão ser formadas Agora resolva esse exercício usando a ideia de contar funções estri tamente crescentes b Quantas saladas de frutas diferentes podemos fazer usando três das quatro frutas abacaxi banana caqui e damasco Resolva usando a contagem de funções Para isto você deve ordenar o conjunto das frutas Resposta comentada a Chamemos o conjunto dos professores de Pp1 p2 p9 e o conjunto dos professores escolhidos de Ee1 e2e5 Escritos dessa forma os conjuntos estão ordenados O problema agora pode ser visto da seguinte forma como contar o número de funções estritamente crescentes entre os conjuntos E e P A partir desse ponto use a ideia de combinação para fazer essa contagem de funções e você verá que a resposta é 126 Note que nesse caso descrever todas essas funções é muito trabalhoso b Chamemos o conjunto de frutas de F abcd a de abacaxi b de banana c de caqui e d de damasco e o conjunto das frutas a serem escolhidas para a salada de S 12 3 1 para a primeira escolha 2 para a segunda e 3 para a terceira Esses conjuntos agora estão ordenados O problema agora pode ser visto da seguinte forma como contar o número de funções estritamente crescente entre os conjuntos S e F Como estamos trabalhando com conjuntos que possuem poucos elementos use diagramas de setas e tabelas para fazer essa contagem e você verá que a resposta é 4 Note que esse número é o número de combinações de um conjunto de 4 elementos tomados 3 a 3 Atividade 7 Jade Gordon SXC Jean Scheijen SXC ZooFari httpcommonswikimedia orgwikiFileBananaFruitJPG Elisabetta Grondona SXC Autor desconhecido SXC Portanto contar o número de funções estritamente crescentes entre um conjunto orde nado A com n elementos e um conjunto ordenado B com k elementos n k é o mesmo que contar o número de combinações tomadas n a n de um conjunto com n elementos 92 Módulo II Matemática Discreta Etapa III MatematicaDiscretaindd 92 150813 1746 Atividade 8 Vamos resolver mais um problema que pode ser solucio nado através de uma das três maneiras anteriores No laboratório de Biologia da professora Regina nas ceram 6 ratinhos brancos idênticos Para estudálos ela resolveu separálos em dois grupos colocandoos em duas gaiolas diferentes De quantas maneiras diferentes isso pode ser feito Resposta comentada A maneira mais natural de atacar esse problema é contar o número de ratinhos que podem participar de cada grupo Grupo 1 Grupo 2 1 5 2 4 3 3 4 2 5 1 Logo teremos 5 maneiras de dividir os ratinhos Porém essa enumeração não levou em conta duas possibilidades 1 a primeira gaiola fica vazia e a segunda com 6 rati nhos 2 a segunda gaiola fica vazia e a primeira com 6 rati nhos Levando em conta essas possibilidades o número de maneiras de dividir os ratinhos cresce para 7 Atividade 8 ser feito essa enumeração não levou em conta duas possibilidades maneiras de dividir os ratinhos cresce para 7 Rob OwenWahl SXC Diante do que acabamos de ver temos três problemas aparentemente bem distintos que podem ser abordados por meio de uma mesma ideia Resolvendo um desses problemas resolvemos todos eles 96 Módulo II Matemática Discreta Etapa III MatematicaDiscretaindd 96 150813 1746 ee ee Agora tente responder Qual o numero de solucées positivas ou nulas TC da equacado x x x x 3 i é a EE 2 Diante do que ja vimos a resposta é Cea Ce 20 que é precisamente o numero de fungdes nadodecrescentes de um conjunto com n3 elementos em um conjunto com k4 elementos Nesse momento é possivel comparar essa solucao com o numero de escolhas de 3 refri gerantes dentre 4 disponiveis vocé se lembra desse problema As solugdes sao idénticas Y xX Xx2 As solucdes da equacdo sao Considere a seguinte pergunta Quantas y 2000 20 0 02 1 10 1 01 0 0 1 sdo as maneiras de se escolher 2 calcas se te Resposta 6 maneiras mos a nossa disposiao 3 marcas diferentes ig f é Compare ainda o resultado com a formula dada nesta Dé uma resposta para essa pergunta F 2 secdo que conta o numero de solucées positivas ou a enumerando os casos yf e f nulas dessa equacgao no caso em que k3 e n2A b relacionando o problema com uma resposta é C3Cj 6 maneiras equacao c contando o numero de funcdes c Chame o conjunto das marcas das calcas de M A B C eo conjunto das calcas de Kc c ou seja c Resposta comentada é a calca escolhida em primeiro lugar e ca escolhida em segundo lugar e os ordenemos conforme essa a Chame o conjunto das marcas das calcas de descrigao O problema reduzse a contar o numero MABC Basta agora contar os casos dessa esco de funcdes naodecrescentes entre K e M Enumere ha AA AB AC BB BC e GC Note que mos essas funcdes por seus pares ordenados ABBA ACCA cy Al Cy AD e Resposta 6 maneiras c A c B cy Al Cy Oh b Se o numero de calcas da marca A é X 0 da c B c B marca B é x eo da marca C é xX o problema c B c Ce pode ser resolvido contandose o numero de c C c C solugdes inteiras positivas ou nulas da equacao e Resposta 6 fungdes ndodecrescentes entre K e M 6 Combinacdes com repeticdo e contagem de funcdes que nunca decrescem 101 MatematicaDiscretaindd 101 150813 1746 Atividade 10 Nesta atividade final preparamos um quadroresumo dos vários tipos especiais de contagem que estudamos durante nossas primeiras três etapas Sua tarefa é ajudarnos a preenchêlo respondendo às perguntas em alguns quadros Obs Princípio Multiplicativo Se uma decisão d1 puder ser tomada de m maneiras e se uma vez tomada a decisão d1 outra decisão d2 puder ser tomada de n maneiras diferentes então o número total de se tomarem as decisões é o produto de m por n ANÁLISE COMBINATÓRIA QUADRORESUMO Respeitando a ordem Simples Fórmula Com repetição Fórmula Permutações Ex De quantas maneiras diferentes podemos estacionar 6 carros em 6 garagens Resp O número de permutações de n elementos é Resp Ex Quantos são os anagramas de URUGUAI que começam com I Resp O número de permutações de n objetos dos quais 1p é igual a 1a 2p é igual a 2a kp é igual a ka é Resp Atividade 10 continua Se 1x é o número de vasos pintados na cor vermelha e 2x é o número de vasos pinta dos de verde então 1 2 3 x x O número de soluções positivas ou nulas dessa equação é 2 1 1 3 2 1 4 4 C C No caso de 4 cores e 5 vasos o número de combinações possíveis é igual ao nú mero de soluções positivas ou nulas da equação 1 2 3 4 5 x x x x que é dado por 4 1 3 4 5 1 8 56 C C Esses exemplos mostram a aplicabilidade das combinações com repetição e ilustram mais uma vez como uma mesma ideia matemática pode ser abordada de várias manei ras Dessa forma pudemos analisar melhor a contagem do número de combinações com repetição que é um assunto pouco abordado em sala de aula A seguir você poderá fazer uma atividade que resume todo o conteúdo de Combi natória que estudamos nas Etapas 1 2 e 3 Como a Etapa 4 abordará principalmente o conceito de Probabilidade essa atividade também servirá como um bom fechamento de todo o estudo de Análise Combinatória feito até aqui em nossa disciplina 104 Módulo II Matemática Discreta Etapa III MatematicaDiscretaindd 104 150813 1746