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): оказывается, что остовные деревья в любом графе можно посчитать как определитель некоторой (очень простой) матрицы. Но по этой дороге мы пройдём чуть позже — а пока давайте вернёмся к остальным вопросам.

Следующий на очереди — вопрос 1. Опять-таки, давайте при небольших n посчитаем, сколькими способами цикл длины n можно разложить в произведение (n-1) транспозиции. Цикл у нас
(123...n)
(то есть 1 переходит в 2, 2 в 3,..., n в 1).
При n=2:
(12) = (12), вариант всего 1.

При n=3 не очень сложно проверить, что первой можно взять любую из трёх транспозиций, а вторая определяется однозначно:
(123)=(13)(12)=(23)(13)=(12)(23).

На всякий случай, я напомню: перестановки это отображения, поэтому при их умножении к элементам они применяются справа налево; то есть если
f=(23), а g=(13),
то при нахождении
fg(1)=f(g(1))
мы сначала находим g(1)=3, а потом f(g(1))=f(3)=2, как раз как нам и нужно.

Итак, при n=3 у нас есть 3 способа.

При n=4 перебор проще всего организовать так. Запишем, что (1234) это произведение 3 транспозиций τ_1, τ_2, τ_3:

Перенесём транспозицию τ_1 в левую часть (умножив на неё слева обе части равенства):

После этого для каждого варианта τ_1 у нас будет вопрос, "сколькими способами произведение в левой части можно разбить в произведение двух транспозиций". И тут количество будет зависеть от τ_1.

Если τ_1 переставляет два соседних по циклу числа, например, τ_1=(12), то в левой части мы увидим цикл длины 3:
(12)(1234)=(234).
И его, как мы уже знаем, можно представить в виде произведения соседних 3 способами.
А если τ_1=(13) или τ_1=(24), то произведение "разрезает" цикл в две транспозиции,
(13)(1234)=(12)(34)
и тут вариантов 2 — в каком порядке их перемножать.
Итого способов:
4*3+2*2=16.

1,3,16 — что-то напоминает, не правда ли?

Посмотрим теперь на третий вопрос, опять же, посчитав при небольших n.
Когда n=2, мы смотрим на квадратный трёхчлен
P(z)=z^2+a_0
с заданным критическим значением c. Такой трёхчлен единственен: a_0=c.

Когда n=3, мы смотрим на кубический многочлен
P(z)=z^3+pz+q
(я обозначу p=a_1 и q=a_0, чтобы формулы легче читались).

Его критические точки это корни уравнения P'(z)=0, т. е.
3z^2+p=0.
То есть это