Біноміальний коефіцієнт
Матеріал з Вікіпедії — вільної енциклопедії.
Біноміальні коефіцієнти — коефіцієнти в розкладі (1 + x)n по степеням x (так званий біном Ньютона):
Значення біноміального коефіцієнта визначено для усіх цілих чисел n і k. Явні формули для обчислення біноміальних коефіцієнтів:
для
;
для k < 0 або
;
для
,
де n! та k! — факторіали чисел n і k.
Біноміальний коефіцієнт є узагальненням кількості невпорядкованих виборів
, що визначена тільки для невід'ємних цілих чисел n, k.
Біноміальні коефіцієнти часто зустрічаються в комбінаторних задачах і теорії імовірності.
Узагальненням біноміального коефіцієнта є поліноміальний коефіцієнт.
Зміст |
[ред.] Трикутник Паскаля
Тотожність
дозволяє розташувати біноміальні коефіцієнти для невід'ємних n, k у вигляді трикутника Паскаля, в якому кожне чмсло рівне сумі двох, що стоять на рядок вище:
Трикутна таблиця, запропонована Паскалем в «Трактаті про арифметичний трикутник» (1654), відрізняється від описаної тут поворотом на 45°. Таблиці для зображення біноміальних коефіцієнтів були відомі й раніше.
[ред.] Тотожності
(згортка Вандермонда)
[ред.] Асимптотика і оцінки
при
(нерівність Чебешева)
(ентропійна оцінка), де H(x) = − xlog2x − (1 − x)log2(1 − x) — ентропія.
(нерівність Чернова)
[ред.] Алгоритми обчислення біноміальних коефіцієнтів
Біноміальні коефіцієнти можуть бути обчислені за формулою , якщо на кажному кроці зберігати значення
для
. Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення
при фіксованому n. Алгоритм потребує O(n) пам'яті (O(n2) для обчислення всієї таблиці) і O(n2) часу (припускаючи, що кожне число займає однакову кількість пам'яті і операції з числами виконуються за одиницю часу).
Інший спосіб ґрунтується на тотожності . Він дозволяє обчислити значення
при фіксованому k. Алгоритм потребує O(1) пам'яті і O(k) часу.