[obm-l] Re: [obm-l] Combinações com repetições.

["Eduardo Casagrande Stabel" <dudasta@xxxxxxxxxxxx>]

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: Korshinoi@aol.com
>
>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 é <nicolau@mat.puc-rio.br>
=========================================================================