Факторіал

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Обрані числа із факторіальної послідовності (Послідовність A000142 з Онлайн енциклопедії послідовностей цілих чисел, OEIS); значення наведені в науковій нотації округлені до наведеної точності
n n!
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
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 3,55687428096E+14
18 6 402 373 705 728 000.
19 121 645 100 408 832 000.
20 2 432 902 008 176 640 000.
25 1.551121004×1025
50 3.041409320×1064
70 1.197857167×10100
100 9.332621544×10157
450 1.733368733×101000
1000 4.023872601×102567
3249 6.412337688×1010 000
10 000 2.846259681×1035 659
25 206 1.205703438×10100 000
100 000 2.824229408×10456 573
205 023 2.503898932×101 000 004
1 000 000 8.263931688×105 565 708
10100 1010Too Many Digits

Факторіал натурального числа добуток натуральних чисел від одиниці до включно, позначається !.

.

За означенням , згідно конвенції для порожнього добутку[en].[1].

При великих наближене значення факторіала можна обчислити за формулою Стірлінга.

Факторіал дорівнює кількості перестановок з елементів.

Історія[ред. | ред. код]

Факторіали використовувалися для підрахунку перестановок ще в 12-му столітті, індійськими вченими.[2] В 1677, Фабіан Стедмен[en] описав застосування факторіалів для узгодження передзвону[en], музичного мистецтва із використанням багатьох підібраних налаштованих дзвонів.[3] Після описання рекурсивного методу, Стедмен приводить визначення факторіалу.

Математична нотація[en] n! була запропонована французьким математиком Крістіаном Крампом[en] у 1808.[4]

Визначення[ред. | ред. код]

Функція факторіалу визначається добутком

для початкового цілого числа n ≥ 1. Цей добуток можна представити у нотації великим Пі для добутку наступним чином

Із цих формул можна отримати наступне рекурентне співвідношення:

Наприклад, маємо наступне:

і так далі.

Факторіал нуля[ред. | ред. код]

Для того, щоб рекурентне співвідношення могло поширюватися на випадок n = 0, необхідним є визначити, що

Так що

Існує ряд незалежних причин, чому це визначення вважають гармонійним. Це є наступні твердження:

  • У випадку n = 0, у визначенні n! як добутку припускає порожній добуток без чисел взагалі, і тому це є прикладом більш ширшої конвенції того що добуток без множників дорівнює мультиплікативній одиниці (див. порожній добуток[en]).
  • Існує рівно одна можлива перестановка нульових об'єктів (оскільки нічого переставляти, єдиною можливою перестановкою може бути це нічого не робити).
  • Це дозволяє утворити багато рівнянь з комбінаторики, що будуть дійсними для всіх заданих розмірів. Кількість різних способів вибрати 0 елементів із порожньої множини задається біноміальним коефіцієнтом
.
В більш загальному випадку, кількість різних способів впорядкувати всі n елементи із множини з n елементів дорівнюватиме
.
  • Це дозволяє мати компактний вираз багатьох формул, таких як показникова функція, що задає степеневий ряд:

Факторіал не цілого числа[ред. | ред. код]

Функцію факторіалу також можна визначити для не цілих чисел з використанням більш складних математичних понять (за допомогою гамма функції n! = Γ(n + 1)). Це більш загальне визначення використовується в інженерних калькуляторах і в математичному програмному забезпеченні такому як Maple, Mathematica або APL.

Факторіали деяких чисел[ред. | ред. код]

0! = 1
1! = 1
2! = 1·2 = 2
3! = 1·2·3 = 6
4! = 1·2·3·4 = 24
5! = 1·2·3·4·5 = 120
6! = 1·2·3·4·5·6 = 720
7! = 1·2·3·4·5·6·7 = 5040
8! = 1·2·3·4·5·6·7·8 = 40320
9! = 1·2·3·4·5·6·7·8·9 = 362880
10! = 1·2·3·4·5·6·7·8·9·10 = 3628800

Властивості[ред. | ред. код]

Рекуррентна формула[ред. | ред. код]

Комбінаторна інтерпретація[ред. | ред. код]

В комбінаториці факторіал натурального числа n інтерпретується як кількість перестановок (упорядкування) множини з n елементів. Наприклад, для множини {A, B, C, D} з 4-х елементів існує 4! = 24 перестановки:

ABCD  BACD  CABD  DABC
ABDC  BADC  CADB  DACB
ACBD  BCAD  CBAD  DBAC
ACDB  BCDA  CBDA  DBCA
ADBC  BDAC  CDAB  DCAB
ADCB  BDCA  CDBA  DCBA

Комбінаторна інтерпретація факторіала слугує обґрунтуванням тотожності 0! = 1, оскільки порожня множина може бути впорядкованою лише одним способом.

Зв'язок з гамма-функцією[ред. | ред. код]

Факторіал є пов'язаним з гамма-функцією від цілого аргумента співвідношенням:

.

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

Формула Стірлінга[ред. | ред. код]

Формула Стірлінґа — одна з найвідоміших наближених формул для обчислення факторіала:

В багатьох випадках для наближеного значення факторіала досить розглядати лише головний член формули Стірлінга:

при цьому можна стверджувати, що

Подвійний факторіал[ред. | ред. код]

Подвійний факторіал числа n позначається n!! і визначається як добуток всіх послідовних парних (якщо n парне) або непарних (якщо n непарне) натуральних чисел до n включно. Таким чином,

За означенням .

Застосування[ред. | ред. код]

Хоча функція факторіалу має свої корені у комбінаториці, формули в яких зустрічається факторіал є в різних областях математики.

  • Існує n! різних способів впорядкування n різних об'єктів у послідовність, перестановок цих об'єктів.[5][6]
  • Часто факторіали присутні у знаменнику формули, аби врахувати факт, що впорядкування ігнорується. Класичним прикладом є підрахунок k-комбінацій (підмножини із k елементів) із множини з n елементів. Таку комбінацію можна обравши k-перестановок: послідовно обираючи і убираючи один елемент з множини, k разів, для загального числа з
можливостей. Однак це підраховує k-комбінацій у заданому порядку, що в даному підрахунку потрібно ігнорувати; оскільки кожну k-комбінацію можна отримати k! різними способами, таким чином правильною кількістю k-комбінацій є
Це число відоме як[7] біноміальний коефіцієнт, оскільки він також є коефіцієнтом xk у (1 + x)n. Терм часто називають спадним факторіалом[en].
хоча цей вираз є неефективний для розрахунку цього числа, він може використовуватися для доведення властивості симетричності[6][7] біноміальних коефіцієнтів:
де Dn xn є нотацією Ейлера[en] для nї похідної функції xn.[10]

Швидкість зростання функції і апроксимація для великих n[ред. | ред. код]

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

Із збільшенням n, факторіал n! зростає швидше за усі поліноміальні та експоненційні функції[en] (але повільніше ніж подвійні експоненційні функції[en]) із n.

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

Графік функції f(n) = ln n! показано на малюнку праворуч. Він має приблизно лінійний вигляд для всіх розумних значень n, але це інтуїтивне сприйняття є хибним. Найпростішу апроксимацію для ln n! можна отримати обмеживши суму за допомогою інтегралу зверху і знизу наступним чином:

що дає нам наступну оцінку

Оскільки ln n! ∼ n ln n (див. Нотація великого O). Цей результат відіграє важливу роль в аналізі розрахункової складності алгоритмів сортування (див. сортування порівняннями). Із тих обмежень для ln n!, що отримані вище ми маємо

Іноді більш практичним є використання слабших але простіших оцінок. Використавши вищенаведену формулу легко показати, що для всіх n ми маємо (n3)n < n!, а для всіх n ≥ 6 ми маємо n! < (n2)n.

Порівняння апроксимації Стірлінґа із факторіалом

Для великих n ми маємо кращу оцінку для числа n! якщо використати апроксимацію Стірлінґа:

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

Інше наближення для ln n! запропонував Срініваса Рамануджан (Ramanujan, 1988)

Обидва останні наближення мають відносну похибку, що має порядок в 1n3, але апроксимація Рамануджана майже в чотири рази точніша. Однак, якщо ми використаємо два терми корекції (як у апроксимації Рамануджана) відносна похибка матиме порядок 1n5:

Розширення факторіалу до не цілих значень аргумента[ред. | ред. код]

Гамма і пі функції[ред. | ред. код]

Гамма функція інтерполює функцію факторіала для не цілих значень. Основна ідея полягає в рекурентному співвідношенні, що узагальнене до неперервної області.
Докладніше: Гамма-функція

Окрім невід'ємних цілих, факторіал також можна визначити для нецілих значень, але це потребуватиме застосування більш складних методів математичного аналізу.

Однією функцією, що "співпадає" із значеннями факторіалу (але із зсувом на 1 в аргументі), що часто використовується для його розрахунку, називається гамма функцією, і позначається як Γ(z). Вона визначена для всіх комплексних чисел z крім не від'ємних цілих, і при додатній дійсній частині z задається наступним чином

Вона пов'язана із факторіала, таким чином, що для будь-якого натурального числа n

Оригінальна формула яку запропонував Ейлер для гамма функції мала наступний вигляд

Іншою функцією що використовується, яка також "співпадає" в своїх значеннях до факторіалу (але без зсуву аргументів), є функція, яку запропонував Карл Фрідріх Гаусс, називається пі функцією, позначається як Π(z) для дійсних чисел z ≥ 0. Вона визначається наступним чином

Якщо виразити через гамма функцію, то пі функція зв'язана з нею наступним чином

Функція факторіалу, узагальнена для всіх дійсних чисел крім від'ємних цілих. Наприклад, 0! = 1! = 1, (−12)! = π, 12! = π2.

Пі функція повністю поширює факторіал до наступного:

Крім того, пі функція задовольняє тому ж правилу рекурентності що і факторіал, але для кожного комплексного значення z для якого вона визначена

Насправді, це більше не є рекурентним відношенням, а є функціональним рівнянням. Якщо виразити його в термінах гамма функції, то це функціональне рівняння прийме вигляд:

Оскільки за допомогою пі функції факторіал поширено для кожного комплексного значення z де він визначений, можна записати наступне:

Значення цих функцій для напів-цілих[en] значень таким чином визначаються однією із них; матимемо

звідки випливає, що для nN,

Наприклад,

Також маємо, що для nN,

Наприклад,

Пі функція, звичайно, не є єдиним способом розширити факторіал до вигляду функції визначеної для майже всіх комплексних значень, і навіть не є єдиною функцією, що є аналітичною у області її визначення. Однак зазвичай її розглядають як найбільш природній спосіб поширити значення факторіала до комплексної функції. Наприклад, Бор-Молерупова теорема стверджує, що гамма функція, що приймає значення 1 при 1, задовольняє функціональному рівнянню Γ(n + 1) = nΓ(n), є мероморфною для комплексних чисел, і є логарифмічно опуклою функцією у додатній частині осі дійсних чисел. Подібне твердження є дійсним так само і для пі функції, при використанні функціонального рівняння Π(n) = nΠ(n − 1).

Однак, існують комплексні функції, які імовірно простіші з точки зору теорії аналітичних функцій і які також інтерполюють значення факторіала. Наприклад, гамма функція Гадамарда[en] (Hadamard, 1894) яка, на відміну від гамма функції є цілою функцією.[11]

Ейлер також розробив збіжну апроксимацію добутків для нецілих факторіалів, яку можна розглядати еквівалентною формулою для гамма функції, наведеної вище:

Однак, ця функція не має практичного застосування для розрахунку пі функції або гама функції, швидкість її збіжності дуже мала.

Застосування гамма функції[ред. | ред. код]

Об'єм n-вимірної гіперсфери радіусом R дорівнює

Факторіал у комплексній площині[ред. | ред. код]

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

Представлення за допомогою гамма функції дозволяє розраховувати факторіал для комплексного аргументу. Ізолінії амплітуди і фази для факторіала показані на зображенні праворуч. Нехай

Показано декілька рівнів для сталого модуля (амплітуди) ρ і сталої фази φ. Сітка покриває діапазон значень −3 ≤ x ≤ 3, −2 ≤ y ≤ 2, з одиничним кроком. Виділена жирним лінія показує рівень φ = ±π.

Тонкі лінії показують проміжні рівні при сталій амплітуді і сталій фазі. В полюсах для кожного від'ємного цілого, фаза і амплітуда не визначені. Ізолінії стають густішими в околі сингулярностей здовж від'ємних цілих значень аргумента.

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

Перші коефіцієнти цього розкладання будуть наступними

n gn наближення
0 1 1
1 γ −0.5772156649
2 π212 + γ22 0.9890559955
3 ζ(3)3π212γ36 −0.9074790760

де γ це Стала Ейлера—Маскероні, а ζ(z) це Дзета-функція Рімана. Системи комп'ютерної алгебри, на кшталт SageMath можуть генерувати багато термів такого ряду.

Наближення факторіалу[ред. | ред. код]

Для великих значень аргументу, факторіал можна наблизити за допомогою інтегрування Дигамма-функції, використавши представлення у формі ланцюгового дробу. Це наближення запропонував Т. Ж. Стілтьєс[en] (1894). Маючи z! = eP(z) де P(z) є

Стілтьєс запропонував ланцюговий дріб для p(z):

Перші декілька коефіцієнтів an виглядатимуть наступним чином:[12]

n an
0 112
1 130
2 53210
3 195371
4 22 99922 737
5 29 944 52319 733 142
6 109 535 241 00948 264 275 462

Існує невірне уявлення про те, що рівняння ln z! = P(z) або ln Γ(z + 1) = P(z) є вірним для будь-яких комплексних значень z ≠ 0. Насправді, відношення задане через логарифм є дійсним лише на певному відрізку значень z в околі осі дійсних значень, де −π < Im(Γ(z + 1)) < π. Чим більшою є дійсна частина аргументу тим меншою має бути уявна частина. Однак, обернене відношення, z! = eP(z), є вірним для всієї комплексної площини значень крім z = 0. Збіжність буде слабшою в околі від'ємної частини осі дійсних значень; також важко мати хорошу збіжність будь-якого наближення біля точок сингулярностей. Коли |Im z|>2 або Re z > 2, шести коефіцієнтів буде вдосталь для розрахунку факторіалу комплексного числа із подвійною точністю. Для більшої точності знадобиться розрахувати більшу кількість коефіцієнтів за допомогою раціональної схеми QD (QD алгоритм Рутісгаузера).[13]

Від'ємні цілі аргументи[ред. | ред. код]

Відношення n! = n × (n − 1)! дозволяє розрахувати факторіал заданого цілого числа у випадку не великих значень. Це співвідношення можна переписати таким чином, аби мати можливість розрахувати факторіал для відносно великих цілих чисел:

Однак використати цю рекурсію не можливо, якщо необхідно розрахувати факторіал для від'ємного цілого числа; якщо використати цю формулу для розрахунку (−1)! ми отримаємо операцію Ділення на нуль, і таким чином це не дозволяє розрахувати факторіал для будь-якого цілого від'ємного числа. Аналогічно тому, гамма-функція також є невизначеною для нуля або від'ємних цілих, хоча вона є визначеною для всіх інших комплексних чисел.

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Graham, Knuth та Patashnik, 1988, с. 111
  2. Biggs, Norman L. (May 1979). The roots of combinatorics. Historia Mathematica 6 (2): 109–136. ISSN 0315-0860. doi:10.1016/0315-0860(79)90074-0 — через ScienceDirect. 
  3. Stedman, 1677, с. 6–9
  4. Higgins, 2008, с. 12
  5. Cheng, Eugenia (2017-03-09). Beyond Infinity: An expedition to the outer limits of the mathematical universe (en). Profile Books. ISBN 9781782830818. 
  6. а б Conway, John H.; Guy, Richard (1998-03-16). The Book of Numbers (en). Springer Science & Business Media. ISBN 9780387979939. 
  7. а б Knuth, Donald E. (1997-07-04). The Art of Computer Programming: Volume 1: Fundamental Algorithms (en). Addison-Wesley Professional. ISBN 9780321635747. 
  8. 18.01 Single Variable Calculus, Lecture 37: Taylor Series. MIT OpenCourseWare. Fall 2006. Архів оригіналу за 2018-04-26. Процитовано 2017-05-03. 
  9. Kardar, Mehran (2007-06-25). Chapter 2: Probability. Statistical Physics of Particles (English). Cambridge University Press. с. 35–56. ISBN 9780521873420. 
  10. 18.01 Single Variable Calculus, Lecture 4: Chain rule, higher derivatives. MIT OpenCourseWare. Fall 2006. Архів оригіналу за 2018-04-26. Процитовано 2017-05-03. 
  11. Luschny, Peter. Hadamard versus Euler – Who found the better Gamma function?. Архів оригіналу за 2009-08-18. 
  12. 5.10. Digital Library of Mathematical Functions. Архів оригіналу за 2010-05-29. Процитовано 2010-10-17. 
  13. Luschny, Peter. On Stieltjes' Continued Fraction for the Gamma Function. Архів оригіналу за 2011-05-14.