Методические рекомендации для проведения курса «Комбинаторика» (стр. 2 )

  Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 г работу “Об искусстве комбинаторики”, в которой впервые появляется сам термин “комбинаторный”. Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. За последние годы комбинаторика переживает период бурного развития, связанного с общим повышением интереса к проблемам дискретной математики. Комбинаторные методы используются для решения транспортных задач, задач по составлению расписаний, в биологии – для изучения состава белков и ДНК, в механике сложных сооружений и т. д.

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

§ 2. Комбинаторные принципы сложения и умножения.

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

  Так как комбинаторика связана с теорией конечных множеств, то такие понятия данной теории, как подмножество, объединение множеств, пересечение множеств используются при решении комбинаторных задач.

  Правило суммы.

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

Правило суммы на языке множеств: «Если множество A состоит из m элементов, а множество B – из  n элементов, причем эти множества не имеют общих элементов, то их объединение A ∪ B, т. е. совокупность всех элементов из A и B, содержит m + n элементов».

  Правило можно сформулировать иначе: «Если некоторый объект A можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор «либо A, либо B» можно осуществить  m + n способами».

С помощью правила суммы можно считать и элементы в A ∪ B, когда A и B имеют общие элементы. Если обозначить через пересечение множеств A ∩ B множество всех общих элементов у множеств A и B, то

n (A ∪ B) = n (A) + n (B) – n (A ∩ B),

где  n (A) – число элементов во множестве A, n (B) – число элементов во множестве B, n (А ∩ B) – число общих элементов у множеств A и B. Это утверждение - частный случай формулы перекрытий (включений и исключений).

  Аналогично рассматривается вопрос о числе элементов в объединении нескольких конечных множеств. Если эти множества  A1,…,Am попарно не пересекаются (т. е. если Ai ∩ Ag = Ш, при i ≠ g), то справедливо равенство:

n(A1 ∪ A2 ∪ … ∪ Am) = n (A1) + n (A2) + … + n (Am),

  которое доказывается методом математической индукции по  m.

Пример: Сколько человек  участвовало в прогулке, если известно, что 16 из них взяли с собой бутерброды с ветчиной, 24 – с колбасой, 15 – с сыром, 11 -  с ветчиной и колбасой, 12 – с сыром и колбасой, 6 – бутерброды всех трёх видов, а 5 вместо бутербродов взяли с собой пирожки?

  Решение: Обозначим через A множество участников, взявших с собой бутерброды с ветчиной, через B – с колбасой, через C – с сыром. Запишем условие задачи с помощью этих обозначений: n (A) = 16, n (B)  = 24, n (C) = 5, n(A ∩ B) = 11, n (A ∩ C) = 8, n (B ∩ C) = 12, n (A ∩ B ∩ C) = 6, n (D) = 5, через D обозначено множество участников прогулки, взявших с собой пирожки. Найдем n (A ∪ B ∪ C), т. е. число участников прогулки, взявших с собой бутерброды:

  n (A ∪ B ∪ C) = n (A) + n (B) + n (C) – n (A ∩ B) – n (A ∩ C) – n (B ∩ C) + n (A ∩ B ∩ C) = 16 + 24 + 5 – 11 – 8 – 12 + 6 = 30.

Следовательно, бутерброды взяли с собой 30 человек, а всего в прогулке участвовали  30 + 5 = 35  человек.

  Можно условие задачи изобразить графически с помощью схемы, которая называется диаграммой Эйлера – Венна и применяется для решения самых разнообразных задач, связанных с конечными множествами, математической логикой и т. д. С помощью диаграммы (рис.2.1) можно решить данную задачу, не используя формулу перекрытий. Для этого заметим, что область обозначенная VIII соответствует множеству  n (A ∩ B ∩ C) = 6 (cодержит 6 элементов). Объединение областей VII и  VIII изображают множество  n (A ∩ B) = 11; (5+6=11, т. к. в области VIII содержится 6 элементов, то в области VII – 5 элементов). Аналогично находим, что в области VI – 2 элемента, в V – 6. Теперь рассмотрим области, имеющие номера II, VI, VII и VIII. Их объединением является множество А, содержащее по условию 16 элементов. Но объединение областей VI, VII, VIII содержит 2 + 5 + 6 = 13 элементов, поэтому II область содержит 16 –13 = 3 элемента. Аналогично находим, что область III содержит 7 элементов, а IV – 1 элемент.

  Но объединение областей II, III, IV, V, VII и VIII является множеством A∪В∪С. Поскольку эти области не пересекаются, то число элементов во множестве n (A ∪ B ∪ C) = 3+7+1+6+2+5+6=30, т. е. что бутерброды взяли 30 человек. Область I изображает множество людей, захвативших пирожки (D), а прямоугольник - всех участников прогулки. Так как n (D) = 5, то общее число равно 35.

Рис. 2.1

Кортежи.

  Не всегда удается составить математическую модель комбинаторной задачи, используя понятия теории множеств. Во многих комбинаторных задачах существенную роль играет порядок элементов  (например, порядок обработки деталей на различных станках, порядок солдат в строю и т. д.), когда для множеств порядок роли не играет. Часто возникают задачи, в которых некоторые элементы неразличимы, тождественны (например, две белые шашки из одного комплекта, две машины одной марки, одного цвета и одного года выпуска и т. д.). Поэтому необходимо рассмотреть новое математическое понятие, которое можно использовать в таких задачах. Этим понятием является «кортеж» («слово», «n – мерный вектор»)

Слово «кортеж» по-французски означает торжественное шествие.

  Пусть дано некоторое множество X. Возьмем множество натуральных чисел  Nn = {1,…,n} и зададим некоторое отображение множества Nn во множество X. Это значит, что числу 1 ставится в соответствие элемент x1 € X. В результате получаем набор  x1,x1,…,xn  элементов множества X, в который некоторые элементы могут входить несколько раз. Располагая элементы этого набора в порядке возрастания номеров, получаем кортеж (x1,…,xn) длины n, составленный из множества элементов X. Элемент xk, 1 ≤ k ≤ n, называют k-й  компонентой или k-й координатой кортежа (x1,…,xn).

  Кортежи длины 2 называют парами (упорядоченными), а кортежи длины 3 – тройками. Примерами кортежей могут служить слова (кортеж, составленный из букв алфавита), десятичные записи чисел (кортеж, составленный из цифр) и т. д.

  Два кортежа  (x1,…,xn) и (y1,…,ym) называются равными, если они имеют одну и ту же длину, причем их компоненты, имеющие одинаковые номера, равны. Обычно кортежи принято обозначать греческими буквами. Если  б = (x1,…,xn), и  в = (y1,…,ym), то  б =  в  (когда  n = m и  хk=yk, для1≤ k ≤ n). Например, если то б = в, так как б и в имеют одинаковую длину и .

  Компонентами кортежа могут быть множества, кортежи и т. д. Кортеж, не содержащий ни одной компоненты, называется пустым и обозначается ( ).

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

Обобщим понятие кортежа путём рассматривания кортежей, компоненты которых принадлежат различным множествам. Т. е. зададим множества Х1, …, Хn и рассмотрим такие наборы  б  =(x1, …, xn) элементов этих множеств, что xk  € Xk, 1≤ k ≤ n. Множество, состоящие из таких кортежей, называется декартовым  произведением множеств Х1, …, Хn и обозначается  X1ЧX2ЧX3Ч…ЧXn.

Например, если  X1={a, b, c}, X2={1, 2}, то  X1ЧX2=6 (состоит из шести пар: (a,1); (a, 2); (b, 1); (b, 2); (c, 1); (c, 2)).

Множества  X1 Ч X2 ≠ X2 Ч X1,  X1 Ч Ш = Ш ЧX1 = Ш.

Найдем число элементов декартова произведения X Ч Y в случае, когда X  является k – множеством, а Y – m-множеством. Пусть X={x1, …, xk}, а Y={y1,…,ym}.Декартово произведение  XЧY состоит из пар (xi, yg), которые можно расположить следующим образом:

(x1,y1); (x1, y2); …; (x1, ym),

(x2, y1); (x2, y2); …;(x2, ym),

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

( xk, y1); (xk, y2); …; (xk, ym).

Мы получили k строк по m пар в каждой строке. Отсюда следует, что общее  число пар, входящих в X Ч Y, равно km, т. е. n (X)n(Y). Запишем формулу:  n(XЧY)=n(X)n(y), которая выражает правило произведения: «Число элементов в декартовом произведении конечных множеств X и Y равно произведению числа элементов множества Х и числа элементов множества Y».

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

« Если  объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А, В) в указанном порядке можно осуществить mn способами».

Пример2: Составляются знаки, состоящие из геометрической фигуры (окружности, квадрата, треугольника и шестиугольника), буквы и цифры. Сколько таких знаков можно составить?