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

Passo 1

O enunciado pede o número de funções
f\colon I_{m} \to I_{n}
estritamente crescentes, onde I_{m}=\{1,2,\dots,m\}, I_{n}=\{1,2,\dots,n\} e m\le n. O conteúdo aqui é combinatória: uma função estritamente crescente satisfaz
f(1)<f(2)<\cdots<f(m),
logo a teoria necessária é a contagem de subconjuntos de tamanho m em um conjunto de n elementos.

Passo 2

Note que atribuir valores a f de modo que f(1)<f(2)<\cdots<f(m) equivale a escolher um subconjunto de m elementos em I_{n} e ordená-los de forma crescente. De fato, uma vez escolhido um conjunto \{a_{1},a_{2},\dots,a_{m}\}\subseteq I_{n} com a_{1}<a_{2}<\cdots<a_{m}, existe exatamente uma função estritamente crescente que manda i\mapsto a_{i}.

Passo 3

O número de subconjuntos de tamanho m em um conjunto de n elementos é dado pelo coeficiente binomial
\binom{n}{m}.

Resposta

\displaystyle \binom{n}{m}

Exercícios relacionados