On Tue, Sep 28, 2004 at 01:54:07PM -0300, Nicolau C. Saldanha wrote: > > 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)
O que eu fiz está incompleto: faltou especificar o valor máximo de i. É bem claro pelo raciocínio que devemos ter k - i*b >= 0. Se definirmos binom(x,y) da forma usual como um polinômio em x de grau y para cada valor fixo de y então a soma completa dá zero, como podemos facilmente provar. Assim, a resposta é Soma_{i >= 0, i <= k/b} (-1)^i binom(n,i) binom(k - i*b + n - 1, n - 1) ou - Soma_{i >= 0, i > k/b} (-1)^i binom(n,i) binom(k - i*b + n - 1, n - 1) Outra maneira de obter a segunda fórmula é observar que o número de solucões para k é igual ao número de solucões para n*(b-1) - k. No problema proposto com n = 4, k = 27, b = 10 a resposta é binom(27+4-1,4-1) - 4*binom(27-10+4-1,4-1) + 6*binom(27-2*10+4-1,4-1) = binom(30,3) - 4*binom(20,3) + 6*binom(10,3) = 4060 - 4*1140 + 6*120 = 220. Observem que a segunda fórmula permite chegar à resposta mais rapidamente: 4*binom(0,3) - binom(-10,3) = 4*0 + 220 = 220. Isto pode ser confirmado procurando o coeficiente de x^27 (ou de x^9) em ((x^10-1)/(x-1))^4 = 36 35 34 33 32 31 30 29 28 x + 4 x + 10 x + 20 x + 35 x + 56 x + 84 x + 120 x + 165 x 27 26 25 24 23 22 21 + 220 x + 282 x + 348 x + 415 x + 480 x + 540 x + 592 x 20 19 18 17 16 15 14 + 633 x + 660 x + 670 x + 660 x + 633 x + 592 x + 540 x 13 12 11 10 9 8 7 + 480 x + 415 x + 348 x + 282 x + 220 x + 165 x + 120 x 6 5 4 3 2 + 84 x + 56 x + 35 x + 20 x + 10 x + 4 x + 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 =========================================================================