число Эйлера

редактировать

Полиномиальная последовательность

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

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

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

∑ N знак равно 0 ∞ A n (t) ⋅ xnn! = т - 1 т - е (т - 1) х. {\ displaystyle \ sum _ {n = 0} ^ {\ infty} A_ {n} (t) \ cdot {\ frac {x ^ {n}} {n!}} = {\ frac {t-1} { t- \ mathrm {e} ^ {(t-1) x}}}.}{\ displaystyle \ sum _ {n = 0} ^ {\ infty} A_ {n} (t) \ cdot {\ frac {x ^ {n}} {n !}} = {\ frac {t-1 } {t- \ mathrm {e} ^ {(t-1) x}}}.}

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

A 0 (t) = 1, {\ displaystyle A_ {0} (t) = 1,}{\ displaystyle A_ { 0} (t) = 1,}
A n (t) = t (1 - t) ⋅ A n - 1 ′ (t) + A n - 1 (t) ⋅ (1 + (n - 1) t), N ≥ 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_{n}(t)=t(1-t)\cdot A_{n-1}'(t)+A_{n-1}(t)\cdot (1+(n-1)t),\quad n\geq 1.}

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

A 0 (t) = 1, {\ displaystyle A_ {0 } (t) = 1,}{\ displaystyle A_ { 0} (t) = 1,}
A n (t) = ∑ k = 0 n - 1 (nk) A k (t) ⋅ (t - 1) n - 1 - k, n ≥ 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.}{\ displaystyle A_ {n} (t) = \ sum _ {k = 0} ^ {n-1} {\ binom {n} {k}} A_ {k} (t) \ cdot (t-1) ^ {n-1-k}, \ четырехъядерный n \ geq 1.}

Другие обозначения для A (n, m): E (n, m) и ⟨nm⟩ {\ displaystyle \ scriptstyle \ left \ langle { n \ atop m} \ right \ rangle}\ scriptstyle \ left \ langle {n \ atop m} \ right \ rangle .

Содержание

  • 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. Например,

nmПерестановкиA (n, m)
10(1)A (1,0) = 1
20(2, 1)A (2,0) = 1
1(1, 2)A (2,1) = 1
30(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) = (n - m) A (n - 1, m - 1) + (m + 1) A (n - 1, m). {\ Displaystyle A (n, m) = (нм) A (n-1, m-1) + (m + 1) A (n-1, m).}A (n, m) = (нм) A (n-1, m-1) + (m + 1) A (n-1, m).

Например,

A (4, 1) = (4 - 1) A (3, 0) + (1 + 1) A (3, 1) = 3 × 1 + 2 × 4 = 11. {\ Displaystyle A (4,1) = (4-1) A (3, 0) + (1 + 1) A (3,1) = 3 \ times 1 + 2 \ times 4 = 11.}A (4,1) = (4-1) A (3,0) + (1 + 1) A (3,1) = 3 \ times 1 + 2 \ times 4 = 11.

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

mn012345678
11
211
3141
4111111
512666261
6157302302571
711201191241611911201
812474293156191561942932471
91502146088823415619088234146085021

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

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

Явная формула для A (n, m):

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

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

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

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

∑ м знак равно 0 N - 1 A (N, т) = п! для n ≥ 1. {\ displaystyle \ sum _ {m = 0} ^ {n-1} A (n, m) = n! {\ text {for}} n \ geq 1.}\ sum _ {{m = 0}} ^ {{n-1}} A (n, m) = n! {\ Text {for}} n \ geq 1.

The переменная сумма чисел Эйлера для фиксированного значения n связана с числом Бернулли B n + 1

∑ m = 0 n - 1 (- 1) m A (n, m) знак равно 2 n + 1 (2 n + 1 - 1) B n + 1 n + 1 для n ≥ 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.}\ 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.

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

∑ m = 0 n - 1 (- 1) m A (n, m) (n - 1 m) Знак равно 0 для n ≥ 2, {\ displaystyle \ sum _ {m = 0} ^ {n-1} (- 1) ^ {m} {\ frac {A (n, m)} {\ binom {n-1 } {m}}} = 0 {\ text {for}} n \ geq 2,}\ sum _ {{m = 0}} ^ {{n-1}} (- 1) ^ {m} {\ frac {A (n, m)} {{\ binom {n -1} {m}}}} = 0 {\ text {for}} n \ geq 2,
∑ m = 0 n - 1 (- 1) m A (n, m) (nm) = (n + 1) В N для n ≥ 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,}\ 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 степеней:

∑ k = 0 ∞ knxk = ∑ m = 0 n - 1 A (N, м) Иксм + 1 (1 - Икс) N + 1 знак равно Икс ⋅ A N (Икс) (1 - Икс) n + 1 {\ Displaystyle \ sum _ {к = 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}}}}{\ 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}}}}

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

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

xn = ∑ m = 0 n - 1 A (n, m) (x + мин). {\ displaystyle x ^ {n} = \ sum _ {m = 0} ^ {n-1} A (n, m) {\ binom {x + m} {n}}.}x ^ {n} = \ sum _ {{m = 0}} ^ {{n-1}} A (n, m) {\ binom { x + m} {n}}.

Это следует из формулы Ворпицки тождество, что

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

Еще одно интересное тождество:

e 1 - ex = ∑ n = 0 ∞ A n (x) n! (1 - х) п + 1. {\ displaystyle {\ frac {e} {1-ex}} = \ sum _ {n = 0} ^ {\ infty} {\ frac {A_ {n} (x)} {n! (1-x) ^ {n + 1}}}.}{\ frac {e} {1-ex}} = \ sum _ {{n = 0 }} ^ {\ infty} {\ frac {A_ {n} (x)} {n! (1-x) ^ {{n + 1}}}}.

Числитель в правой части - многочлен Эйлера.

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

∫ 0 1 ⋯ ∫ 0 1 f (⌊ x 1 + ⋯ + xn ⌋) dx 1 ⋯ dxn = ∑ К А (П, К) е (К) п!. {\ Displaystyle \ int _ {0} ^ {1} \ cdots \ int _ {0} ^ {1} f \ left (\ left \ lfloor x_ {1} + \ cdots + x_ {n} \ right \ rfloor \ справа) dx_ {1} \ cdots dx_ {n} = \ sum _ {k} A (n, k) {\ frac {f (k)} {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,..., n, n}, которые обладают тем свойством, что для каждого k все числа, встречающиеся между двумя вхождения k в перестановке больше, чем k, подсчитываются с помощью двойного факториала числа (2n-1) !!. Число Эйлера второго рода, обозначаемое ⟨⟨nm⟩⟩ {\ displaystyle \ scriptstyle \ left \ langle \! \ Left \ langle {n \ atop m} \ right \ rangle \! \ Right \ rangle}{\ displaystyle \ 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.

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

⟨⟨Нм⟩⟩ знак равно (2 n - m - 1) ⟨⟨n - 1 m - 1⟩⟩ + (m + 1) ⟨⟨n - 1 m⟩⟩, {\ displaystyle \ left \ langle \! \ ! \ left \ langle {n \ на вершине m} \ right \ rangle \! \! \ right \ rangle = (2n-m-1) \ left \ langle \! \! \ left \ langle {n-1 \ на вершине m -1} \ right \ rangle \! \! \ Right \ rangle + (m + 1) \ left \ langle \! \! \ Left \ langle {n-1 \ на вершине m} \ right \ rangle \! \! \ right \ rangle,}\ left \ langle \! \! \ Left \ langle {n \ atop m} \ right \ rangle \! \! \ Right \ rangle = (2n-m-1) \ left \ langle \! \! \ left \ langle {n-1 \ на вершине m-1} \ right \ rangle \! \! \ right \ rangle + (m + 1) \ left \ langle \! \! \ left \ langle {n-1 \ наверху m} \ right \ rangle \! \! \ right \ rangle,

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

⟨⟨0 m⟩⟩ = [m = 0]. {\ displaystyle \ left \ langle \! \! \ left \ langle {0 \ atop m} \ right \ rangle \! \! \ right \ rangle = [m = 0].}\ left \ langle \! \! \ left \ langle {0 \ на вершине m} \ right \ rangle \! \! \ right \ rangle = [m = 0 ].

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

P n (x): = ∑ m = 0 n ⟨⟨nm⟩⟩ xm {\ displaystyle P_ {n} (x): = \ sum _ {m = 0} ^ {n} \ left \ langle \! \! \ left \ langle {n \ atop m} \ right \ rangle \! \! \ right \ rangle x ^ { m}}P_ {n} (x): = \ sum _ {{m = 0}} ^ {n} \ left \ langle \! \! \ left \ langle {n \ на вершине m} \ right \ rangle \! \! \ right \ rangle x ^ {m }

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

P n + 1 (x) = (2 nx + 1) P N (Икс) - Икс (Икс - 1) P N '(Икс) {\ Displaystyle P_ {N + 1} (x) = (2nx + 1) P_ {n} (x) -x (x-1) P_ {n} ^ {\ prime} (x)}P _ {{n + 1}} (x) = (2nx + 1) P_ {n} (x) -x (x-1) P_ {n} ^ { \ prime} (x)

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

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

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

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

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

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

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

un + 1 = (x 1 - xun) ′, u 0 = 1, {\ displaystyle u_ {n + 1} = \ left ({\ frac {x} {1-x}} u_ {n} \ right) ^ {\ prime}, \ quad u_ {0} = 1,}u _ {{n + 1}} = \ left ({\ frac {x} {1-x}} u_ {n} \ right) ^ {\ prime}, \ quad u_ {0} = 1,

откуда можно получить многочлены Эйлера как P n (x) = (1 − x) u n (x), а числа Эйлера второго рода в качестве их коэффициентов.

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

mn012345678
11
212
3186
41225824
5152328444120
61114145244003708720
7124056103212058140339845040
814941995019580064402078530434113640320
911004672601062500576550012440064110262963733920362880

Сумма n-й строки, которая также является значением P n ( 1), равно (2n - 1) !!.

Ссылки

Цитаты

  1. ^Worpitzky, J. (1883). «Studien über die Bernoullischen und Eulerschen Zahlen». Journal für die reine und angewandte Mathematik. 94 : 203–232.
  2. ^Упражнение 6,65 дюйма Конкретная математика Грэма, Кнута и Паташника.

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

Последняя правка сделана 2021-05-19 06:32:42
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте