6.2. Краткие теоретические сведения.

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

Основные разделы ДМ: комбинаторика, математическая логика, теория графов, теория кодирования, теория конечных автоматов и многие другие, в которых изучаемый объект носит дискретный характер.

Тема 1. Комбинаторика.

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

Для решения комбинаторных задач используются правила и формулы комбинаторики.

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

Правило суммы. Если элемент (действие) можно выбрать (выполнить) способами, элемент (действие) - другими способами, отличными от первых , то выбор (выполнение) одного из элементов (действий): или или (но не двух одновременно) можно осуществить способами.

Например, в ящике 300 деталей, из них 150 деталей – 1-го сорта, 100 – 2-го, а остальные – 3-го сорта. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта?

Деталь 1-го сорта из ящика, очевидно, можно извлечь способами, 2-го сорта – способами, тогда по правилу суммы существует способов извлечения из ящика одной детали или 1-го или 2-го сорта.

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

Например, в группе 30 студентов. Необходимо выбрать старосту, его заместителя и профорга. Сколько существует способов это сделать (при условии, что каждый студент имеет равные шансы занять одну и только одну из указанных выше должностей)?

Старостой, очевидно, может быть выбран любой из 30 студентов, его заместителем - любой из оставшихся 29, а профоргом – любой из оставшихся 28 студентов, т.е. n₁=30, n₂=29, n₃=28. По правилу произведения общее число способов выбора старосты, его заместителя и профорга равно способов.

Пусть дано множество из n различных элементов. Из этого множества могут быть образованы подмножества (размещения, сочетания и перестановки) из элементов каждое ( ). Например, из элементов множества могут быть образованы подмножества по 2 элемента - ab, ba, ac, ca, bc, cb, по 3 элемента – abc, acb, bac, bca, cba, cab.

Размещениями из n элементов по m называют такие упорядоченные подмножества множества из m элементов каждое, которые отличаются друг от друга как составом элементов, так и порядком их следования. Общее число размещений из n элементов по m находится по формуле:

,

где (читается: n-факториал) равно произведению n первых чисел натурального ряда, т.е. . По определению .

При построении конкретного размещения на 1-ое место можно поставить любой из элементов множества , на 2-ое – любой из оставшихся элементов и т.д.

Например, расписание одного дня состоит из 5 уроков. Определить число вариантов расписания при выборе из 9 дисциплин.

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

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

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

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

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

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

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

Перестановки являются частными случаями размещений, если . Поэтому для числа перестановок имеем:

Пусть имеется предметов, которые следует разместить по ящикам.

Тогда - число всех возможных способов размещения различных предметов по ящикам без всяких ограничений;

- число всех возможных способов размещения различных предметов по ящикам, не более чем по одному предмету;

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

- - число всех возможных способов размещения неразличимых предметов по ящикам без всяких ограничений;

- число всех возможных способов размещения различных предметов по ящикам, по одному предмету в каждый ящик;

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