Факториал

В математике , то факториал положительного целого числа п , обозначим через п ! , является произведением всех положительных целых чисел, меньших или равных n :

${\ Displaystyle п! = п \ CDOT (п-1) \ CDOT (п-2) \ CDOT (п-3) \ CDOT \ CDOTS \ CDOT 3 \ CDOT 2 \ CDOT 1 \ ,.}$

Например,

${\ Displaystyle 5! = 5 \ CDOT 4 \ CDOT 3 \ CDOT 2 \ CDOT 1 = 120 \ ,.}$

Значение 0! равно 1 в соответствии с соглашением о пустом продукте . ^[1]

Факторная операция встречается во многих областях математики, особенно в комбинаторике , алгебре и математическом анализе . Его самое основное использование считает возможные различные последовательности - перестановки - n различных объектов: их n ! .

Факториальную функцию также можно расширить до нецелочисленных аргументов , сохранив при этом ее наиболее важные свойства, определив x ! = Γ ( x + 1) , где Γ - гамма-функция ; это не определено, если x - отрицательное целое число.

История [ править ]

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Ноябрь 2019 г. )

Использование факториалов задокументировано со времен Талмуда (200–500 гг. Н. Э.), Одним из самых ранних примеров является Еврейская Книга Творения Сефер Йецира, в которой факториалы перечислены как средство подсчета перестановок. ^[2] Индийские ученые использовали факторные формулы, по крайней мере, с 12 века. ^[3] сиддхант Shiromani от Бхаскара II (с. 1114-1185) , упомянутыми факториалами для перестановок в томе I, то Lilavati . Фабиан Стедман позже описал факториалы применительно к изменению звонка , музыкального искусства, включающего звон в несколько настроенных колоколов. ^[4] После описания рекурсивного подхода Стедман дает формулировку факториала (используя язык оригинала):

Природа этих методов такова, что изменения одного числа включают [включают] изменения всех меньших чисел ... до такой степени, что кажется, что полный Звук изменений одного числа формируется объединением полных Звонков на всех числах. меньшее количество в одно тело. ^[5]

Обозначения п ! был введен французским математиком Кристианом Крампом в 1808 г. ^[6]

Определение [ править ]

Факториальная функция определяется произведением

${\ Displaystyle п! = 1 \ CDOT 2 \ CDOT 3 \ CDOTS (п-2) \ CDOT (п-1) \ CDOT п,}$

для целого n ≥ 1 . Это может быть записано в обозначении продукта pi как

${\ displaystyle n! = \ prod _ {i = 1} ^ {n} i.}$

Это приводит к рекуррентному соотношению

${\ Displaystyle п! = п \ cdot (п-1) !.}$

Например,

${\ displaystyle {\ begin {align} 5! & = 5 \ cdot 4! \\ 6! & = 6 \ cdot 5! \\ 50! & = 50 \ cdot 49! \ end {align}}}$

и так далее.

Факториал нуля [ править ]

Факториал 0 равен 1 , или в символах 0! = 1 .

У этого определения есть несколько причин:

• Для n = 0 определение n ! поскольку продукт включает в себя продукт, в котором вообще нет чисел, и поэтому это пример более широкого соглашения, согласно которому продукт без факторов равен мультипликативному тождеству (см. Пустой продукт ).
• Существует ровно одна перестановка нулевых объектов (перестановка не в чем, единственная перестановка - ничего не делать).
• Это делает многие тождества комбинаторики действительными для всех применимых размеров. Количество способов выбрать 0 элементов из пустого набора определяется биномиальным коэффициентом

${\ displaystyle {\ binom {0} {0}} = {\ frac {0!} {0! 0!}} = 1.}$

В более общем смысле, количество способов выбрать все n элементов из набора n равно

${\ displaystyle {\ binom {n} {n}} = {\ frac {n!} {n! 0!}} = 1.}$

• Это позволяет компактно выразить многие формулы, такие как экспоненциальная функция , в виде степенного ряда:

${\displaystyle e^{x}=\sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}.}$

• Он расширяет рекуррентное отношение до 0.

Приложения [ править ]

Хотя факториальная функция уходит корнями в комбинаторику , формулы, включающие факториалы, встречаются во многих областях математики.

• Есть n ! различные способы организации n различных объектов в последовательность, перестановки этих объектов. ^{[7] [8]}
• Часто факториалы появляются в знаменателе формулы, чтобы учесть тот факт, что порядок следует игнорировать. Классический пример - подсчет k - комбинаций (подмножеств из k элементов) из набора с n элементами. Такую комбинацию можно получить, выбрав k -перестановку: последовательно выбирая и удаляя один элемент набора k раз, всего

${\displaystyle (n-0)(n-1)(n-2)\cdots \left(n-(k-1)\right)={\frac {n!}{(n-k)!}}=n^{\underline {k}}}$

возможности. Это, однако, производит k -комбинации в определенном порядке, который нужно игнорировать; поскольку каждая k -комбинация получается за k ! разными способами правильное количество k- комбинаций

${\displaystyle {\frac {n(n-1)(n-2)\cdots (n-k+1)}{k(k-1)(k-2)\cdots 1}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(n-k)!k!}}={\binom {n}{k}}.}$

Это число известно ^[9] как биномиальный коэффициент , потому что это также коэффициент при x ^k в (1 + x ) ⁿ . Этот термин часто называют падающим факториалом (произносится как « н к падающему к »).${\displaystyle n^{\underline {k}}}$

• Факториалы возникают в алгебре по разным причинам, например, через уже упомянутые коэффициенты биномиальной формулы или через усреднение по перестановкам для симметризации определенных операций.
• Факториалы также встречаются в исчислении ; например, они встречаются в знаменателях терминов формулы Тейлора , ^[10] , где они используются в качестве компенсации терминов в связи с п - й производной от й ^п , эквивалентным п ! .
• Факториалы также широко используются в теории вероятностей ^[11] и теории чисел ( см. Ниже ).
• Факториалы могут быть полезны для облегчения манипуляции выражениями. Например, количество k -перестановок n можно записать как

${\displaystyle n^{\underline {k}}={\frac {n!}{(n-k)!}}\,;}$

хотя это неэффективно как средство для вычисления этого числа, оно может служить для доказательства свойства симметрии ^{[8] [9]} биномиальных коэффициентов:

${\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n!}{(n-k)!k!}}={\frac {n^{\underline {n-k}}}{(n-k)!}}={\binom {n}{n-k}}\,.}$

• Факториальную функцию можно показать, используя правило мощности , как

${\displaystyle n!=D^{n}\,x^{n}={\frac {d^{n}}{dx^{n}}}\,x^{n}}$

где D ^п х ^п является обозначением Эйлера для п - й производной по й ^п . ^[12]

Скорость роста и приближения для больших n [ править ]

В п растет, факторный п ! растет быстрее , чем все многочлены и экспоненциальная функция (но медленнее , чем и двойная экспоненциальная функция ) в п .${\displaystyle n^{n}}$

Большинство приближений для n ! основаны на приближении его натурального логарифма

${\displaystyle \ln n!=\sum _{x=1}^{n}\ln x\,.}$

График функции f ( n ) = ln n ! показан на рисунке справа. Он выглядит приблизительно линейным для всех разумных значений n , но эта интуиция неверна. Мы получаем одно из простейших приближений для ln n ! ограничив сумму интегралом сверху и снизу следующим образом:

${\displaystyle \int _{1}^{n}\ln x\,dx\leq \sum _{x=1}^{n}\ln x\leq \int _{0}^{n}\ln(x+1)\,dx}$

что дает нам оценку

${\displaystyle n\ln \left({\frac {n}{e}}\right)+1\leq \ln n!\leq (n+1)\ln \left({\frac {n+1}{e}}\right)+1\,.}$

Следовательно, ln n ! ∼ n ln n (см. Обозначение Big O ). Этот результат играет ключевую роль в анализе вычислительной сложности из алгоритмов сортировки (см сравнения сортировки ). С границ на ln n ! Выведено выше, мы получаем, что

${\displaystyle \left({\frac {n}{e}}\right)^{n}e\leq n!\leq \left({\frac {n+1}{e}}\right)^{n+1}e\,.}$

Иногда целесообразно использовать более слабые, но более простые оценки. Используя приведенную выше формулу, легко показать, что для всех n мы имеем (п/3) ^п < п ! , и для всех n ≥ 6 имеем n ! <(п/2) ^п .

Для больших n мы получаем лучшую оценку числа n ! используя приближение Стирлинга :

${\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.}$

Фактически это происходит из асимптотического ряда для логарифма, а n факториал лежит между этим и следующим приближением:

${\displaystyle {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}<n!<{\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}e^{1/(12n)}\,.}$

Другое приближение для ln n ! дан Шринивасой Рамануджаном ( Рамануджан, 1988 )

${\displaystyle {\begin{aligned}\ln n!&\approx n\ln n-n+{\frac {\ln {\Bigl (}n{\bigl (}1+4n(1+2n){\bigr )}{\Bigr )}}{6}}+{\frac {\ln \pi }{2}}\\[6px]\Longrightarrow \;n!&\approx {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{2n}}+{\frac {1}{8n^{2}}}\right)^{1/6}\,.\end{aligned}}}$

И это, и приближение Стирлинга дают относительную ошибку порядка 1/п ³, но Рамануджан примерно в четыре раза точнее. Однако, если мы используем два поправочных члена в приближении типа Стирлинга, как в приближении Рамануджана, относительная ошибка будет порядка1/п ⁵: ^[13]

${\displaystyle n!\approx {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({{\frac {1}{12n}}-{\frac {1}{360n^{3}}}}\right)\,.}$

Вычисление [ править ]

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

Основная практическая трудность вычисления факториалов - это размер результата. Чтобы гарантировать, что точный результат будет соответствовать всем допустимым значениям даже самого маленького обычно используемого целого типа ( 8-битные целые числа со знаком), потребуется более 700 бит, поэтому никакая разумная спецификация факториальной функции с использованием типов фиксированного размера не может избежать вопросов. от переполнения . Ценности 12! и 20! являются наибольшими факториалами, которые могут быть сохранены, соответственно, в 32-битных и 64-битных целых числах, обычно используемых в персональных компьютерах , однако многие языки поддерживают целочисленные типы переменной длины, способные вычислять очень большие значения. ^[14] Плавающая точкапредставление приближенного результата позволяет пойти немного дальше, но это также остается весьма ограниченным возможным переполнением. Большинство калькуляторов используют научную нотацию с 2-значными десятичными показателями, и тогда наибольший подходящий факториал равен 69 !, потому что 69! <10 ¹⁰⁰ <70! . Другие реализации (например, компьютерное программное обеспечение, например программы электронных таблиц) часто могут обрабатывать большие значения.

Большинство программных приложений вычисляют небольшие факториалы прямым умножением или поиском в таблице. Большие факториальные значения могут быть аппроксимированы с помощью формулы Стирлинга . Wolfram Alpha может вычислить точные результаты для функции потолка и функции пола применительно к двоичной , натурального и десятичного логарифма от п ! для значений n до249 999 и до20 000 000 ! для целых чисел.

Если требуются точные значения больших факториалов, их можно вычислить с помощью арифметики произвольной точности . Вместо того, чтобы выполнять последовательные умножения ((1 × 2) × 3) × 4 ... , программа может разделить последовательность на две части, продукты которых имеют примерно одинаковый размер, и умножить их, используя метод « разделяй и властвуй». . Часто это более эффективно. ^[15]

Асимптотически наилучшая эффективность достигается вычислением n ! от его простой факторизации. Как задокументировал Питер Борвейн , факторизация на простые множители позволяет n ! вычисляться за время O ( n (log n log log n ) ² ) при условии, что используется алгоритм быстрого умножения (например, алгоритм Шёнхаге – Штрассена ). ^[16] Питер Лушни представляет исходный код и тесты для нескольких эффективных факториальных алгоритмов с использованием или без использования решета простых чисел . ^[17]

Теория чисел [ править ]

Факториалы имеют множество приложений в теории чисел. В частности, n ! обязательно делится на все простые числа до n включительно  . Как следствие, n > 5 является составным числом тогда и только тогда, когда

${\displaystyle (n-1)!\equiv 0{\pmod {n}}.}$

Более сильный результат - теорема Вильсона , которая утверждает, что

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

тогда и только тогда, когда p простое число. ^{[18] [19]}

Формула Лежандра дает кратность простого числа p, входящего в разложение числа n на простые множители ! в качестве

${\displaystyle \sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor }$

или, что то же самое,

${\displaystyle {\frac {n-s_{p}(n)}{p-1}},}$

где s _p ( n ) обозначает сумму стандартных p цифр числа n .

Добавление 1 к факториалу n ! дает число, которое делится только на простые числа больше n . Этот факт можно использовать для доказательства теоремы Евклида о бесконечности числа простых чисел. ^[20] Простые числа вида n ! ± 1 называются факториальными простыми числами .

Серия встречных [ править ]

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

${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{n!}}={\frac {1}{1}}+{\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{6}}+{\frac {1}{24}}+{\frac {1}{120}}+\cdots =e\,.}$

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

${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{(n+2)n!}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{30}}+{\frac {1}{144}}+\cdots =1\,.}$

О сходимости этого ряда к 1 свидетельствует тот факт, что его частичные суммы равны . Следовательно, факториалы не образуют иррациональной последовательности . ^[21]${\displaystyle {\frac {k!-1}{k!}}}$

Факториал нецелых значений [ править ]

Функции гаммы и пи [ править ]

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

Одна из часто используемых функций, заполняющих значения факториала (но со сдвигом аргумента на 1), называется гамма-функцией и обозначается Γ ( z ) . Он определен для всех комплексных чисел z, кроме неположительных целых чисел, и задается, когда действительная часть z положительна, как

${\displaystyle \Gamma (z)=\int _{0}^{\infty }t^{z-1}e^{-t}\,dt.}$

Его отношение к факториалу таково: n ! = Γ ( n + 1) для любого целого неотрицательного числа n .

Первоначальная формула Эйлера для гамма-функции была

${\displaystyle \Gamma (z)=\lim _{n\to \infty }{\frac {n^{z}n!}{\displaystyle \prod _{k=0}^{n}(z+k)}}.}$

Карл Фридрих Гаусс использовал обозначение Π ( z ) для обозначения той же функции, но с аргументом, сдвинутым на 1, так что это согласуется с факториалом для неотрицательных целых чисел. Эта функция пи определяется формулой

${\displaystyle \Pi (z)=\int _{0}^{\infty }t^{z}e^{-t}\,dt.}$

Функция пи и гамма-функция связаны формулой Π ( z ) = Γ ( z + 1) . Точно так же Π ( n ) = n ! для любого неотрицательного целого n .

В дополнение к этому, функция pi удовлетворяет той же повторяемости, что и факториалы, но для каждого комплексного значения z, где она определена

${\displaystyle \Pi (z)=z\Pi (z-1)\,.}$

Это уже не рекуррентное соотношение, а функциональное уравнение . Что касается гамма-функции, это

${\displaystyle \Gamma (n+1)=n\Gamma (n)\,.}$

Значения этих функций при полуцелых значениях поэтому определяются одним из них:

${\displaystyle \Gamma \left({\frac {1}{2}}\right)=\left(-{\frac {1}{2}}\right)!=\Pi \left(-{\frac {1}{2}}\right)={\sqrt {\pi }}\,,}$

из которой следует , что при  п ∈ N ,

${\displaystyle {\begin{aligned}&\Gamma \left({\frac {1}{2}}+n\right)=\left(-{\frac {1}{2}}+n\right)!=\Pi \left(-{\frac {1}{2}}+n\right)\\[5pt]={}&{\sqrt {\pi }}\prod _{k=1}^{n}{\frac {2k-1}{2}}={\frac {(2n)!}{4^{n}n!}}{\sqrt {\pi }}={\frac {(2n-1)!}{2^{2n-1}(n-1)!}}{\sqrt {\pi }}\,.\end{aligned}}}$

Например,

${\displaystyle \Gamma \left({\frac {9}{2}}\right)={\frac {7}{2}}!=\Pi \left({\frac {7}{2}}\right)={\frac {1}{2}}\cdot {\frac {3}{2}}\cdot {\frac {5}{2}}\cdot {\frac {7}{2}}{\sqrt {\pi }}={\frac {8!}{4^{4}4!}}{\sqrt {\pi }}={\frac {7!}{2^{7}3!}}{\sqrt {\pi }}={\frac {105}{16}}{\sqrt {\pi }}\approx 11.631\,728\ldots }$

Из этого также следует , что для  п ∈ N ,

${\displaystyle \Gamma \left({\frac {1}{2}}-n\right)=\left(-{\frac {1}{2}}-n\right)!=\Pi \left(-{\frac {1}{2}}-n\right)={\sqrt {\pi }}\prod _{k=1}^{n}{\frac {2}{1-2k}}={\frac {\left(-4\right)^{n}n!}{(2n)!}}{\sqrt {\pi }}\,.}$

Например,

${\displaystyle \Gamma \left(-{\frac {5}{2}}\right)=\left(-{\frac {7}{2}}\right)!=\Pi \left(-{\frac {7}{2}}\right)={\frac {2}{-1}}\cdot {\frac {2}{-3}}\cdot {\frac {2}{-5}}{\sqrt {\pi }}={\frac {\left(-4\right)^{3}3!}{6!}}{\sqrt {\pi }}=-{\frac {8}{15}}{\sqrt {\pi }}\approx -0.945\,308\ldots }$

Функция pi, безусловно, не единственный способ расширить факториалы до функции, определенной почти для всех комплексных значений, и даже не единственный, который является аналитическим, где бы он ни был определен. Тем не менее, это обычно считается наиболее естественным способом расширить значения факториалов до сложной функции. Например, теорема Бора – Моллерупа утверждает, что гамма-функция - единственная функция, которая принимает значение 1 в точке 1, удовлетворяет функциональному уравнению Γ ( n + 1) = n Γ ( n ) , является мероморфной по комплексным числам и является лог-выпуклым на положительной действительной оси. Аналогичное утверждение справедливо и для функции pi с использованиемΠ ( n ) = n Π ( n - 1) функциональное уравнение.

Однако существуют сложные функции, которые, вероятно, более просты в смысле теории аналитических функций и которые интерполируют факториальные значения. Например, «гамма» -функция Адамара ( Hadamard 1894 ), которая, в отличие от гамма-функции, представляет собой целую функцию . ^[22] harv error: no target: CITEREFHadamard1894 (help)

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

${\displaystyle {\begin{aligned}n!=\Pi (n)&=\prod _{k=1}^{\infty }\left({\frac {k+1}{k}}\right)^{n}\!\!{\frac {k}{n+k}}\\&=\left[\left({\frac {2}{1}}\right)^{n}{\frac {1}{n+1}}\right]\left[\left({\frac {3}{2}}\right)^{n}{\frac {2}{n+2}}\right]\left[\left({\frac {4}{3}}\right)^{n}{\frac {3}{n+3}}\right]\cdots \end{aligned}}}$

Однако эта формула не обеспечивает практических средств вычисления функции пи или гамма-функции, поскольку скорость ее сходимости мала.

Применение гамма-функции [ править ]

Объемом из п - мерной гиперсферы радиуса R является

${\displaystyle V_{n}={\frac {\pi ^{n/2}}{\Gamma \left({\frac {n}{2}}+1\right)}}R^{n}\,.}$

Факториал в комплексной плоскости [ править ]

Представление через гамма-функцию позволяет оценить факториал комплексного аргумента. Эквилинии амплитуды и фазы факториала показаны на рисунке. Позволять

${\displaystyle f=\rho e^{i\varphi }=(x+iy)!=\Gamma (x+iy+1)\,.}$

Показаны несколько уровней постоянного модуля (амплитуды) ρ и постоянной фазы φ . Сетка покрывает диапазон −3 ≤ x ≤ 3 , −2 ≤ y ≤ 2 с единичными шагами. Штриховая линия показывает уровень φ = ± π .

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

Для | z | <1 , можно использовать разложения Тейлора:

${\displaystyle z!=\sum _{n=0}^{\infty }g_{n}z^{n}\,.}$

Первые коэффициенты этого разложения равны

где γ - постоянная Эйлера – Маскерони, а ζ - дзета-функция Римана . Системы компьютерной алгебры, такие как SageMath, могут генерировать многие термины этого расширения.

Аппроксимация факториала [ править ]

Для больших значений аргумента факториал может быть аппроксимирован интегралом от дигамма-функции , используя представление непрерывной дроби . Этот подход принадлежит Т. Дж. Стилтьесу (1894). ^{[ необходима цитата ]} Написание z ! = e ^{P ( z ),} где P ( z ) -

${\displaystyle P(z)=p(z)+{\frac {\ln 2\pi }{2}}-z+\left(z+{\frac {1}{2}}\right)\ln(z)\,,}$

Стилтьес дал непрерывную дробь для p ( z ) :

${\displaystyle p(z)={\cfrac {a_{0}}{z+{\cfrac {a_{1}}{z+{\cfrac {a_{2}}{z+{\cfrac {a_{3}}{z+\ddots }}}}}}}}}$

Первые несколько коэффициентов a _n равны ^[23]

п	а н
0	1/12
1	1/30
2	53/210
3	195/371
4	22 999/22 737
5	29 944 523/19 733 142
6	109 535 241 009/48 264 275 462

Существует заблуждение, что ln z ! = P ( z ) или ln Γ ( z + 1) = P ( z ) для любого комплекса z ≠ 0 . ^{[ необходимая цитата ]} Действительно, соотношение через логарифм действительно только для определенного диапазона значений z вблизи действительной оси, где −π <Im (Γ ( z + 1)) <π . Чем больше действительная часть аргумента, тем меньше должна быть мнимая часть. Однако обратное соотношение z ! = e ^{P ( z)} , справедливо для всей комплексной плоскости, кроме z = 0 . Сходимость плохая вблизи отрицательной части действительной оси; ^{[ необходимая цитата ]} трудно иметь хорошую сходимость любого приближения в окрестности особенностей. Когда | Im z | > 2 или Re z > 2 , шести приведенных выше коэффициентов достаточно для вычисления факториала со сложной двойной точностью. Для более высокой точности можно вычислить большее количество коэффициентов с помощью рациональной схемы QD (алгоритм QD Рутисхаузера). ^[24]

Нераспространяемость до отрицательных целых чисел [ править ]

Отношение n ! = п × ( п  - 1)! позволяет вычислить факториал для целого числа с учетом факториала для меньшего целого числа. Отношение можно инвертировать, чтобы можно было вычислить факториал для целого числа с учетом факториала для большего целого числа:

${\displaystyle (n-1)!={\frac {n!}{n}}.}$

Однако эта рекурсия не позволяет нам вычислить факториал отрицательного целого числа; использование формулы для вычисления (-1)! потребует деления ненулевого значения на ноль и, таким образом, блокирует нас от вычисления факториала для каждого отрицательного целого числа. Точно так же гамма-функция не определена для нуля или отрицательных целых чисел, хотя она определена для всех других комплексных чисел.

Факториальные продукты и функции [ править ]

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

Обратный факториал [ править ]

Обозначение иногда используется для представления произведения n целых чисел, считая до x включительно (т.е. ). ^[25]${\displaystyle x^{(n)}}$${\displaystyle {\frac {x!}{(x-(n-1))!}}}$

Это также известно как Факториал падения.

Двойной факториал [ править ]

Произведение всех нечетных целых чисел до некоторого нечетного положительного целого числа n называется двойным факториалом числа n и обозначается n !! . ^[26] То есть

${\displaystyle (2k-1)!!=\prod _{i=1}^{k}(2i-1)={\frac {(2k)!}{2^{k}k!}}={\frac {_{2k}P_{k}}{2^{k}}}={\frac {\left(2k\right)^{\underline {k}}}{2^{k}}}\,.}$

Например, 9 !! = 1 × 3 × 5 × 7 × 9 = 945 .

Последовательность двойных факториалов для n = 1, 3, 5, 7, ... начинается как

1, 3, 15, 105, 945, 10 395 , г.135 135 , ... (последовательность A001147 в OEIS )

Двойной факториал обозначение может быть использовано для упрощения выражения некоторых тригонометрических интегралов , ^[27] , чтобы обеспечить выражение для значений гаммы - функции в полуцелых аргументах и объем гиперсфер , ^[28] и решить многие проблемы подсчета в комбинаторика, включая подсчет бинарных деревьев с помеченными листьями и идеальных пар в полных графах . ^{[26] [29]}

Многофакторные [ править ]

Распространенной связанной нотацией является использование нескольких восклицательных знаков для обозначения многофакторности , произведения целых чисел с шагом два ( n !! ), три ( n !!! ) или более (см. Обобщения двойного факториала ). Двойной факториал - наиболее часто используемый вариант, но можно точно так же определить тройной факториал ( n !!! ) и так далее. Можно определить k- кратный факториал, обозначенный n ! ^{( k )} , рекурсивно для положительных целых чисел как

${\displaystyle n!^{(k)}={\begin{cases}n&{\text{if }}0<n\leq k,\\n\left({(n-k)!}^{(k)}\right)&{\text{if }}n>k.\end{cases}}}$

Кроме того, аналогично 0! знак равно1!/1= 1 , можно определить:

${\displaystyle {n!}^{(k)}=1\quad {\text{if}}\ {-k}<n\leq 0.}$

Для достаточно большого n ≥ 1 обычная однофакториальная функция раскладывается до многофакторных функций следующим образом:

${\displaystyle {\begin{aligned}n!&=n!!\cdot (n-1)!!\,,&n&\geq 1\\[5px]&=n!!!\cdot (n-1)!!!\cdot (n-2)!!!\,,&n&\geq 2\\[5px]&=\prod _{i=0}^{k-1}(n-i)!^{(k)},\quad {\text{ for }}k\in \mathbb {Z} ^{+}\,,&n&\geq k-1.\end{aligned}}}$

Точно так же, как n ! не определено для отрицательных целых чисел, и n !! не определено для отрицательных целых чисел, n ! ^{( k )} не определено для отрицательных целых чисел, делящихся на k .

Первобытный [ править ]

Primorial натурального числа п (последовательность A002110 в OEIS ), обозначаемое п # , аналогичен факториал, но с продуктом берется только за простые числа меньше или равно п . То есть,

${\displaystyle n\#=\prod _{p\leq n}p,}$

где p пробегает простые числа, меньшие или равные n . Например, примориал 11 - это

${\displaystyle 11\#=11\times 7\times 5\times 3\times 2=2310.}$

Суперфакториал [ править ]

Нил Слоан и Саймон Плафф определили суперфакториал в «Энциклопедии целочисленных последовательностей» (Academic Press, 1995) как произведение первых n факториалов. Итак, суперфакториал 4 равен

${\displaystyle \operatorname {sf} (4)=1!\times 2!\times 3!\times 4!=288\,.}$

В целом

${\displaystyle {\begin{aligned}\operatorname {sf} (n)=\prod _{k=1}^{n}k!&=\prod _{k=1}^{n}k^{n-k+1}\\&=1^{n}\cdot 2^{n-1}\cdot 3^{n-2}\cdots (n-1)^{2}\cdot n^{1}\,.\end{aligned}}}$

Эквивалентно суперфакториал дается формулой

${\displaystyle \operatorname {sf} (n)=\prod _{0\leq i<j\leq n}(j-i)}$

который является определяющим фактором из матрицы Вандермонда .

Суперфакториалы могут быть расширены на все комплексные числа с помощью G-функции Барнса , так что для всех положительных целых чисел n . Последовательность суперфакториалов начинается (с n = 0 ) как${\displaystyle G(n)=\operatorname {sf} (n)}$

1, 1, 2, 12, 288, 34 560 , г.24 883 200 ,125 411 328 000 , ... (последовательность A000178 в OEIS )

По этому определению мы можем определить k -суперфакториал числа n (обозначаемый sf _k ( n ) ) как:

${\displaystyle \operatorname {sf} _{k}(n)={\begin{cases}n&{\text{if }}k=0\\\prod _{r=1}^{n}\operatorname {sf} _{k-1}(r)&{\text{if }}k\geq 1\end{cases}}}$

2-суперфакториалы числа n равны

1, 1, 2, 24, 6 912 , г.238 878 720 ,5 944 066 965 504 000 ,745 453 331 864 786 829 312 000 000 , ... (последовательность A055462 в OEIS )

0-суперфакториал числа n равен n .

Суперфакториал Пиковера [ править ]

В своей книге « Ключи к бесконечности» 1995 года Клиффорд Пиковер определил другую функцию n $, которую он назвал суперфакториальной. Это определяется

${\displaystyle n\$\equiv {\begin{matrix}\underbrace {n!^{{n!}^{{\cdot }^{{\cdot }^{{\cdot }^{n!}}}}}} \\n!{\mbox{ copies of }}n!\end{matrix}}.}$

Эта последовательность суперфакториалов начинается

${\displaystyle {\begin{aligned}1\$&=1\,,\\2\$&=2^{2}=4\,,\\3\$&=6^{6^{6^{6^{6^{6}}}}}\,.\end{aligned}}}$

(Здесь, как обычно для составного возведения в степень , группировка понимается справа налево: a ^{b c} = a ^{( b c )} .)

Эта операция также может быть выражена как тетрация

${\displaystyle n\$={}^{n!}(n!)\,,}$

или используя обозначение стрелки вверх Кнута как

${\displaystyle n\$=(n!)\uparrow \uparrow (n!)=(n!)\uparrow \uparrow \uparrow 2\,.}$

Гиперфакториал [ править ]

Иногда hyperfactorial из п считается. Он записывается как H ( n ) и определяется как

${\displaystyle {\begin{aligned}H(n)&=\prod _{k=1}^{n}k^{k}\\&=1^{1}\cdot 2^{2}\cdot 3^{3}\cdots (n-1)^{n-1}\cdot n^{n}.\end{aligned}}}$

Для n = 1, 2, 3, 4, ... значения H ( n ) равны 1, 4, 108,27 648 , ... (последовательность A002109 в OEIS ).

Асимптотическая скорость роста равна

${\displaystyle H(n)\sim An^{(6n^{2}+6n+1)/12}e^{-n^{2}/4}}$

где A = 1,2824 ... - постоянная Глейшера – Кинкелина . ^[30] H (14) ≈ 1,8474 × 10 ⁹⁹ уже почти равно гуголу , а H (15) ≈ 8,0896 × 10 ¹¹⁶ почти такой же величины, как число Шеннона , теоретическое количество возможных шахматных партий. По сравнению с определением суперфакториала Пиковером, гиперфакториал растет относительно медленно.

Гиперфакториальная функция может быть обобщена на комплексные числа аналогично факториальной функции. Полученная функция называется K -функцией .

См. Также [ править ]

Ссылки [ править ]

Цитаты [ править ]

Источники [ править ]

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме Факториал (функция) .

• Факториал (математика) в Британской энциклопедии
• "Факториал" , Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Факториал» . MathWorld .
• Факториал в PlanetMath .