Изменения

'''''Числа Эйлера I рода''''' (''Eulerian numbers'') — количество [[Комбинаторные объекты|перестановок]] чисел от 1 до ''n'' таких, что в каждой из них существует ровно ''m'' подъемов. ==Числа Эйлера I рода обозначают как <tex dpi = "160">\langle{n\atop m}\rangle </tex> или же <tex dpi = "160">A(n, m)</tex>.{{Определение

Пусть <tex dpi = "130">a</tex> и <tex dpi = "130">b</tex> - — соседние элементы некоторой перестановки порядка <tex dpi = "130">n</tex> причем <tex dpi = "130">a > < b</tex>. Тогда пара <tex dpi = "130">(a, b)</tex> называется '''подъемом''' (англ. ''ascent'') данной перестановки.

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

1. # Количество подъемов в перестановке <tex dpi = "130">\theta</tex> равно количеству подъемов в <tex dpi = "130">\pi</tex>. Этого можно добиться, вставляя элемент <tex dpi = "130">n</tex> на самое первое место в <tex dpi = "130">\theta</tex> (всего <tex dpi = "160"190>\langle{n- 1\atop m}\rangle </tex> возможностей) или перед последним последним элементом каждого подъема(еще <tex dpi = "130">k m \times </tex><tex dpi = "160"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>.

Тогда рекуррентная формула имеет вид: <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 dpi = "180"190>\left\langle{n0\atop m}\right\rangle </tex> <tex> = ([m + 1)\left\langle{n - 1\atop m}\right\rangle + (n - m)\left\langle{n - 1\atop m - 1}\right\rangle= 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>.

Примем также ===Пример===Рассмотрим все перестановки порядка <tex>4</tex>, в которых есть ровно <tex>2</tex> подъема (в квадратных скобках один или больше подъемов подряд)::<tex dpi=190> \left\langle{4\atop 2}\right\rangle</tex> <tex> = 11:[124]3,[13][24],[134]2,[14][23],2[134],[23][14],[23][41],[24][13],3[124],[34][12],4[123],</tex> Согласно алгоритму вывода рекуррентной формулы мы можем добавить <tex>4</tex> в следующие начальные значенияпозиции всех перестановок порядка <tex>3</tex> с двумя подъемами, не увеличив количество подъемов: :<tex dpi=190>\left\langle{3\atop 2}\right\rangle</tex> <tex> = 1:[123] \Rightarrow (4)[123], [1(4)][23], [12(4)]3</tex> Далее рассмотрим все перестановки порядка <tex>3</tex> с одним подъемом, причем операцией вставки <tex>4</tex> мы будем увеличивать количество подъемов на <tex>1</tex>: :<tex dpi=190> \left\langle{3\atop 1}\right\rangle</tex> <tex> = 4:</tex> :<tex>[13]2 \Rightarrow [13(4)]2, [13][2(4)];</tex> :<tex>2[13] \Rightarrow [2(4)][13], 2[13(4)];</tex> :<tex>[23]1 \Rightarrow [23(4)]1, [23][1(4)];</tex> :<tex>3[12] \Rightarrow [3(4)][12], 3[12(4)];</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>  ===Треугольник чисел Эйлера I рода===На значениях <tex>n = m</tex> чисел Эйлера I рода можно построить массив <tex>n \times m</tex>, нижнедиагональная часть которого названа треугольником чисел Эйлера I рода. ::{| class="number_triangle"

<tex dpi |- align= "180center">\langle{| style="background:white; color:black; width:50px;" || style="background:white; color:black; width:50px;" | '''''m = 0'''''| style="background:white; color:black; width:50px;" | '''''1'''''| style="background:white; color:black; width:50px;" | '''''2'''''| style="background:white; color:black; width:50px;" | '''''3'''''| style="background:white; color:black; width:50px;" | '''''4'''''| style="background:white; color:black; width:50px;" | '''''5'''''| style="background:white; color:black; width:50px;" | '''''6'''''| style="background:white; color:black; width:50px;" | '''''7'''''| style="background:white; color:black; width:50px;" | '''''8'''''| style="background:white; color:black; width:50px;" | '''''9'''''|- align="center"| style="background:white; color:black;" | '''''n\atop m}\rangle = 0</tex>, если <tex dpi '''''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style= "130background:#FFDEAD; color:red;">m < | '''0</tex> или если <tex dpi '''| style= "130background:#FFDEAD; color:red;">n | '''0'''| style= "background:#FFDEAD; color:red;" | '''0</tex>'''| style="background:#FFDEAD; color:red;" | '''0'''

===ПримерЯвные формулы===Рассмотрим все перестановки порядка :<tex dpi = "130"190>4\left\langle{n\atop m}\right\rangle</tex>, в которых есть ровно 2 подъема <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 = "130"190> \left\langle{4n\atop 2m}\right\rangle </tex> выражает объем части <tex>n</tex>-мерного единичного гиперкуба, ограниченного гиперплоскостями <tex>x_1+x_2+\dots+x_n=m</tex> и <tex>x_1+x_2+\dots+x_n= 11: m-1</tex>.[124]3, |proof=[13][24], Для доказательства этого факта нам потребуется следующая теорема: [134]2, {{Теорема[14][23], |about=Об объемах сечений <tex>n</tex>-мерных гиперкубов полупространствами2[134], |statement=[23][14], [23][41]Пусть <tex>w \in \mathbb{R}</tex> — вектор с ненулевыми компонентами (<tex>w = {w_1, [24][13]w_2 \ldots w_n}</tex>), а <tex>z \in \mathbb{R}_+</tex>. Тогда верно следующее равенство:3[124], [34][12]<tex>\mathrm{Vol}_{n}(G^n_{w, 4z} \cap I^{n}) = \dfrac{1}{n! \prod\limits_{i=1}^{n}w_i} \sum\limits_{K \subseteq [123n], } (-1)^{|K|}(z-w \cdot 1_K)^n_+</tex>

Согласно алгоритму вывода рекуррентной формулы мы можем добавить '4' в следующие позиции всех перестановок порядка *<tex dpi >G_{w, z}^{n} := "130"\{x \in \mathbb{R}^{n} : (w \cdot x) \leqslant z \}</tex> — полупространство;*<tex>I^n := [0,1]^n</tex>;*<tex>[n] := \{1,2\ldots n\}</tex>;*<tex>1_K</tex>, где <tex>K</tex> — подмножество <tex>3\{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=С доказательством можно ознакомиться по ссылке <tex dpi = "130"ref> \left\langle{3\atop 2}\right\rangle = 1http:[123] => (4)[123], [1(4)][23], [12(4)]3//arxiv.org/pdf/math/0607715.pdf</texref>.}}

Далее рассмотрим [[Файл:HypercubeEuler2_2.png|200px|thumb|m = 2, n = 1. V = 1/2]][[Файл:HypercubeEuler3.png|200px|thumb|m = 3, n = 2. V = 1/6]]Рассмотрим пересечение гиперкуба полупространством <tex>G^n_{1_{[n]},m}</tex>. Вектор <tex>1_{[n]}</tex> (все перестановки порядка координаты которого равны единицы) появляется здесь ввиду того, как мы определили в формулировке секущие гиперплоскости (<tex dpi >x_1+x_2+\ldots +x_n = "130"m | m+1</tex>3) {{---}} это вектор нормали к <tex>\mathrm{G}</tex> с одним подъемом. Очевидно, причем операцией вставки что при данном значении вектора произведение <tex dpi >\prod\limits_{i= "130"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>4их обращаются в ноль. Такое скалярное произведение будет равно мощности <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 dpi = "130"> \leftmathrm{Vol}_{n}(G^n_{1_{[n]},m} \langlecap I^{3n}) = \atop dfrac{1}{n!}\rightsum\rangle limits_{j = 4:0}^{m + 1} (-1)^{j}{n \choose j}(m-j)^n</tex>

Положим <tex>W_n^m</tex> — фигура, образованная сечением гиперкуба <tex dpi = "130">[130,1]2 ^{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_{[13(4)]2, [13][2(4)n];} \leqslant m+1 \} \cap I^{n}</tex>

:<tex dpi >\mathrm{Vol}_{n}(W_n^m) = "130"\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!}[23\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> [23:<tex> = \dfrac{1}{n!}\sum\limits_{j=0}^{m}(4-1)]^j{n+1, [23][\choose j}(m+1-j)^n</tex> (4элемент суммы с номером <tex>j=m+1</tex> обращается в ноль)];:<tex> = </tex> <tex>\dfrac{1}{n!}</tex> <tex dpi=190>\left\langle{n\atop m}\right\rangle</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> 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># Связь чисел Эйлера 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>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>.