Лекция № 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,

.

Ответ: .

Дата добавления: 2014-01-03