Re:[obm-l] Contagem

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

---------- Cabeçalho original -----------

De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia: 
Data: Thu, 5 Apr 2007 20:09:10 -0300 (ART)
Assunto: [obm-l] Contagem

> Galera da lista, tenho mais uma questao de contagem. Espero que possam me ajudar....
>    
>   1) Seja Im = {1,2,...,m} e In = {1,2,...,n}. Quantas sao as funçoes f: Im -->In nao decrescentes?
>    
>   Espero que possam me ajudar nessa questao a na que enviei dias anteriores a voces... Muito obrigado por enquanto galera...
>   []s e até....
> 

Cada uma dessas funcoes eh uma m-upla ordenada (a_1,a_2,...,a_m) de elementos de In tal que:
1 <= k <= m-1 ==> 1 <= a_k <= a_(k+1) <= n
(ou seja, os elementos da m-upla estao em ordem nao-decrescente)
Suponhamos que uma dada m-upla tenha x_j elementos iguais a j (1 <= j <= n).
Entao, o numero de tais m-uplas eh igual ao numero de solucoes inteiras e nao-negativas de:
x_1+x_2+...+x_n = m, ou seja, Binom(m+n-1,n-1) = Binom(m+n-1,m) = numero de funcoes nao-decrescentes de Im em In.

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