Для простого p найдите число замкнутых ориентированных связных p-звенных ломаных (возможно, самопересекающихся),проходящих через все вершины данного правильного p-угольника. Ломаные, совмещающиеся поворотом, неотличимы

А можно решить эту задачу для произвольного n пользуясь мб мультпликативностью или еще как?

задан 12 Окт '15 18:12

изменен 1 Дек 17:42

%D0%9A%D0%B0%D0%B7%D0%B2%D0%B5%D1%80%D1%82%D0%B5%D0%BD%D0%BE%D1%87%D0%BA%D0%B0's gravatar image


6.7k211

10|600 символов нужно символов осталось
2

Будем различать периодические и непериодические ломаные. К первому случаю относим те, которые переходят в себя (с учётом ориентации рёбер) при некотором нетождественном повороте. Вершины ломаных удобно считать элементами поля вычетов $%\mathbb Z_p$%, где $%p > 2$% -- простое число.

Из простоты числа $%p$% следует, что периодическая ломаная будут переходить в себя при повороте на любой угол, кратный $%2\pi/p$%. Тогда она однозначно определяется числом $%a$% от $%1$% до $%p-1$%: из каждой вершины $%x$% идёт стрелка в $%x+a$% по модулю $%p$%. Таких ломаных $%p-1$% штука.

Общее число ломаных, которые можно начинать читать с вершины 0, равно $%(p-1)!$%. Вычитая из них число периодических, делим количество остальных на $%p$%, так как каждая непериодическая ломаная у нас учитывается $%p$% раз. К этому количеству добавляем $%p-1$%. Получается $%\frac{(p-1)!-(p-1)}p+p-1=\frac{(p-1)!+1}p+p-2$%. Заодно получили ещё одно доказательство теоремы Вильсона.

ссылка

отвечен 12 Окт '15 19:37

@falcao, большое спасибо!

(1 Дек 17:43) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,195
×50
×2

задан
12 Окт '15 18:12

показан
548 раз

обновлен
1 Дек 17:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru