Комбинаторика

[Stensen]

Всем здравия. Помогите понять подход к решению задачи:
Дан набор чисел $\left\lbrace -1,-2,-3,... ,-26 \right\rbrace$. На доску выписали все возможные подмножества данного набора, в которых есть хотя бы $2 $ числа. Для каждого выписанного подмножества вычислили произведение всех чисел, принадлежащих данному подмножеству. Чему равна сумма $S$ всех этих произведений?
Автор предлагает рассмотреть выражение $\, (1-1)(1-2)(1-3) \, ... \, (1-26)$ , которое раскрыть-то не просто, тем более предугадать, что там внутри содержится искомая сумма $S$. Подскажите, в каком направлении нужно думать, чтобы до этого додуматься? Может где-то об этом почитать можно? Типовые задачи под такой метод?

[mihaild]

Для начала давайте уберем требование "хотя бы $2$ числа" и рассмотрим вообще все подмножества.
Пусть мы решили задачу для какого-то набора чисел, получили сумму $P$. Что произойдет, если к этому набору добавить число $x$ - какие у нас получатся произведения, как можно посчитать их сумму, зная $P$ и $x$?

[Stensen]

mihaild в сообщении #1544455 писал(а):

Для начала давайте уберем требование "хотя бы $2$ числа" и рассмотрим вообще все подмножества.
Пусть мы решили задачу для какого-то набора чисел, получили сумму $P$. Что произойдет, если к этому набору добавить число $x$ - какие у нас получатся произведения, как можно посчитать их сумму, зная $P$ и $x$?

Вроде, должно получится так: $S=xP+P$ ? К набору добавятся все такие же подмножества, содержащие $x$ .
Если к имеющемуся набору последовательно добавлять $x_1, x_2, ... , x_n $, и находя сумму элементов всех подмножеств, получим: $S=P(1+x_1)(1+x_2)...(1+x_n)$. Вроде так?

[mihaild]

Да, всё так. Осталось найти, чему равно $P$ для пустого множества (до того, как мы что-то добавили), и понять, как учесть условие "хотя бы $2$ числа".

[Stensen]

mihaild в сообщении #1544458 писал(а):

Да, всё так. Осталось найти, чему равно $P$ для пустого множества (до того, как мы что-то добавили), и понять, как учесть условие "хотя бы $2$ числа".

1. Не уверен, можно ли считать, что сумма произведений элементов пустого множества $P_0=0$ ?
2. Учесть условие "хотя бы $2$ числа", думаю, нужно так: $S=P_0(1+x_1)(1+x_2)...(1+x_n) - P_0(1+x_1)- P_0(1+x_2)-...- P_0(1+x_n)$ и упростить. Верно?

[mihaild]

Stensen в сообщении #1544461 писал(а):

Не уверен, можно ли считать, что сумма произведений элементов пустого множества $P_0=0$ ?

Нет конечно, какие там в точности произведения суммироваться будут?

Stensen в сообщении #1544461 писал(а):

$S=P_0(1+x_1)(1+x_2)...(1+x_n) - P_0(1+x_1)- P_0(1+x_2)-...- P_0(1+x_n)$

Нет, не так.
Во-первых, учитывать это ограничение нужно сразу на всех элементах, тут уже переходы с добавлением элементов не пройдут.
Во-вторых, вот пусть мы посчитали сумму произведений всех возможных произведений. Как из неё получить сумму произведений всех подмножеств, содержащих не менее двух элементов? Вычесть сумму произведений подмножеств, содержащих менее двух элементов. Что это за подмножества? Какие у них произведения?

[Stensen]

mihaild в сообщении #1544458 писал(а):

Осталось найти, чему равно $P$ для пустого множества (до того, как мы что-то добавили) $2$ числа".

Видимо нужно считать $P_0=1$, там нечего складывать?

mihaild в сообщении #1544463 писал(а):

Stensen в сообщении #1544461 писал(а):

Учесть условие "хотя бы $2$ числа", думаю, нужно так: $S=P_0(1+x_1)(1+x_2)...(1+x_n) - P_0(1+x_1)- P_0(1+x_2)-...- P_0(1+x_n)$ Верно?

Нет, не так.
Во-первых, учитывать это ограничение нужно сразу на всех элементах, тут уже переходы с добавлением элементов не пройдут.
Во-вторых, вот пусть мы посчитали сумму произведений всех возможных произведений. Как из неё получить сумму произведений всех подмножеств, содержащих не менее двух элементов? Вычесть сумму произведений подмножеств, содержащих менее двух элементов. Что это за подмножества? Какие у них произведения?

Если раскрыть скобки и собрать произведения одноэлементных подмножеств, т.е. одночлены первого порядка, и отдельно старшие, то получим: $P_0(1+x_1)(1+x_2)...(1+x_n)=P_0((1+x_1+x_2+...+x_n)+ S_2)$ , где: $ S_2$ - сумма произведений подмножеств из не менее 2-х чисел. Вроде так?

[mihaild]

Stensen в сообщении #1544474 писал(а):

Видимо нужно считать $P_0=1$, там нечего складывать?

Если бы было нечего складывать, то было бы $0$. Но разве нам складывать нечего - неужели у пустого множества нет ни одного подмножества?

Stensen в сообщении #1544474 писал(а):

Если раскрыть скобки и собрать произведения одноэлементных подмножеств, т.е. одночлены первого порядка, и отдельно старшие, то получим: $P_0(1+x_1)(1+x_2)...(1+x_n)=P_0((1+x_1+x_2+...+x_n)+ S_2)$ , где: $ S_2$ - сумма произведений подмножеств из не менее 2-х чисел.

Да, только тут нужно или убрать $P_0$, или сказать, что речь о подмножествах, содержащих хотя бы 2 элемента из нами добавляемых.

[TOTAL]

Stensen в сообщении #1544453 писал(а):

Автор предлагает рассмотреть выражение $\, (1-1)(1-2)(1-3) \, ... \, (1-26)$

$ (x-1)(x-2)(1-3) \, ... \, (x-26)=x^{26}+a_{25}x^{25}+a_{24}x^{24}+ \dots +a_{1}x^{1}+a_{0}x^{0}$
Автор намекает, что надо найти сумму коэффициентов справа (не всех коэффициентов)

[Stensen]

mihaild в сообщении #1544476 писал(а):

Stensen в сообщении #1544474 писал(а):

$P_0(1+x_1)(1+x_2)...(1+x_n)=P_0((1+x_1+x_2+...+x_n)+ S_2)$ , где: $ S_2$ - сумма произведений подмножеств из не менее 2-х чисел.

Нужно или убрать $P_0$, или сказать, что речь о подмножествах, содержащих хотя бы 2 элемента из нами добавляемых.

mihaild в сообщении #1544476 писал(а):

Если бы было нечего складывать, то было бы $0$. Но разве нам складывать нечего - неужели у пустого множества нет ни одного подмножества?

Подмножество пустого множества - это само пустое множество. Не понимаю, чему тогда равно $P_0$ или произведение пустого и ненулевого элемента множества?

[zykov]

Stensen в сообщении #1544494 писал(а):

Не понимаю, чему тогда равно $P_0$ или произведение пустого и ненулевого элемента множества?

Произведение по пустому множеству принимают равным 1 по соглашению.
Логика тут такая, что если перемножить два произведения по непересекающимся множествам, то результат равен произведению по множеству равному объединению этих множеств.
Отсюда и должно равнятся 1 произведение по пустому множеству.

Это по аналогии $(\forall \; x \in S : P_x) = true$, если $S$ - пустое множество.

[mihaild]

Stensen в сообщении #1544494 писал(а):

Не понимаю, чему тогда равно $P_0$ или произведение пустого и ненулевого элемента множества?

Ничего не понял, какой пустой элемент?

У нас есть пустое множество. У нас есть единственное его подмножество - пустое. Нам нужно найти произведение всех элементов пустого множества. Из свойства $\prod\limits_{x \in A \sqcup \{t\}} x = t\cdot \prod\limits_{x \in A} x$ (которым мы пользовались чтобы выписать рекурсивную формулу) оно легко находится.

[Stensen]

mihaild в сообщении #1544476 писал(а):

Stensen в сообщении #1544474 писал(а):

Видимо нужно считать $P_0=1$, там нечего складывать?

Разве нам складывать нечего - неужели у пустого множества нет ни одного подмножества? Если бы было нечего складывать, то было бы $0$.

В связи с этим и возник вопрос: "Подмножество пустого множества - само пустое множество. Не понимаю, чему тогда равно $P_0$? "
Так понимаю, что $P_0=1$ и его нужно просто убрать из равенства: $(1+x_1)(1+x_2)...(1+x_n)=((1+x_1+x_2+...+x_n)+ S_2)$. Двух элементов в нем нет и оно ничего не добавляет. Вроде так?
Посоветуйте задачник с подобными разобранными решениями или др. литературу, углубиться.