Факториал - Factorial
п | п ! |
---|---|
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 году.
Определение
Факториальная функция определяется произведением
Это приводит к рекуррентному соотношению
Факториал нуля
Факториал 0 равен 1 , или в символах 0! = 1 .
У этого определения есть несколько причин:
- Для n = 0 определение n ! поскольку продукт включает в себя продукт, в котором вообще нет чисел, и поэтому это пример более широкого соглашения, согласно которому продукт без факторов равен мультипликативному тождеству (см. Пустой продукт ).
- Существует ровно одна перестановка нулевых объектов (перестановка не в чем, единственная перестановка - ничего не делать).
- Это делает многие тождества комбинаторики действительными для всех применимых размеров. Количество способов выбрать 0 элементов из пустого набора определяется биномиальным коэффициентом :
- Это позволяет компактно выразить многие формулы, такие как экспоненциальная функция , в виде степенного ряда:
- Он расширяет рекуррентное отношение до 0.
- Соответствует гамма-функции .
Приложения
Хотя факториальная функция уходит корнями в комбинаторику , формулы, включающие факториалы, встречаются во многих областях математики.
- Есть n ! различные способы упорядочивания n различных объектов в последовательность, перестановки этих объектов.
- Часто факториалы появляются в знаменателе формулы, чтобы учесть тот факт, что порядок следует игнорировать. Классический пример - подсчет k - комбинаций (подмножеств из k элементов) из набора с n элементами. Такую комбинацию можно получить, выбрав k -перестановку: последовательно выбирая и удаляя один элемент набора k раз, всего
- Факториалы возникают в алгебре по разным причинам, например, через уже упомянутые коэффициенты биномиальной формулы или через усреднение по перестановкам для симметризации определенных операций.
- Факториалы также встречаются в исчислении ; например, они встречаются в знаменателях терминов формулы Тейлора , где они используются в качестве компенсации терминов в связи с п - й производной от й п , эквивалентным п ! .
- Факториалы также широко используются в теории вероятностей и теории чисел ( см. Ниже ).
- Факториалы могут быть полезны для облегчения манипуляции выражениями. Например, количество k -перестановок n можно записать как
- Факториальную функцию можно показать, используя правило мощности , как
Скорость роста и приближения для больших 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, входящего в разложение числа n на простые множители ! в качестве
Добавление 1 к факториалу n ! дает число, которое делится только на простые числа больше n . Этот факт можно использовать для доказательства теоремы Евклида о бесконечности числа простых чисел. Простые числа формы n ! ± 1 называются факториальными простыми числами .
Серия обратных
В обратных факториалах производят сходящийся ряд , сумма которых экспоненциальная базу е :
Факториал нецелых значений
Гамма и пи-функции
Помимо неотрицательных целых чисел, факториал также может быть определен для нецелочисленных значений, но для этого требуются более продвинутые инструменты математического анализа .
Одна из часто используемых функций, заполняющих значения факториала (но со сдвигом аргумента на 1), называется гамма-функцией и обозначается Γ ( z ) . Он определен для всех комплексных чисел z, кроме неположительных целых чисел, и задается, когда действительная часть z положительна, как
Его отношение к факториалу таково: n ! = Γ ( n + 1) для любого целого неотрицательного числа n .
Эйлера для гамма-функции былаКарл Фридрих Гаусс использовал обозначение Π ( z ) для обозначения той же функции, но с аргументом, сдвинутым на 1, так что это согласуется с факториалом для неотрицательных целых чисел. Эта функция пи определяется формулой
Функция пи и гамма-функция связаны формулой Π ( z ) = Γ ( z + 1) . Точно так же Π ( n ) = n ! для любого неотрицательного целого n .
В дополнение к этому, функция pi удовлетворяет той же повторяемости, что и факториалы, но для каждого комплексного значения z, где она определена
Например,
Из этого также следует , что для п ∈ N ,
Функция pi, безусловно, не единственный способ расширить факториалы до функции, определенной почти для всех комплексных значений, и даже не единственный, который является аналитическим, где бы он ни был определен. Тем не менее, это обычно считается наиболее естественным способом расширить значения факториалов до сложной функции. Например, теорема Бора – Моллерупа утверждает, что гамма-функция - единственная функция, которая принимает значение 1 в точке 1, удовлетворяет функциональному уравнению Γ ( n + 1) = n Γ ( n ) , является мероморфной по комплексным числам и является лог-выпуклым на положительной действительной оси. Аналогичное утверждение справедливо и для функции pi с использованием функционального уравнения Π ( n ) = n Π ( n - 1) .
Однако существуют сложные функции, которые, вероятно, более просты в смысле теории аналитических функций и которые интерполируют факториальные значения. Например, «гамма» -функция Адамара (
Hadamard 1894 ), которая, в отличие от гамма-функции, представляет собой целую функцию .Эйлер также разработал приближение сходящегося произведения для нецелочисленных факториалов, которое, как можно видеть, эквивалентно формуле для гамма-функции, приведенной выше:
Однако эта формула не обеспечивает практических средств вычисления функции пи или гамма-функции, поскольку скорость ее сходимости мала.
Приложения гамма-функции
Объемом из п - мерной гиперсферы радиуса R является
Факториал в комплексной плоскости
Представление через гамма-функцию позволяет оценить факториал комплексного аргумента. Эквилинии амплитуды и фазы факториала показаны на рисунке. Позволять
Тонкие линии показывают промежуточные уровни постоянного модуля и постоянной фазы. На полюсах каждого отрицательного целого числа фаза и амплитуда не определены. Равновесные линии плотны в окрестности особенностей вдоль отрицательных целочисленных значений аргумента.
Для | 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, ... начинается как
Двойная факториальная нотация может использоваться для упрощения выражения некоторых тригонометрических интегралов , чтобы обеспечить выражение для значений гамма-функции при полуцелых аргументах и объеме гиперсфер , а также для решения многих задач подсчета в комбинаторике, включая подсчет двоичных деревьев с помеченные листья и идеальные совпадения в полных графах .
Многофакторность
Распространенной связанной нотацией является использование нескольких восклицательных знаков для обозначения многофакторности , произведения целых чисел с шагом два ( n !! ), три ( n !!! ) или более (см. Обобщения двойного факториала ). Двойной факториал - наиболее часто используемый вариант, но можно точно так же определить тройной факториал ( n !!! ) и так далее. Можно определить k- кратный факториал, обозначенный n ! ( k ) , рекурсивно для положительных целых чисел как
Для достаточно большого n ≥ 1 обычная однофакториальная функция раскладывается до многофакторных функций следующим образом:
Точно так же, как n ! не определено для отрицательных целых чисел, и n !! не определено для отрицательных целых чисел, n ! ( k ) не определено для отрицательных целых чисел, делящихся на k .
Первобытный
Primorial натурального числа п (последовательность A002110 в OEIS ), обозначаемое п # , аналогичен факториал, но с продуктом берется только за простые числа меньше или равно п . То есть,
Композитор
Compositorial натурального числа п (последовательность A036691 в OEIS ) похож на факториал, но с продуктом берется только по составным числам меньше или равно п . Например, составное число 11 равно
Фибонориал
Fibonorial является продуктом из первых п положительных чисел Фибоначчи.
Последовательность фибонориалов начинается как
Субфакторный
Субфакториал дает количество нарушений в наборе объектов. Его значение:
где "nint" обозначает функцию, которая округляет свой ввод до ближайшего целого числа (в этом случае никогда не будет никакой двусмысленности / связей, потому что всегда является целым числом и является алгебраически независимым трансцендентным, а именно естественным основанием / числом Эйлера).
Сверхфакторный
Нил Слоан и Саймон Плафф определили суперфакториал в «Энциклопедии целочисленных последовательностей» (Academic Press, 1995) как произведение первых n факториалов. Итак, суперфакториал 4 равен
В основном
Эквивалентно суперфакториал дается формулой
Суперфакториалы могут быть расширены на все комплексные числа с помощью G-функции Барнса , так что для всех положительных целых чисел
n . Последовательность суперфакториалов начинается (с n = 0 ) какПо этому определению мы можем определить k -суперфакториал числа n (обозначаемый sf k ( n ) ) как:
3-суперфакториалы числа n равны
0-суперфакториал числа n равен n .
Суперфакториал Пиковера
В своей книге « Ключи к бесконечности» 1995 года Клиффорд Пиковер определил другую функцию n $, которую он назвал суперфакториальной. Это определяется
Эта операция также может быть выражена как тетрация
Гиперфакториальный
Иногда 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 -функцией .
Смотрите также
- Альтернативный факториал
- Факториал Бхаргавы
- Дигамма функция
- Экспоненциальный факториал
- Факторная система счисления
- Факторион
- Список факториальных и биномиальных тем
- Символ Поххаммера , который дает падающий или восходящий факториал
- Завершающие нули факториала
- Треугольное число , аддитивный аналог факториала
использованная литература
Цитаты
Источники
- Босток, Линда; Чендлер, Сюзанна ; Рурк, К. (2014-11-01), Дополнительная чистая математика , Нельсон Торнс, ISBN 9780859501033
- Грэм, Рональд Л .; Кнут, Дональд Э .; Паташник, Орен (1988), Конкретная математика , чтение, Массачусетс: Аддисон-Уэсли, ISBN 0-201-14236-8
- Гай, Ричард К. (2004), "Последовательности иррациональности E24", Нерешенные проблемы теории чисел (3-е изд.), Springer-Verlag , ISBN 0-387-20860-7, Zbl 1058,11001
- Хиггинс, Питер (2008), История чисел: от подсчета до криптографии , Нью-Йорк: Коперник, ISBN 978-1-84800-000-1
- Стедман, Фабиан (1677), Campanalogia , Лондон Издатель указан как «WS», который, возможно, был Уильямом Смитом, возможно, действующим как агент Общества молодежи колледжей , которому адресовано «Посвящение».
дальнейшее чтение
- Адамар, MJ (1968) [1894], "Sur L'Expression Du Produit 1 · 2 · 3 · · · · · ( n −1) Par Une Fonction Entière" (PDF) , uvres de Jacques Hadamard (на французском языке), Париж: Национальный центр научных исследований
- Рамануджан, Шриниваса (1988), Потерянная записная книжка и другие неопубликованные документы , Springer Berlin, стр. 339, ISBN 3-540-18726-Х
внешние ссылки
- "Факториал" , Энциклопедия математики , EMS Press , 2001 [1994]
- Вайсштейн, Эрик В. «Факториал» . MathWorld .
- Факториал в PlanetMath .