В комбинаторике числом Эйлера I рода из n по k, обозначаемым или , называется количество перестановок порядка n с k подъёмами, то есть таких перестановок , что существует ровно k индексов j, для которых .
Числа Эйлера I рода обладают также геометрической и вероятностной интерпретацией — число выражает: объём части n-мерного гиперкуба, ограниченного гиперплоскостями и ; вероятность того, что сумма n независимых равномерно распределённых в отрезке переменных лежит между k-1 и k.
Пример
Перестановки четвертого порядка, имеющие ровно два подъёма, должны удовлетворять одному из трёх неравенств: , или . Таких перестановок ровно 11: 1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123. Поэтому .
Свойства
Для заданного натурального числа существует единственная перестановка без подъёмов, то есть . Также существует единственная перестановка, которая имеет n-1 подъёмов, то есть . Таким образом, для всех натуральных .
Зеркальным отражением перестановки с m подъёмами является перестановка с n-m-1 подъёмами. Таким образом,
Треугольник чисел Эйлера первого рода
Значение чисел Эйлера для малых значений n и k приведены в следующей таблице ():
n\k 0 1 2 3 4 5 6 7 8 90 11 1 02 1 1 03 1 4 1 04 1 11 11 1 05 1 26 66 26 1 06 1 57 302 302 57 1 07 1 120 1191 2416 1191 120 1 08 1 247 4293 15619 15619 4293 247 1 09 1 502 14608 88234 156190 88234 14608 502 1 0
Легко понять, что значения на главной диагонали матрицы задаются формулой:
Треугольник Эйлера, как и треугольник Паскаля, симметричен слева и справа. Но в этом случае закон симметрии несколько отличен: при n > 0. То есть перестановка имеет n-1-k подъёмов тогда и только тогда, когда её «отражение» имеет k подъёмов.
Рекуррентная формула
Каждая перестановка из набора приводит к перестановкам из , если мы вставляем новый элемент n всеми возможными способами. Вставляя в -ю позицию, получаем перестановку . Количество подъёмов в равняется количеству подъёмов в , если или если ; и оно больше количества подъёмов в , если или если . Следовательно, в сумме имеет
способов построения перестановок из , которые имеют подъёмов, плюс
способов построения перестановок из , которые имеют подъёмов. Тогда искомая рекуррентная формула для целых имеет вид:
Положим также, что (для целых ), и при :
Явные формулы
Явная формула для чисел Эйлера I рода:
позволяет получить относительно простые выражения при малых значениях m:
Формулы суммирования
Из комбинаторного определения очевидно, что сумма чисел Эйлера I рода, расположенных в n-й строке, равна , так как она равна количеству всех перестановок порядка :
Знакопеременные суммы чисел Эйлера I рода при фиксированном значении n связаны с числами Бернулли :
Также справедливы следующие тождества, связывающие числа Эйлера I рода с числами Стирлинга II рода:
Производящая функция
Производящая функция чисел Эйлера I рода имеет вид:
Числа Эйлера I рода связаны также с производящей функцией последовательности -х степеней (полилогарифм целого отрицательного порядка):
Кроме того, Z-преобразование из
является генератором первых N строк треугольник чисел Эйлера, когда знаменатель -й элемента преобразования сокращается умножением на :
Тождество Ворпицкого
Тождество Ворпицкого выражает степенную функцию в виде суммы произведений чисел Эйлера I рода и обобщённых биномиальных коэффициентов:
В частности:
и т. д. Эти тождества легко доказываются по индукции.
Тождество Ворпицкого даёт ещё один способ вычисления суммы первых квадратов:
Литература
Eulerian Numbers. MathPages.
Категория:Комбинаторика Категория:Объекты, названные в честь Леонарда Эйлера Категория:Целочисленные последовательности