Какую задачу решаем
Циклические раскраски с точным количеством использованных цветов (лемма Бёрнсайда). Орбиты отличаются только вращением; зеркальные отражения в этом режиме НЕ отождествляются.
Форма состоит из 3 числовых параметров: Число позиций на круге, Число цветов, Ровно использованных цветов. Все они управляют запасами, числом элементов, запретами, размером сетки или характеристиками групп. В этом варианте под названием «Подсчёт по включению–исключению — с учётом симметрии» параметры задают именно описанную постановку, а не характеристики другого подсчёта.
Как устроен подсчёт
Используется вычислительная схема: (C(k,u)/n) Σₜ Σⱼ (−1)^j C(u,j)(u−j)^gcd(n,t). Она перебирает состояния, а не отдельные огромные списки вариантов; лишь при явном учёте вращений проводится полный ограниченный перебор.
Для темы «подсчёт по включению–исключению» важно различать невозможную конфигурацию (её число равно нулю) и неверно заданные параметры (расчёт отклоняется). Ограничение «с учётом симметрии» изменяет набор допустимых состояний.
Как читать результат
Основной показатель — число способов, удовлетворяющих правилу «циклические раскраски с точным количеством использованных цветов (лемма бёрнсайда)». Дополнительные числа позволяют проверить размер всей совокупности либо вклад выбранного класса.
Контрольное условие: Орбиты отличаются только вращением; зеркальные отражения в этом режиме НЕ отождествляются. Если снять ограничение, количество допустимых вариантов обычно возрастает, но не во всех задачах равенство обязательно становится строгим.
Пример ввода
Начальные значения формы: Число позиций на круге = 7, Число цветов = 5, Ровно использованных цветов = 3. Эти параметры дают полностью воспроизводимую целочисленную задачу. Основной результат для набора по умолчанию: 2580.
После первого расчёта можно изменить один параметр и проверить, как для случая «Подсчёт по включению–исключению — с учётом симметрии» изменяется число решений. Изменять верхнюю границу, длину слова или вместимость имеет смысл отдельно от остальных величин.
Границы применимости
Орбиты отличаются только вращением; зеркальные отражения в этом режиме НЕ отождествляются. При выборе входных параметров для «Подсчёт по включению–исключению — с учётом симметрии» важно соблюдать точное значение каждого ограничения, а также различать маркированные и немаркированные объекты.
Если не выполняются условия для «Подсчёт по включению–исключению — с учётом симметрии», результат другой математической задачи нельзя применять автоматически. Для больших входов вычисление ограничено, чтобы не терять точность целочисленного подсчёта.
Где это полезно
Задачи такого вида встречаются в расписаниях, расположении элементов, дискретных моделях и учебной комбинаторике. Циклические раскраски с точным количеством использованных цветов (лемма Бёрнсайда).
Для самостоятельного разбора сохраните 3 значений формы и правило (C(k,u)/n) Σₜ Σⱼ (−1)^j C(u,j)(u−j)^gcd(n,t). Для небольших случаев ответ можно сверить ручным выписыванием всех конфигураций.
Формула расчёта
(C(k,u)/n) Σₜ Σⱼ (−1)^j C(u,j)(u−j)^gcd(n,t)
Проверенные примеры
Число позиций на круге = 7; Число цветов = 5; Ровно использованных цветов = 3
Точный подсчёт: Циклических раскрасок с точным числом цветов = 2580, Сумма неподвижных раскрасок по вращениям = 1806, Выборов используемых цветов = 10.
Число позиций на круге = 8; Число цветов = 5; Ровно использованных цветов = 3
Точный подсчёт: Циклических раскрасок с точным числом цветов = 7290, Сумма неподвижных раскрасок по вращениям = 5832, Выборов используемых цветов = 10.
Число позиций на круге = 7; Число цветов = 5; Ровно использованных цветов = 4
Точный подсчёт: Циклических раскрасок с точным числом цветов = 6000, Сумма неподвижных раскрасок по вращениям = 8400, Выборов используемых цветов = 5.
Как пользоваться онлайн-калькулятором
- Укажите числа в полях: Число позиций на круге, Число цветов, Ровно использованных цветов.
- Учитывайте правило: циклические раскраски с точным количеством использованных цветов (лемма бёрнсайда).
- Нажмите «Рассчитать» и сравните число допустимых конфигураций с контрольными показателями.