Біноміальні коефіцієнти — коефіцієнти в розкладі по степенях (так званий біном Ньютона):
Біноміальний коефіцієнт є узагальненням кількості невпорядкованих виборів , що визначена тільки для невід'ємних цілих чисел , , тобто та У явному вигляді для : , де та — факторіали чисел і .
Явні формули Обчислюючи коефіцієнти в розкладі у степеневий ряд, можна отримати явні формули для біноміальних коефіцієнтів .
Для всіх дійсних чисел 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, щоб знайти інші коефіцієнти, знадобиться значень:
для
Цілозначні многочлени Біноміальні коефіцієнти … є цілозначними многочленами від , тобто, набувають цілих значень за цілих значень — це неважко зрозуміти, наприклад, за трикутником Паскаля. Більш того, вони утворюють базис цілозначних многочленів, у якому всі цілозначні многочлени виражаються як лінійні комбінації з цілими коефіцієнтами.
Разом з тим, стандартний базис … не дозволяє виразити всіх цілочисельних многочленів, якщо використовувати тільки цілі коефіцієнти, оскільки вже має дробові коефіцієнти при степенях .
Цей результат узагальнюється на многочлени багатьох змінних. А саме, якщо многочлен степеня має дійсні коефіцієнти і набуває цілих значень за цілих значень змінних, то
де — многочлен із цілими коефіцієнтами.
Асимптотика і оцінки
при (нерівність Чебишева) (ентропійна оцінка), де — ентропія. (нерівність Чернова)
Алгоритми обчислення Біноміальні коефіцієнти можуть бути обчислені за допомогою тотожності , якщо на кожному кроці зберігати значення для . Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення при фіксованому . Алгоритм потребує пам'яті ( для обчислення всієї таблиці) і часу.
Інший спосіб ґрунтується на тотожності . Він дозволяє обчислити значення при фіксованому . Алгоритм потребує пам'яті і часу.
Узагальнення Оскільки для , то значення біноміального коефіцієнта можна визначити для усіх комплексних чисел та :
Явні формули для обчислення біноміальних коефіцієнтів для цілих чисел та : для ; для або ; для .
Біноміальні коефіцієнти часто зустрічаються в комбінаторних задачах і теорії імовірностей.
Узагальненням біноміального коефіцієнта є мультиноміальний коефіцієнт.
Генерація на 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; }
Див. також Біном Гауссові біноміальні коефіцієнти Фібономіальний коефіцієнт Функція fusc Центральний біноміальний коефіцієнт
Примітки
Джерела