Факторіал

Обрані числа із факторіальної послідовності (Шаблон:OEIS); значення наведені в науковій нотації округлені до наведеної точності

Шаблон:Math	Шаблон:Math
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	Шаблон:Val
8	Шаблон:Val
9	Шаблон:Val
10	Шаблон:Val
11	Шаблон:Val
12	Шаблон:Val
13	Шаблон:Val
14	Шаблон:Val
15	Шаблон:Val
16	Шаблон:Val
17	Шаблон:Val
18	Шаблон:Val
19	Шаблон:Val
20	Шаблон:Val
25	Шаблон:Val
50	Шаблон:Val
70	Шаблон:Val
100	Шаблон:Val
450	Шаблон:Val
Шаблон:Val	Шаблон:Val
Шаблон:Val	Шаблон:Val
Шаблон:Val	Шаблон:Val
Шаблон:Val	Шаблон:Val
Шаблон:Val	Шаблон:Val
Шаблон:Val	Шаблон:Val
Шаблон:Val	Шаблон:Val
[[Гугол|Шаблон:Val]]	10Шаблон:Val

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

Шаблон:Center За означенням $0!=1$, згідно з конвенцією для порожнього добутку.Шаблон:Sfn.

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

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

Історія

Індійські науковці використовували факторіали для підрахунку перестановок ще в 12-му столітті. В 1677, Шаблон:Нп описав застосування факторіалів для узгодження Шаблон:Нп, музичного мистецтва із використанням багатьох підібраних налаштованих дзвонів.Шаблон:Sfn Після описання рекурсивного методу, Стедмен приводить визначення факторіалу.

Математичний запис Шаблон:Math було запропонована французьким математиком Шаблон:Нп у 1808.

Визначення

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

$n!=1\cdot 2\cdot 3\cdot \dots \cdot (n-2)\cdot (n-1)\cdot n,$

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

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

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

$n!=n\cdot (n-1)!.$

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

$\begin{array}{cc}5!& =5\cdot 4!\\ 6!& =6\cdot 5!\\ 50!& =50\cdot 49!\end{array}$

і так далі.

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

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

$0!=1$

Так що

$1!=1\cdot 0!=1.$

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

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

$(\genfrac{}{}{0ex}{}{0}{0})=\frac{0!}{0!0!}=1$.

В більш загальному випадку, кількість різних способів впорядкувати всі Шаблон:Mvar елементи із множини з Шаблон:Mvar елементів дорівнюватиме

$(\genfrac{}{}{0ex}{}{n}{n})=\frac{n!}{n!0!}=1$.

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

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

Факторіал не цілого числа

Функцію факторіалу також можна визначити для не цілих чисел з використанням більш складних математичних понять (за допомогою гамма-функції Шаблон:Math). Це більш загальне визначення використовується в інженерних калькуляторах і в математичному програмному забезпеченні такому як 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!=\{\begin{array}{cc}1& n=0,\\ n\cdot (n-1)!& n>0.\end{array}$

Комбінаторна інтерпретація

В комбінаториці факторіал натурального числа 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, оскільки порожня множина може бути впорядкованою лише одним способом.

Зв'язок з гамма-функцією

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

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

Формула Стірлінга

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

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

Подвійний факторіал

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

Застосування

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

• Існує Шаблон:Math різних способів впорядкування Шаблон:Mvar різних об'єктів у послідовність, перестановок цих об'єктів.
• Часто факторіали присутні у знаменнику формули, аби врахувати факт, що впорядкування ігнорується. Класичним прикладом є підрахунок Шаблон:Mvar-комбінацій (підмножини із Шаблон:Mvar елементів) із множини з Шаблон:Mvar елементів. Таку комбінацію можна обравши Шаблон:Mvar-перестановок: послідовно обираючи і убираючи один елемент з множини, Шаблон:Mvar разів, для загального числа з

$(n-0)(n-1)(n-2)\cdots (n-(k-1))=\frac{n!}{(n-k)!}=n^{\underset{\_}{k}}$

можливостей. Однак це підраховує Шаблон:Mvar-комбінацій у заданому порядку, що в даному підрахунку потрібно ігнорувати; оскільки кожну Шаблон:Mvar-комбінацію можна отримати Шаблон:Math різними способами, таким чином правильною кількістю Шаблон:Mvar-комбінацій є

$\frac{n(n-1)(n-2)\cdots (n-k+1)}{k(k-1)(k-2)\cdots 1}=\frac{n^{\underset{\_}{k}}}{k!}=\frac{n!}{(n-k)!k!}=(\genfrac{}{}{0ex}{}{n}{k}).$

Це число відоме як біноміальний коефіцієнт, оскільки він також є коефіцієнтом Шаблон:Math у Шаблон:Math. Терм $n^{\underset{\_}{k}}$ часто називають Шаблон:Нп.

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

$n^{\underset{\_}{k}}=\frac{n!}{(n-k)!};$

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

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n^{\underset{\_}{k}}}{k!}=\frac{n!}{(n-k)!k!}=\frac{n^{\underset{\_}{n-k}}}{(n-k)!}=(\genfrac{}{}{0ex}{}{n}{n-k}).$

• За допомогою Шаблон:Нп можна показати, що функція факторіалу є

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

де Шаблон:Math є нотацією Ейлера для Шаблон:Mvarї похідної функції Шаблон:Math.

Швидкість зростання функції і апроксимація для великих Шаблон:Mvar

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

Із збільшенням Шаблон:Mvar, факторіал Шаблон:Math зростає швидше за усі поліноміальні та експоненційні функції (але повільніше ніж Шаблон:Нп) із Шаблон:Mvar.

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

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

Графік функції Шаблон:Math показано на малюнку праворуч. Він має приблизно лінійний вигляд для всіх розумних значень Шаблон:Mvar, але це інтуїтивне сприйняття є хибним. Найпростішу апроксимацію для Шаблон:Math можна отримати обмеживши суму за допомогою інтегралу зверху і знизу наступним чином:

$\underset{1}{\overset{n}{\int }}\ln xdx\le \sum _{x=1}^n\ln x\le \underset{0}{\overset{n}{\int }}\ln (x+1)dx$

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

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

Оскільки Шаблон:Math (див. [[Нотація Ландау|Нотація великого Шаблон:Mvar]]). Цей результат відіграє важливу роль в аналізі розрахункової складності алгоритмів сортування (див. сортування порівняннями). Із тих обмежень для Шаблон:Math, що отримані вище ми маємо

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

Іноді більш практичним є використання слабших, але простіших оцінок. Використавши вищенаведену формулу легко показати, що для всіх Шаблон:Mvar ми маємо Шаблон:Math, а для всіх Шаблон:Math ми маємо Шаблон:Math.

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

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

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

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

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

Інше наближення для Шаблон:Math запропонував Срініваса Рамануджан Шаблон:Harv

$\begin{array}{cc}\ln n!& \approx n\ln n-n+\frac{\ln \left(n\right(1+4n(1+2n)\left)\right)}{6}+\frac{\ln \pi }{2}\\ [6px]⟹n!& \approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n{(1+\frac{1}{2n}+\frac{1}{8n^2})}^{\frac{1}{6}}.\end{array}$

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

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

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

Гамма і пі функції

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

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

Однією функцією, що «збігається» зі значеннями факторіалу (але із зсувом на 1 в аргументі), що часто використовується для його розрахунку, називається гамма-функцією, і позначається як Шаблон:Math. Вона визначена для всіх комплексних чисел Шаблон:Mvar крім не від'ємних цілих, і при додатній дійсній частині Шаблон:Mvar задається наступним чином

$\mathrm{\Gamma }(z)=\underset{0}{\overset{\mathrm{\infty }}{\int }}{t}^{z-1}{e}^{-t}dt.$

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

$n!=\mathrm{\Gamma }(n+1).$

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

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

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

$\mathrm{\Pi }(z)=\underset{0}{\overset{\mathrm{\infty }}{\int }}{t}^z{e}^{-t}dt.$

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

$\mathrm{\Pi }(z)=\mathrm{\Gamma }(z+1).$

Функція факторіалу, узагальнена для всіх дійсних чисел крім від'ємних цілих. Наприклад, Шаблон:Nowrap, Шаблон:Nowrap, Шаблон:Nowrap.

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

$n!=\mathrm{\Pi }(n)\text{ для }n\in 𝐍.$

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

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

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

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

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

$z!=\mathrm{\Pi }(z)$

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

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

звідки випливає, що для Шаблон:Math,

$\begin{array}{cc}& \mathrm{\Gamma }(\frac{1}{2}+n)=(-\frac{1}{2}+n)!=\mathrm{\Pi }(-\frac{1}{2}+n)\\ =& \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{array}$

Наприклад,

$\mathrm{\Gamma }\left(\frac{9}{2}\right)=\frac{7}{2}!=\mathrm{\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.631728\dots$

Також маємо, що для Шаблон:Math,

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

Наприклад,

$\mathrm{\Gamma }(-\frac{5}{2})=(-\frac{7}{2})!=\mathrm{\Pi }(-\frac{7}{2})=\frac{2}{-1}\cdot \frac{2}{-3}\cdot \frac{2}{-5}\sqrt{\pi }=\frac{{(-4)}^{3}3!}{6!}\sqrt{\pi }=-\frac{8}{15}\sqrt{\pi }\approx -0.945308\dots$

Пі функція, звичайно, не є єдиним способом розширити факторіал до вигляду функції визначеної для майже всіх комплексних значень, і навіть не є єдиною функцією, що є аналітичною у області її визначення. Однак зазвичай її розглядають як найбільш природний спосіб поширити значення факторіала до комплексної функції. Наприклад, Бор-Молерупова теорема стверджує, що гамма-функція, що приймає значення 1 при 1, задовольняє функціональному рівнянню Шаблон:Math, є мероморфною для комплексних чисел, і є логарифмічно опуклою функцією у додатній частині осі дійсних чисел. Подібне твердження є дійсним так само і для пі функції, при використанні функціонального рівняння Шаблон:Math.

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

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

$\begin{array}{cc}n!=\mathrm{\Pi }(n)& =\prod _{k=1}^{\mathrm{\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{array}$

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

Застосування гамма-функції

Об'єм [[Розмірність простору|Шаблон:Mvar-вимірної]] гіперсфери радіусом Шаблон:Mvar дорівнює

$V_n=\frac{{\pi }^{\frac{n}{2}}}{\mathrm{\Gamma }(\frac{n}{2}+1)}{R}^n.$

Факторіал у комплексній площині

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

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

$f=\rho e^{i\phi }=(x+\mathrm{i}y)!=\mathrm{\Gamma }(x+iy+1).$

Показано декілька рівнів для сталого модуля (амплітуди) Шаблон:Mvar і сталої фази Шаблон:Mvar. Сітка покриває діапазон значень Шаблон:Math, Шаблон:Math, з одиничним кроком. Виділена жирним лінія показує рівень Шаблон:Math.

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

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

$z!=\sum _{n=0}^{\mathrm{\infty }}{g}_n{z}^n.$

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

Шаблон:Mvar	Шаблон:Mvar	наближення
0	1	1
1	Шаблон:Math	Шаблон:Val
2	Шаблон:Math	Шаблон:Val
3	Шаблон:Math	Шаблон:Val

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

Наближення факторіалу

Для великих значень аргументу, факторіал можна наблизити за допомогою інтегрування дигамма-функції, використавши представлення у формі ланцюгового дробу. Це наближення запропонував Т. Ж. Стілтьєс (1894). Маючи Шаблон:Math де Шаблон:Math є

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

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

$p(z)=\frac{a_0}{z+\frac{a_1}{z+\frac{a_2}{z+\frac{a_3}{z+\ddots }}}}$

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

Шаблон:Math	Шаблон:Math
0	Шаблон:Sfrac
1	Шаблон:Sfrac
2	Шаблон:Sfrac
3	Шаблон:Sfrac
4	Шаблон:Sfrac
5	Шаблон:Sfrac
6	Шаблон:Sfrac

Існує невірне уявлення про те, що рівняння Шаблон:Math або Шаблон:Math є вірним для будь-яких комплексних значень Шаблон:Math. Насправді, відношення задане через логарифм є дійсним лише на певному відрізку значень Шаблон:Mvar в околі осі дійсних значень, де Шаблон:Math. Чим більшою є дійсна частина аргументу тим меншою має бути уявна частина. Однак, обернене відношення, Шаблон:Math, є вірним для всієї комплексної площини значень крім Шаблон:Math. Збіжність буде слабшою в околі від'ємної частини осі дійсних значень; також важко мати хорошу збіжність будь-якого наближення біля точок сингулярностей. Коли |Im z|>2 або Шаблон:Math, шести коефіцієнтів буде вдосталь для розрахунку факторіалу комплексного числа із подвійною точністю. Для більшої точності знадобиться розрахувати більшу кількість коефіцієнтів за допомогою раціональної схеми QD (QD алгоритм Рутісгаузера).

Від'ємні цілі аргументи

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

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

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

Див. також

• Факторизація

Література

• Шаблон:Фіхтенгольц.укр