Тема: Полиномиальная формула. производящие функции
Основные вопросы, рассматриваемые на лекции:
1. Разбиения на блоки. Полиномиальная формула.
2. Перестановки с повторениями.
3. Производящие функции.
Краткое содержание лекционного материала
1. Разбиения на блоки. Полиномиальная формула. Разбиение n- множества на попарно непересекающиеся классы с известным набором
чисел элементов классов называется разбиением на блоки длины
, где 1£n1, …, nk£n, а n1+…+nk=n.
Теорема 4. Пусть
– число разбиений n-множества длины
. Тогда 
.
Доказательство. Пусть множество
разбито на блоки M1,…,Mk, такие, что |M1|=n1,…,|Mk|=nk, 1£n1,…,nk£n, n1+…+nk=n.
Элемент множества M1 можно выбрать
способами, элемент множества M2 –
способами, элемент множества M3 –
способами и т.д. Применим правило произведения:


После сокращений получим: 
.
Докажем теорему о полиномиальной формуле.
Теорема 5.
.
Доказательство. После раскрытия степени, подсчитываем число одночленов вида
. Их столько же, сколько будет разбиений множества множителей
степени
на подмножества, содержащие соответственно
и имеющие мощность
. Потому коэффициент при одночлене
равен
.
Формула, доказываемая в теореме 4, называется полиномиальной (или формулой полинома Ньютона).
Задача 1. Найти коэффициент
одночлена cx2y3z в многочлене, получаемом из степени
после раскрытия скобок и приведения подобных.
Решение. В силу теоремы 9,
.
Ответ:
.