[Katrin_noise]

Помогите пожалуйста с задачей по дискретной математике.
`TZ`
Сколько существует натуральных чисел, не превышающих 10^n, у которых цифры расположены в неубывающем порядке?
[[/TZ]]
Если взять простой случай n=2, где число будет = 100
то получаются такие числа:
(1, ... , 9),(11, ... , 19) (22, ... , 29), (33, ..., 39), ...... , (99), т.е их кол-во:
9 + 9 + 8 + 7 ... + 1 = 54. Подскажите, как мне найти общее решение этой задачи?

Так же не получается доказать тождество:

@темы: Дискретная математика

Comments

[Robot]

Katrin_noise
Почему удалена предыдущая запись , в которой была сделана подсказка?
Правила
пункт 8

[Katrin_noise]

Хотела нажать редактировать, т.к ошибку допустила, а не обратив внимания на то, что там предупреждение выскакивало, случайно получилось, что удалила.

[Epygraph]

Пусть `N(m,n)` есть количество описываемых в задаче чисел, младшая цифра которых не меньше `m`. Тогда
`N(9,n)=1`
`N(8,n)=(n+1)=\sum_{k=0}^n N(9,n-k)` (до некоторого места идут восьмерки, а затем девятки)
`N(7,n)=\sum_{k=0}^n N(8, n-k)` (до некоторого места идут семерки, а затем восьмерки и девятки)

В задаче требуется найти `N(0,n)-1`.

[_ТошА_]

По поводу второго. Распишите через факториалы, упростите, свернётся там хорошо

[Katrin_noise]

Если расписать по факториалам, то я вижу, что сокращается только `(k!)/ ((k-1)!)`. А как дальше поступить? `sum_(k=1)^n (k! (n - 1)! (2 n - k - 1)!)/((n - k)! (k - 1)! (2 n - 1)!)=sum_(k=1)^n (k (n - 1)! (2 n - k - 1)!)/((n - k)! (2 n - 1)!)'

[Epygraph]

[Katrin_noise]

Спасибо большое. Попытаюсь разобраться. А можно ли где то подробнее прочитать про данный способ решения?

[Epygraph]

А можно ли где то подробнее прочитать про данный способ решения?

Сходные мотивы встречаются нередко. Например, биномиальные коэффициенты связаны рекуррентными соотношениями. Кстати, `N(9,n)=C_{n}^0`,`N(8,n)=C_{n+1}^1`, `N(7,n)=C_{n+2}^2`. Так что ответ: `N(0,n)-1=C_{n+9}^9-1`.

[mpl]

Katrin_noise
Наберите все условие текстом.
Картинку сохраните
Карантин