біноміальний коефіцієнт
Біноміальні коефіцієнти - коефіцієнти в розкладанні \ ((1 + x) ^ n \) за ступенями \ (x \) (т. Н. Біном Ньютона): $$ (1 + x) ^ n = + x + x ^ 2 + \ cdots = \ sum_k x ^ k. $$ значення біноміального коефіцієнта \ (\) визначено для всіх цілих чисел \ (n \) і \ (k \). Явні формули для обчислення біноміальних коефіцієнтів: $$ = \ frac = \ frac $$ для \ (0 \ leq k \ leq n \); $$ = 0 $$ для \ (k \) або \ (0 \ leq n Біноміальний коефіцієнт \ (\) є узагальненням числа сполучень \ (C ^ k_n \), яке визначено тільки для невід'ємних цілих чисел \ (n \), \ (k \). Біноміальні коефіцієнти часто виникають в комбінаторних задачах і теорії ймовірностей. Узагальненням біноміальних коефіцієнтів є поліноміальний коефіцієнти.Трикутник Паскаля [ред]
Тотожність $$ = + $$ дозволяє розташувати біноміальні коефіцієнти для невід'ємних \ (n \), \ (k \) у вигляді трикутника Паскаля, в якому кожне число дорівнює сумі двох вищих: $$ \ begin n = 0: 1 \\ n = 1: 1 1 \\ n = 2: 1 2 1 \\ n = 3: 1 3 3 1 \\ n = 4: 1 4 6 4 1 \\ \ vdots \ vdots \ vdots \ vdots \ vdots \ End $$
Трикутна таблиця, запропонована Паскалем в «Трактаті про арифметичний трикутник» (1 654), відрізняється від виписаної тут поворотом на 45 °. Таблиці для зображення біноміальних коефіцієнтів були відомі і раніше.
Властивості [ред]
Цікаво, що якщо розглянути ряди в трикутнику Паскаля, що складаються з біноміальних коефіцієнтів. то в межі отримаємо функцію нормального розподілу - розподіл Гаусса.
Тотожності [ред]
Асимптотика і оцінки [ред]
Алгоритми обчислення біноміальних коефіцієнтів [ред]
Біноміальні коефіцієнти можуть бути обчислені за допомогою формули \ (= + \), якщо на кожному кроці зберігати значення \ (\) при \ (k = 0,1, \ dots, n \). Цей алгоритм особливо ефективний, якщо потрібно отримати всі значення \ (\) при фіксованому \ (n \). Алгоритм вимагає \ (O (n) \) пам'яті (\ (O (n ^ 2) \) при обчисленні всієї таблиці біноміальних коефіцієнтів) і \ (O (n ^ 2) \) часу (в припущенні, що кожне число займає одиницю пам'яті і операції з числами виконуються за одиницю часу).
Другий спосіб заснований на тотожність \ (= \ frac \). Він дозволяє обчислити значення \ (\) при фіксованому \ (k \). Алгоритм вимагає \ (O (1) \) пам'яті (\ (O (l) \) якщо потрібно порахувати \ (l \) послідовних коефіцієнтів з фіксованим \ (k \)) і \ (O (k) \) часу.