Решаю задачу о количестве деревьев с n вершинами. Вполне очевидно, что это идеально попадает под теорему Кэли. Проблема в том, что ее в учебном курсе не было. Следовательно, неплохо бы ее доказать. Самым простым показался способ док-ва через коды Прюфера. Материал брал
отсюда. Там есть замечательная строка: "Очевидно, кодирование Прюфера задаёт взаимно-однозначное соответствие...". Интуитивно, это действительно очевидно, но хотелось бы логически обоснованного док-ва этого очевидного факта. Идеи есть?
Заранее спасибо.
17.04.2012, 23:07 