Falando novamente sobre o assunto, vejam as equa��es:
(I): x1 + x2 + x3 + x4 = 27 (o maior valor para inc�gnitas � 9 e todos os valores s�o naturais)
(II): x1 + x2 + x3 + x4 = 18 (o maior valor para inc�gnitas � 9 e todos os valores s�o naturais)
H� como provar que a equa��o (II) possui mais solu��es que (I) sem resolv�-las pelo m�todo exposto por voc� ?
Da para generalizar este problema, ou seja, comparar 2 equa��es destes tipos (com cotas superior) e dizer qual a que possui mais solu��es ?
Em uma mensagem de 29/9/2004 14:44:33 Hora padr�o leste da Am. Sul, [EMAIL PROTECTED] escreveu:
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.
