Элементы комбинаторики (стр. 4 )

  (2.3)

Сколько разных слов можно образовать при перестановке букв слова «математика»? Здесь типы объектов – это различные буквы (число типов k=6), количество неразличимых объектов каждого из типов – это число повторений конкретной буквы. Если бы все буквы были различны, то таких слов = 10!. Количество перестановок, в которых меняются местами только k одинаковых букв, равно k! Очевидно, что такие перестановки не меняют полученного слова ⇒ при подсчете нужно разделить 10! на k!, и выполнить это для всех повторяющихся элементов. В слове «математика» буква «м» встречается 2 раза, «а» – 3 раза, «т» – 2 раза, «е» – 1 раз, «и» – 1 раз, «к» – 1 раз. Поэтому число различных слов равно .

Аналогичную формулу можно получить при подсчете вариантов разбиений.

Разбиения и числа Стирлинга

Пусть B = {B1,…,Bk} есть разбиение множества X из  n элементов на k подмножеств:  ∀i Bi ⊂ X,  ∪Bi = X,  Bi ≠ ∅,  Bi ∩ Bj = ∅  ∀i≠j. |Bi | = ni, 
n1+…+nk = n. Тогда набор (B1,…,Bk) называется упорядоченным разбиением множества X, а подмножества Bi называются блоками разбиения.

Если B1 и B2 – два разбиения X, то разбиение B1 есть измельчение разбиения B2, если каждый блок  B2 есть объединение блоков  B1. Измельчение является частичным порядком на множестве разбиений.

Если k=2, то упорядоченное разбиение множества X на 2 подмножества, имеющие соответственно n1 и n2 элементов, определяется сочетанием (без повторений!) из  n  элементов  по n1 и  из  n  по n2 , n2 = n– n1. Значит, число разбиений R(n; n1, n2) равно биномиальному коэффициенту C(n, n1)=C(n, n2):

R(n;n1,n2) = .

Пусть множество X = {1,2,3,4,5,6}. B2 – разбиение его на четные и нечетные числа: B2 ={{1,3,5},{2,4,6}}, B1 = {{1,3},{5},{2},{4,6}} – измельчение разбиения B2. Теперь предположим, что X – 6 двоечников, которые 4-й раз идут сдавать физику (для удобства они идентифицированы порядковыми номерами). Преподаватель решил поделить их пополам случайным образом – блок A1 – поставить 3, блок А2 – поставить 2. Сколько различных вариантов возможно (упорядоченные разбиения множества X на 2 блока по три)? R(6;3,3)=6!/(3!·3!)=6·5·4/(3·2)=20. Выпишем все варианты: {{1,2,3},{4,5,6}}, {{1,2,4},{3,5,6}}, {{1,2,5},{3,4,6}}, {{1,2,6},{3,4,5}}, {{1,3,4},{2,5,6}}, {{1,3,5},{2,4,6}}, {{1,3,6},{2,4,5}}, {{1,4,5},{2,3,6}}, {{1,4,6},{2,3,5}}, {{1,5,6},{2,3,4}} ⇒ 10 вариантов. Поскольку есть разница – попасть в А1 или в  А2 (разбиения упорядоченные), то еще 10 вариантов получатся, если поменять местами первый и второй блоки разбиений. Видно, что для конкретного двоечника с номером 1 вероятность попасть в А1 или в  А2  равна Ѕ.

В общем случае, число R(n; n1,n2, …,nk) упорядоченных разбиений (B1, …, Bk), для которых |Bi | = ni, равно (сравнить с формулой  2.3):

R(n; n1,n2, …,nk)=                                                        (2.4)

Число R(n, k) упорядоченных разбиений на k подмножеств вычисляется по формуле  R(n, k) =.                                                (2.5)

Пусть множество X = {1,2,3,4,5}. Определить количество упорядоченных разбиений его на 3 подмножества. Возможные варианты – множества по 1,1,3 элемента в разном порядке и множества по 1,2,2 (тоже в разном порядке). Их количество будет определяться согласно формулам (2.5) и (2.4): R(5,3) = R(5;1,1,3) + R(5;1,3,1) + R(5;3,1,1) + R(5;1,2,2)+ R(5;2,1,2)+ R(5;2,2,1)=(5!/3!)·3+(5!/(2!·2!))·3=3·20+3·30=150.

Числа  R(n; n1, n2, …, nk) называются полиномиальными коэффициентами, поскольку для ∀ a1, a2, …, ak∈R  справедливо соотношение:

(Полиномиальная теорема)

(a1+a2+ …+ak )n = (2.6)

Если рассмотренный выше набор (B1,…,Bk) рассматривать без учета порядка его блоков, то он называется неупорядоченным разбиением множества X,  или просто разбиением на k блоков.

Можно рассмотреть разбиение множества абитуриентов на несколько блоков в соответствии с количеством регистрационных столиков в приемной комиссии – все зарегистрированные за одним столиком относятся к одному блоку. Порядок безразличен ⇒ разбиение является неупорядоченным.

Число разбиений n-элементного множества на k блоков называется числом Стирлинга второго рода и обозначается S(n, k). Определяются числа Стирлинга 2 рода рекурсивно следующим образом:

S(n, k)=S(n–1,k–1)+ k·S(n–1,k)  (0<k<n)                                        (2.7)

При этом S(n,0)=0 при n>0, S(n, k)=0 при n<k, S(n, n)=1, S(0,0)=1.

Из формулы 2.7 следует удобный способ рекуррентного вычисления значений чисел Стирлинга 2 рода, который можно представить в графической форме (в виде треугольника) следующим образом:

В этом треугольнике каждое k-е в ряду число является суммой левого стоящего над ним числа с правым, умноженным на k. Тогда число Стирлинга S(n, k) находится в n–м ряду на k-м месте, если начинать счет от 0.	1	0
0	1	1
0	1	1	2
0	1	3	1	3
0	1	7	6	1	4
0	1	15	25	10	1	5

Сколькими способами можно разбить множество {a, b,c, d} на 2 блока? Порядок значения не имеет. Тогда количество таких разбиений является числом Стирлинга 2 рода S(4,2)=S(3,1)+2·S(3,2)= 1+2·(S(2,1)+2·S(2,2))=1+2·(1+2·1) = 7. Если сравнить с приведенной таблицей, увидим тот же результат. Если выписать эти разбиения, то получим: {{a},{b, c,d}}, {{b},{a, c,d}}, {{c},{a, b,d}}, {{d},{a, b,c}}; {{a, b},{c, d}}, {{a, c},{b, d}}, {{a, d},{b, c}} – 7 подмножеств.

Контрольные вопросы

Сколько разных слов можно получить, переставляя буквы в слове «осколок»? Дайте определение упорядоченного разбиения. Чем оно отличается от неупорядоченного? Имеет ли значение порядок элементов внутри блока разбиения? Какую величину характеризуют числа Стирлинга второго рода? Определите число неупорядоченных разбиений множества {1,2,3,4,5,6,7} на 4 блока двумя способами: используя формулу для R(7;4) и с помощью чисел Стирлинга 2 рода. Сравните результаты. Чему равен коэффициент при x2y3z2 в выражении (x+y+z)7? Используя полиномиальную теорему, запишите в виде многочлена выражение (3x+2y2+z3)4. Чему равен коэффициент при x2y2z3? А при y4z7? Используя полиномиальную теорему, запишите в виде многочлена выражение (2x+3y2)3. Сделайте то же самое, используя формулу бинома Ньютона. Есть ли различия в результатах? Почему? Найти коэффициенты при x17 и x18 в разложении (1+ x5+ x7) n. Принцип включения и исключения

Рассмотренные ранее формулы и алгоритмы дают способы вычисления комбинаторных чисел для некоторых распространенных комбинаторных конфигураций. Практические задачи не всегда прямо сводятся к известным комбинаторным конфигурациям. В этом случае используются различные методы сведения одних комбинаторных конфигураций к другим.

Наиболее часто комбинаторная конфигурация является объединением других, число комбинаций в которых вычислить проще. В таком случае требуется уметь вычислять число комбинаций в объединении. В простых случаях формулы для вычисления очевидны:

(комбинаторный принцип сложения ):

Пусть множества A и B могут пересекаться. Тогда количество элементов, которые можно выбрать из A или B, определяется по формуле:
|A ∪ B| = |A| + |B| – |A ∩ B|.

Доказательство:         Множество C = A∪B = (A \ B)∪ (B \ A) ∪(A∩B), причем все множества в скобках являются попарно непересекающимися. Поэтому в соответствии с утверждением 2.1 |C| = |A∪B| = |A \ B| + |B \ A| + |A∩B|.  Очевидно, что A = (A \ B) ∪ (A∩B),  B = (B \ A) ∪ (A∩B) ⇒ |A| = |A \ B| + |A∩B|,  |B| = |B \ A| + |A∩B|. Значит, |A| + |B| = (|A \ B| + |A∩B|)+(|B \ A| + |A∩B|) . Правая часть утверждения теоремы имеет вид:        
|A| + |B| – |A ∩ B| = (|A \ B| + |A∩B|)+(|B \ A| + |A∩B|) – |A ∩ B| = |A \ B| + |A∩B| + |B \ A| = |A∪B| <.

Очевидно, что рассмотренная теорема будет справедлива для произвольных множеств. Если перейти от двух множеств к большему количеству, в частности, к трем, и проиллюстрировать с помощью диаграмм Венна, то очевидным результатом явится следующая формула: 

|A ∪ B ∪ C| = |A| + |B| + |C| – |A ∩ B| – |A ∩ C| – |B ∩ C| + |A ∩ B ∩ C|, т. е. для вычисления количества элементов объединения трех множеств нужно просуммировать мощности всех этих множеств, вычесть мощности всех попарных пересечений и добавить число элементов, содержащихся в пересечении всех трех множеств.