Материал: erovenko_va_osnovy_vysshei_matematiki_dlia_filologov

Рассмотрим пример, иллюстрирующий комбинаторный принцип умножения.

Пример. Из города A в город B ведет n путей, а из города B в город C ведет m путей. Каково число различных путей, которыми можно совер-

шить путешествие из города A в город C через город B?

Выбрав один из n возможных путей из A â B, дальше можно продолжить путешествие m способами, поэтому общее число различных путей из

города A в город C равно n m.

Комбинаторный принцип умножения. Если множество A содержит n различных элементов, т. е. A = {ai : i =1, 2, …, n}, а множество B — m различных элементов, т. е. B = {bj : j =1, 2, …, m}, то тогда множество C, составленное из всех возможных пар, т. е. C = {(ai, bj) : i = = 1, 2, …, n; j =1, 2, …, m}, содержит n m элементов.

Доказательство. Покажем, что множество C можно разбить на непересекающиеся подмножества вида:

C1 = {(a1, bj): j = 1, 2, …, m}, C2 = {(a2, bj): j = 1, 2, …, m}, …….…………………………

Ci = {(ai, bj): j = 1, 2, …, m},

……….………………………

Cn = {(an, bj): j = 1, 2, …, m}.

Заметим, что C1 C2 = , поскольку подмножество C1 состоит из пар, содержащих a1, а подмножество C2 — только из пар, содержащих a2. Àíà-

логично показывается, что Ci Ck = ïðè i k.

Убедимся в том, что множество C является объединением попарно непересекающихся множеств Ci, i = 1, 2, …, n, ò. å. C = C1 C2 … Cn. Действительно, пусть (ai, bj) — любая возможная пара, тогда она по определению принадлежит множеству C, ò. å. (ai, bj) Ñ, íî òàê êàê ïàðà (ai, bj) Ñi,

òî (ai, bj) C1 C2 … Cn.

Поскольку каждое подмножество Ci , i =1, 2, …, n, содержит m элементов, то в силу комбинаторного принципа сложения число элементов в их

объединении равно n m, что завершает доказательство.

Замечание. Если некоторый объект «A» можно выбрать n способами, а другой объект «B» можно независимо от выбора «A» выбрать m способами, то согласно комбинаторному принципу умножения объект «A и B» можно выбрать n m способами.

Поясним сказанное на следующем примере.

Пример. Рассмотрим, сколькими способами можно выбрать гласную и согласную буквы из слова ПРОЦЕНТ.

77

Гласную букву можно выбрать двумя способами (О или Е), а согласную — пятью способами (П, Р, Ц, Н или Т). Следовательно, согласно комбинаторному принципу умножения и в силу сделанного замечания глас-

ную и согласную буквы можно выбрать 2 ! ! # способами. Комбинаторный принцип умножения по индукции можно распро-

странить на любое число множеств. В частности, если требуется выполнить одно за другим k действий и первое действие можно выполнить n1 способами, второе — n2 способами и так далее до k-ãî действия, которое можно выполнить nk способами, то все k действий вместе могут быть

выполнены n1 n2 … nk способами.

Принцип умножения достаточно очевиден, хотя и не в такой степени, как принцип сложения. «Складывать или умножать — вот в чем вопрос». В такой

«гамлетовской ситуации» иногда оказываются многие студенты, изучающие комбинаторику. Комбинаторный принцип умножения можно объяснить на арифметических задачах следующего типа: «сколько всего листов в 5 стопках тетрадей, если в каждой стопке по 20 тетрадей, а в каждой тетради по 12 листов?». Без упоминания комбинаторики или индукции школьник даст правильный ответ 5 20 12 = 1200 листов. Никто ведь не станет подсчи- тывать число листов, например, так: «есть 5 стоп, да в каждой по 20 тетрадей, да еще в каждой по 12 листов — итого 5 + 20 + 12 = 37 листов».

Рассмотрим пример еще одной задачи, при решении которой используются оба принципа комбинаторики.

Пример. Рассмотрим, сколькими способами студенту филфака можно выбрать две книги по разным наукам, когда на полке находятся 15 книг по философии, 10 книг по информатике и 5 книг по «математике для гума-

нитариев».

Если выбирать книгу по философии и книгу по информатике, то существует 15 вариантов выбора книги по философии и 10 вариантов выбора книги по информатике, поэтому по комбинаторному принципу умножения для этого выбора существует 15 10 = 150 возможностей. Если выбирать книгу по философии и книгу по «математике для гуманитариев», то имеется 15 вариантов выбора книги по философии и 5 — книги по «математике для гуманитариев», поэтому по комбинаторному принципу умножения для указанного выбора имеется 15 5 = 75 возможностей. Если выбирается книга по информатике и книга по «математике для гуманитариев», то существуют 10 способов выбора книги по информатике и 5 — книги по «математике для гуманитариев», поэтому по комбинаторному принципу умножения для такого выбора существует 10 5 = 50 возможностей. Наконец, поскольку указанных три выбора разных пар книг отличаются друг от друга, то согласно

комбинаторному принципу сложения всего существует 150 + 75 + 50 = 275 способов выбора двух книг.

78

Âзаключение этого раздела необходимо сказать еще о том, что в связи

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

Вопросы для самоконтроля

1. Верно ли, что если пересечение множества A, состоящего из n разных элементов, и множества B, состоящего из m разных элементов, не пусто, т. е. A B , то тогда множество A B содержит меньше чем n + m элементов?

2.Верно ли, что если в библиотеке имеются отдельные издания разных лет пьес А. П. Чехова: «Дядя Ваня» — 5 экземпляров, «Три сестры» — 4 экземпляра, «Чайка» — 3 экземпляра, то выбор по одному экземпляру каждой из этих пьес можно сделать 60 способами?

3.Верно ли, что если в магазине одежды продается 5 разных рубашек, 4 разных галстука и 3 разных пар носков нужного размера, то в подарок можно купить два предмета с разными названиями 47 способами?

2.2. КОМБИНАТОРИКА: ВЫБОР БЕЗ ПОВТОРЕНИЙ

Характерной чертой математического анализа комбинаторных задач является абстрагирование, т. е. отвлечение от конкретных черт в

целях выявления глубинного содержания, общего для задач, внешне отличающихся друг от друга. Пользуясь своим мозгом, как изначально данным, математик, психолог и лингвист могли не интересоваться комбинаторными основами его работы, тем не менее, как сказал академик А. Н. Колмогоров в работе «Комбинаторные основания теории информации и исчисления вероятностей» (Успехи математических наук. М., 1983), «искусственный интеллект машин должен быть создан человеком, и человеку приходится погрузиться в неизбежную при этом комбинаторную математику».

Для построения соответствующих математических моделей комбинаторных задач будем использовать математический аппарат теории множеств. Если множество состоит из элементов a, b è c, то нам безразличен порядок, в котором указаны элементы, например:

{a, b, c} = {b, a, c} = {c, b, a}.

79

Но есть задачи, в которых важен порядок следования элементов. При этом указывается, какой элемент считается первым, какой — вторым, какой — третьим и т. д.

Порядок в множестве M из n элементов — это нумерация его эле-

ментов первыми n натуральными числами, т. е. отображение множества M на множество {1, 2, …, n}.

Например, 33 буквы русского алфавита принято располагать в таком порядке:

À, Á, Â, Ã, Ä, Å, ¨, Æ, Ç, È, É, Ê, Ë, Ì, Î, Ï, Ð, Ñ, Ò, Ó, Ô, Õ, Ö, ×, Ø, Ù, Ú, Ü, Ý, Þ, ß.

При таком порядке расположения буква А является первой, буква Б — второй, буква В — третьей и т. д., вплоть до последней тридцать третьей буквы Я. Но можно те же буквы расположить, например, в обратном порядке, тогда буква Я будет считаться первой, буква Ю — второй и т. д., вплоть до последней тридцать третьей буквы А.

Множество вместе с заданным в нем порядком расположения его

элементов называют упорядоченным множеством.

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

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

(a, b, c), (b, a, c), (c, b, a).

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

(À, Á), (Á, À).

Три буквы А, Б и В можно расположить в виде последовательности уже шестью способами. Разумеется, когда мы говорим о последовательности, то имеем в виду упорядоченное множество элементов, так что перестановки элементов не допускаются. Например, АБ и БА — это разные последовательности. К каждой последовательности вида АБ и БА можно подставить букву В тремя различными способами: поставить ее спереди, между буквами или сзади. Тогда из АБ получим: ВАБ, АВБ, АБВ, а из БА получим: ВБА, БВА и БАВ. Все получившиеся последовательности разные и их можно записать в виде следующих упорядоченных множеств:

(À, Á, Â), (À, Â, Á), (Á, À, Â), (Á, Â, À), (Â, À, Á), (Â, Á, À).

Нередко подсчет вариантов облегчают графы. Так называют геометрические фигуры, состоящие из точек, называемых вершинами, и линий,

80

их соединяющих, называемых ребрами графа. С помощью вершин изображают элементы некоторого множества, а с помощью ребер — определенные связи между этими элементами. Теория графов дает простой, доступный и мощный инструмент для построения моделей и решения задач упорядочения объектов. Основателем теории графов считается Леонард Эйлер, который решил познавательную и развлекательную задачу о кенигсбергских мостах, заключающуюся в определении маршрута обхода 4 частей суши по 7 мостам с возвратом в исходный пункт без повторений проходов по каждому мосту.

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

Пример. Антон, Борис и Владимир купили 3 билета на 1-å, 2-å è 3-е места первого ряда центрального сектора на футбольный матч. Рас-

смотрим, сколькими способами они могут занять имеющиеся места.

На 1-е место может сесть любой из трех друзей, т. е. имеется 3 варианта их рассадки, на 2-е место может сесть любой из двух оставшихся, т. е. на каждый из предыдущих вариантов приходится еще 2 варианта, на 3-е место садится последний, т. е. это единственный оставшийся человек. Следовательно, по комбинаторному признаку умножения трех друзей можно

рассадить 3 2 1 = 6 способами. Изобразим эти варианты с помощью дерева (рис. 2.1), помещая в вершины графа (круги) первые буквы имен трех друзей А, Б и В.

81