Комбинаторика

    Комбинаторика

    Комбинаторика- один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в ВТ, кибернетике, робототехнике. Большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств, поэтому эти две темы - элементы теории множеств и комбинаторика- рассматриваются взаимосвязано.

    Человеку  часто приходится иметь дело с  задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число  всех возможных способов осуществления некоторого действия. Например, сколькими способами могли быть распределены золотая, серебряная и бронзовая медали на Олимпийских играх в Сеуле по баскетболу; или сколькими различными способами можно разместить здания на площади? Задачи такого типа называются комбинаторными.

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

    Комбинаторика возникла в XVI веке. Теоретические исследования вопросов комбинаторики предприняли Паскаль и Ферма, Бернулли, Лейбниц и Эйлер и др.

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

1. при конструировании:
• для оптимального размещения элементов системы;
• для размещения микросхем на плате или элементов на кристалле;
• при трассировке (выборе маршрута);
2. синтезе схем и проектирования:
• при решении вопроса, какой набор стандартных микросхем выбрать, чтобы реализовать разработанную схему устройства;
• при разработке схемы на подсхемы для реализации различными блоками и т. д.;
3. при контроле, выбирая-перебирая последовательность тестирующих сигналов;
4. в организации систем, решая вопрос, каким выбрать оптимальный маршрут передачи информации по сети и т. п.

    Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от до где - число элементов множества.

    Всякое  конечное множество можно сделать  упорядоченным, если, например, переписать все элементы множества в некоторый  список ( .), а затем каждому элементу присвоить номер.

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

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

    Пример. Перестановки множества из 3-х элементов имеют вид .

    Число перестановок из элементов !

    Перестановка  с повторением

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

    Пусть - множество из элементов и - натуральные числа, такие, что их сумма равна , а .

    Каждый  упорядоченный набор  элементов содержащий элемент ровно раз ( ) называется перестановкамимножества с повторением:

    

    Примечание: при  получим перестановки множества из элементов без повторений.

    Перестановки  предметов, расположенных  в круг

    Упорядоченные -элементные подмножества множества из элементов называются размещениями из элементов по .

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

    

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

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

    В частном случае, когда  , имеем

    

Размещения  с повторением

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

    

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

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

    

    Сочетания с повторениями

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

    Число различных сочетаний из элементов по c повторениями равно

    

    Свойства  сочетаний

4. Заменяя на и на в соотношении 4, и помня, что , получаем, что

5. Частными случаями формулы 5 при являются следующие суммы рядов:
1. :

    

    

2. :

    

    

3. Аналогично для :

    

    

    

Следовательно,

    

С помощью формулы 7 легко найти сумму квадратов  натуральных чисел от до

    

Формула включения-исключения

    Разобранные примеры позволяют сформулировать общий закон.

    Пусть имеется  предметов , некоторые из которых обладают свойствами .

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

    Если  надо подчеркнуть , что берутся предметы , не обладающие некоторым свойством, то это свойство пишется со штрихами. Например: - количество предметов, обладающих свойством , но не обладающих свойством .

    В самом простом случае при одном  свойстве , где - общее число элементов, формула очевидна.

    Если  имеются два свойства , то

    

    Действительно , каждый элемент , обладающий свойствами и одновременно вычитается дважды, следовательно, к этой разности нужно добавить .

    Обобщением  этого правила является следующий  принцип включения-исключения:

    

    Задачи  с ограничением на порядок

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

    Задача 1. Укротитель хищных зверей хочет вывести на арену 5 львов и 4 тигра, при этом нельзя , чтобы два тигра шли друг за другом. Сколькими способами он может расположить зверей?

    Обозначим львов буквой Л. Для тигров имеется 6 мест.

    _____Л₁_____Л₂_____Л₃____Л₄_____Л₅______

    Львов можно расположить  ! Способами, то есть 120. На шести местах для тигров их можно расположить способами.

    Общее число способов .

    Для задачи в общем виде, если имеется: тигров и львов.

     , но так как  то

    

    Это возможно лишь при условии , что 

    Ограничения на порядок выбора

    Задача 1. На книжной полке стоят 12 книг. Сколькими способами можно выбрать 5 из них так, чтобы никакие две из них не стояли рядом.

    Зашифруем выбор 0 и 1: каждой оставленной книге  поставим в соответствие 0, каждой выбранной - 1. Таким образом, имеем 5 единиц и 7 нулей и задача сводится к предыдущей.

    

    В общем виде: Если стоит  книг, а выбирается книг, не стоящих рядом, то это можно сделать

    

    

    Общая задача о смещении

1. Число перестановок из элементов, при которых ни один элемент не остается в первоначальном положении:

2. Число перестановок ,в которых ровно элементов остаются на месте ,а остальные меняют свое положение выражается формулой

3. В самом деле сначала нужно выбрать какие именно элементов остаются на месте. Это можно сделать способами , а остальные переставлять.Это можно сделать способами. По правилу произведения получаем .
4. Сумма всех смещений равна

5. Число перестановок из элементов, при которых данные элементов смещены(остальные могут быть смещены, а могут оставаться на своих местах), выражается формулой.

    

 
    

1. Аналогично  доказывается ,что количество перестановок из чисел не содержащих ни одной из пар выражается формулой:

2. количество перестановок из элементов, в которые не входят заданные пар, равно

3. если , то