Hmmm... infelizmente, uma função "não-decrescente" não é o mesmo que "uma
função que não é decrescente" -- é, eu concordo que é uma péssima péssima
péssima denominação, mas foi assim que os matemáticos convencionaram...
Uma função decrescente é uma que satisfaz f(x)>f(y) sempre que x<y.
Uma função não-decrescente é uma que satisfaz f(x)<=f(y) sempre que x<y.
Por exemplo, se f(1)=3, f(2)=1 e f(3)=2 então a função não é decrescente
(pois cresce de f(2) para f(3)) nem "não-decrescente" (pois decresce de
f(1)=3 para f(2)=1). Denominação horrível, né?
Solução de (b): imagine bolinhas numeradas de 1 a m. Vamos colocar, entre as
bolinhas, barras indicando onde está cada um dos valores f(1), f(2), ...,
f(n). Por exemplo, se for n=3 e m=9 e escolhermos a função f(1)=2, f(2)=5 e
f(3)=5, temos o seguinte diagrama:
oo|ooo||oooo
A primeira barra diz que f(1)=2 (bolinhas à esquerda dela); a segunda indica
f(2)=5; a terceira indica f(3)=5 também.
Afirmamos que definir uma função não-decrescente é equivalente a escrever
uma sucessão de bolinhas e barras como acima -- dada uma função existe uma
única maneira de escrevê-la com bolas e barras, e dada uma seqüência de n+m
bolas e barras com m bolas e n barras existe uma única função. Bom, para ser
exato não vale começar com uma barra (pois não vale f(1)=0), mas fora isso
vale tudo. Vale até terminar com uma barra (seria f(n)=m) ou várias
(f(n)=f(n-1)=...=m). Uma função constante, por exemplo, teria todas as
barras juntas entre duas bolinhas.
Então a pergunta é: quantas seqüências de (m-1) bolas e n barras existem
(descartei a primeira bola que não pode ser mexida)? Ora, são m+n-1
posições, das quais tenho de escolher n posições para colocar n barras (os
outros lugares terão de conter as bolas), então a resposta é C(m+n-1,n).
Abraço,
Ralph
P.S.: não é coinciência que este raciocínio se parece com a contagem do
número de soluções inteiras não-negativas de x1+x2+...+xn+x(n+1)=m -- basta
identificar x1=f(1), x(i)=f(i)-f(i-1) para i=2,3,...,n e finalmente
x(n+1)=m-f(n). Cada solução (x1,x2,...,x(n+1)) corresponde a uma única f, e
vice-versa.
On Dec 7, 2007 9:53 AM, Eduardo Estrada <[EMAIL PROTECTED]> wrote:
> Olá, Vitório,
>
> Me parece que a resolução é a seguinte:
>
> a) Funções crescentes;
>
> Basta que, do contradomínio com m elementos, selecionem-se n. A cada
> seleção, associa-se uma única função crescente, e vice-versa. Asim, a
> resposta é Cm,n. Observe que, quando m<n, o valor obtido é zero, o que é
> perfeitamente coerente.
>
> b) Funções não decrescentes;
>
> Analogamente, o total de funções decrescentes é Cm,n (de fato, observe
> que, a cada função crescente, associa-se uma única função decrescente, e
> vice-versa). Como o total de funções (de qualquer tipo) é m^n, temos que o
> valor procurado é m^n - Cm,n.
>
> Espero ter ajudado, um abraço!
> Eduardo L. Estrada
>
> ----- Mensagem original ----
> De: vitoriogauss <[EMAIL PROTECTED]>
> Para: obm-l <[email protected]>
> Enviadas: Quinta-feira, 6 de Dezembro de 2007 17:01:58
> Assunto: [obm-l] boa de combinatoria
>
> Caros colegas...
>
>
> Seja In = {1,2,...,n}, analogamente Im, determinar o número de funções f:
> In --> Im tais que:
>
>
> a) f seja crescente
>
> b) f seja não-decrescente
>
> desde já grato....
>
>
> ------------------------------
> Abra sua conta no Yahoo!
> Mail<http://br.rd.yahoo.com/mail/taglines/mail/*http://br.mail.yahoo.com/>,
> o único sem limite de espaço para armazenamento!
>
