5.3 СПЕЦИАЛЬНЫЕ ПРИЕМЫ

Теперь рассмотрим три технических приема, представляющих собой существенное развитие методов, изученных ранее.

Прием 1: выполовинивание

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

Один из способов понять, как это делается, - начать с формулы удвоения:

Это соотношение становится очевидным, если разложить убывающие степени и расположить в левой части множители в чередующемся порядке:

Теперь можно разделить обе части на получая

Если положить где — целое, то это дает

А обращение верхнего индекса доставляет еще одну полезную формулу:

Так, при получаем

Обратите внимание, как мы заменили произведение нечетных чисел на факториал.

Тождество (5.35) приводит к занятному следствию. Положим возьмем сумму по всем целым к. Тогда, согласно (5.23), получим следующий результат:

поскольку либо либо равно — целому неотрицательному числу!

Можно также воспользоваться сверткой Вандермонда (5.27) и получить формулу

Подстановка значений из (5.37) дает

что в сумме равно Следовательно, установлено замечательно свойство „средних" элементов треугольника Паскаля:

Например,

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

Прием 2: разности высших порядков

Ранее мы убедились в том, что частичные суммы ряда с общим членом вычислить можно, а ряда с общим членом — нельзя. Оказывается, что существует много важных приложений биномиальных коэффициентов с чередованием знаков — коэффициентов Одна из причин этого заключается в том, что подобные коэффициенты тесно связаны с разностным оператором А, определенным в разд. 2.6.

Разность функции в точке х есть

если же применить оператор А еще раз, то получим вторую разность:

которая подобна второй производной. Действуя аналогичным образом, получим

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

В общем случае разность есть

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

следовательно, оператор А есть где 1 — тождественный оператор, определяемый по правилу По биномиальной теореме

Это равенство, элементами которого являются операторы, эквивалентно (5.40), поскольку — это оператор, который переводит .

Интересный и важный случай возникает при рассмотрении отрицательных убывающих степеней. Пусть

Тогда по правилу (2.45) имеем а в общем случае

Итак, равенство (5.40) указывает, что

Например,

Сумма в (5.41) представляет собой разложение на элементарные дроби.

Важные результаты могут быть также получены из рассмотрения положительных убывающих степеней. Если — некоторый многочлен степени то разность — это некоторый многочлен степени следовательно, величина — это константа, и при Этот исключительно важный факт упрощает многие формулы.

Более детальное рассмотрение дает дополнительную информацию. Пусть

— некоторый многочлен степени В гл. 6 мы увидим, что обычные степени могут быть выражены в виде сумм убывающих степеней (скажем, следовательно, существуют коэффициенты такие, что

(Оказывается, что но находящиеся между ними коэффициенты связаны более сложным образом.) Пусть при 0 к Тогда

таким образом, любой многочлен может быть представлен в виде суммы величин, кратных биномиальным коэффициентам. Подобное разложение называется рядом Ньютона для в силу того, что оно широко использовалось Исааком Ньютоном.

Ранее в этой главе мы отмечали, что из формулы сложения вытекает формула

Поэтому разность ряда Ньютона очень просто определяется по индукции:

Если теперь подставить то все члены в правой части обращаются в нуль, за исключением члена с следовательно,

Поэтому рядом Ньютона для является

Например, предположим, что Легко вычислить, что

Таким образом, в этом случае ряд Ньютона имеет вид

Используя (5.40) с можно переписать формулу следующим образом:

к целое

Здесь — произвольная последовательность коэффициентов, однако бесконечная сумма на самом деле является конечной при любом к 0, так что вопрос о сходимости не стоит. В частности, можно получить важное тождество

ибо многочлен всегда может быть записан в виде ряда Ньютона

Многие суммы, которые на первый взгляд кажутся безнадежными, в действительности могут быть просуммированы почти тривиальным образом, если воспользоваться понятием разностей. Например, рассмотрим соотношение

Оно выглядит весьма необычно, поскольку совершенно отлично от всего того, с чем мы встречались до сих пор. Но на самом деле понять его просто, как только мы обратим внимание на проясняющий дело множитель в общем члене, ибо функция

представляет собой многочлен степени относительно к со старшим коэффициентом Таким образом, (5.43) — это не более чем одно из применений соотношения (5.42).

Ряд Ньютона обсуждался в предположении, что — многочлен. Но, как мы видели, бесконечный ряд Ньютона

также имеет смысл, поскольку подобные суммы всегда конечны, если х — целое неотрицательное число. Наш вывод формулы проходит для бесконечной суммы точно так же, как и для конечной, так что общее соотношение таково:

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

Ряд Ньютона является конечно-разностным аналогом ряда Тейлора из исчисления бесконечно малых. Точно так же, как ряд Тейлора может быть записан в виде

так и ряд Ньютона для может быть записан в виде

(Это то же самое, что и (5.44), ибо при любом , если Как ряд Тейлора, так и ряд Ньютона являются конечными, если — многочлен или же кроме того, ряд Ньютона конечен, если х — целое положительное число. В остальных случаях эти суммы могут сходиться или расходиться при определенных значениях х. Если ряд Ньютона сходится, когда х не является целым неотрицательным числом, то он может в действительности сходиться к величине, отличной от потому что ряд Ньютона (5.45) зависит только от дискретных значений функции

Один из примеров сходящегося ряда Ньютона доставляет биномиальная теорема. Пусть где фиксированное комплексное число, такое, что Тогда следовательно, . В данном случае бесконечный ряд Ньютона

сходится к «нужной» величине при любом х.

Джеймс Стирлинг пытался использовать ряд Ньютона для распространения факториальной функции на нецелые числа. Сначала он нашел коэффициенты такие, что

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

Поскольку согласно

Итак, искомые коэффициенты суть На этом

пути Стирлинг получил ряд, который действительно сходится (хотя он и не доказал этого); на самом деле найденный им ряд сходится для всех Тем самым он оказался в состоянии благополучно вычислить Окончание этой истории — в упр. 88.

Прием 3: обращение

Частный случай только что выведенного правила (5.45) для ряда Ньютона может быть переписан следующим образом:

Это соотношение двойственности между называется формулой обращения — она весьма похожа на формулы обращения Мёбиуса (4.56) и (4.61), с которыми мы сталкивались в гл. 4. Формулы обращения позволяют разрешать „неявные рекуррентности" в которых подлежащая определению последовательность упрятана в сумму.

Так, известной могла бы оказаться функция а неизвестной — функция и можно было бы умудриться показать, что Тогда формула (5.48) позволяет выразить в виде суммы известных величин.

Формулу (5.48) можно доказать непосредственно, с помощью основных методов из начала этой главы. Если при любом справедливо то

Доказательство в другую сторону, разумеется, такое же, поскольку связь между симметрична.

Проиллюстрируем формулу (5.48), применив ее к „задаче о победе футбольной команды" Группа из фанатов выигрывающей футбольной команды на радостях бросает свои шляпы в воздух. Шляпы возвращаются в случайном порядке — по одной к каждому из болельщиков. Сколько возможностей того, что ровно к болельщиков получат назад свои собственные шляпы?

Так, если и если шляпы и болельщики обозначены буквами то возможных варианта приземления

шляп дают следующие количества их законных владельцев:

Следовательно,

Определить можно, заметив, что это число способов выбора к счастливых обладателей шляп, а именно (?), помноженное на число способов упорядочения оставшихся шляп так, что ни одна из них не попадает к законному владельцу, а именно на . Перестановка называется беспорядком, если в ней переставлен каждый предмет, а само число беспорядков из предметов иногда обозначается символом произносимым как субфакториал" Таким образом, а общая формула выглядит так:

(Стандартного обозначения для субфакториала не существует, и не ясно, насколько удачно наше; тем не менее, пока попробуем использовать его — там будет видно, понравится ли оно нам. Если нас не устроит, то всегда можно прибегнуть к или чему-нибудь в этом роде.)

Задача оказалась бы решенной, если бы у нас было выражение в замкнутой форме для так что посмотрим, как его можно найти. Поскольку сумма по всем к — это общее число перестановок из шляп, то можно легко получить рекуррентность:

(На последнем шаге к заменяется на , а — на ) С помощью этой неявной рекуррентности можно вычислить все какие пожелаем:

Вот, например, как можно вычислить строку для Два крайних справа элемента очевидны — имеется только один вариант того, что все шляпы попадут к своим владельцам, и ни одного варианта того, что только три болельщика получат назад свои собственные шляпы. (Чью шляпу поймал бы тогда четвертый болельщик?) Если то можно воспользоваться нашим уравнением для и получить

Этим уравнением нельзя воспользоваться для вычисления вернее, можно, но тогда получим что правильно, но бесполезно. Перестроившись, можно воспользоваться соотношением с выяснением того, что — это и есть значение Аналогичным образом зависит от других значений при

Но как разрешить рекуррентность типа (5.49)? Ну, это просто: она имеет вид (5.48) с Следовательно, ее решением является

Однако это, на самом деле, еще не решение, а сумма, которую следует выразить в замкнутой форме, если это возможно. Тем не менее, это все же лучше, чем рекуррентность. Данную сумму можно упростить, поскольку сокращается с спрятанным в , так что попробуем это сделать:

Оставшаяся часть суммы быстро сходится к числу Действительно, остальные члены в сумме дают

где заключенная в скобки величина лежит между

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

Это число вариантов того, что ни один из болельщиков не получит назад свою собственную шляпу. При большом более существенно знать вероятность, с которой это происходит. Если предположить, что каждый из исходов равновероятен — ибо все шляпы взлетели очень высоко, — то данная вероятность равна

Так что когда число становится большим, вероятность того, что все шляпы будут перепутаны, составляет почти 37%.

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

Прежде чем покончить с этой задачей, рассмотрим вкратце две интересные закономерности, которые так и смотрят на нас из таблицы начальных значений . Во-первых, судя по всему, числа расположенные под диагональю из нулей, являются треугольными числами. Это наблюдение легко проверяется, поскольку данные элементы таблицы суть числа а

Кроме того, похоже, что числа в первых двух колонках отличаются друг от друга на ±1. Всегда ли это справедливо? Да, поскольку

Другими словами, Это гораздо более простая рекуррентность для числа беспорядков, чем та, с которой мы имели дело раньше.

Теперь применим инверсию к чему-нибудь еще. Если применить инверсию к формуле

которая была выведена нами в (5.41), то выяснится, что

Это интересно, но в действительности не ново: если обратить верхний индекс в , то мы просто-напросто снова получим тождество (5.33).