Если действовать буквально так, то на каких-то "этажах" может статься, что подразбивать не понадобится; а подразбиения на уровнях одинаковой чётности, между которыми ничего не происходит, можно объединять. Скажем, если у нас
P_1=x+x^3, P_2=x+2x^3, P_3=2x,
то уровень x^2 ничего не добавляет, и порядок всех этих трёх многочленов меняется на обратный.

И если это учесть — получается, что перестановке сопоставляется (корневое плоское) дерево, у которого каждая вершина имеет либо 0 потомков, либо не меньше 2.

Только ещё есть вопрос о том, что же происходит на первом уровне (самая младшая степень, в которой отличаются многочлены, чётная или нечётная), поэтому число возможных перестановок будет вдвое больше, чем число таких деревьев.

Таких деревьев с n листьями при n=1,2,3,4 будет 1,1,3 и 11 соответственно — что как раз соответствует 1,2,6,22=24-2 реализующимся перестановкам (а при n=1 удвоения не происходит!)

А если спросить, сколько таких деревьев для n=10, то ответ — 103049 — есть ещё у Плутарха!

И вот соответствующая последовательность —
https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Hipparchus_number

Тем самым, из всех 10!=3628800 перестановок многочленами реализуется всего лишь
2*103049/10! ~ 5.67%.
Так что "незначительный" запрет на порядки четвёрок, на самом деле, довольно быстро приводит к тому, что реализуется лишь малая доля всех перестановок. Собственно — производящая функция для чисел Шредера-Гиппарха считается явно (что есть несложное упражнение на производящие функции), и имеет конечный радиус сходимости — так что растёт их количество лишь экспоненциальным, а не факториальным, образом:

(из всё той же статьи Жиса)

Да, если 5.6% кажется недостаточно малой долей, то для n=20 отношение становится примерно 1.3*10^{-6}. :)

Но — это была лишь отправная точка, как лекции, так и книги. А, наоборот, финальная точка лекции это рассказ про хордовые диаграммы, приходящие из плоских алгебраических кривых.

А именно — пусть на плоскости есть вещественная алгебраическая кривая: множество, заданное уравнением P(x,y)=0. Часто это просто хорошая кривая — скажем, прямая
ax+by+c=0
или окружность
(x-x_0)^2 + (y-y_0)^2 - r^2 =0.
Но иногда на ней бывают особые точки — как начало координат для пары пересекающихся прямых
xy=0
или как "клюв"/"касп"
y^2-x^3=0.

Вот пусть начало координат оказалось такой точкой. Точно так же, как оно окажется им для кривой, задаваемой уравнением
(y-P_1(x))*...*(y-P_n(x))=0,
где P_i — многочлены из первой части, обращающиеся в ноль в точке x=0.

Оказывается, что тогда рядом с этой особой точкой кривая разделяется на чётное число входящих в эту точку "ветвей", которые естественным образом разбиваются на пары:

А значит, возникает разбиение на пары на 2n точках, по которым кривая пересекает маленькую окружность вокруг особой точки:

Иными словами — хордовая диаграмма: