Re: [obm-l] Análise Combinatória

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

Para facilitar a vida de quem não tiver nenhum destes livros:
o número de soluções inteiras *positivas* de
y_1 + .. + y_k = n é binomial(n-1,k-1).
Para ver isso, imagine n asteriscos enfileirados assim (n = 12):
* * * * * * * * * * * *
Para descrever uma solução, introduzimos linhas divisórias nos espaços.
Assim, a solução y_1 = 5, y_2 = 3, y_3 = 4 (k = 4) fica assim:
* * * * *|* * *|* * * *
(y_1 *s até o primeiro |, mais y_2 até o segundo, ...).
Ora, temos n-1 espaços e devemos selecionar k-1 deles para serem
preenchidos e isto pode ser feito de binomial(n-1,k-1) formas
(esta é a descrição mais básica de números binomiais).

Para contar as soluções *não negativas* de
x_1 + x_2 + ... + x_k = n
faça y_i = x_i + 1 donde
y_1 + y_2 + ... + y_k = n-k.
Ou seja, o número de soluções é binomial(n-k-1,k-1).

N.


On 10/21/07, Antonio Neto <osneto@xxxxxxxxxxx> wrote:
>
>
> Bem, como ninguém respondeu, aí vai: o que você quer é saber o número de
> soluções da equação x_1 + x_2 + x_3 + x_4 = 12, onde cada x_i é um inteiro
> não negativo. A resposta é Bin(15, 3) = 455, se não errei nada. A sugestão
> clássica é consultar o livro do Morgado, editado pelo IMPA. Para os mais
> velhinhos, como eu e alguns outros (não vou citar para não melindrá-los), o
> Prelúdio à Análise Combinatória, do Arago, Poppe e Raimundo. Abraços, olavo.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================