Эйлерово число

В комбинаторике Эйлера число ${\textstyle A(n,k)}$ - количество перестановок чисел от 1 до ${\textstyle n}$ в каком именно ${\textstyle k}$ элементы больше предыдущего элемента (перестановки с ${\textstyle k}$ «восхождения»).

Леонард Эйлер исследовал их и связанные с ними полиномы в своей книге 1755 года Institutiones Calculi Differentialis .

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

Другие обозначения для ${\textstyle A(n,k)}$ являются ${\textstyle E(n,k)}$ и $\textstyle \left\langle {n \atop k}\right\rangle$ .

Определение [ править ]

Эйлеровы полиномы $A_{n}(t)$ определяются экспоненциальной производящей функцией

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

Эйлеровы числа $A(n,k)$ могут быть определены как коэффициенты полиномов Эйлера:

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

Явная формула для ${\textstyle A(n,k)}$ является ^[1]

График чисел Эйлера со вторым аргументом, равным 5.

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

Основные свойства [ править ]

Для фиксированного ${\textstyle n}$ существует единственная перестановка, имеющая 0 восхождений: ${\textstyle (n,n-1,n-2,\ldots ,1)}$ . Действительно, как ${\tbinom {n}{0}}=1$ для всех $n$ , ${\textstyle A(n,0)=1}$ . Формально сюда входит пустой набор чисел, ${\textstyle n=0}$ . И так ${\textstyle A_{0}(t)=A_{1}(t)=1}$ .
Для ${\textstyle k=1}$ из явной формулы следует ${\textstyle A(n,1)=2^{n}-(n+1)}$ , последовательность в $n$ это читается ${\textstyle 0,0,1,4,11,26,57,\dots }$ .
Полностью обращая перестановку с ${\textstyle k}$ восхождения создают еще одну перестановку, в которой есть ${\textstyle n-k-1}$ восхождения. Поэтому ${\textstyle A(n,k)=A(n,n-k-1)}$ . Итак, существует также единственная перестановка, которая имеет ${\textstyle n-1}$ восхождения, а именно восходящая перестановка ${\textstyle (1,2,\ldots ,n)}$ . Поэтому также ${\textstyle A(n,n-1)}$ равно $1$ .
Щедрая верхняя граница ${\textstyle A(n,k)\leq (k+1)^{n}\cdot (n+2)^{k}}$ . Между только что обсужденными границами значение превышает $1$ .
Для ${\textstyle k\geq n>0}$ , значения формально равны нулю, что означает множество сумм по ${\textstyle k}$ можно записать с верхним индексом только до ${\textstyle n-1}$ . Это также означает, что полиномы $A_{n}(t)$ действительно имеют степень ${\textstyle n-1}$ для ${\textstyle n>0}$ .

Табуляция чисел в треугольном массиве называется треугольником Эйлера или треугольником Эйлера . Он имеет некоторые общие характеристики с треугольником Паскаля . Ценности ${\textstyle A(n,k)}$ (последовательность A008292 в OEIS ) для ${\textstyle 0\leq n\leq 9}$ являются:

к н	0	1	2	3	4	5	6	7	8
0	1
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

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

Для больших значений ${\textstyle n}$ , ${\textstyle A(n,k)}$ также можно рассчитать по рекурсивной формуле

A(n,k)=(n-k)\,A(n-1,k-1)+(k+1)\,A(n-1,k).

Эта формула может быть мотивирована комбинаторным определением и, таким образом, служит естественной отправной точкой для теории.

Для небольших значений ${\textstyle n}$ и ${\textstyle k}$ , значения ${\textstyle A(n,k)}$ можно посчитать вручную. Например

н	к	Перестановки	А ( п , к )
1	0	(1)	А (1,0) = 1
2	0	(2, 1)	А (2,0) = 1
2	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

Применяя повторение к одному примеру, мы можем найти

A(4,1)=(4-1)\,A(3,0)+(1+1)\,A(3,1)=3\cdot 1+2\cdot 4=11.

Аналогично, полиномы Эйлера можно вычислить с помощью рекуррентного метода

A_{0}(t)=1,

A_{n}(t)=A_{n-1}'(t)\cdot t\,(1-t)+A_{n-1}(t)\cdot (1+(n-1)\,t),{\text{ for }}n>1.

Вторую формулу можно привести к индуктивной форме:

A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k}}A_{k}(t)\cdot (t-1)^{n-1-k},{\text{ for }}n>1.

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

Для любого свойства, разбивающего конечное множество на конечное число меньших множеств, сумма мощностей меньших множеств равна мощности большего множества. Эйлеровы числа разделяют перестановки $n$ элементы, поэтому их сумма равна факториалу $n!$ . Т.е.

\sum _{k=0}^{n-1}A(n,k)=n!,{\text{ for }}n>0.

а также $A(0,0)=0!$ . Чтобы избежать конфликта с соглашением о пустой сумме , удобно просто сформулировать теоремы для $n>0$ только.

В более общем смысле для фиксированной функции $f\colon \mathbb {R} \rightarrow \mathbb {C}$ интегрируемо на интервале $(0,n)$ ^[2]

\sum _{k=0}^{n-1}A(n,k)\,f(k)=n!\int _{0}^{1}\cdots \int _{0}^{1}f\left(\left\lfloor x_{1}+\cdots +x_{n}\right\rfloor \right){\mathrm {d} }x_{1}\cdots {\mathrm {d} }x_{n}

Личность Ворпицкого ^[3] выражает ${\textstyle x^{n}}$ как линейная комбинация эйлеровых чисел с биномиальными коэффициентами :

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

Отсюда следует, что

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

Формулы, включающие знакопеременные суммы [ править ]

Попеременная сумма чисел Эйлера при фиксированном значении ${\textstyle n}$ связано с числом Бернулли ${\textstyle B_{n+1}}$

\sum _{k=0}^{n-1}(-1)^{k}A(n,k)=2^{n+1}(2^{n+1}-1){\frac {B_{n+1}}{n+1}},{\text{  for  }}n>0.

Более того,

\sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n-1}{k}}}=0,{\text{  for  }}n>1

и

\sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n}{k}}}=(n+1)B_{n},{\text{  for  }}n>1

Формулы с полиномами [ править ]

Свойство симметрии подразумевает:

A_{n}(t)=t^{n-1}A_{n}(t^{-1})

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

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

Явное выражение для полиномов Эйлера имеет вид ^[4]

$A_{n}(t)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}k!(t-1)^{n-k}$

Где ${\textstyle \left\{{n \atop k}\right\}}$ – числа Стирлинга второго рода .

Эйлеровы числа второго порядка [ править ]

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

332211,

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

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

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

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

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

\left\langle \!\!\left\langle {0 \atop k}\right\rangle \!\!\right\rangle =[k=0].

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

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

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

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

с начальным состоянием $P_{0}(x)=1.$ . Последнюю рекуррентность можно записать в несколько более компактной форме с помощью интегрирующего множителя:

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

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

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

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

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

Откуда получаются полиномы Эйлера второго порядка как ${\textstyle P_{n}(x)=(1-x)^{2n}u_{n}(x)}$ , а их коэффициентами — эйлеровы числа второго порядка.

В следующей таблице показаны первые несколько эйлеровых чисел второго порядка:

к н	0	1	2	3	4	5	6	7	8
0	1
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 -й строки, которая также является значением ${\textstyle P_{n}(1)}$ , является ${\textstyle (2n-1)!!}$ .

Индексирование эйлеровых чисел второго порядка осуществляется в трех вариантах:

(последовательность A008517 в OEIS ) после Риордана и Конте,
(последовательность A201637 в OEIS ) после Грэма, Кнута и Паташника,
(последовательность A340556 в OEIS ), расширяя определение Гесселя и Стэнли.

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

Эйлер, Леонард [Леонард Эйлер] (1755). Основы дифференциального исчисления с приложениями к конечному анализу и рядам [Основы дифференциального исчисления с приложениями к конечному анализу и рядам] . Петрополитенская Императорская Академия наук; Берлин: Officina Michaelis.
Карлитц, Л. (1959). «Эйлеровы числа и полиномы». Математика. Маг . 32 (5): 247–260. дои : 10.2307/3029225 . JSTOR 3029225 .
Гулд, HW (1978). «Оценка сумм свернутых степеней с использованием чисел Стирлинга и Эйлера» . Фиб. Кварта . 16 (6): 488–497.
Десармениен, Жак; Фоата, Доминик (1992). «Знаковые эйлеровы числа» . Дискретная математика . 99 (1–3): 49–58. дои : 10.1016/0012-365X(92)90364-L .
Лесье, Леонс; Николя, Жан-Луи (1992). «Об эйлеровых числах M=max (A(n,k))» . Европа. Ж. Комбинат . 13 (5): 379–399. дои : 10.1016/S0195-6698(05)80018-6 .
Батцер, Польша; Хаусс, М. (1993). «Эйлеровы числа с параметрами дробного порядка» . уравнения Математические 46 (1–2): 119–142. дои : 10.1007/bf01834003 . S2CID 121868847 .
Коутрас, М.В. (1994). «Эйлеровы числа, связанные с последовательностями полиномов» . Фиб. Кварта . 32 (1): 44.
Грэм; Кнут; Паташник (1994). Конкретная математика : Фонд информатики (2-е изд.). Аддисон-Уэсли. стр. 100-1 267–272.
Сюй, Литч К .; Джау-Шьонг Шиуэ, Питер (1999). «О некоторых задачах суммирования и обобщениях эйлеровых многочленов и чисел» . Дискретная математика . 204 (1–3): 237–247. дои : 10.1016/S0012-365X(98)00379-3 .
Бояджиев, Христо Н. (2007). «Функции Апостола-Бернулли, производные полиномы и полиномы Эйлера». arXiv : 0710.1124 [ math.CA ].
Петерсен, Т. Кайл (2015). «Эйлеровы числа». Эйлеровы числа . Учебники Birkhäuser Advanced Texts Basel. Биркхойзер. стр. 3–18. дои : 10.1007/978-1-4939-3091-3_1 . ISBN 978-1-4939-3090-6 .

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

^ (Л. Конте, 1974, стр. 243)
^ Упражнение 6.65 по конкретной математике Грэма, Кнута и Паташника.
^ Ворпицкий, Дж. (1883). «Исследования о числах Бернулля и Эйлера» . Журнал чистой и прикладной математики . 94 : 203-232.
^ Ци, Фэн; Го, Бай-Ни (01 августа 2017 г.). «Явные формулы и рекуррентные соотношения для полиномов Эйлера высшего порядка» . Indagationes Mathematicae . 28 (4): 884–891. дои : 10.1016/j.indag.2017.06.010 . ISSN 0019-3577 .

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

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

[1] (Л. Конте, 1974, стр. 243)

[2] Упражнение 6.65 по конкретной математике Грэма, Кнута и Паташника.

[3] Ворпицкий, Дж. (1883). «Исследования о числах Бернулля и Эйлера» . Журнал чистой и прикладной математики . 94 : 203-232.

[4] Ци, Фэн; Го, Бай-Ни (01 августа 2017 г.). «Явные формулы и рекуррентные соотношения для полиномов Эйлера высшего порядка» . Indagationes Mathematicae . 28 (4): 884–891. дои : 10.1016/j.indag.2017.06.010 . ISSN 0019-3577 .

[1]

[2]

[3]

[4]