Факториал

Произведение чисел от 1 до n

В математике факториал неотрицательного целого числа , обозначаемый как , является произведением всех положительных целых чисел, меньших или равных . Факториал также равен произведению со следующим меньшим факториалом: Например , Значение 0! равно 1, согласно соглашению для пустого произведения . [ ^1] ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ $${\displaystyle {\begin{aligned}n!&=n\times (n-1)\times (n-2)\times (n-3)\times \cdots \times 3\times 2\times 1\\&=n\times (n-1)!\\\end{aligned}}}$$ $${\displaystyle 5!=5\times 4!=5\times 4\times 3\times 2\times 1=120.}$$

Факториалы были обнаружены в нескольких древних культурах, в частности, в индийской математике в канонических трудах джайнской литературы и еврейскими мистиками в талмудической книге Сефер Йецира . Факториальная операция встречается во многих областях математики, в частности, в комбинаторике , где ее наиболее основное применение заключается в подсчете возможных различных последовательностей — перестановок — различных объектов: есть . В математическом анализе факториалы используются в степенных рядах для показательной функции и других функций, а также они имеют приложения в алгебре , теории чисел , теории вероятностей и информатике . ${\displaystyle n}$ ${\displaystyle n!}$

Большая часть математики факториальной функции была разработана, начиная с конца 18 и начала 19 веков. Приближение Стирлинга обеспечивает точное приближение к факториалу больших чисел, показывая, что он растет быстрее, чем экспоненциальный рост . Формула Лежандра описывает показатели степеней простых чисел в разложении факториалов на простые множители и может использоваться для подсчета конечных нулей факториалов. Даниил Бернулли и Леонард Эйлер интерполировали факториальную функцию до непрерывной функции комплексных чисел , за исключением отрицательных целых чисел, (смещенной) гамма-функции .

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

История

Концепция факториалов возникла независимо во многих культурах:

• В индийской математике одно из самых ранних известных описаний факториалов содержится в Ануйогадвара-сутре ^[2] , одном из канонических произведений джайнской литературы , которому присваиваются даты от 300 г. до н. э. до 400 г. н. э. ^[3]. Он отделяет отсортированный и обратный порядок набора элементов от других («смешанных») порядков, оценивая количество смешанных порядков путем вычитания двух из обычной формулы произведения для факториала. Правило произведения для перестановок также было описано джайнским монахом Джинабхадрой в VI веке н. э . ^[2] Индуистские ученые используют факториальные формулы по крайней мере с 1150 года, когда Бхаскара II упомянул факториалы в своей работе «Лилавати » в связи с проблемой того, сколькими способами Вишну мог бы держать свои четыре характерных объекта ( раковину , диск , булаву и цветок лотоса ) в своих четырех руках, а также с аналогичной проблемой для десятирукого бога. ^[4]
• В математике Ближнего Востока, в еврейской мистической книге творения Сефер Йецира , относящейся к талмудическому периоду (200–500 гг. н. э.), перечислены факториалы до 7! как часть исследования количества слов, которые можно образовать из еврейского алфавита . ^{[5] [6]} Факториалы также изучались по схожим причинам арабским грамматистом VIII века Аль-Халилем ибн Ахмадом аль-Фарахиди . ^[5] Арабский математик Ибн аль-Хайтам (также известный как Альхазен, ок. 965 – ок. 1040) был первым, кто сформулировал теорему Уилсона , связывающую факториалы с простыми числами . ^[7]
• В Европе, хотя греческая математика включала некоторую комбинаторику, и Платон , как известно, использовал 5040 (факториал) как население идеального сообщества, отчасти из-за его свойств делимости, ^[8] нет прямых доказательств древнегреческого изучения факториалов. Вместо этого, первая работа по факториалам в Европе была написана еврейскими учеными, такими как Шаббетай Донноло , объясняющими отрывок из Сефер Йецира. ^[9] В 1677 году британский автор Фабиан Стедман описал применение факториалов для изменения звона , музыкального искусства, включающего звон нескольких настроенных колоколов. ^{[10] [11]}

С конца XV ​​века факториалы стали предметом изучения западных математиков. В трактате 1494 года итальянский математик Лука Пачоли вычислил факториалы до 11! в связи с проблемой расстановки обеденных столов. ^[12] Христофор Клавиус обсуждал факториалы в комментарии 1603 года к работе Иоганнеса де Сакробоско , а в 1640-х годах французский полимат Марен Мерсенн опубликовал большие (но не совсем правильные) таблицы факториалов, до 64!, основанные на работе Клавиуса. ^[13] Степенной ряд для показательной функции с обратными факториалами в качестве коэффициентов был впервые сформулирован в 1676 году Исааком Ньютоном в письме Готфриду Вильгельму Лейбницу . ^[14] Другие важные работы ранней европейской математики по факториалам включают обширное освещение в трактате Джона Уоллиса 1685 года , исследование их приближенных значений для больших значений Авраамом де Муавром в 1721 году, письмо Джеймса Стирлинга де Муавру от 1729 года, в котором излагается то, что стало известно как приближение Стирлинга , и работа того же времени Даниила Бернулли и Леонарда Эйлера, формулирующая непрерывное расширение факториальной функции до гамма-функции . ^[15] Адриен-Мари Лежандр включил формулу Лежандра , описывающую показатели при разложении факториалов на простые степени , в текст по теории чисел 1808 года . ^[16] ${\displaystyle n}$

Обозначение для факториалов было введено французским математиком Кристианом Крампом в 1808 году. ^[17] Также использовались многие другие обозначения. Другое более позднее обозначение , в котором аргумент факториала был наполовину заключен в левую и нижнюю стороны прямоугольника, было популярно некоторое время в Британии и Америке, но вышло из употребления, возможно, из-за того, что его было трудно набирать. ^[17] Слово «факториал» (первоначально французское: factorielle ) было впервые использовано в 1800 году Луи Франсуа Антуаном Арбогастом [ ^18] в первой работе по формуле Фаа ди Бруно ^[19], но ссылаясь на более общую концепцию произведений арифметических прогрессий . «Факторами», к которым относится это название, являются члены формулы произведения для факториала ^{[20] .} ${\displaystyle n!}$ ${\displaystyle \vert \!{\underline {\,n}}}$

Определение

Факториальная функция положительного целого числа определяется произведением всех положительных целых чисел, не превышающих ^[1]. Это можно записать более кратко в записи произведения как ^[1]. ${\displaystyle n}$ ${\displaystyle n}$ $${\displaystyle n!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1)\cdot n.}$$ $${\displaystyle n!=\prod _{i=1}^{n}i.}$$

Если эту формулу произведения изменить, чтобы сохранить все, кроме последнего члена, она определит произведение той же формы, для меньшего факториала. Это приводит к рекуррентному соотношению , согласно которому каждое значение функции факториала может быть получено путем умножения предыдущего значения на : ^[21] ${\displaystyle n}$ Например, . $${\displaystyle n!=n\cdot (n-1)!.}$$ ${\displaystyle 5!=5\cdot 4!=5\cdot 24=120}$

Факториал нуля

Факториал числа ${\displaystyle 0}$ равен , ${\displaystyle 1}$ или в символах . Для такого определения есть несколько мотивов: ${\displaystyle 0!=1}$

• Для , определение как произведения включает в себя произведение вообще никаких чисел, и поэтому является примером более широкого соглашения о том, что пустое произведение , произведение без множителей, равно мультипликативному тождеству. ^[22] ${\displaystyle n=0}$ ${\displaystyle n!}$
• Существует ровно одна перестановка нулевых объектов: поскольку переставлять нечего, единственной перестановкой будет ничего не делать. ^[21]
• Это соглашение делает многие тождества в комбинаторике действительными для всех допустимых выборов их параметров. Например, число способов выбрать все элементы из набора является биномиальным коэффициентом тождества, которое будет действительным только при . ^[23] ${\displaystyle n}$ ${\displaystyle n}$ ${\textstyle {\tbinom {n}{n}}={\tfrac {n!}{n!0!}}=1,}$ ${\displaystyle 0!=1}$
• При , рекуррентное соотношение для факториала остается действительным при . Таким образом, при таком соглашении рекурсивное вычисление факториала должно иметь только значение для нуля в качестве базового случая , что упрощает вычисление и позволяет избежать необходимости в дополнительных особых случаях. ^[24] ${\displaystyle 0!=1}$ ${\displaystyle n=1}$
• Настройка позволяет компактно выразить многие формулы, такие как показательная функция , в виде степенного ряда : ^[14] ${\displaystyle 0!=1}$ ${\textstyle e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}.}$
• Этот выбор соответствует гамма-функции , а гамма-функция должна иметь это значение, чтобы быть непрерывной функцией . ^[25] ${\displaystyle 0!=\Gamma (0+1)=1}$

Приложения

Самые ранние применения факториальной функции включают подсчет перестановок : существуют различные способы упорядочивания отдельных объектов в последовательность. ^[26] Факториалы появляются более широко во многих формулах в комбинаторике , чтобы учитывать различные упорядочения объектов. Например, биномиальные коэффициенты подсчитывают комбинации -элементов (подмножества элементов) из набора с элементами и могут быть вычислены из факториалов с использованием формулы ^[27] Числа Стирлинга первого рода суммируются с факториалами и подсчитывают перестановки сгруппированных в подмножества с одинаковым количеством циклов. ^[28] Другое комбинаторное применение заключается в подсчете нарушений , перестановок, которые не оставляют ни один элемент в его исходном положении; число нарушений элементов является ближайшим целым числом к ​​. ^[29] ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$ $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n!/e}$

В алгебре факториалы возникают из биномиальной теоремы , которая использует биномиальные коэффициенты для расширения степеней сумм. ^[30] Они также встречаются в коэффициентах, используемых для связи определенных семейств многочленов друг с другом, например, в тождествах Ньютона для симметричных многочленов . ^[31] Их использование при подсчете перестановок также можно переформулировать алгебраически: факториалы являются порядками конечных симметрических групп . ^[32] В исчислении факториалы встречаются в формуле Фаа ди Бруно для объединения высших производных. ^[19] В математическом анализе факториалы часто появляются в знаменателях степенных рядов , особенно в рядах для показательной функции , ^[14] и в коэффициентах других рядов Тейлора (в частности, рядов тригонометрических и гиперболических функций ), где они сокращают множители, возникающие из -й производной . ^[33] Такое использование факториалов в степенных рядах возвращает нас к аналитической комбинаторике через экспоненциальную производящую функцию , которая для комбинаторного класса с элементами размера определяется как степенной ряд ^[34] $${\displaystyle e^{x}=1+{\frac {x}{1}}+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}+\cdots =\sum _{i=0}^{\infty }{\frac {x^{i}}{i!}},}$$ ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle x^{n}}$ ${\displaystyle n_{i}}$ ${\displaystyle i}$ $${\displaystyle \sum _{i=0}^{\infty }{\frac {x^{i}n_{i}}{i!}}.}$$

В теории чисел наиболее существенным свойством факториалов является делимость на все положительные целые числа вплоть до , более точно описываемая для простых множителей формулой Лежандра . Из этого следует, что произвольно большие простые числа могут быть найдены как простые множители чисел , что приводит к доказательству теоремы Евклида о том, что число простых чисел бесконечно. ^[35] Когда само является простым, оно называется факториальным простым ; ^[36] в связи с этим проблема Брокара , также поставленная Шринивасой Рамануджаном , касается существования квадратных чисел вида . ^[37] Напротив, все числа должны быть составными, что доказывает существование произвольно больших простых промежутков . ^[38] Элементарное доказательство постулата Бертрана о существовании простого числа в любом интервале вида , одного из первых результатов Пауля Эрдёша , было основано на свойствах делимости факториалов. ^{[39] [40]} Факториальная система счисления представляет собой смешанную систему счисления, в которой значения мест каждой цифры являются факториалами. ^[41] ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle n!\pm 1}$ ${\displaystyle n!\pm 1}$ ${\displaystyle n!+1}$ ${\displaystyle n!+2,n!+3,\dots n!+n}$ ${\displaystyle [n,2n]}$

Факториалы широко используются в теории вероятностей , например, в распределении Пуассона ^[42] и в вероятностях случайных перестановок . ^[43] В информатике , помимо появления в анализе поиска методом грубой силы по перестановкам, ^[44] факториалы возникают в нижней границе числа сравнений, необходимых для сравнительной сортировки набора элементов, ^[45] и в анализе цепочечных хэш-таблиц , где распределение ключей на ячейку может быть точно аппроксимировано распределением Пуассона. ^[46] Более того, факториалы естественным образом появляются в формулах из квантовой и статистической физики , где часто рассматриваются все возможные перестановки набора частиц. В статистической механике вычисления энтропии , такие как формула энтропии Больцмана или уравнение Сакура–Тетроде, должны корректировать количество микросостояний путем деления на факториалы чисел каждого типа неразличимых частиц , чтобы избежать парадокса Гиббса . Квантовая физика дает основную причину, по которой эти поправки необходимы. ^[47] ${\displaystyle \log _{2}n!=n\log _{2}n-O(n)}$ ${\displaystyle n}$

Характеристики

Рост и приближение

Сравнение факториала, аппроксимации Стирлинга и более простой аппроксимации в двойном логарифмическом масштабе ${\displaystyle (n/e)^{n}}$

Относительная ошибка в усеченном ряду Стирлинга в зависимости от количества членов

Как функция от , ${\displaystyle n}$ факториал имеет более быстрый, чем экспоненциальный рост , но растет медленнее, чем двойная экспоненциальная функция . ^[48] Его скорость роста похожа на , ${\displaystyle n^{n}}$ но медленнее на экспоненциальный множитель. Один из способов приближения к этому результату — взять натуральный логарифм факториала, что превращает его формулу произведения в сумму, а затем оценить сумму интегралом: Возведение результата в степень (и игнорирование пренебрежимо малого члена) приближается к . ^[49] Более тщательное ограничение суммы как сверху, так и снизу интегралом с использованием правила трапеций показывает, что эта оценка нуждается в поправочном коэффициенте, пропорциональном . Константу пропорциональности для этой поправки можно найти из произведения Уоллиса , которое выражается как предельное отношение факториалов и степеней двойки. Результатом этих поправок является приближение Стирлинга : ^[50] Здесь символ означает, что при стремлении к бесконечности отношение между левой и правой сторонами приближается к единице в пределе . Формула Стирлинга дает первый член асимптотического ряда , который становится еще точнее при увеличении числа членов: ^[51] Альтернативная версия использует только нечетные показатели степеней в поправочных членах: ^[51] Было также разработано много других вариаций этих формул Шринивасой Рамануджаном , Биллом Госпером и другими. ^[51] $${\displaystyle \ln n!=\sum _{x=1}^{n}\ln x\approx \int _{1}^{n}\ln x\,dx=n\ln n-n+1.}$$ ${\displaystyle +1}$ ${\displaystyle n!}$ ${\displaystyle (n/e)^{n}}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle \pi }$ $${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.}$$ ${\displaystyle \sim }$ ${\displaystyle n}$ $${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}-{\frac {139}{51840n^{3}}}-{\frac {571}{2488320n^{4}}}+\cdots \right).}$$ $${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({\frac {1}{12n}}-{\frac {1}{360n^{3}}}+{\frac {1}{1260n^{5}}}-{\frac {1}{1680n^{7}}}+\cdots \right).}$$

Двоичный логарифм факториала, используемый для анализа сортировки сравнения , может быть очень точно оценен с помощью аппроксимации Стирлинга. В приведенной ниже формуле термин вызывает нотацию большого О. [ ^45] ${\displaystyle O(1)}$ $${\displaystyle \log _{2}n!=n\log _{2}n-(\log _{2}e)n+{\frac {1}{2}}\log _{2}n+O(1).}$$

Делимость и цифры

Формула произведения для факториала подразумевает, что делится на все простые числа , которые не превышают , и ни на какие большие простые числа. ^[52] Более точная информация о его делимости дается формулой Лежандра , которая дает показатель степени каждого простого числа в разложении на простые множители как ^{[53] [54]} Здесь обозначает сумму цифр основания , а показатель степени, заданный этой формулой , также может быть интерпретирован в высшей математике как p -адическое оценивание факториала. ^[54] Применение формулы Лежандра к формуле произведения для биномиальных коэффициентов дает теорему Куммера , аналогичный результат для показателя степени каждого простого числа в разложении биномиального коэффициента. ^[55] Группировка простых множителей факториала в простые степени различными способами дает мультипликативные разбиения факториалов . ^[56] ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n!}$ $${\displaystyle \sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ={\frac {n-s_{p}(n)}{p-1}}.}$$ ${\displaystyle s_{p}(n)}$ ${\displaystyle p}$ ${\displaystyle n}$

Особый случай формулы Лежандра для дает количество конечных нулей в десятичном представлении факториалов. ^[57] Согласно этой формуле, количество нулей можно получить, вычитая цифры с основанием 5 из и разделив результат на четыре. ^[58] Формула Лежандра подразумевает, что показатель степени простого числа всегда больше показателя степени для , поэтому каждый множитель пять можно объединить с множителем два, чтобы получить один из этих конечных нулей. ^[57] Начальные цифры факториалов распределены в соответствии с законом Бенфорда . ^[59] Каждая последовательность цифр в любой системе счисления является последовательностью начальных цифр некоторого факториала в этой системе счисления. ^[60] ${\displaystyle p=5}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p=2}$ ${\displaystyle p=5}$

Другой результат о делимости факториалов, теорема Уилсона , утверждает, что делится на тогда и только тогда, когда является простым числом . ^[52] Для любого заданного целого числа функция Кемпнера числа определяется наименьшим числом , на которое делится . ^[61] Для почти всех чисел (за исключением подмножества исключений с нулевой асимптотической плотностью ) оно совпадает с наибольшим простым множителем числа . ^[62] ${\displaystyle (n-1)!+1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle n!}$ ${\displaystyle x}$

Произведение двух факториалов, , всегда делит нацело . ^[63] Существует бесконечно много факториалов, которые равны произведению других факториалов: если само является любым произведением факториалов, то равно тому же самому произведению, умноженному на еще один факториал, . Единственными известными примерами факториалов, которые являются произведениями других факториалов, но не имеют этой «тривиальной» формы, являются , , и . ^[64] Из гипотезы abc следует , что существует только конечное число нетривиальных примеров. ^[65] ${\displaystyle m!\cdot n!}$ ${\displaystyle (m+n)!}$ ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle (n-1)!}$ ${\displaystyle 9!=7!\cdot 3!\cdot 3!\cdot 2!}$ ${\displaystyle 10!=7!\cdot 6!=7!\cdot 5!\cdot 3!}$ ${\displaystyle 16!=14!\cdot 5!\cdot 2!}$

Наибольший общий делитель значений примитивного многочлена степени над целыми числами делит нацело . ^[63] ${\displaystyle d}$ ${\displaystyle d!}$

Непрерывная интерполяция и нецелочисленное обобщение

Гамма-функция (сдвинутая на одну единицу влево для соответствия факториалам) непрерывно интерполирует факториал до нецелых значений.

Абсолютные значения комплексной гамма-функции, показывающие полюса при неположительных целых числах

Существует бесконечно много способов расширить факториалы до непрерывной функции . ^[66] Наиболее широко используемый из них ^[67] использует гамма-функцию , которая может быть определена для положительных действительных чисел как интеграл Полученная функция связана с факториалом неотрицательного целого числа уравнением , которое может быть использовано в качестве определения факториала для нецелых аргументов. При всех значениях, для которых определены и , гамма-функция подчиняется функциональному уравнению, обобщающему рекуррентное соотношение для факториалов. ^[66] $${\displaystyle \Gamma (z)=\int _{0}^{\infty }x^{z-1}e^{-x}\,dx.}$$ ${\displaystyle n}$ $${\displaystyle n!=\Gamma (n+1),}$$ ${\displaystyle x}$ ${\displaystyle \Gamma (x)}$ ${\displaystyle \Gamma (x-1)}$ $${\displaystyle \Gamma (n)=(n-1)\Gamma (n-1),}$$

Тот же интеграл сходится в более общем случае для любого комплексного числа , действительная часть которого положительна. Его можно распространить на нецелые точки в остальной части комплексной плоскости , решив для формулы отражения Эйлера . Однако эта формула не может быть использована для целых чисел, поскольку для них этот член произведет деление на ноль . Результатом этого процесса расширения является аналитическая функция , аналитическое продолжение интегральной формулы для гамма-функции. Она имеет ненулевое значение для всех комплексных чисел, за исключением неположительных целых чисел, где она имеет простые полюса . Соответственно, это дает определение для факториала для всех комплексных чисел, кроме отрицательных целых чисел. ^[67] Одно свойство гамма-функции, отличающее ее от других непрерывных интерполяций факториалов, дается теоремой Бора–Моллерупа , которая гласит, что гамма-функция (смещенная на единицу) является единственной логарифмически выпуклой функцией для положительных действительных чисел, которая интерполирует факториалы и подчиняется тому же функциональному уравнению. Связанная теорема единственности Гельмута Виландта утверждает, что комплексная гамма-функция и ее скалярные кратные являются единственными голоморфными функциями на положительной комплексной полуплоскости, которые подчиняются функциональному уравнению и остаются ограниченными для комплексных чисел с действительной частью между 1 и 2. ^[68] ${\displaystyle z}$ $${\displaystyle \Gamma (z)\Gamma (1-z)={\frac {\pi }{\sin \pi z}}.}$$ ${\displaystyle \sin \pi z}$

Другие комплексные функции, которые интерполируют значения факториала, включают гамма-функцию Адамара , которая является целой функцией по всем комплексным числам, включая неположительные целые числа. ^{[69] [70]} В p -адических числах невозможно непрерывно интерполировать факториальную функцию напрямую, потому что факториалы больших целых чисел (плотное подмножество p -адических чисел) сходятся к нулю согласно формуле Лежандра, заставляя любую непрерывную функцию, близкую к их значениям, везде быть равной нулю. Вместо этого p -адическая гамма-функция обеспечивает непрерывную интерполяцию модифицированной формы факториала, опуская множители в факториале, которые делятся на p . ^[71]

Функция дигамма является логарифмической производной гамма-функции. Так же, как гамма-функция обеспечивает непрерывную интерполяцию факториалов, смещенных на единицу, функция дигамма обеспечивает непрерывную интерполяцию гармонических чисел , смещенных на константу Эйлера–Маскерони . ^[72]

Вычисление

TI SR-50A , калькулятор 1975 года с клавишей факториала (третий ряд, в центре справа)

Функция факториала является распространенной функцией в научных калькуляторах . ^[73] Она также включена в библиотеки научного программирования, такие как модуль математических функций Python ^[74] и библиотека Boost C++ . ^[75] Если эффективность не важна, вычисление факториалов тривиально: просто последовательно умножьте переменную, инициализированную с ${\displaystyle 1}$ помощью целых чисел до . ${\displaystyle n}$ Простота этого вычисления делает его распространенным примером использования различных стилей и методов компьютерного программирования. ^[76]

Вычисление может быть выражено в псевдокоде с использованием итерации ^[77] как ${\displaystyle n!}$

определить факториал( n ): f  := 1 для i  := 1, 2, 3, ..., n : f  := f * i вернуть f

или с использованием рекурсии ^[78] на основе ее рекуррентного соотношения как

определить факториал( n ): если ( n = 0) вернуть 1 вернуть n * факториал( n − 1)

Другие методы, подходящие для его вычисления, включают мемоизацию , ^[79] динамическое программирование , ^[80] и функциональное программирование . ^[81] Вычислительную сложность этих алгоритмов можно проанализировать с помощью модели вычислений с произвольной стоимостью единицы , в которой каждая арифметическая операция занимает постоянное время, а каждое число использует постоянный объем дискового пространства. В этой модели эти методы могут вычисляться за время , а итеративная версия использует пространство . Если только рекурсивная версия не оптимизирована для хвостовой рекурсии , она занимает линейное пространство для хранения своего стека вызовов . ^[82] Однако эта модель вычисления подходит только тогда, когда достаточно мала, чтобы уместиться в машинное слово . ^[83] Значения 12! и 20! являются наибольшими факториалами, которые могут быть сохранены в 32-битных ^[84] и 64-битных целых числах соответственно . ^[85] Плавающая точка может представлять большие факториалы, но приблизительно, а не точно, и все равно будет переполняться для факториалов, больших, чем . ^[84] ${\displaystyle n!}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$ ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle 170!}$

Точное вычисление больших факториалов включает арифметику произвольной точности из-за быстрого роста и переполнения целых чисел . Время вычисления можно проанализировать как функцию количества цифр или бит в результате. ^[85] По формуле Стирлинга имеет бит. ^[86] Алгоритм Шёнхаге–Штрассена может производить -битное произведение за время , и известны более быстрые алгоритмы умножения, требующие времени . ^[87] Однако вычисление факториала включает в себя повторяющиеся произведения, а не одно умножение, поэтому эти временные ограничения не применяются напрямую. В этой ситуации вычисление путем умножения чисел от 1 до последовательно неэффективно, поскольку оно включает в себя умножения, постоянная доля которых занимает время каждое, что дает общее время . Лучшим подходом является выполнение умножений как алгоритма «разделяй и властвуй», который умножает последовательность чисел, разбивая ее на две подпоследовательности чисел, умножает каждую подпоследовательность и объединяет результаты одним последним умножением. Этот подход к факториалу занимает целое время : один логарифм исходит из числа бит в факториале, второй исходит из алгоритма умножения, а третий исходит из принципа «разделяй и властвуй». ^[88] ${\displaystyle n!}$ ${\displaystyle b=O(n\log n)}$ ${\displaystyle b}$ ${\displaystyle O(b\log b\log \log b)}$ ${\displaystyle O(b\log b)}$ ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle O(n^{2}\log ^{2}n)}$ ${\displaystyle i}$ ${\displaystyle i/2}$ ${\displaystyle O(n\log ^{3}n)}$

Еще большую эффективность можно получить, вычислив n ! из его разложения на простые множители, основываясь на принципе, что возведение в степень путем возведения в квадрат быстрее, чем разложение показателя в произведение. ^{[86] [89]} Алгоритм для этого, разработанный Арнольдом Шёнхаге, начинается с поиска списка простых чисел до , ${\displaystyle n}$ например, с использованием решета Эратосфена , и использует формулу Лежандра для вычисления показателя для каждого простого числа. Затем он вычисляет произведение степеней простых чисел с этими показателями, используя рекурсивный алгоритм, следующим образом:

• Используйте метод «разделяй и властвуй», чтобы вычислить произведение простых чисел, показатели степеней которых нечетны.
• Разделите все показатели степеней на два (округляя до целого числа), рекурсивно вычислите произведение простых степеней с этими меньшими показателями и возведите результат в квадрат.
• Перемножьте результаты двух предыдущих шагов.

Произведение всех простых чисел до является -битным числом по теореме о простых числах , поэтому время для первого шага равно , с одним логарифмом, полученным из алгоритма «разделяй и властвуй», и другим, полученным из алгоритма умножения. В рекурсивных вызовах алгоритма теорема о простых числах может быть снова вызвана для доказательства того, что количество бит в соответствующих произведениях уменьшается на постоянный множитель на каждом уровне рекурсии, поэтому общее время для этих шагов на всех уровнях рекурсии складывается в геометрической прогрессии с . Время для возведения в квадрат на втором шаге и умножения на третьем шаге снова равно , поскольку каждое из них является одним умножением числа на биты. Опять же, на каждом уровне рекурсии вовлеченные числа имеют постоянную долю от количества бит (потому что в противном случае многократное возведение их в квадрат дало бы слишком большой конечный результат), поэтому снова количество времени для этих шагов в рекурсивных вызовах складывается в геометрической прогрессии с . Следовательно, весь алгоритм занимает время , пропорциональное одному умножению с тем же количеством бит в результате. ^[89] ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n\log ^{2}n)}$ ${\displaystyle O(n\log ^{2}n)}$

Связанные последовательности и функции

Несколько других целочисленных последовательностей похожи на факториалы или связаны с ними:

Переменный факториал

Альтернирующий факториал — это абсолютное значение альтернирующей суммы первых факториалов, . Они в основном изучались в связи с их простотой; только конечное число из них может быть простым, но полный список простых чисел этой формы неизвестен. ^[90] ${\displaystyle n}$ ${\textstyle \sum _{i=1}^{n}(-1)^{n-i}i!}$

Факториал Бхаргавы

Факториалы Бхаргавы представляют собой семейство целочисленных последовательностей, определенных Манджулом Бхаргавой , обладающих аналогичными факториалам теоретико-числовыми свойствами, включая сами факториалы как особый случай. ^[63]

Двойной факториал

Произведение всех нечетных целых чисел до некоторого нечетного положительного целого числа ${\displaystyle n}$ называется двойным факториалом числа ${\displaystyle n}$ и обозначается как . ^[91] То есть, например, 9!! = 1 × 3 × 5 × 7 × 9 = 945 . Двойные факториалы используются в тригонометрических интегралах , ^[92] в выражениях для гамма-функции в полуцелых числах и объемах гиперсфер , ^[93] и при подсчете бинарных деревьев и совершенных паросочетаний . ^{[91] [94]} ${\displaystyle n!!}$ $${\displaystyle (2k-1)!!=\prod _{i=1}^{k}(2i-1)={\frac {(2k)!}{2^{k}k!}}.}$$

Экспоненциальный факториал

Так же, как треугольные числа суммируют числа от до , а факториалы берут их произведение, показательный факториал возводит в степень. Показательный факториал определяется рекурсивно как . Например, показательный факториал числа 4 равен Эти числа растут гораздо быстрее, чем обычные факториалы. ^[95] ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle a_{0}=1,\ a_{n}=n^{a_{n-1}}}$ $${\displaystyle 4^{3^{2^{1}}}=262144.}$$

Падающий факториал

Обозначения или иногда используются для представления произведения целых чисел, включая и до , равного . Это также известно как падающий факториал или обратный факториал, и обозначение является символом Похгаммера. ^[96] Падающие факториалы подсчитывают количество различных последовательностей отдельных элементов, которые могут быть извлечены из вселенной элементов. ^[97] Они встречаются как коэффициенты в высших производных полиномов, ^[98] и в факториальных моментах случайных величин . ^[99] ${\displaystyle (x)_{n}}$ ${\displaystyle x^{\underline {n}}}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle x!/(x-n)!}$ ${\displaystyle (x)_{n}}$ ${\displaystyle n}$ ${\displaystyle x}$

Гиперфакториалы

Гиперфакториал есть произведение . Эти числа образуют дискриминанты полиномов Эрмита . ^[100] Они могут быть непрерывно интерполированы с помощью K-функции , [ 101 ^] и подчиняются аналогам формулы Стирлинга ^[102] и теоремы Вильсона. ^[103] ${\displaystyle n}$ ${\displaystyle 1^{1}\cdot 2^{2}\cdots n^{n}}$

Числа Джордана–Полиа

Числа Жордана–Полиа являются произведениями факториалов, допускающими повторения. Каждое дерево имеет группу симметрии , число симметрий которой является числом Жордана–Полиа, и каждое число Жордана–Полиа подсчитывает симметрии некоторого дерева. ^[104]

Первобытный

Праймориал — это произведение простых чисел, меньших или равных ; эта конструкция придает им некоторые свойства делимости, похожие на факториалы, ^[36] но в отличие от факториалов они являются бесквадратными . ^[105] Как и в случае с факториальными простыми числами , исследователи изучали праймориальные простые числа . ^[36] ${\displaystyle n\#}$ ${\displaystyle n}$ ${\displaystyle n!\pm 1}$ ${\displaystyle n\#\pm 1}$

Субфакторный

Субфакториал дает число расстройств набора объектов. Иногда он обозначается , и равен ближайшему целому числу к . ^[29] ${\displaystyle n}$ ${\displaystyle !n}$ ${\displaystyle n!/e}$

Суперфакториальный

Суперфакториал является произведением первых факториалов. Суперфакториалы непрерывно интерполируются функцией Барнса G. ^[106 ] ${\displaystyle n}$ ${\displaystyle n}$

Ссылки

1. Грэм, Рональд Л .; Кнут, Дональд Э .; Паташник, Орен (1988). Конкретная математика . Ридинг, Массачусетс: Аддисон-Уэсли. п. 111. ИСБН 0-201-14236-8.
2. Datta, Bibhutibhusan ; Singh, Awadhesh Narayan (2019). «Использование перестановок и комбинаций в Индии». В Kolachana, Aditya; Mahesh, K.; Ramasubramanian, K. (ред.). Исследования по индийской математике и астрономии: избранные статьи Kripa Shankar Shukla . Источники и исследования по истории математики и физических наук. Springer Singapore. стр. 356–376. doi :10.1007/978-981-13-7326-8_18. ISBN 978-981-13-7325-1. S2CID  191141516.. Переработано К. С. Шуклой из статьи в Indian Journal of History of Science 27 (3): 231–249, 1992, MR 1189487. См. стр. 363.
3. Джадхав, Дипак (август 2021 г.). «Джайнские мысли о единстве, а не о числе». История науки в Южной Азии . 9. Библиотеки Альбертского университета: 209–231. doi : 10.18732/hssa67 . S2CID  238656716.. См. обсуждение датирования на стр. 211.
4. Биггс, Норман Л. (май 1979). «Корни комбинаторики». Historia Mathematica . 6 (2): 109–136. doi :10.1016/0315-0860(79)90074-0. MR  0530622.
5. Katz, Victor J. (июнь 1994). «Этноматематика в классе». Для изучения математики . 14 (2): 26–30. JSTOR  40248112.
6. Сефер Йецира в Викитека, Глава IV, Раздел 4
7. Рашед, Рошди (1980). «Ибн аль-Хайтам и теория Вильсона». Архив истории точных наук (на французском). 22 (4): 305–321. doi :10.1007/BF00717654. MR  0595903. S2CID  120885025.
8. Ачерби, Ф. (2003). «На плечах Гиппарха: переоценка древнегреческой комбинаторики». Архив истории точных наук . 57 (6): 465–502. doi :10.1007/s00407-003-0067-0. JSTOR  41134173. MR  2004966. S2CID  122758966.
9. Katz, Victor J. (2013). "Глава 4: Еврейская комбинаторика". В Wilson, Robin; Watkins, John J. (ред.). Комбинаторика: Древняя и современная . Oxford University Press . стр. 109–121. ISBN 978-0-19-965659-2.См. стр. 111.
10. Хант, Кэтрин (май 2018 г.). «Искусство изменений: колокольный звон, анаграммы и культура комбинирования в Англии семнадцатого века» (PDF) . Журнал исследований Средневековья и раннего Нового времени . 48 (2): 387–412. doi :10.1215/10829636-4403136.
11. Стедман, Фабиан (1677). Campanalogia . Лондон. С. 6–9. Издателем указан «WS», которым, возможно, был Уильям Смит, возможно, действовавший в качестве агента Общества студенческой молодежи , которому и адресовано «Посвящение».
12. Knobloch, Eberhard (2013). "Глава 5: Ренессансная комбинаторика". В Wilson, Robin; Watkins, John J. (ред.). Комбинаторика: Древняя и современная . Oxford University Press . стр. 123–145. ISBN 978-0-19-965659-2. См. стр. 126.
13. Кноблох 2013, стр. 130–133.
14. Эббингауз, Х.-Д. ; Гермес, Х .; Хирцебрух, Ф .; Кочер, М .; Майнцер, К. ; Нойкирх, Дж. ; Престель, А.; Реммерт, Р. (1990). Числа. Тексты для аспирантов по математике. Том. 123. Нью-Йорк: Springer-Verlag. п. 131. дои : 10.1007/978-1-4612-1005-4. ISBN 0-387-97202-1. МР  1066206.
15. Дутка, Жак (1991). «Ранняя история функции факториала». Архив истории точных наук . 43 (3): 225–249. doi :10.1007/BF00389433. JSTOR  41133918. MR  1171521. S2CID  122237769.
16. Диксон, Леонард Э. (1919). «Глава IX: Делимость факториалов и мультиномиальных коэффициентов». История теории чисел . Т. 1. Институт Карнеги в Вашингтоне. С. 263–278.См. в частности стр. 263.
17. Cajori, Florian (1929). «448–449. Факториал «n»». История математических обозначений, том II: обозначения, используемые в основном в высшей математике . Издательская компания Open Court. стр. 71–77.
18. Миллер, Джефф. «Самые ранние известные применения некоторых слов математики (F)». Архив истории математики MacTutor . Университет Сент-Эндрюс.
19. Крейк, Алекс Д.Д. (2005). «Предыстория формулы Фаа ди Бруно». Американский математический ежемесячник . 112 (2): 119–130. дои : 10.1080/00029890.2005.11920176. JSTOR  30037410. MR  2121322. S2CID  45380805.
20. Арбогаст, Луи Франсуа Антуан (1800). Du Calcul des Dérivations (на французском языке). Страсбург: L'imprimerie de Levrault, frères. стр. 364–365.
21. Hamkins, Joel David (2020). Доказательство и искусство математики. Кембридж, Массачусетс: MIT Press. стр. 50. ISBN 978-0-262-53979-1. МР  4205951.
22. Дорф, Ричард С. (2003). "Факториалы". CRC Handbook of Engineering Tables . CRC Press. стр. 5-5. ISBN 978-0-203-00922-2.
23. Гольденберг, Э. Пол; Картер, Синтия Дж. (октябрь 2017 г.). «Студент спрашивает о (−5)!». Учитель математики . 111 (2): 104–110. doi : 10.5951/учитель математики.111.2.0104. JSTOR  10.5951/учитель математики.111.2.0104.
24. Хаберман, Брурия; Авербух, Хаим (2002). «Случай базовых случаев: почему их так трудно распознать? Трудности студентов с рекурсией». В Caspersen, Michael E.; Joyce, Daniel T.; Goelman, Don; Utting, Ian (ред.). Труды 7-й ежегодной конференции SIGCSE по инновациям и технологиям в образовании в области компьютерных наук, ITiCSE 2002, Орхус, Дания, 24–28 июня 2002 г. Ассоциация вычислительной техники. стр. 84–88. doi :10.1145/544414.544441.
25. Фаррелл, Орин Дж.; Росс, Бертрам (1971). Решенные задачи анализа: в применении к гамма-, бета-, легандровым и бесселевым функциям. Dover Books on Mathematics. Courier Corporation. стр. 10. ISBN 978-0-486-78308-6.
26. Конвей, Джон Х .; Гай, Ричард (1998). «Факториальные числа». Книга чисел . Springer Science & Business Media. стр. 55–56. ISBN 978-0-387-97993-9.
27. Грэм, Кнут и Паташник 1988, стр. 156.
28. Риордан, Джон (1958). Введение в комбинаторный анализ. Wiley Publications in Mathematical Statistics. Chapman & Hall. стр. 76. ISBN 9781400854332. МР  0096594.
29. Грэм, Кнут и Паташник 1988, стр. 195.
30. Грэм, Кнут и Паташник 1988, стр. 162.
31. Рандич, Милан (1987). «О вычислении характеристического многочлена с помощью теории симметричных функций». Журнал математической химии . 1 (1): 145–152. doi :10.1007/BF01205340. MR  0895533. S2CID  121752631.
32. Хилл, Виктор Э. (2000). "8.1 Предложение: Симметрическая группа Sn". Группы и характеры . Чапман и Холл. стр. 70. ISBN 978-1-351-44381-4. МР  1739394.
33. Кристенсен, Ким; Молони, Николас Р. (2005). "Приложение A: разложение Тейлора". Сложность и критичность . Тексты по продвинутой физике. Том 1. Imperial College Press. стр. 341. ISBN 978-1-86094-504-5.
34. Wilf, Herbert S. (2006). generationfunctionology (3-е изд.). Уэллсли, Массачусетс: AK Peters. стр. 22. ISBN 978-1-56881-279-3. МР  2172781.
35. Оре, Эйстейн (1948). Теория чисел и ее история. Нью-Йорк: McGraw-Hill. С. 66. ISBN 9780486656205. МР  0026059.
36. Колдуэлл, Крис К.; Галло, Ив (2002). «О простоте n ! ± 1 {\displaystyle n!\pm 1} и 2 × 3 × 5 × ⋯ × p ± 1 {\displaystyle 2\times 3\times 5\times \dots \times p\pm 1}». Математика вычислений . 71 (237): 441–448. doi : 10.1090/S0025-5718-01-01315-1 . MR  1863013.
37. Гай, Ричард К. (2004). "D25: Уравнения с факториалом ". Нерешенные проблемы теории чисел . Задачники по математике. Т. 1 (3-е изд.). Нью-Йорк: Springer-Verlag. С. 301–302. doi :10.1007/978-0-387-26677-0. ISBN ${\displaystyle n}$ 0-387-20860-7. МР  2076335.
38. Нил, Вики (2017). Закрытие разрыва: поиски понимания простых чисел. Oxford University Press. С. 146–147. ISBN 978-0-19-878828-7.
39. Эрдеш, Пал (1932). "Beweis eines Satzes von Tschebyschef" [Доказательство теоремы Чебышева] (PDF) . Акта Литт. наук. Сегед (на немецком языке). 5 : 194–198. Збл  0004.10103.
40. Chvátal, Vašek (2021). "1.5: доказательство постулата Бертрана Эрдёшем". Дискретные математические чары Пола Эрдёша: простое введение . Кембридж, Англия: Cambridge University Press. стр. 7–10. doi : 10.1017/9781108912181. ISBN 978-1-108-83183-3. MR  4282416. S2CID  242637862.
41. Френкель, Авиезри С. (1985). «Системы исчисления». The American Mathematical Monthly . 92 (2): 105–114. doi :10.1080/00029890.1985.11971550. JSTOR  2322638. MR  0777556.
42. Питман, Джим (1993). "3.5: Распределение Пуассона". Вероятность . Нью-Йорк: Springer. С. 222–236. doi :10.1007/978-1-4612-4374-8. ISBN 978-0-387-94594-1.
43. Питман 1993, стр. 153.
44. Кляйнберг, Джон ; Тардос, Ева (2006). Алгоритм проектирования . Аддисон-Уэсли. п. 55.
45. Knuth, Donald E. (1998). Искусство программирования, том 3: Сортировка и поиск (2-е изд.). Addison-Wesley. стр. 182. ISBN 978-0-321-63578-5.
46. Седжвик, Роберт ; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Эддисон-Уэсли. стр. 466. ISBN 978-0-13-276256-4.
47. Кардар, Мехран (2007). Статистическая физика частиц . Издательство Кембриджского университета . С. 107–110, 181–184. ISBN 978-0-521-87342-0. OCLC  860391091.
48. Кэмерон, Питер Дж. (1994). "2.4: Порядки величин". Комбинаторика: темы, методы, алгоритмы . Cambridge University Press. стр. 12–14. ISBN 978-0-521-45133-8.
49. Магнус, Роберт (2020). "11.10: Приближение Стирлинга". Фундаментальный математический анализ . Springer Undergraduate Mathematics Series. Cham: Springer. стр. 391. doi :10.1007/978-3-030-46321-2. ISBN 978-3-030-46321-2. MR  4178171. S2CID  226465639.
50. Палмер, Эдгар М. (1985). "Приложение II: Формула Стирлинга". Графическая эволюция: Введение в теорию случайных графов . Серия Wiley-Interscience по дискретной математике. Чичестер: John Wiley & Sons. стр. 127–128. ISBN 0-471-81577-2. МР  0795795.
51. Chen, Chao-Ping; Lin, Long (2012). «Замечания об асимптотических разложениях для гамма-функции». Applied Mathematics Letters . 25 (12): 2322–2326. doi : 10.1016/j.aml.2012.06.025 . MR  2967837.
52. Beiler, Albert H. (1966). Recreations in the Theory of Numbers: The Queen of Mathematics Entertainments. Серия Dover Recreational Math (2-е изд.). Courier Corporation. стр. 49. ISBN 978-0-486-21096-4.
53. Chvátal 2021. «1.4: Формула Лежандра». стр. 6–7.
54. Роберт, Ален М. (2000). "3.1: -адическое оценивание факториала". Курс -адического анализа . Graduate Texts in Mathematics . Vol. 198. Нью-Йорк: Springer-Verlag. pp. 241–242. doi :10.1007/978-1-4757-3254-2. ISBN ${\displaystyle p}$ ${\displaystyle p}$ 0-387-98669-3. МР  1760253.
55. Пейтген, Хайнц-Отто ; Юргенс, Хартмут ; Саупе, Дитмар (2004). «Результат Куммера и личность Лежандра». Хаос и фракталы: новые рубежи науки . Нью-Йорк: Спрингер. стр. 399–400. дои : 10.1007/b97624. ISBN 978-1-4684-9396-2.
56. Аллади, Кришнасвами ; Гринстед, Чарльз (1977). «О разложении n! на простые степени». Журнал теории чисел . 9 (4): 452–458. doi : 10.1016/0022-314x(77)90006-3 .
57. Koshy, Thomas (2007). "Пример 3.12". Элементарная теория чисел с приложениями (2-е изд.). Elsevier. стр. 178. ISBN 978-0-08-054709-1.
58. Слоан, Н. Дж. А. (ред.). "Последовательность A027868 (Количество конечных нулей в n!; наибольшая степень 5, делящая n!)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
59. Диаконис, Перси (1977). «Распределение ведущих цифр и равномерное распределение по модулю 1». Annals of Probability . 5 (1): 72–81. doi : 10.1214/aop/1176995891 . MR  0422186.
60. Bird, RS (1972). «Целые числа с заданными начальными цифрами». The American Mathematical Monthly . 79 (4): 367–370. doi :10.1080/00029890.1972.11993051. JSTOR  2978087. MR  0302553.
61. Кемпнер, А. Дж. (1918). «Miscellanea». The American Mathematical Monthly . 25 (5): 201–210. doi :10.2307/2972639. JSTOR  2972639.
62. Эрдёш, Пол ; Кастанас, Илиас (1994). «Наименьший факториал, кратный n (решение задачи 6674)» (PDF) . The American Mathematical Monthly . 101 : 179. doi :10.2307/2324376. JSTOR  2324376..
63. Бхаргава, Манджул (2000). «Факториал и обобщения». Американский математический ежемесячник . 107 (9): 783–799. CiteSeerX 10.1.1.585.2265 . дои : 10.2307/2695734. JSTOR  2695734. 
64. Гай 2004. «B23: Равные произведения факториалов». стр. 123.
65. Лука, Флориан (2007). «О факториалах, которые являются произведениями факториалов». Математические труды Кембриджского философского общества . 143 (3): 533–542. Bibcode :2007MPCPS.143..533L. doi :10.1017/S0305004107000308. MR  2373957. S2CID  120875316.
66. Davis, Philip J. (1959). «Интеграл Леонарда Эйлера: исторический профиль гамма-функции». The American Mathematical Monthly . 66 (10): 849–869. doi :10.1080/00029890.1959.11989422. JSTOR  2309786. MR  0106810. Архивировано из оригинала 01.01.2023 . Получено 20.12.2021 .
67. Борвейн, Джонатан М. ; Корлесс, Роберт М. (2018). «Гамма и факториал в ежемесячном журнале ». The American Mathematical Monthly . 125 (5): 400–424. arXiv : 1703.05349 . doi :10.1080/00029890.2018.1420983. MR  3785875. S2CID  119324101.
68. Реммерт, Рейнхольд (1996). «Теорема Виландта о -функции » . The American Mathematical Monthly . 103 (3): 214–220. doi :10.1080/00029890.1996.12004726. JSTOR  2975370. MR  1376175. ${\displaystyle \Gamma }$
69. Адамар, Дж. (1968) [1894]. «Sur l'expression du produit 1·2·3· · · ·(n−1) по всей функции» (PDF) . Œuvres de Jacques Adamard (на французском языке). Париж: Национальный центр научных исследований.
70. Альцер, Хорст (2009). «Супераддитивное свойство гамма-функции Адамара». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 79 (1): 11–23. дои : 10.1007/s12188-008-0009-5. MR  2541340. S2CID  123691692.
71. Роберт 2000. «7.1: Гамма-функция ». С. 366–385. ${\displaystyle \Gamma _{p}}$
72. Росс, Бертрам (1978). «Пси-функция». Mathematics Magazine . 51 (3): 176–179. doi :10.1080/0025570X.1978.11976704. JSTOR  2689999. MR  1572267.
73. Brase, Charles Henry; Brase, Corrinne Pellillo (2014). Понятная статистика: концепции и методы (11-е изд.). Cengage Learning. стр. 182. ISBN 978-1-305-14290-9.
74. "math — Математические функции". Документация Python 3: Стандартная библиотека Python . Получено 21.12.2021 .
75. "Factorial". Документация Boost 1.78.0: Math Special Functions . Получено 21.12.2021 .
76. Addis, Tom; Addis, Jan (2009). Программы рисования: теория и практика схемотехнического функционального программирования. Springer. стр. 149–150. ISBN 978-1-84882-618-2.
77. Чепмен, Стивен Дж. (2019). «Пример 5.2: Факториальная функция». Программирование MATLAB для инженеров (6-е изд.). Cengage Learning. стр. 215. ISBN 978-0-357-03052-3.
78. Эй, Тони; Папай, Дьюри (2014). Вычислительная вселенная: путешествие через революцию. Cambridge University Press. стр. 64. ISBN 9781316123225.
79. Болбоака, Александру (2019). Практическое функциональное программирование на C++: эффективное руководство по написанию ускоренного функционального кода с использованием C++17 и C++20. Packt Publishing. стр. 188. ISBN 978-1-78980-921-3.
80. Грей, Джон В. (2014). Освоение Mathematica: методы программирования и приложения. Academic Press. С. 233–234. ISBN 978-1-4832-1403-0.
81. Торра, Висенс (2016). Scala с точки зрения функционального программирования: введение в язык программирования. Конспект лекций по информатике. Том 9980. Springer. стр. 96. ISBN 978-3-319-46481-7.
82. Сассман, Джеральд Джей (1982). "LISP, программирование и реализация". Функциональное программирование и его приложения: продвинутый курс . CREST Advanced Courses. Cambridge University Press. стр. 29–72. ISBN 978-0-521-24503-6.См. в частности стр. 34.
83. Чаудхури, Ранджан (июнь 2003 г.). «Действительно ли арифметические операции выполняются за постоянное время?». Бюллетень ACM SIGCSE . 35 (2). Ассоциация вычислительной техники: 43–44. doi :10.1145/782941.782977. S2CID  13629142.
84. Fateman, Richard J. (11 апреля 2006 г.). "Комментарии к факториальным программам" (PDF) . Калифорнийский университет в Беркли.
85. Winkler, Jürgen FH; Kauer, Stefan (март 1997 г.). «Доказательство утверждений также полезно». ACM SIGPLAN Notices . 32 (3). Association for Computing Machinery: 38–41. doi : 10.1145/251634.251638 . S2CID  17347501.
86. Борвейн, Питер Б. (1985). «О сложности вычисления факториалов». Журнал алгоритмов . 6 (3): 376–380. doi :10.1016/0196-6774(85)90006-9. MR  0800727.
87. Харви, Дэвид; ван дер Хувен, Йорис (2021). "Целочисленное умножение за время O ( n log ⁡ n ) {\displaystyle O(n\log n)} " (PDF) . Анналы математики . Вторая серия. 193 (2): 563–617. doi :10.4007/annals.2021.193.2.4. MR  4224716. S2CID  109934776.
88. Арндт, Йорг (2011). «34.1.1.1: Вычисление факториала». Matters Computational: Ideas, Algorithms, Source Code (PDF) . Springer. стр. 651–652.См. также «34.1.5: Производительность», стр. 655–656.
89. Шёнхаге, Арнольд (1994). Быстрые алгоритмы: реализация многоленточной машины Тьюринга . BI Wissenschaftsverlag. п. 226.
90. Гай 2004. «B43: Переменные суммы факториалов». С. 152–153.
91. Каллан, Дэвид (2009). «Комбинаторный обзор тождеств для двойного факториала». arXiv : 0906.1317 [math.CO].
92. Meserve, BE (1948). «Заметки в классе: Двойные факториалы». The American Mathematical Monthly . 55 (7): 425–426. doi :10.2307/2306136. JSTOR  2306136. MR  1527019.
93. Mezey, Paul G. (2009). «Некоторые проблемы размерности в молекулярных базах данных». Журнал математической химии . 45 (1): 1–6. doi :10.1007/s10910-008-9365-8. S2CID  120103389..
94. Дейл, МРТ; Мун, Дж. В. (1993). «Пермутированные аналоги трех каталонских множеств». Журнал статистического планирования и вывода . 34 (1): 75–87. doi :10.1016/0378-3758(93)90035-5. MR  1209991..
95. Лука, Флориан ; Маркес, Диего (2010). «Совершенные степени в суммирующей функции силовой башни». Journal de Théorie des Nombres de Bordeaux . 22 (3): 703–718. дои : 10.5802/jtnb.740 . МР  2769339.
96. Грэм, Кнут и Паташник 1988, стр. x, 47–48.
97. Саган, Брюс Э. (2020). «Теорема 1.2.1». Комбинаторика: искусство подсчета . Аспирантура по математике. Том 210. Провиденс, Род-Айленд: Американское математическое общество. стр. 5. ISBN 978-1-4704-6032-7. МР  4249619.
98. Харди, Г. Х. (1921). «Примеры XLV». Курс чистой математики (3-е изд.). Cambridge University Press. стр. 215.
99. Дейли, DJ; Вере-Джонс, Д. (1988). "5.2: Факториальные моменты, кумулянты и производящие функциональные соотношения для дискретных распределений". Введение в теорию точечных процессов . Springer Series in Statistics. Нью-Йорк: Springer-Verlag. стр. 112. ISBN 0-387-96666-8. МР  0950166.
100. Слоан, Н. Дж. А. (ред.). "Последовательность A002109 (Гиперфакториалы: Произведение_{k = 1..n} k^k)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
101. Кинкелин, Х. (1860). «Ueber eine mit der Gammafunction verwandte Transcendente und deren Anwendung auf die Integralrechung» [О трансцендентной вариации гамма-функции и ее применении к интегральному исчислению]. Журнал für die reine und angewandte Mathematik (на немецком языке). 1860 (57): 122–138. дои : 10.1515/crll.1860.57.122. S2CID  120627417.
102. Глейшер, Дж. У. Л. (1877). «О произведении 11.22.33...nn». Вестник математики . 7 : 43–47.
103. Aebi, Christian; Cairns, Grant (2015). «Обобщения теоремы Вильсона для двойных, гипер-, суб- и суперфакториалов». The American Mathematical Monthly . 122 (5): 433–443. doi :10.4169/amer.math.monthly.122.5.433. JSTOR  10.4169/amer.math.monthly.122.5.433. MR  3352802. S2CID  207521192.
104. Слоан, Н. Дж. А. (ред.). "Последовательность A001013 (числа Джордана-Полиа: произведения факториальных чисел)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
105. Нельсон, Рэндольф (2020). Краткое путешествие в дискретную математику. Cham: Springer. стр. 127. doi :10.1007/978-3-030-37861-5. ISBN 978-3-030-37861-5. MR  4297795. S2CID  213895324.
106. Barnes, EW (1900). «Теория G-функции». The Quarterly Journal of Pure and Applied Mathematics . 31 : 264–314. JFM  30.0389.02.

Внешние ссылки

• Арифметический портал
• Математический портал

• Последовательность OEIS A000142 (Факториальные числа)
• «Факториал». Энциклопедия математики . EMS Press . 2001 [1994].
• Вайсштейн, Эрик В. «Факториал». MathWorld .