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

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

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

Определение. Операция называется ассоциативной, если для любых элементов выполняется: .

Определение. Операция называется дистрибутивной слева относительно операции , если для любых выполняется:

,

и дистрибутивной справа относительно операции , если для любых выполняется:

.

(группоид) — в абстрактной алгебре — базовый тип алгебраической структуры. Магма состоит из множества М с одной бинарной операцией M × M → M. Помимо требованиязамкнутости множества относительно заданной на нём операции, других требований к операции и множеству не предъявляется.

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

 коммутативная группа есть группа, в которой групповая операция является коммутативной; то есть группа   абелева если   для любых двух элементов  .

8. Понятие группы. Группа подстановок.

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

Если не использовать в определении понятие полугруппы, то определить понятие группы можно следующим образом.

Определение 2. Множество А с определенной на нем алгебраической операцией (например, умножением) называется группой, если выполнены следующие условия:

1) для любых трех элементов a, b, c  A выполняется свойство ассоциативности:

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

3) для любого элемента а существует элемент а^-1 из этого же множества

9. Понятие кольца. Кольцо вычетов.

Определение. Множество R с двумя определенными в нем алгебраическими операциями, сложением и умножением, называется кольцом, если относительно операции сложения оно является абелевой группой, а операция умножения дистрибутивна, т.е. для любых элементов a, b и с  R справедливы равенства:

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

10. Понятие поля. Поле вычетов.

Определение. Полем называется коммутативное кольцо, в котором для любого ненулевого элемента a 0 и любого элемента b существует единственный элемент такой, что ax = b.

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

11. Понятие перестановки. Теорема о числе перестановок n-элементного множества.

В комбинаторике перестано́вка — это упорядоченный набор чисел   обычно трактуемый как биекция на множестве  , которая числу i ставит соответствиеi-й элемент из набора. Число n при этом называется порядком перестановки.

В теории групп под перестановкой (подстановкой) произвольного множества подразумевается биекция этого множества на себя.

Теорема. Число всех перестановок n – элементного множества равно n!.

12. Понятие перестановки с повторениями. Теорема о числе перестановок с повторениями.

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если k_i — количество элементов i-го типа, то   и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту 

13. Понятие сочетания. Теорема о числе сочетаний из n элементов по k. Свойства сочетаний.

В комбинаторике сочетанием из   по   называется набор   элементов, выбранных из данных   элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Так, например, наборы (3-элементные сочетания, подмножества,  ) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} ( ) являются одинаковыми (однако, как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

В общем случае число, показывающее, сколькими способами можно выбрать   элементов из множества, содержащего   различных элементов, стоит на пересечении  -й диагонали и -й строки треугольника Паскаля.^[1]

Число сочетаний из   по   равно биномиальному коэффициенту

14. Понятие сочетания с повторениями. Теорема о числе сочетания с повторениями.

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

Число сочетаний с повторениями из   по   равно биномиальному коэффициенту

15. Понятие размещения. Теорема о числе размещений.

В комбинаторике размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размеще́нием (из n по k) называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

Например,   — это 4-элементное размещение 6-элементного множества  .

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

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