1. Запишем перестановку, в виде строки циклов, а циклы в строке упорядочим по возрастанию их максимального элемента, который установим на первое место. Такая запись, очевидно, взаимно однозначна. Затем, сопоставим этой строке перестановку чисел в порядке их следования в строке. Например, для перестановки

получим строку

и для нее перестановку

. Теперь взаимно однозначно сопоставим перестановке набор из

чисел, в котором

-ое число набора равно числу инверсий элемента

в перестановке (количеству элементов больших

и расположенных левее). Для нашего примера это

.
i-ое число в таком наборе может быть от нуля до

. Если в исходной перестановке

циклов, то в преобразованной перестановке будет

смен максимального элемента во время чтения ее слева направо и в наборе инверсий будет ровно

нулей по индексам равным соответствующим максимумам при чтении слева направо. За пары

можно брать пары индекс-значение в наборе инверсий для ненулевых элементов. При этом индекс отсчитывается от нуля и справа. В нашем примере это:

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

место от левого элемента. Где

это число инверсий

-ого элемента. Сложность алгоритма вроде

Кстати, у Стэнли в перечислительной комбинаторике есть такое же упражнение на построение биекции, где дается указание к его решению. И там много важных комбинаторных интерпретаций перестановок (одного из самых богатых объектов перечислительной комбинаторики) и соответственно чисел Стирлинга, что обеспечивает неожиданные доказательства разных тождеств.
2. Нет идей как использовать здесь 1.
Можно переписать тождество через биномиальные коэффициенты (чтобы сделать обе части целочисленными) и далее доказывать комбинаторно, но задумка наверное в другом.