Презентация на тему Правила суммы и произведения. Перестановки и подстановки

понятиями комбинаторного анализа

алгоритмы комбинаторики, и теории графов. Донецк, ДПИ, 1982. 368

с.
Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука, 1977. С.170-184.
Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики: Пер. с укр. М.: Главная редакция физико-математической литературы издательства Наука, 1977. 80 с.
Виленкин Н.Я. Индукция. Комбинаторика. М.: Просвещение, 1976. 48 с.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. С.63-67.

подстановки
Цикл
Симметрическая группа подстановок

Во многих математических исследованиях встречаются комбинаторные задачи –

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

Без учета влияния случайных явлений человек становится бессильным

направлять развитие интересующих его процессов в желательном для него направлении
Б.В.Гнеденко

Комбинаторика занимается различного рода сочетаниями (соединениями), которые

можно образовать из элементов некоторого конечного множества.
Термин «комбинаторика» происходит от латинского слова combina − сочетать, соединять.
Некоторые элементы комбинаторики были известны в Индии еще во II веке до н.э. Предполагают, что индусы изучали соединения в связи с применением их в поэтике – науке о структуре поэтических произведений. Они подсчитывали возможные сочетания ударных и безударных слогов стопы, состоящей из n слогов.
В древней Индии, Средней Азии и Китае была известна частично таблица биномиальных коэффициентов.

Как научная дисциплина комбинаторика сформировалась лишь в

XVII веке.
Термин «комбинаторика» стал употребляться после опубликования немецким ученым Г.В. Лейбницем в 1666 г. работы «Рассуждение о комбинаторном искусстве», в котором впервые дано научное обоснование теории сочетаний и перестановок.
Изучением размещений занимался швейцарский математик Якоб Бернулли. Результаты он опубликовал в своей книге «Искусство предугадывания» (1713). Он ввел также термин «перестановка».
Термин «сочетание» применял французский математик и философ Блез Паскаль.

представлено объединением попарно непересекающихся подмножеств M1, M2, …, Mn.

Тогда

М=М1∪М2∪…∪Mn , Mi∩Mj=∅, i≠j.

Комбинаторная формулировка: пусть
объект a1 может быть выбран m1 способами;
объект a2 может быть выбран m2 способами;
……………………………………………..
объект an может быть выбран mn способами.
Тогда выбор объекта a1, либо объекта a2, … , либо объекта an может быть осуществлен m1+m2+…+mn способами.

суток отправляются 6 поездов, 4 автобуса и 1 самолет.

Сколько существует способов добраться до Киева?








Решение. По правилу суммы всего существует 6+4+1=11 способов выехать из Харькова в Киев.

Харьков

Киев

Mn – конечные множества, М=М1×М2×…×Mn – их декартово произведение.
Тогда

|М|=|М1×М2×…×Mn|=|M1|·|M2|·…|Mn|.
Комбинаторная формулировка: пусть
объект a1 выбирается m1 способами;
объект a2 выбирается m2 способами;
……………………………………………..
объект an выбирается mn способами,
при этом выбор объекта ai на влияет на число способов выбора остальных объектов.
Тогда выбор упорядоченного множества объектов (a1,a2,…,an) может быть осуществлен m1·m2·…·mn способами.

и 2 юноши.
Сколько танцующих пар они могут

составить (не одновременно)?
По правилу произведения можно составить 3·2=6 пар. Решение можно представить в виде диаграммы (графа), иллюстрирующего декартово произведение множеств:

n элементов.
Они могут быть перенумерованы при помощи

первых n натуральных чисел 1, 2, ... , n.
Поскольку в интересующих нас вопросах индивидуальные свойства элементов не будут иметь значения, то можно рассматривать в качестве элементов сами числа 1, 2, ... , n: M={1, 2, ... , n}.
Def: каждая последовательность n различных элементов с учетом порядка называется перестановкой этих элементов (перестановкой из n элементов)

2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1,

2
3, 2, 1

множества M отличаются друг от друга только порядком входящих

в них элементов.
Число всех различных перестановок из n элементов равно произведению 1·2·3·…·n=n! (“эн-факториал”).
Пример
Сколькими способами можно расставить на полке 10 различных книг?
Существует 10! различных способов расстановки книг:
10!=3 628 800

из n элементов на себя называется подстановкой степени n.

Пример
Запишем одну под другой две перестановки из 5 cимволов:




Под числом 3 стоит число 5; под 5 – 2; и т.д.
Говорят, что при отображении π5 число 3 переходит в 5, 5 – в 2 и т.д., 4 остается на месте – неподвижная точка подстановки.

все элементы, называется тождественной:





Все точки тождественной подстановки неподвижные.

подстановка элементов множества M:



где {s1,s2,…,sn} – перестановка из элементов

множества М, πn(i)=si, ∀i∈{1,2,…,n}.
Определим произведение двух подстановок из n элементов как последовательное проведение обоих преобразований:

и

Решение:




Определим произведение в обратном порядке:

только совместимые подстановки.
Умножение подстановок n-й степени при n≥3 не

является коммутативным:

n элементов множества М произведение есть однозначно определенная подстановка:

2. Произведение подстановок ассоциативно, но не коммутативно:


3. Для тождественной подстановки имеют место равенства:


4. Каждая подстановка имеет обратную:


Таким образом, все подстановки элементов множества М образуют
группу, порядок которой n! (порядок определяет запас элементов).
Эта группа называется симметрической группой Sn.

как:

элементов множества M={1,2,…n} встречаются два столбца



для которых si

ti>tj (или si>sj, tiDef: подстановка называется четной или нечетной в зависимости от того, четно или нечетно число встречающихся в ней инверсий.

можно привести к виду

,

то πn задает взаимно-однозначное отображение

множества {s1,s2,…,sr} на себя, которое называется циклом длины r.
Каждой неподвижной точке соответствует цикл длины 1.
Каждую подстановку можно однозначно представить в виде произведения циклов, не имеющих общих элементов.

n элементов. Требуется представить множество М в виде объединения

m попарно непересекающихся подмножеств M=M1∪M2∪…∪Mm
так, чтобы |M1|=k1, |M2|=k2, ..., |Mm|=km, где ki – заданные числа, причем

.

Сколькими способами можно получить такое разложение?

km – натуральные числа такие, что k1+k2+…+km =n. Число

способов, которыми можно представить множество M из n элементов в виде объединения m попарно непересекающихся множеств , количество элементов которых составляет соответственно k1, k2, …, km, равно