Примеры простейших комбинаторных задач

Декартово произведение множеств.

Пусть задано множество Х и пусть х и у – элементы этого множества. Назовем (х;у) упорядоченной парой, а х и у – компонентами этой пары. Пары (х₁;у₁) и (х₂;у₂) считаются совпадающими, если х₁=х₂ и у₁=у₂. Поэтому, если х≠у, то пары (х;у) и (у;х) различны.

Пример. Из элементов множества составим все упорядоченные пары: (а;а), (а;б), (а;в), (б;а), (б;б), (б;в), (в;а), (в;б), (в;в).

Но можно брать компоненты упорядоченной пары из различных множеств:

Пример. Пусть даны множества и . Составим пары так, чтобы первая компонента принадлежала множеству Х, а вторая множеству У: (а;4), (а;5), (б;4), (б;5), (в;4), (в;5), (с;4), (с;5).

Декартовым произведением множеств Х и У называют множество , элементами которого являются все пары (х;у) такие, что . Т.е. .

Если Х=У, то множество . Полагают, что для любого множества Х выполняется Х ×Ø=Ø× Х= Ø.

Декартово произведение не обладает ни свойством коммутативности, ни свойством ассоциативности, т.е. 1) если Х≠У, то Х×У≠У×Х, 2) если ни одно из множеств Х, У, Z не пусто, то Х×(У×Z)≠(X×Y)×Z.

Справедливы равенства:

а) А×(В С)=(А×В) (А×С),

б) А×(В С)=(А×В) (А×С),

в) А×(В\С)=(А×В)\ (А×С).

Кортежи.

Пусть даны множества Х₁, Х₂,…Х_n. Возьмем какой-нибудьэлемент а₁ Х₁, а₂ Х₂,..., а_n Х_n. Выбранные элементы расположим по порядку: (а₁, а₂,...а_n). Мы получаем упорядоченную n-ку элементов, выбранных из множеств Х₁, Х₂,…Х_n. Вместо слов “упорядоченная n- ка ” говорят короче – «кортеж» (французское слово, означает торжественное шествие). Число n называют длиной кортежа, элементы а₁, а₂,...а_n - его компонентами.

Множества Х₁, Х₂,…Х_n могут иметь общие элементы или даже совпадать друг с другом. Например, слово «магазин» - кортеж длины 7, составленный из элементов множества Х={а, б, в, г, д, …,ю, я}, при этом входят не все буквы множества, а лишь часть.

Можно составлять и кортежи, компонентами которых являются множества: ({ а;в }, { с;d }, { t;f }).

Два кортежа (а₁, а₂,...а_n) и (в₁, в₂,...в_m) называют равными, если они имеют одинаковую длину, т.е. n=m, и каждая компонента первого кортежа равна компоненте второго кортежа с тем же номером, т.е. а₁=в₁, а₂=в₂, …, a_n=b_m.

Например, кортеж (а, в, с)=(а, в, с)≠(в, а, с)

Пусть заданы n множеств Х₁, Х₂,…Х_n (множества могут иметь общие элементы). Из элементов этих множеств образуем кортежи длины n, первая компонента которых принадлежит множеству Х₁, вторая – множеству Х₂, …, n- я – множеству Х_n. Множество таких кортежей называют декартовым произведением множеств Х₁, Х₂,…Х_n и обозначают Х₁×Х₂×…×Х_n.

Например, декартово произведение множеств Х₁={1;2}, Х₂={3;4}, Х₃={5;6;7} имеет вид: Х₁×Х₂×Х₃={(1;3;5), (1;3;6), (1;3;7), (1;4;5), (1;4;6), (1;4;7), (2;3;5), (2;3;6), (2;3;7), (2;4;5), (2;4;6), (2;4;7)}.

Примеры простейших комбинаторных задач

На практике часто приходится выбирать из некоторого множества объектов его подмножества, располагать элементы какого-то множества в том или ином порядке и т.д. Мастеру приходится распределять виды работ между рабочими, офицеру – выбирать наряд из солдат взвода, шахматисту - из нескольких ходов выбирать лучший. Т.к. в этих задачах речь идет о тех или иных комбинациях работ, солдат, ходов и т.д., их называют комбинаторными.

Задача 1. В классе 30 учащихся. Сколькими способами могут быть выбраны староста и его заместитель, если каждый из учащихся может быть избран на одну из этих должностей.

Решение. Существует 30 способов выбора старосты, значит его заместителем может стать каждый из оставшихся 29 человек. Любой из 30 способов выбора старосты может осуществляться вместе с любым из 29 способов выбора заместителя старосты. Значит существует 30^.29=870 способов выбора старосты и его заместителя.

Задача 2. Для дежурства в классе в течение недели (кроме воскресения) выделены 6 учащихся. Сколькими способами можно установить очередность дежурств, если каждый учащийся дежурит один раз?

Решение. В понедельник может дежурить любой их выделенных 6 человек. Во вторник может дежурить каждый из еще не дежуривших 5 учащихся. Следовательно, расписание на 1-й и 2-й день можно составить 6^.5=30 способами. К среде остаются 4 человека, которые еще не дежурили, и поэтому на среду дежурного можно назначить 4-мя способами. Каждый из этих способов можно комбинировать с любым из 30 способов выбора дежурных на понедельник и вторник. Т.о. существует 6^.5^.4=120 способов установления дежурств на первые три дня. В четверг может дежурить любой из трех оставшихся, в пятницу – из двух, в субботу – последний. Ясно, что число способов, которыми можно установить очередность дежурства, равна 6^.5^.4^.3^.2^.1=720.

Задача 3. Для проведенияэкзамена создается комиссия из двух преподавателей. Сколько различных комиссий можно составить из пяти преподавателей?

Решение. Обозначим для удобства преподавателей буквами А, В, С, Д, Е. Нетрудно выписать все возможные варианты для состава комиссии:

АВ, АС, АД, АЕ

ВС, ВД, ВЕ

СД, СЕ

ДЕ

Т.о., видно, что число различных комиссий равно 10. Но если бы речь шла, допустим, о семи преподавателях и выбирать их надо было бы из 14, то таким способом (перебором) задачу решить было бы трудно (3432 комиссий).

Итак, что же общего в этих задачах и чем они отличаются?

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

В задаче 1 – множество всех учащихся класса, т.е. множество, состоящее из 30 элементов, нужно было найти число всех различных подмножеств этого множества, состоящих их 2-х элементов.

В задаче 2 рассматривалось шестиэлементное множество дежурных и определялось число шестиэлементных подмножеств этого множества, отличающихся друг от друга только порядком следования элементов.

В задаче 3 из 5-элементного множества всех преподавателей выделялись различные двухэлементные подмножества и подсчитывалось их число.

2. Очень важное различие: в задачах 1 и 2 и в задаче 3 по разному понимаются слова «различные множества». В задаче 3 порядок элементов подмножества не принимается во внимание (комиссия Иванов, Петров не отличается от комиссии Петров, Иванов).

В задаче 1, напротив, подмножества, отличающиеся друг от друга порядком элементов, считались различными. В задаче 2 различными считались подмножества, если они отличались друг от друга только порядком следования элементов.

Если подмножества, отличающиеся только порядком следования элементов считаются различными, то говорят об упорядоченных подмножествах. В противном случае прилагательное «упорядоченные» опускают.

Например, у множества { а, b, с, d } существует 4 трехэлементных подмножества:

abc abd acd bcd и 24 трехэлементных упорядоченных подмножеств:

acb adb adc bdc

bac bad cad cbd

bca bda cda cdb

cab dab dac dbc

cba dba dca dcb

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