Изменения

'''''Числа Эйлера 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 dpi = "180">\langle{n\atop m}\rangle = 03</tex>с одним подъемом, если причем операцией вставки <tex dpi = "130">m < 04</tex> или если мы будем увеличивать количество подъемов на <tex dpi = "130">n = 01</tex>;:

===Пример===Рассмотрим все перестановки порядка <tex dpi = "130">4</tex>, в которых есть ровно 2 подъема (в квадратных скобках один или больше подъемов подряд):<tex dpi = "130"> \left\langle{4\atop [13]2}\right\rangle = 11: Rightarrow [12413(4)]32, [13][242(4)], ;</tex> :<tex>2[13413]\Rightarrow [2, [14(4)][2313], 2[13413(4)], ;</tex> :<tex>[23]1 \Rightarrow [1423(4)]1, [23][411(4)], ;</tex> :<tex>3[2412]\Rightarrow [133(4)], 3[12412], [34]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" |- align="center"| 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 = 0'''''| 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="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0''' |- align="center"| style="background:white; color:black;" | '''''1'''''| 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="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''|- align="center"| style="background:white; color:black;" | '''''2'''''| style="background:#FFDEAD; color:black;" | '''1'''| 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="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''|- align="center"| style="background:white; color:black;" | '''''3'''''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:black;" | '''4'''| 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="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''|- align="center"| style="background:white; color:black;" | '''''4[123]'''''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:black;" | '''11'''| style="background:#FFDEAD; color:black;" | '''11'''| 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="background:#FFDEAD; color:red;" | '''0'''|- align="center"| style="background:white; color:black;" | '''''5'''''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:black;" | '''26'''| style="background:#FFDEAD; color:black;" | '''66'''| style="background:#FFDEAD; color:black;" | '''26'''| 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'''|- align="center"| style="background:white; color:black;" | '''''6'''''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:black;" | '''57'''| style="background:#FFDEAD; color:black;" | '''302'''| style="background:#FFDEAD; color:black;" | '''302'''| style="background:#FFDEAD; color:black;" | '''57'''| 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'''|- align="center"| style="background:white; color:black;" | '''''7'''''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:black;" | '''120'''| style="background:#FFDEAD; color:black;" | '''1191'''| style="background:#FFDEAD; color:black;" | '''2416'''| style="background:#FFDEAD; color:black;" | '''1191'''| style="background:#FFDEAD; color:black;" | '''120'''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''|- align="center"| style="background:white; color:black;" | '''''8'''''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:black;" | '''247'''| style="background:#FFDEAD; color:black;" | '''4293'''| style="background:#FFDEAD; color:black;" | '''15619'''| style="background:#FFDEAD; color:black;" | '''15619'''| style="background:#FFDEAD; color:black;" | '''4293'''| style="background:#FFDEAD; color:black;" | '''247'''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:red;" | '''0'''| style="background:#FFDEAD; color:red;" | '''0'''|- align="center"| style="background:white; color:black;" | '''''9'''''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:black;" | '''502'''| style="background:#FFDEAD; color:black;" | '''14608'''| style="background:#FFDEAD; color:black;" | '''88234'''| style="background:#FFDEAD; color:black;" | '''156190'''| style="background:#FFDEAD; color:black;" | '''88234'''| style="background:#FFDEAD; color:black;" | '''14608'''| style="background:#FFDEAD; color:black;" | '''502'''| style="background:#FFDEAD; color:black;" | '''1'''| style="background:#FFDEAD; color:red;" | '''0'''|} ===Явные формулы===:<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>w \in \mathbb{R}</tex> — вектор с ненулевыми компонентами (<tex>w = {w_1, w_2 \ldots w_n}</tex>), а <tex>z \in \mathbb{R}_+</tex>. Тогда верно следующее равенство:

Согласно алгоритму вывода рекуррентной формулы мы можем добавить '4' в следующие позиции всех перестановок порядка <tex dpi >\mathrm{Vol}_{n}(G^n_{w,z} \cap I^{n}) = "130">3\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 >G_{w, z}^{n} := "130"> \left{x \in \langlemathbb{3R}^{n} : (w \atop 2}cdot x) \rightleqslant z \rangle }</tex> — полупространство;*<tex>I^n := [0,1:]^n</tex>;*<tex>[123n] :=\{1,2\ldots n\}</tex>;*<tex>1_K</tex>, где <tex>K</tex> — подмножество <tex>\{1,2\ldots n\}</tex>, {{---}} вектор, где значения координат с номерами, входящими в <tex>K</tex> (4)[123], [равны <tex>1</tex>, а остальные {{---}} нули; *Для <tex>r \in \mathbb{R}</tex> и <tex>n \in \mathbb{N}</tex> : <tex>r^n_+ := (4)][23]\max{\{r, [12(40\}})]3^n</tex>.

Далее рассмотрим все перестановки порядка |proof=С доказательством можно ознакомиться по ссылке <tex dpi = "130"ref>3<http://arxiv.org/pdf/math/tex> с одним подъемом, причем операцией вставки <tex dpi = "130">40607715.pdf</texref> мы будем увеличивать количество перестановок на 1:.}}

[[Файл: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>) {{---}} это вектор нормали к <tex>\mathrm{G}</tex>. Очевидно, что при данном значении вектора произведение <tex> \leftprod\langlelimits_{i=1}^{n}w_i</tex> равно единице (вектор <tex>w_i</tex> тут {{---}} единичный вектор <tex>1_{[n]}</tex>, то есть рассматривается произведение всех его координат {{---}} единиц). Рассмотрим выражение, стоящее под знаком суммы. При итерации по подмножествам <tex>[n]</tex> равной мощности будут получаться одинаковые слагаемые, так как выражение <tex>(-1)^{3|K|}(z-w \atop 1cdot 1_K)^n_+</tex> зависит лишь от мощности итерируемого в сумме подмножества <tex>K</tex> {{---}}скалярное произведение <tex>w \rightcdot 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 \rangle choose j}</tex> таких одинаковых слагаемых, где <tex>j = 4:|K|</tex>.

Тогда перейдем от первоначальной формулировки теоремы к следующей::<tex dpi = "130">\mathrm{Vol}_{n}(G^n_{1_{[13n]2 },m} \cap I^{n}) => [13\dfrac{1}{n!}\sum\limits_{j = 0}^{m + 1} (4-1)]2, [13][2^{j}{n \choose j}(4m-j)];^n</tex>

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

:<tex dpi >\mathrm{Vol}_{n}(W_n^m) = "130">3\mathrm{Vol}_n(G_{1_{[12n] => [3},m+1}^{n} \cap I^n) - \mathrm{Vol}_n(4)]G_{1_{[12n]}, 3m}^{n} \cap I^n)</tex>:<tex>= \dfrac{1}{n!}[12\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}(4m-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 dpi = "160"> \left\langle{4\atop 2}\right\rangle = (2 + 1) \left\langle{3\atop 2}\right\rangle + (4 - 2)\left\langle{4\atop 2}\right\rangle = 11;</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>.