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

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

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

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

,

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

Явні формулиРедагувати

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

Для всіх дійсних чисел n і цілих чисел k:

 

де   позначає факторіал числа k.

Для невід'ємних цілих n і k також справедливі формули:

 

Для цілих від'ємних показників коефіцієнти розкладу бінома   рівні

 

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

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

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

 

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

ВластивостіРедагувати

Твірні функціїРедагувати

Для фіксованого значення n твірною функцією послідовності біноміальних коефіцієнтів   … є

 

Для фіксованого значення k твірною функцією послідовності коефіцієнтів   … є

 .

Двовимірною твірною функцією біноміальних коефіцієнтів   для цілих   є

  або  

ПодільністьРедагувати

Із теореми Люка випливає, що:

  • коефіцієнт   непарний   в двійкового запису числа k одиниці не стоять у тих розрядах, де в числі n стоять нулі;
  • коефіцієнт   не кратний простому число p   при записі числа k в системі числення з основою p, всі розряди не перевищують відповідних розрядів числа n;
  • у послідовності біноміальних коефіцієнтів  :
    • всі числа не кратні заданому простому p   число   можна подати у вигляді  , де натуральне число  ;
    • всі числа, крім першого й останнього, кратні даному простому p    ;
    • кількість непарних чисел дорівнює степеню двійки, показник якої дорівнює кількості одиниць у двійковому записі числа n;
    • парних і непарних чисел не може бути порівну;
    • кількість чисел, не кратних простому p, дорівнює  , де числа   — розряди p-кового запису числа n; а число   де   — функція «підлоги» — це довжина даного запису.

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

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

Біном Ньютона і наслідкиРедагувати

  •   де  
  •  
  •  
  •   де  
  • Сильніша тотожність:   де  
  •  

а в загальнішому вигляді

 

Згортка Вандермонда і наслідкиРедагувати

  •   (згортка Вандермонда), де   а  

Це тотожність виходить обчисленням коефіцієнта при   у розкладі   з урахуванням тотожності   Сума береться за всіма цілими  , для яких   Для довільних дійсних  ,   число ненульових доданків у сумі буде скінченним.

  •  .
  • загальніша тотожність:  , якщо  .
  •  

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

  •   — n- е гармонічне число.
  • Мультисекція ряду   дає тотожність, що виражає суму біноміальних коефіцієнтів із довільним кроком s і зміщенням t   у вигляді скінченної суми з s доданків:
 
  • Виконуються рівності[1]:
 
 
 

Звідки випливає:

 
 
 
 

де   — кількість розміщень із n по k.

Матричні співвідношенняРедагувати

Якщо взяти квадратну матрицю, відрахувавши N елементів по катетах трикутника Паскаля і повернувши матрицю на будь-який з чотирьох кутів, то детермінант цих чотирьох матриць дорівнює ±1 за будь-якого N, причому детермінант матриці з вершиною трикутника у верхньому лівому куті дорівнює 1.

У матриці   числа на діагоналі   повторюють числа рядків трикутника Паскаля  . Її можна розкласти в добуток двох строго діагональних матриць: нижньотрикутної та одержуваної з неї транспонуванням. А саме:

 

де  . Обернена матриця до   має вигляд:

 

Таким чином, матрицю, обернену до  , можна розкласти в добуток двох строго діагональних матриць: перша матриця — верхньотрикутна, а друга виходить з першої транспонуванням, що дозволяє дати явний вираз для обернених елементів:

 , де i, j, m, n = 0..p.

Елементи оберненої матриці змінюються за зміни її розміру і, на відміну від матриці  , недостатньо приписати новий рядок і стовпець. Стовпець j матриці   є многочленом степеня j за аргументом i, отже, перші p стовпців утворюють повний базис у просторі векторів довжини p+1, чиї координати можна інтерполювати многочленом степеня рівного або меншого ніж p-1. Нижній рядок матриці   ортогональний до будь-якого такого вектора.

 
  при  , де   многочлен степеня  .

Якщо довільний вектор довжини   можна інтерполювати многочленом степеня  , то скалярний добуток з рядками   (нумерація з 0) матриці   дорівнює нулю. Використовуючи тотожність вище і рівність одиниці скалярного добутку нижнього рядка матриці   на останній стовпець матриці  , маємо:

 

Для показника, більшого від p, можна задати рекурентну формулу:

 

де многочлен

 

Для доведення спершу доводиться тотожність:

 

Якщо потрібно знайти формулу не для всіх показників степеня, то

 

Старший коефіцієнт   дорівнює 1, щоб знайти інші коефіцієнти, знадобиться   значень:

  для  

Цілозначні многочлениРедагувати

Біноміальні коефіцієнти   … є цілозначними многочленами від  , тобто, набувають цілих значень за цілих значень   — це неважко зрозуміти, наприклад, за трикутником Паскаля. Більш того, вони утворюють базис цілозначних многочленів, у якому всі цілозначні многочлени виражаються як лінійні комбінації з цілими коефіцієнтами[2].

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

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

 

де   — многочлен із цілими коефіцієнтами.[3]

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

  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;
}

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

ПриміткиРедагувати

  1. Четырёхмерные таблицы в комбинаторике — два странных способа посчитать сочетания. habr.com. 30 листопада 2020. Архів оригіналу за 25 жовтня 2021. Процитовано 27 березня 2021. 
  2. Прасолов В. В. Глава 12. Целозначные многочлены // [1] — М. : МЦНМО, 1999, 2001, 2003. Архівовано з джерела 21 січня 2022
  3. Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993. — С. 20,185,194.

ДжерелаРедагувати

  • Завало С. Т. (1972). Елементи аналізу. Алгебра многочленів. Київ: Радянська школа. с. 462.  (укр.)