Математические байки
Вопрос 2: сколько есть разных деревьев с n пронумерованными от 1 до n вершинами? Рассмотрим наши пронумерованные вершины как вершины полного графа. Тогда дерево с этими вершинами — это остовное дерево такого графа. Поэтому тот же вопрос можно переформулировать…
---
Вопросы сформулированы — и давайте сначала немного посчитаем, какими будут ответы при небольших n. Проще всего это сделать для второго вопроса.
Вопросы сформулированы — и давайте сначала немного посчитаем, какими будут ответы при небольших n. Проще всего это сделать для второго вопроса.
Для n=2 единственное дерево на двух вершинах это отрезок, так что ответ 1.
Для n=3 это два последовательных отрезка — но важно, какая из трёх вершин в центре, поэтому мы получаем 3 варианта (можно сказать, что полный граф на трёх вершинах это треугольник, а мы выкидываем одну из его сторон).
Для n=4 деревьев без пометок два, это три последовательных отрезка и "лапа" из трёх отрезков с общей вершиной. В первом случае пометки можно расставить 12 способами (потому что 24/2 — подписываем всеми возможными способами, а потом вспоминаем, что дерево можно перевернуть), во втором 4 (единственное, что важно, это значение в центральной вершине; ну или 24/6, потому что отрезки из центра переставляются 3!=6 способами).
Итого 12+4=16 вариантов.
Для n=3 это два последовательных отрезка — но важно, какая из трёх вершин в центре, поэтому мы получаем 3 варианта (можно сказать, что полный граф на трёх вершинах это треугольник, а мы выкидываем одну из его сторон).
Для n=4 деревьев без пометок два, это три последовательных отрезка и "лапа" из трёх отрезков с общей вершиной. В первом случае пометки можно расставить 12 способами (потому что 24/2 — подписываем всеми возможными способами, а потом вспоминаем, что дерево можно перевернуть), во втором 4 (единственное, что важно, это значение в центральной вершине; ну или 24/6, потому что отрезки из центра переставляются 3!=6 способами).
Итого 12+4=16 вариантов.
Forwarded from Непрерывное математическое образование
Сколько существует деревьев с n вершинами? (Фрагмент — из «Задач от 5 до 15» Арнольда.)
Наконец, для n=5 есть три разных дерева без пометок:
* четыре отрезка в линию — вершины можно подписать 60=120/2 способами;
* лапа-трилистник, у которой один из выходящих отрезков продолжается ещё одним; тут вершины можно подписать тоже 60=120/2 способами;
* одна точка, из которой выходят все четыре ребра; тут есть всего 5=120/24 способов подписать вершины (единственное, что имеет значение, это номер центральной вершины).
Итого 60+60+5=125.
* четыре отрезка в линию — вершины можно подписать 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}.
2^0, 3^1, 4^2, 5^3,
и становится ясно, что ответом должно быть n^{n-2}.
Этот ответ носит название формулы Кэли — и давайте я опять процитирую коллег:
Forwarded from Непрерывное математическое образование
Ответ: n^{n-2}. У этой формулы Кэли много разных доказательств на любой вкус.
Есть чисто комбинаторные способы — например, код Прюфера (см. «Введение в дискретную математику» Ландо или почти любую книгу по графам) или биективное доказательство Joyal’а (можно найти в «Доказательствах из КНИГИ» или, скажем, вот).
Есть и использующие некоторую технику — например, вычисление производящей функции при помощи формулы обращения Лагранжа (см., например, «Лекции о производящих функциях» Ландо) или теорему о подсчете остовных деревьев при помощи определителя (см., например, те же «Доказательства из КНИГИ»).
Есть чисто комбинаторные способы — например, код Прюфера (см. «Введение в дискретную математику» Ландо или почти любую книгу по графам) или биективное доказательство Joyal’а (можно найти в «Доказательствах из КНИГИ» или, скажем, вот).
Есть и использующие некоторую технику — например, вычисление производящей функции при помощи формулы обращения Лагранжа (см., например, «Лекции о производящих функциях» Ландо) или теорему о подсчете остовных деревьев при помощи определителя (см., например, те же «Доказательства из КНИГИ»).
Peter Cameron's Blog
Joyal’s proof
One of my favourite proofs is Joyal’s proof of Cayley’s Theorem on trees. Today at the Cochin conference on graph theory and combinatorics, in response to a question from Brendan McKay,…
Forwarded from Непрерывное математическое образование
а вот доказательство формулы Кэли для числа деревьев в… Квантике:
http://old.kvantik.com/art/files/pdf/2018-12.12-15.pdf
(К.Кохась. Как Бусенька разбирала новогоднюю ёлку)
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.
(123...n)
(то есть 1 переходит в 2, 2 в 3,..., n в 1).
При n=2:
(12) = (12), вариант всего 1.
При n=3 не очень сложно проверить, что первой можно взять любую из трёх транспозиций, а вторая определяется однозначно:
(123)=(13)(12)=(23)(13)=(12)(23).
(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, как раз как нам и нужно.
f=(23), а g=(13),
то при нахождении
fg(1)=f(g(1))
мы сначала находим g(1)=3, а потом f(g(1))=f(3)=2, как раз как нам и нужно.
При 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.
(12)(1234)=(234).
И его, как мы уже знаем, можно представить в виде произведения соседних 3 способами.
А если τ_1=(13) или τ_1=(24), то произведение "разрезает" цикл в две транспозиции,
(13)(1234)=(12)(34)
и тут вариантов 2 — в каком порядке их перемножать.
Итого способов:
4*3+2*2=16.