Факторіал
Вступ до факторіала
Факторіал, що позначається як \(n!\), представляє добуток усіх додатних цілих чисел від \(1\) до \(n\). Простіше кажучи, для заданого невивідничого цілого числа факторіал цього числа обчислюється шляхом множення всіх додатних цілих чисел від \(1\) до \(n\).
\begin{align*} n! &= n \times (n-1) \times (n-2) \times … \times 2 \times 1 \\ &= n \times (n-1)! \end{align*}
Наприклад:
\[4! = 4 \times 3! = 4 \times 3 \times 2 \times 1 \ = 24\]
За домовленістю, факторіал \(0\) дорівнює \(1\).
Означення
У більш формальних термінах, факторіал додатного цілого числа \(n\) можна виразити через наступну рекурсивну функцію:
\[ n! = \begin{cases} n \times (n-1)! & \text{ якщо } n \in \mathbb{N} \quad n \gt 0\\[1em] 1 & \text{ якщо } n = 0 \end{cases} \]
Факторіал також можна записати компактніше як добуток \(\prod\) значень \(k\), що ітеруються від \(k=1\) до \(k=n\). Формула факторіала у компактному вигляді має такий вигляд:
\[ n! = \begin{cases} \displaystyle{\prod_{k=1}^{n} k} & \text{ якщо } n \in \mathbb{N} \quad n \gt 0\\[1em] 1 & \text{ якщо } n = 0 \end{cases} \]
Формула факторіала використовується для обчислення біноміального коефіцієнта, який представляє кількість способів вибрати певну кількість елементів із більшої множини.
Спрощення відношень факторіалів
Відношення факторіалів часто зустрічаються в комбінаториці та теорії ймовірностей. Коли два факторіали мають спільну структуру, більшість множників скорочуються, і вираз зводиться до скінченного добутку. Нехай задано два цілих числа \(n\) та \(k\), при цьому \(n > k\):
\[ \frac{n!}{(n-k)!} = n \times (n-1) \times (n-2) \times \cdots \times (n-k+1) \]
Знаменник скорочує всі множники від \((n-k)\) вниз до \(1\), залишаючи рівно \(k\) членів у чисельнику.
Приклад
Обчислити відношення: \[\frac{10!}{5!}\]
У цьому прикладі \(n=10\) та \(n -k=5\). За означенням факторіала ми отримаємо:
\begin{align} \frac{10!}{5!} & = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot \overbrace{ 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}^{5!}}{\underbrace{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}_{5!}}\\[1em] &= \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 !}{5 !} \\[0.6em] &= 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \\[1em] &= 30240 \end{align}
Останній член відповідає \(n -k +1\), тобто \(10 -5 + 1 = 6\).
Розв'язання: \[\frac{10!}{5!} = 30240\]
Факторіал у комбінаториці
У комбінаториці факторіал \(n!\) визначає кількість різних перестановок \(n\) об'єктів. Наприклад, розташування 3 різних об'єктів дає \(3! = 6\) можливих варіантів:
\begin{array}{rrrr} & o_1 & o_2 & o_3 \\ \hline & 1 & 2 & 3 \\ & 1 & 3 & 2 \\ & 2 & 1 & 3 \\ & 2 & 3 & 1 \\ & 3 & 1 & 2 \\ & 3 & 2 & 1 \\ \end{array}
Коли порядок вибору не має значення, багато з цих варіантів стають еквівалентними. Вибір об'єктів \(1, 2, 3\) є таким самим, як вибір \(3, 2, 1\) або будь-якого іншого розташування тих самих трьох елементів. Щоб підрахувати лише різні вибори, потрібно поділити на \(k!\) перестановок обраних об'єктів, що призводить до біноміального коефіцієнта:
\[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \]
Корисна тотожність із факторіалом
Виходячи з означення факторіала, \( n! = n \cdot (n – 1)! \), ми можемо виділити \( n \) і поділити обидві частини на \( n! \). Це призводить до тотожності:
\[ \frac{n}{n!} = \frac{1}{(n – 1)!} \]
Ця тотожність широко використовується в багатьох алгебраїчних та імовірнісних контекстах, де з'являються факторіали. Вона допомагає спростити вирази, що містять \( n! \), і полегшує коригування індексу підсумовування при роботі з рядами або дискретними імовірнісними моделями. Цей простий зв'язок часто виявляється корисним у практичних виводах, наприклад, при обчисленні середнього значення розподілу Пуассона або спрощенні вигляду біноміальних коефіцієнтів.
Зв'язок між факторіалом та гамма-функцією
Існує глибокий зв'язок між факторіалом та гамма-функцією. Факторіал застосовується лише до натуральних чисел, тоді як гамма-функція поширює цю ж ідею на всі додатні дійсні значення, створюючи його гладку та неперервну версію. Для будь-якого \( c \in \mathbb{R}^+ \) гамма-функція визначається інтегралом:
\[ \Gamma(c) = \int_{0}^{+\infty} x^{c - 1} e^{-x} \, dx \]
Коли аргумент є цілим числом, гамма-функція відтворює факторіал відповідно до тотожності:
\[ \Gamma(n) = (n - 1)! \]
У цьому сенсі факторіал можна розглядати як дискретний випадок гамма-функції.
Та сама функція також з'являється в означенні бета-розподілу, де вона забезпечує нормалізуючу сталу, яка гарантує, що повна ймовірність дорівнює одиниці.
Наближення Стірлінга
Для великих значень \(n\) пряме обчислення \(n!\) стає непрактичним. Факторіал зростає швидше за будь-який поліном і швидше за будь-яку показникову функцію: як показує таблиця нижче, навіть при \(n = 15\) він уже перевищує один мільярд, тоді як \(2^n\) все ще перебуває в межах десятків тисяч.
| \(n\) | Поліном \(n^2\) | Показникова функція \(2^n\) | Факторіал \(n!\) |
|---|---|---|---|
| 2 | 4 | 4 | 2 |
| 5 | 25 | 32 | 120 |
| 10 | 100 | 1,024 | 3,628,800 |
| 15 | 225 | 32,768 | ~1.307 мільярда |
Наближення Стірлінга дає точну асимптотичну оцінку:
\[ n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n \]
де \(e\) — число Ейлера. Це асимптотичний результат у строгому сенсі: відносна похибка прямує до нуля, коли \(n\) необмежено зростає:
\[ \lim_{n \to \infty} \frac{n!}{\sqrt{2\pi n}\left(\dfrac{n}{e}\right)^n} = 1 \]
і наближення стає дедалі точнішим зі збільшенням \(n\). Для \(n = 10\) точне значення становить \(10! = 3{,}628{,}800\), тоді як формула Стірлінга дає приблизно \(3{,}598{,}696\), що становить похибку менше \(1%\). Для \(n = 100\) відносна похибка падає нижче \(0.1%\). Удосконалена версія наближення включає поправочний член:
\[ n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n \left(1 + \frac{1}{12n}\right) \]
Наближення Стірлінга з'являється в асимптотичному аналізі біноміальних коефіцієнтів, в обчисленнях ентропії в статистичній механіці та в оцінках швидкості збіжності в теорії ймовірностей.