Análise Combinatória - Bolas em caixas

por **angeruzzi** » Dom Mai 16, 2010 01:33

Olá, me ocorreu um problema de análise combinatória que estou confuso ao tentar resolver.

Tenho 20 bolas a serem distribuídas em 5 caixas, podendo no final as caixas ficarem com número de bolas diferentes ou até mesmo vazias. Qual o número de possibilidades de distribuição de bolas nas caixas em 3 situações:

a) Todas as bolas da mesma cor;
b) Todas as bolas de cores distintas;
c) 8 bolas azuis, 7 bolas verdes e 5 bolas vermelhas.

Creio que a resposta da "b" seria: 5^20 = 95.367.431.640.625 , mas não estou seguro disso e não sei como abordar as demais situações.

por **Douglasm** » Dom Mai 16, 2010 10:28

Olá angeruzzi. Faz um tempo que não estudo combinatória, então caso você possua o gabarito da questão seria interessante postá-lo para conferirmos. Comecemos:

a) Aqui, o que nós temos é uma combinação completa (caso não esteja familiarizado com isso, sugiro que procure em um bom livro de combinatória) de 20 elementos que devem ser encaixados em 5 categorias. Deste modo:

$CR_{20}^5 \: = \: C_{20+5-1}^5 \: = \: C_{24}^5 = 42504$

Temos então, 42504 possibilidades de organizar esses elementos.

b) Aqui eu concordo com a resposta $5^{20}$ , pois cada elemento é diferente do outro e pode entrar em qualquer uma das 5 caixas. (5 . 5 . 5 . 5 . 5 . 5 . 5 . {...} . 5 - 20 vezes)

c) Nessa última, creio que devemos fazer, separadamente, a combinação completa de cada tipo de bola e multiplicá-las:

$(CR_8^5) \: . \: (CR_7^5) \: . \: (CR_5^5) \: = \: (C_{12}^5) \: . \: (C_{11}^5) \: . \: (C_9^5) = 792 \: . \: 462 \: . \: 126 \: = \: 46103904$

Como disse, seria interessante ter um gabarito. De qualquer modo espero ter ajudado.

Até a próxima.

por **angeruzzi** » Ter Jun 08, 2010 02:15

Olá Douglas, muito obrigado pela resposta.

Realmente não conhecia a Combinação Completa, segui o seu conselho e comprei um livro de análise combinatória que julguei ser bom (http://www.siciliano.com.br/produto/264 ... babilidade) e me deparei com exercícios interessantes, onde percebi por exemplo que o problema que citei no ítem "A" poderia ser descrito como a+b+c+d+e = 20 , sendo resolvido realmente utilizando a Combinação Completa.

Porém tive problemas com outros exercícios, vou citá-los:

1) Quantas são as soluções inteiras e não negativas da inequação x + y + z <= 5 ?
Para resolvê-lo, separei em 6 equações e apliquei a Combinação Completa em cada uma:
a) x + y + z = 5
$CR_{5}^{3} = C_{7}^{3} = 35$

b) x + y + z = 4
$CR_{4}^{3} = C_{6}^{3} = 20$

c) x + y + z = 3
$CR_{3}^{3} = C_{5}^{3} = 10$

d) x + y + z = 2
$CR_{2}^{3} = C_{4}^{3} = 4$

e) x + y + z = 1
$CR_{1}^{3} = C_{3}^{3} = 1$

f) x + y + z = 0
Que não dá pra ser aplicado a CR, mas intuitivamente é 1

Sendo assim: 35 + 20 + 10 + 4 + 1 + 1 = 71; Porém o gabarito é 56.
Fiz todas as permutações a mão (acredite) e realmente é 56, e todas as parciais são diferentes das anteriores com exceção da c:
a) 21, b) 15, c) 10, d) 6, e) 3, f)1 -> 56

Tive o mesmo problema em outro exercício:

2) Quantas são as soluções inteiras da equação x + y + z = 20, nas quais nenhuma é menor que 2? Sugestão: chame x = a + 2, y = b + 2 e z = c + 2 e resolva a equação a + b + c = 14.
Solução: $CR_{14}^{3} = C_{16}^{3} = 560$
Porém o gabarito é 120.

Onde eu errei na solução destes problemas ?

por **MarceloFantini** » Ter Jun 08, 2010 04:41

Angeruzzi, por favor crie um novo tópico para a sua dúvida para facilitar a localização e evitar amontoados em um mesmo tópico.

por **Douglasm** » Ter Jun 08, 2010 09:24

Olá angeruzzi. Como Fantini disse, para novas perguntas crie um novo tópico. Mas sobre sua dúvida, seu único erro foi fazer "ao contrário" (erro esse que eu também cometi ao resolver sua primeira questão, que será corrigido no próximo post). O certo seria fazer as combinações como:

$CR_3^5 \; ; \; CR_3^4 \; ; \; CR_3^3 \; ...$

Corrigindo isso, encontrará as respostas do gabarito. Na verdade, o que devemos fazer aqui, é combinar 3 incógnitas, 5 a 5, 4 a 4, etc. Assim teríamos como solução, por exemplo:

x_1 ; x_1 ; x_1 ; x_3 ; x_3

O que representaria:

$x_1 = 3 \; ; \; x_2 = 0 \; ; \; x_3 = 2$

De modo geral é isso, mas gostaria de chamar a atenção para um outro jeito de se resolver a primeira questão:

Podemos expressar esse problema do seguinte modo:

$x + y + z \leq 5 \; \therefore \; x + y + z + f = 5$

Tal que "f" seria a "folga" das soluções. f = 5 - (x+y+z). Podemos então prosseguir descobrindo o número de soluções de x + y + z + f = 5, que é dado por:

CR_4^5 = C_8^5 = 56

OBS: Cuidado com algo que pode confundir muito: certos livros (como o que eu usei), usam uma notação "inversa" (em relação a notação mais usual para combinação). Ao invés de C_p^n

, preferem fazer C_n^p

. É interessante tomar muito cuidado com isso, e observar bem que combinação está fazendo.

por **Douglasm** » Ter Jun 08, 2010 09:33

Errata:

Sobre a questão das bolas na caixa:

a) A combinação certa aqui é:

$CR_5^{20} = C_{24}^{20} = 10626$

Esta questão pode ser interpretada também como o número de soluções da equação:

x_1 + x_2 + x_3 + x_4 + x_5 = 20

c) A correção aqui é semelhante a anterior:

$(CR_5^8)(CR_5^7)(CR_5^5) = (C_{12}^8)(C_{11}^7)(C_9^5) = (495)(330)(126) = 20582100$

Desculpe a desatenção e até a próxima.