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

Не путать с числом Эйлера или числом Эйлера .

В комбинаторике число Эйлера ${\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)}$ является

График эйлеровых чисел со вторым аргументом, равным 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
	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)$

$\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}$

Личность Ворпицкого выражает ${\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)$

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

$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-е изд.). Аддисон-Уэсли. стр. 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 .

Внешние ссылки

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