6.2 ЧИСЛА ЭЙЛЕРА

Время от времени возникает еще один треугольник чисел, которым мы обязаны Эйлеру [368, § 13; 374, с. 485] и элементы которого мы обозначаем через . В данном случае угловые скобки напоминают знаки «меньше» и «больше»: — это число перестановок множества имеющих к участков подъема, а именно, к мест, где (Предупреждаем: это обозначение еще менее употребительно, чем наши обозначения для чисел Стирлинга. Однако мы увидим, что в этом обозначении есть свой резон.)

Таблица 298 Треугольник Эйлера.

К примеру, одиннадцать перестановок множества содержат по два участка подъема:

(В первой строке перечислены перестановки с во второй строке перечислены перестановки с Следовательно, . В табл. 298 приведены начальные числа Эйлера — обратите внимание, что на этот раз „фирменным знаком" данной последовательности служит 1, 11, 11, 1. При может быть самое большее участков подъема, так что мы имеем на диагонали этого треугольника.

Треугольник Эйлера, подобно треугольнику Паскаля, симметричен слева-направо. Однако на этот раз правило симметрии несколько иное:

Перестановка П] содержит к участков подъема тогда и только тогда, когда ее „отражение" содержит к таких участков.

Попробуем найти рекуррентность для Каждая перестановка множества приводит к перестановкам множества если вставлять новый элемент во все возможные места. Предположим, что мы вставляем на место, получая Если или если то число участков подъема в такое же, как и число участков подъема в ; если же или же то оно на единицу больше того же числа в . Поэтому в целом перестановка с к участками подъема получается способами из перестановок , которые содержат к участков подъема, плюс

способами из перестановок , которые содержат участков подъема. Итак, искомая рекуррентность:

А для „запуска" данной рекуррентности полагаем

и считаем, что при

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

(Это „тождество Ворпицкого" [57].) Так,

и т.д. Тождество (6.37) легко доказать по индукции (упр. 14).

Между прочим, тождество (6.37) дает еще один способ вычисления суммы первых квадратов: имеем следовательно,

Эйлерова рекуррентность (6.35) несколько сложнее рекуррентностей Стирлинга (6.3) и (6.8), так что не следует рассчитывать, что числа будут удовлетворять такому же количеству простых тождеств. Хотя кое-что есть:

Таблица 300 Треугольник чисел Эйлера второго порядка.

Если умножить (6.39) на и просуммировать по то получим . А замена z на и приравнивание коэффициентов при дает (6.40). Таким образом, два последних тождества, в сущности, эквивалентны. Первое тождество (6.38) доставляет отдельные значения при малом

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

Эти числа допускают любопытную комбинаторную интерпретацию, впервые подмеченную Гесселем и Стенли [72]: если образовать перестановки мультимножества с тем особым свойством, что все числа между двумя встречающимися больше этого при то является числом таких перестановок, которые содержат к участков подъема. К примеру, имеется восемь соответствующих „одноподъемных" перестановок множества

Таким образом, . А всего имеется

соответствующих перестановок мультимножества поскольку оба появляющихся должны быть смежными и имеется мест их вставки в перестановку мультимножества . К примеру, при перестановка 1221 имеет пять мест для вставки, что дает 331221, 133221, 123321, 122331 и 122133. Рекуррентность (6.41) может быть доказана путем перенесения на нее той аргументации, которая использовалась для обычных чисел Эйлера.

Числа Эйлера второго порядка важны, главным образом, в силу своей связи с числами Стирлинга [74]: индукцией по получаем, что

Например,

(Случай уже встречался в Эти тождества справедливы тогда, когда х — целое и — неотрицательное целое число. Поскольку правые части этих тождеств являются многочленами относительно х, тождества (6.43) и (6.44) можно использовать для определения чисел Стирлинга при произвольных вещественных (или комплексных) х.

Если соответствующие многочлены равны нулю при следовательно, они делятся на Интересно взглянуть на то, что остается после деления на эти множители. Определим многочлены Стирлинга по правилу

Таблица 302 Формулы сверток Стирлинга.

(Многочлен имеет степень Несколько первых случаев таковы:

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

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

И, вообще, если степенной ряд удовлетворяет тождеству

то

Поэтому мы можем вывести общие формулы сверток для чисел Стирлинга, как мы это сделали для биномиальных коэффициентов в табл. 229, - результаты сведены в табл. 302. Если сумма чисел Стирлинга не соответствует тождествам из табл. 294 или 295, то табл. 302 может оказаться как раз тем, что нужно. (Такой пример приводится в этой главе — вслед за уравнением . А в упр. 7.19 обсуждаются общие принципы сверток, основанных на тождествах типа (6.50) и (6.53).)