Combinações Completas

Frequentemente encontro problemas envolvendo combinações completas na seção de Análise Combinatória e não entendem a minha resolução por não saberem como são utilizadas ou a origem das combinações completas. As explicações aqui dadas são baseadas no livro do célebre Augusto César Morgado.

Motivação: de quantos modos podemos comprar 4 sorvetes em uma loja que oferece 7 sabores?

Se os 4 sabores fossem necessariamente diferentes, a resposta seria C(7,4), que é a combinação simples já bastante conhecida, ou seja, seria a resposta da pergunta "de quantos modos podemos selecionar 4 elementos em um conjunto com 7 elementos?". Ora, neste caso, não seriam aceitas repetições. A resposta correta é CR(7,4), onde CR representa combinações com repetição (combinações completas).

Todavia, as combinações completas aceitam repetições. Não há obstáculo para que os 4 sorvetes escolhidos sejam iguais (algo que não seria admitido pela combinação simples). Para resolver este problema, chamemos a respectiva quantidade comprada de cada um dos 7 sabores possíveis de [latex]x_1, x_2, x_3, ..., x_7[/latex]. Assim, [latex]x_1=3, x_2=1[/latex] significa que foram comprados 3 sorvetes do sabor 1 e 1 sorvete do sabor 2, totalizando 4 sorvetes comprados. Naturalmente, o problema inicial exige que o total de sorvetes comprados, considerando todos os 7 sabores, seja 4:

[latex]x_1 + x_2 + x_3 + ... + x_7 = 4[/latex]

Para resolver o problema, a pergunta passa a ser: quantas soluções inteiras não-negativas existem para essa equação? Pois, cada solução, representa um conjunto possível de sorvetes, conforme exemplificado anteriormente com [latex]x_1=3, x_2=1[/latex].

Com base na equação, imagine que temos 4 bolas e 6 traços. Essas 4 bolas representam os 4 sorvetes que serão comprados e, os traços, os sinais de +. 
[latex]x_1 + x_2 + x_3 + ... + x_7 = 4[/latex]
[latex]ooo | o | x_3 |x_4|x_5|x_6|x_7 [/latex]
mostra uma possível solução com [latex]x_1=3, x_2=1[/latex] (e nenhum sorvete dos sabores 3, 4, 5, 6, 7).

[latex]x_1 + x_2 + x_3 + ... + x_7 = 4[/latex]
[latex]oo | o | o |x_4|x_5|x_6|x_7 [/latex]
mostra uma possível solução com [latex]x_1=2, x_2=1, x_3=1[/latex] (e nenhum sorvete dos sabores 4, 5, 6, 7).

Logo, para cada organização diferente do conjunto bolas-traços, obtemos uma solução diferente. Para saber quantas soluções da equação há no total, basta contar de quantas maneiras podemos organizar essas bolas-traços.

Ora, há um total de 4 bolas + 6 traços = 10 objetos, que podem ser enfileirados de 10! modos. Todavia, como as bolas são iguais entre si, pois representam apenas uma unidade. O que determina o sabor é a posição da bola em relação aos traços, não a própria bola. Portanto, devemos dividir 10! por 4! para descontar as repetições das bolas. Analogamente, divide-se por 6! para tirar da contagem as permutações de traços.

Logo, a resposta é CR(7,4) = 10!/(4!6!).

Por fim, pode-se interpretar CR(p,n) de dois modos:
a) CR(p,n) é o número de modos de selecionar p objetos, distintos ou não, entre n objetos distintos dados.
b) CR(p,n) é o número de soluções da equação [latex]x_1 + x_2 + x_3 + ... + x_n = p[/latex]

Note que CR(7,4) = C(10,4) = C(10,6).
De maneira geral, CR(n,p) = C(n+p-1,p). Esta equação pode ser decorada. Particularmente, nunca decorei, sempre escrevo as equações e efetuo a permutação com repetição, por achar mais simples.

Regra prática: escreva a equação e some o resultado da equação com a quantidade de sinais de "+" e divida pelo produtos dos dois, lembrando de colocar fatorial nos termos: (4+6)!/(4!6!) = 10!/(4!6!).


OBS: a opção de saber demonstrar isso e sempre escrever a equação, além de mais fácil, na minha opinião, também é útil para resolver variações desse problema.

Excelente!

O Morgado foi meu professor de Geometria Analítica 3D no 2º ano da faculdade.

Elcioschin escreveu:Excelente!

O Morgado foi meu professor de Geometria Analítica 3D no 2º ano da faculdade.

Que privilégio! Sempre desejei ter tido aulas com ele e com o Possani. Às vezes, abria as aulas do Morgado no youtube, mesmo já sabendo a matéria, só por gosto pela maneira como ensinava combinatória.

O Morgado era/é fera em matemática.

Quando estava tendo aulas com ele, em 1966, no 2º ano, ele era bem jovem, com vinte e poucos anos.
Em conversa de corredor na escola com outros colegas eu pedi a ele dicas de como resolver uma questão de geometria plana do vestibular que eu e meus colegas tínhamos prestado:

Num heptágono regular ABCDEFGA prove que 1/AB = 1/AC + 1/AD

Ninguém acertou esta questão no vestibular e estávamos curiosos a respeito.

Ele caiu na gargalhada e nós não entendíamos porque. Ai ele explicou que tinha sido ele quem preparou a prova e postou esta questão como um desafio para testar a criatividade dos vestibulandos.

E meu duas dicas: ou resolvia por trigonometria ou por geometria plana, usando teorema de Hiparco.

Após pesquisar o teorema, em livros do Ensino Fundamental 2, consegui resolver usando Hiparco.
Mas nunca consegui resolver por trigonometria, já que os ângulos são completamente "esquisitos": ângulo central = (360/7)º

Postei esta questão no fórum ha anos atrás. Pesquisem.

Hahahaha, que história! Um professor e amigo meu teve aulas com o Guidorizzi e também com o Paulo Boulos. Se eu estivesse no lugar de vocês e soubesse que esse professores seriam famosos, teria pedido um autógrafo na época, hahahaha, mas mesmo dentro do anonimato, seria válido de recordação! Outra figura que me despertar curiosidade é o Iezzi, mas muito pouco parece ser conhecido sobre ele.

Fiquei instigado a tentar resolver esse problema por trigonometria. Quando tiver um tempo, vou tentar e, se conseguir, posto a resolução.

Uma curiosidade: o Morgado te deu aulas onde? Sempre achei que ele fosse do RJ e, até onde sei, o senhor é de Santos. E o vestibular era de qual universidade?

Sim, à época ele morava no Rio de Janeiro, assim como vários professores meus.

Eu estudei e me formei e Engenharia Elétrica, na Universidade Federal de Juiz de Fora - UFJF, por sinal excelente universidade. 
Eu sou mineiro e morava lá, na época do vestibular. Sai de lá muito bem preparado para enfrentar minha vida profissional.

Estes professores davam aula no Rio e semanalmente iam a Juiz de Fora dar aulas na UFJF. Professores de alto nível, a exemplo do Morgado.

Após formado fiz mais um ano de pós-graduação em Engenharia de Equipamentos de Petróleo, na Petrobras. Depois em 1970 vim para Santos.

Tive um professor que teve aulas com o Morgado também, mas infelizmente ele faleceu em 2015 vítima de Parkinson.