В комбинаторике числом Эйлера I рода из n по k, обозначаемым
или
, называется количество перестановок порядка n с k подъёмами, то есть таких перестановок
, что существует ровно k индексов j, для которых
.
Числа Эйлера I рода обладают также геометрической и вероятностной интерпретацией — число
выражает:
Пример
Перестановки
четвертого порядка, имеющие ровно два подъёма, должны удовлетворять одному из трёх неравенств:
,
или
. Таких перестановок ровно 11:
- 1324, 1423, 2314, 2413, 3412, 1243, 1342, 2341, 2134, 3124, 4123.
Поэтому
.
Свойства
Для заданного натурального числа
существует единственная перестановка без подъёмов, то есть
. Также существует единственная перестановка, которая имеет n-1 подъёмов, то есть
. Таким образом,
для всех натуральных
.
Зеркальным отражением перестановки с m подъёмами является перестановка с n-m-1 подъёмами. Таким образом,

Треугольник чисел Эйлера первого рода
Значение чисел Эйлера
для малых значений n и k приведены в следующей таблице (последовательность A008292 в OEIS):
n\k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 1 |
1 | 1 | 0 |
2 | 1 | 1 | 0 |
3 | 1 | 4 | 1 | 0 |
4 | 1 | 11 | 11 | 1 | 0 |
5 | 1 | 26 | 66 | 26 | 1 | 0 |
6 | 1 | 57 | 302 | 302 | 57 | 1 | 0 |
7 | 1 | 120 | 1191 | 2416 | 1191 | 120 | 1 | 0 |
8 | 1 | 247 | 4293 | 15619 | 15619 | 4293 | 247 | 1 | 0 |
9 | 1 | 502 | 14608 | 88234 | 156190 | 88234 | 14608 | 502 | 1 | 0 |
Легко понять, что значения на главной диагонали матрицы задаются формулой: ![{\displaystyle \left\langle {n \atop n}\right\rangle =[n=0].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dca3ca898f95aff292f140b9bb338c0d650e8235)
Треугольник Эйлера, как и треугольник Паскаля, симметричен слева и справа. Но в этом случае закон симметрии несколько отличен:
при n > 0.
То есть перестановка имеет n-1-k подъёмов тогда и только тогда, когда её «отражение» имеет k подъёмов.
Рекуррентная формула
Каждая перестановка
из набора
приводит к
перестановкам из
, если мы вставляем новый элемент n всеми возможными способами. Вставляя
в
-ю позицию, получаем перестановку
. Количество подъёмов в
равняется количеству подъёмов в
, если
или если
; и оно больше количества подъёмов в
, если
или если
. Следовательно,
в сумме имеет
способов построения перестановок из
, которые имеют
подъёмов, плюс
способов построения перестановок из
, которые имеют
подъёмов. Тогда искомая рекуррентная формула для целых
имеет вид:

Положим также, что
(для целых
),
и при
:

Явные формулы
Явная формула для чисел Эйлера I рода:

позволяет получить относительно простые выражения при малых значениях m:



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

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



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



Производящая функция
Производящая функция чисел Эйлера I рода имеет вид:

Числа Эйлера I рода связаны также с производящей функцией последовательности
-х степеней (полилогарифм целого отрицательного порядка):

Кроме того, Z-преобразование из

является генератором первых N строк треугольник чисел Эйлера, когда знаменатель
-й элемента преобразования сокращается умножением на
:
![{\displaystyle Z\left[\{n^{k}\}_{k=1}^{3}=\left\{{\frac {z}{(z-1)^{2}}},{\frac {z+z^{2}}{(z-1)^{3}}},{\frac {z+4z^{2}+z^{3}}{(z-1)^{4}}}\right\}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f518370f0d85e8e87cc190394bc7dc211a0b2bc1)
Тождество Ворпицкого
Тождество Ворпицкого выражает степенную функцию в виде суммы произведений чисел Эйлера I рода и обобщённых биномиальных коэффициентов:

В частности:



и т. д. Эти тождества легко доказываются по индукции.
Тождество Ворпицкого даёт ещё один способ вычисления суммы первых
квадратов:



Литература