Re: [obm-l] Re:[obm-l] [obm-l] Combinat �ria: n�mero de solu��es de uma equa��o

[Rafael <rfa1989@xxxxxxxxx>]

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 <claudio.buffara@terra.com.br> wrote:
>
> De:owner-obm-l@mat.puc-rio.br
>
> 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
=========================================================================