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

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

 

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.