Біноміальний коефіцієнт
Вступ до біноміального коефіцієнта
Біноміальний коефіцієнт позначає кількість способів вибрати певну кількість елементів \(k\) з більшої множини з \(n\) елементів, не враховуючи порядок вибору. У комбінаториці біноміальний коефіцієнт позначається як \(n\) по \(k.\) Формула для біноміального коефіцієнта має вигляд:
\[ \binom{n}{k} = \begin{cases} \displaystyle\frac{n!}{k!\,(n-k)!} & \text{якщо } 0 \leq k \leq n \\[1em] 0 & \text{якщо } k > n \end{cases} \]
- \(n\) представляє загальну кількість елементів у множині.
- \(k\) позначає кількість елементів, які необхідно вибрати.
- \(n!\) та \((n-k)!\) представляють факторіал натуральних чисел \(n\) та \((n-k)!\).
Щоб визначити значення біноміального коефіцієнта \( \large{4 \choose 2} \), ми підрахуємо кількість пар, які можна створити з множини з чотирьох елементів. Розглянемо множину \(P=(p,q,r,s)\). Кількість підмножин, утворених двома елементами, дорівнює шести. Ці підмножини:
\[ (p,q) \quad (p,r) \quad (p,s) \quad (q,r) \quad (q,s) \quad (r,s) \]
Порядок тут не відіграє ролі. Пара \((p,q)\) та пара \((q,p)\) стосуються одного і того ж вибору, тому вони рахуються як одна. Саме це відрізняє сполучення від перестановки — і саме це враховує формула.
Чисельник \( \frac{n!}{(n-k)!} \) підраховує впорядковані послідовності з \( k \) елементів, вибраних із множини з \( n \): це кількість перестановок. Оскільки порядок не має значення, кожна невпорядкована підмножина з'являється \( k! \) разів у цьому підрахунку — по одному разу для кожного способу розташування її елементів. Ділення на \( k! \) усуває надмірний підрахунок:
\[ \binom{n}{k} = \frac{n!}{(n-k)!} \cdot \frac{1}{k!} = \frac{n!}{k!\,(n-k)!} \]
що і є виразом, наведеним вище.
Біноміальний коефіцієнт з'являється в біноміальній теоремі, де він представляє коефіцієнти кожного члена у розкладанні \( (a + b)^n \).
Трикутник Паскаля
Трикутник Паскаля — це візуальне представлення біноміальних коефіцієнтів. Коротко кажучи, це геометричне розташування біноміальних коефіцієнтів, які є коефіцієнтами при розкладанні бінома \( (a + b) \), піднесеного до будь-якого степеня \( n \).
Трикутник будується за наступними правилами. Перший рядок містить лише 1. Кожне число в наступних рядках є сумою двох чисел, що знаходяться безпосередньо над ним. Найкрайні елементи завжди дорівнюють 1. Ось перші шість рядків:
\[ \begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1 \end{array} \]
Кожен елемент у рядку \( n \) та стовпці \( k \) відповідає біноміальному коефіцієнту. Наприклад, число при \( n = 4, k = 2 \) дорівнює:
\[ \binom {4}{2} = \frac{4!}{2!(4 – 2)!} = \frac{4!}{2!2!} = \frac{24}{4} = 6 \]
І дійсно, у четвертому рядку третє число — 6.
Трикутник Паскаля задовольняє рекурентне співвідношення:
\[ \binom{n}{k} = \binom{n – 1}{k – 1} + \binom{n - 1}{k} \]
що безпосередньо випливає з побудови трикутника.
Фундаментальні властивості біноміального коефіцієнта
Властивість краю біноміального коефіцієнта виражає базове правило, що проявляється вздовж меж трикутника Паскаля. Вона стверджує, що коефіцієнти, розташовані на двох кінцях кожного рядка, завжди дорівнюють одиниці:
\[ \binom{n}{0} = \binom{n}{n} = 1 \]
Для будь-якого натурального числа \( n \) існує рівно один можливий спосіб не обрати жодного з доступних елементів, і так само лише один спосіб обрати їх усі.
Властивість симетрії спостерігається при виборі підмножини з \(k\) елементів із множини з \(n\) елементів, причому кількість способів зробити це завжди дорівнює кількості способів обрати решту \(n-k\) елементів. Ця симетрія відображена в еквівалентності:
\[ \binom{n}{k} = \binom{n}{n-k} \]
Цей принцип симетричного вибору є не просто теоретичною ідеєю, а практичним інструментом, що використовується в різних галузях. Він особливо корисний у теорії ймовірностей, комбінаториці та статистиці, де допомагає обчислювати ймовірності, підраховувати варіанти та аналізувати дані.
Адитивна властивість біноміального коефіцієнта встановлює зв'язок між послідовними біноміальними коефіцієнтами. Якщо розглянемо біноміальні коефіцієнти \( \large{n \choose k} \) та \( \large{{n \choose k+1}}\), то:
\[{n \choose k} + {n \choose k+1} = {n+1 \choose k+1} \]
Ця властивість є фундаментальною в практичних застосуваннях, оскільки вона дає спосіб швидко обчислити значення наступного біноміального коефіцієнта, знаючи попередні. Вона ґрунтується на означенні біноміального коефіцієнта та його рекурентному зв'язку, що дозволяє виразити біноміальний коефіцієнт через попередні біноміальні коефіцієнти.
Рекурентна властивість описує, як кожен біноміальний коефіцієнт може бути отриманий з коефіцієнтів попереднього рядка трикутника Паскаля. Згідно з цим зв'язком, кожен коефіцієнт отримується як сума двох елементів, розташованих безпосередньо над ним:
\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]
Це правило надає рекурентне означення для біноміального коефіцієнта та пояснює адитивну структуру, що лежить в основі трикутника Паскаля.
Помітні тотожності біноміального коефіцієнта
Окрім основних властивостей, біноміальний коефіцієнт задовольняє низку глибших тотожностей, які неодноразово зустрічаються в комбінаториці, теорії ймовірностей та аналізі. Кожна з них відображає структурну істину про те, як працює підрахунок.
Тотожність суми рядка стверджує, що сума всіх біноміальних коефіцієнтів у рядку \( n \) трикутника Паскаля дорівнює \( 2^n \):
\[ \sum_{k=0}^{n} \binom{n}{k} = 2^n \]
Один зі способів зрозуміти, чому це так: розглянемо множину з \( n \) елементів. Кожен елемент може бути або включений у підмножину, або ні, що дає два незалежних вибори для кожного елемента. Загальна кількість підмножин, отже, становить \( 2^n \), і оскільки \( \binom{n}{k} \) підраховує підмножини рівно з \( k \) елементів, підсумовування по всіх можливих значеннях \( k \) від \( 0 \) до \( n \) відновлює той самий підрахунок.
Тотожність знакоперемінної суми є близькою родичкою суми рядка, але зі знакоперемінними знаками:
\[ \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \]
Це випливає безпосередньо з обчислення біноміальної теореми при \( a = 1 \) та \( b = -1 \). Результат відображає симетрію між підмножинами парного та непарного розміру: для будь-якого \( n \geq 1 \) кількість підмножин парного розміру множини з \( n \) елементів точно дорівнює кількості підмножин непарного розміру.
Тотожність Вандермонде описує, що відбувається, коли два незалежних вибори об'єднуються в один. Дано дві розривні групи з \( m \) та \( n \) елементів відповідно, тоді кількість способів обрати \( r \) елементів із об'єднаної групи дорівнює:
\[ \binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} \]
Міркування пряме: будь-який вибір \( r \) елементів із об'єднаної групи повинен містити рівно \( k \) елементів із першої групи та \( r - k \) із другої, для деякого значення \( k \) від \( 0 \) до \( r \). Кожен такий розподіл дає \( \binom{m}{k} \cdot \binom{n}{r-k} \) комбінацій, і підсумовування по всіх допустимих значеннях \( k \) дає загальний результат. Особливо корисний спеціальний випадок виникає, коли \( m = n \) та \( r = n \):
\[ \binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^2 \]
Це говорить нам, що центральний біноміальний коефіцієнт — середній запис рядка \( 2n \) у трикутнику Паскаля — підраховує кількість способів обрати \( n \) елементів із групи з \( 2n \), що завжди може бути розкладено як вибір \( k \) з однієї половини та \( n - k \) з іншої.
Тотожність верхньої суми пов'язує біноміальний коефіцієнт із сумою коефіцієнтів із попередніх рядків:
\[ \sum_{i=0}^{r} \binom{n+i}{i} = \binom{n+r+1}{r} \]
Назва походить від форми, яку ця тотожність описує в трикутнику Паскаля: діагональний ряд записів, сума яких дорівнює одному запису на один крок праворуч і на один крок вниз — що нагадує лезо та руків'я хокейного ключки. Ця тотожність особливо корисна при обчисленні кумулятивних підрахунків, що будуються рядок за рядком.
Узагальнений біноміальний коефіцієнт
Означення, введене на початку цієї сторінки, вимагає, щоб \( n \) та \( k \) були натуральними числами. Однак це обмеження не є таким суворим, як здається. Факторіал у чисельнику можна замінити добутком, який має сенс для будь-якого дійсного числа \( \alpha \), що призводить до узагальненого біноміального коефіцієнта:
\[ \binom{\alpha}{k} = \frac{\alpha(\alpha – 1)(\alpha - 2) \cdots (\alpha - k + 1)}{k!} \]
де \( \alpha \in \mathbb{R} \), а \( k \) залишається цілим невід'ємним числом. Коли \( \alpha \) є натуральним числом і \( k \leq \alpha \), цей вираз зводиться до стандартного біноміального коефіцієнта. Коли \( \alpha \) не є натуральним числом або коли \( k > \alpha \), він дає значення, які більше не є цілими, але залишаються добре визначеними. Саме це узагальнення дозволяє біноміальній теоремі поширюватися на показники, що не є цілими числами. Для \( |x| < 1 \) Ньютон показав, що:
\[ (1 + x)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k \]
На відміну від стандартної біноміальної теореми, ця сума не є скінченною і є нескінченним рядом. Варто відзначити два випадки. При \( \alpha = -1 \) ми отримуємо геометричний ряд:
\[ \frac{1}{1+x} = \sum_{k=0}^{\infty} (-1)^k x^k \]
При \( \alpha = \tfrac{1}{2} \) отримуємо розклад \( \sqrt{1+x} \):
\[ \sqrt{1+x} = 1 + \frac{1}{2}x - \frac{1}{8}x^2 + \frac{1}{16}x^3 - \cdots \]
це наближення, яке рутинно використовується у фізиці та інженерії, коли \( x \) є малим. В обох випадках коефіцієнти обчислюються безпосередньо з узагальненого біноміального коефіцієнта (та сама формула, але \( \alpha \) більше не обмежене цілим числом).
Приклад 1
Дослідницька група складається з 7 науковців та 8 інженерів. Скількома способами можна сформувати робочу групу, що складається з 3 науковців та 4 інженерів? Щоб сформувати групу, ми повинні незалежно вибрати 3 науковців із 7 та 4 інженерів із 8. Оскільки ці два вибори є незалежними, загальна кількість можливих комбінацій визначається як:
\[ N = \binom{7}{3} \times \binom{8}{4} \]
Тепер обчислимо кожен член:
\[ \binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35 \]
\[ \binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70 \]
Отже, комбінуючи можливі вибори науковців та інженерів, ми отримаємо:
\[ N = 35 \times 70 = 2450 \]
Це означає, що, виходячи з нашої групи науковців та інженерів, ми можемо сформувати 2 450 різних робочих команд, що складаються з 3 науковців та 4 інженерів.
Приклад 2
Тепер розглянемо ту саму ситуацію, що описана в Прикладі 1, але з додатковою умовою: якщо 2 інженери мають розбіжності та не можуть бути призначені в одну групу, скільки допустимих комбінацій можна сформувати? Ми вже знаємо, що загальна кількість можливих груп без будь-яких обмежень становить 2450.
Тепер ми повинні виключити групи, які включають обох інженерів, що не можуть працювати разом. Якщо обидва конфліктні інженери включені в одну групу, ми вже вибрали 2 конкретних інженерів, тому нам потрібно вибрати лише решту 2 інженерів з інших 6:
\[ \binom{6}{2} \]
Водночас нам все ще потрібно вибрати 3 науковців із 7 доступних:
\[ \binom{7}{3} \]
Кількість недопустимих груп, що містять обох конфліктних інженерів, отже становить:
\[ N_{\text{invalid}} = \binom{7}{3} \times \binom{6}{2} \]
Підставимо значення, які ми маємо:
\[ \binom{7}{3} = 35 \qquad \binom{6}{2} = 15 \]
\[ N_{\text{invalid}} = 35 \times 15 = 525 \]
Нарешті, віднімемо ці недопустимі випадки від загальної кількості, щоб знайти кількість допустимих комбінацій:
\[ N_{\text{valid}} = N_{\text{total}} – N_{\text{invalid}} = 2450 - 525 = 1925 \]
Існує 1 925 допустимих комбінацій, якщо двоє конфліктних інженерів не можуть бути призначені в одну групу.
Рекурсія
Біноміальний коефіцієнт має природну рекурсивну структуру: щоб обчислити кількість способів вибору \( k \) елементів із \( n \), достатньо знати відповіді на дві менші версії тієї самої задачі.
\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]
Обґрунтування є комбінаторним. Зафіксуємо один елемент із множини — назвемо його \( x \). Кожна підмножина розміром \( k \) або містить \( x \), або не містить його. Якщо містить, то решта \( k-1 \) елементів мають бути обрані з інших \( n-1 \), що дає \( \binom{n-1}{k-1} \). Якщо не містить, то всі \( k \) елементів обираються з решти \( n-1 \), що дає \( \binom{n-1}{k} \). Ці два випадки є взаємовиключними і разом охоплюють усі можливості. Наприклад:
\[ \binom{3}{2} = \binom{2}{1} + \binom{2}{2} = 2 + 1 = 3 \]
Ця тотожність є особливо корисною при обчисленнях, оскільки рекурсія не нав'язана задачі ззовні: вона вже закладена в математиці. Рекурсивна функція лише слідує цій структурі безпосередньо, зводячи кожен виклик до двох менших, доки не будуть досягнуті базові випадки:
\[ \binom{n}{0} = \binom{n}{n} = 1 \]
public static int binomialCoefficient(int n, int k) {
if (k == 0 || k == n) return 1;
return binomialCoefficient(n - 1, k - 1) + binomialCoefficient(n - 1, k);
}Зауважимо, що ця реалізація, хоч і є прозорою, багатократно переобчислює одні й ті самі значення. Обчислювальна складність швидко зростає зі збільшенням \( n \), і цю проблему вирішує мемоїзація шляхом збереження проміжних результатів у міру їх обчислення. Цей компроміс між простотою та ефективністю детально розглянуто в аналізі нотації Big O.
Основи біноміального розподілу
Біноміальний коефіцієнт є основою для біноміального розподілу, який описує ймовірність отримання певної кількості успіхів у фіксованій кількості незалежних випробувань. Якщо кожне випробування має лише два можливі результати — успіх з ймовірністю \( p \) та невдача з ймовірністю \( q = 1 - p \), то ймовірність спостереження рівно \( x \) успіхів у \( n \) випробуваннях визначається як:
\[ b(x; n, p) = \binom{n}{x} p^{x} q^{n – x} \]
Цей вираз поєднує дві речі: біноміальний коефіцієнт, який підраховує кількість способів розміщення \( x \) успіхів у \( n \) випробуваннях, та множник \( p^x q^{n-x} \), який вимірює ймовірність будь-якого одного такого розміщення. Фіксуючи \( n \) та \( p \) і дозволяючи \( x \) змінюватися від \( 0 \) до \( n \), ми отримуємо повний розподіл — кожен можливий результат, зважений відповідно до того, скількома способами він може виникнути.
Резюме
| Означення | \( \dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!} \) |
| Граничні випадки | \( \dbinom{n}{0} = \dbinom{n}{n} = 1 \) |
| Симетрія | \( \dbinom{n}{k} = \dbinom{n}{n-k} \) |
| Адитивність | \( \dbinom{n}{k} + \dbinom{n}{k+1} = \dbinom{n+1}{k+1} \) |
| Рекурсія | \( \dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k} \) |
| Сума рядка | \( \displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n \) |
| Змінна сума | \( \displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \) |
| Вандермонде | \( \dbinom{m+n}{r} = \displaystyle\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} \) |
| Верхня сума | \( \displaystyle\sum_{i=0}^{r} \binom{n+i}{i} = \binom{n+r+1}{r} \) |