14. Обобщенные перестановки и сочетания.

ТЕОРЕМА 8.58. Пусть множество S содержит n объектов k таких различных типов, что имеется n₁ неразличимых объектов типа 1, n₂ неразличимых объектов типа 2, n₃ неразличимых объектов типа 3 и, вообще, n_i неразличимых объекта типа i. Пусть P(n; n₁, n₂, n₃, ... ,n_k) – количество различных размещений элементов множества S. Тогда

P(n; n₁, n₂, n₃, ... ,n_k) = C(n,n₁)C(n – n₁,n₂)С(n – n₁ – n₂, n₃)…С(n – n₁ – n₂ –… – n_k–1 , n_k)=

n!

n₁!n₂!n₃! … n_к! ДОКАЗАТЕЛЬСТВО. Рассмотрим первое уравнение. Имеется n мест, которые можно заполнить элементами из S. Существует C(n, n₁) способов выбрать места для n₁ неразличимых объектов типа 1. Если эти места выбраны, то для заполнения останется n – n₁ мест, поэтому имеются С(n – n₁, n₂) способов выбрать места для n₂ неразличимых объектов типа 2. Если объекты типа 1 и типа 2 выбраны, то для заполнения остается n – n₁ – n₂ мест, поэтому объекты типа 3 можно разместить С(n – n₁ – n₂, n₃) способами. Аналогично, объекты типа i для 2 < i < k можно выбрать С(n – n₁ – n₂ –… – n_i–1 , n_i) способами. Используя комбинаторный принцип умножения, имеем C(n,n₁)C(n – n₁,n₂)С(n – n₁ – n₂, n₃) … С(n – n₁ – n₂ –… – n_k–1 , n_k) способов выбора различных размещений элементов из S. Чтобы показать, что

P(n; n1, n2, n3, ... ,nk)

=

n! n1!n2!n3! … nк!

воспользуемся рассуждением, которое использовалось неоднократно. Сначала предположим, что все n объектов из S различны. Если это так, то имеется n! способов разместить данные объекты. Для 1 < i < k, n_i объектов являются неразличи­мыми. Поэтому способы расположения таких объектов, при которых остальные объекты остаются на своих местах, неразличимы. Поскольку имеется n_i! таких расположений, то для нахождения количества различных размещений, когда все n_i объектов типа i являются неразличимыми, необходимо n! разделить на n_i! для каждого i. Это дает , что и требовалось доказать.

ТЕОРЕМА 8.61. Для заданного положительного числа n

(x1+x2+x3+ + xт)n = 

n! . n1!n2!n3! …nm!

x1 n1 x2 n2 x3 n3 … xm nm ,

где сумма взята по всем неотрицательным целым числам n₁,n₂, … ,n_m, таким, что n₁ + n₂ + …+ n_m = n.

ДОКАЗАТЕЛЬСТВО. Поскольку (х₁ + х₂ + … + x_m)ⁿ = (x₁ + x₂ + …+ х_т)(х₁ + х₂ +…+ х_т) … (х₁+х₂ +… + x_m), то каждое слагаемое в разложении получено путем выбора x_i из каждого сомножителя в произведении и их перемножения. Для нахождения коэффициента при x₁ ⁿ¹ x₂ ⁿ² x₃ ⁿ³ … x_m ^nm необходимо найти все воз­можные способы выбора х₁ в количестве n₁, х₂ в количестве n₂, … и х_т в количестве n_т. Но это есть не что иное, как число размещений х₁ в количестве n₁, x₂ в количестве n₂, ,..их_m в количестве n_т, которое равно

P(n; n1,n2, … ,nm) =

n! . n1!n2! … ,nm!

ТЕОРЕМА 8.64. Пусть C(n;n₁,n₂,n₃,..., n_m) – количество разбиений множества S, содержащего n элементов на т множеств S₁, S₂, S₃, ... и S_m, содержа­щих n₁, n₂, n₃, ... и n_m элементов соответственно. Тогда

C(n;n1,n2,n3,..., nm) =

P(n;n1,n2,n3,..., nm) =

n! n1!n2!n3!... nm!

ДОКАЗАТЕЛЬСТВО. Существуют C(n,n₁) способов выбора элементов для S₁. Как только эти элементы выбраны, остается n – n₁ элементов, из которых необ­ходимо выбрать n₂ элементов для S₂. Последнее можно осуществить C(n – n₁,n₂) способами. Если эти элементы выбраны, остаются n – n₁ – n₂ элементов, из ко­торых необходимо выбрать n₃ элементов для S₃. Предположим, что множества S₁, S₂, S₃, ... и S_i-1 уже выбраны, тогда для выбора n_i элементов для множества S_i остается n – n₁ – n₂ – … – n_i-1 элементов. Этот выбор можно осуществить C(n–n₁– n₂ –…– n_i-1,n_i) способами. Используя принцип умножения, получаем

C(n;n1,n2,n3,..., nm) =

C(n;n1)C(n–n1,n2)C(n–n1–n2, n3)

…

…

C(n–n1– … –nk-1, nk)

=

n! n1!n2!n3!... nm!

=

P(n;n1,n2,n3,..., nm)

Заметим, что сочетание С(n,k) = С(n;k,n – k) является частным случаем разбиения n-элементного множества на множество, содержащее k элементов (которые мы выбираем), и множество, содержащее n – k элементов (которые остаются) Важно отметить, что множество разбивается в последовательность подмножеств с заданным количеством элементов. При этом мы подсчитываем количество разбиений множества в последовательность подмножеств заданных размеров. Один из способов убедиться в этом – заметить, что С(n,k) = С(n;k,n – k) – количество способов выбрать k объектов из n объектов. Мы не включаем сюда количество способов выбрать n – k объектов и, следовательно, оставляем k объектов, что также дает разбиение множества S, содержащего n объектов, на подмножества содержащие k и n – k объектов. Для этого также существуют С(n;k,n – k) способов, поэтому существуют 2 С(n;k,n – k) способов разбиения множества S на множества, содержащие k объектов и n – k объектов. Другой способ представить себе содержание теоремы – это рассматривать ее как описание раскладывания различимых шаров в разные коробки.