Биномиальный коэффициент

Биномиа́льный коэффицие́нт — коэффициент перед членом разложения бинома Ньютона $(1 + x)^{n}$ по степеням $x$ . Коэффициент при $x^{k}$ обозначается $(\binom{n}{k})$ или $C_{n}^{k}$ и читается «биномиальный коэффициент из $n$ по $k$ » (или «число сочетаний из $n$ по $k$ »):

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

для натуральных степеней $n$ .

Биномиальные коэффициенты могут быть также определены для произвольных действительных показателей $n$ . В случае произвольного действительного числа $n$ биномиальные коэффициенты определяются как коэффициенты разложения выражения $(1 + x)^{n}$ в бесконечный степенной ряд:

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

,

где в случае неотрицательных целых $n$ все коэффициенты $(\binom{n}{k})$ при $k > n$ обращаются в нуль и поэтому данное разложение является конечной суммой.

В комбинаторике биномиальный коэффициент $(\binom{n}{k})$ для неотрицательных целых чисел $n$ и $k$ интерпретируется как количество сочетаний из $n$ по $k$ , то есть как количество всех (нестрогих) подмножеств (выборок) размера $k$ в $n$ -элементном множестве.

Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.

Явные формулы

Вычисляя коэффициенты в разложении $(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}

.

Треугольник Паскаля

Шаблон:Main

Тождество:

(\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°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, Омару Хайяму, аль-Караджи, Яну Хуэю).

Если в каждой строке треугольника Паскаля все числа разделить на $2^{n}$ (это сумма всех чисел в строке), то все строки при стремлении $n$ к бесконечности примут вид функции нормального распределения.

Свойства

Производящие функции

Для фиксированного значения $n$ производящей функцией последовательности биномиальных коэффициентов $(\binom{n}{0}), (\binom{n}{1}), (\binom{n}{2}), \dots$ является:

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

.

Для фиксированного значения $k$ производящая функция последовательности коэффициентов $(\binom{0}{k}), (\binom{1}{k}), (\binom{2}{k}), \dots$ равна:

\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$ $⟺$ в $p$ -ичной записи числа $k$ все разряды не превосходят соответствующих разрядов числа $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}) = (- 1)^{k} (\binom{- n + k - 1}{k})$ .
$(\binom{n}{k}) = (\binom{n}{n - k})$ (правило симметрии).
$(\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{k - 1})$ (вынесение за скобки).
$(\binom{n}{m}) (\binom{m}{n - k}) = (\binom{n}{k}) (\binom{k}{n - m})$ (замена индексов).
$(n - k) (\binom{n}{k}) = n (\binom{n - 1}{k})$ .

Бином Ньютона и следствия

$(\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}) (- 1)^{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})$ .

Другие тождества

$\frac{4}{n} \sum_{k = 1}^{n} k^{2} (\binom{2 n}{n + k}) = 2^{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}

.

Также имеют место равенства:

\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 \dots 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{2 n}{n}) \sim \frac{2^{2 n}}{\sqrt{π n}}$ .
$\sum_{k = 0}^{m} (\binom{n}{k}) ⩽ \frac{n}{(n / 2 - m)^{2}} 2^{n - 3}$ при $m < \frac{n}{2}$ (неравенство Чебышёва).
$\sum_{k = 0}^{m} (\binom{n}{k}) ⩽ 2^{n H (\frac{m}{n})}$ , при $m \leq \frac{n}{2}$ (энтропийная оценка), где $H (x) = - x \log_{2} x - (1 - x) \log_{2} (1 - x)$ — энтропия.
$\sum_{k = 0}^{n / 2 - λ} (\binom{n}{k}) ⩽ 2^{n} e^{- 2 λ^{2} / n}$ (неравенство Чернова).

Непосредственно из формулы Стирлинга следует, что для $α \in (0; 1)$ верно $C_{n}^{α n} \sim \sqrt{\frac{1}{2 π α (1 - α) n}} {(\frac{1}{α})}^{α n} {(\frac{1}{1 - α})}^{(1 - α) n} = {(\frac{1}{α^{α} {(1 - α)}^{(1 - α)}} + o (1))}^{n}$ .

Целозначные полиномы

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

В то же время стандартный базис $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$ — полином с целыми коэффициентами.^[2]

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

Биномиальные коэффициенты можно вычислить с помощью рекуррентной формулы $(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1})$ , если на каждом шаге $n$ хранить значения $(\binom{n}{k})$ при $k = \overline{0, 1, \dots, n}$ . Этот алгоритм особенно эффективен, если нужно получить все значения $(\binom{n}{k})$ при фиксированном $n$ . Алгоритм требует $O (n)$ памяти ( $O (n^{2})$ при вычислении всей таблицы биномиальных коэффициентов) и $O (n^{2})$ времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени), где $O$ — « $o$ » большое.

При фиксированном значении $k$ биномиальные коэффициенты могут быть вычислены по рекуррентной формуле $(\binom{n}{k}) = \frac{n}{n - k} \cdot (\binom{n - 1}{k})$ с начальным значением $(\binom{k}{k}) = 1$ . Для вычисления значения $(\binom{n}{k})$ этот метод требует $O (1)$ памяти и $O (n)$ времени.

Если требуется вычислить коэффициенты $(\binom{n}{k})$ при фиксированном значении $n$ , можно воспользоваться формулой $(\binom{n}{k}) = \frac{n - k + 1}{k} \cdot (\binom{n}{k - 1})$ при начальном условии $(\binom{n}{0}) = 1$ . При каждом шаге итерации числитель уменьшается на $1$ (начальное значение равно $n$ ), а знаменатель соответственно увеличивается на $1$ (начальное значение — $1$ ). Для вычисления значения $(\binom{n}{k})$ этот метод требует $O (1)$ памяти и $O (k)$ времени.

Примечания

Шаблон:Примечания

Литература

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

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

[1]

[2]

Биномиальный коэффициент

Содержание

Явные формулы

Треугольник Паскаля

Свойства

Производящие функции

Делимость

Основные тождества

Бином Ньютона и следствия

Свёртка Вандермонда и следствия

Другие тождества

Матричные соотношения

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

Целозначные полиномы

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

Примечания

Литература

Навигация

Биномиальный коэффициент

Явные формулы

Треугольник Паскаля

Свойства

Производящие функции

Делимость

Основные тождества

Бином Ньютона и следствия

Свёртка Вандермонда и следствия

Другие тождества

Матричные соотношения

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

Целозначные полиномы

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

Примечания

Литература

Навигация

Поиск