Boa tarde.
Devido ao meu conhecimento limitado a respeito do assunto nao consegui
entender porque é importante para a solucao do problema achar o
coeficiente do polinomio apresentado(porque esse polinomio?) e qual
seria o metodo mais rapido para encontrar tal coeficiente sem ter que
desenvolver o polinomio, visto que nao se trata de um simples binomio.
Agradeco antecipadamente.
On 5/18/07, claudio.buffara <[EMAIL PROTECTED]> wrote:
De:[EMAIL PROTECTED]
Para:obm-l@mat.puc-rio.br
Cópia:
Data:Fri, 18 May 2007 00:19:30 -0300
Assunto:[obm-l] [obm-l] Combinatória: número de soluções de uma equação
> Saudações,
>
> amigos da lista. Bem, surgiu aqui uma dúvida quando eu estava estudando
> combinatória. É em relação a uma variação não tão clássica do problema
> clássico do número de soluções inteiras não-negativas de uma equação.
>
> x_1+x_2+x_3...+x_n = k
>
> O número de soluções não-negativas e inteiras, para k também inteiro, é
> (k+n-1)/[k!*(n-1)!]. É fácil visualizar isso utlizando 'bolinhas' e
> 'barrinhas'. Limitar "por baixo" o valor das incógnitas (garantir que
todas
> ou algumas delas não possam ser inferiores a algum valor dado) também é
> simples. O problema é limitar 'por cima'. Exemplo:
>
> x1+x2+x3+x4 = 21
> x_i <= 6, para qualquer i inteiro.
>
> Como eu determino o número de soluções dessa equação?
>
Coeficiente de t^21 na expansão de (1+t+t^2+t^3+t^4+t^5+t^6)^4
Ou seja, 20.
Como você obtem um expoente 21 por meio da soma de 4 expoentes entre 0 e 6
(inclusive)?
6+6+6+3: 4 maneiras;
6+6+5+4: 2*Binom(4,2) = 12 maneiras;
6+5+5+5: 4 maneiras.
Total = 20 maneiras.
O caso 6+6+5+4 é:
Escolha dos 2 polinômios que vão contribuir o expoente 6:
Binom(4,2) = 6 maneiras;
Escolha do polinômio que vai contribuir o expoente 5:
Binom(2,1) = 2 maneiras;
Escolha do polinômio que vai contrinuir o expoente 4:
1 maneira.
***
Use essa idéia (coeficiente de t^n de um produto de polinômios especialmente
escolhidos) pra achar o número de soluções inteiras e não-negativas de:
x + 2y + 3z + 4w = 10.
Resp: 23
[]s,
Claudio.
--
-----------------------------
RAFAEL
=========================================================================
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
=========================================================================
