Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел. 7021 326, е-mail: ri@kture.kharkov.ua 1 СОЧЕТАНИЯ. РАЗМЕЩЕНИЯ. ЛЕКЦИЯ 17 С.В.ЧУМАЧЕНКО. - презентация

1 Харьковский национальный университет радиоэлектроники, кафедра АПВТ, тел , е-mail: 1 СОЧЕТАНИЯ. РАЗМЕЩЕНИЯ. ЛЕКЦИЯ 17 С.В.ЧУМАЧЕНКО Факультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭ ДИСКРЕТНАЯ МАТЕМАТИКА КОМБИНАТОРНЫЙ АНАЛИЗ

2 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 2 Содержание: Сочетания Геометрическая интерпретация чисел Количество подмножеств множества Размещения, их связь с перестановками Сочетания и размещения с повторениями Тема: Сочетания. Размещения Цель лекции – изучить комбинаторные конфигурации «сочетания» и «размещения», свойства и формулы подсчета их количества

3 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 3 Литература Глускин Л.М., Шор Л.А., Шварц В.Я. Задачи и алгоритмы комбинаторики, и теории графов. Донецк, ДПИ, с. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука, с. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики: Пер. с укр. М.: Главная редакция физико-математической литературы издательства Наука, с. Виленкин Н.Я. Индукция. Комбинаторика. М.: Просвещение, с. Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу Дискретна математика. Харків, ХНУРЕ С

4 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 4 Базовые понятия: Множество Бином Биномиальные коэффициенты и формула для них Перестановка Термины Ключевые слова: Сочетание Размещение Сочетание и размещение с повторением

5 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 5 Сочетания Def: произвольное k-элементное подмножество n-элементного множества называется сочетанием из n элементов по k. В сочетаниях порядок элементов не имеет значения. Иногда вместо слова сочетание используют термин комбинация. Число сочетаний из n элементов по k имеет смысл биномиальных коэффициентов, о которых шла речь ранее: Установлено, что число сочетаний из n элементов по k равно

6 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 6 Пример Сколькими способами можно выбрать 3 книги из 5 ? Количество способов определяется числом 3-элементных подмножеств множества из 5 элементов:

7 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 7 Геометрическая интерпретация чисел Рассмотрим прямоугольную сетку квадратов размерами (шахматный город – Манхеттен) Он состоит из прямоугольных кварталов, разделенных горизонтальными и вертикальными улицами) Каково число различных кратчайших путей на этой сетке, ведущих из левого нижнего угла – точки (0;0) – в правый верхний угол – точку (m,n) ? (0,0) (m,n)(m,n) (m,0) (0,n)

8 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 8 Любой кратчайший путь из точки (0; 0) в точку (m; n) состоит из m+n отрезков, из них m горизонтальных и n вертикальных (если не бродить по улицам туда-сюда). Общее количество путей равно числу способов, которыми из m+n можно выбрать n вертикальных: Наравне с этим можно рассматривать число способов выбора m горизонтальных отрезков из общего числа m+n: Итак, геометрически установлено равенство в справедливости которого нетрудно убедиться, вычисляя по формуле: Геометрическая интерпретация чисел Решение

9 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 9 Количество подмножеств данного множества – мощность булеана Сколько всего подмножеств имеет множество М, состоящее из n элементов? Булеан множества M содержит: – пустое множество ( ); – одноэлементных подмножеств; – двухэлементных подмножеств; – трехэлементных подмножеств; – k-элементных подмножеств; – одно n-элементное подмножество (M). Таким образом,.

10 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 10 Time-Out

11 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 11 Размещения. (Упорядоченные подмножества данного множества) Дано неупорядоченное множество М, состоящее из n элементов: | M | = n Таким образом, получим все упорядоченные k-элементные подмножества множества M. Составим подмножества данного множества M Число всех k-элементных подмножеств множества M равно Каждое такое подмножество может быть упорядочено каким-либо возможным способом Количество способов упорядочения каждого k-элементного множества k!

12 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 12 Размещения. Определение Def: упорядоченные k-элементные подмножества множества из n элементов называются размещениями из n элементов по k Различные размещения отличаются количеством элементов либо их порядком. Число различных размещений из n по k определяется следующей теоремой

13 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 13 Количество размещений. Связь с перестановками Теорема Число упорядоченных k-элементных подмножеств множества М, состоящего из n элементов, равно При k=n получаем количество перестановок/подстановок множества M.

14 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 14 Пример В турнире участвуют 8 команд. Сколько различных предсказаний (прогнозов) относительно первых трех первых мест по результатам соревнований можно сделать? Требуется определить число различных способов распределения трех первых мест при восьми командах, т.е. найти число различных размещений из 8 команд по 3: 1) Выбираем из 8 команд 3: 2) Эти три команды можно упорядочить 3! способами 3) Всего существует размещений

15 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 15 Размещения с повторениями и их количество Def: любой упорядоченный набор k элементов с повторениями из элементов множества M, содержащего n элементов, называется размещением с повторениями Число различных размещений с повторениями из n элементов по k определяется как n k Пример Число различных трехбуквенных слов, которые можно составить из 32 букв алфавита, есть

16 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 16 Сочетания с повторениями и их количество Объединим все размещения с повторением из n элементов по k, состоящие из одинакового количества одних и тех же элементов (без учета расположения), в классы эквивалентности. Каждый класс эквивалентности называется сочетанием с повторением из n элементов по k. Число различных сочетаний с повторением из n элементов по k равно Пример: определить количество результатов бросания двух одинаковых кубиков

17 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 17 Выводы: связь размещений и сочетаний Два размещения с повторениями или без принадлежат одному сочетанию с повторениями или без соответственно только тогда, когда существует перестановка множества {1,2,..,k} такая, что в результате одно размещение преобразуется в другое. Размещение из n элементов по k можно рассматривать как сочетание из этих k элементов, упорядоченное каким-либо способом

18 Сочетания. Размещения Декабрь, 2003 ХНУРЭ, факультет КИУ, кафедра АПВТ, тел , 18 Тест-вопросы 1. Являются ли сочетания с повторениями различными: МАМА, МАША? а) да; б) нет. 2. Являются ли сочетания с повторениями различными: ПАПА, АППА? а) да; б) нет. 3. Какие из сочетаний с повторениями являются различными? а) МАМА, МАША; б) ПАПА, АППА; в) ПАРА, РАПА. 4. Являются ли перестановки с повторениями различными: А А Б, А Б А? а) да;б) нет. 5. Являются ли перестановки с повторениями различными: А Б С, А Б А? а) да;б) нет. 6. Являются ли перестановки различными: А А Б, А Б А;А В С, А В А; а) да;б) нет. 7. Какие из размещений являются идентичными: а) abcba, abcba;б) abc, cba; в) abce, abc. 8. Какие из сочетаний являются идентичными: а) 123, 232;б) abc, cba;в) КСМ, МСК.