Числа Эйлера

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

Это следует из того, что каждая перестановка ... , содержит n-1-k отрезков подъема тогда и только тогда, когда ее «отражение» ... содержит k таких участков.

2. Числа Эйлера первого порядка: рекуррентные формулы, дополнительные тождества

Рассмотрим перестановку {1,2,…,n-1}, из любой такой перестановки можно образовать n новых перестановок, вставляя элемент n во всевозможные места. Если в исходной перестановке содержалось k отрезков подъема (далее просто отрезков), то ровно k новых перестановок будут иметь k отрезков; в остальных n-k перестановках будет по k+1отрезков, поскольку всякий раз, когда n вставляется не в конец уже существующего отрезка, число отрезков увеличивается на единицу.

Например, среди шести перестановок, полученных из перестановки 3 1 2 4 5,

Все, кроме второй и последней перестановок, содержат по три отрезка вместо исходных двух. Отсюда, имеем рекуррентное соотношение

Положим, что

то есть будем считать, что в пустой перестановке содержится один отрезок. И так же будем считать, что =0 при k<0.

Эйлерова рекуррентность несколько сложнее рекуррентностей Стирлинга:

Поэтому числа удоволетворяют значительно меньшему числу простых тождеств. В качестве примера рассмотрим следующие:

(1)

(2)

(3)

Если умножить (2) на и просуммировать по m, то получим:

А замена z на z-1 и приравнивание коэффициентов при дает тождество (3). Таким образом, два последних тождества, в сущности, эквивалентны. Первое тождество доставляется отдельные значения при малом m:

3. Связь натуральных степеней и последовательных биномиальных коэффициентов

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

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

, где i1 i2 …in - однозначно определенная перестановка множества {1,2,…,n}, такая что ij<ij+1, если другими словами, из ij>ij+1следует

Покажем, что если в перестановке i1 i2 …in содержится k отрезков, то число соответствующих ей последовательностей равно , тем самым будет доказана нужная нам формула, если заменить k на n+1-k.

Пусть, например, n=9, i1 i2 …in = 3 5 7 1 6 8 9 4 2 и требуется подсчитать число последовательностей , таких, что:

Оно будет равно числу последовательностей , таких что:

+5,

Так как можно положить:

Число способов, которыми можно выбрать элементы a, равно просто-напросто числу способов выбрать 9 предметов из m+5, т.е. . Аналогичное доказательство годится для произвольных n и k и любой перестановки i1 i2 … in c k отрезками.

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

Например,

Кроме того, описанное выше тождество дает еще один способ вычисления суммы первых n квадратов: имеем ; следовательно

=

=+

Докажем еще одно следствие. Положив х=1 в тождестве, покажем, что

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

Далее подставляя х=3,4,…., убедимся, что все числа полностью определяются приведенным выше тождеством, и придем к формуле, впервые найденной Эйлером:

=

Для доказательства формулы достаточно показать, что, подставив это значение в исходное тождество, мы получим верное равенство при x=k, если . Формулу можно преобразовать в

=

При s<k суммирование по j можно распространить на промежуток , а эта сумма будет равна нулю.((n+1)-ая разность полинома n-й степени от j).

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

1. Для заданного натурального числа существует единственная перестановка без подъёмов, то есть (n, n-1,n-2,….1).

2. Также существует единственная перестановка, которая имеет n-1 подъёмов, то есть . Таким образом, для всех натуральных n

3. Зеркальным отражением перестановки с m подъёмами является перестановка с n-m-1 подъёмами. Таким образом,

Числа Эйлера I рода обладают также геометрической и вероятностной интерпретацией -- число выражает:

· объём части n-мерного гиперкуба, ограниченного гиперплоскостями и ;

· вероятность того, что сумма n независимых равномерно распределённых в отрезке переменных лежит между k-1 и k.

Далее приведем некоторые полезные формулы суммирования:

Формулы суммирования

Из комбинаторного определения, очевидно, что сумма чисел Эйлера I рода, расположенных в n-й строке равна , так как она равна количеству всех перестановок порядка :

Знакопеременные суммы чисел Эйлера I рода при фиксированном значении n связаны с числами Бернулли :

Также справедливы следующие тождества, связывающие числа Эйлера I рода с числами Стирлинга II рода:

4. Числа Эйлера второго рода: треугольник Эйлера

Обозначим через <<n,k>> число Эйлера второго порядка. Причем верна следующая рекуррентная формула:

<<n,k>> = (k+1)<<n-1,k>> + (2n-1-k)<<n-1,k-1>>

Эти числа допускают любопытную комбинаторную интерпретацию, впервые помеченную Гесселем и Стенли. Если образовать перестановки мультимножества {1,1,2,2,….,n,n} с тем особым свойством, что все числа между двумя встречающимися m больше этого m при , то <<n,k>> является числом таких перестановок, которые содержат k участков подъема. К примеру, имея восемь соответствующих «одноподъемных» перестановок множества {1,1,2,2,3,3}:

Таким образом, <<3,1>>=8. А всего имеется

число эйлер треугольник формула

соответствующих подстановок мультимножества {1,1,2,2,…,n,n}, поскольку оба появляющихся n должны быть смежными и имеется 2n-1 мест их вставки в перестановку мультимножества {1,1,2,2,….,n-1,n-1}. К примеру, при n=3 перестановка 1221 имеет пять мест для вставки, что дает 331221, 133221,123321, 122331, 122133. Рекуррентность доказывается по аналогии с числами Эйлера первого рода.

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

=

=

Например,

==

=+,=+

=++, =++

Эти тождества справедливы тогда, когда x- целое и n-неотрицательное целое число. Поскольку правые части этих тождеств являются многочленами относительно х, то тождества в общем виде можно использовать для определения чисел Стирлинга , при произвольных вещественных или комплексных х. На Таблице №2 представлен треугольник, составленный из чисел Эйлера второго рода.

Tаблица №2. Треугольник Эйлера( второго рода)