Спец.гл.мат-ки_Ч.1_УП

71

10.Сколькими способами можно составить команду из 4 человек, если имеется 7 бегунов?

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

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

13.Запишите разложение бинома (a − b)5 .

14.Докажите свойство симметрии биномиальных коэффи-

циентов, сравнив формулы для Сnk и Сnn−k .

15.Найдите максимальный числовой коэффициент в разложении бинома (1+ x)8 .

16.Пользуясь формулой бинома Ньютона, вычислите

0,0825 с точностью до ε = 0,0001.

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

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

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

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

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

ческой операции.

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

72

множестве целых чисел; в самом деле, если r и s – любые два целых числа, то r + s тоже является целым числом.

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

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

2)существует единичный элемент e G такой, что для

каждого x G выполняется условие: x e = e x = x ;

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

Пример 1. Пусть на множестве G = Z задана операция сложения целых чисел. Проверить, является ли группой пара (Z, +).

Первое требование определения выполняется, так как сложение целых чисел ассоциативно: для любых a,b,c Z справед-

ливо (a + b) + c = a + (b + c) .

Единичным элементом относительно сложения целых чисел является число нуль. Действительно, для любого x Z выполняется условие: 0 + x = x + 0 = x .

Обратным элементом для произвольного целого числа x является противоположное ему число (–x). В самом деле, для каждого x Z найдется элемент – x Z, такой, что x + (− x) = (− x) + x = 0 .

Итак, множество целых чисел с заданной на нем операцией сложения (Z, +) является группой.

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

Умножение целых чисел ассоциативно, а единичным элементом является число 1: для каждого x Z выполняется условие x 1 = 1 x = x . Но обратный элемент существует не для каждого целого числа. Например, для целого числа x = 2 Z невозможно найти целое число y такое, чтобы 2 y = 1 .

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

73

Определение 2. Множество H G называется подгруппой группы (G, ), если оно замкнуто относительно операции , содержит единичный элемент группы G ( e H ) и для каждого x H обратный элемент x−1 H .

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

Пусть множество X состоит из n элементов x1, x2 ,..., xn , рас-

положенных в произвольном, но фиксированном порядке. Биекция ϕ : X → X называется подстановкой.

В случаях, когда природа элементов не имеет значения, удобно обращать внимание только на индексы и считать, что мы имеем дело с множеством A = {1,2,...,n} , равномощным X. Сле-

довательно,

1	2	...	n
ϕ =	i2	...	.
i1			in

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

но, что Sn = Pn = n!.

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

(ϕ1 ϕ 2 )(x) = ϕ 2 (ϕ1(x)) для любого x A .
Эта операция обладает свойствами:
1)	(ϕ1 ϕ 2 ) ϕ3 = ϕ1 (ϕ 2		ϕ 3 ) − выполняется свойство ассо-
циативности;			1			n
2)				2	...		, для кото-
	существует подстановка e =					Sn
				2	...
			1			n
рой e	ϕ = ϕ	e = ϕ для каждого ϕ Sn , т.е. существует единич-
ный элемент;		любого ϕ Sn			ϕ −1 Sn
3)	для		существует				такое, что
ϕ ϕ −1 = ϕ −1		ϕ = e − существует обратный элемент.

74

Следовательно, множество Sn образует группу относитель-

но операции перемножения перестановок. Отметим, что эта операция не является коммутативной, то есть ϕ ψ ≠ ψ ϕ , на-

пример,

ϕ ψ		1	2	3	1	2	3	1		2	3	,
	=							=
		3	2		2	3				3
				1			1	1			2
ψ ϕ		1	2	3	1	2	3		1	2	3
	=							=			.
		2	3		3	2			2	1
				1			1				3
Рассмотрим	произвольную					подстановку π Sn . Элемент

x A такой, что π (x) = x будем называть стационарным относительно подстановки π .

Пусть x1, x2 ,..., xk − все нестационарные элементы подстановки π , причем,

π (x1 ) = x2 , π (x2 ) = x3 ,..., π (xk −1) = xk , π (xk ) = x1 ,

где k – наименьшее из всех возможных. Такая подстановка называется циклом длины k и записывается в виде

π = (x1, x2 ,..., xk ) .

	1	2 3		4
Пример 1. Пусть π =					.
		2	4	1
	3
Стационарный элемент x = 2 . Подстановка π является цик-
лом длины k = 3 и может быть записана в виде π = (1,3,4) .
Пример 2. Пусть	1	2	3	4	5
	p =				.
		4	1	2
	5				3

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

1	2	3	4	5	1	2	3	4	5
										= (1,5,3) (2,4),
p =
5	2	1	4	3	1	4	3	2	5

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

75

Теорема 1. Любая подстановка π Sn может быть пред-

ставлена в виде композиции непересекающихся циклов длины

≥ 2 :

π = σ 1 σ 2 ... σ r .

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

лов.

Найдем в A наименьший нестационарный относительно

π элемент x1 ,	т.е. π (x1 ) ≠ x1 и для каждого x A выполняется
условие: если	x < x1 , тоπ (x) = x . (Если такого элемента не су-

ществует, то π является тождественной подстановкой (π = e ) и ее можно рассматривать как пустое произведение циклов).

Будем строить образы элемента x1 ,π (x1 ),π 2 (x1 ),... до тех

пор, пока не получим π k (x1 ) = x1 при наименьшем из возможных k (1 < k ≤ n ). Тогда подстановка

σ 1 = (x1,π (x1),π 2 (x1 ),...,π k −1 (x1 ))

определяет цикл длины k внутри подстановки π . Если все не-

стационарные элементы подстановки	π содержатся в σ 1 , то
π = σ1 . В противном случае найдем x2	– наименьший из неста-

ционарных элементов подстановки π , не входящий в цикл σ 1 . Строим цикл

σ 2 = (x2 ,π (x2 ),π 2 (x2 ),...,π m−1 (x2 )).

Очевидно, что σ 1 и σ 2 – непересекающиеся. Если все нестационарные элементы исчерпаны, то π = σ 1 σ 2 , в противном

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

π = σ 1 σ 2 ... σ r .

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

1	2	3	4	5	6
π =						.
	4	1	6	5	2
3

76

x1 = 1; π (x1) = 3; π 2 (x1 ) = π (3) = 1, значит σ 1 = (1,3) ;

x2 = 2; π (x2 ) = 4; π 2 (x2 ) = π (4) = 6; π 3 (x2 ) = 2 ,значитσ 2 = (2,4,6) ; x5 = 5 − стационарный элемент.

Следовательно, π = σ 1 σ 2 = (1,3) (2,4,6) .

Определение. Порядком подстановки π называется наи-

меньшее натуральное число p такое, что π p = e .

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

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

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

Определение. Группы G1 и G2 называются изоморфными,

если существует биекция f : G1 → G2 , сохраняющая групповую

операцию, т.е. f (x y) = f (x) f ( y) для всех x, y G1 . Пример. Пусть G1 − группа преобразований правильного

треугольника в себя G1 = {ϕ 0 ,ϕ1,ϕ 2 ,ϕ 3 ,ϕ 4 ,ϕ 5} , где ϕ 0 = e − тождественное преобразование, ϕ1 − поворот вокруг точки O на 120°,

ϕ 2 − поворот вокруг точки O на 240°, ϕ 3 ,ϕ 4 ,ϕ 5 − отражение относительно осей симметрии I, II, III соответственно (рис. 2.3).

	2
III	I
1	3

II

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

77

В качестве группы G2						рассмотрим группу подстановок на
множестве		X = {1,2,3}					вершин						треугольника
G2 = {π 0 ,π 1,π 2 ,π 3 ,π 4 ,π 5}, где
π 0	1 2 3			π 1 =		1	2 3		π 2 =		1	2		3
	=		,					,						,
						2					3	1
	1 2 3						3 1							2
π 3	1 2 3			π 4 =		1 2 3			π 5 =		1	2 3
	=		,					,						.
											2	1
	1 3 2					3 2 1								3
Легко убедиться, что					биекция			f (ϕi ) = π i , i =						группы G1
													1,5

на группу G2 является изоморфизмом.

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

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

Доказательство. Пусть G произвольная подгруппа порядка n. Обозначим Sn группу подстановок на множестве G . Зафиксируем произвольный элемент a G и рассмотрим отображение ϕa : G → G такое, что ϕ a (x) = x a для любого x G . Очевидно, образы различных элементов x и y, принадлежащих G , различны и, следовательно, множество значений E(ϕ a ) = G . Действительно, предположим, что ϕ a (x) = ϕ a ( y) при x ≠ y . Тогда

x a = a x x a = y a

(x a) a−1 = ( y a) a−1 x (a a−1 ) == y (a a−1 ) x = y .

Значит, отображение ϕ a является подстановкой на множестве G , причем ϕ a Sn , ϕ a−1 = ϕ a−1 Sn , e = ϕ a−1 ϕ a , т.е. множество F = {ϕ a a G} Sn образует подгруппу группы Sn . При этом

ϕ a b (x) = x (a b) = (x a) b = ϕ a (x) b = ϕb (ϕ a (x)) .

	78
Следовательно,	отображение	f : G → F Sn такое,	что
f (x) = ϕ x x G	является	изоморфизмом,	т.к.

f (x y) = f (x) f ( y) .

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

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

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

можно построить группы самосовмещений других геометрических фигур и показать их изоморфизм с подгруппой группы Sn .

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

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

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

	I	II
1		2
		III
4		3
		IV
	Рис. 2.4

79

Тождественное перемещение описывает тождественная

подстановка	1	2	3	4		. Вращения на 90°, на 180° и на 270°
		2	3	4
	1

− подстановки				1 2 3 4						1 2 3 4								и	1 2 3 4
									,
				2 3 4 1						3 4 1 2									4 1 2 3
соответственно.
Поворот			относительно						оси			I			описывает					подстановка
1 2 3 4			; относительно оси II – подстановка																	1 2 3 4
																								;
2 1 4 3																				3 2 1 4
1 2 3 4						; оси IV −				1 2 3 4
оси III −																	.
4 3 2 1										1 4 3 2
Таким образом, мы получили группу подстановок, изо-
морфную группе самосовмещений квадрата:
		1	2	3	4		1	2	3	4				1	2	3	4		1	2	3	4
						,						,						,						,
S8 =
		1	2	3	4		2	3	4	1				3	4	1	2		4	1	2	3
	1		2	3	4		1	2	3	4			1		2	3	4		1	2	3	4
						,					,							,
	2 1 4 3						3 2 1 4						4 3 2 1										.
																		1 4 3 2

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

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

2.Дано множество X = {−1,1} . Проверить, является ли дан-

ное множество группой относительно операции умножения.

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

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

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

6. Чему равен порядок подстановки	1	2	3	4	5		?
		3	2	5	4
	1

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

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

фигур.

80

ПРИЛОЖЕНИЕ 1

Контрольная работа № 1

Вариант 1

1. Решить задачу, используя диаграмму Эйлера–Венна. Четырнадцать спортсменов участвовали в кроссе, 16 – в со-

ревнованиях по плаванию, 10 – в велосипедных гонках. Восемь участников участвовали в кроссе и заплыве, 4 – в кроссе и велосипедных гонках, 9 – в плавании и велосипедных гонках. Во всех трех соревнованиях участвовали три человека. Сколько всего было спортсменов?

2. Задано универсальное множество U = {1,2,3,4,5,6,7,8} и

множества X = {1,3,6,7},Y = {3,4,7,8}, Z = {3,4,7,8}. Записать булеан множества X, любое разбиение множества Y, покрытие множества Z. Выполнить действия (X \ Y ) ∩ Z .

3. Доказать, используя законы и тождества алгебры множеств (перечислить используемые законы):

(A ∩ B) (B ∩ C) = (A ∩ C ) ∩ B.

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

A ∩ (B C) = (A ∩ B) (A ∩ C) .

5. Пусть X = {1,2,3,4} . Бинарное отношение R X × X задано характеристическим свойством:

R = {(a,b) a + b − четное, a,b X } .

Представить отношение различными способами. Выяснить, какими свойствами оно обладает.

6. Дано множество

X = {1,2,3,6} и отношение

R = {(x, y) x, y X , x − делитель y} . Показать, что отношение R

является отношением порядка. Построить диаграмму Хассе частично упорядоченного множества (X , R) . Существует ли в

множестве X наибольший и наименьший элементы? Существуют ли несравнимые элементы?

7. Заданы отношения: