Combinatória

Sejam Im = {1, 2, . . . , m} e In = {1, 2, . . . , n} com m e n números
inteiros positivos tais que m ≤ n. Quantas são as funções f : Im → In que são
crescentes?

Vou admitir que crescente é o seguinte:
Se x < y então f(x) < f(y)



Escolha um subconjunto A de I_n com m elementos. Digamos que  A = {a₁, a₂, a₃, ..., a_m}, com a₁ < a₂ < ... < a_m. A partir desse conjunto podemos criar uma função f: I_m → I_n crescente fazendo
f(1) = a₁
f(2) = a₂
...
f(m) = a_m

Da mesma forma, dada uma função crescente podemos recriar o subconjunto A como sendo a imagem de f. Ou seja, para cada conjunto dessa forma temos uma função f. O número de tais conjuntos é justamente uma combinação de n elementos tomados m a m. Ou seja, o número de funções é \( \dfrac{n!}{m!(n-m)!}\).