Полиномиальная последовательность
В комбинаторике число Эйлера A (n, m) - количество перестановок чисел от 1 до n, в которых ровно m элементов больше, чем предыдущий элемент (перестановки с m «восходящими»). Они являются коэффициентами полиномов Эйлера :
Многочлены Эйлера определяются экспоненциальной производящей функцией
Многочлены Эйлера могут быть вычислены с помощью повторения
Эквивалентный способ записать это определение - задать полиномы Эйлера индуктивно с помощью
Другие обозначения для A (n, m): E (n, m) и .
Содержание
- 1 История
- 2 Основные свойства
- 3 Явная формула
- 4 Свойства суммирования
- 5 Тождества
- 6 Эйлеров n элементы второго типа
- 7 Ссылки
- 8 Цитаты
- 9 Внешние ссылки
История
Показывает многочлены, известные в настоящее время как многочлены Эйлера в работе Эйлера 1755 года, Institutiones Calculi Differenceis, часть 2, стр.. 485/6. Коэффициенты этих многочленов известны как числа Эйлера.
В 1755 году Леонард Эйлер исследовал в своей книге Institutiones Calculi Differentialis полиномы α 1 (x) = 1, α 2 (x) = x + 1, α 3 (x) = x + 4x + 1 и т. Д. (См. Факсимильное сообщение). Эти многочлены представляют собой сдвинутую форму того, что сейчас называется многочленами Эйлера A n (x).
Основные свойства
Для заданного значения n>0 индекс m в A (n, m) может принимать значения от 0 до n - 1. Для фиксированного n существует единственный перестановка, которая имеет 0 восхождений: (n, n - 1, n - 2,..., 1). Также существует единственная перестановка, которая имеет n - 1 восхождение; это восходящая перестановка (1, 2, 3,..., n). Следовательно, A (n, 0) и A (n, n - 1) равны 1 для всех значений n.
Обращение перестановки с m восхождениями создает другую перестановку, в которой есть n - m - 1 подъемов. Следовательно, A (n, m) = A (n, n - m - 1).
Значения A (n, m) могут быть вычислены «вручную» для малых значений n и m. Например,
n | m | Перестановки | A (n, m) |
---|
1 | 0 | (1) | A (1,0) = 1 |
2 | 0 | (2, 1) | A (2,0) = 1 |
1 | (1, 2) | A (2,1) = 1 |
3 | 0 | (3, 2, 1) | A (3,0) = 1 |
1 | (1, 3, 2) (2, 1, 3 ) (2, 3, 1) (3, 1, 2) | A (3,1) = 4 |
2 | (1, 2, 3) | A (3,2) = 1 |
Для больших значений n, A (n, m) может быть вычислено с использованием рекурсивного формула
Например,
Значения A (n, m) (последовательность A008292 в OEIS ) для 0 ≤ n ≤ 9:
mn | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|
1 | 1 | | | | | | | | |
---|
2 | 1 | 1 | | | | | | | |
---|
3 | 1 | 4 | 1 | | | | | | |
---|
4 | 1 | 11 | 11 | 1 | | | | | |
---|
5 | 1 | 26 | 66 | 26 | 1 | | | | |
---|
6 | 1 | 57 | 302 | 302 | 57 | 1 | | | |
---|
7 | 1 | 120 | 1191 | 2416 | 1191 | 120 | 1 | | |
---|
8 | 1 | 247 | 4293 | 15619 | 15619 | 4293 | 247 | 1 | |
---|
9 | 1 | 502 | 14608 | 88234 | 156190 | 88234 | 14608 | 502 | 1 |
---|
Вышеупомянутый треугольный массив называется треугольником Эйлера или треугольником Эйлера, и он имеет некоторые общие характеристики с Треугольник Паскаля. Сумма строки n - это факториал n !.
Явная формула
Явная формула для A (n, m):
(L. Comtet 1974, стр. 243) Из этой формулы, а также из комбинаторной интерпретации видно, что для , так что - полином степени для .
Свойства суммирования
Из комбинаторного определения ясно, что сумма чисел Эйлера для фиксированного значения n - это общее количество перестановок чисел от 1 до n, поэтому
The переменная сумма чисел Эйлера для фиксированного значения n связана с числом Бернулли B n + 1
Другие свойства суммирования чисел Эйлера:
где B n - n-е число Бернулли.
Тождества
Числа Эйлера участвуют в производящей функции для последовательности из n степеней:
для . Это предполагает, что 0 = 0 и A (0,0) = 1 (так как есть одна перестановка без элементов, и она не имеет восходов).
Тождество Ворпицки выражает x как линейную комбинацию чисел Эйлера с биномиальными коэффициентами :
Это следует из формулы Ворпицки тождество, что
Еще одно интересное тождество:
Числитель в правой части - многочлен Эйлера.
Для фиксированной функции , которая интегрируется на имеем интегральную формулу
Числа Эйлера второго рода
Перестановки мультимножества {1, 1, 2, 2,..., n, n}, которые обладают тем свойством, что для каждого k все числа, встречающиеся между двумя вхождения k в перестановке больше, чем k, подсчитываются с помощью двойного факториала числа (2n-1) !!. Число Эйлера второго рода, обозначаемое , подсчитывает количество всех таких перестановок, имеющих ровно m подъемов. Например, для n = 3 таких перестановок 15, 1 без восхождений, 8 с одним восхождением и 6 с двумя восхождениями:
- 332211,
- 221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,
- 112233, 122133, 112332, 123321, 133122, 122331.
Числа Эйлера второго рода удовлетворяют рекуррентному соотношению, которое непосредственно следует из приведенного выше определения:
с начальным условием для n = 0, выраженным в обозначении скобок Айверсона :
Соответственно, многочлен Эйлера второй вид, здесь обозначенный P n (для них не существует стандартной записи), равны
и указанные выше рекуррентные соотношения переводятся в рекуррентное соотношение для последовательности P n (x):
с начальным условием
Последнее повторение может можно записать в более компактной форме с помощью интегрирующего множителя:
так что что рациональная функция
удовлетворяет простому автономному повторению:
откуда можно получить многочлены Эйлера как P n (x) = (1 − x) u n (x), а числа Эйлера второго рода в качестве их коэффициентов.
Вот некоторые значения чисел Эйлера второго порядка (последовательность A008517 в OEIS ):
mn | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|
1 | 1 | | | | | | | | |
---|
2 | 1 | 2 | | | | | | | |
---|
3 | 1 | 8 | 6 | | | | | | |
---|
4 | 1 | 22 | 58 | 24 | | | | | |
---|
5 | 1 | 52 | 328 | 444 | 120 | | | | |
---|
6 | 1 | 114 | 1452 | 4400 | 3708 | 720 | | | |
---|
7 | 1 | 240 | 5610 | 32120 | 58140 | 33984 | 5040 | | |
---|
8 | 1 | 494 | 19950 | 195800 | 644020 | 785304 | 341136 | 40320 | |
---|
9 | 1 | 1004 | 67260 | 1062500 | 5765500 | 12440064 | 11026296 | 3733920 | 362880 |
---|
Сумма n-й строки, которая также является значением P n ( 1), равно (2n - 1) !!.
Ссылки
- Эйлер, Леонард [Леонард Эйлер] (1755). Учреждения дифференциального исчисления с приложениями к конечному анализу и рядам [Основы дифференциального исчисления с приложениями к конечному анализу и рядам]. Academia imperialis scientiarum Petropolitana; Беролини: Officina Michaelis.
- Карлитц, Л. (1959). «Числа Эйлера и многочлены». Математика. Mag. 32 (5): 247–260. doi : 10.2307 / 3029225. JSTOR 3029225.
- Гулд, Х. У. (1978). «Оценка сумм свернутых степеней с использованием чисел Стирлинга и Эйлера». Фиб. Кварта. 16 (6): 488–497.
- Desarmenien, Jacques; Фоата, Доминик (1992). «Знаковые числа Эйлера». Дискретная математика. 99 (1–3): 49–58. doi : 10.1016 / 0012-365X (92) 90364-L.
- Lesieur, Leonce; Николя, Жан-Луи (1992). «О числах Эйлера M = max (A (n, k))». Europ. J. Combinat. 13 (5): 379–399. doi : 10.1016 / S0195-6698 (05) 80018-6.
- Butzer, P.L.; Хаус, М. (1993). «Числа Эйлера с дробными параметрами порядка». Aequationes Mathematicae. 46(1–2): 119–142. doi : 10.1007 / bf01834003. S2CID 121868847.
- Котрас, М.В. (1994). «Числа Эйлера, ассоциированные с последовательностями многочленов». Фиб. Кварта. 32 (1): 44.
- Грэм; Кнут; Паташник (1994). Конкретная математика : Фонд компьютерных наук (2-е изд.). Эддисон-Уэсли. стр. 267–272.
- Hsu, Leetsch C. ; Джау-Шионг Шиуэ, Питер (1999). «О некоторых задачах суммирования и обобщениях многочленов и чисел Эйлера». Дискретная математика. 204 (1–3): 237–247. doi : 10.1016 / S0012-365X (98) 00379-3.
- Бояджиев, Христо Н. (2007). «Функции Апостола-Бернулли, производные многочлены и многочлены Эйлера». arXiv : 0710.1124 [math.CA ].
- Петерсен, Т. Кайл (2015). «Числа Эйлера». Birkhäuser Advanced Texts Basler Lehrbücher. Birkhäuser. С. 3–18. DOI : 10.1007 / 978-1-4939-3091-3_1. ISBN 978-1-4939-3090-6. Отсутствует или пусто
| title =
()
Цитаты
- ^Worpitzky, J. (1883). «Studien über die Bernoullischen und Eulerschen Zahlen». Journal für die reine und angewandte Mathematik. 94 : 203–232.
- ^Упражнение 6,65 дюйма Конкретная математика Грэма, Кнута и Паташника.
Внешние ссылки