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

.

Ответ: .

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

Перестановкой с повторениями называется размещение с повторениями по n из n элементов k-множества M (kn) со следующим дополнительным условием: различные k элементов множества M повторяются соответственно n₁,…,n_k раз, 1n₁,…,n_kn, n₁…n_kn.

Теорема 6. Число перестановок с повторениями различных k элементов n₁,…,n_k раз, 1n₁,…,n_kn, n₁…n_kn, равно .

Доказательство. Пусть M – множество номеров перестановки с повторениями, одной из указанных в условии теоремы, M₁,…,M_k – множества номеров с одинаковыми элементами, повторяющимися n₁,…,n_k раз соответственно. Тогда семейство множеств M₁,…,M_k будет разбиением множества M на k блоков. Значит, каждой перестановке с повторениями соответствует вполне определенное разбиение множества M на k блоков. Ясно, что это соответствие является биекцией. Значит, искомое число перестановок с повторениями равно числу разбиений на k блоков .

Задача 3. Найти число всех перестановок букв слова «баобаб».

Решение. n₁3 (буква «б»), n₂2 ( «а»), n₁1 («о»), значит, .

3. Производящие функции. Формальный ряд a₀a₁xa₂x²…a_kx^k… называется производящей функцией последовательности a₀,a₁,a₂,…,a_k,…

Производящая функция является или сходящимся рядом, или расходящимся рядом. Два расходящихся ряда могут быть равны как функции, но быть производящимися функциями различных последовательностей. Например, ряды 12x2²x²…2^kx^k… и 13x3²x²…3^kx^k… определяют одну и ту же функцию (равную 1 в точке x1, неопределенную в точках x1), но являются производящими функциями различных последовательностей.

Свойства производящих функций последовательностей:

сумма (разность) производящих функций последовательностей a_n и b_n равна производящей функции сумме (разности) последовательностей a_nb_n;

произведение производящих функций последовательностей a_n и b_n является производящей функцией свёртки последовательностей a_n и b_n:

c_na₀b_na₁b_n1…a_n1b₁a_nb_0.

Пример 1. Функция является производящей для последовательности

Пример 2. Функция является производящей для последовательности 1, 1, 1, …