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

В математике биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона по степеням x. Коэффициент при обозначается или и читается «биномиальный коэффициент из n по k» (или «це из n по k»):

причём n здесь может быть как целым, так и произвольным действительным числом. Для неотрицательных целых n все коэффициенты с индексами k>n в этом ряду являются нулевыми, и поэтому данное разложение представляет собой конечную сумму (см. бином Ньютона).

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

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

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

Значение биномиального коэффициента определено для всех действительных чисел n и целых чисел k по формулам:

\binom{n}{k}=\begin{cases} \frac{n(n-1)(n-2)\cdot\ldots\cdot(n-k+1)}{k!}, & k\geqslant 0,\\ 0, & k<0, \end{cases}

где обозначает факториал числа m.

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

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

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

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

Тождество

позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел 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 производящей функцией последовательности биномиальных коэффициентов является:

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

Двумерной производящей функцией биномиальных коэффициентов для целых является:

Делимость

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

нечётен в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули.
некратен простому p в p-ичной записи числа k все разряды не превосходят соответствующих разрядов числа n.
В последовательности биномиальных коэффициентов :
- все числа не кратны заданному простому p , где натуральное число m < p;
- все числа, кроме первого и последнего, кратны заданному простому p ;
- количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);
- не может быть поровну чётных и нечётных чисел;
- количество не кратных простому p чисел равно , где числа — разряды p-ичной записи числа n; а число — её длина.

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

(правило симметрии).
(вынесение за скобки).
(замена индексов).

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

$\sum_{i+j=m}\binom{n}{j}\binom{n}{i}(-1)^j= \begin{cases} (-1)^{m/2} \binom{n}{m/2} & \text{if}\ m\equiv 0\pmod{2},\\ 0 & \text{if}\ m\equiv 1\pmod{2}. \end{cases}$
Это тождество можно усилить:

или, в более общем виде,

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

(свёртка Вандермонда).
.
, если , — более общий вид тождества выше.

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

— m-ое гармоническое число.
Мультисекция ряда даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом s и смещением t в виде замкнутой суммы из s слагаемых:

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

Если взять квадратную матрицу, отсчитав N элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом N, причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.

В матрице числа на диагонали i + j = const повторяют числа строк треугольника Паскаля (i, j = 0,1,…). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием. А именно:

где . Обратная матрица к U имеет вид:

Таким образом, можно разложить обратную матрицу к в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путем транспонирования, что позволяет дать явное выражение для обратных элементов:

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

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы , недостаточно приписать новую строку и столбец. Столбец j матрицы есть многочлен степени j по аргументу i, следовательно, первые p столбцов образуют полный базис в пространстве векторов длины p+1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени p-1. Нижняя строка матрицы ортогональна любому такому вектору.

при , где многочлен степени a.

Если произвольный вектор длины можно интерполировать многочленом степени , то скалярное произведение со строками (нумерация с 0) матрицы равно нулю. Используя тождество выше и равенство единицы скалярного произведения нижней строки матрицы на последний столбец матрицы , получаем:

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

где многочлен

Для доказательства сперва доказывается тождество:

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

Старший коэффициент равен 1, потребуется a-1 значений, чтобы найти другие коэффициенты:

для

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

при (неравенство Чебышёва).
, при (энтропийная оценка), где — энтропия.
(неравенство Чернова).

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

Биномиальные коэффициенты могут быть вычислены с помощью формулы , если на каждом шаге хранить значения при . Этот алгоритм особенно эффективен, если нужно получить все значения при фиксированном . Алгоритм требует памяти ( при вычислении всей таблицы биномиальных коэффициентов) и времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле с начальным значением . Для вычисления значения этот метод требует памяти и времени.

См. также

Литература

Биномиальные коэффициенты // Энциклопедический словарь Брокгауза и Ефрона: В 86 томах (82 т. и 4 доп.). — СПб., 1890—1907.
Фукс Д., Фукс М. Арифметика биномиальных коэффициентов // Квант. — 1970. — № 6. — С. 17—25.
Кузьмин О. В. Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6. — № 5. — С. 101—109.
Ландо С. К. Теневое исчисление // VIII летняя школа «Современная математика». — Дубна, 2008.
Винберг Э. Б. Удивительные арифметические свойства биномиальных коэффициентов // Математическое просвещение. — 2008. — В. 12. — С. 33–42.
Дональд Кнут, Роналд Грэхем, Орен Паташник Конкретная математика. Математические основы информатики = Concrete Mathematics. A Foundation for Computer Science. — 2-е. — М.: Мир; Бином. Лаборатория знаний; «Вильямс», 1998 — 2009. — 703, 784 с. — ISBN 95-94774-560-7, 78-5-8459-1588-7.

Sud-mal.ru

МОУ СОШ

Новости