комбинаторика или высшая алгебра?

Автор темы ушами_хлоп 
ОбъявленияПоследний пост
ОбъявлениеПремия для молодых математиков Образовательного фонда «Талант и успех»21.06.2021 00:48
ОбъявлениеHuawei - Research scientist (math)22.06.2021 11:25
ОбъявлениеЧисло «Пи» рассчитано с рекордной точностью на «бюджетном» компьютере27.08.2021 22:26
16.06.2003 11:57
ушами_хлоп
комбинаторика или высшая алгебра?
Такая вот задача: Сколько существует разных бус из n бусин, из которых k черные, а остальные белые? Бусы считаются одинаковыми, если они переходят в себя
а) при поворотах,
б) при поворотах и отражении.
16.06.2003 21:10
И то и другое :-)
Во-первых: в каком виде ожидается ответ? Замкнутая формула вряд ли существует. Например, если не будем ограничивать число бусинок одного цвета, то получится формула Маг-Магона (см, например, "Конкретную математику" ).

Так что в лучшем случае стоит рассчитывать на формулу с суммированием.

Если же цель состоит в том, чтобы подсчитать (чисто алгоритмически) число таких орбит, то это легко: рассмотрите действите соответствующей группы (Z/nZ или D_n) на множестве допустимых бус, а затем для вычисления числа орбит воспользуйтесь формулой Бернсайда.
16.06.2003 21:17
ушами_хлоп
формулой кого?
Скажите, что это за формула Бернсайда, я не знаю :( ,
насколько я понимаю, требуется просто подсчитать число (заданы конкретные значения n и k).
16.06.2003 22:14
Формула Бернсайда
утверждает, что число орбит действия группы G на множестве X равно сумме мощностей стабилизаторов элементов группы, деленной на мощность группы G, т.е. орбит только же, какова средняя мощность стабилизатора.

Вроде бы за полчаса написать программу, которая для разумно малых (не больше тысячи, например) n и k находит число орбит, вполне несложно, -- просто по этой формуле, группы-то вычетов и диэдра маленькие совсем.
19.06.2003 12:36
ушами_хлоп
что-то я торможу :(
Группа поворотов и группа отражений - это же две разные группы? Как считать орбиты по формуле Б. при действии нескольких разных групп?
19.06.2003 13:45
Так какая же все-таки задача?
У вас две разные задачи под пунктами (a) и (b) или одна? :-)

Если бусы должны выдерживать только повороты, то действует циклическая группа поворотов, если повороты, а также потороты с отражениями, то группа диэдра.
20.06.2003 09:54
Андрей М.
Рыбников, "Введение в комбинаторный анализ"
см. там главу про теорию Пойа
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти