Дискретная математика 2 курс 1 семестр / лекции / Раздел 6 Комбинаторика

Раздел 6. Комбинаторика

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

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

Возникновение и развитие комбинаторики тесно связано с развитием других разделов математики: теории чисел, алгебры. Еще математикам Древнего Востока была известна формула, выражающая число сочетаний через биноминальные коэффициенты и Бином Ньютона для натуральных . С мистическими целями изучались свойства магических квадратов 3-его порядка.

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

С появлением работы Лейбница и Бернулли «Искусство предположений» посвященной теории вероятностей комбинаторные схемы выделились в отдельную часть математики.

Возрождение интересов к комбинаторике относится к 50 годам ХХ века. Этот интерес связан с развитием кибернетики. Большой развивающийся раздел комбинаторики это теория блок-схем. Основные проблемы этого раздела связаны с вопросами классификации, условиями существования и методами построения некоторых классов блок-схем.

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

Будем считать, что рассматриваем множество , состоящее из n различных элементов.

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

Теорема: Число размещений без повторений равно

Доказательство: Для того чтобы расположить элементов в определенном порядке выберем один и будем считать его «первым». Это можно сделать способами. Оставшееся множество содержит элемент. Из него выберем ещё один и будем считать его «вторым». Для выбора второго элемента существует способ. Осталось элемента. Продолжая рассуждать подобным образом понятно, что -ый элемент можно способами. Пользуясь утверждением, приведенном в начале параграфа получим

Пример: Определить, сколько трехзначных чисел можно составить из множества цифр 1,2,3,4,5 без повторений.

Решение:

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

Теорема: Число Перестановок без повторений равно

Доказательство: Повторяет доказательство предыдущей теоремы, полагая .

Пример: К кассе за получением денег одновременно подошли 4 человека. Сколькими способами они могут выстроиться в очередь.

Решение: Очередь состоит из 4 различных человек, поэтому эти очереди отличаются только порядком элементов. Это перестановки без повторений.

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

Теорема: Число

Доказательство: Рассмотрим перестановку из n элементов по . Если не считаться с порядком элементов, то существует ! Перестановок, которые не различимы. Следовательно . Упрощая эту формулу, получим искомую.

Пример: Имеется 6 штаммов бактерий. Для определения скорости их роста необходимо выбрать 3 штамма. Сколькими способами можно это сделать?

Решение: Способы отбора различаются, если каждая группа штаммов различаются хотя бы одним элементом. Это число

Пример: Выбрать из 20 человек в группе 8 человек для сдачи зачета досрочно.

Решение:

Пример: В ящике 20 шаров, среди них 12 белых, остальные зелёные. Отбирается наугад 2. Сколькими способами можно отобрать а) два белых шара, б) два зелёных, в) один белый и один зелёный.

Решение:

а)

б)

в)

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

Теорема: Число размещений с повторениями из элементов по равно

Доказательство: Рассуждения очень похожи на доказательство числа размещения без повторений. Значение, которое стоит на «первом» месте можно выбрать способами. Значение, стоящее на «втором» месте также можно выбрать способами (т.к. они могут повторяться, элементы после выбора не удаляются из множества, из которого выбирают). И т.д. процедура повторяется раз.

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

Теорема: Число

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

Решение: Общее число перестановок равно Но отношение соседства сохраняется при циклических перестановках (повороте) их для каждого различного размещения и при симметричном отображении (их 2). Следовательно .

Пример: Из колоды в 52 карты вынули 10 карт. В скольких случаях среди этих карт окажется а) хотя бы один туз; б) ровно один туз; в) не менее двух тузов; г) ровно два туза.

Решение:

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

б)

в) С₅₂¹⁰ – С₄₈¹⁰ – С₄¹ С₄₈⁹

г)

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

Решение:

Выбрать места для мужчин и женщин можно двумя способами. После этого рассадить мужчин на выбранные места можно способами. На остальных местах способами можно посадить женщин. Всего способов.

Пример: Сколькими способами можно составить 3 пары из шахматистов?

Решение:

Выбираем 6 шахматистов способами. В каждой из этих выборок рассмотрим количество перестановок их 6!. Считая, что в первой паре элементы с 1 – ого и 2 – го места перестановки и т.д. Но при этом несущественен порядок в каждой паре 23 и порядок пар 3!. Следовательно, количество перестановок равно 6!/ (23 3!). Итого

Задачи:

Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт с маркой?

Сколько словарей нужно издать, чтобы переводить с любого из 5 языков на любой другой?

Есть пятиразрядный цифровой замок, каждый диск которого содержит цифры от0 до 5. Сколько комбинаций таких цифр?

Сколькими способами можно упорядочить множество цифр от 1 до 2n так, чтобы все четные числа стояли на четных местах.

Сколькими способами можно упорядочить множество цифр от 1 до n так, чтобы числа 1,2,3 стояли рядом и в порядке возрастания.

Какое количество различных символов можно передать не более чем 5 знаками «.» и «-».

Автомобильные номера состоят из 3 букв и 4 цифр. Найти количество возможных номеров, если используются 32 букв русского алфавита.

Сколько машинных слов можно составить из букв слова КОЛОКОЛ, слова ВОДОРОД.

Сколькими способами 9 одинаковых конфет можно разложить по 5 пакетам, если ни один из пакетов не должен быть пустым. Тот же вопрос, но пакеты могут быть пустыми.