- Биномиальный коэффициент
-
В математике биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона
по степеням x. Коэффициент при
обозначается
или
и читается «биномиальный коэффициент из n по k» (или «це из n по k»):
В комбинаторике биномиальный коэффициент
интерпретируется как количество сочетаний из n по k, то есть количество всех подмножеств (выборок) размера k в n-элементном множестве.
Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.
Содержание
Явные формулы
Значение биномиального коэффициента
определено для всех целых чисел n и k. Явные формулы для вычисления биномиальных коэффициентов:
для
для
или
для
где
обозначает факториал числа m.
Треугольник Паскаля
Тождество
позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:
Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).
Строки в треугольнике Паскаля в пределе стремятся к функции нормального распределения.
Если взять квадратную матрицу, отсчитав N элементов по катетам треугольника и повернув квадрат на любой из четырёх углов, то детерминант этих четырёх матриц по модулю равен 1 при любом N. Если поставить уголом из 1 в верхний левый угол, то детерминант матрицы будет равен 1.
В матрице
числа на диагонали i + j = const повторяют числа строк треугольника Паскаля (i, j = 0...∞).
Матрицу
, где i, j = 0..p можно разложить в произведение двух строго диагональных матриц. Первая нижнетреугольная, а вторая получается из первой путем транcпонирования. Матрицы
удовлетворяет соотношению:
где i, j = 0..p.
Обратная матрица к U имеет вид:
Таким образом, можно разложить обратную матрицу к
в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путем транспонирования, что позволяет дать явное выражение для обратных элементов:
, где i, j , m, n = 0..p.
Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы
, недостаточно приписать новую строку и столбец.
Свойства
Производящие функции
Для фиксированного значения n производящей функцией последовательности биномиальных коэффициентов
является:
Для фиксированного значения k производящей функцией последовательности биномиальных коэффициентов
является:
Двумерной производящей функцией биномиальных коэффициентов является:
Делимость
Из теоремы Люка следует, что:
нечётен
в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули.
некратен простому p
в p-ичной записи числа k все разряды не превосходят соответствующих разрядов числа n.
- В последовательности биномиальных коэффициентов
:
- все числа не кратны заданному простому p
, где натуральное число m < p;
- все числа, кроме первого и последнего, кратны заданному простому p
;
- количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);
- не может быть поровну чётных и нечётных чисел;
- количество не кратных простому p чисел равно
, где числа
— разряды p-ичной записи числа n; а число
— её длина.
- все числа не кратны заданному простому p
Основные тождества
(правило симметрии).
(вынесение за скобки).
(замена индексов).
Бином Ньютона и следствия
для
.
Это тождество можно усилить
Свёртка Вандермонда и следствия
(свёртка Вандермонда).
.
если
— более общий вид тождества выше.
Другие тождества
— m-ое гармоническое число.
- Мультисекция ряда
даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом s и смещением t
в виде замкнутой суммы из s слагаемых:
Асимптотика и оценки
при
(неравенство Чебышёва).
, при
(энтропийная оценка),
где
— энтропия.
(неравенство Чернова).
Алгоритмы вычисления
Биномиальные коэффициенты могут быть вычислены с помощью формулы
, если на каждом шаге хранить значения
при
. Этот алгоритм особенно эффективен, если нужно получить все значения
при фиксированном
. Алгоритм требует
памяти (
при вычислении всей таблицы биномиальных коэффициентов) и
времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).
При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле
с начальным значением
. Для вычисления значения
этот метод требует
памяти и
времени.
См. также
- Биномиальное распределение
- История комбинаторики
- Композиция (теория чисел)
- Пирамида Паскаля
- Разбиение числа
- Треугольник Паскаля
- Треугольное число
Ссылки
- Фукс Д., Фукс М. Арифметика биномиальных коэффициентов // Квант. — 1970. — № 6. — С. 17—25.
- Абачиев С. К. О треугольнике Паскаля, простых делителях и фрактальных структурах // Журнал "В мире науки". — 1989. — № 9. — С. 112—119.
- Кузьмин О. В. Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6. — № 5. — С. 101—109.
- Ландо С. К. Теневое исчисление // VIII летняя школа «Современная математика». — Дубна, 2008.
- Винберг Э. Б. Удивительные арифметические свойства биномиальных коэффициентов // Математическое просвещение. — 2008. — В. 12. — С. 33–42.
Категория:- Комбинаторика
Wikimedia Foundation. 2010.