- Числа Эйлера I рода
-
В комбинаторике числом Эйлера 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 приведены в следующей таблице (последовательность 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 рода и обобщённых биномиальных коэффициентов:
В частности:
и т. д. Эти тождества легко доказываются по индукции.
Тождество Ворпицкого даёт ещё один способ вычисления суммы первых
квадратов:
Литература
- Дональд Кнут, Роналд Грэхем, Орен Паташник Числа Эйлера // Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7
- Д. Кнут Основные алгоритмы // Искусство программирования. — М.: Вильямс , 2006. — Т. 1.
- Weisstein, Eric W. Eulerian Number (англ.) на сайте Wolfram MathWorld.
- Weisstein, Eric W. Worpitzky’s Identity (англ.) на сайте Wolfram MathWorld.
- Eulerian Numbers. MathPages.
Категория:- Комбинаторика
- объём части n-мерного гиперкуба, ограниченного гиперплоскостями
Wikimedia Foundation. 2010.