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
=========================================================================