Sejam
e
, com
. Quantas sĩo as funçöes
estritamente crescentes?
Passo 1
O enunciado define
e
com
e pede a quantidade de funções
que sejam estritamente crescentes, ou seja, satisfazem
Para resolver, vamos usar raciocínio combinatório de escolha de valores distintos em ordem.
Passo 2
Como
é estritamente crescente, ela é injetora e seus valores
formam uma sequência estritamente crescente de elementos de
. Logo, cada função corresponde exatamente a escolher
elementos distintos de
e colocá-los em ordem crescente.
Passo 3
Escolher
elementos distintos de um conjunto de
elementos sem se importar com a ordem (pois a ordem já fica determinada como crescente) é o mesmo que formar um subconjunto de tamanho
. O número de tais subconjuntos é dado pelo coeficiente binomial.
Passo 4
Portanto, o total de funções estritamente crescentes
é