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

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлена: 15.06.2021

Просмотров: 19

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

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

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

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

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

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

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

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

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

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

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

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


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

Решение:

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

Решение:

а)

б)

в)

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

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

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

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