Re: [obm-l] CR(n,p) = C(n+p-1,p)

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 29.03.04 14:33, David M. Cardoso at david-obm@suati.com.br wrote:

> 
> CR -> Combinação com repetição.
> C  -> Combinação
> 
> Se não me engano, existe uma formula q diz o seguinte:
> CR(n,p) = C(n+p-1,p)
> 
> Eu queria entender a lógica dessa formula,
> que é útil por exemplo pra resolver:
> 
> a + b + c + d = 20
> Quantas soluções tem isso?
> 
> Exemplos de soluções:
> 3 + 4 + 2 + 11 => 111.1111.11.11111111111
> 5 + 0 + 9 + 6  => 11111..111111111.111111
> 
> Para calcular todas as soluções, seria (eu acho) "só"
> contar de quantas formas eu posso posicionar 3 pontinhos
> em 21 posições.
> 
> O meu conceito de Combinação era decorado, até eu ler
> uma mensagem do Nicolau, explicando como se chegava
> na fórmula..
> (http://www.mail-archive.com/obm-l@mat.puc-rio.br/msg18766.html)
> Agora queria entender a CR.
> 
> 
Oi, David:

A sua ideia de colocar separadores (".") entre os 1's eh boa, mas talvez
seja melhor comecar contando o numero de solucoes inteiras e ESTRITAMENTE
POSITIVAS da equacao:
x_1 + x_2 + ... + x_p = n

Voce comeca com n 1's em sequencia e precisa colocar p separadores de modo
que dois separadores quaisquer nao possam ficar adjacentes. Ou seja, dos n-1
espacos existentes entre os 1's voce precisa escolher p-1 espacos, de modo a
ficar com p grupos nao vazios de 1's (o i-esimo grupo contem x_i 1's e deve
ser nao vazio pois x_i deve ser positivo). Logo, o numero de solucoes
inteiras e positivas dessa equacao eh igual ao numero de maneiras de se
escolher p-1 espacos de um universo de n-1 espacos, ou seja, Binom(n-1,p-1).
 
Agora, suponha que voce queira o numero de solucoes inteiras e NAO-NEGATIVAS
de:
x_1 + x_2 + ... + x_p = n  (*)

Nesse caso, alguns dos x_i podem ser iguais a zero. No entanto, voce pode
fazer a mudanca de variaveis y_i = x_i + 1 (1 <= i <= p), de forma que a
cada solucao nao-negativa (x_1,x_2,...,x_p) corresponda exatamente uma
solucao positiva (y_1,y_2,...,y_p). Re-escrevendo a equacoa em funcao dos
y_i, ficamos com: 
(y_1 - 1) + (y_2 - 1) + ... + (y_p - 1) = n
ou:
y_1 + y_2 + ... + y_p = n + p  (**).

Soh que os y_i soh podem ser positivos. Ou seja, o numero de solucoes
inteiras e nao-negativas de (*) eh igual ao numero de solucoes inteiras e
positivas de (**)

Mas isso eh igual a Binom(n+p-1,p-1).

Espero ter sido claro.


[]s,
Claudio.


=========================================================================
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
=========================================================================