Комбинаторика. Основы теории групп

КОМБИНАТОРИКА. ОСНОВЫ ТЕОРИИ ГРУПП

Комбинаторика

Задачи комбинаторики

 

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

а) выяснить, сколько существует элементов, обладающих заданным свойством;

б) составить алгоритм, перечисляющий все элементы с заданным свойством;

в) отобрать наилучший по некоторому признаку среди перечисленных элементов.

Мы будем заниматься только задачами первого типа. При этом будет идти речь об отборе r элементов с заданным свойством из конечного множества X, состоящего из n элементов. Результат такого отбора будем называть выборкой. Нас будет интересовать вопрос о количестве выборок заданного типа.

 

Типы выборок

 

Выборки делятся на типы по двум признакам: а) важен ли порядок отбора элементов; б) есть ли среди отобранных элементов одинаковые. Будем обозначать n – количество элементов в исходном множестве X, r – количество элементов в выборке.

Упорядоченный набор элементов, среди которых нет повторяющихся, называется размещением из n элементов по r. Количество размещений обозначается (табл. 2.1).

Таблица 2.1

Типы выборок

	Повторений элементов нет	Повторения элементов есть
Порядок важен	размещения	размещения с повторениями
Порядок не важен	сочетания	сочетания с повторениями

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

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

Пример. Составляя всевозможные четырехзначные телефонные номера из десяти цифр, мы получаем размещения с повторениями из 10по 4, т.к. в телефонном номере могут встретиться одинаковые цифры, порядок записи цифр важен.

Неупорядоченный набор элементов, среди которых нет повторяющихся, называется сочетанием из n элементов по r. Количество сочетаний обозначается .

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

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

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

 

Размещения с повторениями

Задача. Определить количество всех упорядоченных наборов длины r, которые можно составить из элементов множества X (), если выбор каждого элемента , производится из всего множества X.

Упорядоченный набор – это элемент декартова произведения , состоящего из r одинаковых множителей X. По правилу произведения количество элементов множества равно . Мы вывели формулу .

Пример. Сколько четырехзначных телефонных номеров можно составить, если использовать все десять цифр?

Здесь , и количество телефонных номеров равно

 

Размещения без повторений

 

Задача. Сколько упорядоченных наборов можно составить из n элементов множества X, если все элементы набора различны?

Первый элемент можно выбрать n способами. Если первый элемент уже выбран, то второй элемент можно выбрать лишь способами, а если уже выбран элемент , то элемент можно выбрать способами (повторение уже выбранного элемента не допускается). По правилу произведения получаем

Эта формула записывается иначе с использованием обозначения . Так как

то

.

Пример. Сколько может быть различных списков победителей олимпиады (первое, второе, третье место), если участвовало 20человек?

Здесь , искомым является число

 

Перестановки без повторений

 

Рассмотрим частный случай размещения без повторений: если , то в размещении участвуют все элементы множества X, т.е. выборки имеют одинаковый состав и отличаются друг от друга только порядком элементов. Такие выборки называются перестановками. Количество перестановок из n элементов обозначают :

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

.

 

Перестановки с повторениями

 

Пусть множество X состоит из k различных элементов: . Перестановкой с повторениями состава будем называть упорядоченный набор длины , в котором элемент встречается раз . Количество таких перестановок обозначается .

Пример. Из букв запишем перестановку с повторением состава . Ее длина , причем буква a входит 2 раза, b – 2 раза, c – один раз. Такой перестановкой будет, например, или .

Выведем формулу количества перестановок с повторениями. Занумеруем все одинаковые элементы, входящие в перестановку, различными индексами, т.е. вместо перестановки получим . Теперь все элементы перестановки различны, а количество таких перестановок равно . Первый элемент встречается в выборке раз. Уберем индексы у первого элемента (в нашем примере получим перестановку ), при этом число различных перестановок уменьшится в раз, т.к. при изменении порядка одинаковых элементов наша выборка не изменится. Уберем индексы у второго элемента – число перестановок уменьшится в раз. И так далее, до элемента с номером k – число перестановок уменьшится в раз. Получим формулу

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

В этом слове буквы “е” и “а” встречаются два раза, остальные по одному разу. Речь идет о перестановке с повторением состава длины . Количество таких перестановок равно

.

 

Сочетания

 

Задача. Сколько различных множеств из r элементов можно составить из множества, содержащего n элементов?

Будем составлять вначале упорядоченные наборы по r элементов в каждом. Количество таких наборов (это размещения из n элементов по r) равно . Теперь учитываем, что порядок записи элементов нам безразличен. При этом из различных размещений, отличающихся только порядком элементов, получим одно сочетание. Например, два различных размещения и из двух элементов соответствуют одному сочетанию . Таким образом, число сочетаний в раз меньше числа размещений :

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

 

Сочетания с повторениями

 

Задача. Найти количество сочетаний с повторениями из n предметов по r.

Рассмотрим вывод формулы на примере с фотографиями (см. 2.1.2). Имеется n типов предметов ( негатива). Нужно составить набор из r предметов ( фотографий). Наборы различаются своим составом, а не порядком элементов. Например, разными будут наборы состава и – один содержит три фотографии с первого негатива и по одной со второго и с третьего, а другой – одну с первого и четыре с третьего. Разложим эти наборы на столе, разделяя фотографии разного типа карандашами. Карандашей нам понадобится , а фотографий . Мы будем получать различные сочетания с повторениями, переставляя между собой эти предметов, т.е. - число сочетаний с повторениями из n предметов по r равно числу перестановок с повторениями длины состава . В нашем примере

Иначе формулу сочетаний с повторениями можно записать

Бином Ньютона

 

В школе изучают формулы сокращенного умножения:

Бином Ньютона позволяет продолжить этот ряд формул. Раскроем скобки в следующем выражении:

Общий член суммы будет иметь вид Чему равен коэффициент C? Он равен количеству способов, которыми можно получить слагаемое (т.е. количеству способов, которыми можно выбрать k скобок с множителем a, а из остальных скобок взять множитель b). Например, если то слагаемое можем получить, выбрав множитель a из первой и пятой скобки. Каков тип выборки? Порядок перечисления не важен (выбираем сначала первую, затем пятую скобки, или, наоборот, сначала пятую, затем первую – безразлично), повторяющихся элементов (одинаковых номеров скобок) в выборке нет. Это сочетание без повторений. Количество таких выборок равно

Таким образом, формула бинома для произвольного натурального n имеет вид:

или

.

Пример. При получим формулу

т.к.

Проверьте правильность формулы, перемножив на .

Строгое доказательство формулы бинома Ньютона проводится методом математической индукции.

 

Группы подстановок

Понятие группы

 

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

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

Для этого сначала определим понятие бинарной алгебраической операции.

Бинарная операция на множестве – это соответствие, при котором каждой упорядоченной паре элементов данного множества отвечает однозначно определенный элемент того же множества. Так, действие сложения есть бинарная операция на множестве целых чисел; в самом деле, если r и s – любые два целых числа, то тоже является целым числом.

Определение 1. Непустое множество G с заданной на нем бинарной алгебраической операцией Ä называется группой, если:

1) операция Ä ассоциативна;

2) существует единичный элемент такой, что для каждого выполняется условие: ;

3) для каждого существует обратный элемент такой, что .

Эти три условия, необходимые для того, чтобы множество G с заданной на нем операцией Ä являлось группой, называются аксиомами группы.

Пример 1. Рассмотрим в качестве множества G множество всех целых чисел Z, а в качестве бинарной операции – сложение.

Проверим для пары (Z, +) аксиомы группы.

1) Ассоциативность. Сложение чисел ассоциативно: для любых Z, ;

2) Единичный элемент: нуль является единичным элементом для рассматриваемого множества относительно операции сложения, так как для каждого Z выполняется условие: ;

3) Обратный элемент: для каждого Z существует элемент –x, такой, что .

Итак, проверка показывает, что (Z, +) – группа.

Пример 2. Рассмотрим то же множество Z, но теперь с операцией умножения, т.е. рассмотрим пару (Z, ·). Проверим аксиомы группы.

1) Ассоциативность. Умножение чисел ассоциативно: для любых Z, ;

2) Единичный элемент: число 1 является единичным элементом рассматриваемого множества относительно операции умножения, т.е. для каждого Z выполняется условие: ;

3) Обратный элемент. Так как аксиома должна выполняться для любого элемента множества Z, то попытаемся найти обратный элемент для числа 2, т.е. нужно найти Z, такой что или . Такого целого числа не существует, таким образом, множество целых чисел, с заданной на нем операцией умножения, не является группой.

Определение 2. Множество называется подгруппой группы G, если оно замкнуто относительно операции Ä, , и для каждого обратный элемент .

 

Группа подстановок

 

Пусть множество X состоит из n элементов , расположенных в произвольном, но фиксированном порядке.

Биекция называется подстановкой.

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

.

Обозначим - множество всех подстановок на A. Очевидно, что .

На множестве будем рассматривать операцию перемножения (композиции) подстановок и :

для любого .

Эта операция обладает свойствами:

1) - выполняется свойство ассоциативности;

2) существует подстановка , для которой для каждого - выполняется аксиома существования единичного элемента;

3) для любого существует такое, что - выполняется аксиома существования обратного элемента.

Следовательно, множество образует группу относительно операции перемножения перестановок. Отметим, что эта операция не является коммутативной, то есть , например,

,

.

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

Пример 1. Пусть .

Стационарный элемент . Подстановка является циклом длины и может быть записана в виде .

Пример 2. Пусть .

Подстановка p не является циклом, но может быть представлена в виде композиции двух циклов:

причем эти циклы являются непересекающимися, т.е. не имеют общих нестационарных элементов.

Теорема 1. Любая подстановка может быть представлена в виде композиции непересекающихся циклов длины :

.

Доказательство теоремы дает процедуру построения циклов.

Найдем в A наименьший нестационарный относительно элемент , т.е. и для каждого выполняется условие: если , то . (Если такого элемента не существует, то является тождественной подстановкой () и ее можно рассматривать как пустое произведение циклов).

Будем строить образы элемента , до тех пор, пока не получим при наименьшем из возможных k (). Тогда подстановка

определяет цикл длины k внутри подстановки . Если все нестационарные элементы подстановки содержатся в , то . В противном случае найдем - наименьший из нестационарных элементов подстановки , не входящий в цикл . Строим цикл

.

Очевидно, что и - непересекающиеся. Если все нестационарные элементы исчерпаны, то , в противном случае повторяем процесс, пока каждый нестационарный элемент не войдет в какой-либо цикл. В конечном итоге получим .

Пример. Представить в виде композиции циклов подстановку

.

, значит ;

,значит ;

- стационарный элемент.

Следовательно, .

Определение. Порядком подстановки называется наименьшее натуральное число p такое, что .

Теорема 2. Порядок подстановки равен наименьшему общему кратному порядков циклов в ее разложении на непересекающиеся циклы.

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

 

Изоморфизм групп

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

для всех .

Пример. Пусть - группа преобразований правильного треугольника в себя , где - тождественное преобразо-вание, - поворот вокруг точки O на 120°, - поворот вокруг точки O на 240°, - отражение относительно осей симметрии I, II, III соответственно (рис. 2.3).

 

2

 

III I

 

1 3

 

II

Рис. 2.3. Преобразование правильного треугольника

 

В качестве группы рассмотрим группу подстановок на множестве вершин треугольника , где

, , ,

, , .

Легко убедиться, что биекция группы на группу является изоморфизмом.

Будем называть порядком конечной группы количество ее элементов .

Теорема (Кэли). Всякая конечная группа порядка n изоморфна некоторой подгруппе группы подстановок .

Доказательство. Пусть произвольная подгруппа порядка n. Обозначим группу подстановок на множестве . Зафиксируем произвольный элемент и рассмотрим отображение такое, что для любого . Очевидно, образы различных элементов x и y, принадлежащих , различны и, следовательно, множество значений . Действительно, предположим, что при . Тогда .

Значит, отображение является подстановкой на множестве , причем , , , т.е. множество образует подгруппу группы . При этом

.

Следовательно, отображение такое, что является изоморфизмом, т.к. .

Задача. Найти группу подстановок, изоморфную группе поворотов правильного восьмиугольника на плоскости.

Решение задачи провести самостоятельно.

 

Самосовмещения фигур

 

Обширный и очень важный класс разнообразных групп как конечных, так и бесконечных составляют группы “самосовмещений” геометрических фигур. Под самосовмещением данной геометрической фигуры F понимают такое перемещение фигуры F (в пространстве или на плоскости), которое переводит F в самое себя, т.е. совмещает фигуру F с самой собой.

Мы уже познакомились с одной из простейших групп самосовмещений, а именно с группой поворотов правильного треугольника на плоскости и показали, что она изоморфна некоторой подгруппе группы подстановок . Аналогичным образом можно построить группы самосовмещений других геометрических фигур и показать их изоморфизм с подгруппой группы .

Задача. Построить группу симметрий квадрата.

Решение. Занумеруем вершины квадрата и оси симметрий (рис. 2.4). Обозначим O – центр симметрии квадрата.

В группу самосовмещений войдет тождественное перемещение – поворот вокруг точки O на 0°; повороты вокруг этой точки на 90°, на 180° и на 270°; повороты относительно четырех осей симметрии. Итого, получаем восемь элементов группы симметрий.

 

 

 

Тождественное перемещение описывает тождественная подстановка . Вращения на 90°, на 180° и на 270° - подстановки , и соответственно.

Поворот относительно оси I описывает подстановка ; относительно оси II – подстановка ; оси III - ; оси IV - .

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

S₈ =

.

2.2.5. Контрольные вопросы и упражнения

 

1. Что такое группа?

2. Дано множество . Проверить, является ли данное мно-жество группой относительно операции умножения.

3. Что такое подгруппа?

4. Привести пример подстановки, которая является полным циклом.

5. Объяснить процедуру разложения подстановки в произведение независимых циклов.

6. Чему равен порядок подстановки ?

7. Какие группы называются изоморфными?

8. Приведите примеры самосовмещений геометрических фигур.

 

КОМБИНАТОРИКА. ОСНОВЫ ТЕОРИИ ГРУПП

Комбинаторика

Задачи комбинаторики

 

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

а) выяснить, сколько существует элементов, обладающих заданным свойством;

б) составить алгоритм, перечисляющий все элементы с заданным свойством;

в) отобрать наилучший по некоторому признаку среди перечисленных элементов.

Мы будем заниматься только задачами первого типа. При этом будет идти речь об отборе r элементов с заданным свойством из конечного множества X, состоящего из n элементов. Результат такого отбора будем называть выборкой. Нас будет интересовать вопрос о количестве выборок заданного типа.

 

Типы выборок

 

Выборки делятся на типы по двум признакам: а) важен ли порядок отбора элементов; б) есть ли среди отобранных элементов одинаковые. Будем обозначать n – количество элементов в исходном множестве X, r – количество элементов в выборке.

Упорядоченный набор элементов, среди которых нет повторяющихся, называется размещением из n элементов по r. Количество размещений обозначается (табл. 2.1).

Таблица 2.1

Типы выборок

	Повторений элементов нет	Повторения элементов есть
Порядок важен	размещения	размещения с повторениями
Порядок не важен	сочетания	сочетания с повторениями

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

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

Пример. Составляя всевозможные четырехзначные телефонные номера из десяти цифр, мы получаем размещения с повторениями из 10по 4, т.к. в телефонном номере могут встретиться одинаковые цифры, порядок записи цифр важен.

Неупорядоченный набор элементов, среди которых нет повторяющихся, называется сочетанием из n элементов по r. Количество сочетаний обозначается .

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

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

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