Перестановки с повторениями и полиномиальная формула

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

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

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

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

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

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

Теорема 2. .

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

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

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

Теорема 3. Число перестановок с повторениями различных 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 блоков .