2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Комбинаторика
Сообщение20.09.2015, 18:36 
Аватара пользователя


17/10/13
790
Деревня
Сколько есть $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}$, так?

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение20.09.2015, 19:17 
Заслуженный участник


16/02/13
4105
Владивосток
MestnyBomzh в сообщении #1055264 писал(а):
всего их получается: $10^{21}$
Уж не знаю, так или не так, но, учитывая, что 20-значных чисел всего-то $10^{20}$, ответ несколько странен.

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение20.09.2015, 19:24 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение20.09.2015, 19:27 


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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение20.09.2015, 19:36 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение20.09.2015, 19:42 


26/08/11
2057
ewert в сообщении #1055280 писал(а):
это стандартная задача: разбить число 20 на именно это количество положительных слагаемых;

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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение20.09.2015, 19:49 
Заслуженный участник


11/05/08
32166
Shadow в сообщении #1055282 писал(а):
Ведь есть только одно число, состоящее из напр. 4 единиц, 7 двоек, 0 троек,....9 девяток,

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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение20.09.2015, 19:52 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение20.09.2015, 20:19 
Заслуженный участник


11/05/08
32166
iancaple в сообщении #1055288 писал(а):
Давайте скачки посчитаем,

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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение21.09.2015, 13:19 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение21.09.2015, 14:42 


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

 Профиль  
                  
 
 Re: Комбинаторика
Сообщение22.09.2015, 06:15 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group