Элементы комбинаторики. МБОУ г. Мурманска гимназия 3 Шахова Татьяна Александровна

2 Рождение комбинаторики как раздела математики связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г. Лейбниц, Я. Бернулли и Л. Эйлер. Блез Паскаль Пьер Ферма Готфрид Лейбниц Якоб Бернулли Леонард Эйлер

3 Историческая справка. Блез Паскаль Паскаль доказал одну из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). Письма к провинциалу Паскаля явились шедевром французской классической прозы. 1623–1662

4 Историческая справка. Пьер Ферма 1601–1665 Французский математик, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел. По профессии юрист, с 1631 года советник парламента в Тулузе. Блестящий полиглот. Наиболее известен формулировкой Великой теоремы Ферма. Для любого натурального числа n >2 уравнение a n +b n =c n не имеет натуральных решений a, b, c. Доказательство, найденное в 1994 году Эндрю Уайлсом, содержит 129 страниц и опубликовано в журнале «Annals of Mathematics» в 1995 году.

5 Историческая справка. Готфрид Лейбниц Немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи. Описал двоичную систему счисления с цифрами 0 и 1, на которой основана современная компьютерная техника. 1646–1716

6 Историческая справка. Якоб Бернулли Швейцарский математик, профессор математики Базельского университета. Один из основателей теории вероятностей и математического анализа. Он изучил теорию вероятностей по книге Гюйгенса «О расчётах в азартной игре», в которой ещё не было определения и понятия вероятности (её заменяет количество благоприятных случаев). Якоб Бернулли ввёл значительную часть современных понятий теории вероятностей. Имя Якоба носит важное в комбинаторике распределение Бернулли. 1654–1705

7 Историческая справка. Леонард Эйлер 1707–1783 Швейцарский, немецкий и российский математик и механик, внёсший фундаментальный вклад в развитие этих наук (а также физики, астрономии и ряда прикладных наук). Эйлер автор более чем 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближённым вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др. Почти полжизни провёл в России, где внёс существенный вклад в становление российской науки. Некоторые из его потомков до сих пор живут в России.

8 Комбинаторика изучает вопросы о том, сколько комбинаций определенного типа можно составить из данных предметов (элементов). Мы рассмотрим некоторые способы таких подсчетов. 1) Перебор. 2) Дерево вариантов. 3) Комбинаторное правило умножения (подсчет размещений с повторениями). 4) Подсчет перестановок. 5) Подсчет размещений без повторений. 6) Подсчет сочетаний.

9 Перебор вариантов. 2) Сколько трехзначных чисел можно составить из цифр 0, 1, 2? Цифры могут повторяться ) Сколько трехзначных чисел можно составить из цифр 0, 1, 2? Цифры не могут повторяться Ответ: 4 Ответ: 16 В этой задаче от нас потребовалось больше внимания, чтобы не пропустить ни один вариант и не повторится

NNN Не пропустить ни один вариант и не повторится поможет дерево вариантов Ученик помнит, что в формуле азотной кислоты подряд идут буквы H, N, O и что есть один нижний индекс – то ли двойка, то ли тройка. а)Нарисуйте дерево возможных вариантов, из которых ученику придется выбирать ответ. 1-я буква 1-й индекс 2-я буква 2-й индекс 3-я буква 3-й индекс H 23 нет 23 OOOOO 23 6 комбинаций

N _ O _ N _ O _ 11 б)Нарисуйте дерево возможных вариантов, если ученик не помнит порядок букв. H 23 нет N 3 O NO 223 NONOHOHOHONHNHNH ____ ____ OO NN H H HH 2 3 _ 23 _ 23 _ 23 _ 23 _ 23 _ OO O OO O NN N NN N HH H HH H комбинаций

12 2. Сколько трехзначных чисел можно составить из цифр 2, 3, 4, 5. Цифры не повторяются A если цифры могут повторяться? А если число четырехзначное? Рисовать все дерево в этом случае очень неудобно. Но, оказывается, в этом нет необходимости.

13 Размещения с повторениями. Рассмотрим множество Х={х 1 ; х 2 …x n }. Будем выбирать из этого множества различные упорядоченные подмножества Y из k элементов. Если выбор элементов множества Y из Х происходит с возвращением, т.е. каждый элемент множества Х может быть выбран несколько раз, то такой выбор называется размещением с повторениями. Пример: Сколько пятизначных чисел можно составить используя цифры 7; 8; 9 (цифры могут повторяться)?

14 Как видим, в этой задаче перебор довольно затруднителен, как и построение дерева вариантов. Решим задачу иначе. На первом месте может стоять любая из трех цифр – 3 варианта. На втором месте может стоять любая из трех цифр – 3 варианта. На третьем месте может стоять любая из трех цифр – 3 варианта. На четвертом месте может стоять любая из трех цифр – 3 варианта. На пятом месте может стоять любая из трех цифр – 3 варианта. Число размещений с повторениями из n по k находится по формуле n k. Комбинаторное правило умножения

15 Перестановки. Рассмотрим множество Х={х 1 ; х 2 …x n }. Будем выбирать из этого множества различные упорядоченные подмножества Y из n элементов. Если выбор элементов множества Y из Х происходит без возвращения, т.е. каждый элемент множества Х может быть выбран только один раз, то такой выбор называется перестановкой. Пример: Сколько пятизначных чисел можно составить используя цифры 5; 6; 7; 8; 9 (цифры не могут повторяться)? Другими словами перестановка – это вариант упорядочивания данного множества.

16 На первом месте может стоять любая из пяти цифр – 5 вариантов. На втором месте может стоять любая из четырех оставшихся цифр – 4 варианта. На третьем месте может стоять любая из трех оставшихся цифр – 3 варианта. На четвертом месте может стоять любая из двух оставшихся цифр – 2 варианта. На пятом месте может стоять одна оставшаяся цифра– 1 вариант. Пример: Сколько пятизначных чисел можно составить используя цифры 5; 6; 7; 8; 9 (цифры не могут повторяться)?

17 Размещения без повторений. Рассмотрим множество Х={х 1 ; х 2 …x n }. Будем выбирать из этого множества различные упорядоченные подмножества Y из k элементов (k<n). Если выбор элементов множества Y из Х происходит без возвращения, т.е. каждый элемент множества Х может быть выбран только один раз, то такой выбор называется размещением без повторений или просто размещением. Пример: Сколько трехзначных чисел можно составить используя цифры 5; 6; 7; 8; 9 (цифры не могут повторяться)?

18 На первом месте может стоять любая из пяти цифр – 5 вариантов. На втором месте может стоять любая из четырех оставшихся цифр – 4 варианта. На третьем месте может стоять любая из трех оставшихся цифр – 3 варианта. Пример: Сколько трехзначных чисел можно составить используя цифры 5; 6; 7; 8; 9 (цифры не могут повторяться)?

19 Сочетания. Рассмотрим множество Х={х 1 ; х 2 …x n }. Будем выбирать из этого множества различные неупорядоченные подмножества Y из k элементов. Если выбор элементов множества Y из Х происходит без возвращения, т.е. каждый элемент множества Х может быть выбран только один раз, то такой выбор называется сочетанием. Пример: Учитель хочет назначить 3 учеников для уборки класса из 27 учеников. Сколькими способами можно это сделать?

20 Первый дежурный выбирается из 27 учеников. Второй – из 26 оставшихся. Третий – из 25 оставшихся. Но, порядок в тройках не имеет значения. Нужно убрать перестановки в тройках (разделить на P 3 ). Пример: Учитель хочет назначить 3 учеников для уборки класса из 27 учеников. Сколькими способами можно это сделать?

Дополнение. Симметричные перестановки. n различных объектов можно расположить по кругу (n-1)! способами. Пример: Сколькими способами можно усадить 6 человек за круглым столом, считая способы одинаковыми, если их можно получить один из другого движением по кругу? (n-1)!=(6-1)!=120

22 Решение задач. Чтобы научиться быстро бегать, нужно много бегать. Чтобы научиться хорошо решать сложные задачи, нужно решать много простых задач. И то, и другое надо делать с умом. Последовательно тренировать определенные группы мышц, и постепенно вникать в смысл математических выражений. Рассмотрим несколько очень простых задач, сравнивая их между собой. Сравнение поможет нам понять и запомнить, как выбрать нужную формулу для подсчёта числа вариантов в той или иной ситуации.

23 При окончании деловой встречи специалисты обменялись визитными карточками. Сколько всего визитных карточек перешло из рук в руки, если во встрече участвовали 6 специалистов? При встрече каждый из друзей пожал другому руку. Сколько всего было рукопожатий, если встретились 6 друзей? 1 Каждый из 6-ти специалистов отдал по 5 карточек (всем, кроме себя). Потребовалось 6·5 = 30 карточек. Ответ: друзей объединялись в группы по 2 без учёта порядка следования (сочетания.) Ответ: 15.

24 В хоровом кружке занимаются 9 человек. Необходимо выбрать двух солистов. Сколькими способами это можно сделать? В спортивной команде 9 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами это можно сделать? 2 Порядок в группе из 2-ух человек, выбранных из 9-ти, неважен (сочетания). Ответ: 36. Ответ: 72. Порядок в группе из 2-ух человек, выбранных из 9-ти, важен. Выборка: капитан- заместитель (размещения).

25 В меню столовой предложено на выбор 2 первых блюда, 6 вторых и 4 третьих блюда. Сколько различных вариантов обеда, состоящего из первого, второго и третьего блюда, можно составить? Имеется 6 видов овощей. Решено готовить салаты из трёх видов овощей. Сколько различных вариантов салатов можно приготовить? 3 Правило умножения. Ответ: 48. Ответ: 20. Чем отличается салат от обеда? Первое блюдо – 2 варианта Второе блюдо – 6 вариантов Третье блюдо – 4 варианта Очередность попадания овощей в общее блюдо не важна. Значит наши выборки это сочетания из 6 по 3.

26 В магазине продаются блокноты 7 разных видов и ручки 4 разных видов. Сколькими разными способами можно выбрать покупку из одного блокнота и одной ручки? В магазине продаются блокноты 7 разных видов и ручки 4 разных видов. Сколькими способами можно выбрать покупку из двух разных блокнотов и одной ручки? 4 Правило умножения. Ответ: 28. Ответ: 84. Ручка – 4 варианта Блокнот – 7 вариантов Ручка – 4 варианта Два блокнота – сочетание из 7 по 2 Далее - правило умножения.

27 Задачи с дополнительными условиями и ограничениями.

28 Имеется набор из 5 ручек разных цветов. Сколькими способами можно выбрать 3 ручки для обводки чертежа, если среди них обязательно должен быть красный цвет? 1 Если из 5 ручек надо выбрать 3, при этом одна из них должна быть красной, то выбирать придется из n = 5 1 = 4 элементов по k = 3 1 = 2 элемента. Таким образом, вместо C 5 3 надо считать C 4 2. Решение: Ответ: 6.

29 В группе из 20 студентов, среди которых 2 отличника, надо выбрать 4 человека для участия в конференции. Сколькими способами можно выбрать этих четверых, если отличники обязательно должны попасть на конференцию? 2 Решение: Итак, есть группа из n = 20 студентов. Но выбрать надо лишь k = 4 из них. Если бы не было дополнительных ограничений, то количество вариантов равнялось числу сочетаний C Однако нам поставили дополнительное условие: 2 отличника должны быть среди этих четырех. Таким образом мы уменьшаем числа n и k на 2. Имеем: Ответ: 153.

30 У Пети в кармане есть 8 монет, из которых 6 монет по рублю и 2 монеты по 10 рублей. Петя перекладывает какие-то три монеты в другой карман. Сколькими способами Петя может это сделать, если известно, что обе монеты по 10 рублей оказались в другом кармане? 3 Решение: Итак, есть n = 8 монет. Петя перекладывает k = 3 монеты, из которых 2 десятирублевые. Получается, что из 3 монет, которые будут переложены, 2 уже зафиксированы, поэтому числа n и k надо уменьшить на 2. Ответ: 6.

31 На книжной полке помещается 5 томов. Сколькими способами их можно расставить, чтобы при этом 1-й и 2-й тома стояли рядом? 4 Решение: Речь идет о перестановках с ограничениями. Представим сначала, что первый и второй том склеены. Тогда переставляются четыре объекта. Но на самом деле первый и второй том не склеены и тоже могут переставляться относительно друг друга. Такие перестановки независимы. Можно применить правило умножения: Ответ: 6.

32 Для тренировки воспользуйся задачником А. Г. Мордкович. Профильный уровень.

При создании презентации использованы ресурсы: