Редактирование: Числа Эйлера I и II рода

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
==Числа Эйлера I рода==
 
==Числа Эйлера I рода==
 +
'''''Числа Эйлера 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>.
 
{{Определение
 
{{Определение
 
|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\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>. Далее рассмотрим два случая:
+
Пусть у нас есть некая перестановка <tex> \pi = \pi_1, \pi_2...\pi_{n-1} </tex>. Тогда операцией вставки элемента с номером <tex>n</tex> в какую-либо из позиций мы получим <tex>n</tex> перестановок вида <tex>\theta = \theta_1, \theta_2...\theta_p, n, \theta_q...\theta_{n-1}</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>\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> раз).
Строка 206: Строка 206:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|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>.
+
Число <tex dpi=190>\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>;
 
|proof=
 
|proof=
 
Для доказательства этого факта нам потребуется следующая теорема:  
 
Для доказательства этого факта нам потребуется следующая теорема:  
Строка 213: Строка 213:
 
|statement=
 
|statement=
  
Пусть <tex>w \in \mathbb{R}</tex> — вектор с ненулевыми компонентами (<tex>w = {w_1, w_2 \ldots w_n}</tex>), а <tex>z \in \mathbb{R}_+</tex>. Тогда верно следующее равенство:
+
Пусть <tex>w \in \mathbb{R}</tex> — вектор с ненулевыми компонентами (<tex>w = {w_1, w_2 ... w_n}</tex>), а <tex>z \in \mathbb{R}_+</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 dpi = "140">\mathrm{Vol}_{n}(G^n_{w,z} \cap I^{n}) = \frac{1}{n! \prod\limits_{i=1}^{n}w_i} \sum\limits_{K \subseteq [n]} (-1)^{|K|}(z-w \cdot 1_K)^n_+</tex>
  
*<tex>G_{w, z}^{n} := \{x \in \mathbb{R}^{n} : (w \cdot x) \leqslant z \}</tex> — полупространство;
+
*<tex>G_{w, z}^{n} := \{x \in \mathbb{R}^{n} : (w \cdot x) \le z \}</tex> — полупространство;
 
*<tex>I^n := [0,1]^n</tex>;
 
*<tex>I^n := [0,1]^n</tex>;
*<tex>[n] := \{1,2\ldots n\}</tex>;
+
*<tex>[n] := \{1,2...n\}</tex>;
*<tex>1_K</tex>, где <tex>K</tex> — подмножество <tex>\{1,2\ldots n\}</tex>, {{---}} вектор, где значения координат с номерами, входящими в <tex>K</tex>, равны <tex>1</tex>, а остальные {{---}} нули;  
+
*<tex>1_K</tex>, где <tex>K</tex> — подмножество <tex>\{1,2...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>.
 
*Для <tex>r \in \mathbb{R}</tex> и <tex>n \in \mathbb{N}</tex> : <tex>r^n_+ := (\max{\{r, 0\}})^n</tex>.
  
Строка 228: Строка 228:
 
[[Файл:HypercubeEuler2_2.png|200px|thumb|m = 2, n = 1. V = 1/2]]
 
[[Файл:HypercubeEuler2_2.png|200px|thumb|m = 2, n = 1. V = 1/2]]
 
[[Файл:HypercubeEuler3.png|200px|thumb|m = 3, n = 2. V = 1/6]]
 
[[Файл: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>.  
+
Рассмотрим пересечение гиперкуба полупространством <tex>G^n_{1_{[n]},m}</tex>. Вектор <tex>1_{[n]}</tex> (все координаты которого равны единицы) появляется здесь ввиду того, как мы определили в формулировке секущие гиперплоскости (<tex>x_1+x_2+...+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>.  
  
 
Тогда перейдем от первоначальной формулировки теоремы к следующей:
 
Тогда перейдем от первоначальной формулировки теоремы к следующей:
:<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>
+
:<tex>\mathrm{Vol}_{n}(G^n_{1_{[n]},m} \cap I^{n}) = \frac{1}{n!}\sum\limits_{j = 0}^{m + 1} (-1)^{j}{n \choose j}(m-j)^n</tex>
  
 
Положим <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>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>W_n^m := \{ x \in \mathbb{R} : m \leqslant x \cdot 1_{[n]} \leqslant m+1 \} \cap I^{n}</tex>
+
:<tex>W_n^m := \{ x \in \mathbb{R} : m \le x \cdot 1_{[n]} \le m+1 \} \cap I^{n}</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>\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>= \frac{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> = \frac{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> = \frac{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> = </tex> <tex dpi=190>\frac{1}{n!}\left\langle{n\atop m}\right\rangle</tex> (вторая явная формула)
  
 
}}
 
}}
Строка 249: Строка 249:
  
 
# Нетрудно увидеть, что каждый ряд ненулевых значений симметричен относительно своей середины, то есть:
 
# Нетрудно увидеть, что каждый ряд ненулевых значений симметричен относительно своей середины, то есть:
#:<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 dpi=190>\left\langle{n\atop m}\right\rangle = \left\langle{n\atop (n-1) - k}\right\rangle</tex><tex>,\ n \ge 1,\ 0 \le k \le n-1. \, </tex>
 
# Сумма всех значений каждого ряда равна <tex> n! </tex>:
 
# Сумма всех значений каждого ряда равна <tex> n! </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>
+
#:<tex>\sum\limits_{m=0}^{n}</tex><tex dpi=190> \left\langle{n\atop m}\right\rangle</tex> <tex> = n!,\ n \ge 0, \,</tex>
 
# Связь чисел Эйлера I рода с числом сочетаний:
 
# Связь чисел Эйлера I рода с числом сочетаний:
 
#:<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>\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>.
+
# Вероятность того, что сумма <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>.
  
 
==Числа Эйлера II рода==
 
==Числа Эйлера II рода==
'''''Числа Эйлера 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>
+
'''''Числа Эйлера 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 dpi = "190"> \scriptstyle \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle </tex>
  
  
Строка 269: Строка 269:
  
 
{{Лемма
 
{{Лемма
|statement=Количество перестановок мультимножества <tex>\{1,1,2,2\ldots n,n\}</tex> со свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex>z</tex> для любого <tex>z</tex>, больше, чем
+
|statement=Количество перестановок мультимножества <tex>\{1,1,2,2..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>.
 
|proof = Докажем лемму методом математической индукции.  
 
|proof = Докажем лемму методом математической индукции.  
Строка 284: Строка 284:
  
 
===Треугольник чисел Эйлера II рода===
 
===Треугольник чисел Эйлера II рода===
Значения чисел Эйлера II рода для <tex>0 \leqslant n \leqslant m \leqslant 9</tex> представлены в данном массиве. Нижнедиагональная его часть называется треугольником чисел Эйлера II рода.
+
Значения чисел Эйлера II рода для <tex>0 \le n \le m \le 9</tex> представлены в данном массиве. Нижнедиагональная его часть называется треугольником чисел Эйлера II рода.
  
 
:::{| class="number_triangle"
 
:::{| class="number_triangle"

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)