Хабрахабр

[Перевод] Делимые факториалы

Недавно я был совершенно сбит с толку этим твитом «Библиотеки Ферма»:

«Вот что получится, если в факториале не умножать, а делить.»

Результат в черновом виде казался логичным. Когда я увидел его, мне пришлось бросить свои дела, схватить блокнот и проверить форулу. И $\frac{n!}$ ведёт себя именно так; полиномиальная функция $n^2$ растёт медленнее, чем степенная функция $n!$ для достаточно больших $n$: Так как мультипликативная версия $n!$ при увеличении $n$ стремится к бесконечности, то «делительная» версия должна стремиться к нулю.

$\frac{1}{1}, \frac{4}{2}, \frac{9}{6}, \frac{16}{24}, \frac{25}{120}, \frac{36}{720}, \frac{49}{5040}, \frac{64}{40320}, \frac{81}{362880}, \frac{100}{3628800}$

Но почему результат деления принимает именно вид $\frac{n^2}{n!}$? Откуда берётся $n^2$?
Чтобы ответить на этот вопрос, мне пришлось разбередить старую травму, связанную с изучением деления дробей, но я справился с болью. Двигаясь по формуле из твита слева направо, мы сначала получаем $\frac{n}{n-1}$. Затем, поделив эту величину на $n-2$, получаем

$\cfrac{\frac{n}{n-1}}{n-2} = \frac{n}{(n-1)(n-2)}$

Продолжая таким образом, мы в результате приходим к:

$n \mathbin{/} (n-1) \mathbin{/} (n-2) \mathbin{/} (n-3) \mathbin{/} \cdots \mathbin{/} 1 = \frac{n}{(n-1) (n-2) (n-3) \cdots 1} = \frac{n}{(n-1)!}$

Чтобы прийти к показанному в твите результату $\frac{n^2}{n!}$, мы просто умножим числитель и знаменатель на $n$. (Хотя на мой вкус, выражение $\frac{n}{(n-1)!}$ более понятно.)
Я официально признанный фанат факториалов. Оставьте при себе свои последовательности Фибоначчи; вот моя любимая функция. Каждый раз, когда я изучаю новый язык программирования, моим первым упражнением становится написание нескольких процедур для вычисления факториалов. За многие годы я придумал несколько вариаций этой темы, например, замену в определении $\times$ на $+$ (что даёт нам треугольные числа). Но кажется, что раньше я никогда не задумывался о замене $\times$ на $\mathbin{/}$. Получается странно. Так как умножение коммутативно и ассоциативно, мы можем определить $n!$ просто как произведение всех целых чисел от $1$ до $n$, не беспокоясь о порядке операций. Но при делении порядок игнорировать не получится. В общем случае, $x \mathbin{/} y \ne y \mathbin{/}x$ и $(x \mathbin{/} y) \mathbin{/} z \ne x \mathbin{/} (y \mathbin{/} z)$.

Очевиднее всего будет заменить это на порядок по возрастанию: $1, 2, 3, \ldots, n$. В твите «Библиотеки Ферма» делители поставлены в порядке по убыванию: $n, n-1, n-2, \ldots, 1$. Ещё один возврат к школьному алгоритму деления дробей даёт нам простой ответ: Что произойдёт, если мы зададим факториал деления как $1 \mathbin{/} 2 \mathbin{/} 3 \mathbin{/} \cdots \mathbin{/} n$?

$1 \mathbin{/} 2 \mathbin{/} 3 \mathbin{/} \cdots \mathbin{/} n = \frac{1}{2 \times 3 \times 4 \times \cdots \times n} = \frac{1}{n!}$

Другими словами, когда мы многократно выполняем деление, выполняя подсчёт от $1$ до $n$, окончательный результат будет равен величине, обратной $n!$. (Мне хотелось бы поставить в конце этого предложения восклицательный знак, но увы!) Если вы ищете канонический ответ на вопрос «Что мы получим при делении вместо умножения в $n!$?», то я бы заявил, что $\frac{1}{n!}$ — лучший кандидат, чем $\frac{n}{(n - 1)!}$. Почему бы нам не принять симметрию между $n!$ и обратной ему величиной?

Но сколько именно? Разумеется, есть множество других способов размещения n целочисленных значений во множестве $\{1 \ldots n\}$. Поэтому, может показаться, что есть $n!$ уникальных способов задания делительной функции $n!$. Как оказалось, ровно $n!$! Какой бы элемент последовательности не появился первым, он оказывается в числителе большой дроби, а знаменателем оказывается произведение всех других элементов. Однако, изучение ответов двух показанных выше перестановок даёт нам понять, что здесь работает более простой паттерн. Для любого целочисленного $k$ в интервале от $1$ до $n$, поставив $k$ в начало очереди, мы создаём делительное $n!$, равное $k$, поделённому на все другие коэффициенты. Поэтому в итоге остаётся всего $n$ различных результатов (если предположить, что мы всегда выполняем операции деления строго слева направо). Можно записать это следующим образом:

$\cfrac{k}{\frac{n!}{k}}, \text{ что можно преобразовать в } \frac{k^2}{n!}$

И таким образом мы решили небольшую загадку о том, как в этом твите $\frac{n}{(n-1)!}$ превратилось в $\frac{n^2}{n!}$.
Стоит заметить, что все эти функции сходятся к нулю при стремлении $n$ к бесконечности. С асимптотической точки зрения, $\frac{1^2}{n!}, \frac{2^2}{n!}, \ldots, \frac{n^2}{n!}$ идентичны.
Та-да! Миссия выполнена. Задача решена. Дело сделано. Теперь мы знаем всё, что нам нужно, о делительных факториалах, верно?

Что скажет компьютер? Ну, возможно, есть ещё один вопрос. Какие из $n$ вариантов делительного $n!$ выдаст нам программа? Если взять наш любимый алгоритм факториала, и сделать то, что предлагается в твите, заменив все вхождения оператора $\times$ (или *) на /, то что случится?

Вот мой любимый алгоритм для вычисления факториалов в виде программы на Julia:

function mul!(n) if n == 1 return 1 else return n * mul!(n - 1) end
end

Этот алгоритм познакомил целые поколения нердов с концепцией рекурсии. В текстовом виде он гласит: если $n$ равно $1$, то $mul!(n)$ равно $1$. В противном случае нужно вычислить функцию $mul!(n-1)$, а затем умножить результат на $n$.

Спросить вы можете, но лучше не надо. Вы можете спросить, что произойдёт, если $n$ будет равным нулю или отрицательным. Для наших текущих целей $n \in \mathbb{N}$.

Начав с любого положительного $n$, последовательность рекурсивных вызовов рано или поздно опустится к $n = 1$.

Функцию можно записать более лаконично с помощью однострочного стиля определений Julia:

mul!(n) = n == 1 ? 1 : n * mul!(n - 1)

Правая часть оператора присваивания — это условное выражение, или тернарный оператор, имеющий вид a ? b : c. Здесь a — булево условие теста, которое должно вернуть значение или true, или false. Если a равно true, то вычисляется выражение b, а результат становится значением всего выражения. В противном случае вычисляется c.

Просто чтобы убедиться, что я сделал всё верно, вот первые 10 факториалов, вычисленных этой программой:

[mul!(n) for n in 1:10]
10-element Array{Int64,1}: 1 2 6 24 120 720 5040 40320 362880 3628800

Теперь давайте изменим это определение и преобразуем единственное вхождение * в /, оставив всё остальное неизменным (за исключением названия функции).

div!(n) = n == 1 ? 1 : n / div!(n - 1)

И вот что вернёт программа, если мы запустим её для значений $n$ от $1$ до $20$:

[div!(n) for n in 1:20]
20-element Array{Real,1}: 1 2.0 1.5 2.6666666666666665 1.875 3.2 2.1875 3.657142857142857 2.4609375 4.063492063492063 2.70703125 4.432900432900433 2.9326171875 4.773892773892774 3.14208984375 5.092152292152292 3.338470458984375 5.391690662278897 3.523941040039063 5.675463855030418

Что? Это точно не походит на схождение к нулю, как и на $\frac{1}{n!}$ или $\frac{n}{n - 1}$. На самом деле значения так не выглядят, потому что и не собираются сходиться. Судя по показанному ниже графику, последовательность состоит из двух перемежающихся компонентов, каждый из которых, похоже, медленно растёт в сторону бесконечности, а также отклоняется от другого.

Разбираясь с тем, что же мы здесь наблюдаем, полезно будет изменить тип выходных данных функции div!. Вместо использования оператора деления /, который возвращает значение как число с плавающей запятой, мы можем заменить его оператором //, возвращающим точное рациональное значение, округлённое до младшего члена.

div!(n) = n == 1 ? 1 : n // div!(n - 1)

Вот последовательность значений для n в интервале 1:20:

20-element Array{Real,1}: 1 2//1 3//2 8//3 15//8 16//5 35//16 128//35 315//128 256//63 693//256 1024//231 3003//1024 2048//429 6435//2048 32768//6435 109395//32768 65536//12155 230945//65536 262144//46189

В списке полно любопытных паттернов. Это двойная спираль, в которой чётные и нечётные числа зигзагами перемещаются в комплементарных нитях. Чётные числа не просто чётные, все они являются степенями $2$. Кроме того, они появляются в парах — сначала в числителе, затем в знаменателе — и их последовательность неубывающая. Но существуют пробелы; присутствуют не все степени $2$. Нечётная нить выглядит ещё более сложной, в числах появляются и исчезают разные небольшие простые коэффициенты. (Простые числа должны быть малыми, как минимум, меньше $n$.)

Я ожидал увидеть гораздо более смирную последовательность, наподобие тех, которые я вычислял на бумаге. Этот результат удивил меня. Как не имел смысла и общий тренд к неограниченному росту соотношения. Все эти изломанные скачки вверх и вниз не имели никакого смысла. Как мы можем постоянно делить, получая при этом всё бОльшие и бОльшие числа?

Если вам нужна подсказка, то у вас она есть, и очень сильная, почти спойлер: поищите последовательность числителей или последовательность знаменателей в «Онлайн-энциклопедии целочисленных последовательностей». На этом этапе можете приостановить чтение и попытаться придумать собственную теорию о том, откуда взялись эти зигзагообразные числа.

Вот ещё одна подсказка. Небольшое изменение в программе div! полностью преобразует выходные данные. Просто изменим последнее выражение, заменив n // div!(n - 1) на div!(n - 1) // n.

div!(n) = n == 1 ? 1 : div!(n - 1) // n

Теперь результаты выглядят вот так:

10-element Array{Real,1}: 1 1//2 1//6 1//24 1//120 1//720 1//5040 1//40320 1//362880 1//3628800

Это обратная функция факториала, которую мы уже видели, ряд значений, сгенерированные при обходе слева направо по возрастающей последовательности делителей $1 \mathbin{/} 2 \mathbin{/} 3 \mathbin{/} \cdots \mathbin{/} n$.

В конце концов, мы знаем, что деление не коммутативно и не ассоциативно. Неудивительно, что изменение последнего выражения в процедуре менят результат. Какой механизм порождает такие парные степени двойки и попеременные нечётные и чётные значения? Но сложно понять, почему последовательность сгенерированных исходной программой значений даёт такую странную зигзагообразную форму.

(Это заявление может показаться досадным тем, кто считает рекурсивные определения более простыми, но так уж получилось.) Вот как выглядит программа: Я обнаружил, что объяснить происходящее в зигзагообразной последовательности проще на итеративной версии процедуры, а не на рекурсивной.

function div!_iter(n) q = 1 for i in 1:n q = i // q end return q
end

Я заявляю, что эта процедура с циклом по функционалу идентична рекурсивной функции, в том смысле, что если div!(n) и div!_iter(n) возвращают результат для какого-то положительного целого n, то он всегда будет одинаковым. Вот моё доказательство:

[div!(n) for n in 1:20] [div!_iter(n) for n in 1:20] 1 1//1 2//1 2//1 3//2 3//2 8//3 8//3 15//8 15//8 16//5 16//5 35//16 35//16 128//35 128//35 315//128 315//128 256//63 256//63 693//256 693//256 1024//231 1024//231 3003//1024 3003//1024 2048//429 2048//429 6435//2048 6435//2048 32768//6435 32768//6435 109395//32768 109395//32768 65536//12155 65536//12155 230945//65536 230945//65536 262144//46189 262144//46189

Чтобы понять процесс, порождающий эти числа, рассмотрим последовательные значения переменных $i$ и $q$ при каждом выполнении цикла. Изначально $i$ и $q$ равны $1$; поэтому после первого прохода цикла выражение q = i // q даёт $q$ значение $\frac{1}{1}$. Затем $i = 2$, а $q = \frac{1}{1}$, то есть новое значение $q$ равно $\frac{2}{1}$. При третьей итерации $i = 3$, а $q = \frac{2}{1}$, что даёт нам $\frac{i}{q} \rightarrow \frac{3}{2}$. Если это всё ещё сбивает вас с толку, то представьте $\frac{i}{q}$ как $i \times \frac{1}{q}$. Важным наблюдением здесь является то, что при каждом обходе цикла $q$ получает обратное значение, становясь $\frac{1}{q}$.

Если развернуть эти операции и посмотреть на умножения и деления, входящие в каждый элемент ряда, то возникает паттерн:

$\frac{1}{1}, \quad \frac{2}{1}, \quad \frac{1 \cdot 3}{2}, \quad \frac{2 \cdot 4}{1 \cdot 3}, \quad \frac{1 \cdot 3 \cdot 5}{2 \cdot 4} \quad \frac{2 \cdot 4 \cdot 6}{1 \cdot 3 \cdot 5}$

В общем виде:

$\frac{1 \cdot 3 \cdot 5 \cdot \cdots \cdot n}{2 \cdot 4 \cdot \cdots \cdot (n-1)} \quad (\text{odd } n) \qquad \frac{2 \cdot 4 \cdot 6 \cdot \cdots \cdot n}{1 \cdot 3 \cdot 5 \cdot \cdots \cdot (n-1)} \quad (\text{even } n)$

Функции $1 \cdot 3 \cdot 5 \cdot \cdots \cdot n$ для нечётного $n$ и $2 \cdot 4 \cdot 6 \cdot \cdots \cdot n$ для чётного $n$ имеют собственное название! Они называются двойными факториалами, и записываются как $n!!$.

Лучше бы их назвали «полуфакториалами». Ужасная терминология, правда? И если бы я этого не знал, то прочитал бы $n!!$ как «факториал факториала».

Таким образом, наша любопытная последовательность зигзагообразных значений — это просто $\frac{n!!}{(n-1)!!}$. Двойной факториал n определяется как произведение n и всех меньших положительных целых чисел той же чётности.

Гулда и Джослин Куэнтенс (увы, находящаяся за paywall) исследуются применения двойных факториалов. В статье 2012 года Генри У. В середине 17-го века Джон Валлис вывел следующее тождество: Они встречаются гораздо чаще, чем можно подумать.

$\frac{\pi}{2} = \frac{2 \cdot 2 \cdot 4 \cdot 4 \cdot 6 \cdot 6 \cdots}{1 \cdot 3 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdots} = \lim_{n \rightarrow \infty} \frac{((2n)!!)^2}{(2n + 1)!!(2n - 1)!!}$

Ещё более странный ряд с участием куба значений двойных факториалов суммируется в $\frac{2}{\pi}$. Его обнаружил не кто иной, как Сриниваса Рамануджан.

Стандартный биномиальный коэффициент определяется как: Гулд и Киэнтенс также рассматривали эквивалент двойного факториала для биномиальных коэффициентов.

(n-k)!}$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/f11/d1a/4fd/f11d1a4fdce5b55b85399ca01c32c8bd.svg" alt="$\binom{n}{k} = \frac{n!}{k!

Двойная версия выглядит так:

(n-k)!!}$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/703/4cf/bec/7034cfbeca333f5efad30c1891d9b072.svg" alt="$\left(\!\binom{n}{k}\!\right) = \frac{n!!}{k!!

Заметьте, что наши зигзагообразные числа соответствуют этому описанию, а потому могут считаться биномиальными коэффициентами двойных факториалов. Говоря конкретнее, они являются такими числами:

(n-1)!!}$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/564/f27/832/564f27832aa2a0bf6b142a3c72f01e70.svg" alt="$\left(\!\binom{n}{1}\!\right) = \left(\!\binom{n}{n - 1}\!\right) = \frac{n!!}{1!!

Обычный бином $\binom{n}{1}$ не очень интересен; он просто равен $n$. Но двойная версия $\left(\!\binom{n}{1}\!\right)$, как мы видели, танцует более оживлённый танец. И в отличие от обычного бинома она не всегда бывает целочисленной. (Единственные целые значения — это $1$ и $2$.)

Также мы можем увидеть, почему все чётные числа в последовательности являются степенями 2. Взгляд на зигзагообразные числа как на частное двойных факториалов объясняет довольно многие их свойства, начиная с попеременных чётных и нечётных значений. Числитель этой дроби — это $2 \cdot 4 \cdot 6 = 48$, получающий от $6$ множитель $3$. Рассмотрим пример с $n = 6$. Тройки сверху и снизу сокращаются, оставляя нам $\frac{16}{5}$. Но знаменатель равен $1 \cdot 3 \cdot 5 = 15$. Каждый раз, когда в последовательности чётных чисел появляется нечётный множитель $m$, он обязательно имеет вид $2 \cdot m$, но к этому времени само $m$ уже должно появиться в последовательности нечётных чисел. Такие сокращения происходят в каждом из случаев.

Является ли последовательность зигзагообразных чисел разумным ответом на вопрос: «Что произойдёт, если мы будем делить, а не умножать в $n!$?» Или генерирующая их компьютерная программа просто оказалась ошибочным алгоритмом? По моему личному мнению, $\frac{1}{n!}$ — более интуитивный ответ, зато $\frac{n!!}{(n - 1)!!}$ — более интересный.

Как сказано выше, если вы настаиваете, что алгоритм деления всегда должен по порядку проходить по списку числителей $n$, на каждом шаге деля число слева на число справа, то имеется всего $n$ возможных результатов, и все они выглядят очень похожими. Более того, само существование зигзагообразной последовательности расширяет наши горизонты. Мы можем сформулировать задачу следующим образом: возьмём множество числителей $\{1 \dots n\}$, выберем его подмножество и обратим все элементы этого подмножества; теперь перемножим все числители, как обратные, так и прямые. Но зигзагообразное решение обеспечивает намного более широкие возможности. Если все числители превратились в обратные им значения, то мы получаем обратный $\frac{1}{n!}$. Если обращённое подмножество пусто, то результатом будет обычный факториал $n!$. А если обращён каждый второй числитель, начиная с $n - 1$, то результатом будет элемент зигзагообразной последовательности.

Например, можно брать обратные значения каждого числа, являющегося простым или степенью простого числа $(2, 3, 4, 5, 7, 8, 9, 11, \dots)$. Это только некоторые из множества возможных вариантов; в сумме здесь есть $2^n$ подмножеств из $n$ элементов. При малых $n$ результаты скачут, но постоянно остаются меньше, чем $1$:

Однако если бы я продолжил этот график для бОльших $n$, он бы взлетел в стратосферу. Степени простых чисел становятся очень разреженными на числовой прямой.
Теперь я задам вопрос. Мы видели вариации факториалов, приближающиеся к нулю при стремлении $n$ к бесконечности, например $1/n!$. Мы видели другие вариации, растущие при увеличении $n$ безгранично, в том числе сам $n!$ и зигзагообразные числа. Существуют ли какие-то разновидности процесса факториалов, сходящиеся к какой-то конечной границе, не являющейся нулём?

В первую очередь мне пришёл в голову такой алгоритм:

function greedy_balance(n) q = 1 while n > 0 q = q > 1 ? q /= n : q *= n n -= 1 end return q
end

Мы циклически перебираем целые значения от $n$ вниз до $1$, вычисляя в процессе текущее произведение/частное $q$. На каждом шаге, если текущее значение $q$ больше $1$, мы делим его на следующий числитель, в противном случае, выполняем умножение. Эта схема реализует своего рода управление обратной связью или поведение поиска цели. Если $q$ становится слишком большим, мы уменьшаем его; если слишком маленьким, мы увеличиваем его. Я предположил, что при стремлении $n$ к бесконечности, $q$ будет сходиться к постоянно сужающемуся интервалу значений рядом с $1$.

Но эксперимент подкинул мне ещё один сюрприз:

Такая пилообразная волна — не совсем то, чего я ожидал. Любопытно, что кривая не симметрична около $1$; отклонения сверху имеют бОльшую амплитуду, чем снизу. Но это искажение больше визуальное, чем математическое. Так как $q$ является частным, расстояние от $1$ до $10$ такое же, как расстояние от $1$ до $\frac{1}{10}$, но в линейном масштабе таким не выглядит. Исправить это можно, составив логарифмический график частного:

Теперь график симметричен, или хотя бы приблизительно таков, и центрирован относительно значения $0$, которое является логарифмом $1$. Но остаётся более серьёзная тайна. Пилообразная волна очень регулярна и имеет период $4$, при этом не показывает признаков сжатия по направлению к ожидаемому ограничивающему значению $\log q = 0$. Численные значения предполагают, что при стремлении $n$ к бесконечности пики кривой сходятся к значению чуть выше $q = \frac{5}{3}$, а минимумы приближаются к значению чуть ниже $q = \frac{3}{5}$. (Соответствующие логарифмы по основанию $10$ примерно равны $\pm0.222$). Мне не удалось разобраться, почему так происходит. Возможно, кто-то сможем объяснить.

Неудача с этим жадным алгоритмом не означает, что мы не сможем делительный факториал, сходящийся к $q = 1$.

Нам даётся множество вещественных чисел, и мы должны разделить их на два множества, сумма которых равна, или как можно ближе к равенству. Если мы будем работать с логарифмами числителей, то эта процедура становится случаем хорошо известной вычислительной задачи под названием «задача разбиения множества чисел». Это подтверждённо сложная задача, но её также называют (PDF) «простейшей сложной задачей».

= 1$" data-tex="inline"/>. Для любого $n$ мы можем обнаружить, что при использовании обратных значений какого-то другого подмножества числителей даёт нам лучшее приближение к <img src="https://habrastorage.org/getpro/habr/formulas/4b4/02e/c5c/4b402ec5c3ceaa72c1fb898b9e82a7b9.svg" alt="$n! Для малых $n$ мы можем решить эту задачу способом перебора: просто рассмотреть все $2^n$ подмножеств и выбрать самое лучшее.

Я вычислил оптимальные разбиения вплоть до $n = 30$, когда выбирать нужно из миллиарда вариантов.

Очевидно, что график становится всё более плоским. Можно использовать тот же метод для принудительного схождения к любому другому значению в интервале от $0$ до $n!$.

Что произойдёт, если мы будем делить, а не умножать в $n!$? И таким образом мы получаем ещё один ответ на вопрос, заданный твитом и начавший наше путешествие. Всё, что нам угодно.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть