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

Определение. Любой вектор длины , составленный из элементов элементного множества , в котором все элементы различны, называется перестановкой без повторений из элементов. Число всех перестановок без повторений из элементов обозначается и равно .

Из определения и формулы видно, что перестановки без повторений есть частный случай размещений без повторений, при условии .

Пример 4. Сколькими различными способами можно расставить на полке 10 различных книг?

Здесь, в отличие от примера 2, значение имеет только порядок расставляемых книг. Поэтому речь идёт о перестановках из 10 элементов. Получаем: .

Рассмотрим случай, когда элементы множества повторяются по нескольку раз. Для определённости пусть 1-й элемент повторяется раз, 2-й элемент - раз и так далее. Тогда векторы длины , образованные из элементов данного множества называются перестановками из элементов с повторениями. Число таких перестановок обозначается и равно .

Положив в последней формуле , получим формулу для перестановок без повторений.

Пример 5. Сколько различных шестизначных чисел могут быть записано с помощью цифр 1, 2, 2, 2, 3, 3?

Имеется набор из шести цифр, в котором цифра 2 повторяется трижды и цифра 3 – дважды. Полученные числа будут представлять собой перестановки с повторениями из 6 элементов. Получаем: .

4. Содержание

   • Конспект лекций по дисциплине “Дискретная математика”
   • Санкт Петербург Содержание.
   • Раздел I. Множества, функции, отношения. Лекция № 1. Множества и операции над ними.
   • 1. Основные понятия теории множеств.
   • 2. Операции над множествами и их свойства.
   • 3. Векторы и прямые произведения.
   • Лекция № 2. Соответствия и функции.
   • Соответствия.
   • Отображения и функции.
   • Лекция № 3. Отношения и их свойства.
   • Основные понятия и определения.
   • Свойства отношений.
   • Лекция № 4. Основные виды отношений.
   • Отношения эквивалентности.
   • Отношения порядка.
   • Лекция № 4. Пересчёт.
   • Раздел II. Введение в общую алгебру. Лекция № 6. Элементы общей алгебры.
   • 1. Свойства бинарных алгебраических операций.
   • 2. Алгебраические структуры.
   • Гомоморфизм и изоморфизм.
   • Лекция № 7. Различные виды алгебраических структур.
   • Полугруппы.
   • Группы.
   • Поля и кольца.
   • Раздел III. Введение в логику. Лекция № 8. Элементы математической логики.
   • Булевы функции.
   • Лекция № 9. Логические функции.
   • Функции алгебры логики.
   • Примеры логических функций.
   • Суперпозиции и формулы.
   • Лекция № 10. Булевы алгебры.
   • Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
   • Булева алгебра функций.
   • Эквивалентные преобразования.
   • Лекция № 11. Булевы алгебры и теория множеств.
   • Двойственность.
   • Булева алгебра и теория множеств.
   • Днф, интервалы и покрытия.
   • Лекция № 12. Полнота и замкнутость.
   • Функционально полные системы.
   • Алгебра Жегалкина и линейные функции.
   • Замкнутые классы. Монотонные функции.
   • Теоремы о функциональной полноте.
   • Лекция № 13. Язык логики предикатов.
   • Предикаты.
   • Кванторы.
   • Истинные формулы и эквивалентные соотношения.
   • Доказательства в логике предикатов.
   • Лекция № 14. Комбинаторика.
   • Правила суммы и произведения.
   • Размещения.
   • Перестановки.
   • Сочетания. Бином Ньютона.
   • Раздел IV. Теория графов. Лекция № 15. Графы: основные понятия и операции.
   • Графы, их вершины, рёбра и дуги. Изображение графов.
   • Матрица инцидентности и список рёбер. Матрица смежности графа.
   • Идентификация графов, заданных своими представлениями.
   • Лекция № 16. Маршруты, цепи и циклы.
   • Основные определения.
   • Связные компоненты графов.
   • Расстояния. Диаметр, радиус и центр графа. Протяжённости.
   • Эйлеровы графы.
   • Лекция № 17. Некоторые классы графов и их частей.
   • Деревья.
   • Ориентированные графы.
   • Графы с помеченными вершинами и рёбрами.
   • Лекция № 18. Теория алгоритмов Понятие алгоритма
   • 1.2.1. Основные требования к алгоритмам
   • 1.2.2. Машина Тьюринга
   • Универсальная машина Тьюринга
   • 1.2.3. Тезис Тьюринга
   • 1.3. Граф машина
   • 1.3.1. Модель данных
   • 1.3.2. Построение моделей алгоритмов в системе graph
   • 2. Сложность алгоритмов
   • 2.1.Временная и пространственная сложность алгоритма. Классы dtime и dspace
   • 2.2. Классы сложности
   • 2.2.1. Полиномиальность и эффективность
   • 2.2.2. Алгоритмическая сводимость задач
   • 3. Алгоритмы и их сложность
   • 3.1. Представление абстрактных объектов (последовательностей)
   • 3.1.1. Смежное представление последовательностей
   • 3.1.2. Связанное представление последовательностей
   • Список вопросов для подготовки к экзамену по дисциплине "дискретная математика"