Формула включений-исключения для полиномов

[sergei1961]

Для полинома $S(x)=x^2+px+q$ для произвольных чисел $a,b,c$ справедливо тождество

$$ S(0)=S(a)+S(b)+S(c)-S(a+b)-S(b+c)-S(c+a)+S(a+b+c). $$

Проверьте! Тот же аналог формулы вкл/искл верен и для кубического полинома. Понятно, что это общий известный факт --- дайте ссылку...

-- 11.08.2016, 16:34 --

[maxal]

Пусть целое $n\geq 0$ - фиксировано. Наша цель показать, что для полиномов $S(x)$ степени меньшей $n$, выполняется тождество:

$$(\star)\qquad\qquad \sum_{I\subset [n]} (-1)^{|I|} S\big(\sum_{i\in I} a_i\big) = 0,$$

где $[n]:=\{1,2,\dots,n\}$.

Достаточно доказать $(\star)$ для каждой степени $S(x)=x^d$, где $d<n$, и произвольных целых неотрицательных чисел $a_1,\dots,a_n$. Тогда на произвольные полиномы $S(x)$ степени меньшей $n$ утверждение распространяется по линейности, а на произвольные действительные $a_1,\dots,a_n$ в виду того, что $S(x)$ - полином.

Интерпретируя каждое $a_i$ как мощность некоторого множества $A_i$, так что все эти множества попарно не пересекаются, мы получаем, что $S(a_{i_1}+\dots+a_{i_k})=(a_{i_1}+\dots+a_{i_k})^d$ -- это количество отображений $f$ из множества $[d]$ во множество $A_{i_1}\cup \ldots \cup A_{i_k}$.

Для каждого $i\in [n]$ определим $P_i$ как свойство, что образ $f$ не пересекается с $A_i$. Далее, для $I\subset [n]$ определим $N(I)$ как количество отображений из $[d]$ в $A_1\cup\ldots\cup A_n$ обладающих свойствами $P_i$ для всех $i\in I$. Понятно, что $N(I)=S\left(\sum_{i\notin I} a_i\right)=\left(\sum_{i\notin I} a_i\right)^d$. Тогда согласно формуле включений-исключений для свойств, выражение

$$\sum_{I\subset [n]} (-1)^{|I|} S\big(\sum_{i\in I} a_i\big) = \sum_{I\subset [n]} (-1)^{|I|} N(\bar I) = \sum_{J\subset [n]} (-1)^{n-|J|} N(J)$$

даёт умноженное на $(-1)^n$ количество функций не обладающих не одним из свойств (образ таких функций имеет непустое пересечение с каждым $A_i$). При $d<n$ количество таких функций равно нулю, что доказывает тождество $(\star)$.

P.S. Можно обобщить на произвольные целые $d\geq 0$:

$$\sum_{I\subset [n]} (-1)^{|I|} \left(\sum_{i\in I} a_i\right)^d = (-1)^n d!\ [x^d]\ \prod_{i=1}^n (e^{a_ix}-1).$$

[sergei1961]

maxal - большое спасибо.
А как от целых значений перейти к нецелым - это просто полином по одной переменной с бесконечным числом целых корней, этого хватает, или нет?
Более серьёзный вопрос - не верно ли это для целых функций, которые не могут только нетривиально занулятся в целых точках, т.е. с ограничениями на порядок?

[maxal]

sergei1961 в сообщении #1143383 писал(а):

А как от целых значений перейти к нецелым - это просто полином по одной переменной с бесконечным числом целых корней, этого хватает, или нет?

Да.

[ewert]

maxal в сообщении #1143381 писал(а):

Достаточно доказать это для каждой степени $S(x)=x^d$ и произвольных целых неотрицательных чисел $a_1,\dots,a_n$.

И начать лучше со случая $d=2$ и $n=2$.

На самом деле просто индукция по степени многочлена. Фактически ведь что надо доказать?... -- что то самое выражение "включений-исключений" не зависит от аргументов. Ну так пусть $S$ -- многочлен степени $n$ и

$$F(x)=S(a_1)+\ldots+S(a_n)+S(x)-S(a_1+a_2)-\ldots-S(a_1+x)-\ldots+(-1)^{n}S(a_1+a_2+\ldots+x)$$

.
Тогда

$$F^{(k)}(x)=S^{(k)}(x)-S^{(k)}(a_1+x)-\ldots+S^{(k)}(a_n+x)+\ldots+(-1)^{n}S^{(k)}(a_1+a_2+\ldots+x)$$

(за чётностью не следил, какая разница). По индукционному предположению все производные $F$ в нуле равны нулю, вот $F(x)$ и постоянно, вот и всё.

[maxal]

ewert в сообщении #1143404 писал(а):

На самом деле просто индукция по степени многочлена.

Это-то да, но тут нет привязки к включениям-исключениям, хотя ноги растут именно оттуда.

[ewert]

(Оффтоп)

maxal в сообщении #1143426 писал(а):

хотя ноги растут именно оттуда.

это-то да, но с параметрами задачки надо бы всё же поаккуратнее

[POLO]

Где про это написано? Можно ли указать источник?

[sergei1961]

Осталось сказать, что я узнал эту задачу от своего коллеги д.ф.-м.н. И.П.Половинкина (Воронежский университет).

[maxal]

ewert в сообщении #1143428 писал(а):

но с параметрами задачки надо бы всё же поаккуратнее

Да, было очень неаккуратно. Исправил и обобщил (не прошло и пяти лет:)

[ozheredov]

(Оффтоп)

maxal в сообщении #1143381 писал(а):

формуле включений-выключений

Забавное Вы придумали для нее название ))

[maxal]

ozheredov, видимо, спелл-чекер постарался, а я и не заметил. Исправлено.

[alisa-lebovski]

maxal в сообщении #1143381 писал(а):

P.S. Можно обобщить на произвольные целые $d\geq 0$:

$$\sum_{k=0}^n (-1)^k \sum_{|I|=k} \left(\sum_{i\in I} a_i\right)^d = (-1)^n d!\ [x^d]\ \prod_{i=1}^n (e^{a_ix}-1).$$

Просьба уточнить это.

[Verkhovtsev]

Все то же самое в рабоче-крестьянских обозначениях:

$$\sum_{k=0}^n (-1)^k \sum_{|I|=k} \left(\sum_{i\in I} a_i\right)^d = (-1)^n \sum_{k_i > 0, \atop k_1+k_2+\cdots+k_n=d}\frac{(k_1+k_2+\cdots+k_n)!}{k_1!k_2!\ldots k_n!}a^{k_1}a^{k_2}\ldots a^{k_n}$$

Поскольку $k_i > 0,$ то $d = k_1+k_2+\cdots+k_n \ge n.$

[Verkhovtsev]

Пардон, забыл индексы $a_i$ выше. И я понимаю, что прошло 5 лет, но...

ewert в сообщении #1143404 писал(а):

И начать лучше со случая $d=2$ и $n=2$.

Все-таки $d=1$ и $n=2,$ а то там ненулевое получается выраженьице.