DoubleRec1. Магия биномиальных коэффициентов
Всем привет. Это статья. Я её пишу. Вы её читаете.
DoubleRec это типа rec rec — два слова: recursion и recovery. Рекурсия и излечение. Инь и Ян. Как вы поняли, мы будем лечить ваши функции от рекурсии.
Эта статья — опыт, накопленный мной за последние два года, в превращении рекурсивно заданных последовательностей в явно заданные [от номера элемента]. Конечно, эти подходы решают очень малую часть подобных задач, однако мне всё равно есть, что рассказать.
И, скорее всего, я не буду формулировать какие-то определённые методы, а просто придумаю и разберу три-четыре задачки.
Советую запастись биномиальными коэффициентами, знаками суммирования и произведения, математическими индукциями и малым пониманием комбинаторики.
Итак, начнём.
Если кто не понял правила последовательности, то мы просто увеличиваем цифру в цепочке до тех пор, пока она не станет равна предыдущей.
За что тут можно зацепиться? За цепочки с нулями. Заметим простой факт:
от цепочки 53210 до 53220 столько же элементов, сколько и от 9765410 до 9765420. А цепочек между 74300 и 74400 столько же, сколько и цепочек между 987300 и 987400.
Отсюда как раз выведем рекурсивный закон
Теперь нам с вами остаётся заметить, что 1 — это биномиальный коэффициент, а рекурсивная формула выше — это сумма всех последовательных элементов на порядок ниже. Если они все окажутся последовательными биномиальными коэффициентами, то и z(n, a) тоже будет биномиальным коэффициентом.
Следующее свойство я предлагаю доказать вам самим:
Вытекает оно из довольно простого свойства биномиальных коэффициентов
На самом деле, это обозначение не биномиального коэффициента, а количества сочетаний, но какая разница, если численно это одно и то же?
Тут важное замечание: если биномиальный коэффициент невозможно посчитать [случаи k < 0 и k > n], ты мы принимаем его равным нулю. Везде в этой статье и в этой математике.
Итак, суперкруто, вау, но мы отвлеклись. Напомню, у нас тут формула чуть-чуть отличается
Суммирование происходит так же от нуля, но не до a-1, а до a. Одно лишнее слагаемое. И, выходит, при увеличении n количество лишних слагаемых будет накапливаться.
Если вы посчитаете пару-тройку разных значений нашей функции и сравните их с треугольником Паскаля, то найдёте такую вот закономерность:
Теперь надо доказать это с помощью математической индукции. Это просто самый быстрый способ. Уже потом можно будет найти в этом особый комбинаторный смысл.
Ура! Продолжим. Теперь введём ещё одну функцию:
Красивенько. Теперь мы можем ответить на вопрос задачи. Номер известной цепочки — это сумма всех Z, где вместо a стоит значение альфы, а вместо n порядковый номер. Вот и имеем:
Давайте теперь проверим на примере из условия. Возьмём цепочку 211. Известно, что её порядковый номер — 7. Что же даст наша формула?
И, чтобы ещё раз убедиться, проверим на 222:
По-моему, получилось замечательно.
Давайте теперь, зная номер и длину цепочки, восстановим её?
Сначала на примере, потом обобщим алгоритм и запишем функцию.
Итак, необходимо найти 121-ю цепочку длины 5.
Если кто захочет проверить, буду рад.
Теперь выведем общую формулу.
Для этого введём следующую функцию
Она ищет наибольший такой биномиальный коэффициент, который можно вычесть из данного числа n. Её, кстати, тоже можно записать рекурсивно
Прибавляемый флур никогда не будет больше единицы. Это своеобразный индикатор равенства n следующему биномиальному коэффициенту. Я не нашёл пока способ записать данную функцию без рекурсии, но если найду, то внесу такую задачку в статью.
И теперь введём последовательность
То есть мы последовательно вычитаем из n максимальные биномиальные коэффициенты и забиваем получившимися результатами нашу последовательность.
Кстати, она тоже рекурсивно задана. Но, боюсь, пока у нас нет явного задания для g, мы не сможем выразить и m.
И всё. Для заданного номера n и длины цепочки k наша цепочка может быть получена следующим образом:
Проверим на разобранном примере. n = 121, k = 5.
Вроде, решили.
Усложняем.
Тут также легко заметить рекурсивный закон, который, однако, требует двух функций:
И та самая рекурсивная формула:
Откуда эта формула? Ну, первую цифру мы знаем. Она a. Оставшиеся k-1 цифра могут образовывать любые законные цепочки, за исключением тех, в которых a встречается максимальное число раз. Если в цепочке a встречается максимальное число раз, то мы не сможем прилепить к ней ещё одну a.
Тут стоит отметить, что z' — это обрезанное z. Из z просто взяли и вычли все цепочки с максимальным количеством элементов a.
Что же это за цепочки? Это те цепочки, в которых первые m-1 элементов — это a, и больше a впихнуть нельзя. А оставшиеся элементы образуют любые маленькие цепочки, начинающиеся на цифру меньше a.
Отсюда вот:
Здесь важно отметить, что эта формула будет работать довольно плохо для случая k ≤ m-1. Потому что z при неположительных k мне определять не хочется, а он появляется в правой части формулы. Будет лучше, если мы запишем эти случаи отдельно:
И теперь z' нам становится не нужна, так как мы нашли способ определить z через саму себя. Просто подставим вместо z' те формулки, что мы вывели:
По аналогии выведем все остальные. В итоге получим:
И теперь, чтобы было совсем красивенько:
И чтобы рекурсия где-нибудь как-нибудь прекратилась, заметим, что последний вариант (k < m) ничем не отличается от прошлой задачи. Ведь если m > k, то m никак не ограничивает нашу цепочку.
Следующий этап решения задачи называется «считай и замечай». Возьмём какое-нибудь конкретное значение m и запишем первые несколько членов при любых a.
Например, мы знаем, что
Теперь рекурсивно вычислим z(3, 3, a). Это сумма биномиальных коэффициентов прошлого уровня без единицы.
Зная, что впереди нас ждут сложения циферок, и что биномиальные коэффициенты хорошо складываются, запишем 1 в удобном для нас виде:
Вот вам две маленькие леммы, которые на самом деле одна, и которые даже не леммы.
Пользуясь этим прекрасным отношением запишем вот что:
То есть мы можем просто брать биномиальные коэффициенты из прошлого z, увеличивать им верхушку на единицу, низушку либо увеличивать, либо не увеличивать, и таким образом оставлять.
Так мы и будем поступать дальше, и выведем ещё несколько элементов:
Надеюсь, логику вы поняли, и дальше я могу приводить значения без вычислений
Тут уже видно некоторую закономерность: слагаемые идут парами, а коэффициенты, стоящие перед ними, также являются биномиальными коэффициентами:
Заметим, что у коэффициентов в произведениях совпадают индексы по диагонали. Давайте введём «триномиальные коэффициенты»:
В общем случае это называется мультиномиальным коэффициентом, или полиномиальным коэффициентом, и у них много интересных и, наверное, неизученных свойств. Возникают они в задачах типа «сколькими различными способами можно разбить множество из a элементов на подмножества по b, c, … элементов»
Нам достаточно триномиального коэффициента.
Пользуясь нововведением, перепишем наши подсчитанные штучки:
Вот, теперь уже совсем красиво. Остаётся заметить, что те тройки, на которые отличаются нижние части триномиальных коэффициентов [идущих через один]— это m, а те двойки, на которые отличаются нижние части соседних триномиальных коэффициентов — это m-1.
Тогда можно предположить, что общая формула имеет вид:
Или, более коротко:
На деле, конечно, слагаемых будет не бесконечно много. Просто с определённого момента все триномиальные коэффициенты станут равны нулю. А бесконечность — потому что с бесконечностью проще работать.
Спойлер: формула верна. Доказывается, как мы с вами и Если вам интересно почитать доказательство, то вот:
На практике нам, наверное, будет удобнее пользоваться этой формулой:
Её мы, кстати, с вами в первую очередь и заметили: перед тем как перешли к триномиальным коэффициентам.
Если вы подойдёте к какому-нибудь человеку и скажете, что эту формулу вы заметили, то вас хорошенько так треснут сковородой. Тем не менее, используя разные подходы, можно заметить разные штуки, зачастую намного сложнее этой. Вспомним, например, статью Арифметические прогрессии 2.0. Хотя я бы не сказал, что там было сильно сложнее, чем здесь.
Итак, дело за мылом. За мылам. Малом. Мылам. Сейчас. Ещё немного и я попаду пальцами туда, куда хочу. За малым.
Вводим функцию, по аналогии с прошлой задачей, обозначающую количество всех цепочек, первая цифра которой не больше заданного значения:
И, как мы делали в прошлый раз, запишем формулу для номера текущей цепочки:
Решить обратную задачу — по номеру восстановить цепочку, — можно как и в прошлый раз, но мне, честно говоря, это очень лень делать.
Небольшие рассуждения одного Мынки о биномиальных и мультиномиальных коэффициентах
В большинстве задач, особенно комбинаторных, да и в определении биномиальных коэффициентов через бином Ньютона, нам удобно располагать все биномиальные коэффициенты в виде известного вам треугольника Паскаля:
Здесь в строке зафиксировано n, а k проходит по всем возможным значениям. При этом каждое значение равно сумме двух стоящих над ним.
Однако в тех задачах, которые решаем мы с вами, намного понятнее смотрится матрица Паскаля:
Здесь каждый элемент равен сумме стоящих над и слева от него. И, кроме этого, каждый элемент равен сумме всех стоящих над ним элементов. Это очень крутое свойство.
Но, согласитесь, смотрится эта матрица совсем не очень. Было бы намного лучше, сделай мы так:
По хорошему, между i и j нужно ставить запятые, но поскольку у нас везде пока что однозначные числа, я позволил себе этого не делать.
Итак, что же это за надпись такая? Это обозначение я придумал [хотя не думаю, что оно новое], когда заметил, что, как правило, на делитель (n-k)! все забивают:
При этом n-k находится в равном с k положении. И отсюда запись:
Которая легко расширяется в нечто большее:
И если биномиальный коэффициент действительно часто удобнее записывать классическим образом, то все свойства мультиномиального коэффициента в полной красе раскрываются лишь в той записи, что я привёл.
Ну и, конечно, наше любимое свойство:
Записывается очень красиво в новом виде:
И оно же обобщённое:
И, например, выражение мультиномиального коэффициента через произведение биномиальных:
Вот. К чему я это? Сам не знаю. Но тема очень интересная и не лишняя в рамках этой статьи. Можете попробовать записать функции из прошлых задач, используя новую запись, должно выйти красиво.
Тем не менее, цикл (возможно, цикл) статей посвящён рекурсиям. И конкретно эта статья, в основном, о том, как, заметив бинауральные коэффициенты, задать данную вам функцию явно. Поэтому оставим вопросы о записи в прошлом разделе и вернёмся к основной части.
Немного отдохнём. Возможно, вы согласитесь, что первые числа, которые ассоциируются с рекурсией — это числа Фибоначчи. Удивительное свойство связывает эти крутейшие числа с не менее крутейшими и более родными нам биномиальными коэффициентами.
Я наткнулся на него случайно, листая Википедию. Доказывается оно просто, по индукции, поэтому если вы будете знать это свойство, вы без проблем его докажете. Я же хочу предложить вам заметить его самостоятельно.
Если что, мы принимаем следующий вариант нумерации чисел Фибоначчи:
К сожалению, я не гений и не волшебник, и не могу показать вам красивого вывода через комбинаторику или другие штуки. Но, по-моему, вполне логично записать:
Ну и из той же логики запишем:
Чего не хватает F3? F3 = 2. Не хватает единицы. F4 = 3. Ему не хватает 2. Среди биномиальных коэффициентов лишь один равен двум. Если предположить [следуя из жизненного опыта от прошлой задачи], что правые части для 3-го и 4-го чисел Фибоначчи содержат по два слагаемых, то запишем:
И коэффициент для 3-го числа, максимально близкий по виду к тому, что мы записали, будет такой:
Соглашусь, что это может быть притянуто за уши, так как я, к сожалению, это свойство самостоятельно никогда не замечал. Тем не менее, теперь вы можете видеть, что общий вид это всё и вправду имеет.
В общем, вот:
В общем виде это свойство выглядит так:
Вот так красиво. Доказывается по индукции, как и всё то, чем мы занимались в этой статье. А самое главное — данный вид не содержит рекурсии, что позволяет посчитать любое число Фибоначчи без расчёта предыдущих.
Это никому не нужно, так как посчитать n/2 биномиальных коэффициентов не легче. А ещё существует формула Бине. Но всё равно прикольно.
.
.
.
Прошло несколько дней, и я наконец-то вроде настроился написать последний раздел статьи. Прошу простить меня за мою лень, просто появились продвижения в области магических квадратов, и я слегка отвлёкся.
Предлагаю решить с вами одну задачу, пользуясь методами комбинаторики тем свойством фибоначчиевых чисел, что мы обсудили только что — для вас, и три дня назад — для меня.
Задача, в общем-то, про рекурсии. Но эту рекурсию в моём решении вы не увидите, так как её мы частично устранили тем самым свойством, и окончательно добьём другими способами. Задачу я публиковал однажды на стене. Многие, в отличие от меня, её быстро решили, но решения, хотя бы примерно столь же тупого, как моё, я не увидел. Только сегодня и только сейчас! Делюсь тупизмом.
Три абзаца пустого текста, и вот, наконец-то задача:
Первым делом найдём вероятность того, что n-й математик будет последним. То есть на n-м и (n-1)-м бросках должны выпасть орлы. Здесь стоит отметить, что если на каком-то броске падает решка, то следующий бросок ничем не будет отличаться от самого первого. Назовём такое явление «новым началом». От одного начала до другого начала можно добраться либо одной решкой, либо последовательностью орёл-решка.
Чтобы игра закончилась, последние два хода должны выпасть орлы — вероятность этого ½*½ = ¼. А до этого должно наступить начало. Остаётся посчитать вероятность того, что n-2-й ход окажется началом. Прийти к этому можно различными комбинациями решек и орлорешек. Вообще говоря, вероятность любой конкретной комбинации
так как мы сделали n-2 независимых бросков монеты с вероятностью ½. Наша же задача — посчитать общее количество таких комбинаций.
Я предлагаю объединять их в группы по количеству орлорешек. Например, возьмём все комбинации в которых 0 орлорешек. Сколько таких комбинаций в группе? Очевидно — одна. Это комбинация из одних решек.
Теперь возьмём комбинации с 1 орлорешкой? Сколько таких комбинаций? Орлорешка занимает 2 места, значит, должно быть n-2-2 = n-4 просто решки. Нам нужно разбить некоторое множество элементов на подмножества по 1-му элементу и по n-4. Иначе, посчитать биномиальный коэффициент:
Ровно столько комбинаций с одной орлорешкой.
Сколько же комбинаций с k орлорешками? У нас k орлорешек и n-2-2k отдельных решек. В сумме n-2-k элементов. Из них нам нужно случайным образом выбрать k орлорешек. То есть нужно найти количество сочетаний
из n-2-k по k. Вот и имеем
различных комбинаций, в которых ровно k орлорешек.
Очевидно при этом, что мы не сможем вместить в n-2 места больше орлорешек, чем мы сможем вместить. Одна орлорешка занимает 2 места, поэтому
— это максимальное количество орлорешек в комбинации. Всего же комбинаций, выходит:
А мы с вами уже выяснили, что такая сумма равна фибоначчивскому числу:
Вот и выходит, что вероятность того, что n-й математик будет последними, равна
Давайте проверим, что мы действительно правы, и сумма всех вероятностей [события, при которых математики с номерами n и m оказались последними, и n ≠ m — несовместные] равна единице [условие нормировки]. То есть нам надо доказать следующее равенство
Здесь мы используем старый морской обычай. Обычно этот метод используют, считая ряды, похожие на сумму геометрической прогрессии, но и с числами Фибоначчи он прекрасно сработал [отчасти потому, что если расписать число Фибоначчи по формуле Бине, получится сумма двух геометрических прогрессий]. Для удобства, решим это в общем виде:
Давайте запишем рядышком нашу сумму, и её же, домноженную на q:
И теперь сложим:
Остаётся перенести S в правую сторону и вынести за скобку:
Теперь подставим ½ вместо q и получим необходимое нам равенство. В уме считается, что и в числителе, и в знаменателе будет -¼, и при сокращении получится 1.
Отлично.
Матожидание в таком случае можно посчитать как ряд:
Повторим наш предыдущий опыт:
Запишем этот ряд, и такой же:
И сложим их. Я постараюсь объяснять шаги в процессе:
Обратите внимание, что в левой части новых скобок у нас теперь возрастает коэффициент перед числом Фибоначчи, а в правой части этих скобок числа Фибоначчи идут с коэффициентом 1. Сейчас мы раскроем скобки и попытаемся объединить часть слагаемых в ряд S, а другую часть в ряд T:
Итак, в новой первой скобке у нас ряд, практически равный T/q. Однако для того, чтобы равенство случилось, нужно прибавить к этому ряду 2S/q. И, соответственно, вычесть. Сумма, записанная во второй скобке — это ряд S, которому, формально, не хватает слагаемого qF0. Поэтому превращая скобку в S, мы должны будем вычесть qF0:
Теперь дело за малым. Вспомним, что F0 = 0, и забьём на все слагаемые, содержащие F0. Те, которые есть, выкинем, а те, что нужны, допишем. В правой части скобок мы почти получили T/q, не хватает F0 + 2qF1, которые можно взять из правой части этих же скобок. Учитывая это всё, запишем:
Остаётся подставить q = ½, и получить:
Согласитесь, довольно неожиданное число. Чтобы выпало два орла подряд, нужно в среднем подкинуть монету 12 раз.
На этом я предлагаю закончить статью. В следующей части, если она будет, рассмотрим другие обобщения последней задачи, скорее всего, поразбираемся в линейной рекуррентной последовательности и введём какую-нибудь новую крутую теорему в этот бренный мир.
Всем большого добра и хорошего сна в последний месяц лета.