Биномиальный коэффициент: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
м Добавил ссылку на статью, чтение которой нужно для понимания данной статьи |
м →Треугольник Паскаля: уже есть картинка |
||
Строка 35: | Строка 35: | ||
== Треугольник Паскаля == |
== Треугольник Паскаля == |
||
[[Файл:Треугольник Паскаля.svg|thumb]] |
[[Файл:Треугольник Паскаля.svg|thumb]] |
||
⚫ | |||
{{main|Треугольник Паскаля}} |
{{main|Треугольник Паскаля}} |
||
Строка 51: | Строка 52: | ||
Строки в треугольнике Паскаля, делённые на <math>2^n</math> (сумма всех чисел в строке), в [[Поточечная сходимость|пределе]] стремятся к функции [[распределение Гаусса|нормального распределения]]. |
Строки в треугольнике Паскаля, делённые на <math>2^n</math> (сумма всех чисел в строке), в [[Поточечная сходимость|пределе]] стремятся к функции [[распределение Гаусса|нормального распределения]]. |
||
⚫ | |||
Визуализация биномиального коэффициента до 4 степени [http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Binomial_theorem_visualisation.svg/450px-Binomial_theorem_visualisation.svg.png] |
|||
== Свойства == |
== Свойства == |
Версия от 20:34, 27 июня 2020
В математике биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона по степеням x. Коэффициент при обозначается или и читается «биномиальный коэффициент из n по k» (или «число сочетаний из n по k», читается как «це из n по k»):
(1) |
для натуральных степеней .
Биномиальные коэффициенты могут быть также определены для произвольных действительных чисел . В случае произвольного действительного числа биномиальные коэффициенты определяются как коэффициенты разложения выражения в бесконечный степенной ряд:
Для неотрицательных целых a все коэффициенты с индексами k>a в этом ряду являются нулевыми (т.е. ), и поэтому данное разложение представляет собой конечную сумму (1).
В комбинаторике биномиальный коэффициент для неотрицательных целых чисел n и k интерпретируется как количество сочетаний из n по k, то есть количество всех подмножеств (выборок) размера k в n-элементном множестве.
Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.
Явные формулы
Вычисляя коэффициенты в разложении в степенной ряд, мы получим явные формулы для биномиальных коэффициентов .
Для всех действительных чисел n и целых чисел k:
где обозначает факториал числа k.
Для неотрицательных целых n и k также справедливы формулы:
Для целых отрицательных показателей степени коэффициенты разложения равны
Треугольник Паскаля
Тождество
позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:
Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).
Строки в треугольнике Паскаля, делённые на (сумма всех чисел в строке), в пределе стремятся к функции нормального распределения.
Свойства
Производящие функции
Для фиксированного значения n производящей функцией последовательности биномиальных коэффициентов является:
Для фиксированного значения k производящей функцией последовательности биномиальных коэффициентов является:
Двумерной производящей функцией биномиальных коэффициентов для целых является:
Делимость
Из теоремы Люка следует, что:
- нечётен в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули.
- некратен простому p в p-ичной записи числа k все разряды не превосходят соответствующих разрядов числа n.
- В последовательности биномиальных коэффициентов :
- все числа не кратны заданному простому p , где натуральное число m < p;
- все числа, кроме первого и последнего, кратны заданному простому p ;
- количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);
- не может быть поровну чётных и нечётных чисел;
- количество не кратных простому p чисел равно , где числа — разряды p-ичной записи числа n; а число — её длина.
Основные тождества
Этот раздел не завершён. |
- (правило симметрии).
- (вынесение за скобки).
- (замена индексов).
- .
Бином Ньютона и следствия
- где
- где Это тождество можно усилить:
- где
или, в более общем виде,
Свёртка Вандермонда и следствия
Этот раздел не завершён. |
- (свёртка Вандермонда), где
Получается вычислением коэффициента при в тождестве . Сумма берётся по всем целым , для которых слагаемое отлично от нуля. Для произвольных действительных , число ненулевых слагаемых в сумме будет конечно.
- .
- , если , — более общий вид тождества выше.
Другие тождества
- — 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 значений, чтобы найти другие коэффициенты:
- для
Асимптотика и оценки
- при (неравенство Чебышёва).
- , при (энтропийная оценка), где — энтропия.
- (неравенство Чернова).
Непосредственно из формулы Стирлинга следует, что для верно .
Целозначные полиномы
Нетрудно видеть, что биномиальные коэффициенты являются целозначными полиномами от , т.е. принимают целые значения при целых значениях . Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.[1]
В то же время стандартный базис не позволяет выразить все целочисленные полиномы, используя только целые коэффициенты, так как уже имеет дробные коэффициенты при степенях .
Этот результат обобщается на полиномы многих переменных. А именно, если полином степени имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то
где — полином с целыми коэффициентами.[2]
Алгоритмы вычисления
Биномиальные коэффициенты могут быть вычислены с помощью формулы , если на каждом шаге хранить значения при . Этот алгоритм особенно эффективен, если нужно получить все значения при фиксированном . Алгоритм требует памяти ( при вычислении всей таблицы биномиальных коэффициентов) и времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).
При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле с начальным значением . Для вычисления значения этот метод требует памяти и времени.
Если требуется вычислить коэффициенты при фиксированном значении можно воспользоваться формулой при начальном задании . При каждом шаге итерации числитель уменьшается на (начальное значение ), а знаменатель соответственно увеличивается на (начальное значение ). Для вычисления значения этот метод требует памяти и времени.
См. также
- Биномиальное распределение
- Бином Ньютона
- История комбинаторики
- Композиция (теория чисел)
- Разбиение числа
- Треугольник Паскаля
- Треугольное число
- Теорема Люка
Примечания
- ↑ Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены. — М.: МЦНМО, 1999, 2001, 2003.
- ↑ Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993.
Литература
- Биномиальные коэффициенты // Энциклопедический словарь Брокгауза и Ефрона : в 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.