---------- 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
=========================================================================
__________________________________________________
Fale com seus amigos de graça com o novo Yahoo! Messenger
http://br.messenger.yahoo.com/