2. 5 Правила комбинаторики

При исполнении нескольких операций (размещений, перестановок, сочетаний или разбиений) следует применять дополнительные правила: суммы, произведения и включения-исключения.

Правило суммы: если комбинаторный объект t_i может быть выбран из исходного множества X “s” способами, а другой комбинаторный объект t_j из того же исходного множества X “p” способами, то выбор “либо t_i, либо t_j“ может быть осуществлен “(s+p)” способами.

Пример: сколько можно составить перестановок из n перфокарт, в которых две перфокарты ‘a’ и ‘b’ не стояли бы рядом?

Известно, что общее число перестановок равно n!.

Если ‘a’ стоит непосредственно перед ‘b’, то раcположение пары ‘a, b’ среди множества перфокарт равно (n-1). Если ‘b’ стоит непосредственно перед ‘a’, то раcположение пары 'b, a’ среди множества перфокарт также равно (n-1).

По правилу суммы общее число размещений рядом перфокарт “a” и “b” равно (n-1)+(n-1)=2(n-1).

Число перестановок оставшихся перфокарт для каждого случая, когда перфокарты ’a’ и ‘b’ стоят рядом, равно (n-2)!

По правилу суммы общее число перестановок, когда перфокарты ‘a’ и ‘b’ стоят рядом, равно 2(n-1)(n-2)! = 2(n-1)!

Следовательно, искомое число перестановок равно

n! - 2(n-1)!=(n-2)(n-1)!

Пусть даны четыре перфокарты X={a, b, c, d}. Число перестановок, когда карты ‘a’ и ‘b’ не стоят рядом, равно

(4-2)(4-1)!=12.

Множество комбинаторных объектов по этому условию есть:

{(a c b d), (a c d b), (a d b c), (a d c b), (b c a d), (b c d a), (b d a c),

(b d c a), (c a d b), (c b d a), (d a c b), (d b c a)}.

Правило произведения: если комбинаторный объект t_i может быть выбран из исходного множества “s” способами и после каждого из таких выборов комбинаторный объект t_j может быть выбран “p” способами, то выбор “t_i и t_j“ в указанном порядке может быть осуществлен “(sp)” способами.

Пример: Из m букв и n цифр следует сформировать k элементные множества, содержащие s букв и (k-s) цифр при условии sm, (k-s)n.

Число подмножеств, содержащих s букв, есть

.

Число подмножеств, содержащих (k-s) цифр есть .

Тогда число подмножеств, содержащих s букв и (k-s) цифр, по правилу умножения есть

Пусть даны четыре буквы {a, b, c, d} и три цифр {1, 2, 3}, для которых m=4 и n=3. Сформировать трехэлементные подмножества (k=3), содержащих две буквы (s=2) и одну цифру ((к-s)=1).

Число трехэлементных комбинаторных объекта, содержащих две буквы и одну цифру равно:

Множество таких объектов:

{{a, b, 1}, {a, b, 2}, {a, b, 3}, {a, c, 1}, {a, c, 2}, {a, c, 3}, {a, d, 1}, {a, d, 2}, {a, d, 3}, {b, c, 1}, {b, c, 2}, {b, c, 3}, {b, d, 1}, {b, d, 2}, {b, d, 3}, {c, d, 1}, {c, d, 2}, {c, d, 3}}.

Правило включения-исключения: если существует множество объектов Х и множество свойств Y={y₁,y₂,..y_t}, которыми могут обладать элементы x_iХ, то может быть выполнено разбиение множества Х на подмножества по числу свойств, которыми они обладают.

В этом случае разбиение множества на подмножества удовлетворяет следующему условию:

|X₀|=|X|-|X₁|+|X₂|-|X₃|...+(-1)^t|X_t|,

где |X₀| - число элементов множества Х, не обладающих ни одним свойством множества Y;

|X | - общее число элементов множества Х;

|X₁| - число элементов множества Х, обладающих только одним свойством из множества Y, т.е. y_iY;

|X₂| - число элементов множества Х, обладающих только двумя свойствами множества Y, т.е. {y_i, y_j}Y;

|X₃| - число элементов множества Х, обладающих только тремя свойствами множества Y, т.е. {y_i, y_j, y_k}Y и т.д.

Следует обратить внимание, что знак “+” ставят для подмножеств, обладающих четным числом свойств, а знак “-” - нечетным.

Пример: даны множества A, B и C. При этом xA, xB, xC, x(AB), x(AC), x(BC) или x(ABC). Найти x(ABC).

Согласно правилу включения-исключения имеем:

=|ABC|-|A|-|B|-|C|+|(AB)|+|(AC)|+|(BC)|-|ABC)|.

О ткуда |ABC|=|A|+|B|+|C|-|(AB)|-|(AC|-|BC|+ |ABC)|.

Пусть даны по четыре прописных буквы латиницы A’={A, B, C, D},

кириллицы А”={А, Б, В, Г} и греческого алфавита А’”={А, B, Γ, Δ}.

Тогда (A'А”)={A, B}, (A’А”)={A, B},

(А”А’”)={A, В, Г},

Рис. 2.1 Поиск объединения множеств (A’А”А’”)={A, B}.

Следовательно, |A’А”А’”|=|A’|+|А”|+|А’”|-|(A’А”)|-|(A’А’”)|-|(А”А’”)|+|(A’А”А’”)|= 4+4+4-2-2-3+2 =7.

Множество букв объединения четырех алфавитов есть (A’А”А’”) = {A, B, C, D, Б, Г, Δ}.

Пример: Дана колода из n индексированных перфокарт. Сколькими способами можно расположить их в колоде, чтобы ни одна перфокарта с номером i не занимала i-го места? для 1in.

Общее число перестановок перфокарт в колоде равно n!

Число перестановок, при котором i перфокарт занимают i мест есть (n-i)!

Число перестановок i перфокарт, когда i-я перфокарта занимает i-е место по правилу произведения равно:

.

И наконец, число размещений перфокарт

в колоде, при котором ни одна из перфокарт с номером i не занимает i-го места по правилу включения-исключения равно:

B₀ .

номер места
1	2	3	4
номер перфокарты
4	1	2	3
3	1	4	2
2	1	4	3
4	3	1	2
3	4	1	2
2	4	1	3
4	3	2	1
3	4	2	1
2	3	4	1

Пусть n=4.

Тогда B₀ ..

В таблице приведены возможные расположения перфокарт, когда ни одна перфокарта не занимает соответствующего места.

Пример: в студенческой группе обучается 50 человек, т.е. |X|=50. В группе 20 юношей (свойство -”быть юношей”), т.е. |X₁₁|=20, 20 студентов имеют хорошую успеваемость (свойство -”быть успевающим”), т.е. |X₁₂|=20, 20 студентов увлекаются спортом (свойство -”быть спортсменом”), т.е. |X₁₃|=20, 5 юношей имеют хорошую успеваемость (два свойства: ”быть юношей” и “быть успевающим”), т.е. |X₂₁|=|X₁₁X₁₂|=5, 10 юношей увлекаются спортом (два свойства: “быть юношей” и “быть спортсменом”), т.е. |X₂₂|=|X₁₁X₁₃|=10, 10 успевающих студентов увлекаются спортом (два свойства: “быть успевающим” и “быть спортсменом”), т.е. |X₂₃|=|X₁₂X₁₃|=10, 5 юношей имеют хорошую успеваемость и увлекаются спортом (три свойства: “ быть юношей”, “быть успевающим” и “быть спортсменом”), т.е. |X₃₁|=|X₁₁X₁₂X₁₃|=5.

Сколько девушек (X₁₁) имеют слабую успеваемость (X₁₂) и не увлекаются спортом (X₁₃) или (X₁₁X₁₂X₁₃)?

По правилу включения-исключения имеем:

|(X₁₁X₁₂X₁₃)|=|X|-|X₁₁|-|X₁₂|-|X₁₃|+|X₂₁|+|X₂₂|+|X₂₃|-|X₃₁|

|(X₁₁X₁₂X₁₃)|=50-20-20-20+5+10+10-5=10.

Следовательно, 10 девушек имеют слабую успеваемость и не увлекаются спортом.

Пример: в цехе имеется 9 свободных рабочих мест, из которых на двух могут работать только женщины, а на трех - только мужчины. Сколькими способами можно распределить трех женщин и четырех мужчин на эти рабочие места?

Е

рабочие места

м м м     ж ж

м м м м - - ж ж ж

м м м м - ж ж ж -

м м м м ж ж ж - -

- м м м м - ж ж ж

- м м м м ж ж ж -

- - м м м м ж ж ж

Рис.2.2 Распределение мужчин и женщин на

рабочие места

сли трех мужчин направить на три рабочих места, оборудованных для мужчин, без учета их квалификации, то из четырех общих рабочих мест без учета их специализации одно будет занято мужчиной. В этом случае существует три способа размещения женщин на рабочих местах без учета их квалификации и специализации рабочих мест (см. рисунок). Если двух мужчин направить на два специализированных для мужчин рабочих места, то из четырех общих рабочих мест два места будут заняты мужчинами без учета их квалификации. В этом случае существует два способа размещения женщин на рабочих местах без учета их квалификации (см. рисунок).

И наконец, если одного мужчину направить на одно специализированное для мужчин рабочее место, то из 4-х общих свободных рабочих мест три будут заняты мужчинами без учета их квалификации. В этом случае существует один способа размещения женщин на рабочих местах.

Итого существует шесть способов распределения трех женщин и четырех мужчин без учета их квалификации и специализации девяти рабочих мест.