Число Эйлера - Eulerian number

Не путать с Число Эйлера или же Число Эйлера.

В комбинаторика, то Число Эйлера А(п, м) - количество перестановки чисел от 1 до п в котором именно м элементов больше, чем предыдущий элемент (перестановки с м "восхождения"). Это коэффициенты при Полиномы Эйлера:

${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 ngeq 1.}$

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

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

${displaystyle A_{n}(t)=sum _{k=0}^{n-1}{inom {n}{k}}A_{k}(t)cdot (t-1)^{n-1-k},quad ngeq 1.}$

Другие обозначения для А(п, м) находятся E(п, м) и ${displaystyle scriptstyle leftlangle {n atop m}ightangle }$.

История

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

В 1755 г. Леонард Эйлер исследовал в своей книге Институты дифференциального исчисления многочлены α₁(Икс) = 1, α₂(Икс) = Икс + 1, α₃(Икс) = Икс² + 4Икс + 1и др. (см. факсимиле). Эти многочлены представляют собой сдвинутую форму того, что сейчас называется многочленами Эйлера. А_п(Икс).

Основные свойства

Для данного значения п > 0 индекс м в А(п, м) может принимать значения от 0 до п - 1. Для фиксированных п есть единственная перестановка, которая имеет 0 восхождений: (п, п − 1, п - 2, ..., 1). Также существует единственная перестановка, которая имеет п - 1 восхождение; это восходящая перестановка (1, 2, 3, ..., п). Следовательно А(п, 0) и А(п, п - 1) равны 1 для всех значений п.

Обращение перестановки с м ascents создает другую перестановку, в которой п − м - 1 восхождение. А(п, м) = А(п, п − м − 1).

Ценности А(п, м) можно рассчитать «вручную» для малых значений п и м. Например

п	м	Перестановки	А(п, м)
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)=(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 imes 1+2 imes 4=11.}$

Ценности А(п, м) (последовательность A008292 в OEIS ) для 0 ≤ п ≤ 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

Вышесказанное треугольная решетка называется Треугольник Эйлера или же Треугольник Эйлера, и он имеет некоторые общие характеристики с Треугольник Паскаля. Сумма строки п это факториал п!.

Явная формула

Явная формула для А(п, м) является^[1]

${displaystyle A(n,m)=sum _{k=0}^{m+1}(-1)^{k}{inom {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}$.

Свойства суммирования

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

${displaystyle sum _{m=0}^{n-1}A(n,m)=n!{ ext{ for }}ngeq 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}}{ ext{ for }}ngeq 1.}$

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

${displaystyle sum _{m=0}^{n-1}(-1)^{m}{frac {A(n,m)}{inom {n-1}{m}}}=0{ ext{ for }}ngeq 2,}$

${displaystyle sum _{m=0}^{n-1}(-1)^{m}{frac {A(n,m)}{inom {n}{m}}}=(n+1)B_{n}{ ext{ for }}ngeq 2,}$

куда B_п это п^th Число Бернулли.

Идентичности

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

${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 {xcdot A_{n}(x)}{(1-x)^{n+1}}}}$

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

Личность Ворпицки^[2] выражает Икс^п как линейная комбинация чисел Эйлера с биномиальные коэффициенты:

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

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

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

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

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

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

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

${displaystyle int _{0}^{1}cdots int _{0}^{1}fleft(leftlfloor x_{1}+cdots +x_{n}ightfloor ight)dx_{1}cdots dx_{n}=sum _{k}A(n,k){frac {f(k)}{n!}}.}$

Числа Эйлера второго рода

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

332211,

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

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

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

${displaystyle leftlangle !!leftlangle {n atop m}ightangle !!ightangle =(2n-m-1)leftlangle !!leftlangle {n-1 atop m-1}ightangle !!ightangle +(m+1)leftlangle !!leftlangle {n-1 atop m}ightangle !!ightangle ,}$

с начальным условием для п = 0, выраженный в Кронштейн Айверсона обозначение:

${displaystyle leftlangle !!leftlangle {0 atop m}ightangle !!ightangle =[m=0].}$

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

${displaystyle P_{n}(x):=sum _{m=0}^{n}leftlangle !!leftlangle {n atop m}ightangle !!ightangle x^{m}}$

и указанные выше рекуррентные соотношения переводятся в рекуррентное соотношение для последовательности п_п(Икс):

${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)ight)^{prime }}$

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

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

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

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

откуда можно получить многочлены Эйлера как п_п(Икс) = (1−Икс)^2п ты_п(Икс), а числа Эйлера 2-го рода - их коэффициентами.

Вот некоторые значения чисел Эйлера второго порядка (последовательность 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

Сумма п-я строка, которая также является значением п_п(1), это (2п − 1)!!.

Рекомендации

• Эйлер, Леонард [Леонард Эйлер] (1755). Учреждения дифференциального исчисления с применением к конечному анализу и рядам [Основы дифференциального исчисления с приложениями к конечному анализу и рядам]. Academia imperialis scientiarum Petropolitana; Беролини: Officina Michaelis.
• Карлитц, Л. (1959). «Числа Эйлера и многочлены». Математика. Mag. 32 (5): 247–260. Дои:10.2307/3029225. JSTOR  3029225.
• Гулд, Х. В. (1978). «Оценка сумм свернутых степеней с использованием чисел Стирлинга и Эйлера». Фиб. Кварта. 16 (6): 488–497.
• Desarmenien, Jacques; Фоата, Доминик (1992). «Знаковые числа Эйлера». Дискретная математика. 99 (1–3): 49–58. Дои:10.1016 / 0012-365X (92) 90364-L.
• Lesieur, Leonce; Николя, Жан-Луи (1992). «О числах Эйлера M = max (A (n, k))». Europ. J. Combinat. 13 (5): 379–399. Дои:10.1016 / S0195-6698 (05) 80018-6.
• Butzer, P.L .; Хаус, М. (1993). «Числа Эйлера с дробными параметрами порядка». Aequationes Mathematicae. 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 Basler Lehrbücher. Birkhäuser. С. 3–18. Дои:10.1007/978-1-4939-3091-3_1. ISBN  978-1-4939-3090-6. Отсутствует или пусто | название = (помощь)

Цитаты

1. (Л. Контет, 1974, с. 243).
2. Ворпицки Дж. (1883 г.). "Studien über die Bernoullischen und Eulerschen Zahlen". Журнал für die reine und angewandte Mathematik. 94: 203–232.
3. Упражнение 6,65 дюйма Конкретная математика Грэхем, Кнут и Паташник.

внешняя ссылка

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