Re: [obm-l] analise combinatoria

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] analise combinatoria

on 28.10.03 16:35, guilherme S. at guilherme_s_ctba@yahoo.com.br wrote:

> pessoal preciso de ajuda pra estas duas questoes:
>
> Oi, Guilherme:
>
> Aqui vao minhas tentativas:
>
>
> QUANTAS SAO as solucoes inteiras nao negativas da eq: x+y+z+w=20 , tal que x>y
>
> O numero de solucoes sem restricao eh Binom(23,3) = 1771.
>
> Agora dividimos em casos: x > y, x < y e x = y, observando que o numero de solucoes com x > y eh igual ao no. de solucoes com x < y. 
> Chamemos esse numero de N. 
>
> O caso x = y equivale ao no. de solucoes nao-negativas de 2x + z + w = 20. 
> Isso eh igual ao coeficiente de x^20 no polinomio:
> (1+x+x^2+x^3+...+x^20)^2*(1+x^2+x^4+x^6+...+x^20),
> o qual, segundo o PARI-GP, eh igual a 121.
> (tambem dava pra calcular no braco sem muita dificuldade, fazendo x variar de 0 a 10, caso em que obteriamos: 21+19+17+...+3+1 = soma dos impares de 1 a 2*11-1 = 11^2 = 121).
>
> Logo, 2N + 121 = 1771 ==> N = 825.
>
> *****
>
> quantas sao as funcoes nao decrescentes f:A->B , tal que A={1,2,3..m} e B={1,2,...n}
>
> Considere as quantidades:
> x1 = f(1),  x2 = f(2) - f(1),  x3 = f(3) - f(2),  ...,  xm = f(m) - f(m-1).
> Cada uma delas deve ser nao negativa e a soma de todas (igual a f(m) - f(1)) deve ser um inteiro entre 0 e n-1 (inclusive).
> Assim, a cada funcao podemos fazer corresponder uma solucao inteira nao-negativa da desigualdade: 
> 0 <= x1 + x2 + ... + xm <= n-1.
>
> Por outro lado, a cada solucao inteira e nao negativa (x1,x2,...,xm) dessa desigualdade podemos associar uma funcao f tal que:
> f(1) = x1, f(2) = x1+x2, f(3) = x1+x2+x3, ..., f(m) = x1+...+xm.
>
> Logo, o numero de funcoes eh igual ao numero de solucoes da desigualdade.
>
> Esse numero eh igual a:
> Binom(m-1,m-1) + Binom(m,m-1) + ... + Binom(m+n-2,m-1) = Binom(m+n-1,m)
> (pelo teorema das colunas do triangulo de Pascal).
>
>
> Um abraco,
> Claudio.