Лекция № 7. Основные вопросы, рассматриваемые на лекции:

Тема: Полиномиальная формула. производящие функции

Основные вопросы, рассматриваемые на лекции:

1. Разбиения на блоки. Полиномиальная формула.

2. Перестановки с повторениями.

3. Производящие функции.

Краткое содержание лекционного материала

1. Разбиения на блоки. Полиномиальная формула. Разбиение n- множества на попарно непересекающиеся классы с известным набором чисел элементов классов называется разбиением на блоки длины , где 1£n₁, …, n_k£n, а n₁+…+n_k=n.

Теорема 4. Пусть – число разбиений n-множества длины . Тогда .

Доказательство. Пусть множество разбито на блоки M₁,…,M_k, такие, что |M₁|=n₁,…,|M_k|=n_k, 1£n₁,…,n_k£n, n₁+…+n_k=n.

Элемент множества M₁ можно выбрать способами, элемент множества M₂ – способами, элемент множества M₃ – способами и т.д. Применим правило произведения:

После сокращений получим: .

Докажем теорему о полиномиальной формуле.

Теорема 5. .

Доказательство. После раскрытия степени, подсчитываем число одночленов вида . Их столько же, сколько будет разбиений множества множителей степени на подмножества, содержащие соответственно и имеющие мощность . Потому коэффициент при одночлене равен .

Формула, доказываемая в теореме 4, называется полиномиальной (или формулой полинома Ньютона).

Задача 1. Найти коэффициент одночлена cx²y³z в многочлене, получаемом из степени после раскрытия скобок и приведения подобных.

Решение. В силу теоремы 9,

.

Ответ: .