Re: [obm-l] Combinat�ria

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sat, Sep 25, 2004 at 07:28:32PM -0400, Faelccmm@aol.com 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
=========================================================================