Автор работы: Пользователь скрыл имя, 09 Ноября 2012 в 14:35, курс лекций
I. Множество замкнуто относительно некоторой операции, если результат действия операции на элементы этого множества дает снова элемент из . Например, множество целых чисел замкнуто относительно операций сложения, вычитания и умножения ( сумма, разность и произведение целых чисел также целое число) и не замкнуто относительно операций извлечения корня и деления ( и не целые числа).
Элементы комбинаторики.
Если из некоторого количества элементов, различных меду собой, составлять различные комбинации, то среди них можно выделить три типа комбинаций, носящих общее название – соединения.
Рассмотрим подробнее эти три типа соединений:
1) Перестановки.
Определение. Если в некотором множестве переставлять местами элементы, оставляя неизменным их количество, то каждая полученная таким образом комбинация называется перестановкой.
Общее число перестановок из m элементов обозначается Pm и вычисляется по формуле:
2) Размещения.
Определение. Если составлять из т различных элементов группы по n элементов в каждой, располагая взятые элементы в различном порядке. Получившиеся при этом комбинации называются размещениями из т элементов по п.
Общее число таких размещений расчитывается по формуле:
Вообще говоря, перестановки являются частным случаем размещений.
3) Сочетания.
Определение. Если из т элементов составлять группы по п элементов в каждой, не обращая внимания на порядок элементов в группе, то получившиеся при этом комбинации называются сочетаниями из т элементов по п.
Общее число сочетаний находится по формуле:
Также одним из вариантов комбинаций являются перестановки с повторяющимися элементами.
Если среди т элементов имеется т1 одинаковых элементов одного типа, т2 одинаковых элементов другого типа и т.д., то при перестановке этих элементов всевозможными способами получаем комбинации, количество которых определяется по формуле:
Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.
Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10.000.
Число всех возможных комбинаций из 30 букв по две равно .
Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное количество комбинаций по две буквы равно 900.
Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает 27.000 комбинаций.
Окончательно, т.к. каждой буквенной комбинации можно поставить в соответствие числовую комбинацию, то полное количество автомобильных номеров равно 270.000.000.