Відкрити головне меню
Біноміальні коефіцієнти розташовані у вигляді трикутника Паскаля.

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

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

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

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

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

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

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

Зміст

ТотожностіРедагувати

  1.  
  2.  
  3.  
  4.  
  5.  
  6.   (згортка Вандермонда)

Трикутник ПаскаляРедагувати

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

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

 

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

Асимптотика і оцінкиРедагувати

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

Алгоритми обчисленняРедагувати

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

Генерація на 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+'0') << endl;
		else
			C(n, m - 1, i + 1, s + (char)(i+'0'));
	}	
}

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

Див. такожРедагувати