Примеры комбинаторных задач Перестановки Перестановки Размещения Размещения Сочетания Сочетания. - презентация

1 Примеры комбинаторных задач Перестановки Перестановки Размещения Размещения Сочетания Сочетания

2 Перебор возможных вариантов Пример 1. Из группы теннисистов, в которую входят четыре человека Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары? Составим сначала все пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий). Получим три пары: АГ, АС, АФ. Пары, в которые входит Григорьев, но не входит Антонов: ГС, ГФ. Пары, в которые входит Сергеев, но не входят Антонов и Григорьев: СФ. Других вариантов составления пар нет, так как все пары, в которые входит Федоров, уже составлены. Итак, мы получили шесть пар: АГ, АС, АФ, ГС, ГФ, СФ. Значит, всего существует шесть вариантов выбора тренером пары теннисистов из данной группы. Способ рассуждений, которым мы воспользовались при решении задачи, называют перебором возможных вариантов.

3 Перестановки Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки. Пример. Пусть имеются три книги. Обозначим их буквами а, Ъ и с. Эти книги можно расставить на полке по-разному. буквами а, Ъ и с. Эти книги можно расставить на полке по-разному. Если первой поставить книгу а, то возможны такие расположения книг: abc, acb. Если первой поставить книгу Ь, то возможными являются такие расположения:bac, bca. И наконец, если первой поставить книгу с, то получим такие расположения:cab, cba. Каждое из этих расположений называют перестановкой из трех элементов.

4 Перестановки Р n =1* 2*3* (n-2)(n- 1) n Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке. Задача. Сколькими способами 4 человека могут разместиться на четырехместной скамейке ?

5 Размещения Пусть имеется 4 шара(обозначим a,b,c,d) и 3 пустые ячейки. Одна из возможных троек: ячейки. Одна из возможных троек: Выбирая по-разному 1-й, 2-й и 3-й шары, получаем различные упорядоченные тройки шаров, например: Каждую упорядоченную тройку, которую можно составить из 4- х элементов, называют размещением из 4-х элементов по 3. abc cabbacdcb

6 Размещения Размещением из n элементов по k (k

7 Сочетания Пусть имеются 5 гвоздик разного цвета. Обозначим их a,b,c,d,e. Требуется составить букет из 3-х цветов. Если в букет входит цветок а, то можно составить такие букеты: Если в букет входит цветок а, то можно составить такие букеты: abc,abd,abe,acd,ace,ade. abc,abd,abe,acd,ace,ade. Если в букет не входит а, но входит гвоздика b, то такие : bcd,bce,bde. bcd,bce,bde. Наконец, если в букет входят ни а, ни b,то возможен только 1 вариант составления букета: cde. cde. Мы указали все возможные способы составления букетов, в котором по-разному сочетаются 3 гвоздики из данных 5. Это сочетания из 5 элементов по 3. Это сочетания из 5 элементов по 3.

8 Сочетания Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов. Задача. Из 15 членов туристической группы надо выбрать трех дежурных. Сколькими надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор? способами можно сделать этот выбор?

9 Контрольные вопросы 1. Объясните, в чем состоит комбинаторное правило умножения, используемое для подсчета числа возможных вариантов. 2. Что называется перестановкой из n элементов? Запишите правило для вычисления числа перестановок из n элементов. Какой смысл имеет запись n !? 3. Что называется размещением из n элементов по к ? Запишите формулу. 4. Что называется сочетанием из n элементов по к ? Запишите формулу. по к ? Запишите формулу.