Интересная задача с неизвестным результатом.
Модератор: модераторы
-
- Администратор сайта
- Сообщения: 7202
- Зарегистрирован: Вс, 28 дек 2003, 11:47
- Откуда: Луга
- Контактная информация:
Интересная задача с неизвестным результатом.
Пусть множество A = {1, 2, ... , n-1}. Чему равно количество подмножеств A, в которых сумма элементов кратна n?
Последний раз редактировалось PSP Сб, 22 сен 2007, 10:12, всего редактировалось 1 раз.
Ответом является
SUM ( phi(d) * 2^(n/d) ) / (2*n)
где phi() - функция Эйлера, а сумма берется по всем нечётным делителям d числа n.
Доказать это можно, например, через мультисекцию производящей функции
f(x) = (1+x)*(1+x^2)*...*(1+x^(n-1))
SUM ( phi(d) * 2^(n/d) ) / (2*n)
где phi() - функция Эйлера, а сумма берется по всем нечётным делителям d числа n.
Доказать это можно, например, через мультисекцию производящей функции
f(x) = (1+x)*(1+x^2)*...*(1+x^(n-1))
Вернуться в «Доска математических объявлений»
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 16 гостей