Математические байки

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

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

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

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

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

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

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

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

Ответ: n^{n-2}. У этой формулы Кэли много разных доказательств на любой вкус. Есть чисто комбинаторные способы — например, код Прюфера (см. «Введение в дискретную математику» Ландо или почти любую книгу по графам) или биективное доказательство Joyal’а (можно найти в «Доказательствах из КНИГИ» или, скажем, вот). Есть и использующие некоторую технику — например, вычисление производящей функции при помощи формулы обращения Лагранжа (см., например, «Лекции о производящих функциях» Ландо) или теорему о подсчете остовных деревьев при помощи определителя (см., например, те же «Доказательства из КНИГИ»).

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

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

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

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

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

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

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

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

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