2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Формула включений-исключения для полиномов
Сообщение11.08.2016, 15:33 


25/08/11

1074
Для полинома $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 
Модератор
Аватара пользователя


11/01/06
5660
Пусть целое $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 


25/08/11

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

 Профиль  
                  
 
 Re: Формула включений-исключения для полиномов
Сообщение11.08.2016, 17:09 
Модератор
Аватара пользователя


11/01/06
5660
sergei1961 в сообщении #1143383 писал(а):
А как от целых значений перейти к нецелым - это просто полином по одной переменной с бесконечным числом целых корней, этого хватает, или нет?

Да.

 Профиль  
                  
 
 Re: Формула включений-исключения для полиномов
Сообщение11.08.2016, 20:05 
Заслуженный участник


11/05/08
32166
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 
Модератор
Аватара пользователя


11/01/06
5660
ewert в сообщении #1143404 писал(а):
На самом деле просто индукция по степени многочлена.

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

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


11/05/08
32166

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Формула включений-исключения для полиномов
Сообщение12.08.2016, 12:12 


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

 Профиль  
                  
 
 Re: Формула включений-исключения для полиномов
Сообщение12.08.2016, 22:00 


25/08/11

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

 Профиль  
                  
 
 Re: Формула включений-исключения для полиномов
Сообщение04.11.2020, 23:54 
Модератор
Аватара пользователя


11/01/06
5660
ewert в сообщении #1143428 писал(а):
но с параметрами задачки надо бы всё же поаккуратнее

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

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


10/03/16
3870
Aeroport

(Оффтоп)

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

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

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


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

 Профиль  
                  
 
 Re: Формула включений-исключения для полиномов
Сообщение05.11.2020, 10:06 
Заслуженный участник
Аватара пользователя


05/12/09
1760
Москва
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 


30/09/20
78
Все то же самое в рабоче-крестьянских обозначениях:
$$\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 


30/09/20
78
Пардон, забыл индексы $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