Открыть главное меню

В комбинаторике числом Эйлера 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

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

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

  при n > 0.

То есть перестановка имеет n-1-k подъёмов тогда и только тогда, когда её «отражение» имеет k подъёмов.

Рекуррентная формулаПравить

Каждая перестановка   из набора   приводит к   перестановкам из  , если мы вставляем новый элемент n всеми возможными способами. Вставляя   в  -ю позицию, получаем перестановку  . Количество подъёмов в   равняется количеству подъёмов в  , если   или если  ; и оно больше количества подъёмов в  , если   или если  . Следовательно,   в сумме имеет   способов построения перестановок из  , которые имеют   подъёмов, плюс   способов построения перестановок из  , которые имеют   подъёмов. Тогда искомая рекуррентная формула для целых   имеет вид:

 

Положим также, что

  (для целых  ),

и при  :

 

Явные формулыПравить

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

 

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

 
 
 

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

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

 

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

 
 
 

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

 
 
 

Производящая функцияПравить

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

 

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

 

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

 

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

 

Тождество ВорпицкогоПравить

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

 

В частности:

 
 
 

и т. д. Эти тождества легко доказываются по индукции.

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

 
 
 

ЛитератураПравить