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.