Факториал - Factorial

Выбранные члены факториальной последовательности (последовательность A000142 в OEIS ); значения, указанные в экспоненциальном представлении, округляются до отображаемой точности
п п !
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5 040
8 40 320
9 362 880
10 3 628 800
11 39 916 800
12 479 001 600
13 6 227 020 800
14 87 178 291 200
15 1 307 674 368 000
16 20 922 789 888 000
17 355 687 428 096 000
18 6 402 373 705 728 000
19 121 645 100 408 832 000
20 2 432 902 008 176 640 000
25 1,551 121 004 × 10 25
50 3,041 409 320 × 10 64
70 1,197 857 167 × 10 100
100 9,332 621 544 × 10 157
450 1,733 368 733 × 10 1 000
1 000 4,023 872 601 × 10 2 567
3 249 6,412 337 688 × 10 10 000
10 000 2,846 259 681 × 10 35 659
25 206 1,205 703 438 × 10 100 000
100 000 2,824 229 408 × 10 456 573
205 023 2,503 898 932 × 10 1 000 004
1 000 000 8,263 931 688 × 10 5 565 708
10 100 1010 101,998 109 775 4820

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

Например,

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

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

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

История

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

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

Обозначение

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

Определение

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

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

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

Например,
и так далее.

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

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

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

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

Приложения

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

  • Есть n ! различные способы упорядочивания n различных объектов в последовательность, перестановки этих объектов.
  • Часто факториалы появляются в знаменателе формулы, чтобы учесть тот факт, что порядок следует игнорировать. Классический пример - подсчет k - комбинаций (подмножеств из k элементов) из набора с n элементами. Такую комбинацию можно получить, выбрав k -перестановку: последовательно выбирая и удаляя один элемент набора k раз, всего
    возможности. Это, однако, производит k -комбинации в определенном порядке, который нужно игнорировать; поскольку каждая k -комбинация получается за k ! разными способами правильное количество k -комбинаций
    Это число известно как биномиальный коэффициент , потому что это также коэффициент при x k в (1 + x ) n . Этот термин часто называют падающим факториалом (произносится как « н к падающему к »).
  • Факториалы возникают в алгебре по разным причинам, например, через уже упомянутые коэффициенты биномиальной формулы или через усреднение по перестановкам для симметризации определенных операций.
  • Факториалы также встречаются в исчислении ; например, они встречаются в знаменателях терминов формулы Тейлора , где они используются в качестве компенсации терминов в связи с п - й производной от й п , эквивалентным п ! .
  • Факториалы также широко используются в теории вероятностей и теории чисел ( см. Ниже ).
  • Факториалы могут быть полезны для облегчения манипуляции выражениями. Например, количество k -перестановок n можно записать как
    хотя это неэффективно как средство для вычисления этого числа, оно может служить для доказательства свойства симметрии биномиальных коэффициентов:
  • Факториальную функцию можно показать, используя правило мощности , как
    где D п х п является обозначением Эйлера для п - й производной по й п .

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

График натурального логарифма факториала

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

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

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

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

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

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

Сравнение приближения Стирлинга с факториалом

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

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

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

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

Вычисление

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

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

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

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

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

Теория чисел

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

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

тогда и только тогда, когда p простое число.

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

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

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

Серия обратных

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

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

Факториал нецелых значений

Гамма и пи-функции

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

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

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

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

Первоначальная формула

Эйлера для гамма-функции была

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

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

Факториальная функция, обобщенная для всех действительных чисел, кроме отрицательных целых. Например, 0! = 1! = 1 , (-1/2)! = π ,1/2! знак равноπ/2.

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

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

Например,

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

Например,

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

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

Hadamard 1894 ), которая, в отличие от гамма-функции, представляет собой целую функцию .

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

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

Приложения гамма-функции

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

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

Амплитуда и фаза факториала комплексного аргумента

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

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

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

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

Первые коэффициенты этого разложения равны
п g n Приближение
0 1 1
1 - γ -0,577 215 6649
2 π 2/12 + γ 2/2 0,989 055 9955
3 -ζ (3)/3 - π 2/12 - γ 3/6 -0,907 479 0760

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

Аппроксимации факториала

Для больших значений аргумента факториал может быть аппроксимирован логарифмом гамма-функции с использованием представления непрерывной дроби . Этот подход принадлежит Т. Дж. Стилтьесу (1894). Пишу

Стилтьес дал непрерывную дробь для :
Первые несколько коэффициентов равны
п а н
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

Непрерывная дробь сходится тогда и только тогда . Вблизи мнимой оси сходимость плохая. Когда , шести приведенных выше коэффициентов достаточно для оценки факториала со сложной двойной точностью. Для более высокой точности можно вычислить большее количество коэффициентов с помощью рациональной схемы QD (алгоритм QD Рутисхаузера).

Нерасширяемость до отрицательных целых чисел

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

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

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

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

Обратный факториал

Обозначение иногда используется для представления произведения

n целых чисел, считая до x включительно (т.е. ).

Это также известно как падающий факториал .

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

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

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

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

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

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

Многофакторность

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

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

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

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

Первобытный

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

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

Композитор

Compositorial натурального числа п (последовательность A036691 в OEIS ) похож на факториал, но с продуктом берется только по составным числам меньше или равно п . Например, составное число 11 равно

Фибонориал

Fibonorial является продуктом из первых п положительных чисел Фибоначчи.

Последовательность фибонориалов начинается как

1, 1, 1, 2, 6, 30, 240, 3120 , г.65 520 , ... (последовательность A003266 в OEIS )

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

Субфакториал дает количество нарушений в наборе объектов. Его значение:

где "nint" обозначает функцию, которая округляет свой ввод до ближайшего целого числа (в этом случае никогда не будет никакой двусмысленности / связей, потому что всегда является целым числом и является алгебраически независимым трансцендентным, а именно естественным основанием / числом Эйлера).

Сверхфакторный

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

В основном

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

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

Суперфакториалы могут быть расширены на все комплексные числа с помощью G-функции Барнса , так что для всех положительных целых чисел

n . Последовательность суперфакториалов начинается (с n = 0 ) как
1, 1, 2, 12, 288, 34 560 , г.24 883 200 ,125 411 328 000 , ... (последовательность A000178 в OEIS )

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

3-суперфакториалы числа 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 $, которую он назвал суперфакториальной. Это определяется

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

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

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

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

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

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

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

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

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

Смотрите также

использованная литература

Цитаты

Источники

дальнейшее чтение

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