Здравствуйте, _DAle_, Вы писали:

_DA>Хм.. http://mathworld.wolfram.com/EulersNumberTriangle.html, http://en.wikipedia.org/wiki/Eulerian_number

Что-то я не вкурил, как соотнести классы ожерелий и классы перестановкок с подъёмами.
Хотя... Наверное, можно показать, что пересаживание рыцарей не изменяет количество подъёмов. В этом случае неважно, чему равно E(n-1,k), — важно, что таких классов n-1.

Поскольку ожерелья не учитывают вращение, можем просто закрепить первого рыцаря на первой позиции. (Отсюда, кстати, следует n-1).


(1...,a,x,y,b,...z) выполняем пересаживание x,y (допустим, они не смежные)
(1...,a,y,x,b,...z)
где x,y — не смежные числа
a < x < y < b --- три подъёма
a < y > x < b --- два подъёма
То есть, класс наших ожерелий не совпадает с классом перестановок с одинаковыми подъёмами.
Что-то в лоб не вышло.