Дискретная математика Элементы комбинаторики

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

 Рассмотрим подробнее эти три типа соединений:

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

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

 

 Общее число перестановок из m элементов обозначается Pm и вычисляется по формуле:

 2) Размещения.

"Дерево" решений Примеры, которые мы рассматривали до сих пор, включали получение единого решения. Однако на практике результат одного решения приводит к необходимости принятия следующего решения и т.д. Эту последовательность принятия решений нельзя выразить таблицей доходов, поэтому приходится использовать другой алгоритм принятия управленческих решений. Графически подобные процессы могут быть представлены с помощью "дерева" решений. Такое представление облегчает описание многоэтапного процесса принятия управленческого решения в целом. Рассмотрим "дерево" решений, которое применяют тогда, когда нужно принять несколько взаимосвязанных решений в условиях неопределенности в случае принятия решения, зависящего от исхода предыдущего или исходов испытаний.

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

 

 Общее число таких размещений расчитывается по формуле:

 

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

 3) Сочетания.

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

 

 Общее число сочетаний находится по формуле:

 

 

 Также одним из вариантов комбинаций являются перестановки с повторяющимися элементами.

 Если среди т элементов имеется т1 одинаковых элементов одного типа, т2 одинаковых элементов другого типа и т.д., то при перестановке этих элементов всевозможными способами получаем комбинации, количество которых определяется по формуле:

 Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.

 

 Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10.000.

 Число всех возможных комбинаций из 30 букв по две равно .

Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное количество комбинаций по две буквы равно 900.

 Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает 27.000 комбинаций.

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

Бином Ньютона. (полиномиальная формула)

 Бином Ньютона – это формула, выражающая выражение (a + b)n  в виде многочлена. Эта формула имеет вид:

Пример

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

Конъюнкция Дизъюнкция

Импликация Эквиваленция

Примеры

Булевы функции

 Определение. Булевой функцией  f(X1, X2, …, Xn) называется называется произвольная n – местная функция, аргументы и значения которой принадлежат множеству {0, 1}.

Исчисление предикатов

Конечные графы и сети. Основные определения

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

 При этом элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

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

( v , w) в Х называется кратностью ребра (v, w).

 Множество V и набор Х определяют граф с кратными ребрами – псевдограф.

Матрицы графов

Примеры

Достижимость и связность. Вершина w графа D (или орграфа) называется достижимой из вершины v, если либо w=v, либо существует путь из v в w(маршрут, соединяющий v и w).

Деревья и циклы

Элементы топологии Топология изучает понятия непрерывности и близости с абстрактной точки зрения.

Открытые и замкнутые множества

Непрерывные отображения

Топологические произведения

Примеры решения контрольной по математике