Изменения

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

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

Пусть у нас есть некая перестановка <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> (всего <texdpi=190>\langle{n\atop m}\rangle </tex> возможностей) или перед последним последним элементом каждого подъема (еще <tex>m \times </tex><texdpi=190> \langle{n\atop m}\rangle </tex> раз).# Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex>n</tex> во все места, не подходящие по критерию первого пункта. Таких вставок, как не трудно догадаться, можно совершить <tex>(n - m)</tex><texdpi=190>\langle{n\atop m}\rangle</tex>.

:<texdpi=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>

:<texdpi=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>.

Рассмотрим все перестановки порядка <tex>4</tex>, в которых есть ровно <tex>2 </tex> подъема (в квадратных скобках один или больше подъемов подряд)::<texdpi=190> \left\langle{4\atop 2}\right\rangle </tex> <tex> = 11:

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

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

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

:<texdpi=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>

:<texdpi=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>

:<texdpi=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>

Число <texdpi=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>;

Пусть <tex>w \in \mathbb{R}</tex> - — вектор с ненулевыми компонентами (<tex>w = {w_1, w_2 ... w_n}</tex>), а <tex>z \in \mathbb{R}_+</tex>. Тогда верно следующее равенство:

*<tex>G_{w, z}^{n} := \{x \in \mathbb{R}^{n} : (w \cdot x) \le z \}</tex> - — полупространство;

*<tex>1_K</tex>, где <tex>K</tex> - — подмножество <tex>\{1,2...n\}</tex>, {{---}} вектор, где значения координат с номерами, входящими в <tex>K</tex>, равны <tex>1</tex>, а остальные {{---}} нули;

|proof=С доказательством можно ознакомиться по [ссылке <ref>http://arxiv.org/pdf/math/0607715.pdf этой] ссылке</ref>.

Положим <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> = </tex> <tex dpi=190>\frac{1}{n!}\left\langle{n\atop m}\right\rangle</tex> (вторая явная формула)

#:<texdpi=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>\sum\limits_{m=0}^{n} </tex><tex dpi=190> \left\langle{n\atop m}\right\rangle </tex> <tex> = n!,\ n \ge 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>

'''''Числа Эйлера 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 = "140190"> \scriptstyle \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle </tex>

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

|neat 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>.

:<texdpi=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>

:<texdpi=190> \left\langle \!\! \left\langle {0 \atop m} \right\rangle \!\! \right\rangle </tex> <tex> = [m=0]. </tex>

==СсылкиПримечания==<references/> ==Источники информации==