2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Формула включений-исключения для полиномов
Сообщение11.08.2016, 15:33 
Для полинома $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 --


 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение11.08.2016, 16:42 
Аватара пользователя
Пусть целое $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).$$

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

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение11.08.2016, 17:09 
Аватара пользователя
sergei1961 в сообщении #1143383 писал(а):
А как от целых значений перейти к нецелым - это просто полином по одной переменной с бесконечным числом целых корней, этого хватает, или нет?

Да.

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение11.08.2016, 20:05 
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)$ и постоянно, вот и всё.

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение11.08.2016, 20:48 
Аватара пользователя
ewert в сообщении #1143404 писал(а):
На самом деле просто индукция по степени многочлена.

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

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение11.08.2016, 20:54 

(Оффтоп)

maxal в сообщении #1143426 писал(а):
хотя ноги растут именно оттуда.

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

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение12.08.2016, 12:12 
Где про это написано? Можно ли указать источник?

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение12.08.2016, 22:00 
Осталось сказать, что я узнал эту задачу от своего коллеги д.ф.-м.н. И.П.Половинкина (Воронежский университет).

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение04.11.2020, 23:54 
Аватара пользователя
ewert в сообщении #1143428 писал(а):
но с параметрами задачки надо бы всё же поаккуратнее

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

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение05.11.2020, 00:49 

(Оффтоп)

maxal в сообщении #1143381 писал(а):
формуле включений-выключений

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

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение05.11.2020, 02:26 
Аватара пользователя
ozheredov, видимо, спелл-чекер постарался, а я и не заметил. Исправлено.

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение05.11.2020, 10:06 
Аватара пользователя
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).$$

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

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение05.11.2020, 10:17 
Все то же самое в рабоче-крестьянских обозначениях:
$$\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.$

 
 
 
 Re: Формула включений-исключения для полиномов
Сообщение05.11.2020, 12:49 
Пардон, забыл индексы $a_i$ выше. И я понимаю, что прошло 5 лет, но...
ewert в сообщении #1143404 писал(а):
И начать лучше со случая $d=2$ и $n=2$.

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

 
 
 [ Сообщений: 19 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group