Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


Основные понятия.

КОМБИНАТОРИКА

 

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

 

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

Число всех перестановок (от фран. "permutation"- перестановка).

 

Доказательство.

 

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

 

Пример.

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

; ; ;; ;

 

Очевидно, что 10 книг на полке можно расставить различными способами.

 

Перестановки обладают следующими свойствами: аддитивностью (правилом суммы) и мультипликативностью (правилом произведения).

Свойство аддитивностизаключается в следующем. Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор "А или В" можно осуществить m+n способами.

Пример. От Октябрьской площади до цирка можно проехать через Северную и Южную дамбы. В первом случае количество дорог равно 4, а во втором — 3. Сколькими способами можно добраться от Октябрьской площади до цирка?



Решение. Очевидно, число разных путей от Октябрьской площади до цирка равно 4+3=7.

Свойство мультипликативностизаключается в следующем. Если некоторый объект А можно выбрать m способами, а после этого объект В можно выбрать n способами, то выбор "А и В" можно осуществить m∙n способами.

 

<== предыдущая лекция | следующая лекция ==>
Переход от автомата Мура к автомату Мили | Решение

Дата добавления: 2014-01-04; Просмотров: 866; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.