Quantas são as funções f : Im -->Im ?

Im = {1,2,3,...,m} e In = {1,2,3,...,n}. Quantas são as funções f : Im -->Im não decrescentes?

Resposta:

Se na pergunta não houvesse a restrição "não decrescentes", eu obteria a resposta sem problemas. Esse é um problema de combinação completa ( aquele das bolinhas e dos bastões). Na maneira como eu interpretei, cada elemento de In é uma casa, enquanto os de Im representam as bolinhas. Desse modo, numa função constante teríamos todas as bolinhas em uma única casa, por exemplo. O problema é que, ao meu ver, a combinação cujo valor é a resposta representaria todas as funções possíveis, mesmo as constantes e decrescentes. Não entendo por que esse valor é, na verdade, a contagem das funções não decrescentes.

Acabei desenrolando aqui. O lance é que, se a questão pede as funções não decrescentes, obtemos as constantes ou crescentes. Para isso, o mais fácil é pensar que precisamos criar um conjunto imagem a partir do contradomínio In = {1,2,3...,n}. Esse conjunto precisa ter, obviamente, o mesmo número de elementos do domínio, Im = {1,2,3...,m}, para que possamos fazer a associação entre cada um dos elementos deste aos daquele. Desse modo, pensando nos elementos de Im como bolinhas e nos de In como casas, temos que o número de conjuntos imagem que podemos formar vale C[(m+n-1),(n-1)] (Lê-se : Combinação de m+n-1 escolhe n-1). Montado um conjunto imagem qualquer, só existe uma única possibilidade de "ligar as setas", ou de associar os elementos do domínio aos da imagem, de modo que seja formada uma função não decrescente.

Edit: m = bolinhas
        n-1 = bastões que separam as casas
        m+n-1 = número de entradas para esses elementos.
        Talvez usar permutação nesse caso seja mais natural para alguns em termos de raciocínio .