Caro Korshinói, No segundo grau, me ensinaram a dissociar permutação, arranjo e combinação usando uma palavreado de ordem e natureza que em vez de me ajudar só fez uma confusão dos assuntos na minha cabeça.
Existe uma fórmula que engloba todas as outras e que considero muito mais simples e esclarecedora. Suponha que temos elementos de vários tipos (possivelmente mais de um elemento de cada tipo). Para simplificar (com uma notação geral) vou chamar os tipos de: tipo 1, tipo 2, tipo 3, ..., tipo K. Vou dizer que temos a_1 elementos do tipo correspondente a 1, a_2 elementos do tipo 2, ..., a_K elementos do tipo K. De forma que dois elementos do mesmo tipo (por exemplo do tipo 3) não podem ser diferenciados um do outro, eles são idênticos. Agora considere uma caixa com todos esses elementos. A caixa tem, portanto, a_1+a_2+...+a_K = N elementos. Faço a seguinte pergunta: - De quantos modos posso retirar dessa caixa todos os N elementos (um por um) de forma que, como disse, dois elementos do mesmo tipo são indistingüiveis? Se você souber responder a essa pergunta, saberá responder a qualquer pergunta sobre combinações, arranjos e permutações. Mostrarei como no final. Primeiro vamos responder a essa pergunta. A idéia que tenho em mente é a seguinte. Inicialmente considere todos os N elementos (lembre-se que N = a_1+a_2+...+a_k) distintos entre si, e numere-os por 1, 2, ...., N. Pergunto: de quantos modos podemos retirar um por um os elementos da caixa? Bem, o primeiro elemento pode ser qualquer um dos N. O segundo pode ser qualquer um dos N-1 restantes (são todos distintos), portanto temos N*(N-1) modos pelo princípio fundamental da contagem. Seguindo assim, concluimos que temos N*(N-1)*(N-2)*...*2*1 = N! modos de retirar todos esse elementos da caixa. A idéia agora, é tranformar os a_1 primeiros elementos numerados (1, 2, ..., a_1) da caixa no tal tipo 1. Ou seja, façamos todos eles iguais. E fazemos a pergunta: de quantos modos podemos retirar os elementos um por um da caixa? Em cada um dos N! modos anteriores, temos os elementos 1, 2, ..., a_k presentes. Como identificamos esses elementos, cada permutação é identificada com muitas outras, para ser preciso, com exatamente a_1! outras. Por que? Suponhamos que em uma das N! permutações os elementos 1, 2,..., a_1 ocupem determinadas posições fixas. Nós podemos alternar esses elementos entre si e ainda teremos a mesma permutação (isso depois de identificar os elementos), e podemos fazer isso de a_1*(a_1-1)*(a_1-2)*...*2*1 = a_1 maneiras, pois em cada uma das posições fixas, em ordem, vamos dispondo os elementos 1, 2, ..., a_1. Portanto separamos as N! permutações anteriores em grupos de a_1! permutações e as identificamos, logo restam N! / a_1! permutações. Faça o mesmo raciocínio para a_2, identificando os elementos a_1+1, a_1+2, ..., a_1+a_2. E restará (N! / a_1!) / a_2! = N! / (a_1!*a_2!). Prossiga esse raciocínio até o tipo K. Restará N! / (a_1! * a_2! * a_3! *...* a_k!) ou, o que dá no mesmo, (a_1 + a_2 +...+ a_k)! / (a_1! * a_2!* a_3! *...* a_k!). Tentarei esclarecer com um exemplo o processo acima. Imagine que tenho 3 letras a, 2 letras b, e 5 letras c. E quero formar palavras de 10 letras utilizando todas elas. A idéia é começar perguntando. Se as dez letras forem diferentes (0, 1, ..., 9), quantos serão as palavras? Um total de 10!. Se idenfiticarmos as 3 primeiras letras (0, 1, 2) como sendo a letra a, quantas serão as pelavras? 10! / 3!. Se identificarmos as 2 letras seguinte (3, 4) como sendo a letra b, quantas palavras poderemos formar? 10! / (3! * 2!). Finalmente, se identificarmos as 5 últimas letras (5, 6, 7, 8, 9) como sendo a letra c, quantas palavras poderemos formar? 10! / (3! * 2! * 5!). E essas são as palavras com 3 a's, 2 b's e 5 c's. COMBINAÇÕES Quantos são os subconjuntos de P elementos de um conjunto com N elementos? Enumeramos os N elementos: 1, 2, ..., P, P+1, ..., N. De quantos modos podemos permutá-los, ou seja, tirá-los um por um de uma caixa? Exatamente N!. Se identificarmos os P primeiros (1, 2, ..., P) por a, restará N! / P! maneiras. Se identificarmos os N-P últimos (P+1, ..., N) por b, restará N! (P! * (N-P)!). Para cada palavra (aabbaba...ba) corresponde o suconjunto dos elementos cujos números são as posições de a nessa palávra. E para cada subconjunto de P elementos dos N números, corresponde uma palavra (abaa...ba) onde os a's estão na posicão dos elementos selecionados e os b's dos elementos deixados de lado. ARRANJOS Quantas são os conjuntos ordenados de P elementos de um conjunto com N elementos? Enumeramos os N elementos: 1, 2, ..., P, P+1, ..., N. De quantos modos podemos permutá-los, ou seja, tirá-los um por um de uma caixa? Exatamente N!. Identificamos os N-P últimos por b, restará N! / (N-P)! permutações. Para cada palavra (1bbPb...23b) corresponde uma subconjunto de P elementos onde o primeiro é a posição onde se encontra o 1, o segundo corresponde à posição onde está o 2, e assim por diante. A cada suconjunto de P elementos ordenados, corresponde uma palavra do mesmo modo. PERMUTAÇÕES Esse termo é que engloba todos os outros. Espero ter esclarecido muito pontos. O assunto combinatória certamente não termina aqui. Existem muitas outras formas de permutar elementos, em círculos, de forma caótica, ... Mas o básico, que é cobrado - acredito - nos vestibulares de todo o país está aí. Um grande abraço a todos! Eduardo Casagrande Stabel. Porto Alegre, RS. >From: [EMAIL PROTECTED] > >Gostaria de saber se combinações com repetições são exploradas no >vestibular. Gostaria de saber onde encontro algo sobre isso, haja vista, que >nos principais livros que abordam análise combinatória no ensino médio, ou >mesmo em livros intermediarios, nunca vi menção sobre o >assunto....aproveito pra mandar o problema abaixo ,onde tenho dúvidas >sobre o que usar. >Uma sorveteria tem sorvetes de 10 sabores diferentes. De quantos modos >uma pessoa pode escolher seis bolas de sorvete, não necessáriamente de >sabores diferentes?? > Agradeço qualquer ajuda!! > Korshinói > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================