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

Материал из Википедии — свободной энциклопедии

Биномиальные коэффициенты — коэффициенты в разложении $(1 + x) n$ по степеням $x$ (т. н. бином Ньютона):

$(1+x)^n = {n\choose 0} + {n\choose 1}x + {n\choose 2}x^2 + \cdots = \sum_k {n\choose k} x^k.$

Иначе говоря, $(1 + x) n$ является производящей функцией для биномиальных коэффициентов.

Значение биномиального коэффициента ${n\choose k}$ определено для всех целых чисел $n$ и $k$ . Явные формулы для вычисления биномиальных коэффициентов:

${n\choose k} = \frac{n!}{k!\;(n-k)!}= \frac{n(n-1)(n-2)\cdot\dots\cdot(n-k+1)}{k!}$ для $0\leqslant k \leqslant n$ ;

${n\choose k} = 0$ для

k < 0

или $0\leqslant n < k$ ;

${n\choose k} = (-1)^k {-n+k-1\choose k}$ для $n<0\leqslant k$ ,

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

Биномиальный коэффициент ${n\choose k}$ является обобщением числа сочетаний $C^k_n$ , которое определено только для неотрицательных целых чисел $n$ , $k$ .

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

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

Содержание

1 Треугольник Паскаля
2 Свойства
3 Тождества
4 Асимптотика и оценки
5 Алгоритмы вычисления биномиальных коэффициентов
6 См. также
7 Ссылки

[править] Треугольник Паскаля

Основная статья: Треугольник Паскаля

Тождество

${n\choose k}={n-1\choose k-1} + {n-1\choose 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\\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots & \end{matrix}$

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

[править] Свойства

Интересно, что если рассмотреть ряды в треугольнике Паскаля, состоящие из биномиальных коэффициентов, то в пределе получим функцию нормального распределения — распределение Гаусса.

Из теоремы Люка следует, что:

${n\choose k}$ нечётен $\iff$ в двоичной записи числа $k$ единицы не стоят в тех разрядах, где в числе $n$ стоят нули,
${n\choose k}$ некратен простому $p$ $\iff$ в $p$ -ичной записи числа $k$ все разряды не превосходят соотв. разрядов числа $n$ ,
В ряду биномиальных коэффициентов :
- все числа не кратны заданному простому $p$ $\iff$ $n = m p k - 1$ , где натуральное $m < p$ ,
- все числа, кроме первого и последнего, кратны заданному простому $p$ $\iff$ $n = p k$ , где натуральное $m < p$ ,
- количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n),
- не может быть поровну чётных и нечётных чисел,
- количество не кратных простому $p$ чисел равно $(a_1+1)\ldots(a_m+1)$ , где числа $a_1,\ldots,a_m$ — разряды $p$ -ичной записи числа $n$ ; а число $m = [l o g p n] + 1$

[править] Тождества

${n\choose k} = {n-1\choose k-1} + {n-1\choose k}$
${n\choose k} = {n\choose n-k}$ (правило симметрии)
${n\choose 0} + {n\choose 1} + \cdots + {n\choose n} = 2^n$
${n\choose 0} - {n\choose 1} + \cdots + (-1)^n{n\choose n} = 0$
${n\choose 0} + {n\choose 2} + \cdots + {n\choose 2\lfloor n/2\rfloor} = 2^{n-1}$
${n\choose 0}^2 + {n\choose 1}^2 + \cdots + {n\choose n}^2 = {2n\choose n}$
$\sum_{k=0}^n{r\choose m+k}{s\choose n-k}={r+s\choose m+n}$ (свёртка Вандермонда)
Мультисекция ряда $(1 + x) n$ дает следующее тождество, выражающее суммы биномиальных коэффициентов с произвольным шагом s $(0\leqslant t<s)$ в виде замкнутой суммы из s слагаемых:

$\binom{n}{t} + \binom{n}{t+s} + \binom{n}{t+2s} + \ldots = \frac{1}{s} \sum_{j=0}^{s-1} \left(2\cos\frac{\pi j}{s}\right)^n \cos\frac{\pi(n-2t)j}{s}.$

[править] Асимптотика и оценки

${2n\choose n}\sim \frac{2^{2n}}{\sqrt{\pi n}}$
$\sum^{m}_{k=0}{n\choose k}\leqslant \frac{n}{(n/2-m)^2}2^{n-3}$ при $m < n / 2$ (неравенство Чебышёва)
$\sum^{m}_{k=0}{n\choose k}\leqslant 2^{nH(m/n)}$ (энтропийная оценка), где $H (x) = - x log 2 x - (1 - x)log 2 (1 - x)$ — энтропия.
$\sum^{n/2-\lambda}_{k=0}{n\choose k} \leqslant 2^ne^{-2\lambda^2/n}$ (неравенство Чернова)

[править] Алгоритмы вычисления биномиальных коэффициентов

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

Второй способ основан на тождестве ${n\choose k}=\frac{n}{n-k}{n-1\choose k}$ . Он позволяет вычислить значения ${n\choose k}$ при фиксированном $k$ . Алгоритм требует $O (1)$ памяти ( $O (l)$ если нужно посчитать $l$ последовательных коэффициентов с фиксированным $k$ ) и $O (k)$ времени.

[править] См. также

[править] Ссылки

О. В. Кузьмин Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6. — № 5. — С. 101—109.
С. К. Абачиев Радужная фрактальность треугольника Паскаля

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

Материал из Википедии — свободной энциклопедии

Содержание

[править] Треугольник Паскаля

[править] Свойства

[править] Тождества

[править] Асимптотика и оценки

[править] Алгоритмы вычисления биномиальных коэффициентов

[править] См. также

[править] Ссылки

Просмотры

Личные инструменты

Навигация

Поиск

Участие

Инструменты

На других языках