[obm-l] Combinatória: número de soluções de uma equação

["Pedro Cardoso" <pedrolazera@xxxxxxxxxxx>]

Cláudio,

me desculpe, mas eu não entendi muita coisa. Por que o macete do coeficiente 
de t^n de um polinômio me ajuda a resolver a questão? Pelo que entendi - e 
por isso acho que não entendi direito -, você fez no braço, listando as 
possibilidades, que no caso seriam (6,6,6,3),(6,6,5,4),(6,5,5,5) e suas 
permutações.

Se o problema fosse x1 + x2 + x3 + x4 + x5 + x6 = 105, x_i <= 35 (número 
"grandes"), como ficaria a solução?

E sobre o comentário do Jaare Oregim,

"por que não o no. de soluções inteiras não-negativas menos o no. de 
soluções com x_i > 6, para todo i?já que limitar por baixo é simples...."

É que não é a mesma coisa. Veja:

x1+x2+x3+x4 = 15, x<=5

No. de soluções em que qualquer x > 5 = 0. Entendeu?
Faltou descontar os casos em que somente uma, ou somente duas, ou somente 3 
das incóginas são maiores que 5. Aí eu acho que também acabaria caindo em um 
monte de casos.
-------------------------------------------------------------------------------------------------------------------------------------

Mensagem antiga:
(...)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?
.......................................................................................................

Resposta do Cláudio Bufara:

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.

_________________________________________________________________
Mande torpedos SMS do seu messenger para o celular dos seus amigos 
http://mobile.msn.com/

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