e
. Quantas são as funções
nāo decrescentes?
Passo 1
O enunciado define os conjuntos \r
e
\r
e pede o número de funções não decrescentes. Isso equivale a contar sequências \r
com \r
. Vamos usar o método de estrelas e barras para resolver.
e pede o número de funções
Passo 2
Cada função não decrescente corresponde exatamente a uma sequência \r
satisfazendo \r
Para contar essas sequências, basta agrupar quantas vezes cada valor de
a
aparece.
Passo 3
Defina
como o número de índices
tais que
. Então cada
é inteiro não negativo e vale \r
Contar as sequências é o mesmo que contar as soluções não negativas dessa equação.
Passo 4
Pelo teorema de estrelas e barras, o número de soluções inteiras não negativas de \r
é dado por \r