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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

< Предыдущая		Следующая >