Quantos inteiros entre 1 e 100 000, inclusive, têm a propriedade: “cada dígito é menor ou igual ao seu sucessor”?
Passo 1
O enunciado pede para contar quantos inteiros em
têm dígitos não decrescentes (cada dígito é menor ou igual ao sucessor). O conteúdo necessário é contagem de sequências não decrescentes de dígitos, que se resolve via o princípio de combinação com repetição.
Passo 2
Observamos que todo número de
até
pode ser visto como uma sequência de 5 dígitos com zeros à esquerda. Por exemplo, o número
corresponde à sequência de dígitos
. A condição “dígitos não decrescentes” equivale a exigir
onde cada
está em
.
Passo 3
O número de sequências de comprimento
de um alfabeto de
símbolos (dígitos
a
) que são não decrescentes é dado por combinação com repetição:
Passo 4
Essa contagem inclui a sequência
, que corresponde ao inteiro
, mas queremos só de
a
. Então subtraímos 1:
Passo 5
Finalmente, o único inteiro de seis dígitos no intervalo é
, cuja sequência de dígitos é
, não não decrescente (pois
). Logo não o incluímos.