И вдогонку — брошюра ЛШСМ, заканчивающаяся как раз конструкцией подковы Смейла:
https://www.mccme.ru/free-books/dubna/ilyashenko-smale.pdf

Ну и — соответствующая глава из фильма "Хаос": https://www.chaos-math.org/ru/chaos-vi.html — вот тут показывают, как устроено символическое кодирование для неё: https://youtu.be/LktmWlabav0?t=363 (там есть русские субтитры)

Да, и более короткий ролик с подковой —
https://www.youtube.com/watch?v=SrJm6bkLuPs

По случаю прошедшего юбилея Сергея Константиновича — "байка о трёхглавом драконе".
(У меня, конечно, ещё не закончен рассказ про ренормализацию, но давайте я его чуть-чуть отложу.)

Давайте зададимся тремя вопросами.

Вопрос 1: сколько есть разных способов разложить цикл длины n в произведение (n-1) транспозиции?

Иными словами: мы расставили n статуй по стоящим вокруг площади постаментам, и только закончив работу, обнаружили, что перепутали, откуда надо было начинать. Статуя 1 стоит на постаменте 2, статуя 2 на постаменте 3, и так далее до статуи n, которая стоит на постаменте с подписью 1.

Надо их поставить на места; единственный доступный нам инструмент — "погрузчик", позволяющий поменять местами любые две статуи. Причём погрузчик нас просили вернуть как можно скорее — так что нужно обойтись минимальным числом операций.

Операций нам понадобится (n-1) — что, собственно, часть вопроса, но пока давайте в это поверим. Так вот, вопрос формулируется классическим комбинаторным образом: а сколькими способами мы сможем это сделать — поставить статуи на свои места за (n-1) применение погрузчика?

Вопрос 2: сколько есть разных деревьев с n пронумерованными от 1 до n вершинами?

Рассмотрим наши пронумерованные вершины как вершины полного графа. Тогда дерево с этими вершинами — это остовное дерево такого графа. Поэтому тот же вопрос можно переформулировать как "сколько есть остовных деревьев в полном графе на n вершинах" ?

Вопрос 3: сколько есть многочленов степени n с комплексными коэффициентами и с заданными (n-1) критическими значениями (т.е. значениями в критических точках — там, где производная обращается в 0)?

Понятно, что в такой формулировке ответом будет "бесконечность", потому что если мы сдвинем многочлен, перейдя от P(z) к P(z+a), критические значения от этого не изменятся. Поэтому можно наложить условие, что коэффициент при z^{n-1} равен 0 (как раз любой многочлен в такой можно единственным образом сдвинуть).
И ещё наложим условие, что старший коэффициент равен 1. Опять-таки, любой многочлен с данными критическими значениями к такому виду приводится — только на этот раз заменой w=bz при правильном выборе b. А если никакого условия тут не наложить, то все такие замены нам из одного решения сделают бесконечное количество — что естественно, потому что у нас неизвестных коэффициентов пока n, а условий на критические значения (n-1).

Так что окончательная формулировка третьего вопроса — сколько есть многочленов вида
z^n + a_{n-2}z^{n-2} +...+a_1 z + a_0
с заданными (n-1) критическими значениями c_1,...,c_{n-1} ?

---
Вопросы сформулированы — и давайте сначала немного посчитаем, какими будут ответы при небольших n. Проще всего это сделать для второго вопроса.

Для n=2 единственное дерево на двух вершинах это отрезок, так что ответ 1.
Для n=3 это два последовательных отрезка — но важно, какая из трёх вершин в центре, поэтому мы получаем 3 варианта (можно сказать, что полный граф на трёх вершинах это треугольник, а мы выкидываем одну из его сторон).
Для n=4 деревьев без пометок два, это три последовательных отрезка и "лапа" из трёх отрезков с общей вершиной. В первом случае пометки можно расставить 12 способами (потому что 24/2 — подписываем всеми возможными способами, а потом вспоминаем, что дерево можно перевернуть), во втором 4 (единственное, что важно, это значение в центральной вершине; ну или 24/6, потому что отрезки из центра переставляются 3!=6 способами).
Итого 12+4=16 вариантов.

Сколько существует деревьев с n вершинами? (Фрагмент — из «Задач от 5 до 15» Арнольда.)

Наконец, для n=5 есть три разных дерева без пометок:
* четыре отрезка в линию — вершины можно подписать 60=120/2 способами;
* лапа-трилистник, у которой один из выходящих отрезков продолжается ещё одним; тут вершины можно подписать тоже 60=120/2 способами;
* одна точка, из которой выходят все четыре ребра; тут есть всего 5=120/24 способов подписать вершины (единственное, что имеет значение, это номер центральной вершины).
Итого 60+60+5=125.

125 это 5^3, и это ответ при n=5. Если после этого посмотреть на 16 как на ответ при n=4, то немедленно хочется записать 16=4^2.

После чего последовательность ответов записывается как
2^0, 3^1, 4^2, 5^3,
и становится ясно, что ответом должно быть n^{n-2}.

Этот ответ носит название формулы Кэли — и давайте я опять процитирую коллег:

Ответ: n^{n-2}. У этой формулы Кэли много разных доказательств на любой вкус.

Есть чисто комбинаторные способы — например, код Прюфера (см. «Введение в дискретную математику» Ландо или почти любую книгу по графам) или биективное доказательство Joyal’а (можно найти в «Доказательствах из КНИГИ» или, скажем, вот).

Есть и использующие некоторую технику — например, вычисление производящей функции при помощи формулы обращения Лагранжа (см., например, «Лекции о производящих функциях» Ландо) или теорему о подсчете остовных деревьев при помощи определителя (см., например, те же «Доказательства из КНИГИ»).

а вот доказательство формулы Кэли для числа деревьев в… Квантике:
http://old.kvantik.com/art/files/pdf/2018-12.12-15.pdf
(К.Кохась. Как Бусенька разбирала новогоднюю ёлку)

Рассказ К.Кохася совершенно прекрасен — но мне, честно говоря, больше всего всё-таки нравится подход через матричную теорему о деревьях (Matrix Tree Formula): оказывается, что остовные деревья в любом графе можно посчитать как определитель некоторой (очень простой) матрицы. Но по этой дороге мы пройдём чуть позже — а пока давайте вернёмся к остальным вопросам.