Презентация на тему "Комбинаторика"

Содержание

• 
  Слайд 1

  Комбинаторика

  Захарова В.Ф. Zakharova.vf@gmail.com

• 
  Слайд 2
  

  Общие правила комбинаторики Перестановки Размещения Сочетания. Свойства сочетаний

• 
  Слайд 3
  

  Combinare (лат.) – сочетать, соединять В науке и практике часто встречаются комбинаторные задачи, решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитать число комбинаций. Раздел математики, в котором рассматриваются комбинаторные задачи, называется комбинаторикой. Немного из истории: Комбинаторика возникла в XVI веке. В карты и кости выигрывались и проигрывались золото, бриллианты, дворцы и имения. Поэтому первые комбинаторные задачи касались в основном азартных игр.

• 
  Слайд 4

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

  Перебор возможных вариантов Пример: Из группы теннисистов, в которую входят пять человек - Антон, Борис, Виктор, Глеб и Дмитрий, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары? Дерево (граф) возможных вариантов Пример: Сколько трехзначных чисел можно составить из цифр 1, 3, 5 и 7, используя в записи числа каждую из них не более одного раза?

• 
  Слайд 5
  

  Комбинаторное правило умножения Пример: В меню столовой возможные первые блюда: борщ, щи, рассольник. На второе: гуляш, жаркое, голубцы, плов. Из напитков: чай, кофе, компот. Сколько различных обедов может заказать посетитель? В общем виде Пусть имеется n элементов (n1 возможных первых, n2 возможных вторых и т. д.) и требуется выбрать из них один за другим k элементов. Число способов , которыми могут быть выбраны все k элементов, равно произведению n1 ∙ n2 ∙ n3 ∙ … ∙ nк.

• 
  Слайд 6

  Примеры

  Из города А в город В ведут 5 дорог, а из города В в город С — 3 дороги. Сколько путей, проходящих через В, ведут из А в С? Имеется 5 видов конвертов без марок и 4 вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма? Сколькими способами можно выбрать гласную и согласную буквы из слова «камзол»? А из слова «здание»? Бросают игральную кость с 6 гранями и запускают волчок, имеющий 8 граней. Сколькими различными способами могут они упасть? На вершину горы ведут 5 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям. На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз? Сколькими способами можно указать на шахматной доске два квадрата — белый и черный? А если нет ограничений на цвет выбранных квадратов? Сколькими способами можно выбрать на шахматной доске белый и черный квадраты, не лежащие на одной и той же горизонтали и вертикали?

• 
  Слайд 7

  Факториал

  Произведение первых подряд идущих n натуральных чисел обозначают n! n! = 1 ∙2 ∙3 ∙… ∙ (n -2)∙ (n – 1)∙ n 1! = 1 2! = 1∙2 = 2 3! = 1∙2∙3 = 6 4! = 1∙2∙3∙4 = 24 5! = 1∙2∙3∙4∙5 = 120 6! = 5! ∙ 6 = 120 ∙ 6 = 720 7! = 6! ∙ 7 = 720 ∙7 = 5040

• 
  Слайд 8
  

  Полезные упражнения: 1. 2. 3. 4. 5. 6. 7. Что больше 6!∙5 или 5!∙6 ? 8. Что больше (n+1)!∙n или n!∙(n+1) ? 9. На сколько нулей оканчивается 10!, 15!, 25! ?

• 
  Слайд 9

  Перестановки

   Опр. Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке  Рn = n∙(n -1)∙(n – 2 )∙ …∙3∙2∙1=n! Рn = n! – формула количества всевозможных перестановок из n элементов Задача: Сколькими способами можно составить трехцветный  полосатый флаг, если имеется материал желтого, красного и синего цветов? 

• 
  Слайд 10
  

  1. Сколькими способами можно расставить 6 участниц финального забега на 6 беговых дорожках? 2. Сколькими способами 4 человека могут разместиться на четырехместной скамейке? 3. Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0,5,4,8 ? Р4 - Р3 = 4! – 3! = 24 – 6 = 18 4. Сколько пятизначных чисел содержат все цифры а) 1, 2, 3, 4, 5? б) 0, 2, 4, 6, 8? Какова сумма всех таких пятизначных чисел в каждом из пунктов?* 5. Сколько четных и сколько нечетных чисел можно составить перестановкой цифр из числа 3694? 6. Имеется 10 различных книг, из которых 3 – на французском языке. Сколькими способами их можно расставить на полке, при условии, что книги на французском языке должны стоять рядом? 7. Сколькими способами можно расставить на полке 4 книги по алгебре и 3 по геометрии так, чтобы книги по геометрии стояли рядом? 8. Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом? 9. Сколькими способами можно посадить на карусель 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом. Способы, переходящие друг в друга при вращении карусели, считаются совпадающими.

• 
  Слайд 11

  Размещения

  Опр. Размещением из n элементов по k (k ≤n) называется любое множество, состоящее из k элементов, взятых в определенном порядке из данных  n элементов. Аnk =  Задача: Сколькими способами можно составить 3х-цветный  полосатый флаг, если имеется материал 5 разных цветов цветов? Частный случай n=k : Аnn = Pn = n! Перестановки – частный случай размещений

• 
  Слайд 12
  

  Пример 1. Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета Решение: А84 = 5 ∙ 6 ∙ 7 ∙ 8 = 1680 Пример 2. Сколько трехзначных чисел (без повторения цифр в записи числа) можно составить из цифр 0,1,2,3,4,5? Решение: А63 - А52 =  4 ∙ 5 ∙ 6 - 4 ∙ 5 = 120-20=100. Пример 3. Сколько существует трехзначных чисел (без повторения цифр в записи числа)? Решение: А103 - А92 =  8 ∙9 ∙10 - 8 ∙9 = 720-72=648.

• 
  Слайд 13
  

  В организацию избрано 9 человек. Из них надо избрать председателя, его заместителя и секретаря. Сколькими способами это можно сделать? Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, французского, немецкого, итальянского, на любой  другой из этих пяти языков? Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов? Та же задача, если одна из полос должна быть красной? Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1,3,5,7,9? б) 0,2,4,6,8? Какова сумма всех таких пятизначных чисел в каждом из пунктов?

• 
  Слайд 14

  Сочетания

  Задача: Сколькими способами можно выбрать из 5 человек 3 дежурных? Опр. Сочетанием из n элементов по k (k ≤n) называется любое множество, состоящее из k элементов, взятых из данных  n элементов. (порядок не важен!) Сnk = Аnk : Рk , Сnk = 

• 
  Слайд 15
  

  Пример 1. На первенстве мира по футболу в отборочной группе 6 команд. Продолжат соревнования только две из них. Сколько разных вариантов прохождения команд? Решение : С62 = (6 ∙ 5) : (1∙ 2 ) = 15 Пример 2. В классе учатся 12 мальчиков и 10 девочек. Для уборки территории около школы требуется выделить трех мальчиков и двух девочек. Сколькими способами можно сделать этот выбор? Решение: С123 ∙ С102 =  (12 ∙11 ∙ 10) : (1∙ 2 ∙ 3) ∙ (10 ∙ 9) : (1∙ 2) = 220 ∙ 45 = 9900

• 
  Слайд 16
  

  Встретились 6 друзей и каждый пожал руку каждому своему другу. Сколько было рукопожатий? В шахматном турнире участвуют 9 человек. Каждый из них сыграл с каждым по одной партии. Сколько всего партий было сыграно? Сколько диагоналей можно провести в выпуклом 7-угольнике? n-ке? В библиотеке читателю предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами он может выбрать из них 3 книги и 2 журнала? Из вазы с фруктами, где лежат 9 яблок и 6 груш, нужно выбрать 3 яблока и 2 груши. Сколькими способами можно это сделать? Из лаборатории, в которой работают заведующий и 10 сотрудников, надо отправить 5 человек в командировку. Сколькими способами это можно сделать, если: а)заведующий лабораторией должен ехать в командировку; б)заведующий лабораторией должен остаться? На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений. Сколькими способами читатель может выбрать 3 книги, если: а) словарь нужен ему обязательно; б) словарь ему не нужен? 

• 
  Слайд 17
  

  У мамы 2 яблока и 3 груши. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано? У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано? Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз? Во скольких случаях ровно один туз? Во скольких случаях не менее двух тузов? Ровно два туза?

• 
  Слайд 18

  Свойства сочетаний

• 
  Слайд 19

  Треугольник паскаля. Бином Ньютона

• 
  Слайд 20

  Свойства сочетаний

  Примеры: 1. Разложите (a+b)8 2. Найдите пятый член разложения (a-b)9 3. В разложении (1+x)n четвертый член равен 0,96. Найти значения x и n, если сумма биномиальных коэффициентов равна 1024.

• 
  Слайд 21

  Использованная литература

  Макарычев Ю. Н. Алгебра : элементы статистики и теории вероятностей : учеб. пособие для учащихся 7—9 кл. общеобразоват. учреждений / Ю. Н. Макарычев, Н. Г. Миндюк; под ред. С. А. Теляковского. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. - М.: ФИМА, МЦНМО, 2006. - 400 с.