Материал: Михайленко Е.В. Математика. Ч. 1. Элементы общей алгебры

конфигурация – сочетания с повторениями. Используя первую часть формулы числа сочетаний с повторениями из 4 по 10, рассчитаем количество способов покупки:

Значит, существует 286 способов приобретения десяти пирожных при условиях, описанных в условии задачи.

6.4. Разбиения

Разбиением исходного n-элементного множества называется совокупность непересекающихся k подмножеств данного множества, содержащих n1, n2, n3, ... , nk элементов данного множества, причем n1 + n2 + n3

+ ... + nk = n.

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

На практике обычно используют упорядоченные разбиения множеств. Упорядоченное разбиение множества из n элементов на k подмножеств обозначаются следующим выражением: R(n1, n2, n3, ... , nk). Данная запись указывает на то, что в первое подмножество содержит ровно n1 элементов, второе – n2 элементов, третье – n3 элементов, …, k-ое – nk элементов.

Для подсчета числа упорядоченных разбиений можно использовать следующую формулу:

R(n1,n2, ,nk ) n1! n2!n! nk ! .

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

106

Решение. В данной задаче мы имеем упорядоченные разбиения множества из n = 6 книг на k = 3 подмножества. Причем, первое подмножество содержит n1 = 2 элемента, втрое – n2 = 3 элемента, а третье n3 = 1 элемент. Используя формулу числа упорядоченных разбиений получим:

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

Пример. Сколькими способами можно разбить группу из 25 курсантов на три подгруппы по 6, 9 и 10 человек в каждой группе?

Решение. По условию задачи общее количество курсантов в группе n = 25, количество подгрупп, на которые разбивается наша группа, k = 3, а количество курсантов в каждой подгруппе определены соответственно, как n1=6, n2=9, n3=10. Число упорядоченных разбиений группы рассчитаем по формуле:

Таким образом, группу курсантов из 25 человек можно разбить на три подгруппы по 6, 9 и 10 человек 16 360 143 800 способами. Число впечатляет!

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

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

Таких вариантов получилось равно три. Рассчитаем число возможных разбиений в каждой конфигурации:

Сложив количества разбиений в каждом из выше перечисленных вариантов, получим:

R = R(3,5) + R(4,4) + R(5,3) = 56 + 70 + 56 = 182.

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

108

Глава 7. Алгебраические структуры

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

7.1. Отображения и операции

Пусть заданы два множества X и Y . Правило f, по которому каждому элементу x множества X сопоставляется однозначно определённый элемент y множества Y, называют отображением множества X в множество Y. f : X → Y.

Пример. Пусть С - множество комплексных чисел, R - множество действительных чисел. Правило f, по которому каждому комплексному числу с множества С сопоставляется однозначно определённое действительное число r множества R можно определить, как нахождение модуля комплексного числа.

Понятие алгебраической операции

Пусть A - непустое множество.

Отображение f : An → A, такое что каждому упорядоченному набору из n элементов (a1, a2, a3, …, an) множества A ставится в соответствие некоторый однозначно определённый элемент b множества A называется n-арной алгебраической операцией на множестве A.

f(a1, a2, a3, …, an)= b

Если n = 1, то используется набор, состоящий из одного элемента (a) множества A. При этом операция называется унарной.

Пример. Пусть A - множество чисел {-5; -1; 1; 5}. Под унарной операцией f будем понимать нахождение противоположного числа.

Тогда f(-5) = 5; f(-1) = 1; f(1) = -1; f(5) = -5.

Пример. Пусть A - множество всех комплексных чисел. Унарную операцию f определим, как взятие комплексно сопряженного числа.

Антипример. Пусть A - множество всех целых чисел. Предположим, что унарная операция f ставит в соответствие целому числу его квадратный корень,

109

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

При n = 2 используется кортеж, содержащий два элемента (a1 , a2) множества A. В этом случае говорят о бинарной операции.

Пример. Пусть A - множество всех натуральных чисел. Бинарную операцию f (a1, a2) определим, как сумму чисел a1+ a2, например,

f(5, 7) = 5 + 7 = 12.

Антипример. Пусть A - множество всех натуральных чисел. Под бинарной операцией f предположим разность чисел a1 - a2.

Предположение некорректно, так как часть значений не является натуральными числами, например, f(6, 10) = -4.

Пример. Пусть множество A = {$, &, #}. Зададим на множестве A операцию с помощью таблицы Кэли:

7.2. Свойства алгебраических операций

Алгебраическая операция f на множестве A называется коммутативной, если для x, y A выполняется:

x * y = y * x.

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

Антипример. Операция возведения в степень, определенная на

множестве натуральных чисел не является коммутативной, например,

28 = 256 , однако 82 = 64.

Алгебраическая операция f на множестве A называется ассоциативной, если для x, y A выполняется:

110