Элементы комбинаторики: перестановки, размещения, сочетания.

Комбинаторика – это наука о расположении элементов в определенном порядке и о подсчете числа способов такого расположения.

 

Комбинаторный принцип умножения если одну часть действия можно выполнить k способами, а другую - p способами, то все действие можно выполнить k*p числом способов.

 

 

Размещением из n элементов множества Х по k элементам назовем любой упорядоченный набор элементов множества Х.

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

 

Если выбор элементов множества Y из Х происходит с возвращением, т.е. каждый элемент множества Х может быть выбран несколько раз, то число размещений из n по k находится по формуле: = n^k.

 

Пусть из множества Х выбирается неупорядоченное подмножество Y (порядок элементов в подмножестве не имеет значения). Сочетаниями из n элементов по k называются подмножества из k элементов, отличающиеся друг от друга хотя бы одним элементом. Общее число всех сочетаний из n по k обозначается и равно
.

Справедливы равенства: , , .

 

 

Сочетание с повторениями – сколько способами можно взять из n k элементов с возвращениями и без учета порядка. Число сочетаний с повторениями из n по k равно биномиальному коэффициенту.

 

Перестановки.

P_n – количество перестановок из n элементов (сколько способами можно упорядочить)

 

Основные комбинаторные схемы.

- число перестановок (упорядочивание)

- число перемещений (число размещений)

- число сочетаний (без учета порядка)

 

- число сочетаний с возвращениями с учетом порядка

 

- число сочетаний с возвращениями без учета порядка (число сочетаний с повторениями)

 

Основные алгебраические структуры: полугруппы, группы, кольца, поля и их простейшие свойства.

 

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

Множество с одной бинарной ассоциативной операцией называется полугруппой. Полугруппы иногда называют моноидами.

Полугруппа называется группой если:

а) есть нейтральный элемент

б) для любого элемента есть обратный.

 

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

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

б) операция умножения дитрибутивна относительно операции сложения, то есть для любых элементов a, b, c исходного множества справедливы тождества:

a + (b * c) = a * c + b * c

c * (a + b) = c * a + c * b

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

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

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

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

Множество всех комплексных чисел с операциями сложения и умножения – поле

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

 

Свойства элементов группы. Подгруппы группы.

 

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

 

Подгруппа – подмножество группы, также является само группой относительно той же операции. (G > H)

 

e – нейтральный элемент. Если есть в группе, то он есть и в подгруппе. Это один и тот же элемент, и быть другим в подгруппе он не может.

g^-1 – обратный, есть и в группе и в подгруппе, отличаться не может.

 

 

Отношения эквивалентности.

x1, x2 ∈ X

x1 ρ x2 – находятся в отношении

Отношение эквивалентности – это отношение, для которого выполняются 3 свойства:

1) Для любого х есть свойство быть в отношении самому с собой

x ∈ X

x ρ x

2) x ρ y à y ρ x (свойство симметричности)

3) x ρ y, y ρ x à x ρ z (свойство транзитивности)

 

 

⇐ Предыдущая123456789Следующая ⇒

Поделиться: