===== №106 ===== Некоторые из марафонских задач привели к появлению новых последовательностей в OEIS. Макс Алексеев предложил использовать обратный механизм. ** Конкурсная задача №106 ** (от 3 баллов) Последовательность A116983 из OEIS определяется так:\\ a(n) есть порядковый номер n! при лексико-графическом упорядочении наборов цифр числа n! (система счисления десятичная). Последнее число, представленное в OEIS, - a(14). Требуется найти еще несколько членов A116983. Примечание:\\ Три балла будут присуждаются за нахождение a(15). За нахождение большего числа членов последовательности можно заработать больше баллов (но шкала, конечно, не линейная). **Решение** Приведу решение Кирилла Веденского. Алгоритм выглядит достаточно простым: посчитаем количество перестановок, следующих до данной.\\ Для этого суммируем количество перестановок:\\ - в которых первая цифра меньше исходной;\\ - в которых первая цифра такая же, а вторая цифра меньше исходной;\\ ...\\ - в которых первые N-2 цифр такие же, а N-1-я цифра меньше исходной;\\ Проиллюстрируем на примере 8! = 40320.\\ Количество перестановок, в которых первая цифра меньше исходной:\\ 4! (первая цифра 0) + 4!/2! (первая цифра 2, есть две цифры 0) + 4!/2 \\ (первая цифра 3, есть две цифры 0) \\ Количество перестановок, в которых первая цифра такая же, а вторая цифра меньше исходной;\\ 0 (нет таких) \\ Количество перестановок, в которых первые 2 цифры такие же, а третья цифра меньше исходной; \\ 2! + 2! \\ Количество перестановок, в которых первые 3 цифры такие же, а четвертая цифра меньше исходной; \\ 1! \\ Итого 53 перестановки, значит, 8! - 54-я перестановка из всех перестановок цифр {4, 0, 3, 2, 0}. 15! = 1307674368000 Расписываем в то же порядке:\\ 12!/(3!2!2!2!)\\ 11!/(3!2!2!2!)\\ 0\\ 9!/(2!2!2!) + 9!/(3!2!2!) + 9!/(3!2!2!) + 9!/(3!2!)\\ 8!/(2!2!) + 8!/(3!2!) + 8!/(3!2!)\\ 7!/2! + 7!/3! + 7!/3! + 7!/3!\\ 6!/2! + 6!/3!\\ 5!/2!\\ 4!/2!\\ 3!/2!\\ 0\\ 0\\ Итого a(15) = 10939036. **Обсуждение** Способ нахождения членов последовательсти A116983 вполне алгоритмичен, чем и воспользовались некоторые участники, написав программки для вычисления членов A116983. Вот список первых 56 элементов последовательности: a(1) = 1\\ a(2) = 1\\ a(3) = 1\\ a(4) = 1\\ a(5) = 4\\ a(6) = 6\\ a(7) = 11\\ a(8) = 54\\ a(9) = 150\\ a(10) = 648\\ a(11) = 5013\\ a(12) = 9849\\ a(13) = 19345\\ a(14) = 1060707\\ a(15) = 10939036\\ a(16) = 4343045\\ a(17) = 2498014850\\ a(18) = 5271260976\\ a(19) = 78029366100\\ a(20) = 531495923280\\ a(21) = 805809810981\\ a(22) = 1936900666393\\ a(23) = 28724010464057580\\ a(24) = 29052364970866225\\ a(25) = 75805259574286872\\ a(26) = 7466893805506395652\\ a(27) = 80374513001512054041\\ a(28) = 107970218135938755545\\ a(29) = 470625860768285164823489\\ a(30) = 1092067058367696093174712\\ a(31) = 23984179502628809216577528\\ a(32) = 28431347279097359718381340\\ a(33) = 5150626025769827081670834298\\ a(34) = 1383260201138264136247099733688\\ a(35) = 40096653135679607283637405247475\\ a(36) = 3027594894915571935964583506118250\\ a(37) = 82517117748871209433749833265061771\\ a(38) = 10023949507379486198666370320376\\ a(39) = 29591831094276619678264441606954339281\\ a(40) = 46163337982794725066771282077346710635365\\ a(41) = 167123778203520614156182186766168917610\\ a(42) = 4272219633615780983161453419886264089692720\\ a(43) = 3546219319786770869389311505619069504631590\\ a(44) = 3204643067047695510545225270846590879418010540\\ a(45) = 301067471734634074167312982076454590413566273570\\ a(46) = 3478763899948438152773353635560057199222936720\\ a(47) = 314243141648440488497781888595628832937846875377365\\ a(48) = 14170607816144726336291784998260829063896134279304644\\ a(49) = 81202660426509885662918837537639284122923959544881921\\ a(50) = 13644407265774224299787535849835296136167182364020957\\ a(51) = 3052207259954845501804716327832959568946835875197382056\\ a(52) = 177399590232335095419162842190728774132068534221263601977\\ a(53) = 63105836544205896419818591639582430508711794388085938746998\\ a(54) = 1806209354593919702746922384504295016188456176805030340137733\\ a(55) = 308850865213754797767705699091611299087770935471801259228401390\\ a(56) = 58908915753538772653766821227935807457550571804703650490041199\\ И это, разумеется тоже не предел! Например, Анатолий Казмерчук добрался до a(1214), Петр Бежик (по его словам: он прислал меньше членов A116983, чем продекларировал) - аж до a(1300). Отмечу, что по традиции на задачу, которая показалась скучной, как мне, так и участникам Марафона (см. эстетическую оценку), прислано рекордное для тура количество ответов :) **Награды** За правильное решение задачи ММ106 Виктор Филимоненков получает 3 призовых балла, Николай Дерюгин (он добрался до a(22)) - 4 баклла, Кирилл Веденский (он дошел до a(56) - 5 баллов, а Анатолий Казмерчук и Петр Бежик (им покорились более 1000 членов последовательности) - по 7 баллов. **Эстетическая оценка задачи - 2.3 балла** ----