Комбинаторика

[MestnyBomzh]

Сколько есть $20$ -ти значных чисел, цифры в записи которых расположены в порядке неубывания.
Я сначала подумал про меньше, чем 10- ти значные числа: там можно сделать строгое убывание $C_{10}^n$ способами: берем $n$ цифр, далее их однозначно можно поставить в порядке убывания. Кажется мне, что если решить проблему неубывания для <10 значных чисел, то и для 20-ти можно будет решить. Только вот я не знаю как решить эту проблему

-- 20.09.2015, 19:49 --

Хотя сейчас у меня возникла такая идея.
Так сказать, идея "дополнительного множества". Поставим в соответствие каждому неубывабщему числу свое число по следующему правилу: 1->9; 2->8;...;9->1. Нетрудно видеть, что полученные числа будут невозрастающими. Тогда их суммой будет $n \cdot 10^{21}$. В то же время $n*10^{21}= S-S_1-S_2$. Где $S$-сумма всех натуральных чисел от 1..99999999999999999999 (20 девяток). А $S_1, S_2$ - сумма всех строго возрастающих и строго убывающих. Но их сумма равна нулю, так как таких чисел нет просто.
Получилось линейное уравнение, верно?

-- 20.09.2015, 19:53 --

Только нужно учесть число 555...5: $n \cdot 10^{21} = S + 5....5$

-- 20.09.2015, 20:04 --

Ну и тогда всего их получается: $10^{21}$, так?

[iifat]

MestnyBomzh в сообщении #1055264 писал(а):

всего их получается: $10^{21}$

Уж не знаю, так или не так, но, учитывая, что 20-значных чисел всего-то $10^{20}$, ответ несколько странен.

[MestnyBomzh]

А, ну конечно. Я неправильно посчитал сумму неубывающего и невозрастающего
Сейчас пересчитаю

[Shadow]

Количесто композиций числа, определенной длиной, с нулями

[ewert]

Ну если достаточно получить результат в виде некой суммы, то можно так. Перебираем все возможные количества различных цифр, задействованных в числе. Для каждого конкретного количества перебор по возможным группировкам одинаковых цифр -- это стандартная задача: разбить число 20 на именно это количество положительных слагаемых; ответом будет некоторое $C_n^k$. Теперь для каждой группировки рассыпаем по группам возможные цифры; это -- ещё какое-то $C_n^k$. Перемножаем, складываем -- и всё; а удастся ли потом это дело свернуть -- не знаю, лень. Если удастся, то, конечно, есть какой-то более эффективный способ решения.

[Shadow]

ewert в сообщении #1055280 писал(а):

это стандартная задача: разбить число 20 на именно это количество положительных слагаемых;

Только неотрицательых слагаемых. И я думаю все. Ведь есть только одно число, состоящее из напр. 4 единиц, 7 двоек, 0 троек,....9 девяток, цифры которого расположены в неубывающем порядке.

[ewert]

Shadow в сообщении #1055282 писал(а):

Ведь есть только одно число, состоящее из напр. 4 единиц, 7 двоек, 0 троек,....9 девяток,

Да, это правда. (я набил свой ответ до Вашего, а дальше вдумываться было опять же лень)

[iancaple]

Давайте скачки посчитаем, это $a_k-a_{k-1},k=1,...21,a_0=1,a_{21}=9$,а остальные $a_1...a_{20}$ это цифры числа. Их сумма равна 8, их 21 штука, мы как будто размещаем 8 "единиц скачка" с повторениями на 21 позицию. Ответ оставляю вам

Вспомнил термин"сочетания с повторениями"

[ewert]

iancaple в сообщении #1055288 писал(а):

Давайте скачки посчитаем,

Это практически то же самое, что и у Shadow, только с лишними логическими пируэтами.

[TOTAL]

Или как сумма коэффициентов перед маленькими степенями $x$ в $x(1-x)^{-20}$

[ET]

А вам это для чего? Рекуррентные формулы там элементарные, на компе по ним считается доли секунды, даже на листе бумажки по ним, наверное, возможно. Если просто цифру получить, то вроде вот: 3108105 (это именно 20значные числа, то есть первая цифра не 0)

[TOTAL]

Без рекуррентных формул: это коэффициент перед $x^{8}$ в $(1+x)^{20+8}$