Бойкова_АВ_Комбинаторные задачи

Элементы комбинаторики 9 ­11 классы, МКОУ Кармаклинская СОШ учитель Бойкова  А.В. 1

Основные вопросы: I. Что такое комбинаторика?    Какие задачи считают комбинаторными? II. Перестановки III. Размещения  IV. Сочетания 2

Не будем спорить - будем вычислять. Г. Л е й б н и ц • Комбинаторика – радел математики, в  котором рассматриваются задачи о подсчёте числа  комбинаций составленных по определённым  правилам. 3

II. Какие задачи считают  комбинаторными? Комбинаторные задачи Задачи подсчёта числа комбинаций из конечного  числа элементов • Комбинаторика – от латинского слова  combinare, что означает «соединять, сочетать». • Методы комбинаторики находят широкое  применение в физике, химии, биологии, экономики  и др. областях знания. • Комбинаторику можно рассматривать как  часть теории множеств – любую комбинаторную  задачу можно свести к задаче о конечных  множествах и их отображениях. 4

I. Уровни решения комбинаторных задач 1. Начальный уровень.  Задачи поиска хотя бы одного решения, хотя бы одного  расположения объектов, обладающих заданным  свойствами ­ отыскание такого расположения десяти точек на пяти  отрезках, при      котором на каждом отрезке лежит по  четыре точки;  ­  такого расположения восьми ферзей на шахматной доске,  при котором они не бьют друг друга.  Иногда удаётся доказать, что данная задача не имеет  решения  (например, нельзя расположить 10 шаров в 9 урнах так, что бы в каждой урне было  не более одного шара – хотя бы в  одной урне окажется не менее двух шаров). 5

2. Второй уровень.  Если комбинаторная задача имеет несколько решений, то  возникает вопрос о подсчете числа таких решений,  описании всех решений данной задачи. • 3. Третий уровень.     Решения данной комбинаторной задачи отличаются друг от  друга некоторыми параметрами. В этом случае возникает  вопрос отыскания оптимального варианта решения такой  задачи. Например:  Путешественник хочет выехать из города А, посетить  города В, С, и D. После чего вернуться в город А. 6

На рис. изображена схема путей, связывающих эти города.  Различные варианты путешествий отличаются друг от друга  порядком посещения городов В, С, и .D. Существует шесть  вариантов путешествия. В таблице указаны варианты и длин  каждого пути: Путь Длина пути Путь Длина пути ABCDA ABDCA ACBDA 300 1555 1300 1450 А 200 ACDBA ADBCA ADCBA 500 400 1300 1450 1550 @ Gryznova A.K. С 400 7 D В 350

• Комбинаторные задачи на  оптимизацию приходится решать  мастеру, стремящемуся к  быстрейшему выполнению задания,  агроному, стремящемуся к  наивысшей урожайности на данных  полях, и т.д. 8

• Мы будем рассматривать лишь задачи  о подсчёте числа решений  комбинаторной задачи.  Этот раздел комбинаторики,  называемый теорией перечислений,  тесно связан с теорией вероятностей.  9

Правила суммы и произведения • 1. Сколько различных коктейлей можно составить  из четырёх напитков, смешивая их в равных  количествах по два?                    AB, AC, AD, BC, BD, CD – всего 6 коктейлей А В • D С • 2. Сколько различных двузначных чисел можно составить из  цифр     0, 1, 2, 3 ? Первой цифрой двузначного числа может одна из цифр  1, 2, 3 (цифра 0 не   может быть первой). Если первая цифра выбрана, то вторая может быть любая из  цифр 0, 1, 2, 3. Т.к. каждой выбранной первой соответствует  четыре способа   выбора второй, то всего имеется               4 + 4 + 4 = 4∙3 = 12    различных двузначных чисел. 10

• 2. Сколько различных двузначных чисел можно составить из цифр     0, 1, 2, 3  ?             4 + 4 + 4 = 43 = 12    различных двузначных чисел. • Первая цифра                                вторая цифра • • • 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 11

Правило произведения: • Если элемент А можно выбрать из  множества элементов п способами и для  каждого такого выбора элемент В  можно выбрать  т способами, то два  элемента (пару) А и В можно выбрать  п∙т способами. @ Gryznova A.K. 12

«Примеры решения комбинаторных задач: перебор вариантов,  правило суммы, правило умножения». 1. Сколькими способами могут быть расставлены 4 участниц финального  забега на четырёх беговых дорожках? Рп = 4∙ 3 ∙2 ∙1= 24 способа   (перестановки из 4­х элементов)      1 2 3 4 1 дорожка          2         3        4          1        3     4              1       2       4 1       2     3 2 доржка 3    4   2     4    2   3 3    4   1    4  3   1 2   4   1  4   1  2 2  3   1  3   1  2 3доржка 4  3    4      2   3    2 4     3   4    1   1   3 4  2   4  1   2  1 3   2   3  1   2    1 4 дор. Р е ш е н о    п е р е б о р о м    в а р и а н т о в 13

II. Перестановки (1) К в а р т е т                  Проказница Мартышка,                                             Осёл,                                                         Козёл                  Да косолапый Мишка                   Затеяли сыграть Квартет. …………………………………………………….                 Ударили в смычки, дерут, а толку нет.               «Стой, братцы, стой! ­ кричит Мартышка. –                                                         Погодите!               Как музыке идти? Ведь вы не так сидите» 4∙3∙2∙1 = 4!    способов 14

II. Перестановки (2) • Перестановкой из п ­ элементов называется  комбинации, отличающиеся друг от друга  лишь порядком следования элементов permutation­ перестановка) • Рп­ число перестановок (Р первая буква французского слова      Рп= n∙(n­1)∙(n­2)∙(n­3)∙(n­4)∙. . .∙3 ∙2 ∙1= n! Рп = n! В математике принято считать   0! =1   и  1! = 1 15

Размещения   (1) • Четыре попутчик решили обменяться визитными карточками.  Сколько всего карточек при этом было использовано? 2                             получилось 12 карточек. Каждый из четырёх                             попутчиков вручил визитку каждому из                              трёх попутчиков                                4  ∙  3  = 12 1 3 4 Комбинации, составленные из k элементов, взятых из n элементов, и   отличающиеся друг от друга либо составом, либо порядком  расположения элементов, называются размещениями из n  элементов по k (0< k ≤n ). Ak n          ­    размещение из n элементов по k элементов. А первая буква               французского слова arrangement : «размещение»,                 «приведение в порядок» 16

Размещения   (2)  • Пуст имеется 4 шара и 3 пустых ячейки. Обозначим шары  буквами a, b, c, d. В пустые ячейки можно по разному разместить  три шара из этого набора. • Выбирая по­разному первый, второй и третий шары, будем  получать различные упорядоченные тройки шаров a b c d b c a c b b a c • Каждая упорядоченная тройка, которую можно составить  из четырёх элементов называется  размещением из  четырёх элементов по три nnAk  n   1 n   2 n   2  n ...   k   1 . 17

Размещения   (3) • Сколько же размещений можно  составить из 4­х элементов  (abcd)  по  три?   abc      abd      acb      acd      adb      adc • •   bac      bad      bca      bcd      bda      bdc  •   cab      cad      cba      cbd      cda      cdb •    dab     dac      dba      dbc      dca      dcb A 234 3 4 Р е ш е н о    п е р е б о р о м    в а р и а н т о в n n A   !n P n 18

Размещения   (4) • Можно решить и не выписывая самих размещений: • первый элемент можно выбрать четырьмя способами, так  им может быть любой элемент из четырёх; • для каждого первого второй можно выбрать тремя  способами; • для каждых первых двух можно двумя способами выбрать  третий элемент из двух оставшихся. Получаем A3 4 = 4∙3∙2 = 24 Решено  с  использованием      п р а в и л а    у м н о ж е ни  я 19

Сочетания • Сочетанием из  п элементов по  k называют  любое множество, составленное из  k   элементов, выбранных из  п  элементов   nn  1 Ck n     2 n kn...  321 k...  1   C k n  !  п   !  knk  !  В отличии от размещений в сочетаниях не имеет  значение порядок элементов. Два сочетания  отличаются друг от друга хотя бы одним  элементом 20

Р е ш и   з а д а ч и: 1.    На плоскости отмечено 5 точек.      Сколько получится отрезков, если соединить  точки попарно?  C 2 5  54321       (3! 21 ! 25! 2 ) ! 5    543     52   321 10 2. На окружности отмечено  п точек. Сколько  существует треугольников с вершинами в этих  точках? 3 C п  (! 3  п 321 !  п(       п ! 3)­  п() ...  32(1321 2 п...( 3  п()  3)) 1  п)  п(    1  п)  2 п()  321 21

Источники информации 1. В.Ф.Бутузов, Ю.М.Колягин, Г.Л. Луканкин, Э.Г.Позняк и др. «Математика» учебное пособие для 11кл общеобразовательных учреждений /рекомендовано Министерством образования РФ/ М., Просвещение, 1996. 2. Е.А. Бунимович, В.А. Булычёв: «Вероятность и статистика», пособие для  общеобразовательных учебных заведений  5 – 9 классы / допущено  Министерством образования Российской Федерации // Дрофа Москва 2002 3. Ю.Н. Макарычев, Н.Г.Миндюк «Алгебра: элементы статистики и теории  вероятностей   7 – 9 классы» Под редакцией С.А.Теляковского М: Просвещение ,  2006 г 22