On Sat, Sep 25, 2004 at 07:28:32PM -0400, [EMAIL PROTECTED] wrote: > Olá pessoal, > > É sabido, por várias formas, como calcular equações do tipo: > x[1] + x[2] + x[3] + ... + x[n] = k, em que > 0 =< x[1] , x[2] , x[3] , ... , x[n] =< k, ou seja, as incógnitas são > naturais. > > Pergunta: > > Vocês conhecem a fórmula para resolver > > x[1] + x[2] + x[3] + ... + x[n] = k, em que > > 0 =< x[1] , x[2] , x[3] , ... , x[n] =< a (a < k) ? > > Um exemplo do caso geral acima : > > Resolva x + y + w + z = 27 sendo que o maior valor que as incógnitas podem > assumir seja 9, ou seja, > 0 =< x, y, w, z =< 9
Eu acho que a pergunta não está muito bem formulada. Eu adivinho que você quer saber *quantas* soluções *inteiras* a equação tem. É isso? Se for, não é difícil. O número de soluções de x1 + x2 + ... + xn = k, xi >= 0 é binom(k+n-1,n-1). Agora é só fazer inclusão e exclusão: o número de soluções de x1 + x2 + ... + xn = k, xi >= 0, x1 >= b é binom(k-b+n-1,n-1): basta fazer y1 = x1 - b e considerar o problema y1 + x2 + ... + xn = k - b. Assim, para calcular o número de soluções com 0 <= xi < b precisamos tirar fora estas soluções, com o cuidado usual do somar de volta o que for excluído duas vezes e assim por diante: binom(k+n-1,n-1) - n*binom(k-b+n-1,n-1) + binom(n,2)*binom(k-2b+n-1,n-1) -... = Soma_{i >= 0} (-1)^i binom(n,i) binom(k - i*b + n - 1, n - 1) []s, N. ========================================================================= 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 =========================================================================