Sejam I_{m}=\{1,2, \ldots, m\} e I_{n}=\{1,2, \ldots, n\}, com m \leq n. Quantas sĩo as funçöes f: I_{m} \rightarrow I_{n} estritamente crescentes?

Passo 1

O enunciado define I_{m}=\{1,2,\dots,m\} e I_{n}=\{1,2,\dots,n\} com m\le n e pede a quantidade de funções
f\colon I_{m}\to I_{n}
que sejam estritamente crescentes, ou seja, satisfazem
f(1)<f(2)<\cdots<f(m).
Para resolver, vamos usar raciocínio combinatório de escolha de valores distintos em ordem.

Passo 2

Como f é estritamente crescente, ela é injetora e seus valores f(1),f(2),\dots,f(m) formam uma sequência estritamente crescente de elementos de I_{n}. Logo, cada função corresponde exatamente a escolher m elementos distintos de I_{n} e colocá-los em ordem crescente.

Passo 3

Escolher m elementos distintos de um conjunto de n elementos sem se importar com a ordem (pois a ordem já fica determinada como crescente) é o mesmo que formar um subconjunto de tamanho m. O número de tais subconjuntos é dado pelo coeficiente binomial.

Passo 4

Portanto, o total de funções estritamente crescentes f:I_{m}\to I_{n} é
\binom{n}{m}.

Resposta

\displaystyle \binom{n}{m}

Exercícios relacionados