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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

для ;
для або ;
для ,

де та факторіали чисел і .

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

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

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

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

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

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

Докладніше у статті Трикутник Паскаля

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

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

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

  1. при (нерівність Чебишева)
  2. (ентропійна оцінка), де ентропія.
  3. (нерівність Чернова)

Алгоритми обчислення[ред.ред. код]

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

Генерація на C++[ред.ред. код]

#include <iostream>
#include <string>

using namespace std;

void C(int n, int m, int startAt = 1, string s = "") {
	for (int i = startAt; i <= n - m + 1; i++) {
		if (1 == m)
			cout << s + (char)(i+48) << endl;
		else
			C(n, m - 1, i + 1, s + (char)(i+48));
	}	
}

int main() {
	C(7, 3);
	
	return 0;
}

Див. також[ред.ред. код]