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

Біноміальні коефіцієнти — коефіцієнти в розкладі $(1 + x)^{n}$ по степенях $x$ (так званий біном Ньютона):

(1 + x)^{n} = (\binom{n}{0}) + (\binom{n}{1}) x + (\binom{n}{2}) x^{2} + \dots + (\binom{n}{n}) x^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} .

Біноміальний коефіцієнт є узагальненням кількості невпорядкованих виборів $C_{n}^{k}$ , що визначена тільки для невід'ємних цілих чисел $n$ , $k$ , тобто $n + 1 \in ℕ$ та $k + 1 \in ℕ .$ У явному вигляді для $0 \leq k \leq n$ :

(\binom{n}{k}) = C_{n}^{k} = \frac{n!}{k! (n - k)!}

,

де $n!$ та $k!$ — факторіали чисел $n$ і $k$ .

Явні формули

Обчислюючи коефіцієнти в розкладі $(1 + x)^{n}$ у степеневий ряд, можна отримати явні формули для біноміальних коефіцієнтів $(\binom{n}{k})$ .

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

(\binom{n}{k}) = {\begin{matrix} \frac{n (n - 1) (n - 2) \cdot \dots \cdot (n - k + 1)}{k!}, & k ⩾ 0, \\ 0, & k < 0, \end{matrix}

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

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

(\binom{n}{k}) = {\begin{matrix} \frac{n!}{k! (n - k)!}, & 0 ⩽ k ⩽ n, \\ 0, & k > n . \end{matrix}

Для цілих від'ємних показників коефіцієнти розкладу бінома $(1 + x)^{- n}$ рівні

(\binom{- n}{k}) = {\begin{matrix} (- 1)^{k} \cdot \frac{(n + k - 1)!}{k! (n - 1)!}, & k ⩾ 0, \\ 0, & k < 0 . \end{matrix}

Трикутник Паскаля

Шаблон:Докладніше Тотожність $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ дозволяє розташувати біноміальні коефіцієнти для невід'ємних $n$ , $k$ у вигляді трикутника Паскаля, в якому кожне число рівне сумі двох, що стоять на рядок вище:

\begin{matrix} n = 0 : & 1 \\ n = 1 : & 1 & 1 \\ n = 2 : & 1 & 2 & 1 \\ n = 3 : & 1 & 3 & 3 & 1 \\ n = 4 : & 1 & 4 & 6 & 4 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix}

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

Властивості

Твірні функції

Для фіксованого значення n твірною функцією послідовності біноміальних коефіцієнтів $(\binom{n}{0}), (\binom{n}{1}), (\binom{n}{2}),$ … є

\sum_{k = 0}^{\infty} (\binom{n}{k}) x^{k} = (1 + x)^{n} .

Для фіксованого значення k твірною функцією послідовності коефіцієнтів $(\binom{0}{k}), (\binom{1}{k}), (\binom{2}{k}),$ … є

\sum_{n} (\binom{n}{k}) y^{n} = \frac{y^{k}}{(1 - y)^{k + 1}}

.

Двовимірною твірною функцією біноміальних коефіцієнтів $(\binom{n}{k})$ для цілих $n, k$ є

\sum_{n, k} (\binom{n}{k}) x^{k} y^{n} = \frac{1}{1 - y - x y},

або

\sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n} = \frac{1}{1 - y - x y} .

Подільність

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

коефіцієнт $(\binom{n}{k})$ непарний $⟺$ в двійкового запису числа k одиниці не стоять у тих розрядах, де в числі n стоять нулі;
коефіцієнт $(\binom{n}{k})$ не кратний простому число p $⟺$ при записі числа k в системі числення з основою p, всі розряди не перевищують відповідних розрядів числа n;
у послідовності біноміальних коефіцієнтів (n0),(n1),…,(nn):
- всі числа не кратні заданому простому p $⟺$ число $n$ можна подати у вигляді $m p^{k} - 1$ , де натуральне число $m < p$ ;
- всі числа, крім першого й останнього, кратні даному простому p $⟺$ $n = p^{k}$ ;
- кількість непарних чисел дорівнює степеню двійки, показник якої дорівнює кількості одиниць у двійковому записі числа n;
- парних і непарних чисел не може бути порівну;
- кількість чисел, не кратних простому p, дорівнює $(a_{1} + 1) * \dots * (a_{m} + 1)$ , де числа $a_{1}, \dots, a_{m}$ — розряди p-кового запису числа n; а число $m = ⌊ \log_{p} n ⌋ + 1,$ де $⌊ \cdot ⌋$ — функція «підлоги» — це довжина даного запису.

Тотожності

$(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$
$(\binom{n}{k}) = \frac{n}{n - k} (\binom{n - 1}{k})$
$(\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n}$
$(\binom{n}{0}) + (\binom{n}{2}) + \dots + (\binom{n}{2 ⌊ n / 2 ⌋}) = 2^{n - 1}$
${(\binom{n}{0})}^{2} + {(\binom{n}{1})}^{2} + \dots + {(\binom{n}{n})}^{2} = (\binom{2 n}{n})$
$\sum_{k = 0}^{n} (\binom{r}{m + k}) (\binom{s}{n - k}) = (\binom{r + s}{m + n})$ (згортка Вандермонда)

Біном Ньютона і наслідки

$(\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n},$ де $n \in ℕ .$
$\sum_{i + j = m} (\binom{n}{j}) (\binom{n}{i}) (- 1)^{j} = {\begin{matrix} (\binom{n}{m / 2}), & якщо m \equiv 0 (\mod 2), \\ 0, & якщо m \equiv 1 (\mod 2) . \end{matrix}$
$\sum_{j = k}^{n} (\binom{n}{j}) (- 1)^{j} = (- 1)^{k} (\binom{n - 1}{k - 1}) .$
$(\binom{n}{0}) - (\binom{n}{1}) + \dots + (- 1)^{n} (\binom{n}{n}) = 0,$ де $n \in ℕ .$
Сильніша тотожність: $(\binom{n}{0}) + (\binom{n}{2}) + \dots + (\binom{n}{2 ⌊ n / 2 ⌋}) = 2^{n - 1},$ де $n \in ℕ .$
$\sum_{k = - a}^{a} (- 1)^{k} {(\binom{2 a}{k + a})}^{3} = \frac{(3 a)!}{(a!)^{3}},$

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

\sum_{k = - a}^{a} (- 1)^{k} (\binom{a + b}{a + k}) (\binom{b + c}{b + k}) (\binom{c + a}{c + k}) = \frac{(a + b + c)!}{a! b! c!} .

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

$\sum_{k} (\binom{r}{m + k}) (\binom{s}{n - k}) = (\binom{r + s}{m + n})$ (згортка Вандермонда), де $m, n \in ℤ,$ а $r, s \in ℝ .$

Це тотожність виходить обчисленням коефіцієнта при $x^{m + n}$ у розкладі $(1 + x)^{r} (1 + x)^{s}$ з урахуванням тотожності $(1 + x)^{r + s} = (1 + x)^{r} (1 + x)^{s} .$ Сума береться за всіма цілими $k$ , для яких $(\binom{r}{m + k}) (\binom{s}{n - k}) \neq 0 .$ Для довільних дійсних $r$ , $s$ число ненульових доданків у сумі буде скінченним.

$(\binom{n}{0}) (\binom{a}{a}) - (\binom{n}{1}) (\binom{a + 1}{a}) + \dots + (- 1)^{n} (\binom{n}{n}) (\binom{a + n}{a}) = (- 1)^{n} (\binom{a}{n})$ .
загальніша тотожність: $\sum_{i = 0}^{p} (- 1)^{i} (\binom{p}{i}) \prod_{m = 1}^{n} (\binom{i + s_{m}}{s_{m}}) = 0$ , якщо $\sum_{m = 1}^{n} s_{m} < p$ .
${(\binom{n}{0})}^{2} + {(\binom{n}{1})}^{2} + \dots + {(\binom{n}{n})}^{2} = (\binom{2 n}{n}) .$

Інші тотожності

$\sum_{k = 1}^{n} \frac{(- 1)^{k - 1}}{k} (\binom{n}{k}) = \sum_{k = 1}^{n} \frac{1}{k} = H_{n}$ — n- е гармонічне число.
Мультисекція ряду $(1 + x)^{n}$ дає тотожність, що виражає суму біноміальних коефіцієнтів із довільним кроком s і зміщенням t $(0 ⩽ t < s)$ у вигляді скінченної суми з s доданків:

(\binom{n}{t}) + (\binom{n}{t + s}) + (\binom{n}{t + 2 s}) + \dots = \frac{1}{s} \sum_{j = 0}^{s - 1} {(2 \cos \frac{π j}{s})}^{n} \cos \frac{π (n - 2 t) j}{s} .

Виконуються рівності^[1]:

\begin{matrix} (\binom{n}{3}) & = \frac{n (n - 1) (n - 2)}{2} - \sum_{i = 2}^{n - 1} (n - i) (n - i + 1) = \\ = n (n - 1) (n - 2) - \sum_{i = 2}^{n - 1} (n - i) (2 n - i + 1) = \\ = 3 (\binom{n}{3}) - 2 (\binom{n}{3}); \end{matrix}

\begin{matrix} (\binom{n}{4}) & = \frac{n (n - 1) (n - 2) (n - 3)}{2} - \sum_{i = 3}^{n - 1} (n - i) (n (n - 1) - \sum_{i_{0} = 1}^{i - 2} i_{0}) = \\ = n (n - 1) (n - 2) (n - 3) - \sum_{i = 3}^{n - 1} (n - i) (2 n (n - 1) - \sum_{i_{0} = 1}^{i - 2} i_{0}) = \\ = 24 (\binom{n}{4}) - 23 (\binom{n}{4}); \end{matrix}

\begin{matrix} (\binom{n}{5}) & = \frac{n (n - 1) (n - 2) (n - 3) (n - 4)}{2} - \\ - \sum_{i = 4}^{n - 1} (n - i) (n (n - 1) (n - 2) - \sum_{i_{0} = 1}^{i - 3} \sum_{i_{1} = 1}^{i_{0}} i_{1}) = \\ = n (n - 1) (n - 2) (n - 3) (n - 4) - \\ - \sum_{i = 4}^{n - 1} (n - i) (2 n (n - 1) (n - 2) - \sum_{i_{0} = 1}^{i - 3} \sum_{i_{1} = 1}^{i_{0}} i_{1}) = \\ = 120 (\binom{n}{5}) - 119 (\binom{n}{5}) . \end{matrix}

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

(\binom{n}{3}) = \frac{\sum_{i = 2}^{n - 1} (n - i) (2 n - i + 1)}{2} = \frac{\sum_{i = 2}^{n - 1} (n - i) (2 A_{n}^{1} - (\binom{i - 1}{1}))}{2};

(\binom{n}{4}) = \frac{\sum_{i = 3}^{n - 1} (n - i) (2 n (n - 1) - \sum_{i_{0} = 1}^{i - 2} i_{0})}{23} = \frac{\sum_{i = 3}^{n - 1} (n - i) (2 A_{n}^{2} - (\binom{i - 1}{2}))}{23};

\begin{matrix} (\binom{n}{5}) = \frac{\sum_{i = 4}^{n - 1} (n - i) (2 n (n - 1) (n - 2) - \sum_{i_{0} = 1}^{i - 3} \sum_{i_{1} = 1}^{i_{0}} i_{1})}{119} = \\ = \frac{\sum_{i = 4}^{n - 1} (n - i) (2 A_{n}^{3} - (\binom{i - 1}{3}))}{119}; \end{matrix}

(\binom{n}{k}) = \frac{\sum_{i = k - 1}^{n - 1} (n - i) (2 A_{n}^{k - 2} - (\binom{i - 1}{k - 2}))}{k! - 1},

де $A_{n}^{k}$ — кількість розміщень із n по k.

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

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

У матриці $[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]$ числа на діагоналі $i + j = c o n s t$ повторюють числа рядків трикутника Паскаля $(i, j = 0, 1, \dots)$ . Її можна розкласти в добуток двох строго діагональних матриць: нижньотрикутної та одержуваної з неї транспонуванням. А саме:

[\begin{matrix} (\binom{i + j}{i}) \end{matrix}] = U U^{T},

де $U = [\begin{matrix} (\binom{i}{j}) \end{matrix}]$ . Обернена матриця до $U$ має вигляд:

U^{- 1} = [\begin{matrix} (- 1)^{i + j} (\binom{i}{j}) \end{matrix}] .

Таким чином, матрицю, обернену до $[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]$ , можна розкласти в добуток двох строго діагональних матриць: перша матриця — верхньотрикутна, а друга виходить з першої транспонуванням, що дозволяє дати явний вираз для обернених елементів:

{[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]}_{m, n}^{- 1} = \sum_{k = 0}^{p} (- 1)^{m + n} (\binom{k}{m}) (\binom{k}{n})

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

Елементи оберненої матриці змінюються за зміни її розміру і, на відміну від матриці $[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]$ , недостатньо приписати новий рядок і стовпець. Стовпець j матриці $[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]$ є многочленом степеня j за аргументом i, отже, перші p стовпців утворюють повний базис у просторі векторів довжини p+1, чиї координати можна інтерполювати многочленом степеня рівного або меншого ніж p-1. Нижній рядок матриці ${[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]}_{m, n}^{- 1}$ ортогональний до будь-якого такого вектора.

{[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]}_{p, n}^{- 1} = \sum_{k = 0}^{p} (- 1)^{p + n} (\binom{k}{p}) (\binom{k}{n}) = (- 1)^{p + n} (\binom{p}{n})

\sum_{n = 0}^{p} (- 1)^{p + n} (\binom{p}{n}) P_{a} (n) = 0

при

a < p

, де

P_{a} (n)

многочлен степеня

a

.

Якщо довільний вектор довжини $p + 1$ можна інтерполювати многочленом степеня $i < p$ , то скалярний добуток з рядками $i + 1, i + 2, \dots, p$ (нумерація з 0) матриці ${[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]}_{m, n}^{- 1}$ дорівнює нулю. Використовуючи тотожність вище і рівність одиниці скалярного добутку нижнього рядка матриці ${[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]}_{m, n}^{- 1}$ на останній стовпець матриці $[\begin{matrix} (\binom{i + j}{i}) \end{matrix}]$ , маємо:

\sum_{n = 0}^{p} (- 1)^{p + n} (\binom{p}{n}) n^{p} = p! .

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

\sum_{n = 0}^{p} (- 1)^{p + n} (\binom{p}{n}) n^{p + a} = p! P_{2 a} (p) = f_{a} (p),

де многочлен

P_{2 a + 2} (p) = \sum_{x = 1}^{p} x P_{2 a} (x); a ⩾ 0; P_{0} (p) = 1 .

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

f_{a} (p + 1) = \sum_{x = 0}^{a} {(p + 1)}^{x + 1} f_{a - x} (p) .

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

P_{2 a} (p) = \frac{p}{2^{a}} (\binom{p + a}{a}) Q_{a - 1} (p); a > 0 .

Старший коефіцієнт $Q_{a - 1} (p)$ дорівнює 1, щоб знайти інші коефіцієнти, знадобиться $a - 1$ значень:

Q_{a - 1} (p) = p (p + 1) T_{a - 3} (p)

для

a \equiv 1 (\mod 2); a ⩾ 3 .

Цілозначні многочлени

Біноміальні коефіцієнти $(\binom{x}{0}) = 1, (\binom{x}{1}) = x, (\binom{x}{2}) = \frac{x^{2}}{2} - \frac{x}{2},$ … є цілозначними многочленами від $x$ , тобто, набувають цілих значень за цілих значень $x,$ — це неважко зрозуміти, наприклад, за трикутником Паскаля. Більш того, вони утворюють базис цілозначних многочленів, у якому всі цілозначні многочлени виражаються як лінійні комбінації з цілими коефіцієнтами^[2].

Разом з тим, стандартний базис $1, x, x^{2},$ … не дозволяє виразити всіх цілочисельних многочленів, якщо використовувати тільки цілі коефіцієнти, оскільки вже $(\binom{x}{2}) = \frac{x^{2}}{2} - \frac{x}{2}$ має дробові коефіцієнти при степенях $x$ .

Цей результат узагальнюється на многочлени багатьох змінних. А саме, якщо многочлен $R (x_{1}, \dots, x_{m})$ степеня $k$ має дійсні коефіцієнти і набуває цілих значень за цілих значень змінних, то

R (x_{1}, \dots, x_{m}) = P ((\binom{x_{1}}{1}), \dots, (\binom{x_{1}}{k}), \dots, (\binom{x_{m}}{1}), \dots, (\binom{x_{m}}{k})),

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

Асимптотика і оцінки

$(\binom{2 n}{n}) \sim \frac{2^{2 n}}{\sqrt{π n}}$
$\sum_{k = 0}^{m} (\binom{n}{k}) \leq \frac{n}{(n / 2 - m)^{2}} 2^{n - 3}$ при $m \leq n / 2$ (нерівність Чебишева)
$\sum_{k = 0}^{m} (\binom{n}{k}) \leq 2^{n H (m / n)}$ (ентропійна оцінка), де $H (x) = - x \log_{2} x - (1 - x) \log_{2} (1 - x)$ — ентропія.
$\sum_{k = 0}^{n / 2 - λ} (\binom{n}{k}) \leq 2^{n} e^{- 2 λ^{2} / n}$ (нерівність Чернова)

Алгоритми обчислення

Біноміальні коефіцієнти можуть бути обчислені за допомогою тотожності $(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1})$ , якщо на кожному кроці зберігати значення $(\binom{n}{k})$ для $k = 0, 1, \dots, n$ . Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення $(\binom{n}{k})$ при фіксованому $n$ . Алгоритм потребує $O (n)$ пам'яті ( $O (n^{2})$ для обчислення всієї таблиці) і $O (n^{2})$ часу.

Інший спосіб ґрунтується на тотожності $(\binom{n}{k}) = \frac{n}{n - k} (\binom{n - 1}{k})$ . Він дозволяє обчислити значення $(\binom{n}{k})$ при фіксованому $k$ . Алгоритм потребує $O (1)$ пам'яті і $O (n)$ часу.

Узагальнення

Оскільки для $n + 1 \in ℕ : n! = Γ (n + 1)$ , то значення біноміального коефіцієнта можна визначити для усіх комплексних чисел $n \in ℂ$ та $k \in ℂ$ :

(\binom{n}{k}) = \frac{Γ (n + 1)}{Γ (k + 1) Γ (n - k + 1)}

Явні формули для обчислення біноміальних коефіцієнтів для цілих чисел $n$ та $k$ :

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

для

0 \leq k \leq n

;

(\binom{n}{k}) = 0

для

k < 0

або

0 \leq n < k

;

(\binom{n}{k}) = (- 1)^{k} (\binom{- n + k - 1}{k})

для

n < 0 \leq k

.

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

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

Генерація на 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;
}

Див. також

Примітки

Шаблон:Примітки

Джерела

Шаблон:Завало.Елементи аналізу. Алгебра многочленів.

Шаблон:Бібліоінформація Шаблон:ВП-портали

[example-1] Шаблон:Cite web

[2] Шаблон:Книга

[3] Шаблон:Книга

[1]

[2]

[3]

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

Зміст

Явні формули

Трикутник Паскаля

Властивості

Твірні функції

Подільність

Тотожності

Біном Ньютона і наслідки

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

Інші тотожності

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

Цілозначні многочлени

Асимптотика і оцінки

Алгоритми обчислення

Узагальнення

Генерація на C++

Див. також

Примітки

Джерела

Навігаційне меню

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

Явні формули

Трикутник Паскаля

Властивості

Твірні функції

Подільність

Тотожності

Біном Ньютона і наслідки

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

Інші тотожності

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

Цілозначні многочлени

Асимптотика і оцінки

Алгоритми обчислення

Узагальнення

Генерація на C++

Див. також

Примітки

Джерела

Навігаційне меню

Пошук