Вопрос: какие перестановки таким образом реализуются?
Для n=1,2,3 — все возможные. Это простое упражнение — а вот картинка из книги Жиса "A Singular Mathematical Promenade":

Для n=4 же есть ровно две невозможные перестановки: та, которую Концевич показывал Жису на билете в метро, и её обратная (соответствующая зеркальному отражению картинки).

А что будет для произвольного n?
Теорема: Перестановка n элементов реализуется некоторым набором из n полиномов тогда и только тогда, когда никакие четыре точки не переставляются ни одним из двух запрещённых способов.

Из статьи Этьена Жиса "Intersecting curves
(variation on an observation of Maxim Kontsevich)" — http://perso.ens-lyon.fr/ghys/articles/intersectingcurves.pdf

Кстати, вышла эта статья в номере American Mathematical Monthly, посвящённом "евро-Дубне" — европейской летней школе-близнецу ЛШСМ, проходившей в Бремене и в Лионе.
Поэтому у этого номера бременские музыканты на обложке:
https://www.jstor.org/stable/10.4169/amer.math.monthly.120.03.232?seq=1

Доказать теорему Концевича очень просто:
Доказательство. От противного — пусть такая четвёрка полиномов существует. Сразу можно предположить, что f_1=0 (просто вычтя его из остальных).
Определение. Нормирование (valuation) v(P) многочлена P — это порядок его корня в нуле, иными словами, самая младшая степень, коэффициент при которой отличен от нуля.
Это определение очень полезно: если нормирование у многочлена чётно, то он справа и слева от нуля одного знака, а если нечётно, то разных. А ещё легко увидеть, что верно вот такое вспомогательное утверждение:
Лемма. Если |P|>|Q| в левой или правой окрестности нуля, то v(P)<=v(Q).
(Собственно, очень логично: чем выше порядок нуля, тем меньше в малой окрестности должен быть многочлен.)

Применим эту лемму: слева от нуля
|f_4|>|f_3|>|f_2|
(напомним, f_1=0), поэтому
v(f_4)<=v(f_3)<=v(f_2).
С другой стороны, справа от нуля |f_2|>|f_4|, поэтому
v(f_2)<=v(f_4),
значит, все три нормирования совпадают.

Но f_2 меняет знак при переходе через ноль, значит, его нормирование нечётное. А f_3 сохраняет, значит, его нормирование чётное. Но одно и то же число не может быть и чётным, и нечётным одновременно!

Для произвольного n — стрелка в одну сторону в теореме Жиса очевидна. А вот почему запрет на четвёрки единственно необходимый, надо смотреть.
Давайте я об этом сюжете скажу ещё буквально пару слов — и отошлю к выложенной записи лекции и к книге Жиса "A Singular Mathematical Promenade", английский текст которой, кстати, выложен в открытом доступе.

к сегодняшней лекции Этьена Жиса напомним про книгу A Singular Mathematical Promenade — английская версия доступна на архиве ( https://arxiv.org/abs/1612.06373 ), русское издание готовится к выходу

https://youtu.be/dUqJIdhICDQ

см. тж. рассказ в «математических байках», https://news.1rj.ru/str/mathtabletalks/2710 и далее

Ссылка на видео лекции, конечно, есть и на https://www.mccme.ru/dubna/lect2020/ ; кстати, видео вчерашней лекции Александра Логунова тоже уже выложено (как и его слайды) — см. https://youtu.be/wuOqN-jfie4

Да — в качестве рекламы, первый слайд лекции Логунова:

Понятно, что угол, под которым из точки X виден отрезок AB, это аргумент отношения ((X-B)/(X-A)), иными словами, мнимая часть логарифма этого отношения. А мнимая часть комплексно-дифференцируемой функции гармонична — и остаётся применить теорему о среднем.
Но красиво — такое чисто геометрическое утверждение. :)

Но давайте я вернусь к лекции и к книге Жиса.
Вообще, можно спросить, как описывать порождаемую какими-то многочленами перестановку. И тут ответ очень простой и логичный: давайте их сгруппируем сначала по производной в нуле (или по коэффициенту при x), потом внутри одной группы по коэффициенту при x^2, и так далее. Тогда (под)группы, отличающиеся в первый раз в нечётной степени, меняют свой порядок на обратный, а группы, отличающиеся в чётной, его сохраняют.

Картинка из лекции —

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