Біноміальний коефіцієнт - Вікіпедія

# Біноміальний коефіцієнт

### Матеріал з Вікіпедії — вільної енциклопедії.

Біноміальні коефіцієнти — коефіцієнти в розкладі (1 + x)n по степеням x (так званий біном Ньютона):

Значення біноміального коефіцієнта визначено для усіх цілих чисел n і k. Явні формули для обчислення біноміальних коефіцієнтів:

  для ;
  для k < 0 або ;
  для ,

де n! та k! — факторіали чисел n і k.

Біноміальний коефіцієнт є узагальненням кількості невпорядкованих виборів , що визначена тільки для невід'ємних цілих чисел n, k.

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

Узагальненням біноміального коефіцієнта є поліноміальний коефіцієнт.

## [ред.] Трикутник Паскаля

Тотожність

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

Трикутна таблиця, запропонована Паскалем в «Трактаті про арифметичний трикутник» (1654), відрізняється від описаної тут поворотом на 45°. Таблиці для зображення біноміальних коефіцієнтів були відомі й раніше.

## [ред.] Тотожності

5. (згортка Вандермонда)

## [ред.] Асимптотика і оцінки

2. при (нерівність Чебешева)
3. (ентропійна оцінка), де H(x) = − xlog2x − (1 − x)log2(1 − x) — ентропія.
4. (нерівність Чернова)

## [ред.] Алгоритми обчислення біноміальних коефіцієнтів

Біноміальні коефіцієнти можуть бути обчислені за формулою , якщо на кажному кроці зберігати значення для . Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення при фіксованому n. Алгоритм потребує O(n) пам'яті (O(n2) для обчислення всієї таблиці) і O(n2) часу (припускаючи, що кожне число займає однакову кількість пам'яті і операції з числами виконуються за одиницю часу).

Інший спосіб грунтується на тотожності . Він дозволяє обчислити значення при фіксованому k. Алгоритм потребує O(1) пам'яті і O(k) часу.

Отримано від "http://uk.wikipedia.org../../../%D0%B1/%D1%96/%D0%BD/%D0%91%D1%96%D0%BD%D0%BE%D0%BC%D1%96%D0%B0%D0%BB%D1%8C%D0%BD%D0%B8%D0%B9_%D0%BA%D0%BE%D0%B5%D1%84%D1%96%D1%86%D1%96%D1%94%D0%BD%D1%82.html"

Категорії: Математика | Комбінаторика | Алгоритми

##### Views

- Стаття
- Обговорення
- Поточна версія

##### Пошук

##### Іншими мовами

- Български
- বাংলা
- Česky
- Deutsch
- English
- Español
- Suomi
- Français
- Italiano
- 한국어
- Lietuvių
- Nederlands
- Polski
- Русский
- Slovenščina
- Српски / Srpski
- 中文