Бином Ньютона не бином Ньютона
У меня давно уже руки чешутся исправить кое-какую историческую несправедливость. Сейчас как почешу…
Вы же знаете, как люди говорят: “Ну это же не бином Ньютона!” – подразумевая, что вот этот бином – забористая вещь, а всё остальное на его фоне – так, ерунда. Но на самом деле это очаровательная маленькая формула, которая здорово облегчает жизнь всем, кто имеет дело с уравнениями.
“Но я, – можете возразить вы мне, – не имею никаких дел с уравнениями.” А вот и нет. В статистических расчётах, оценках стоимости проекта, в планировании архитектурных сооружений и оптимизации компьютерных программ – везде уравнения. В формировании прогнозов погоды уравнения, а уж прогнозы погоды-то вы точно смотрите.
И везде, абсолютно везде можно применить бином Ньютона, чтобы сократить объёмы вычислений. Так что я вам сообщаю со всей серьёзностью: бином Ньютона заслуживает вашей любви.
Он, кроме того, заслуживает любви, потому что представляет собой образец чистой математической эстетики. Он сформулирован так удивительно изящно, что им нельзя не любоваться. Давайте же рассмотрим его поближе. Вы его легко узнаете: он знаком вам со школы, просто не всем его представляют как положено.
Итак, бином Ньютона – универсальный инструмент для разложения на слагаемые любого выражения вида
У меня в школе их предлагалось просто заучить, что, на мой взгляд, есть форма насилия над личностью. На самом же деле ученикам нужно знать про биномиальный коэффициент – число способов, которыми можно выбрать k объектов из n объектов в любом порядке (где k меньше n, разумеется): три объекта из четырёх, два из восьми и так далее.
Биномиальный коэффициент
Давайте рассмотрим простой пример: у нас есть четыре буквы (А, Б, В, Г), и мы из них выбираем разными способами по две. Вы можете легко проверить, что таких вариантов всего 12, записав их на бумаге: “АБ”, “АВ”, “АГ”, “БА” и так далее.
Каждый раз, когда мы выбираем букву на первое место в паре, у нас 4 варианта, а когда выбираем на второе место – 3 (потому что одну букву уже забрали). В итоге, число таких пар можно посчитать так: 4*3. Очень просто.
В общем виде, когда у нас n букв, из которых надо выбрать k, получается так:
(n-k+1) – это число объектов, которые остаются на выбор для последней позиции. В нашем случае на вторую позицию мы выбирали из (4-2+1) = 3 букв. Если бы мы выбирали не пары, а тройки, у нас бы на первую позицию было четыре варианта, на вторую три, на третью – два. 4*3*(4-3+1) = 24 комбинации. Попробуйте выписать все комбинации и проверить.
Чтобы записать эту формулу короче, воспользуемся факториалом (!). Помните, что такое факториал? Произведение всех натуральных чисел от 1 до данного числа.
В нашей формуле n*(n-1)*(n-2)*...*(n-k+1) у нас почти получается n!. Почти.
Вернёмся к примеру с четырьмя буквами: 4! = 24, а мы знаем, что, если выбирать парами, комбинаций будет 12. То есть, в формуле факториала нам не нужно всё, что идёт дальше тройки (у нас же только две позиции). А что идёт после тройки? 2!
То есть, (n-k)! в общем виде. Поняли, почему так?
Полная формула факториала n с учётом того, что есть некое k, и оно меньше n, была бы записана так:
Но весь длинный хвост после (n-k+1) нам без надобности. Почему? У нас позиции закончились, куда выбирать объекты. Остальные не нужны. Приглядевшись, мы понимаем, что ненужный хвост представляет собой факториал (n-k). Чтобы его не использовать, можно факториал n на него поделить. Вот так:
Хотя подождите. Мы с вами считали пары типа “АБ” и “БА”, а это одно и то же. Иногда это важно, но не здесь. Это важно, когда позиция 1 и позиция 2 – это два разных исхода: первое и второе место на соревновании, первая и вторая локации в маршруте на карте и так далее. Если мы генерируем пароли, например, позиции каждого объекта – буквы или цифры – тоже важны. Но это не наш случай.
У нас случай вида “мы достали пять белых шариков из мешка, где было восемь белых шариков.” Не важно, какой белый шарик мы достали первым. И как нам теперь выкинуть повторяющиеся варианты?
Да просто, на самом деле. В нашем примере с четырьмя буквами мы выбирали пару. Выбрали. Сколько есть вариантов переставить выбранные две буквы местами? 2! (это факториал, а не эмоциональное восклицание, если что). На первую позицию у нас два кандидата, на вторую – один: 2*1 = 2!
Если бы мы выбирали тройки, число перестановок выбранных букв было бы равно по той же логике факториалу трёх: 3*2*1 = 3!
Ну и всё. Берём нашу формулу и делим ещё на факториал k, потому что мы выбирали объекты на k позиций, и так мы уберём все перестановки одних и тех же объектов местами. Вышло
В нашем примере осталось шесть комбинаций: “АБ”, “АВ”, “АГ”, “БВ”, “БГ”, “ВГ”. Можете остановиться и проверить, записав их на бумаге.
И мы с вами получили биномиальный коэффициент, который записывается так: C(n, k) – “число комбинаций из n по k штук”.
Бином
На самом деле, придумал не Ньютон. Этот принцип осознали и записали математики из Персии и Индии очень-очень давно. Ньютон же вывел общий случай, сделав формулу применимой к любому показателю степени: хоть (x + y) в квадрате, хоть в кубе, хоть в степени 115. Как?
Её можно записать следующим образом:
И так с любой степенью. Что мы сейчас делаем, если не перебираем комбинации?
Из каждой скобки берём одно число, перемножаем с числом из другой скобки, складываем. И нам не важен порядок чисел: x*y = y*x. Идеальный сценарий для применения биномиального коэффициента. Давайте возьмём куб суммы для примера:
Выберем 0 y из 3 скобок: C(3, 0). Способов это сделать
3! / (0! (3-0)!) = 1.
Факториал нуля и единицы равен единице. Тому есть причина, но про неё в другой раз.
Единственная комбинация, которую мы получим — x*x*x
Теперь выберем 1 y из 3 скобок. Сколько у нас вариантов? С(3, 1):
3! / (1! * (3-1)!) = 3
Это будут комбинации x*x*y + x*y*x + y*x*x, – все одинаковые и все равны
Потом мы так же выберем 2 y из 3 скобок и 3 y из 3 скобок и закончим наш расчёт, получив ровно ту формулу, которую я привела вам в самом начале:
Коэффициенты 1, 3, 3 и 1 перед каждым слагаемым биномиальные коэффициенты С(3,0), С(3,1), С(3,2) и С(3,3).
А теперь обратим внимание на степени x и y. Видите закономерность?
Показатель степени x справа налево уменьшается:
а показатель степени y растёт:
И понятно, почему: сначала мы брали ровно 0 y из 3 – степень 0; потом 1 из 3 – степень 1, и так далее. А все незанятые y места были заняты x, поэтому их сначала было 3, а в конце стало 0.
Ну разве это не красиво? Согласитесь же, что красиво.
Треугольник Паскаля
Есть ещё одна невероятно изящная штука, которую надо брать в комплекте с биномом Ньютона – треугольник Паскаля. Его придумал и описал не Паскаль, но Паскаль настолько крут, что в европейской традиции назвали треугольник в его честь. А вообще его в разных странах по-разному называют. Вот он:
Этот треугольник позволяет не высчитывать каждый раз биномиальный коэффициент.
В первой строке единица, она соответствует сумме
Что угодно в нулевой степени равно единице, так что всё просто.
Вторая строка соответствует сумме
Видите, что происходит? Каждая строка – это набор коэффициентов перед слагаемыми. В четвёртой строке коэффициенты 1, 3, 3, 1 для формулы
Написать такой треугольник просто: по границе единицы, а внутри каждое число равно сумме двух чисел над ним.
Всё, теперь любая сумма двух слагаемых в любой степени у вас в кармане. Хотела бы я узнать об этом в школе! (это не факториал, а эмоциональное восклицание)
С разностями тоже ничего сложного, на самом деле. Всё, что вам нужно знать – если отрицательное число возвести в чётную степень, результат положительный, если в нечётную – отрицательный. Соответственно, если мы имеем (x - y), нам всего лишь надо будет заменить минус на плюс перед y везде, где он в нечётной степени.
Спойлер: знаки будут просто чередоваться: +-+-+-
Начинаем с плюса перед x (он-то положительный тут персонаж) и чередуем. И несложно заметить, что минусы там, где у y нечётная степень: 1 и 3.
Вот и всё. Теперь, когда вам скажут: “Да это же не бином Ньютона,” – с чистой совестью отвечайте: “Конечно, бином Ньютона такой замечательный, а вы мне суёте какую-то ерунду!”