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

Биномиальные коэффициенты — коэффициенты в разложении (1 + x)ⁿ по степеням 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\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 &amp;lt; k$;

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

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

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

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

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

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

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

Тождество

${n\choose k}={n-1\choose k-1} + {n-1\choose k}$

позволяет расположить биномиальные коэффициенты для неотрицательных n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

$\begin{matrix} n=0: &amp;amp; &amp;amp; &amp;amp; &amp;amp; &amp;amp; 1 &amp;amp; &amp;amp; &amp;amp; &amp;amp;\\ n=1: &amp;amp; &amp;amp; &amp;amp; &amp;amp; 1 &amp;amp; &amp;amp; 1 &amp;amp; &amp;amp; &amp;amp;\\ n=2: &amp;amp; &amp;amp; &amp;amp; 1 &amp;amp; &amp;amp; 2 &amp;amp; &amp;amp; 1 &amp;amp; &amp;amp;\\ n=3: &amp;amp; &amp;amp; 1 &amp;amp; &amp;amp; 3 &amp;amp; &amp;amp; 3 &amp;amp; &amp;amp; 1 &amp;amp;\\ n=4: &amp;amp; 1 &amp;amp; &amp;amp; 4 &amp;amp; &amp;amp; 6 &amp;amp; &amp;amp; 4 &amp;amp; &amp;amp; 1\\ \vdots &amp;amp; &amp;amp; \vdots &amp;amp; &amp;amp; \vdots &amp;amp; &amp;amp; \vdots &amp;amp; &amp;amp; \vdots &amp;amp; \end{matrix}$

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

Свойства

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

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

• ${n\choose k}$ нечётен $\iff$ в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули,
• ${n\choose k}$ некратен простому p $\iff$ в p-ичной записи числа k все разряды не превосходят соотв. разрядов числа n,
• В ряду биномиальных коэффициентов ${n\choose 0}, \ldots, {n\choose k}, \ldots, {n\choose n}$:
  • все числа не кратны заданному простому p $\iff$ n = mp^k − 1, где натуральное m < p,
  • все числа, кроме первого и последнего, кратны заданному простому p $\iff$ n = p^k, где натуральное m < p,
  • количество нечётных чисел равно степени двойки,
  • не может быть поровну чётных и нечётных чисел,
  • количество не кратных простому p чисел равно $(a_1+1)\ldots(a_m+1)$, где числа $a_1,\ldots,a_m$ — разряды p-ичной записи числа n; а число m = [log_pn] + 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)ⁿ дает следующее тождество, выражающее суммы биномиальных коэффициентов с произвольным шагом s $(0\leqslant t&amp;lt;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) = − xlog₂x − (1 − x)log₂(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²) при вычислении всей таблицы биномиальных коэффициентов) и O(n²) времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

Второй способ основан на тождестве ${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.
• С. К. Абачиев Радужная фрактальность треугольника Паскаля