Изменения

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

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

===Явная формулаЯвные формулы===Воспользуемся для вывода треугольником, построенным с помощью рекурсивного варианта формулы.:<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>m\dfrac{1}{n!}</tex>-той строки равен 1, а второй --- <texdpi=190>2^\left\langle{n\atop m} \right\rangle</tex> выражает объем части <tex>n</tex>- (мерного единичного гиперкуба, ограниченного гиперплоскостями <tex>x_1+x_2+\dots+x_n=m + 1)</tex>. Третий выражается как:и <tex>3^{m}-(m x_1+ 1)2^m x_2+ \frac{(dots+x_n=m+-1)m}</tex>.|proof=Для доказательства этого факта нам потребуется следующая теорема: {{2};Теорема|about=Об объемах сечений <tex>n</tex>-мерных гиперкубов полупространствами|statement=

и так далее. Первые три элемента могут быть записаны в форме::Пусть <tex>w \left\langle{m\atop 1}\right\rangle = {{m + 1} in \choose {0}}1^mathbb{mR}</tex>:— вектор с ненулевыми компонентами (<tex>\left\langle{m\atop 2}\right\rangle w = {{m + 1} \choose {0}}2^{m} + {{m + 1} w_1, w_2 \choose {1}}1^{mldots w_n}</tex>:), а <tex>z \left\langle{m\atop 3}\right\rangle = {{m + 1} \choose {0}}3^{m} - {{m + 1} in \choose mathbb{1}R}2^{m} + {{m _+ 1} \choose {2}}1^{m}</tex>. Тогда верно следующее равенство:

Тогда нетрудно проверить, что эта сумма продолжается именно таким образом и, следовательно, мы можем обобщить ее в "строгом виде" как::<tex>\leftmathrm{Vol}_{n}(G^n_{w,z} \langlecap I^{m\atop n}) = \right\rangle = dfrac{1}{n! \sumprod\limits_{ji=1}^{n+1}w_i} \sum\limits_{K \subseteq [n]} (-1)^{n|K|}(z-j+1} {m+1w \choose n-jcdot 1_K)^n_+1}j^{m}</tex>

*<tex>G_{w, z}^{n} :=\{x \in \mathbb{R}^{n} : (w \cdot x) \leqslant z \}</tex> — полупространство;*<tex>I^n :==Свойства===[0,1]^n</tex>;*<tex>[[Файлn] :EulerianHC1.png|200px|thumb|Свойство 4 для m = \{1,2\ldots n\}</tex>;*<tex>1_K</tex>, где <tex>K</tex> — подмножество <tex>\{1, 2\ldots n = 1. V = \}</tex>, {{---}} вектор, где значения координат с номерами, входящими в <tex>K</tex>, равны <tex>1</2]]tex>, а остальные {{---}} нули; [[Файл*Для <tex>r \in \mathbb{R}</tex> и <tex>n \in \mathbb{N}</tex> : <tex>r^n_+ :EulerianHC2.png|200px|thumb|Свойство 4 для m = 3(\max{\{r, 0\}})^n = 2</tex>. V = 1/6]]

1. Нетрудно увидеть, что каждый ряд ненулевых значений симметричен относительно своей середины, то есть::|proof=С доказательством можно ознакомиться по ссылке <texref>\left\langle{n\atop m}\right\rangle = \left\langle{n\atop (n-1) - k}\right\rangle,\ n \ge 1,\ 0 \le k \le n-1http://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>x_1+x_2+\ldots +x_n = m | m+1</tex>) {{---}} это вектор нормали к <tex>\mathrm{G}</tex>. Очевидно, что при данном значении вектора произведение <tex>\sumprod\limits_{ki=01}^{n} \left\langlew_i</tex> равно единице (вектор <tex>w_i</tex> тут {{---}} единичный вектор <tex>1_{[n]}</tex>, то есть рассматривается произведение всех его координат {{---}} единиц). Рассмотрим выражение, стоящее под знаком суммы. При итерации по подмножествам <tex>[n]</tex> равной мощности будут получаться одинаковые слагаемые, так как выражение <tex>(-1)^{|K|}(z-w \atop mcdot 1_K)^n_+</tex> зависит лишь от мощности итерируемого в сумме подмножества <tex>K</tex> {{---}}скалярное произведение <tex>w \right\rangle = 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 \ge 0, \choose j}</tex> таких одинаковых слагаемых,где <tex>j = |K|</tex>.

3. Связь чисел Эйлера I рода с числом сочетанийТогда перейдем от первоначальной формулировки теоремы к следующей::<tex>\sum\limits_mathrm{m=0Vol}^_{n }(-1)G^m n_{\left\langle1_{[n\atop ]},m}\rightcap I^{n}) = \rangledfrac{1}{n-1!}\sum\choose mlimits_{j = 0}^{m + 1} (-1)^{j}=0.{n \choose j}(m-j)^n</tex>

4. Число Положим <tex>W_n^m</tex> — фигура, образованная сечением гиперкуба <tex>\frac{[0,1}]^{n!}\left\langle{n\atop m}\right\rangle</tex> выражает объем части плоскостями <tex>\sum\limits_{i=1}^{n} x_{i} = m</tex>-мерного единичного гиперкуба, ограниченного гиперплоскостями и <tex>x_1+x_2+\dots+x_nsum\limits_{i=1}^{n} x_{i} =m+1</tex> и . :<tex>x_1+x_2+W_n^m := \{ x \in \mathbb{R} : m \leqslant x \cdot 1_{[n]} \dotsleqslant m+x_n=m-1\} \cap I^{n}</tex>;

Положим :<tex>\mathrm{Vol}_{n}(W_n^k</tex> - фигура, образованная сечением гиперкуба <tex>m) = \mathrm{Vol}_n(G_{1_{[0n]},m+1}^{n} \cap I^n) - \mathrm{Vol}_n(G_{1_{[n]},m}^{n}\cap I^n)</tex> плоскостями :<tex>= \dfrac{1}{n!}[\sum\limits_{ij=0}^{m+1}(-1)^{j}{n\choose j} x_(m+1-j)^{in} = k</tex> и <tex>- \sum\limits_{ij=0}^{m}(-1)^{j}^{n\choose j} x_(m-j)^{in} = k+1]</tex>. Будем обозначать полупространство в :<tex>= \dfrac{1}{n!}\sum\mathbblimits_{j=0}^{Rm+1}(-1)^j{n+1 \choose j}(m+1-j)^n</tex> как :<tex>G_= \dfrac{w, z1}^{n!} = \sum\limits_{x \in \mathbbj=0}^{Rm}(-1)^j{n} : w \cdot x \le z +1 \choose j}(m+1-j)^n</tex> (элемент суммы с номером <tex>j=m+1</tex>обращается в ноль):<tex>W_n^k := </tex> <tex>\dfrac{ x \in \mathbb1}{Rn!} : k </tex> <tex dpi=190>\le x left\cdot 1_langle{[n]\atop m} \le k+1 \} right\cap I^{n}rangle</tex>(вторая явная формула) }}

# Нетрудно увидеть, что каждый ряд ненулевых значений симметричен относительно своей середины, то есть:#:<texdpi=190>\mathrm{Vol}_left\langle{n\atop m}(W_n^k) \right\rangle = \mathrmleft\langle{Vol}_nn\atop (G_{1_{[n]-1) - k}\right\rangle</tex><tex>,k+1}^{n} \cap I^n) - \mathrm{Vol}_n(G_{1_{[n]}geqslant 1,\ 0 \leqslant k}^{\leqslant n} -1. \cap I^, </tex># Сумма всех значений каждого ряда равна <tex> n)! </tex>:#:<tex>= \frac{1}{n!}[\sum\limits_{jm=0}^{k+1}(-1)^{jn}</tex><tex dpi=190> \left\langle{n \choose j}(k+1-j)^{natop m} - \sumright\limits_{jrangle</tex> <tex> =0}^{k}(-1)^{j}{n !,\choose j}(k-j)^{n}]\geqslant 0, \,</tex># Связь чисел Эйлера I рода с числом сочетаний:#:<tex> = \frac{1}{n!}\sum\limits_{jm=0}^{k+1}n (-1)^j{n+1 \choose j}(k+1-j)^nm </tex>:<texdpi=190> = \frac{1}{n!}\left\langle{n\atop km}\right\rangle}</tex> <tex>{n-1\choose m}^{-1}=0.</tex> 5. # Вероятность того, что сумма <tex>n</tex> независимых равномерно распределённых в отрезке <tex>[0,1]</tex> переменных лежит между <tex>m-1</tex> и <tex>m</tex> равна <tex>\fracdfrac{1}{n!}\left\langle{n\atop m}\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 = "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> подъема:

|statement=Количество перестановок мультимножества <tex>\{1,1,2,2..\ldots n,n\}</tex> со свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex>z</tex> для любого <tex>z</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>

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

==СсылкиСм. также ==* [[Комбинаторные_объекты#.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/> ==Источники информации==