Дистанционный курс "Комбинаторика"

ГАПОУ МО «Подмосковный колледж «Энергия» Тема 1: Сочетания. Размещения.  Перестановки. Дистанционный курс по математике для  студентов 1 курса Преподаватель: Добрынина Н.В.

КОМБИНАТОРИКА  Занимается задачами о существовании и подсчете  различных комбинаций, которые можно составлять  и элементов заданного конечного множества.

Задача: На какую сумму очков выгоднее  поставить ставку, если очки выпадают  при подбрасывании двух игральных  костей?

Решение: Сумма  очков Число  способов Возможные варианты 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 5 4 3 2 1 1 + 1 1 + 2; 2 + 1 1 + 3; 3 + 1; 2 + 2 1 + 4; 4 + 1; 2 + 3; 3 + 2 1 + 5; 5 + 1; 2 + 4; 4 + 2; 3 + 3 1 + 6; 6 + 1; 2 + 5; 5 + 2; 3 + 4; 4 + 3 2 + 6; 6 + 2; 3 + 5; 5 + 3; 4 + 4 3 + 6; 6 + 3; 4 + 5; 5 + 4 4 + 6; 6 + 4; 5 + 5 5 + 6; 6 + 5 6 + 6 1. Рассмотрим возможные  варианты. 2. Представим  полученные результаты  в таблице. 3. Видно, что   целесообразно сделать  ставку на выпадение   сумме 7 очков,  поскольку она  получается наибольшим  количеством вариантов. Ответ: 7.

ФАКТОРИАЛ ЧИСЛА N ­ произведение всех натуральных  чисел от 1 до n, включая n.

ПРИМЕР: 5! Решение: 5! = 1*2*3*4*5= 120

ПРИМЕР:  Решение:

ПРИМЕР: Решение:

Основные формулы  комбинаторики

ПЕРЕСТАНОВКИ Перестановками  из  n  различных  элементов  называются  все  возможные  последовательности  этих элементов. Pn­ перестановка . {a, b, c} – множество элементов Перестановки: abc, acb, bac, bca, cab, cba. Pn=n! P3=3!=1*2*3= 6

ПЕРЕСТАНОВКИ с  повторениями  из  n  Перестановками  элементов  k  типов,  причем  1  типа  –  n1  штук,  2  типа  –  n2  штук,  3  типа  –  n3  штук  и  так  далее,  называются  все  возможные  последовательности  исходных элементов .  {a, b, а} – множество элементов Перестановки: aаb, baа, аba.

ЗАДАЧА:  Сколькими способами можно переставить  буквы в слове «ананас»?

Решение: Всего букв 6.  Из них одинаковы n1«а»=3, n2«н»=2, n3«с»=1.

РАЗМЕЩЕНИЯ взятых  из  исходного  множества,  Размещениями  из  n  различных  элементов  по  m  элементов,    называются  все  возможные  последовательности  из  m  элементов,  которые  отличаются  составом  элементов  или порядком их следования. (Аnm) {a, b, c} – множество элементов Размещения: ab, ac, bc, ba, cb, ca.

РАЗМЕЩЕНИЯ Размещениями  с  повторениями  из  элементов  n  различных  типов  по  m  элементов,  взятых  из  исходного  множества,  возможные  которые  последовательности  отличаются  составом  элементов  или  порядком  их  следования. (Аnm) называются  все    из  m  элементов,  {a, b, c} – множество элементов Размещения: ab, aa, ba, bb, cb, ca, ac, cc, bc.

СОЧЕТАНИЯ Сочетаниями  из  n  различных  элементов  по  m  элементов  называются  все  такие  последовательности  из m элементов, взятых из исходного множества. (Cnm) {a, b, c} – множество элементов Сочетания: ab, cb, ac.

Задача: В первенстве по футболу участвует 16  команд, причем любые 2 играют между собой  1 матч. Сколько игр будет сыграно?

Решение: n=16, m= 2

СОЧЕТАНИЯ Сочетаниями  c  повторениями  из  n  различных  элементов  по  m  элементов  называются  все  такие  последовательности  из  m  элементов,  взятых  из  исходного множества. (Cnm) {a, b, c} – множество элементов Сочетания: ab, cb, ac, aa, bb, cc.

Задача: В кондитерской имеется 5 различных  видов пирожных. Сколькими способами  можно составить набор из4 пирожных?

Решение: n= 5, m=4

Замечания: • При  использовании  в  задаче  формул  исходного  элементов  перестановок  множества не происходит выбор. из  порядок  •   Сочетания  применяются  в  задачах,  где  не  элементов.  важен  порядок  Размещения  следования  элементов  имеет  принципиальное  значение. применяются,  следования  где

Схема решения комбинаторных задач Перестановка Начало Есть ли в задаче  выбор? ДА Размещение Могут ли элементы  повторяться? Важен ли  порядок? НЕТ Сочетание С повтором Без повтора

6:  Сколькими  Задача  способами  можно  раскрасить  столбцов  из  четырехцветной ручкой так, чтобы каждый столбец  был окрашен в определенный цвет. диаграмму  4  Решение: Pn =n! = 4! = 1234 = 24.

Задача 7:  Имеется 5 кружков: 3 белых и 2 черных.  Сколько различных узоров можно получить,  располагая кружки в ряд. .

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

Задача 9: На железнодорожной станции имеется  5 светофоров. Сколько может быть дано  различных комбинаций их сигналов, если  каждый светофор имеет 3 состояния.

Задача  10:  12  человек  играли  в  городки.  Сколькими  способами  они  могут  разбиться  на  команды по 4 человека в каждой.

.  Задача  11:    В  цветочном  магазине  продаются  цветы  6  видов.  Сколько  можно  составить  букетов  из 10 цветов в каждом (букеты отличающиеся лишь  расположением цветов считать одинаковыми). .

11  и  хорошистов  Задача 12: В группе 20 студентов, из которых 5  остальные  отличников,  троечники.  Сколькими  способами  можно  выбрать  группу  для  выполнения  лабораторной  работы,  состоящей  из  3  хорошистов,  1  отличника  и  1  троечника. 165*5*4=3300

Задача 13: Имеется 4 чашки, 5 блюдец, 6 ложек  (все  чашки,  блюдца,  ложки  различны).  Сколькими  способами  можно  накрыть  стол  к  чаю  на  3  человека, если каждый получает 1 чашку, 1 блюдце  и 1 ложку. 24*60*120= 172800

Список литературы: 1. Новоселов  О.В.  Комбинаторика  и  вероятность:  учебн.  пособие  для  слушателей  подготовит.  курсов / О. В. Новоселов, Л.П. Скиба. СибГАУ,  Красноярск, 2009. – 78 с. 2. Филимонова  Л.В.,  Быкова  Е.А.  Математика  и  информатика.  Учебное  пособие  (для  студентов  гуманитарных  факультетов  ВУЗов).  –  2­е  изд.  Дополненное и переработанное – Елец, ЕГУ им.  И.А. Бунина, 2001, 110 с. 3. http://math4school.ru/elementy_kombinatoriki

Спасибо за внимание!