Re: [obm-l] Combinatória

[Faelccmm@xxxxxxx]

Ok !

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, nicolau@mat.puc-rio.br 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.