Открытый урок по дисциплине «Математика» Тема: «Комбинаторика» ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ ПОЛИТЕХНИЧЕСКИЙ ТЕХНИКУМ 2 (ГБОУ СПО ПТ 2 ) Преподаватель : Щепинова Л.С. Москва, 2014 г Москва, 2014 г.

ИСТОРИЯ ВОЗНИКНОВЕНИЯ КОМБИНАТОРИКИ Комбинаторика– раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Выбором объектов и расположением их в том или ином порядке приходится заниматься практически во всех областях человеческой деятельности. С аналогичными задачами, получившими название комбинаторных, люди столкнулись в глубокой древности (составление магических квадратов, теория фигурных чисел и т.д.) Комбинаторные задачи возникали и в связи с такими играми, как шашки, шахматы, карты и т.п. Комбинаторика становится наукой лишь в конце ΧΙΙ века – в период, когда возникла теория вероятностей (1). 2

СОЗДАТЕЛИ КОМБИНАТОРИКИ ДЖЕРОЛАМО КАРДАНО (1501 – 1576) – итальянский математик, философ, врач. Практикующий врач, читал лекции по математике в Миланском, Павийском и Болонском университетах. Сфера интересов: в алгебре – мнимые корни уравнений, в механике – вопросы передачи движения (карданные передачи). НИКОЛО ТАРТАЛЬЯ (1499 – 1557) – итальянский математик. Сфера интересов – арифметика, алгебра, геометрия, механика, баллистика. ГАЛИЛЕО ГАЛИЛЕЙ (1564 – 1642) – итальянский физик, механик, астроном и математик. БЛЕЗ ПАСКАЛЬ (1623 – 1662) французский математик, физик, философ и писатель. В 16 лет написал свою первую научную работу. 3

СОЗДАТЕЛИ КОМБИНАТОРИКИ ГОТФРИД ВИЛЬГЕЛЬМ ЛЕЙБНИЦ (1646 – 1716) – немецкий философ и математик. Первым рассматривал комбинаторику как самостоятельную ветвь науки. ПЬЕР ФЕРМА (1601 – 1665) французский математик. По профессии – юрист. Математикой занимался в свободное время. Полученные им математические результаты стали известны благодаря переписке и личному общению. ЛЕОНАРД ЭЙЛЕР (1707 – 1783) - математик, физик, механик, астроном. Щвейцарец по происхождению, большую часть жизни провел в России. Круг научных занятий – все разделы математики и механики, теория упругости, оптика, теория машин, картография, баллистика, морская наука, страховое дело, теория музыки и др (1). 4

n! = 1·2·3 … n, где n - натуральное число Решить уравнение: Решаем квадратное уравнение: Ответ: Принято считать, что 0! = 1 ПОНЯТИЕ ФАКТОРИАЛА Пример: Решение: 5

Пусть имеется множество, содержащее n элементов. Каждое упорядоченное его подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов Пусть имеется множество, состоящее из 5-ти элементов. Сколькими способами можно выбрать из него по 3 элемента ? Первый элемент можно выбрать пятью способами, второй – четырьмя, третий – тремя способами. Всего способов – 5·4·3 = 60. РАЗМЕЩЕНИЯ 6

или Аналогично, число размещений из n элементов по k элементов равно Полученную формулу можно представить в другом виде: Обозначение размещений происходит от французского слова Arrangement – размещение. РАЗМЕЩЕНИЯ 7

Задача 1 Группа учащихся изучает 7 учебных дисциплин. Сколькими способами можно составить расписание на среду, если в этот день должно быть 4 различных урока? Задача 2 В группе 12 человек. Сколькими способами можно выбрать старосту и заместителя старосты? ПРАКТИЧЕСКИЕ ЗАДАНИЯ 8

Размещения из n элементов по n элементов называются перестановками из n элементов. Обозначение перестановок происходит от французского слова Permutation – перестановка. ПЕРЕСТАНОВКИ 9

Пример 1 Сколько различных шестизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3,4, 5, 6 при условии, что в числе цифры не повторяются. Решение: Цифра 5 обязана стоять на последнем месте. Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое число равно числу перестановок из пяти элементов, т.е. 5!=1·2·3·4·5 = 120 Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое число равно числу перестановок из пяти элементов, т.е. 5!=1·2·3·4·5 = 120. Пример 2 Вычислить Вычислить : Решение: ПРАКТИЧЕСКИЕ ЗАДАНИЯ 10

Пример 3 Найти n, если Решение: ПРАКТИЧЕСКИЕ ЗАДАНИЯ 11

Пример 4 Из цифр составлены всевозможные четырехзначные числа так, что в каждом числе нет одинаковых цифр. Сколько получилось чисел? Сколько среди них четных чисел? Из цифр 0, 1, 2, 3 составлены всевозможные четырехзначные числа так, что в каждом числе нет одинаковых цифр. Сколько получилось чисел? Сколько среди них четных чисел? Решение: Число все возможных перестановок из четырех элементов равно. Из этого числа надо отнять число таких вариантов, когда цифра 0 стоит на первом месте. Таких вариантов будет. Итак, всего получилось чисел. Четное число получится, если в конце стоит либо цифра, либо цифра. Число все возможных перестановок из четырех элементов равно Р 4 = 1·2·3·4 = 24. Из этого числа надо отнять число таких вариантов, когда цифра 0 стоит на первом месте. Таких вариантов будет Р 3 = 1·2·3 = 6. Итак, всего получилось чисел N = 24 – 6 = 18. Четное число получится, если в конце стоит либо цифра 0, либо цифра 2. Если в конце стоит, то таких вариантов будет. Если же в конце стоит цифра, то из шести надо вычесть число вариантов, когда цифра стоит впереди. Таких вариантов будет Если в конце стоит 0, то таких вариантов будет m 1 = P 3 = 1·2·3 = 6. Если же в конце стоит цифра 2, то из шести надо вычесть число вариантов, когда цифра 0 стоит впереди. Таких вариантов будет. P 2 = 2! = 2. Т.е., число вариантов, когда стоит впереди, равно. Четных чисел будет. Т.е., число вариантов, когда 0 стоит впереди, равно m 2 = 6 – 2 = 4. Четных чисел будет m = m 1 +m 2 = 6 +4 = 10. ПРАКТИЧЕСКИЕ ЗАДАНИЯ 12

Пусть имеется множество, состоящее из n элементов. Каждое его подмножество, содержащее k элементов, называется сочетанием из n элементов по k элементов. Обозначение связано с французским словом Combinasion – сочетание. СОЧЕТАНИЯ 13

Пример Сколько матчей будет сыграно в футбольном чемпионате с участием команд, если каждые две команды встречаются между собой один раз? Сколько матчей будет сыграно в футбольном чемпионате с участием 16 команд, если каждые две команды встречаются между собой один раз? Решение: Свойства сочетаний 1) 2) ( k < n ). СОЧЕТАНИЯ 14

Формула Формула ( k < n ). позволяет последовательно находить сочетания. Например, положив получим положив n = 1, k = 0, получим С 2 1 = С С 1 0 = = 2; Еслито будем иметь Если n = 2, k = 0, то будем иметь С 3 1 = С С 2 0 = = 3; Если то будем иметь Если n = 2, k = 1, то будем иметь С 3 2 = С С 2 1 = = 3 ; Если то получим Если n = 3, k = 0, то получим С 4 1 = С С 3 0 = = 4; Если то получим Если n = 3, k = 1, то получим С 4 2 = С С 3 1 = = 6; Если то получим Если n = 3, k = 2, то получим С 4 3 = С С 3 2 = 1+ 3 = 4. СОЧЕТАНИЯ 15

Расположим числа в виде треугольной таблицы Расположим числа С n k в виде треугольной таблицы С 0 0 С 0 0 С 1 0 С 1 1 С 1 0 С 1 1 С 2 0 С 2 1 С 2 2 С 2 0 С 2 1 С 2 2 С 3 0 С 3 1 С 3 2 С 3 3 С 3 0 С 3 1 С 3 2 С 3 3 Можно заметить, что в начале и в конце каждой строки будут стоять единицы, так как, а любое другое число будет равно сумме двух чисел, стоящих над ним в предыдущей строке. Можно заметить, что в начале и в конце каждой строки будут стоять единицы, так как С n 0 = C n n = 1, а любое другое число будет равно сумме двух чисел, стоящих над ним в предыдущей строке. Эта таблица называется треугольником Паскаля. ТРЕУГОЛЬНИК ПАСКАЛЯ 16

Первые восемь строк треугольника Паскаля выглядят следующим образом: Таблицу можно продолжать дальше ТРЕУГОЛЬНИК ПАСКАЛЯ 17

Пример 1 Вычислить: Решение: Пример 2 Сколько диагоналей имеет выпуклый десятиугольник? Решение: Общее число отрезков, соединяющих вершины десятиугольника, включая стороны десятиугольника, равно числу сочетаний. Отсюда число Общее число отрезков, соединяющих вершины десятиугольника, включая стороны десятиугольника, равно числу сочетаний m = С 10 2 = 45. Отсюда число диагоналей равно. диагоналей равно 45 – 10 = 35. ПРАКТИЧЕСКИЕ ЗАДАНИЯ 18

Пример 3 Сколькими способами можно из группы, состоящей из четырех мужчин и трех женщин выбрать четыре человека так, чтобы среди них было не более двух женщин? Решение: Возможны три варианта выбора 1 вариант - 2 муж. и 2 жен. 2 вариант - 3 муж. и 1 жен. 3 вариант - 4 муж. и 0 жен. В первом варианте выбрать двух мужчин из четырех возможно способами, а двух женщин из трех - способами. В первом варианте выбрать двух мужчин из четырех возможно С 4 2 способами, а двух женщин из трех - С 3 2 способами. Всего способов в первом варианте - Всего способов в первом варианте - N 1 = C 4 2 ·C 3 2 = 6·3 =18. Во втором варианте выбрать трех мужчин из четырех можно способами, а одну женщину из трех - способами. Во втором варианте выбрать трех мужчин из четырех можно С 4 3 способами, а одну женщину из трех - С 3 1 способами. Всего способов во втором варианте Всего способов во втором варианте N 2 = C 4 3 ·C 3 1 = 4·3 = 12. В третьем варианте выбрать четырех мужчин из четырех можно способами, а 0 женщин из трех - способами. В третьем варианте выбрать четырех мужчин из четырех можно С 4 4 способами, а 0 женщин из трех - С 4 0 способами. Всего способов во втором варианте - Всего способов во втором варианте - N 3 = C 4 4 ·C 4 0 = 1·1 = 1. Всего способов Всего способов N = N 1 + N 2 + N 3 = = 31. ПРАКТИЧЕСКИЕ ЗАДАНИЯ 19

1. Найти область определения функции и множество ее значений Решение: Для того, чтобы заданная функция была определена, должны выполняться следующие условия: Для того, чтобы заданная функция была определена, должны выполняться следующие условия: 7 - x x – 3; x – 3 0; При этом выражения и должны быть либо натуральными, либо равными нулю. При этом выражения 7 – x и x – 3 должны быть либо натуральными, либо равными нулю. Решив неравенства, получимт.е., Решив неравенства, получим 3 x 5, т.е., x =3; 4; 5. Подставив полученные значения в функцию, Подставив полученные значения x в функцию,получим РАЗНЫЕ ЗАДАЧИ 20

2. На один ряд, в котором 8 стульев, рассаживаются 5 юношей и 3 девушки. Сколькими способами они могут сесть, чтобы не все девушки оказались сидящими рядом? Решение: 8 человек рассадить на 8 стульев можно Р 8 способами. Из этого числа надо вычесть число вариантов, когда девушки сидят рядом. Число таких вариантов будет равно числу перестановок из шести элементов (поскольку все девушки в этом случае объединяются в один условный элемент), умноженному на число перестановок из трех элементов (столькими способами девушки могут быть рассажены внутри этого условного элемента). Всего способов: N = P 8 – P 6 · P 3 = 8! - 6! ·3! = 6! · 7 · 8 – 6!·3! = 6!( 7 ·8 – 6) = РАЗНЫЕ ЗАДАЧИ 21

Задача 1 В розыгрыше первенства по футболу было сыграно 153 матча. Каждые две команды встречались между собой один раз. Сколько команд участвовало в розыгрыше первенства? Задача 2 Во взводе 3 сержанта и 30 солдат. Сколькими способами можно выделить одного сержанта и трех солдат для патрулирования? ЗАДАНИЕ НА ДОМ 22

1. Алгебра и начала анализа, часть 2. Математика для техникумов. Под редакцией Г.Н. Яковлева, М. «Наука», 1988 г. ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА 23