Основы комбинаторики. Размещения, перестановки, сочетания.
Проказница Мартышка Осёл, Козёл, Да косолапый Мишка Затеяли играть квартет … Стой, братцы стой! – Кричит Мартышка, - погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Вот пуще прежнего пошли у них разборы И споры, Кому и как сидеть…
знать: определения трех важнейших понятий комбинаторики: размещения из n элементов по m ; сочетания из n элементов по m ; перестановки из n элементов; основные комбинаторные формулы уметь: отличать задачи на «перестановки», «сочетания», «размещения» друг от друга; применять основные комбинаторные формулы при решении простейших комбинаторных задач.
множество Множество характеризуется объединением некоторых однородных объектов в одно целое. Объекты, образующие множество, называются элементами множества. Множество будем записывать, располагая его элементы в фигурных скобка { a, b, c, …, e, f }. Во множестве порядок элементов роли не играет, так { a, b } = { b, a }. Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается символом ø.
множество Если каждый элемент множества А является элементом множества В, то говорят, что множество А является подмножеством множества В. В А Множество { a, b } является подмножеством множества { a, b, c, …, e, f }. Обозначается Пример : Задача Перечислите возможные варианты подмножества множества { 3, 4, 5, 7, 9 }.
Комбинаторикой называется область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих заданному множеству. Комбинаторика является важным разделом математики, который исследует закономерности расположения, упорядочения, выбора и распределения элементов с фиксированного множества.
ПРАВИЛО СУММИРОВАНИЯ Если два взаимоисключающие действия могут быть выполнены в соответствии k и m способами, тогда какое-то одно из этих действий можно выполнить k + m способами. Пример №1 Из города А в город В можно добраться 12 поездами, 3 самолетами, 23 автобусами. Сколькими способами можно добраться из города А в город В? Решение N=12+13+23=38
Пример № 2 В ящике имеется n разноцветных шариков. Произвольным образом вынимаем один шарик. Сколькими способами это можно сделать? Решение. Конечно, n способами. Теперь эти n шариков распределены по двум ящикам: В первом m шариков, во втором k. Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами это можно сделать? Решение. Из первого ящика шарик можно вытянуть m различными способами, из второго k различными способами, всего N = m + k способами.
ПРАВИЛО ПРОИЗВЕДЕНИЯ Пусть две выполняемые одно за другим действия могут быть осуществлены в соответствии k и m способами Тогда обе они могут быть выполнены k ∙ m способами. Пример № 3 В турнире принимают участие 8 хоккейных команд. Сколько существует способов распределить первое, второе и третье места? Решение N= 8∙7∙6=336
Пример № 4 Сколько можно записать двузначных чисел в десятичной системе счисления? Решение. Поскольку число двузначное, то число десятков ( m ) может принимать одно из девяти значений: 1,2,3,4,5,6,7,8,9. Число единиц ( k ) может принимать те же значения и может, кроме того быть равным нулю. Отсюда следует, что m = 9, а k = 10. Всего получим двузначных чисел N = m · k = 9·10 =90.
Пример № 5 В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать, для выполнения различных заданий, двух студентов одного пола? Решение. По правилу умножения двух девушек можно выбрать 14 ·13 = 182 способами, а двух юношей 6·5 = 30 способами. Следует выбрать двух студентов одного пола: двух студентов или студенток. Согласно правилу сложения таких способов выбора будет N =182 + 30 = 212.
Типы соединений Множества элементов называются соединениями. Различают три типа соединений: перестановки из n элементов; размещения из n элементов по m ; сочетания из n элементов по m ( m < n ).
Определение : Перестановкой из n элементов называется любое упорядоченное множество из n элементов. Иными словами, это такое множество, для которого указано, какой элемент находится на первом месте, какой – на втором, какой- на третьем, …, какой – на n-м месте. ПЕРЕСТАНОВКИ Перестановки – это такие соединения по n элементам из данных элементов, которые отличаются одно от другого порядком элементов. Число перестановок из n элементов обозначают Р n. Р n = n · ( n - 1) · ( n – 2) · … · 2 · 1 = n !
Определение : Пусть n - натуральное число. Через n ! (читается " эн факториал") обозначается число, равное произведению всех натуральных чисел 1 от до n : n ! = 1 · 2 · 3 ·... · n. В случае, если n = 0, по определению полагается: 0! = 1. ФАКТОРИАЛ
Пример № 6 Найдем значения следующих выражений: 1! 2! 3! 7! Пример № 7 Чему равно а) Р 5 ; б) Р 3. Пример № 8 Упростите а) 7! · 8 б) 12! · 13 ·14 в) κ ! · ( κ + 1)
Пример № 9 Сколькими способами можно расставить 8 участниц финального забега на восьми беговых дорожках? Решение. n =8 Р 8 =8! = 8·7·6·5 · 4 · 3 · 2 ·1 =40320
РАЗМЕЩЕНИЯ Определение. Размещением из n элементов по m называется любое упорядоченное множество из m элементов, состоящее из элементов n элементного множества. Число размещений из m элементов по n обозначают: вычисляют по формуле:
Пример № 9 Учащиеся 11-го класса изучают 9 учебных предметов. В расписании учебных занятий на один день можно поставить 4 различных предмета. Сколько существует различных способов составления расписания на один день? Решение. Имеем 9-элементное множество, элементы которого учебные предметы. При составлении расписания мы будем выбирать 4-элементное подмножество ( урок ов ) и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре ( m=9, n= 4) то есть A 9 4 :
Пример № 10 Сколькими способами из класса, где учатся 24 ученика, можно выбрать старосту и помощника старосты? Решение. Имеем 24-элементное множество, элементы которого ученики класса. При выборах старосты и помощника старосты мы будем выбирать 2-элементное подмножество (у ченика ) и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре ( m=24, n= 2 ), то есть A 24 2 :
СОЧЕТАНИЯ Определение. Сочетанием без повторений из n элементов по m -называется любое m элементное подмножество n -элементного множества Число сочетаний из n элементов по m обозначают и вычисляют по формуле:
Пример № 11 Сколькими способами из класса, где учатся 24 ученика, можно выбрать два дежурных ? Решение. n =24, m =2
Учитывается ли порядок следования элементов в соединении? Д А НЕТ Все ли элементы входят в соединение? СОЧЕТАНИЯ РАЗМЕЩЕНИЯ ПЕРЕСТАНОВКИ Р n = n ! Д А НЕТ
Определить к какому типу относится соединений относится задача. 1. Сколькими способами можно составить расписание одного учебного дня из 5 различных уроков? 2. В 9«Б» классе 12 учащихся. Сколькими способами можно сформировать команду из 4 человек для участия в математической олимпиаде? Учитывается ли порядок следования элементов в соединении? ( да) Все ли элементы входят в соединение? ( да) Вывод: перестановка Учитывается ли порядок следования элементов в соединении? Все ли элементы входят в соединение? (нет) ( на этот вопрос ответ не нужен) Вывод: сочетания
3.Сколько существует различных двузначных чисел, в записи которых можно использовать цифры 1, 2, 3, 4, 5, 6, если цифры в числе должны быть различными? Учитывается ли порядок следования элементов в соединении? Все ли элементы входят в соединение? (нет) ( да ) Вывод: размещение
Проказница Мартышка Осёл, Козёл, Да косолапый Мишка Затеяли играть квартет … Стой, братцы стой! – Кричит Мартышка, - погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Вот пуще прежнего пошли у них разборы И споры, Кому и как сидеть… Сколько различных вариантов расположения музыкантов возможно?
Решение. Учитывается ли порядок следования элементов в соединении? ( да) Все ли элементы входят в соединение? (да) Вывод: перестановка Р n = n ! = n · ( n - 1) · ( n – 2) · … · 2 · 1 n =4 Р 4 = 4! = 4 · 3 · 2 ·1=24
«Рано или поздно всякая правильная математическая идея находит применение в том или ином деле»? Кто автор высказывания?
Е Е перестановки К размещение Л сочетание Е А С Й Н И О Ы Р Ч В М 12 21 120 56 132 720 6720 5040 9 1
Результаты решения задач 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 А Л Е К С Е Й Н К И О В Л А Е Л О Ч И В Ы Р К
