2014 dxdy logo

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

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



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


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

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

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

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

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



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


25/08/11
1025
Для полинома $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
5147
Достаточно доказать это для каждой степени $S(x)=x^d$ и произвольных целых неотрицательных чисел $a_1,\dots,a_n$. Тогда на произвольные полиномы $S(x)$ утверждение распространяется по линейности, а на произвольные $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=\{1,2,\ldots,d\}$ во множество $A_{i_1}\cup \ldots \cup A_{i_k}$.

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

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


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

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


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

Да.

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


11/05/08
30866
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
5147
ewert в сообщении #1143404 писал(а):
На самом деле просто индукция по степени многочлена.

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

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


11/05/08
30866

(Оффтоп)

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

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

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


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

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group