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

Биномиальные коэффициенты В комбинаторике биномиальный коэффициент означает, число всех  возможных вариантов выборки k элементов из множества элементов n. Пример: Из множества n {1,2,3,4}, выбираем все возможные комбинации из двух элементов, k=2 {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} Получается шесть возможных вариантов. Подставив значения в формулу, проверим полученный результат: Расширенные биномиальные коэффициенты В данном очень важном приложении речь пойдёт о биномиальных коэффициентах, точнее,  об их расширении на случай произвольных значений верхнего индекса. Иногда такая тема в литературе называется «расширенный треугольника Паскаля», поскольку расширение  биномиальных коэффициентов влечёт за собой расширение треугольника Паскаля,  который из этих коэффициентов состоит, а также рассматриваемая здесь  функция(1+z)n (точнее, её разложение в ряд) называется биномиальным рядом. Свойства биномиальных коэффициентов и доказательства основных тождеств в этом  разделе не предусматривается, речь о них идёт только в контексте производящих функций. Предполагается, что читатель знаком с основными положениями комбинаторики или, по  крайней мере, встречался с ними в реальной жизни. Ведь математика окружает нас со всех  сторон. Числа, закономерности и разнообразные комбинации могут появиться где угодно:  во время похода в магазин, расчета шансов на победу в казино, в теории управления и даже в футурологических прогнозах. В целом, все умеют считать. Но иногда комбинаторикаоказывается более сложной, чем это необходимо в повседневной жизни. Скажем, при  расчётах энтропии некоторой сложной физической системы, когда требуется вычислять  количество допустимых конфигураций соответствующей физической модели. Так вот  расширенные биномиальные коэффициенты как раз больше относятся к научным, а не  повседневным расчетам. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ Здесь я вынужден немного остановиться на определениях и обозначениях, чтобы не  возникало недоразумений. Подготовленный читатель может пропустить этот пункт. Биномиальный коэффициент обозначается символом  , или (что часто встречается в  русской литературе)  . Давайте сразу определимся с обозначениями. Правильное обозначение для биномиальных  коэффициентов не  , как учат в российских школах (и в университетах), а  . К  сожалению, я не знаю, по какой причине в России чаще используется обозначение  , а в  остальном Мире —  . Поэтому учтите, что если вы пишите статью для российских  журналов, вас поймут, как бы вы эти коэффициенты не обозначили, а для зарубежных  журналов советую писать правильно. Читается этот символ разными способами: «число сочетаний из n по k», или просто  «изn по k», а также говорят «выбор k из n». Смысл указанных выражений заключён в  комбинаторной интерпретации этого символа — это число способов выбрать k объектов  из nразличных объектов, причём порядок выбора не важен. Например, из  множества{1,2,3,4,5} можно выбрать два элемента десятью способами: Таким образом, В общем случае известно, чтоВ процессе вычислений, чтобы не считать лишние факториалы, можно сразу часть  множителей сократить: От этой формулы и будем отталкиваться в будущем. Именно она и является правильным  определением биномиальных коэффициентов. Число n называется верхним индексом,  аk — нижним. В соответствии с комбинаторной интерпретацией, числа n и k должны быть  целыми неотрицательными. Наша задача будет заключаться в том, чтобы расширить  определение на произвольные значения n. Биномиальные коэффициенты, упорядоченные специальным образом,  образуюттреугольник Паскаля. В XVII веке французский математик, физик, философ Блез Паскаль впервые в своем  «трактате об арифметическом треугольнике» наиболее полно рассказал о свойствах этого  самого треугольника (хотя сам треугольник встречался в работах других математиков  задолго до Паскаля). Строится этот замечательный треугольник очень просто: По краям треугольника ставятся единицы, а любое число, стоящее не с краю, вычисляется  как сумма двух чисел, расположенных сверху слева и сверху справа от него.  Например, 10=4+6, или 3=1+2. Итак, речь зашла о треугольнике Паскаля в связи с тем,  что он как раз образован биномиальными коэффициентами:Для наших целей (и для удобства) лучше записывать треугольник, выравнивая его по  левому краю: Нули появляются за счёт нуля в числителе (когда k>n). Заметьте, что в нулевом столбце  ставятся единицы, так как В числителе стоит произведение нулевого числа элементов, которое по определению равно  1. Данная формула верна для любого (в том числе, комплексного) n. Ну вот, мы уже приближаемся к тому, чтобы изучить биномиальные коэффициенты для  любого n. Наше расширение, во­первых, должно быть таким, чтобы формула осталась  прежней (для удобства), во­вторых, треугольник Паскаля, образованный биномиальными  коэффициентами (с целым отрицательным значением индекса), не должен потерять своё  основное свойство: оно гласит, что число в клетке (n,k) равно сумме верхнего числа и верхнего левого (когда  числа выровнены по левому краю).В­третьих (что самое важное), должна остаться справедливой биномиальная теорема,  утверждение которой напоминается в следующем пункте. БИНОМИАЛЬНАЯ ТЕОРЕМА Содержание данной теоремы в классической формулировке известно еще из средних  классов школы: Это выражение также носит название бином Ньютона. Коэффициенты бинома Ньютона и  называются биномиальными коэффициентами. Теперь, пользуясь биномом Ньютона и треугольником Паскаля, можно посчитать,  например (взяв третью строчку треугольника), Данный сайт посвящён производящим функциям, поэтому нас данная теорема интересует  лишь с этой позиции. Запишем производящую функцию в следующем виде: Представленная производящая функция генерирует последовательность биномиальных  коэффициентов с верхним индексом, равным n. Верхний индекс в сумме можно записать  равным ∞, это ничего не меняет, когда n целое неотрицательное (почему?). Обратите  внимание, что подстановка z=1 даёт замечательное тождество (ряд конечный, поэтому  подстановка справедлива): которое показывает, что сумма всех чисел в n­й строке треугольника Паскаля равняется  двойке, возведённой в степень n. Данное разложение функции (1+z)n в ряд согласуется с формулой Тейлора, в соответствие  с которой коэффициент, стоящий при zk равенНапомню, что для этой функции ряд Тейлора сходится при |z|<1 (когда n произвольно).  Эта функция также носит название «Биномиальный ряд». РАСШИРЕНИЕ Теперь нас интересует ответ на вопрос: можно ли допустить в биномиальной теореме,  чтобы n было целым отрицательным? Можно, причём треугольник Паскаля расширяется  «вверх» единственным образом, если мы хотим сохранить его основное свойство: при этом  . Рассмотрим отрицательные строчки подробнее: Например, минус первая строка треугольника может быть только такой, и никакой иначе,  поскольку  , а остальные элементы вычисляются однозначно: Для чего нужны расширенные биномиальные коэффициенты? Для того, чтобы  раскладывать в ряд простые дроби. Например, Поэтому, кстати (читайте о разложении 1/(1−z)),Теперь выведем формулу для целых отрицательных биномиальных коэффициентов исходя  не из их положения в треугольнике, а из их правильного определения: Таким образом, Данная формула также согласуется с разложением этой функции в ряд Тейлора для |z|<1. Пойдём дальше. На практике могут пригодиться рациональные показатели степени,  например, рассмотрим биномиальный ряд для n=1/2: Эта формула даёт нам возможность раскладывать в ряд функциюАналогично (мы оставляем подробный вывод читателю), а это, в свою очередь, позволяет записать ещё одну полезную производящую функцию: Биномиальные коэффициенты Биномиальным коэффициентом  предметов из  количество неупорядоченных наборов).  различных предметов без учёта порядка расположения этих элементов (т.е.   называется количество способов выбрать набор    Также биномиальные коэффициенты ­ это коффициенты в разложении  Ньютона):  (т.н. бином  Считается, что эту формулу, как и треугольник, позволяющий эффективно находить  коэффициенты, открыл Блез Паскаль (Blaise Pascal), живший в 17 в. Тем не менее, она  была известна ещё китайскому математику Яну Хуэю (Yang Hui), жившему в 13 в.  Возможно, её открыл персидский учёный Омар Хайям (Omar Khayyam). Более того,  индийский математик Пингала (Pingala), живший ещё в 3 в. до н.э., получил близкие  результаты. Заслуга же Ньютона заключается в том, что он обобщил эту формулу для  степеней, не являющихся натуральными. Вычисление Аналитическая формула для вычисления:Эту формулу легко вывести из задачи о неупорядоченной выборке (количество способов  неупорядоченно выбрать   элементов из  упорядоченных выборок. Выбрать первый элемент есть  третий —   элементов). Сначала посчитаем количество  ,  , и так далее. В результате для числа упорядоченных выборок получаем   способов, второй —  формулу:  перейти, если заметить, что каждой неупорядоченной выборке соответствует ровно  упорядоченных (т.к. это количество всевозможных перестановок   элементов). В  . К неупорядоченным выборкам легко    результате, деля   на  , мы и получаем искомую формулу. Рекуррентная формула (с которой связан знаменитый "треугольник Паскаля"): Её легко вывести через предыдущую формулу. Стоит заметить особо, при   значение   всегда полагается равным нулю. Свойства Биномиальные коэффициенты обладают множеством различных свойств, приведём  наиболее простые из них:  Правило симметрии:  Внесение­вынесение:  Суммирование по  :  Суммирование по  :  Суммирование по   и  : Суммирование квадратов:  Взвешенное суммирование:  Cвязь с числами Фибоначчи: Вычисления в программе Непосредственные вычисления по аналитической формуле Вычисления по первой, непосредственной формуле, очень легко программировать, однако  этот способ подвержен переполнениям даже при сравнительно небольших значениях   и    (даже если ответ вполне помещается в какой­нибудь тип данных, вычисление  промежуточных факториалов может привести к переполнению). Поэтому очень часто этот  способ можно применять только вместе с [[Длинная арифметика|Длинной арифметикой]]:   int C (int n, int k) { int res = 1; for (int i=n­k+1; i<=n; ++i) res *= i; for (int i=2; i<=k; ++i) res /= i; } Улучшенная реализация Можно заметить, что в приведённой выше реализации в числителе и знаменателе стоит  одинаковое количество сомножителей ( ), каждый из которых не меньше единицы.  Поэтому можно заменить нашу дробь на произведение   дробей, каждая из которыхявляется вещественнозначной. Однако, можно заметить, что после домножения текущего  ответа на каждую очередную дробь всё равно будет получаться целое число (это,  например, следует из свойства "внесения­вынесения"). Таким образом, получаем такую  реализацию:   int C (int n, int k) { double res = 1; for (int i=1; i<=k; ++i) res = res * (n­k+i) / i; return (int) (res + 0.01); } Здесь мы аккуратно приводим дробное число к целому, учитывая, что из­за  накапливающихся погрешностей оно может оказаться чуть меньше истинного значения  (например,   вместо трёх). Треугольник Паскаля С использованием же рекуррентного соотношения можно построить таблицу биномиальных коэффициентов (фактически, треугольник Паскаля), и из неё брать результат.  Преимущество этого метода в том, что промежуточные результаты никогда не превосходят ответа, и для вычисления каждого нового элемента таблицы надо всего лишь одно  сложение. Недостатком является медленная работа для больших N и K, если на самом деле таблица не нужна, а нужно единственное значение (потому что для вычисления  понадобится строить таблицу для всех  до  , или хотя бы    ).   const int maxn = ...; int C[maxn+1][maxn+1]; for (int n=0; n<=maxn; ++n) { C[n][0] = C[n][n] = 1;for (int k=1; k 0 с нечетными номерами взяты со  знаком плюс, а с четными – со знаком минус?Ответ Чрезвычайно важное свойство биномиального разложения связано с тем, что его  коэффициенты   оказывается, представляют собой не что иное, как числа сочетаний по  элементов из множества с   элементами (см. «Комбинаторика»; там же доказывается общая формула для этих чисел:  ). Приведем одно из свойств, связанных с делимостью биномиальных коэффициентов.  Рассмотрим таблицу 2. Легко видеть, что все числа ее 5­й строки, кроме крайних единиц,  делятся на 5; все числа 7­й строки, кроме крайних единиц, делятся на 7. У каких еще строк есть такое же свойство? Очевидно – у 2­й и 3­й. А у остальных, легко видеть, такого  свойства нет. Что объединяет числа 2, 3, 5 и 7 и отличает их от других чисел первого  десятка? Правильно, все они простые. Можно доказать, что, действительно, все числа n­ой  строки треугольника Паскаля (в форме таблицы 2), кроме крайних единиц, делятся  на n тогда и только тогда, когда n простое. Еще одно красивое свойство треугольника Паскаля (в форме таблицы 2) связано с  вопросом, сколько нечетных чисел содержит n­я строка. Оказывается, число этих нечетных чисел всегда равно 2k, где k – число единиц в двоичной записи числа n. Проверьте этот  неочевидное свойство самостоятельно. И наконец приведем сравнительно недавно и, в общем, то, случайно обнаруженное  свойство треугольника Паскаля, связывающее его с простыми числами(Г. В. Манн, Д.  Шенкс, 1972 г.). Запишем строки треугольника Паскаля (в форме таблицы 2), каждый раз  сдвигая строки вправо на две позиции. 0    1 1 2 3 4 1 1 1 2 1 1 3 3 1 1 4 6 4 15 6 7 8 9 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 1 8 28 56 1 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Таблица 4. Связь ряда простых чисел и треугольника Паскаля Числа, стоящие в таблице, выделены, если они делятся на номер строки. Числа в нижней  строке, нумерующие столбцы, выделены, если в этом столбце все числа выделены.  Выходит, что выделенные номера столбцов в точности соответствуют простым числам. Биномиальные коэффициенты и их свойства Из курса алгебры хорошо известна формула квадрата  суммы:  А теперь выведем формулу куба суммы:  результат умножения  так:   Давай посмотрим,  сколько в полученной сумме слагаемых, в которых два множителя a и один множитель b?  Таких слагаемых три: aab, aba, baa — столько же, сколько способов выбора из трёх  элементов по два. Это число мы знаем —  других комбинаций множителей. Тогда получим формулу куба  суммы:   Так же можно рассуждать и для любых   Запишем  Таким же способом можно получить формулу для возведения a + b в произвольную  натуральную степень n. Тогда  всего n множителей. Если раскрыть скобки, то получим сумму  из которых является произведением n множителей, взятых по одному из каждой скобки.  слагаемых, каждоеПредположим, что в некотором таком произведении ровно k множителей a. Тогда в этом  произведении множитель b встречается n – k раз. Поэтому произведение можно записать в  виде одночлена  А сколько раз встречается этот одночлен в сумме? Столько, сколько есть способов  расставить k множителей среди n множителей, т. е.  формулу, которая называется  Таким образом, получаем  бином Ньютона: Числа сочетаний  называются биномиальными коэффициентами. , которые используются в формуле бинома Ньютона, по­другому  Основные свойства биномиальных коэффициентов: 1. Число всех членов разложения на единицу больше показателя степени бинома, т. е.  равно n + 1. 2. Сумма всех коэффициентов разложения (a + b)n равна 2n. 3. Коэффициенты членов, равноудалённых от концов разложения, равны. 4. Для каждого члена разложения сумма показателей степеней a и b равна показателю  степени бинома. 5. Сумма биномиальных коэффициентов разложения, стоящих на нечётных местах,  равна сумме биномиальных коээффициентов, стоящих на чётных местах, и равна 2n – 1. Кроме этого, мы уже знаем, что  и  Треугольник Паскаля Мы умеем находить числа   по  формуле  удобно.    Но это не оченьСоставим таблицу этих чисел. Запишем первую строку, n = 1,  тогда  Теперь вторая строка. Мы знаем, что  второй строке равны 1. А для нахождения  свойство:  сумма двух чисел первой строки.  значит, крайние числа во   используем   То есть,   получается как  Третья строка и все последующие получаются по тем же правилам: 1. Крайние числа в каждой строке равны 1. 2. Любое не крайнее число во всех строках, начиная со второй, получается сложением двух чисел, стоящих над ним (в том же столбце и в предыдущем). 6 7 8 9 10 120 210 252 210 120 45 Этот треугольник называется числовым, арифметическим, а также треугольником  Паскаля по имени выдающегося французского математика Блеза Паскаля, изучавшего  свойства этого треугольника. Чаще треугольник поворачивают на 45°, тогда он выглядит  так: n 1 2 3 4 5 6 7 8 9 10 k 0 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 10 2   1 3 6 10 15 21 28 36 45 3     1 4 10 20 35 56 84 4       1 5 15 35 70 5         1 6 21 56 126 126           1 7 28 84             1 8 36               1 9                 1 10                   1Обычно устройство треугольника Паскаля объясняют просто: каждое число равно сумме  двух расположенных над ним чисел. Всё элементарно, но сколько в этом таится чудес!