Числа Эйлера I и II рода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства)
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
==Числа Эйлера I рода==
 
==Числа Эйлера I рода==
'''''Числа Эйлера I рода''''' (''Eulerian numbers'') — количество [[Комбинаторные объекты|перестановок]] чисел от 1 до ''n'' таких, что в каждой из них существует ровно ''m'' подъемов. Числа Эйлера I рода обозначают как <tex>\langle{n\atop m}\rangle </tex> или же <tex>A(n, m)</tex>.
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть <tex>a</tex> и <tex>b</tex> - соседние элементы некоторой перестановки порядка <tex>n</tex> причем <tex>a > b</tex>. Тогда пара <tex>(a, b)</tex> называется '''подъемом''' (''ascent'') данной перестановки.
+
Пусть <tex>a</tex> и <tex>b</tex> соседние элементы некоторой перестановки порядка <tex>n</tex> причем <tex>a < b</tex>. Тогда пара <tex>(a, b)</tex> называется '''подъемом''' (англ. ''ascent'') данной перестановки.
 
}}
 
}}
 +
'''''Числа Эйлера I рода''''' (англ. ''Eulerian numbers'') — количество [[Комбинаторные объекты|перестановок]] чисел от <tex>1</tex> до <tex>n</tex> таких, что в каждой из них существует ровно <tex>m</tex> подъемов. Числа Эйлера I рода обозначают как <tex dpi=190>\langle{n\atop m}\rangle </tex> или же <tex>A(n, m)</tex>.
  
 
===Вывод рекуррентной формулы===
 
===Вывод рекуррентной формулы===
Пусть у нас есть некая перестановка <tex> \pi = \pi_1, \pi_2...\pi_{n-1} </tex>. Тогда операцией вставки элемента с номером n в какую-либо из позиций мы получим <tex>n</tex> перестановок вида <tex>\theta = \theta_1, \theta_2...\theta_p, n, \theta_q...\theta_{n-1}</tex>. Далее рассмотрим два случая:
+
Пусть у нас есть некая перестановка <tex> \pi = \pi_1, \pi_2\ldots \pi_{n-1} </tex>. Тогда операцией вставки элемента с номером <tex>n</tex> в какую-либо из позиций мы получим <tex>n</tex> перестановок вида <tex>\theta = \theta_1, \theta_2\ldots \theta_p, n, \theta_q\ldots \theta_{n-1}</tex>. Далее рассмотрим два случая:
  
1. Количество подъемов в перестановке <tex>\theta</tex> равно количеству подъемов в <tex>\pi</tex>. Этого можно добиться, вставляя элемент <tex>n</tex> на самое первое место в <tex>\theta</tex> (всего <tex>\langle{n\atop m}\rangle </tex> возможностей) или перед последним последним элементом каждого подъема (еще <tex>m \times </tex><tex> \langle{n\atop m}\rangle </tex> раз).
+
# Количество подъемов в перестановке <tex>\theta</tex> равно количеству подъемов в <tex>\pi</tex>. Этого можно добиться, вставляя элемент <tex>n</tex> на самое первое место в <tex>\theta</tex> (всего <tex dpi=190>\langle{n - 1\atop m}\rangle </tex> возможностей) или перед последним последним элементом каждого подъема (еще <tex>m \times </tex><tex dpi=190> \langle{n - 1\atop m}\rangle </tex> раз).
 
+
# Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex>n</tex> во все места, не подходящие по критерию первого пункта. Таких вставок, как не трудно догадаться, можно совершить <tex>(n - m)</tex><tex dpi=190>\langle{n - 1\atop m - 1}\rangle</tex>.
2. Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex>n</tex> во все места, не подходящие по критерию первого пункта. Таких вставок, как не трудно догадаться, можно совершить <tex>(n - m)</tex><tex>\langle{n\atop m}\rangle</tex>.
 
  
 
Тогда рекуррентная формула имеет вид:
 
Тогда рекуррентная формула имеет вид:
  
:<tex>\left\langle{n\atop m}\right\rangle = (m + 1)\left\langle{n - 1\atop m}\right\rangle + (n - m)\left\langle{n - 1\atop m - 1}\right\rangle</tex>
+
:<tex dpi=190>\left\langle{n\atop m}\right\rangle</tex> <tex> = (m + 1)</tex> <tex dpi=190>\left\langle{n - 1\atop m}\right\rangle</tex> <tex> + (n - m)</tex> <tex dpi=180>\left\langle{n - 1\atop m - 1}\right\rangle</tex>
  
 
Примем также следующее начальное значение:
 
Примем также следующее начальное значение:
:<tex>\left\langle{n\atop m}\right\rangle = [m = 0]</tex>,
+
:<tex dpi=190>\left\langle{0\atop m}\right\rangle</tex> <tex> = [m = 0]</tex><ref>http://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%82%D0%B0%D1%86%D0%B8%D1%8F_%D0%90%D0%B9%D0%B2%D0%B5%D1%80%D1%81%D0%BE%D0%BD%D0%B0 нотация Айверсона</ref>.
Запись [выражение] означает [http://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%82%D0%B0%D1%86%D0%B8%D1%8F_%D0%90%D0%B9%D0%B2%D0%B5%D1%80%D1%81%D0%BE%D0%BD%D0%B0 нотацию Айверсона].
 
 
 
  
 
===Пример===
 
===Пример===
Рассмотрим все перестановки порядка <tex>4</tex>, в которых есть ровно 2 подъема (в квадратных скобках один или больше подъемов подряд):
+
Рассмотрим все перестановки порядка <tex>4</tex>, в которых есть ровно <tex>2</tex> подъема (в квадратных скобках один или больше подъемов подряд):
:<tex> \left\langle{4\atop 2}\right\rangle = 11:
+
:<tex dpi=190> \left\langle{4\atop 2}\right\rangle</tex> <tex> = 11:
 
[124]3,
 
[124]3,
 
[13][24],
 
[13][24],
Строка 38: Строка 35:
 
</tex>
 
</tex>
  
Согласно алгоритму вывода рекуррентной формулы мы можем добавить '4' в следующие позиции всех перестановок порядка <tex>3</tex> с двумя подъемами, не увеличив количество подъемов:
+
Согласно алгоритму вывода рекуррентной формулы мы можем добавить <tex>4</tex> в следующие позиции всех перестановок порядка <tex>3</tex> с двумя подъемами, не увеличив количество подъемов:
  
:<tex>
+
:<tex dpi=190>
\left\langle{3\atop 2}\right\rangle = 1:
+
\left\langle{3\atop 2}\right\rangle</tex> <tex> = 1:
[123] => (4)[123], [1(4)][23], [12(4)]3
+
[123] \Rightarrow (4)[123], [1(4)][23], [12(4)]3
 
</tex>
 
</tex>
  
Далее рассмотрим все перестановки порядка <tex>3</tex> с одним подъемом, причем операцией вставки <tex>4</tex> мы будем увеличивать количество перестановок на 1:
+
Далее рассмотрим все перестановки порядка <tex>3</tex> с одним подъемом, причем операцией вставки <tex>4</tex> мы будем увеличивать количество подъемов на <tex>1</tex>:
  
:<tex> \left\langle{3\atop 1}\right\rangle = 4:</tex>
+
:<tex dpi=190> \left\langle{3\atop 1}\right\rangle</tex> <tex> = 4:</tex>
  
:<tex>[13]2 => [13(4)]2, [13][2(4)];</tex>
+
:<tex>[13]2 \Rightarrow [13(4)]2, [13][2(4)];</tex>
  
:<tex>2[13] => [2(4)][13], 2[13(4)];</tex>
+
:<tex>2[13] \Rightarrow [2(4)][13], 2[13(4)];</tex>
  
:<tex>[23]1 => [23(4)]1, [23][1(4)];</tex>
+
:<tex>[23]1 \Rightarrow [23(4)]1, [23][1(4)];</tex>
  
:<tex>3[12] => [3(4)][12], 3[12(4)];</tex>
+
:<tex>3[12] \Rightarrow [3(4)][12], 3[12(4)];</tex>
  
 
Таким образом мы убеждаемся в верности формулы:
 
Таким образом мы убеждаемся в верности формулы:
  
:<tex> \left\langle{4\atop 2}\right\rangle = (2 + 1) \left\langle{3\atop 2}\right\rangle + (4 - 2)\left\langle{3\atop 1}\right\rangle  = 11;</tex>
+
:<tex dpi=190> \left\langle{4\atop 2}\right\rangle</tex> <tex> = (2 + 1)</tex> <tex dpi=190>\left\langle{3\atop 2}\right\rangle</tex> <tex> + (4 - 2)</tex> <tex dpi=190>\left\langle{3\atop 1}\right\rangle</tex> <tex> = 11;</tex>
  
  
Строка 202: Строка 199:
 
|}
 
|}
  
===Явная формула===
+
===Явные формулы===
Воспользуемся для вывода треугольником, построенным с помощью рекурсивного варианта формулы.
+
:<tex dpi=190>\left\langle{n\atop m}\right\rangle</tex> <tex> = \sum\limits_{j=1}^{m+1} (-1)^{m-j+1} {n+1\choose m-j+1}j^{n}</tex>
 +
:<tex  dpi=190>\left\langle{n\atop m}\right\rangle</tex> <tex> = \sum\limits_{j=0}^{m}(-1)^j {n+1\choose j} (m+1-j)^n</tex>
 +
 
 +
===Связь чисел Эйлера I рода с сечениями гиперкубов===
 +
{{Теорема
 +
|statement=
 +
Число <tex>\dfrac{1}{n!}</tex> <tex dpi=190>\left\langle{n\atop m}\right\rangle</tex> выражает объем части <tex>n</tex>-мерного единичного гиперкуба, ограниченного гиперплоскостями <tex>x_1+x_2+\dots+x_n=m</tex> и <tex>x_1+x_2+\dots+x_n=m-1</tex>.
 +
|proof=
 +
Для доказательства этого факта нам потребуется следующая теорема:
 +
{{Теорема
 +
|about=Об объемах сечений <tex>n</tex>-мерных гиперкубов полупространствами
 +
|statement=
  
Следует заметить, что первый элемент каждой <tex>m</tex>-той строки равен 1, а второй --- <tex>2^{m} - (m + 1)</tex>. Третий выражается как
+
Пусть <tex>w \in \mathbb{R}</tex> — вектор с ненулевыми компонентами (<tex>w = {w_1, w_2 \ldots w_n}</tex>), а <tex>z \in \mathbb{R}_+</tex>. Тогда верно следующее равенство:
:<tex>3^{m}-(m + 1)2^m + \frac{(m+1)m}{2};</tex>
 
  
и так далее. Первые три элемента могут быть записаны в форме:
+
<tex>\mathrm{Vol}_{n}(G^n_{w,z} \cap I^{n}) = \dfrac{1}{n! \prod\limits_{i=1}^{n}w_i} \sum\limits_{K \subseteq [n]} (-1)^{|K|}(z-w \cdot 1_K)^n_+</tex>
:<tex>\left\langle{m\atop 1}\right\rangle = {{m + 1} \choose {0}}1^{m}</tex>
 
:<tex>\left\langle{m\atop 2}\right\rangle = {{m + 1} \choose {0}}2^{m} + {{m + 1} \choose {1}}1^{m}</tex>
 
:<tex>\left\langle{m\atop 3}\right\rangle = {{m + 1} \choose {0}}3^{m} - {{m + 1} \choose {1}}2^{m} + {{m + 1} \choose {2}}1^{m}</tex>
 
  
Тогда нетрудно проверить, что эта сумма продолжается именно таким образом и, следовательно, мы можем обобщить ее в "строгом виде" как:
+
*<tex>G_{w, z}^{n} := \{x \in \mathbb{R}^{n} : (w \cdot x) \leqslant z \}</tex> — полупространство;
:<tex>\left\langle{m\atop n}\right\rangle = \sum\limits_{j=1}^{n+1} (-1)^{n-j+1} {m+1\choose n-j+1}j^{m}</tex>
+
*<tex>I^n := [0,1]^n</tex>;
 +
*<tex>[n] := \{1,2\ldots n\}</tex>;
 +
*<tex>1_K</tex>, где <tex>K</tex> — подмножество <tex>\{1,2\ldots n\}</tex>, {{---}} вектор, где значения координат с номерами, входящими в <tex>K</tex>, равны <tex>1</tex>, а остальные {{---}} нули;
 +
*Для <tex>r \in \mathbb{R}</tex> и <tex>n \in \mathbb{N}</tex> : <tex>r^n_+ := (\max{\{r, 0\}})^n</tex>.
  
===Свойства===
+
|proof=С доказательством можно ознакомиться по ссылке <ref>http://arxiv.org/pdf/math/0607715.pdf</ref>.
[[Файл:EulerianHC1.png|200px|thumb|Свойство 4 для m = 2, n = 1. V = 1/2]]
+
}}
[[Файл:EulerianHC2.png|200px|thumb|Свойство 4 для m = 3, n = 2. V = 1/6]]
 
  
1. Нетрудно увидеть, что каждый ряд ненулевых значений симметричен относительно своей середины, то есть:
+
[[Файл:HypercubeEuler2_2.png|200px|thumb|m = 2, n = 1. V = 1/2]]
:<tex>\left\langle{n\atop m}\right\rangle = \left\langle{n\atop (n-1) - k}\right\rangle,\ n \ge 1,\ 0 \le k \le n-1. \, </tex>
+
[[Файл:HypercubeEuler3.png|200px|thumb|m = 3, n = 2. V = 1/6]]
 +
Рассмотрим пересечение гиперкуба полупространством <tex>G^n_{1_{[n]},m}</tex>. Вектор <tex>1_{[n]}</tex> (все координаты которого равны единицы) появляется здесь ввиду того, как мы определили в формулировке секущие гиперплоскости (<tex>x_1+x_2+\ldots +x_n = m | m+1</tex>) {{---}} это вектор нормали к <tex>\mathrm{G}</tex>. Очевидно, что при данном значении вектора произведение <tex>\prod\limits_{i=1}^{n}w_i</tex> равно единице (вектор <tex>w_i</tex> тут {{---}} единичный вектор <tex>1_{[n]}</tex>, то есть рассматривается произведение всех его координат {{---}} единиц). Рассмотрим выражение, стоящее под знаком суммы. При итерации по подмножествам <tex>[n]</tex> равной мощности будут получаться одинаковые слагаемые, так как выражение <tex>(-1)^{|K|}(z-w \cdot 1_K)^n_+</tex> зависит лишь от мощности итерируемого в сумме подмножества <tex>K</tex> {{---}} скалярное произведение <tex>w \cdot 1_K</tex> одинаково за счет того лишь факта, что оно вычисляется как сумма произведений соответствующих координат, где ровно <tex>n - |K|</tex> их обращаются в ноль. Такое скалярное произведение будет равно мощности <tex>K</tex>. Заменим итератор суммы значением мощности множества <tex>K</tex>. Также ограничим верхний индекс суммирования значением  <tex>m+1</tex>, так как при больших значениях <tex>j</tex> слагаемое будет обращаться в ноль (<tex>r^n_+</tex>). Отсюда имеем <tex>{n \choose j}</tex> таких одинаковых слагаемых, где <tex>j = |K|</tex>.
  
2. Сумма всех значений каждого ряда равна <tex> n! </tex>:
+
Тогда перейдем от первоначальной формулировки теоремы к следующей:
:<tex>\sum\limits_{k=0}^{n} \left\langle{n\atop m}\right\rangle = n!,\ n \ge 0, \,</tex>
+
:<tex>\mathrm{Vol}_{n}(G^n_{1_{[n]},m} \cap I^{n}) = \dfrac{1}{n!}\sum\limits_{j = 0}^{m + 1} (-1)^{j}{n \choose j}(m-j)^n</tex>
  
3. Связь чисел Эйлера I рода с числом сочетаний:
+
Положим <tex>W_n^m</tex> — фигура, образованная сечением гиперкуба <tex>[0,1]^{n}</tex> плоскостями <tex>\sum\limits_{i=1}^{n} x_{i} = m</tex>  и <tex>\sum\limits_{i=1}^{n} x_{i} = m+1</tex>.
:<tex>\sum\limits_{m=0}^n (-1)^m {\left\langle{n\atop m}\right\rangle}{n-1\choose m}^{-1}=0.</tex>
+
:<tex>W_n^m := \{ x \in \mathbb{R} : m \leqslant x \cdot 1_{[n]} \leqslant m+1 \} \cap I^{n}</tex>
  
4. Число <tex>\frac{1}{n!}\left\langle{n\atop m}\right\rangle</tex> выражает объем части <tex>n</tex>-мерного единичного гиперкуба, ограниченного гиперплоскостями <tex>x_1+x_2+\dots+x_n=m</tex> и <tex>x_1+x_2+\dots+x_n=m-1</tex>;
+
Тогда перейдем к следующему равенству:
  
''Доказательство''
+
:<tex>\mathrm{Vol}_{n}(W_n^m) = \mathrm{Vol}_n(G_{1_{[n]},m+1}^{n} \cap I^n) - \mathrm{Vol}_n(G_{1_{[n]},m}^{n} \cap I^n)</tex>
 +
:<tex>= \dfrac{1}{n!}[\sum\limits_{j=0}^{m+1}(-1)^{j}{n \choose j}(m+1-j)^{n} - \sum\limits_{j=0}^{m}(-1)^{j}{n \choose j}(m-j)^{n}]</tex>
 +
:<tex> = \dfrac{1}{n!}\sum\limits_{j=0}^{m+1}(-1)^j{n+1 \choose j}(m+1-j)^n</tex>
 +
:<tex> = \dfrac{1}{n!}\sum\limits_{j=0}^{m}(-1)^j{n+1 \choose j}(m+1-j)^n</tex>  (элемент суммы с номером <tex>j=m+1</tex> обращается в ноль)
 +
:<tex> = </tex> <tex>\dfrac{1}{n!}</tex> <tex dpi=190>\left\langle{n\atop m}\right\rangle</tex> (вторая явная формула)
  
Положим <tex>\Xi_m^n</tex> - фигура, образованная сечением гиперкуба <tex>I^{n}</tex> плоскостями <tex>\sum\limits_{i=1}^{n} x_{i} = k</tex>  и <tex>\sum\limits_{i=1}^{n} x_{i} = k+1</tex>.
+
}}
:<tex>\Xi_m^n </tex><tex>:= \{ x \in \mathbb{R} : k \le x \cdot 1_{[n]} \le k+1 \} \cap I^{n}</tex>
 
  
Тогда перейдем к следующему равенству:
+
===Свойства===
  
:<tex>Vol_{n}(\Xi_m^n) = Vol_n(G_{1_{[n]},k+1}^{n} \cap I^n) - Vol_n(G_{1_{[n]},k}^{n} \cap I^n)</tex>
+
# Нетрудно увидеть, что каждый ряд ненулевых значений симметричен относительно своей середины, то есть:
:<tex>= \frac{1}{n!}[\sum\limits_{j=0}^{k+1}(-1)^{j}{n \choose j}(k+1-j)^{n} - \sum\limits_{j=0}^{k}(-1)^{j}{n \choose j}(k-j)^{n}]</tex>
+
#:<tex dpi=190>\left\langle{n\atop m}\right\rangle = \left\langle{n\atop (n-1) - k}\right\rangle</tex><tex>,\ n \geqslant 1,\ 0 \leqslant k \leqslant n-1. \, </tex>
:<tex> = \frac{1}{n!}\sum\limits_{j=0}^{k+1}(-1)^j{n+1 \choose j}(k+1-j)^n</tex>
+
# Сумма всех значений каждого ряда равна <tex> n! </tex>:
:<tex> = \frac{1}{n!}\left\langle{n\atop k}\right\rangle</tex>
+
#:<tex>\sum\limits_{m=0}^{n}</tex><tex dpi=190> \left\langle{n\atop m}\right\rangle</tex> <tex> = n!,\ n \geqslant 0, \,</tex>
+
# Связь чисел Эйлера I рода с числом сочетаний:
5. Вероятность того, что сумма <tex>n</tex> независимых равномерно распределённых в отрезке <tex>[0,1]</tex> переменных лежит между <tex>m-1</tex> и <tex>m</tex> равна <tex>\frac{1}{n!}\left\langle{n\atop m}\right\rangle</tex>.
+
#:<tex>\sum\limits_{m=0}^n (-1)^m </tex><tex dpi=190>{\left\langle{n\atop m}\right\rangle}</tex> <tex>{n-1\choose m}^{-1}=0.</tex>
 +
# Вероятность того, что сумма <tex>n</tex> независимых равномерно распределённых в отрезке <tex>[0,1]</tex> переменных лежит между <tex>m-1</tex> и <tex>m</tex> равна <tex>\dfrac{1}{n!}\left\langle{n\atop m}\right\rangle</tex>.
  
 
==Числа Эйлера II рода==
 
==Числа Эйлера II рода==
'''''Числа Эйлера II рода''''' (''Eulerian numbers of the second kind'')  — количество перестановок мультимножества от <tex>1</tex> до <tex>n</tex> вида <tex>\{1,1,2,2..n,n\}</tex>, обладающих свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex>z</tex> для любого <tex>z</tex>, больше, чем <tex>z</tex>", таких, что в каждой из них существует ровно <tex>m</tex> подъемов. Числа Эйлера II рода обозначаются как <tex> \scriptstyle \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle </tex>
+
'''''Числа Эйлера II рода''''' (англ. ''Eulerian numbers of the second kind'')  — количество перестановок мультимножества от <tex>1</tex> до <tex>n</tex> вида <tex>\{1,1,2,2\ldots n,n\}</tex>, обладающих свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex>z</tex> для любого <tex>z</tex>, больше, чем <tex>z</tex>", таких, что в каждой из них существует ровно <tex>m</tex> подъемов. Числа Эйлера II рода обозначаются как <tex dpi = "190"> \scriptstyle \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle </tex>
  
  
 
'''Пример'''
 
'''Пример'''
  
Рассмотрим <tex> n = 3</tex>. Тогда существует 15 перестановок такого вида, среди которых одна не имеет подъемов, 8 штук имеют всего 1 подъем, и 6 перестановок имеют 2 подъема:
+
Рассмотрим <tex> n = 3</tex>. Тогда существует <tex>15</tex> перестановок такого вида, среди которых одна не имеет подъемов, <tex>8</tex> штук имеют всего <tex>1</tex> подъем, и <tex>6</tex> перестановок имеют <tex>2</tex> подъема:
  
 
:<tex> 332211,\; </tex>
 
:<tex> 332211,\; </tex>
Строка 258: Строка 269:
  
 
{{Лемма
 
{{Лемма
|statement=Количество перестановок мультимножества <tex>\{1,1,2,2..n,n\}</tex> со свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex>z</tex> для любого <tex>z</tex>, больше, чем
+
|statement=Количество перестановок мультимножества <tex>\{1,1,2,2\ldots n,n\}</tex> со свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex>z</tex> для любого <tex>z</tex>, больше, чем
 
<tex dpi="130">z</tex>" равно двойному факториалу <tex dpi="130">(2n-1)!!</tex>.
 
<tex dpi="130">z</tex>" равно двойному факториалу <tex dpi="130">(2n-1)!!</tex>.
|neat = 1
+
|proof = Докажем лемму методом математической индукции.
 +
*'''База'''. Для <tex>n=1</tex> очевидно, что существует только одна такая перестановка.
 +
*'''Переход'''.  Рассмотрим какую-нибудь перестановку длины <tex>2n</tex>. Таких перестановок <tex>(2n-1)!!</tex>. Теперь докажем, что перестановок длины <tex>2(n+1)</tex> будет <tex>(2(n+1)-1)!!</tex>. Попробуем вставить два числа <tex>n + 1</tex>. Очевидно, что их нельзя вставить не на соседние места, так как в таком случае между ними точно будут меньшие элементы. Но их можно вставить в любые два соседних места, так как они больше всех чисел в перестановке, а значит они не нарушат свойства для других элементов. Таким образом два новых элемента можно вставить в <tex>2n+1</tex> место. В итоге перестановок длины <tex>2(n+1)</tex> будет <tex>(2n-1)!!\cdot (2n+1)=(2n+1)!!=(2(n+1)-1)!!</tex>.
 
}}
 
}}
 
  
 
===Рекуррентная формула===
 
===Рекуррентная формула===
 
Числа Эйлера II рода можно выразить рекурсивно следующим образом:
 
Числа Эйлера II рода можно выразить рекурсивно следующим образом:
:<tex> \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, </tex>
+
:<tex dpi=190> \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle</tex> <tex> = (2n-m-1) </tex> <tex dpi=180>\left\langle \!\! \left\langle {n-1 \atop m-1} \right\rangle \!\! \right\rangle</tex> <tex> + (m+1) </tex> <tex dpi=190>\left\langle \!\! \left\langle {n-1 \atop m} \right\rangle \!\! \right\rangle, </tex>
  
 
С начальным условием для <tex>n = 0</tex>:
 
С начальным условием для <tex>n = 0</tex>:
:<tex> \left\langle \!\! \left\langle {0 \atop m} \right\rangle \!\! \right\rangle = [m=0]. </tex>
+
:<tex dpi=190> \left\langle \!\! \left\langle {0 \atop m} \right\rangle \!\! \right\rangle</tex> <tex> = [m=0]. </tex>
  
 
===Треугольник чисел Эйлера II рода===
 
===Треугольник чисел Эйлера II рода===
Значения чисел Эйлера II рода для <tex>0 \le n \le m \le 9</tex> представлены в данном массиве. Нижнедиагональная его часть называется треугольником чисел Эйлера II рода.
+
Значения чисел Эйлера II рода для <tex>0 \leqslant n \leqslant m \leqslant 9</tex> представлены в данном массиве. Нижнедиагональная его часть называется треугольником чисел Эйлера II рода.
  
 
:::{| class="number_triangle"
 
:::{| class="number_triangle"
Строка 412: Строка 424:
 
|}
 
|}
  
==Ссылки==
+
== См. также ==
 +
* [[Комбинаторные_объекты#.D0.9F.D0.B5.D1.80.D0.B5.D1.81.D1.82.D0.B0.D0.BD.D0.BE.D0.B2.D0.BA.D0.B8|Перестановки]]
 +
* [[Числа_Стирлинга_первого_рода|Числа Стирлинга первого рода]]
 +
* [[Числа_Стирлинга_второго_рода|Числа Стирлинга второго рода]]
 +
* [[Числа_Каталана|Числа Каталана]]
 +
 
 +
==Примечания==
 +
<references/>
 +
 
 +
==Источники информации==
 
<references/>
 
<references/>
 
*[http://en.wikipedia.org/wiki/Eulerian_number Eulerian number — Wikipedia]
 
*[http://en.wikipedia.org/wiki/Eulerian_number Eulerian number — Wikipedia]

Текущая версия на 19:35, 4 сентября 2022

Числа Эйлера I рода

Определение:
Пусть [math]a[/math] и [math]b[/math] — соседние элементы некоторой перестановки порядка [math]n[/math] причем [math]a \lt b[/math]. Тогда пара [math](a, b)[/math] называется подъемом (англ. ascent) данной перестановки.

Числа Эйлера I рода (англ. Eulerian numbers) — количество перестановок чисел от [math]1[/math] до [math]n[/math] таких, что в каждой из них существует ровно [math]m[/math] подъемов. Числа Эйлера I рода обозначают как [math]\langle{n\atop m}\rangle [/math] или же [math]A(n, m)[/math].

Вывод рекуррентной формулы

Пусть у нас есть некая перестановка [math] \pi = \pi_1, \pi_2\ldots \pi_{n-1} [/math]. Тогда операцией вставки элемента с номером [math]n[/math] в какую-либо из позиций мы получим [math]n[/math] перестановок вида [math]\theta = \theta_1, \theta_2\ldots \theta_p, n, \theta_q\ldots \theta_{n-1}[/math]. Далее рассмотрим два случая:

  1. Количество подъемов в перестановке [math]\theta[/math] равно количеству подъемов в [math]\pi[/math]. Этого можно добиться, вставляя элемент [math]n[/math] на самое первое место в [math]\theta[/math] (всего [math]\langle{n - 1\atop m}\rangle [/math] возможностей) или перед последним последним элементом каждого подъема (еще [math]m \times [/math][math] \langle{n - 1\atop m}\rangle [/math] раз).
  2. Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента [math]n[/math] во все места, не подходящие по критерию первого пункта. Таких вставок, как не трудно догадаться, можно совершить [math](n - m)[/math][math]\langle{n - 1\atop m - 1}\rangle[/math].

Тогда рекуррентная формула имеет вид:

[math]\left\langle{n\atop m}\right\rangle[/math] [math] = (m + 1)[/math] [math]\left\langle{n - 1\atop m}\right\rangle[/math] [math] + (n - m)[/math] [math]\left\langle{n - 1\atop m - 1}\right\rangle[/math]

Примем также следующее начальное значение:

[math]\left\langle{0\atop m}\right\rangle[/math] [math] = [m = 0][/math][1].

Пример

Рассмотрим все перестановки порядка [math]4[/math], в которых есть ровно [math]2[/math] подъема (в квадратных скобках один или больше подъемов подряд):

[math] \left\langle{4\atop 2}\right\rangle[/math] [math] = 11: [124]3, [13][24], [134]2, [14][23], 2[134], [23][14], [23][41], [24][13], 3[124], [34][12], 4[123], [/math]

Согласно алгоритму вывода рекуррентной формулы мы можем добавить [math]4[/math] в следующие позиции всех перестановок порядка [math]3[/math] с двумя подъемами, не увеличив количество подъемов:

[math] \left\langle{3\atop 2}\right\rangle[/math] [math] = 1: [123] \Rightarrow (4)[123], [1(4)][23], [12(4)]3 [/math]

Далее рассмотрим все перестановки порядка [math]3[/math] с одним подъемом, причем операцией вставки [math]4[/math] мы будем увеличивать количество подъемов на [math]1[/math]:

[math] \left\langle{3\atop 1}\right\rangle[/math] [math] = 4:[/math]
[math][13]2 \Rightarrow [13(4)]2, [13][2(4)];[/math]
[math]2[13] \Rightarrow [2(4)][13], 2[13(4)];[/math]
[math][23]1 \Rightarrow [23(4)]1, [23][1(4)];[/math]
[math]3[12] \Rightarrow [3(4)][12], 3[12(4)];[/math]

Таким образом мы убеждаемся в верности формулы:

[math] \left\langle{4\atop 2}\right\rangle[/math] [math] = (2 + 1)[/math] [math]\left\langle{3\atop 2}\right\rangle[/math] [math] + (4 - 2)[/math] [math]\left\langle{3\atop 1}\right\rangle[/math] [math] = 11;[/math]


Треугольник чисел Эйлера I рода

На значениях [math]n = m[/math] чисел Эйлера I рода можно построить массив [math]n \times m[/math], нижнедиагональная часть которого названа треугольником чисел Эйлера I рода.

m = 0 1 2 3 4 5 6 7 8 9
n = 0 1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0
2 1 1 0 0 0 0 0 0 0 0
3 1 4 1 0 0 0 0 0 0 0
4 1 11 11 1 0 0 0 0 0 0
5 1 26 66 26 1 0 0 0 0 0
6 1 57 302 302 57 1 0 0 0 0
7 1 120 1191 2416 1191 120 1 0 0 0
8 1 247 4293 15619 15619 4293 247 1 0 0
9 1 502 14608 88234 156190 88234 14608 502 1 0

Явные формулы

[math]\left\langle{n\atop m}\right\rangle[/math] [math] = \sum\limits_{j=1}^{m+1} (-1)^{m-j+1} {n+1\choose m-j+1}j^{n}[/math]
[math]\left\langle{n\atop m}\right\rangle[/math] [math] = \sum\limits_{j=0}^{m}(-1)^j {n+1\choose j} (m+1-j)^n[/math]

Связь чисел Эйлера I рода с сечениями гиперкубов

Теорема:
Число [math]\dfrac{1}{n!}[/math] [math]\left\langle{n\atop m}\right\rangle[/math] выражает объем части [math]n[/math]-мерного единичного гиперкуба, ограниченного гиперплоскостями [math]x_1+x_2+\dots+x_n=m[/math] и [math]x_1+x_2+\dots+x_n=m-1[/math].
Доказательство:
[math]\triangleright[/math]

Для доказательства этого факта нам потребуется следующая теорема:

Теорема (Об объемах сечений [math]n[/math]-мерных гиперкубов полупространствами):
Пусть [math]w \in \mathbb{R}[/math] — вектор с ненулевыми компонентами ([math]w = {w_1, w_2 \ldots w_n}[/math]), а [math]z \in \mathbb{R}_+[/math]. Тогда верно следующее равенство:

[math]\mathrm{Vol}_{n}(G^n_{w,z} \cap I^{n}) = \dfrac{1}{n! \prod\limits_{i=1}^{n}w_i} \sum\limits_{K \subseteq [n]} (-1)^{|K|}(z-w \cdot 1_K)^n_+[/math]

  • [math]G_{w, z}^{n} := \{x \in \mathbb{R}^{n} : (w \cdot x) \leqslant z \}[/math] — полупространство;
  • [math]I^n := [0,1]^n[/math];
  • [math][n] := \{1,2\ldots n\}[/math];
  • [math]1_K[/math], где [math]K[/math] — подмножество [math]\{1,2\ldots n\}[/math], — вектор, где значения координат с номерами, входящими в [math]K[/math], равны [math]1[/math], а остальные — нули;
  • Для [math]r \in \mathbb{R}[/math] и [math]n \in \mathbb{N}[/math] : [math]r^n_+ := (\max{\{r, 0\}})^n[/math].
Доказательство:
[math]\triangleright[/math]
С доказательством можно ознакомиться по ссылке [2].
[math]\triangleleft[/math]
m = 2, n = 1. V = 1/2
m = 3, n = 2. V = 1/6

Рассмотрим пересечение гиперкуба полупространством [math]G^n_{1_{[n]},m}[/math]. Вектор [math]1_{[n]}[/math] (все координаты которого равны единицы) появляется здесь ввиду того, как мы определили в формулировке секущие гиперплоскости ([math]x_1+x_2+\ldots +x_n = m | m+1[/math]) — это вектор нормали к [math]\mathrm{G}[/math]. Очевидно, что при данном значении вектора произведение [math]\prod\limits_{i=1}^{n}w_i[/math] равно единице (вектор [math]w_i[/math] тут — единичный вектор [math]1_{[n]}[/math], то есть рассматривается произведение всех его координат — единиц). Рассмотрим выражение, стоящее под знаком суммы. При итерации по подмножествам [math][n][/math] равной мощности будут получаться одинаковые слагаемые, так как выражение [math](-1)^{|K|}(z-w \cdot 1_K)^n_+[/math] зависит лишь от мощности итерируемого в сумме подмножества [math]K[/math] — скалярное произведение [math]w \cdot 1_K[/math] одинаково за счет того лишь факта, что оно вычисляется как сумма произведений соответствующих координат, где ровно [math]n - |K|[/math] их обращаются в ноль. Такое скалярное произведение будет равно мощности [math]K[/math]. Заменим итератор суммы значением мощности множества [math]K[/math]. Также ограничим верхний индекс суммирования значением [math]m+1[/math], так как при больших значениях [math]j[/math] слагаемое будет обращаться в ноль ([math]r^n_+[/math]). Отсюда имеем [math]{n \choose j}[/math] таких одинаковых слагаемых, где [math]j = |K|[/math].

Тогда перейдем от первоначальной формулировки теоремы к следующей:

[math]\mathrm{Vol}_{n}(G^n_{1_{[n]},m} \cap I^{n}) = \dfrac{1}{n!}\sum\limits_{j = 0}^{m + 1} (-1)^{j}{n \choose j}(m-j)^n[/math]

Положим [math]W_n^m[/math] — фигура, образованная сечением гиперкуба [math][0,1]^{n}[/math] плоскостями [math]\sum\limits_{i=1}^{n} x_{i} = m[/math] и [math]\sum\limits_{i=1}^{n} x_{i} = m+1[/math].

[math]W_n^m := \{ x \in \mathbb{R} : m \leqslant x \cdot 1_{[n]} \leqslant m+1 \} \cap I^{n}[/math]

Тогда перейдем к следующему равенству:

[math]\mathrm{Vol}_{n}(W_n^m) = \mathrm{Vol}_n(G_{1_{[n]},m+1}^{n} \cap I^n) - \mathrm{Vol}_n(G_{1_{[n]},m}^{n} \cap I^n)[/math]
[math]= \dfrac{1}{n!}[\sum\limits_{j=0}^{m+1}(-1)^{j}{n \choose j}(m+1-j)^{n} - \sum\limits_{j=0}^{m}(-1)^{j}{n \choose j}(m-j)^{n}][/math]
[math] = \dfrac{1}{n!}\sum\limits_{j=0}^{m+1}(-1)^j{n+1 \choose j}(m+1-j)^n[/math]
[math] = \dfrac{1}{n!}\sum\limits_{j=0}^{m}(-1)^j{n+1 \choose j}(m+1-j)^n[/math] (элемент суммы с номером [math]j=m+1[/math] обращается в ноль)
[math] = [/math] [math]\dfrac{1}{n!}[/math] [math]\left\langle{n\atop m}\right\rangle[/math] (вторая явная формула)
[math]\triangleleft[/math]

Свойства

  1. Нетрудно увидеть, что каждый ряд ненулевых значений симметричен относительно своей середины, то есть:
    [math]\left\langle{n\atop m}\right\rangle = \left\langle{n\atop (n-1) - k}\right\rangle[/math][math],\ n \geqslant 1,\ 0 \leqslant k \leqslant n-1. \, [/math]
  2. Сумма всех значений каждого ряда равна [math] n! [/math]:
    [math]\sum\limits_{m=0}^{n}[/math][math] \left\langle{n\atop m}\right\rangle[/math] [math] = n!,\ n \geqslant 0, \,[/math]
  3. Связь чисел Эйлера I рода с числом сочетаний:
    [math]\sum\limits_{m=0}^n (-1)^m [/math][math]{\left\langle{n\atop m}\right\rangle}[/math] [math]{n-1\choose m}^{-1}=0.[/math]
  4. Вероятность того, что сумма [math]n[/math] независимых равномерно распределённых в отрезке [math][0,1][/math] переменных лежит между [math]m-1[/math] и [math]m[/math] равна [math]\dfrac{1}{n!}\left\langle{n\atop m}\right\rangle[/math].

Числа Эйлера II рода

Числа Эйлера II рода (англ. Eulerian numbers of the second kind) — количество перестановок мультимножества от [math]1[/math] до [math]n[/math] вида [math]\{1,1,2,2\ldots n,n\}[/math], обладающих свойством "все элементы перестановки, встречающиеся между двумя вхождниями [math]z[/math] для любого [math]z[/math], больше, чем [math]z[/math]", таких, что в каждой из них существует ровно [math]m[/math] подъемов. Числа Эйлера II рода обозначаются как [math] \scriptstyle \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle [/math]


Пример

Рассмотрим [math] n = 3[/math]. Тогда существует [math]15[/math] перестановок такого вида, среди которых одна не имеет подъемов, [math]8[/math] штук имеют всего [math]1[/math] подъем, и [math]6[/math] перестановок имеют [math]2[/math] подъема:

[math] 332211,\; [/math]
[math] 221[13]3,\; 22[13]31,\; 2[23]311,\; [23]3211,\; 1[13]322,\; [13]3221,\; 331[12]2,\; 33[12]21, [/math]
[math]1[12][23]3,\; [12]2[13]3,\; 1[123]32,\; [123]321,\; [13]3[12]2,\; [12][23]31. [/math]
Лемма:
Количество перестановок мультимножества [math]\{1,1,2,2\ldots n,n\}[/math] со свойством "все элементы перестановки, встречающиеся между двумя вхождниями [math]z[/math] для любого [math]z[/math], больше, чем [math]z[/math]" равно двойному факториалу [math](2n-1)!![/math].
Доказательство:
[math]\triangleright[/math]

Докажем лемму методом математической индукции.

  • База. Для [math]n=1[/math] очевидно, что существует только одна такая перестановка.
  • Переход. Рассмотрим какую-нибудь перестановку длины [math]2n[/math]. Таких перестановок [math](2n-1)!![/math]. Теперь докажем, что перестановок длины [math]2(n+1)[/math] будет [math](2(n+1)-1)!![/math]. Попробуем вставить два числа [math]n + 1[/math]. Очевидно, что их нельзя вставить не на соседние места, так как в таком случае между ними точно будут меньшие элементы. Но их можно вставить в любые два соседних места, так как они больше всех чисел в перестановке, а значит они не нарушат свойства для других элементов. Таким образом два новых элемента можно вставить в [math]2n+1[/math] место. В итоге перестановок длины [math]2(n+1)[/math] будет [math](2n-1)!!\cdot (2n+1)=(2n+1)!!=(2(n+1)-1)!![/math].
[math]\triangleleft[/math]

Рекуррентная формула

Числа Эйлера II рода можно выразить рекурсивно следующим образом:

[math] \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle[/math] [math] = (2n-m-1) [/math] [math]\left\langle \!\! \left\langle {n-1 \atop m-1} \right\rangle \!\! \right\rangle[/math] [math] + (m+1) [/math] [math]\left\langle \!\! \left\langle {n-1 \atop m} \right\rangle \!\! \right\rangle, [/math]

С начальным условием для [math]n = 0[/math]:

[math] \left\langle \!\! \left\langle {0 \atop m} \right\rangle \!\! \right\rangle[/math] [math] = [m=0]. [/math]

Треугольник чисел Эйлера II рода

Значения чисел Эйлера II рода для [math]0 \leqslant n \leqslant m \leqslant 9[/math] представлены в данном массиве. Нижнедиагональная его часть называется треугольником чисел Эйлера II рода.

m = 0 1 2 3 4 5 6 7 8 9
n = 0 1 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0
2 1 2 0 0 0 0 0 0 0 0
3 1 8 6 0 0 0 0 0 0 0
4 1 22 58 24 0 0 0 0 0 0
5 1 52 328 444 120 0 0 0 0 0
6 1 114 1452 4400 3708 720 0 0 0 0
7 1 240 5610 32120 58140 33984 5040 0 0 0
8 1 494 19950 195800 644020 785304 341136 40320 0 0
9 1 1004 67260 1062500 5765500 12440064 11026296 3733920 362880 0

См. также

Примечания

Источники информации