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 \{1,2,\dots,100000\} 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 1 até 99999 pode ser visto como uma sequência de 5 dígitos com zeros à esquerda. Por exemplo, o número 335 corresponde à sequência de dígitos 0,0,3,3,5. A condição “dígitos não decrescentes” equivale a exigir
d_1 \le d_2 \le d_3 \le d_4 \le d_5,
onde cada d_i está em \{0,1,\dots,9\}.

Passo 3

O número de sequências de comprimento 5 de um alfabeto de 10 símbolos (dígitos 0 a 9) que são não decrescentes é dado por combinação com repetição:
\binom{10+5-1}{5} \;=\;\binom{14}{5}\;=\;2002.

Passo 4

Essa contagem inclui a sequência 0,0,0,0,0, que corresponde ao inteiro 0, mas queremos só de 1 a 99999. Então subtraímos 1:
2002 - 1 = 2001.

Passo 5

Finalmente, o único inteiro de seis dígitos no intervalo é 100000, cuja sequência de dígitos é 1,0,0,0,0,0, não não decrescente (pois 1>0). Logo não o incluímos.

Resposta

2001

Exercícios relacionados