Sejam
e
, com
. Quantas são as funções
estritamente crescentes?
Passo 1
O enunciado nos dá os conjuntos
com
, e pede o número de funções
que sejam estritamente crescentes. O conteúdo aplicado é combinatória de funções monotônicas, e vamos usar a ideia de escolher subconjuntos de tamanho
.
Passo 2
Uma função
é estritamente crescente se, para todo
em
, tem-se
. Logo os valores
são
elementos distintos de
, tomados em ordem crescente.
Passo 3
Assim, dar uma função estritamente crescente é o mesmo que escolher um subconjunto
com
e, em seguida, atribuir a
os elementos de
na sua ordem natural. Cada subconjunto de tamanho
gera exatamente uma função crescente.
Passo 4
O número de formas de escolher um subconjunto de tamanho
de um conjunto de
elementos é o coeficiente binomial