Sejam
e
, com
. Quantas são as funções
estritamente crescentes?
Passo 1
O enunciado pede o número de funções
estritamente crescentes, onde
,
e
. O conteúdo aqui é combinatória: uma função estritamente crescente satisfaz
logo a teoria necessária é a contagem de subconjuntos de tamanho
em um conjunto de
elementos.
Passo 2
Note que atribuir valores a
de modo que
equivale a escolher um subconjunto de
elementos em
e ordená-los de forma crescente. De fato, uma vez escolhido um conjunto
com
, existe exatamente uma função estritamente crescente que manda
.
Passo 3
O número de subconjuntos de tamanho
em um conjunto de
elementos é dado pelo coeficiente binomial