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

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

30fbe0e875379d4e82198ed7e6908576.png


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

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

В твите «Библиотеки Ферма» делители поставлены в порядке по убыванию: $n, n-1, n-2, \ldots, 1$. Очевиднее всего будет заменить это на порядок по возрастанию: $1, 2, 3, \ldots, n$. Что произойдёт, если мы зададим факториал деления как $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!$. Однако, изучение ответов двух показанных выше перестановок даёт нам понять, что здесь работает более простой паттерн. Какой бы элемент последовательности не появился первым, он оказывается в числителе большой дроби, а знаменателем оказывается произведение всех других элементов. Поэтому в итоге остаётся всего $n$ различных результатов (если предположить, что мы всегда выполняем операции деления строго слева направо). Для любого целочисленного $k$ в интервале от $1$ до $n$, поставив $k$ в начало очереди, мы создаём делительное $n!$, равное $k$, поделённому на все другие коэффициенты. Можно записать это следующим образом:

$\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!}$ идентичны.
Та-да! Миссия выполнена. Задача решена. Дело сделано. Теперь мы знаем всё, что нам нужно, о делительных факториалах, верно?

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

Вот мой любимый алгоритм для вычисления факториалов в виде программы на 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}$. На самом деле значения так не выглядят, потому что и не собираются сходиться. Судя по показанному ниже графику, последовательность состоит из двух перемежающихся компонентов, каждый из которых, похоже, медленно растёт в сторону бесконечности, а также отклоняется от другого.

e9f03a8df280af6746a7b293829a0fe1.svg


Разбираясь с тем, что же мы здесь наблюдаем, полезно будет изменить тип выходных данных функции 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!!$ как «факториал факториала».

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

В статье 2012 года Генри У. Гулда и Джослин Куэнтенс (увы, находящаяся за paywall) исследуются применения двойных факториалов. Они встречаются гораздо чаще, чем можно подумать. В середине 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}$. Его обнаружил не кто иной, как Сриниваса Рамануджан.

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

$\binom{n}{k} = \frac{n!}{k! (n-k)!}$


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

$\left(\!\binom{n}{k}\!\right) = \frac{n!!}{k!! (n-k)!!}$


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

$\left(\!\binom{n}{1}\!\right) = \left(\!\binom{n}{n - 1}\!\right) = \frac{n!!}{1!! (n-1)!!}$


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

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


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

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

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

ce5a6d5518cc103015a969f3966526c8.svg


Однако если бы я продолжил этот график для бОльших $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$.

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

487ddbe774a4b993cf27a0f852953819.svg


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

069b45b1c9ce52f9608e950349af035b.svg


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

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

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

Для любого $n$ мы можем обнаружить, что при использовании обратных значений какого-то другого подмножества числителей даёт нам лучшее приближение к $n! = 1$. Для малых $n$ мы можем решить эту задачу способом перебора: просто рассмотреть все $2^n$ подмножеств и выбрать самое лучшее.

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

a5858e47c77d107a79d4c905613b0141.svg


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

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

© Habrahabr.ru