19. Основные элементы комбинаторики

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

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

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

Основными задачами комбинаторики являются:

1. Определение типа комбинации

2. подсчет количества.

Виды комбинаций:

1. перестановки

2. размещение

3. сочетание.

Размещение и сочетание бывают с повтором и без повтора.

Количество перестановок:

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

(без повторений)

(с повторениями)

Количество сочетаний: (не имеет значение порядок)

(без повторений)

(с повторениями)

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

Перестановки - некоторое количество объектов называется любое размещение этих объектов в сторго определенном линейном порядке.

Перестановками - называются комдинация, составленные из n одних и тех же, но различных элементов отличающихся только порядком их расположения.

Пример: Какими способами можно расставить на полке три книги: A,B,C.

1 способ: Дерево рассуждений

2 способ: По формуле

3

2

1

3способ: =3*2*1=6

Общий случай правила перестановок:

Пусть нужно выполнить какие либо k действий. Если I_д можно выполнить n₁ количеством способов. II_д – n₂ способов, ….. К_д – n_к способов. То все К действий можно выполнить n₁∙ n₂∙…… ∙n_к способов.

Пример:

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

Ответ: 24

2) номер автомобиля состоит из двух латинских букв(26), за которыми следует трехзначное число. Сколько существует таких номеров?

26

26

9

10

10

=26² *9*10²=608400.

21. Размещение

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

ПР.:Сколькими способами из 7 книг можно отобрать 3 и расставить на 3 места на книжной полке.

ПР.:Сколько 5-буквеных слов можно образовать из букв, составляющих слово «треугольник».

=55440

ПР.:Сколько различных перестановок можно получить по 5 карт из 52 карт.

ПР.:Сколько 4-хзначных чисел можно составить используя 1-5, если:

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

2)повторение цифр допустимо.

1)

2)

22. Сочетания

Сочетанием наз-ся комбинации, составленные из n-элементов по к-элементам, которые различаются хотя бы одним элементом.

Различие между размещением и сочетанием состоит в том, что в размещениях порядок элементов учитывается, а в сочетании – нет.

ПР.: х.у - человек

1. очередь – 2 способа: ху,ух – порядок важен – размещение

2. комиссия – 1 способ - порядок не учитывается – сочетание

ПР.: Сколькими способами читатель может отобрать 3 книги из 4-х:

1) если порядок книг не интересует:

2) если порядок книг интересует:

ПР.: Сколькими способами можно выбрать 2 детали из 10:

ПР.: Сколькими способами можно составить комиссию в составе 3-х человек из 4-х супружеских пар:

1) в комиссию входит любые 3 человека:

2) 2 женщины + 1 мужчина:

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

;

Среди комбинатор. Задач выделяют следующие: пересчет, перечисление, классификация и оптимизация.

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

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

Набор элементов (х_i1, x_i2,…,x_ik), составленный из элементов множества х=(x₁,…,x_n) называется выборкой объема к. (n,k выборка)

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

Замечание: 2 выборки с различным порядком следования одних и тех же элементов считаются различными.

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

(n,k) – упорядоченная выборка, элементы которой могут повторяться, называется

размещением из n элементов по к с повторением.

(n,k) – размещение называется перестановкой из n элементов.

Неупорядоченной (n,k) – выборкой называется сочетанием из n элементов по к элементам.

Замечание: Если нет повторяющихся элементов, то . Если есть повторяющиеся элементы, тогда .

Правило суммы в частном случае: Если мощность множества х .

Правило суммы в общем случае: Пусть даны множества х_i, если .