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

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

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

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

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

Перенесём транспозицию τ_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» Арнольда.)