Re: [obm-l] Análise Combinatória

["Fetofs Ashu" <fetofs@xxxxxxxxx>]

On 10/21/07, Gustavo Souza <gustavoandre2006site@xxxxxxxxxxxx > wrote:

Puts não entendi nada, hauHUahu...

 

Tambem não entendi isso:

" Assim, a solução y_1 = 5, y_2 = 3, y_3 = 4 (k = 4) fica assim:
* * * * *|* * *|* * * * "

 

Por que você dividiu os asteriscos dessa maneira, e de onde partiu o raciocinio para encontrar isso>  y_1 = 5, y_2 = 3, y_3 = 4 (k = 4)

 

A resposta encontrada esta certa sim Antonio.

 

Se alguem puder me explicar por favor...

 

Obrigado

 

Vamos por partes gustavo.

 

"Se você diz que a resposta é binomial(n-1,k-1) porque no n-1 você não coloca o 11?"

 

O número de soluções inteiras *positivas* de y_1 + ... + y_k = n é binomial(n-1,k-1).

 

Ele colocou o asterisco no *positivas* por uma razão, já que nesse caso os valores de y_x têm de ser maiores do que 0, o que não acontece no nosso problema (é permitido que os valores sejam iguais a 0).

 

"Tambem não entendi isso:

" Assim, a solução y_1 = 5, y_2 = 3, y_3 = 4 (k = 4) fica assim:
* * * * *|* * *|* * * * "

 

Por que você dividiu os asteriscos dessa maneira, e de onde partiu o raciocinio para encontrar isso>  y_1 = 5, y_2 = 3, y_3 = 4 (k = 4)"

 

Essa foi uma divisão arbitrária, apenas uma das combinações possíveis, para te mostrar qual a relação entre a equação e a fileira de asteriscos (e como qualquer solução inteira da equação tem um correspondente direto no problema de divisão da fileira)

 

"Não entendi da onde surgiu o 15 nem o 4..."

 

Releia a explicação do Nicolau sobre como chegar em binomial(n-1, k-1) para as soluções positivas. Agora crie

 variáveis x_1, x_2..., x_k iguais a y_1+ 1, y_2 + 1,... y_k + 1. É fácil notar que as variáveis y são todas positivas, já que o valor mínimo de qualquer y é 0, e 0 + 1 = 1.

Logo o problema original pode ser reduzido ao problema já conhecido.

Se y_1 + ... + y_k = n

     x_1 + ... + x_k = y_1 + 1 + y_2 + 1 + ... + y_k + 1 = n+k (note que aqui é n+k, e não n-k como dito anteriormente)

Combinações finais: Bin(n+k-1, k-1)

Agora sim vamos entender de onde vieram o 15 e o 3. O seu problema é:

y_1 + y_2 + y_3 + y_4 = 12

n = valor total = 12
k = número de marcas = 4
combinações = Bin(n+k-1, k-1) = Bin(15, 3) = 455

Aluno dando uma de professor é duro, mas felizmente você deve ter entendido alguma coisa. Qualquer coisa pergunte que talvez alguém responda, mas entender essa solução não é nada que uma quebrada de cabeça não resolva :)

Fernando Oliveira