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

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

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

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

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

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

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

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

Пример.

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

; ; ;; ;

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

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

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

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

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

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

Дата добавления: 2014-01-04