85
правок
Изменения
Нет описания правки
1. Количество подъемов в перестановке <tex dpi = "130">\theta</tex> равно количеству подъемов в <tex dpi = "130">\pi</tex>. Этого можно добиться, вставляя элемент <tex dpi = "130">n</tex> на самое первое место в <tex dpi = "130">\theta</tex> (всего <tex dpi = "160">\langle{n\atop m}\rangle </tex> возможностей) или перед последним последним элементом каждого подъема(еще <tex dpi = "130">k \times </tex><tex dpi = "160"> \langle{n\atop m}\rangle </tex> раз).
2. Количество подъемов в новой перестановке на один больше предыдущего количества. Этого эффекта добиваемся вставкой элемента <tex dpi = "130">n</tex> между последним символом <tex dpi = "130">a</tex> любого подъема и <tex dpi = "130">b</tex> (если <tex dpi = "130">(a, b)</tex> - не подъем) в конце каждой перестановки или после элемента перестановки со значением <tex dpi = "130">n-1</tex>. Таких элементов, как не трудно догадаться, будет <tex dpi = "130">(n - k)</tex><tex dpi = "160">\langle{n\atop m}\rangle</tex>.
Тогда рекуррентная формула имеет вид:
<tex dpi = "180">\langle{n\atop m}\rangle = 0</tex>, если <tex dpi = "130">m < 0</tex> или если <tex dpi = "130">n = 0</tex>;
===Пример===
Рассмотрим все перестановки порядка <tex dpi = "130">4</tex>, в которых есть ровно 2 подъема (в квадратных скобках один или больше подъемов подряд):
<tex dpi = "130"> \left\langle{4\atop 2}\right\rangle = 11:
[124]3,
[13][24],
[134]2,
[14][23],
2[134],
[23][14],
[23][41],
[24][13],
3[124],
[34][12],
4[123],
</tex>
Согласно алгоритму вывода рекуррентной формулы мы можем добавить '4' в следующие позиции всех перестановок порядка <tex dpi = "130">3</tex> с двумя подъемами, не увеличив количество подъемов:
<tex dpi = "130">
\left\langle{3\atop 2}\right\rangle = 1:
[123] => (4)[123], [1(4)][23], [12(4)]3
</tex>
Далее рассмотрим все перестановки порядка <tex dpi = "130">3</tex> с одним подъемом, причем операцией вставки <tex dpi = "130">4</tex> мы будем увеличивать количество перестановок на 1:
<tex dpi = "130"> \left\langle{3\atop 1}\right\rangle = 4:</tex>
<tex dpi = "130">[13]2 => [13(4)]2, [13][2(4)];</tex>
<tex dpi = "130">2[13] => [2(4)][13], 2[13(4)];</tex>
<tex dpi = "130">[23]1 => [23(4)]1, [23][1(4)];</tex>
<tex dpi = "130">3[12] => [3(4)][12], 3[12(4)];</tex>
==Треугольник чисел Эйлера I рода и явная формула==
==Числа Эйлера II рода==
