Изменения

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

Числа Эйлера I и II рода

9452 байта добавлено, 01:51, 19 декабря 2013
Нет описания правки
Тогда рекуррентная формула имеет вид:
:<tex dpi = "180160">\left\langle{n\atop m}\right\rangle = (m + 1)\left\langle{n - 1\atop m}\right\rangle + (n - m)\left\langle{n - 1\atop m - 1}\right\rangle</tex>
Примем также следующие начальные значения:
:<tex dpi = "180160">\langle{n\atop m}\rangle = 0</tex>, если <tex dpi = "130">m < 0</tex> или если  Также для четных <tex dpi = "130">k</tex>::<tex dpi = "160">\left\langle{n \atop m}\right\rangle = [k = 0]</tex>, Запись [выражение] означает нотацию Айверсона, где:<tex dpi = "160"> [statement] =</tex><tex dpi = "140"> \begin{cases} 1 & \text{statement} \\ 0& \text{!statement} \end{cases}</tex>;
===Пример===
Рассмотрим все перестановки порядка <tex dpi = "130">4</tex>, в которых есть ровно 2 подъема (в квадратных скобках один или больше подъемов подряд):
:<tex dpi = "130140"> \left\langle{4\atop 2}\right\rangle = 11:
[124]3,
[13][24],
Согласно алгоритму вывода рекуррентной формулы мы можем добавить '4' в следующие позиции всех перестановок порядка <tex dpi = "130">3</tex> с двумя подъемами, не увеличив количество подъемов:
:<tex dpi = "130140">
\left\langle{3\atop 2}\right\rangle = 1:
[123] => (4)[123], [1(4)][23], [12(4)]3
Далее рассмотрим все перестановки порядка <tex dpi = "130">3</tex> с одним подъемом, причем операцией вставки <tex dpi = "130">4</tex> мы будем увеличивать количество перестановок на 1:
:<tex dpi = "130140"> \left\langle{3\atop 1}\right\rangle = 4:</tex>
:<tex dpi = "130140">[13]2 => [13(4)]2, [13][2(4)];</tex>
:<tex dpi = "130140">2[13] => [2(4)][13], 2[13(4)];</tex>
:<tex dpi = "130140">[23]1 => [23(4)]1, [23][1(4)];</tex>
:<tex dpi = "130140">3[12] => [3(4)][12], 3[12(4)];</tex>
Таким образом мы убеждаемся в верности формулы:
:<tex dpi = "160"> \left\langle{4\atop 2}\right\rangle = (2 + 1) \left\langle{3\atop 2}\right\rangle + (4 - 2)\left\langle{3\atop 1}\right\rangle = 11;</tex>
==Треугольник чисел Эйлера I рода и явная формула==
Приведем также без вывода явную формулу для вычисления чисел Эйлера I рода:
:<tex dpi = "180">\left\langle{n\atop m}\right\rangle = \sum_{k=0}^{m}[ (-1)^k {n+1\choose k} (m+1-k)^n]</tex>
|- align="center"
| style="background:white; color:black; width:50px;" |
| style="background:white; color:black; width:50px;" | '''''k m = 0'''''
| style="background:white; color:black; width:50px;" | '''''1'''''
| style="background:white; color:black; width:50px;" | '''''2'''''
Стоит отметить, что гистрограмма, построенная на значениях чисел Эйлера I рода аппроксимируется к гистограмме, построенной на биноминальных коээфициентах (оба графика, представленные '''справа''', смасштабированы; масштаб указан на гистограмме):
[[Файл:Euler_I_hist.gif|300px|thumb|right|Числа Эйлера I рода (m < 90)]][[Файл:Binomial_hist.gif|300px|thumb|right|Биномиальные коээфициенты (m < 60)]]
'''Полезные факты о числах Эйлера I рода'''
:<tex dpi = "160">\sum_{k=0}^{n} \left\langle{n\atop m}\right\rangle = n!,\ n \ge 0, \,</tex>
3. Еще одно условие равенства нулю::<tex dpi = "160">\sum_{m=0}^n (-1)^m {\left\langle{n\atop m}\right\rangle}{n-1\choose m}^{-1}=0.</tex> 
==Числа Эйлера II рода==
'''''Числа Эйлера II рода''''' — количество перестановок мультимножества от <tex dpi = "130">1</tex> до <tex dpi = "130">n</tex> вида <tex dpi = "130">\{1,1,2,2..n,n\}</tex>, обладающих свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex dpi = "130">z</tex> для любого <tex dpi = "130">z</tex>, больше, чем <tex dpi = "130">z</tex>", таких, что в каждой из них существует ровно <tex dpi = "130">m</tex> подъемов. Числа Эйлера II рода обозначаются как <tex dpi = "160"> \scriptstyle \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle </tex>
 
 
'''Пример'''
 
Рассмотрим <tex dpi = "130"> n = 3</tex>. Тогда существует 15 перестановок такого вида, среди которых одна не имеет подъемов, 8 штук имеют всего 1 подъем, и 6 перестановок имеют 2 подъема:
 
:<tex dpi = "140">112233,\; 122133,\; 112332,\; 123321,\; 133122,\; 122331. </tex>
:<tex dpi = "140"> 221133,\; 221331,\; 223311,\; 233211,\; 113322,\; 133221,\; 331122,\; 331221, </tex>
:<tex dpi = "140"> 332211,\; </tex>
 
{{Лемма
|statement=Количество перестановок мультимножества <tex dpi = "130">\{1,1,2,2..n,n\}</tex> со свойством "все элементы перестановки, встречающиеся между двумя вхождниями <tex dpi = "130">z</tex> для любого <tex dpi = "130">z</tex>, больше, чем
<tex dpi="130">z</tex>" равно двойному факториалу <tex dpi="130">(2n-1)!!</tex>.
|neat = 1
}}
 
 
===Рекурсивная формула===
Числа Эйлера II рода можно выразить рекурсивно следующим образом:
:<tex dpi = "160"> \left\langle \!\! \left\langle {n \atop m} \right\rangle \!\! \right\rangle = (2n-m-1) \left\langle \!\! \left\langle {n-1 \atop m-1} \right\rangle \!\! \right\rangle + (m+1) \left\langle \!\! \left\langle {n-1 \atop m} \right\rangle \!\! \right\rangle, </tex>
 
С начальным условием для <tex dpi = "130>n = 0</tex>:
:<tex dpi = "160"> \left\langle \!\! \left\langle {0 \atop m} \right\rangle \!\! \right\rangle = [m=0]. </tex>
 
 
 
===Треугольник чисел Эйлера II рода===
Значения чисел Эйлера II рода представлены в данном массиве. Нижнедиагональная его часть называется треугольником чисел Эйлера II рода.
 
::{| 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'''''
|- 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'''
 
|- 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'''
|- align="center"
| style="background:white; color:black;" | '''''2'''''
| style="background:#FFDEAD; color:black;" | '''1'''
| style="background:#FFDEAD; color:black;" | '''2'''
| 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;" | '''8'''
| style="background:#FFDEAD; color:black;" | '''6'''
| 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'''''
| style="background:#FFDEAD; color:black;" | '''1'''
| style="background:#FFDEAD; color:black;" | '''22'''
| style="background:#FFDEAD; color:black;" | '''58'''
| style="background:#FFDEAD; color:black;" | '''24'''
| 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;" | '''52'''
| style="background:#FFDEAD; color:black;" | '''328'''
| style="background:#FFDEAD; color:black;" | '''444'''
| style="background:#FFDEAD; color:black;" | '''120'''
| 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;" | '''114'''
| style="background:#FFDEAD; color:black;" | '''1452'''
| style="background:#FFDEAD; color:black;" | '''4400'''
| style="background:#FFDEAD; color:black;" | '''3708'''
| style="background:#FFDEAD; color:black;" | '''720'''
| 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;" | '''240'''
| style="background:#FFDEAD; color:black;" | '''5610'''
| style="background:#FFDEAD; color:black;" | '''32120'''
| style="background:#FFDEAD; color:black;" | '''58140'''
| style="background:#FFDEAD; color:black;" | '''33984'''
| style="background:#FFDEAD; color:black;" | '''5040'''
| 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;" | '''494'''
| style="background:#FFDEAD; color:black;" | '''19950'''
| style="background:#FFDEAD; color:black;" | '''195800'''
| style="background:#FFDEAD; color:black;" | '''644020'''
| style="background:#FFDEAD; color:black;" | '''785304'''
| style="background:#FFDEAD; color:black;" | '''341136'''
| style="background:#FFDEAD; color:black;" | '''40320'''
| 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;" | '''1004'''
| style="background:#FFDEAD; color:black;" | '''67260'''
| style="background:#FFDEAD; color:black;" | '''1062500'''
| style="background:#FFDEAD; color:black;" | '''5765500'''
| style="background:#FFDEAD; color:black;" | '''12440064'''
| style="background:#FFDEAD; color:black;" | '''11026296'''
| style="background:#FFDEAD; color:black;" | '''3733920'''
| style="background:#FFDEAD; color:black;" | '''362880'''
|}
==Ссылки==
VolhovM
85
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/34412»

Навигация