Интересная задача с неизвестным результатом.

Здесь вы можете сформулировать математическую задачу, с которой вам не справиться, или, наоборот, поделиться своим маленьким открытием.
Возможно, другие пользователи помогут вам или порадуются вместе с вами...

Модератор: модераторы

PSP
Администратор сайта
Сообщения: 7157
Зарегистрирован: Вс, 28 дек 2003, 11:47
Откуда: Луга
Контактная информация:

Интересная задача с неизвестным результатом.

Сообщение PSP » Чт, 07 сен 2006, 7:53

Пусть множество A = {1, 2, ... , n-1}. Чему равно количество подмножеств A, в которых сумма элементов кратна n?
Последний раз редактировалось PSP Сб, 22 сен 2007, 10:12, всего редактировалось 1 раз.

maxale
Сообщения: 8
Зарегистрирован: Чт, 07 июн 2007, 4:14

Сообщение maxale » Чт, 07 июн 2007, 5:24

Ответом является

SUM ( phi(d) * 2^(n/d) ) / (2*n)

где phi() - функция Эйлера, а сумма берется по всем нечётным делителям d числа n.

Доказать это можно, например, через мультисекцию производящей функции
f(x) = (1+x)*(1+x^2)*...*(1+x^(n-1))


Вернуться в «Доска математических объявлений»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя