Так, ну давайте, действительно, начнем с основных правил комбинаторики.
Основные правила
комбинаторики.
Ну, вообще,
если говорить так совершенно обще, комбинаторика – это,
конечно, наука, которая изучает различные комбинации каких-то объектов.
Разумеется, как правило, мы имеем дело с конечными множествами объектов,
и в рамках этого курса никаких бесконечностей у нас не возникнет.
Не пугайтесь.
Поэтому вот сейчас,
когда я буду формулировать основные правила комбинаторики, я буду говорить все
время о конечных множествах объектов и обозначать как-то элементы этих множеств.
Ну вот давайте, первое правило, самое простое, самое основное.
И большинству, конечно, кто хоть как-то знаком с математикой,
оно кажется абсолютно тривиальным.
Зачем такое разжевывать?
Но все-таки это нужно.
Значит, первое – это то, что называется «правило сложения».
Правило сложения.
Ну давайте, я его подробно сформулирую.
Жалко что-ли?
Значит вот, пусть у нас есть два множества объектов.
Есть множество объектов A.
A – это какое-то множество объектов.
Давайте, как водится в математике, множество обозначать фигурными скобками,
а внутри фигурных скобок указывать те объекты,
которые этому множеству принадлежат.
Вот, я перечисляю эти объекты.
Их сколько-то там n штук.
Вот так вот я обозначаю конечное множество A,
состоящее из элементов или из объектов a1, ..., a с индексом n.
То есть всего у меня n объектов в этом множестве, но,
как я уже сказал, множеств объектов у нас два.
Давайте, второе множество объектов будет обозначаться B, и оно будет состоять,
соответственно, из элементов b1, ..., b с индексом m.
То есть у нас есть два разных множества объектов.
В одном – n объектов, которые обозначены латинскими буковками a,
в другом – m (вообще говоря, другое количество, но может быть,
совпадающее) объектов, которые обозначены латинскими буковками b.
Так вот, утверждение состоит в том, что если нам хочется посчитать
количество способов вытащить либо объект из множества A,
либо объект из множества B, оба раза по одной штуке, то, естественно,
это количество способов равняется сумме количеств объектов в наших множествах.
Ну давайте, я это зафиксирую на доске.
Количество способов
выбрать один
объект из
A или один объект из B,
или один объект из B,
равно суммарному количеству
объектов в этих исходных множествах.
Ну все-таки мне кажется, что вот этот вот принцип, это правило комбинаторики
настолько тривиально, что даже человек, который изначально не был знаком с ним,
должен его понять сразу, и, конечно, никакого доказательства не требуется.
Ну представьте себе какой-нибудь совершенно простой пример.
Чтобы не было как-то вот это сухо и абстрактно, представьте себе,
что первое множество объектов (ну давайте даже с этим будем работать регулярно),
первое множество объектов – это просто множество букв русского алфавита.
А второе множество объектов – это множество цифр от 0 до 9.
Вот пример такой.
A у нас состоит из букв
русского алфавита.
Значит, товарищи, я, конечно, вот это «ё» нарисовал не для того,
чтобы поиздеваться над слушателями, а для того,
чтобы подчеркнуть, что у нас просто количество букв в русском алфавите 33.
Так, вот я здесь палочку нарисовал.
Это тоже очень полезное дело.
Давайте вот так вот модулем множества обозначать количество элементов в нем.
Это важное тоже обозначение.
Давайте введем его.
Вот это вот количество элементов в множестве A.
Количество элементов в множестве A.
Просто по определению: модуль множества – это, как говорят,
мощность этого множества, это сколько в нем элементов.
Ну то есть вот это число n в нашем случае, оно равняется, разумеется, 33, потому
что в русском алфавите, как я специально подчеркнул, все-таки 33, а не 32 буквы.
Вот, ну это так, чтобы просто народ понимал.
Вот, соответственно, опять же, в качестве примера,
как я уже сказал, давайте рассматривать множество B,
состоящее из цифр от 0 до 9 в нашей десятичной системе исчисления.
Ну тогда понятно, что количество способов выбрать одну букву, то
есть один объект из A – это выбрать одну какую-нибудь букву из русского алфавита,
или выбрать одну цифру, то есть какой-нибудь один объект из B.
Количество способов либо выбрать одну букву, либо выбрать одну цифру,
это количество способов действительно равняется 33 + 10,
и это есть 43.
Это есть 43.
Ну я надеюсь, что после этого пояснения сухие слова про какие-то множества
объектов, их мощности и так далее наполняются содержательным смыслом, и
совершенно понятно, что да, действительно, правило сложения имеет место быть.
Конечно, если мы хотим либо взять одну букву, либо взять одну цифру,
то это делается суммарным числом способов, то есть 33 + 10, а это и есть 43.
Ну, наверное, все-таки в этом месте больше разжевывать не нужно.
Дмитрий Ильинскийпреподаватель
Андрей Райгородскийпрофессор, доктор физико-математических наук
