числа с неубывающими цифрами и пути

[2old]

Сколько есть четырехзначных чисел, цифры которых возрастают? А неубывают?

Первый вопрос вроде совсем просто: $0$ нигде появиться не может, цифры совпадать не могут. Порядок задается требованием возрастания. Поэтому $9 \choose 4$.

Глядя на первый, на второй вопрос хочется ответить сочетаниями с повторениями. Но тут я как-то запутываюсь. Кодировать следующую цифру можно так: $0$ если повторяю, $k$ единиц, на которые увеличиваю. Вроде бы увеличить больше чем на $8$ единиц не получится. Тогда $x_1+x_2+x_3+x_4\leq 8$. Число решений неравенства совпадает с числом решений $x_1+x_2+x_3+x_4+x_5=8$. Получается $8+5-1\choose 5-1$.

Так? Исходя из неравенства и способа кодировки, кажется что тут еще можно думать об этом, как о неунывающих путях не выше чего-то, но я не могу разобраться.

[Brukvalub]

Может, проще вычесть из общего числа 4-хзначных чисел число чисел , для которых нет неубывания цифр?

[2old]

Brukvalub
А это все неправильно?

Всего чисел четырехзначных $9\cdot 10^3$. А нет неубывания как найти? Как найти убывание понятно, это $9 \choose 4$, но там же еще часть где совсем как угодно

[grizzly]

2old в сообщении #1030458 писал(а):

А неубывают?

А тупо посчитать какими-то включениями-исключениями здесь не проще? (Сам думать не пробовал, но издали кажется, что там несложно подправленные аналоги двузначных и трёхзначных вариантов первого вопроса.)

А ответ на первый вопрос сомнений не вызывает.

[2old]

grizzly
Наверное да, но мне не нравится формула включений-исключений тут потому что если спросят про $5,6...m$ значное число будет грустно. А тут если решение верное, ответ всегда готов: $8+m \choose m$

Сейчас тогда попробую с вкл-выкл и сверю результаты

[Shadow]

Ваша формула верная. Нули выбрать не можем. Можем выбрать $x_1$ единиц, $x_2$ двоек ...$x_9$ девяток и упорядочить их единствееным образом. Для $m$ значного числа должно выполнятся

$x_1+x_2+\cdots+x_9=m$, что и есть число композиций числа $m$ длиной 9, естественно, с нулями. Или $C_{m+8}^8$