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

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

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

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

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

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

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





(згортка Вандермонда)
Біном Ньютона і наслідки[ред. | ред. код]
де 


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

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

Згортка Вандермонда і наслідки[ред. | ред. код]
(згортка Вандермонда), де
а 
Це тотожність виходить обчисленням коефіцієнта при
у розкладі
з урахуванням тотожності
Сума береться за всіма цілими
, для яких
Для довільних дійсних
,
число ненульових доданків у сумі буде скінченним.
.
- загальніша тотожність:
, якщо
.

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




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




де
— кількість розміщень із 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]
Асимптотика і оцінки[ред. | ред. код]

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

Явні формули для обчислення біноміальних коефіцієнтів для цілих чисел
та
:
для
;
для
або
;
для
.
Біноміальні коефіцієнти часто зустрічаються в комбінаторних задачах і теорії імовірностей.
Узагальненням біноміального коефіцієнта є поліноміальний коефіцієнт.
#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;
}
- Завало С. Т. (1972). Елементи аналізу. Алгебра многочленів. Київ: Радянська школа. с. 462. (укр.)