Число Эйлера

В комбинаторике число Эйлера A ( n , m ) - это количество перестановок чисел от 1 до n, в которых ровно m элементов больше предыдущего (перестановки с m «подъемами»). Они являются коэффициентами многочленов Эйлера :

${\ Displaystyle A_ {n} (t) = \ sum _ {m = 0} ^ {n} A (n, m) \ t ^ {m}.}$

Многочлены Эйлера определяются экспоненциальной производящей функцией

${\ displaystyle \ sum _ {n = 0} ^ {\ infty} A_ {n} (t) \ cdot {\ frac {x ^ {n}} {n!}} = {\ frac {t-1} { t- \ mathrm {e} ^ {(t-1) x}}}.}$

Многочлены Эйлера могут быть вычислены с помощью рекуррентности

${\ displaystyle A_ {0} (t) = 1,}$

${\ Displaystyle A_ {n} (t) = t (1-t) \ cdot A_ {n-1} '(t) + A_ {n-1} (t) \ cdot (1+ (n-1) t ), \ quad n \ geq 1.}$

Эквивалентный способ записать это определение - задать полиномы Эйлера индуктивно следующим образом:

${\ displaystyle A_ {0} (t) = 1,}$

${\ Displaystyle A_ {n} (t) = \ sum _ {k = 0} ^ {n-1} {\ binom {n} {k}} A_ {k} (t) \ cdot (t-1) ^ {n-1-k}, \ quad n \ geq 1.}$

Другие обозначения для A ( n , m ) - E ( n , m ) и .${\ Displaystyle \ scriptstyle \ left \ langle {п \ на вершине m} \ right \ rangle}$

История [ править ]

Показывает многочлены, известные в настоящее время как многочлены Эйлера в работе Эйлера 1755 года, Institutiones Calculi Differenceis, часть 2, стр. 485/6. Коэффициенты этих многочленов известны как числа Эйлера.

В 1755 году Леонард Эйлер исследовал в своей книге Institutiones Calci Differentialis полиномы α ₁ ( x ) = 1 , α ₂ ( x ) =  x  + 1 , α ₃ ( x ) =  x ²  + 4 x  + 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 . Например

п	м	Перестановки	А ( п , м )
1	0	(1)	А (1,0) = 1
2	0	(2, 1)	А (2,0) = 1
	1	(1, 2 )	А (2,1) = 1
3	0	(3, 2, 1)	А (3,0) = 1
	1	(1, 3 , 2) (2, 1, 3 ) (2, 3 , 1) (3, 1, 2 )	А (3,1) = 4
	2	(1, 2 , 3 )	А (3,2) = 1

Для больших значений п , ( п , т ) может быть вычислена с помощью рекурсивной формулы

${\ Displaystyle A (n, m) = (нм) A (n-1, m-1) + (m + 1) A (n-1, m).}$

Например

${\ Displaystyle A (4,1) = (4-1) A (3,0) + (1 + 1) A (3,1) = 3 \ раз 1 + 2 \ раз 4 = 11.}$

Значения A ( n , m ) (последовательность A008292 в OEIS ) для 0 ≤ n ≤ 9:

м п	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 ): ^[1]

${\displaystyle A(n,m)=\sum _{k=0}^{m+1}(-1)^{k}{\binom {n+1}{k}}(m+1-k)^{n}.}$

Как видно из этой формулы, а также от комбинаторной интерпретации, что для , так что есть многочлен от степени для .${\displaystyle A(n,n)=0}$${\displaystyle n>0}$${\displaystyle A_{n}(t)}$ ${\displaystyle n-1}$${\displaystyle n>0}$

Свойства суммирования [ править ]

Из комбинаторного определения ясно, что сумма чисел Эйлера для фиксированного значения n - это общее количество перестановок чисел от 1 до n , поэтому

${\displaystyle \sum _{m=0}^{n-1}A(n,m)=n!{\text{ for }}n\geq 1.}$

Альтернированная сумма из эйлеровых чисел при фиксированном значении п связано с числом Бернулли B _{п +1}

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}A(n,m)={\frac {2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}}{\text{ for }}n\geq 1.}$

Другие свойства суммирования чисел Эйлера:

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n-1}{m}}}=0{\text{ for }}n\geq 2,}$

${\displaystyle \sum _{m=0}^{n-1}(-1)^{m}{\frac {A(n,m)}{\binom {n}{m}}}=(n+1)B_{n}{\text{ for }}n\geq 2,}$

где B _n - n- ^е число Бернулли.

Личности [ править ]

Числа Эйлера входят в производящую функцию для последовательности n- ^х степеней:

${\displaystyle \sum _{k=0}^{\infty }k^{n}x^{k}={\frac {\sum _{m=0}^{n-1}A(n,m)x^{m+1}}{(1-x)^{n+1}}}={\frac {x\cdot A_{n}(x)}{(1-x)^{n+1}}}}$

для . Это предполагает, что 0 ⁰ = 0 и A (0,0) = 1 (так как есть одна перестановка без элементов, и у нее нет подъемов).${\displaystyle n\geq 0}$

Тождество Ворпицки ^[2] выражает x ⁿ как линейную комбинацию чисел Эйлера с биномиальными коэффициентами :

${\displaystyle x^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {x+m}{n}}.}$

Из тождества Ворпицкого следует, что

${\displaystyle \sum _{k=1}^{N}k^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {N+1+m}{n+1}}.}$

Еще одна интересная идентичность

${\displaystyle {\frac {e}{1-ex}}=\sum _{n=0}^{\infty }{\frac {A_{n}(x)}{n!(1-x)^{n+1}}}.}$

В числителе в правой части стоит полином Эйлера.

Для фиксированной функции, интегрируемой на, имеем интегральную формулу ^[3]${\displaystyle f:\mathbb {R} \rightarrow \mathbb {C} }$${\displaystyle (0,n)}$

${\displaystyle \int _{0}^{1}\cdots \int _{0}^{1}f\left(\left\lfloor x_{1}+\cdots +x_{n}\right\rfloor \right)dx_{1}\cdots dx_{n}=\sum _{k}A(n,k){\frac {f(k)}{n!}}.}$

Числа Эйлера второго рода [ править ]

Перестановки в мультимножестве {1, 1, 2, 2, ···, п , п } , которые обладают свойством , что для каждого к , все числа , возникающие между двумя вхождений к в перестановке больше , чем к подсчитываются на двойное факториальное число (2 n −1) !!. Обозначенное число Эйлера второго рода подсчитывает количество всех таких перестановок, имеющих ровно m подъемов. Например, для n = 3 таких перестановок 15, 1 без восхождений, 8 с одним восхождением и 6 с двумя подъемами:${\displaystyle \scriptstyle \left\langle \!\left\langle {n \atop m}\right\rangle \!\right\rangle }$

332211, г.

221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,

112233, 122133, 112332, 123321, 133122, 122331.

Числа Эйлера второго рода удовлетворяют рекуррентному соотношению, которое непосредственно следует из приведенного выше определения:

${\displaystyle \left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle =(2n-m-1)\left\langle \!\!\left\langle {n-1 \atop m-1}\right\rangle \!\!\right\rangle +(m+1)\left\langle \!\!\left\langle {n-1 \atop m}\right\rangle \!\!\right\rangle ,}$

с начальным условием для n = 0, выраженным в скобках Айверсона :

${\displaystyle \left\langle \!\!\left\langle {0 \atop m}\right\rangle \!\!\right\rangle =[m=0].}$

Соответственно, полином Эйлера второго рода, обозначенный здесь P _n (для них не существует стандартных обозначений), являются

${\displaystyle P_{n}(x):=\sum _{m=0}^{n}\left\langle \!\!\left\langle {n \atop m}\right\rangle \!\!\right\rangle x^{m}}$

и приведенные выше рекуррентные соотношения переводятся в рекуррентное соотношение для последовательности P _n ( x ):

${\displaystyle P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x)}$

с начальным условием

${\displaystyle P_{0}(x)=1.}$

Последнее повторение может быть записано в более компактной форме с помощью интегрирующего множителя:

${\displaystyle (x-1)^{-2n-2}P_{n+1}(x)=\left(x(1-x)^{-2n-1}P_{n}(x)\right)^{\prime }}$

так что рациональная функция

${\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)}$

удовлетворяет простому автономному повторению:

${\displaystyle u_{n+1}=\left({\frac {x}{1-x}}u_{n}\right)^{\prime },\quad u_{0}=1,}$

откуда получаются полиномы Эйлера как P _n ( x ) = (1 - x ) ^{2 n} u _n ( x ) и числа Эйлера второго рода в качестве их коэффициентов.

Вот некоторые значения чисел Эйлера второго порядка (последовательность A008517 в OEIS ):

м п	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), равна (2 n - 1) !!.

Ссылки [ править ]

• Эйлер, Леонард [Леонард Эйлер] (1755). Учреждения дифференциального исчисления с приложениями к конечному анализу и рядам [Основы дифференциального исчисления с приложениями к конечному анализу и рядам] . Academia imperialis scientiarum Petropolitana; Беролини: Officina Michaelis.
• Карлитц, Л. (1959). «Числа Эйлера и многочлены». Математика. Mag . 32 (5): 247–260. DOI : 10.2307 / 3029225 . JSTOR  3029225 .
• Гулд, HW (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, PL; Хаус, М. (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=( справка )

Цитаты [ править ]

Внешние ссылки [ править ]

• Многочлены Эйлера в OEIS Wiki.
• «Числа Эйлера» . MathPages.com .
• Вайсштейн, Эрик В. «Число Эйлера» . MathWorld .
• Вайсштейн, Эрик У. "Числовой треугольник Эйлера" . MathWorld .
• Вайсштейн, Эрик В. «Личность Ворпицки» . MathWorld .
• Вайстейн, Эрик В. "Эйлеров треугольник второго порядка" . MathWorld .
• Матрица Эйлера (обобщенные индексы строк, расходящееся суммирование)