Элементы комбинаторики. Методы решения некоторых задач
Разделы: Математика
1) Немного истории.
В математике и ее приложениях часто приходится иметь дело с различного рода множествами и подмножествами: устанавливать их связь между элементами каждого, определять число множеств или их подмножеств, обладающих заданным свойством. Такие задачи приходится рассматривать при определении наиболее выгодных коммуникаций внутри города, при организации автоматической телефонной связи, работы морских портов, при выявлении связей внутри сложных молекул, генетического кода, а также в лингвистике, в автоматической системе управления, значит и в теории вероятностей, и в математической статистике со всеми их многочисленными приложениями.
Поговорим об одном из разделов теории вероятности – комбинаторике.
Комбинаторика — ветвь математики,
изучающая комбинации и перестановки предметов.
Еще комбинаторику можно понимать как перебор
возможных вариантов. Комбинаторика возникла в 17
веке. Долгое время она лежала вне основного русла
развития математики.
С задачами, в которых приходилось выбирать те или
иные предметы, располагать их в определенном
порядке и отыскивать среди разных расположений
наилучшие, люди столкнулись еще в доисторическую
эпоху, выбирая наилучшее положение охотников во
время охоты, воинов – во время битвы,
инструментов — во время работы.
Комбинаторные навыки оказались полезными и в
часы досуга. Нельзя точно сказать, когда наряду с
состязаниями в беге, метании диска, прыжках
появились игры, требовавшие, в первую очередь,
умения рассчитывать, составлять планы и
опровергать планы противника.
Со временем появились различные игры (нарды,
карты, шашки, шахматы и т.д.). В каждой из этих игр
приходилось рассматривать различные сочетания
фигур, и выигрывал тот, кто их лучше изучил, знал
выигрышные комбинации и умел избегать
проигрышных. Не только азартные игры давали пищу
для комбинаторных размышлений математиков. Еще с
давних пор дипломаты, стремясь к тайне переписки,
изобретали сложные шифры, а секретные службы
других государств пытались эти шифры разгадать.
Стали применять шифры, основанные на
комбинаторных принципах, например, на различных
перестановках букв, заменах букв с
использованием ключевых слов и т.д.
Итак, произведение всех натуральных чисел от 1 до n включительно называют n-факториалом и пишут: n!=1 2 3 … (n-1) n
В комбинаторике решаются задачи, связанные с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств. В зависимости от правил составления можно выделить три типа комбинаций: перестановки, размещения, сочетания.
2) ЗАДАЧИ
1. В школьной столовой на первое можно заказать борщ, солянку, грибной суп, на второе - мясо с макаронами, рыбу с картошкой, курицу с рисом, а на третье — чай и компот. Сколько различных обедов можно составить из указанных блюд?
1 способ. Перечислим возможные варианты
Чай(Ч) |
Мясо с макаронами(М) |
Рыба с картошкой(Р) |
Курица с рисом(Кр) |
Борщ (Б) |
БМЧ/ БМК |
БРЧ/БРК |
БКрЧ/БКрК |
| Солянка(С) | СМЧ/ СМК |
СРЧ/СРК |
СКрЧ/СКрК |
Грибной суп(Г) |
ГМЧ/ГМК |
ГРЧ/ГРК |
ГКрЧ/ГКрК |
18 вариантов.
2 способ. Дерево возможностей.
3 способ. Используя правило умножения, получаем: 3х3х2=1
2. Свете на день рождения подарили 4 плюшевых игрушки, 2 мяча и 5 кукол. Мама положила все игрушки в большую коробку. Сколькими способами Света сможет достать из коробки 1 плюшевую игрушку, 1 мяч и 1 куклу?
1 способ. Обозначим мячи — М1, М2,
игрушки- И1,И2,И3, И4, куклы- К1,К2, К3, К4, К5.
Перечислим возможные варианты:
М1-И1-К1, М1-И1-К2, М1-И1-К3, М1-И1-К4, М1-И1-К5,
М1-И2-К1, М1-И2-К2, М1-И2-К3, М1-И2-К4, М1-И2-К5,
М1-И3-К1, М1-И3-К2, М1-И3-К3, М1-И3-К4, М1-И3-К5,
М1-И4-К1, М1-И4-К2, М1-И4-К3, М1-И4-К4, М1-И4-К5
М2-И1-К1, М2-И1-К2, М2-И1-К3, М2-И1-К4, М2-И1-К5,
М2-И2-К1, М2-И2-К2, М2-И2-К3, М2-И2-К4, М2-И2-К5,
М2-И3-К1, М2-И3-К2, М2-И3-К3, М2-И3-К4, М2-И3-К5,
М2-И4-К1, М2-И4-К2, М2-И4-К3, М2-И4-К4, М2-И4-К5
Ответ: 40 вариантов.
2 способ. Используя правило умножения,
получаем: 2х4х5= 40
3. Сколько четных двузначных чисел можно составить из цифр 0, 2, 3, 6, 7, 9?
1 способ.
Перечислим возможные варианты.
0 |
2 |
6 |
|
2 |
20 |
22 |
26 |
3 |
30 |
32 |
36 |
6 |
60 |
62 |
66 |
7 |
70 |
72 |
76 |
9 |
90 |
92 |
96 |
2 способ. Дерево возможностей.
3 способ. Используя правило умножения, получаем: 5х3=15 .
4. Мисс Марпл, расследуя убийство, заметила отъезжающее от дома мистера Дэвидсона такси. Она запомнила первую цифру “2”. В городке номера машин были трехзначные и состояли из цифр 1,2,3,4 и 5. Скольких водителей, в худшем случае, ей придется опросить, чтобы найти настоящего убийцу?
1 способ. Перечислим возможные варианты номеров такси:
1 |
2 |
3 |
4 |
5 |
|
1 |
211 |
212 |
213 |
214 |
215 |
2 |
221 |
222 |
223 |
224 |
225 |
3 |
231 |
232 |
233 |
234 |
235 |
4 |
241 |
242 |
243 |
244 |
245 |
5 |
251 |
252 |
253 |
254 |
255 |
Ответ: 25 человек.
2 способ. Используя правило умножения, получаем: 5х5=25
5. Саша, Петя, Денис, Оля, Настя часто ходят в кафе. Каждый раз, обедая там, они рассаживаются по-разному. Сколько дней друзья смогут это сделать без повторения?
1 способ. Пронумеруем стулья, на которых должен сесть каждый, и будем считать, что они рассаживаются поочередно:
№1 — Саша — есть возможность выбрать из 5
вариантов (стульев)
№2 — Петя — 4 варианта
№3- Денис — 3 варианта
№4- Оля — 2 варианта
№5 — Настя- 1 вариант
Используя правило умножения, получаем: 5х4х3х2х1=120
2 способ. Решаем, используя понятие факториала: 5!=120
6. Из учащихся пяти 11 классов нужно выбрать двоих дежурных. Сколько пар дежурных можно составить (ученики в паре не должны быть из одного класса)?
1 способ. Перечислим возможные варианты состава пары:
11А-11Б, 11А-11В, 11А-11Г, 11А-11Д,
11Б-11В, 11Б-11Г, 11Б-11Д, 11В-11Г, 11В-11Д, 11Г-11Д
Ответ: 10 пар.
2 способ. Из пяти классов нужно
выбрать 2 дежурных.
Число элементарных событий = = 10
7. В 8 “а” классе лучше всех математику знают 5 учеников: Вася, Дима, Олег, Катя и Аня. На олимпиаду по математике нужно отправить пару, состоящую из 1 мальчика и 1 девочки. Сколькими способами учительница может эту пару выбрать?
1 способ. Обозначим имена детей
первыми заглавными буквами.
Получаем следующие пары:
В-К, В-А, Д-К, Д-А, О-К, О-А.
Ответ: 6 пар.
2 способ. Мальчиков 3, из них 1 можно
выбрать ,
девочек 2, из них можно 1 выбрать , используя
правило умножения, получаем:
х = 6
8. В соревнованиях по фигурному катанию принимали участие россияне, итальянцы, украинцы, немцы, китайцы и французы.
Сколькими способами могут
распределится места по окончании соревнований?
Обозначим участников по первой заглавной букве
страны и пронумеруем: Р1, И2, У3, Н4,К5, Ф6
Р1 — имеют возможность занять с1-6 места, т.е. 6
вариантов
И2 — 5 вариантов
У3- 4 варианта
Н4- 3 варианта
К5- 2 варианта
Ф6- 1 вариант
Используя правило умножения, получаем: 6х5х4х3х2х1=
720
2 способ. Используя понятие факториала, получаем: 6!=720
9. В 9 “б” классе 6 человек (Галя, Света, Катя, Оля, Максим, Витя) учатся на все пятерки. Департамент образования премировал лучших учащихся путевками в Анапу. Но, к сожалению, путевок всего четыре. Сколько возможно вариантов выбора учеников на отдых?
Обозначим первыми заглавными буквами
имен учащихся.
Возможны следующие тройки:
Г-С-К-О, Г-С-К-М, Г-С-К-В,
Г-С-О-М, Г-С-О-В, Г-С-М-В
С-К-О-М, С-К-О-В, С-К-М-В,
К-О-М-В, С-О-М-В, Г-К-О-В,
Г-К-О-В, Г-О-М-В, Г-К-М-В
2 способ. Из 6 человек нужно выбрать 4, число элементарных событий равно = 15
10. Пете на день рождения подарили 7 новых дисков с играми, а Вале папа привез 9 дисков из командировки. Сколькими способами они могут обменять 4 любых диска одного на 4 диска другого?
Вычислим, сколько четверок из 7 дисков
можно составить у Пети:
=35, число
четверок у Вали из 9 дисков -= 126
По правилу умножения находим число обменов 35х126=4410
11. Войсковое подразделение состоит из 5 офицеров, 8 сержантов и 70 рядовых. Сколькими способами можно выделить отряд из 2 офицеров, 4 сержантов и 15 рядовых?
Из 5 офицеров выбрать 2 можно с помощью
числа сочетаний =10 способами, из 8 сержантов 4 — =70, из 70 рядовых 15 -. По правилу
умножения находим число выбора отряда:
10х70х= 700х
12. В ювелирную мастерскую привезли 6 изумрудов, 9 алмазов и 7 сапфиров. Ювелиру заказали браслет, в котором 3 изумруда, 5 алмазов и 2 сапфиров. Сколькими способами он может выбрать камни на браслет?
Из 6 изумрудов 3 он может выбрать =20 способами, из 9 алмазов 5 -=126, из 7 сапфиров 2 — =21. По правилу умножения находим число вариантов 20х126х21=52920
13. На выборах победили 9 человек - Сафонов, Николаев, Петров, Кулаков, Мишин, Гусев, Володин, Афонин, Титов. Из них нужно выбрать председателя, заместителя и профорга. Сколькими способами это можно сделать?
Здесь речь идет о размещениях
Можно было решать по-другому. На должность
председателя выбираем из 9 человек, на
заместителя — из 8, на профорга — из 7
По правилу умножения получаем 9х8х7=504
14. В районе построили новую школу. Из пришедших 25 человек нужно выбрать директора школы, завуча начальной школы, завуча среднего звена и завуча по воспитательной работе. Сколькими способами это можно сделать?
На должность директора выбираем из 25
человек, на завуча начальной — из 24, завуча
среднего звена — из 23, завуча по воспитательной
работе — 22. По правилу умножения получаем:
25х24х23х22 = 303600
Или, зная формулу размещения, получаем
15. В студенческом общежитии в одной комнате живут трое студентов Петя, Вася и Коля. У них есть 6 чашек, 8 блюдец и 10 чайных ложек (все принадлежности отличаются друг от друга). Сколькими способами ребята могут накрыть стол для чаепития (так, что каждый получит чашку, блюдце и ложку)?
Для Пети набор можно набрать 6х8х10=480
способами, для Васи — 5х7х9=315, для Коли — 4х6х8=192. По
правилу умножения получаем
480х315х192=29030400 способами.
16. В кабинете заведующего ювелирного магазина имеется код, состоящий из двух различных гласных букв русского алфавита, за которой следуют 3 различные цифры. Сколько вариантов придется перебрать мошеннику, чтобы раздобыть драгоценности, которые там хранятся?
В русском языке 9 гласных букв — а, е, е,
и, о, у, э, ю, я. Выбрать из них 2 можно =36 способами. Из 10
цифр выбрать 3 можно=120 способами. Применяя правило умножения,
получаем:
36х120=4320
17. Сколькими способами можно составить
трехцветный флаг из полос разной ширины, если
имеются материи из 8 тканей?
Эта задача на размещение
Другой способ решения.
1цвет выбирается из 8 тканей 8 способами
2цвет выбирается 7 способами
3 цвет — 6способами
Используя правило умножения, получаем 8х7х6=336
способов.
18. В 9 классе 15 предметов. Завучу школы нужно составить расписание на субботу, если в этот день 5 уроков. Сколько различных вариантов расписания можно составить, если все уроки различные?
Из 15 предметов 5 любых можно выбрать
19. В огороде у бабушки растут 3 белые, 2 алые и 4 чайных розы. Сколькими различными способами можно составить букет из трех роз разного цвета?
1 способ. Обозначим белые — Б1, Б2, Б3,
алые — А1,А2, чайные — Ч1, Ч2, Ч3,Ч4
Перечислим возможные варианты
Б1-А1-Ч1, Б1-А1-Ч2, Б1-А1-Ч3, Б1-А1-Ч4, Б1-А2-Ч1,Б1-А2-Ч2, Б1-А2-Ч3,
Б1-А2-Ч4
Б2- А1-Ч1, Б2-А1-Ч2, Б2-А1-Ч3, Б2-А1-Ч4, Б2-А2-Ч1,Б2-А2-Ч2, Б2-А2-Ч3,
Б2-А2-Ч4
Б3- А1-Ч1, Б3-А1-Ч2, Б3-А1-Ч3, Б3-А1-Ч4, Б3-А2-Ч1,Б3-А2-Ч2, Б3-А2-Ч3,
Б3-А2-Ч4
Ответ: 24 варианта.
2способ. Дерево возможностей
3 способ. Используя правило умножения, получаем: 2х3х4=24
20. К 60-летию Победы группа школьников отправилась по местам боевых действий в Смоленской области. Они планировали осуществить поход по маршруту деревни Сосновка-Быковка- Масловка- Видово. Из С в Б можно проплыть по реке или пройти пешком, из Б в М- пешком или на автобусе, из М в В — по реке, пешком или автобусе. Сколько вариантов похода есть у щкольников?
1 способ. Обозначим СБ — путь из
Сосновки в Бытовку, ВГ — путь из Быковки в
Масловку, МВ — путь из Масловки в Видово.
По реке -Р, пешком — П, на автобусе — А
Перечислим возможные варианты:
СБР- БМП-МВР, СБР- БМП-МВП, СБР- БМП-МВА
СБР-БМА-МВР, СБР-БМА-МВП, СБР-БМА-МВА
СБА- БМП-МВР, СБА- БМП-МВП, СБА- БМП-МВА
СБА-БМА-МВР, СБА-БМА-МВП, СБА-БМА-МВА
Ответ: 12 вариантов.
2 спосо
xn--i1abbnckbmcl9fb.xn--p1ai
Элементы комбинаторики
Вопросы занятия:
· вспомнить, что изучает комбинаторика;
· повторить основные виды комбинаций элементов: перестановки, размещения и сочетания;
· вспомнить, как выводят формулы для их вычисления.
Материал урока
В науке и на практике очень часто встречаются задачи, решая которые приходится составлять различные комбинации из конечного числа элементов, а затем подсчитывать число этих комбинаций.
Такие задачи получили своё название. Их называют комбинаторными задачами.
А раздел математики, в котором рассматриваются подобные задачи, называют комбинаторикой.
Само слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать».
Определение.
Комбинаторика – это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.
Комбинаторика тесно связана со многими другими областями математики – алгеброй, геометрией, теорией вероятностей. И имеет широкий спектр применения, например, в информатике и статистической физике.
Давайте решим несколько комбинаторных задач.
Задача. Лера, Карина, Глеб и Максим решили сыграть друг с другом по одной партии в бадминтон. Сколько партий было сыграно?
Для краткости имена будем обозначать первой буквой.
Сначала давайте составим все пары, в которых принимала участие Лера. Получим три такие пары.
Теперь составим пары, в которых участвовала Карина, но не принимала участия Лера. Так как пара Лера – Карина у нас уже записана. Таким образом, получим две новые пары.
Затем запишем пары, в которые входит Глеб, но не входят Лера и Карина. Получим только одну пару.
Других вариантов составления пар нет, так как все пары, куда входит Максим, уже составлены.
Итак, мы получили 6 различных пар.
Можем сделать вывод, что было сыграно 6 партий в бадминтон.
Способ рассуждений, которым мы воспользовались при решении задачи, называют перебором возможных вариантов.
Задача.
Определить, сколько различных трёхзначных чисел можно составить, используя цифры 2, 6, 8 и 9. При этом цифры в числе не должны повторяться.
Первой цифрой числа может быть любая из данных цифр.
Поставим на первое место, например, цифру 2. Тогда на втором месте могут стоять цифры 6, 8 или 9. Если на втором месте стоит цифра 6, то на третьем соответственно могут быть цифры 8 или 9. Так мы получим 2 числа: 268 и 269. Если на втором месте стоит цифра 8, то на третьем может быть 6 или 9. Также получим два числа. И если на втором месте стоит 9, то третьей цифрой числа могут быть 6 или 8. Аналогично можно расписать возможные варианты, если первой цифрой числа являются 6, 8 или 9.
Схему, которую мы построили при решении задачи, называют деревом возможных вариантов. И по ней становится понятно, что, используя 4 цифры, можно составить 24 различных трёхзначных числа.
Можно было по-другому решить задачу. Рассуждая так: первую цифру мы выбираем четырьмя способами, вторую тремя, так как после выбора первой осталось три цифры. А третью — двумя. Получаем, что общее количество искомых трёхзначных чисел равно:
При решении данной задачи мы воспользовались комбинаторным правилом умножения.
Этот метод решения комбинаторных задач применяется, когда не требуется перечислять все возможные варианты, а нужно ответить на вопрос — сколько их существует.
Сформулируем его в общем виде.
Пусть имеется элементов и требуется выбрать из них один за другим элементов. Если первый элемент можно выбрать способами, после чего второй элемент можно выбрать способами из оставшихся, затем третий элемент можно выбрать способами из оставшихся и так далее, то число способов, которыми могут быть выбраны все элементов, равно произведению:
В комбинаторике различают три вида различных соединений (комбинаций) элементов фиксированного(конечного) множества. Это перестановки, размещения и сочетания.
И сейчас давайте поговорим о каждом из этих видов поподробнее.
Начнём с перестановок. Кстати, перестановки – это простейшие комбинации, которые можно составить из элементов конечного множества.
Вот, например. Пусть есть 3 книги. Обозначим их буквами a, b и c. Понятно, что эти книги мы можем расставить на полке совершенно разными способами.
Если первой поставить книгу а, то возможны такие расположения книг на полке: a, b, c и a, c, b.
Если первой поставить книгу b, то возможными будут такие расположения книг: b, a, c и b, c, a.
Ну, а если же первой поставить книгу c, то можно получить следующие расположения книг на полке: c, a, b и c, b, a.
Заметим, мы получили 6 возможных расположений книг на полке.
Каждое из этих возможных расположений книг называют перестановкой из трёх элементов.
Определение.
Перестановкой из элементов называется каждое расположение этих элементов в определённом порядке.
Напомним, что число перестановок из элементов обозначают так:
и говорят « из ».
Вернувшись к рассмотренному примеру, можно сказать, что число перестановок из трёх элементов .
Это же значение мы могли бы получить, пользуясь комбинаторным правилом умножения:
Т.е. для выбора первого элемента существует 3 варианта. Для каждого из них есть 2 варианта выбора второго элемента. И третий элемент мы выбираем единственным способом.
Значит, число перестановок из трёх элементов действительно равно 6.
А теперь давайте вспомним, как выводится формула числа перестановок из элементов.
Пусть у нас есть элементов. Тогда на первое место можно поставить один из них, то есть вариантов. На второе место можно поставить любой из оставшихся «» элементов. На третье место можно поставить любой из оставшихся «» элементов. И так далее … . В результате получим следующую запись:
Расположив множители в порядке возрастания, получаем формулу числа перестановок из элементов:
Кстати, для записи произведения первых натуральных чисел есть специальное обозначение .А читают его « факториал».
Например, .
По определению считают, что .
Таким образом, число всевозможных перестановок из элементов вычисляется по формуле: .
Например, найдём число перестановок из 5 элементов.
Задача.
Имеется 9 карандашей, 4 из которых — простые. Сколькими способами можно разложить их в коробке так, чтобы все простые карандаши лежали рядом?
Сначала все простые карандаши давайте условимся рассматривать как один карандаш. Тогда нам нужно разложить в коробке не 9, а 6 карандашей.
Найдём сколькими способами это можно сделать. Т.е. имеем, число перестановок из 6 элементов равно .
В каждом из полученных способов 4 простых карандаша тоже можно разложить по-разному. А точнее .
Для нахождения общего числа способов нужно . В ответ запишем 17280 способов.
Теперь перейдём к следующему виду комбинаций – размещения.
И начнём с примера. Пусть есть 4 шара и 3 пустые ячейки. В каждую ячейку можно поместить только по одному шару. Для удобства обозначим шары буквами: А, B, C и D.
Если поместим шар А в первую ячейку, шар B — во вторую ячейку, а шар C — в третью, то мы получим одну из возможных упорядоченных троек шаров.
Выбирая по-разному шары для каждой из ячеек, получим, например, такие тройки:
Каждую такую упорядоченную тройку, составленную из 4 элементов, называют размещением из 4 элементов по 3.
Определение.
Размещением из элементов по , где , называется любое множество, состоящее из элементов, взятых в определённом порядке из данных элементов.
Два размещения из элементов по считаются различными, если они различаются самими элементами или порядком их следования.
Число размещений из элементов по обозначают так:
И читают « из по ».
Вернёмся к примеру. Можем обозначить число размещений из четырёх элементов по три таким образом: .
Вычислим количество таких размещений для данного случая, пользуясь правилом комбинаторного умножения. Первый элемент мы выбирали одним из 4 способов, так как им может быть любой из 4 шаров. Второй элемент мы можем выбрать 3 способами и третий — 2. Так получаем, что число размещений из 4 элементов по 3 равно
С помощью таких же рассуждений можно вывести формулу для вычисления числа размещений из элементов по .
Для выбора первого элемента можно взять любой из элементов, то есть существует способов. Для выбора второго элемента можем взять любой из «» оставшихся элементов, то есть «» способов. Третий элемент можно выбрать «» способами. И так далее … . Так -ый элемент можно выбрать «» способами.
Умножим и разделим правую часть этого равенства на «». Заменим произведением и расположим множители в порядке возрастания. Заметим, что в числителе записано произведение всех натуральных чисел от 1 до включительно. А ведь это произведение равно .
Мы получили формулу для вычисления числа размещений из элементов по при .
Стоит обратить внимание на то, что размещения из элементов по отличаются только порядком следования элементов, так как каждый из них должен участвовать в размещении. Тогда получаем, что такое размещение является перестановкой.
Рассмотрим пример: вычислить число размещений из 5 элементов по 3.
Воспользовавшись формулой размещений, получим,
Задача.
Девять карточек пронумерованы цифрами от 1 до 9. Из этих карточек 4 наугад выкладывают в ряд. Сколько при этом различных четырёхзначных чисел можно получить?
Суть задачи состоит в том, что из 9 данных цифр нужно составить всевозможные четырёхзначные числа, не повторяя цифры в числе. Следовательно, решение задачи сводится к отысканию числа размещений из 9 элементов по 4.
Запишем формулу для нахождения числа размещений. Представим числитель и знаменатель в виде произведения. Сократим дробь. Остаётся вычислить произведение. В результате получим,
Значит, можно получить 3024 различных четырёхзначных числа.
Ну а теперь давайте поговорим о последнем виде комбинаций элементов, о сочетаниях.
Начнём с примера. Пусть имеются 5 цветков различного цвета. Для удобств обозначим их буквами: А, B, C, D и Е. Будем составлять букеты из 3 цветков.
Если в букет входит цветок А, то можем составить такие букеты:
АBC, АBD, АBЕ, АCD, АCЕ, и АDЕ.
Если в букет входит цветок B, но не входит А, то составим букеты:
BCD, BCЕ, и BDЕ.
Если же в букет входит цветок C и не входят А и B, то получим только один букет: CDЕ.
Так мы с вами указали все возможные способы составления букетов, в которых по-разному сочетаются 3 цветка из данных 5.
Таким образом, мы составили все возможные сочетания из 5 элементов по 3.
Определение.
Сочетанием из элементов по называется любое множество, составленное из элементов, выбранных из данных элементов.
Число сочетаний из элементов по обозначают так:
И читают « из по ».
В отличие от размещений в сочетаниях не имеет значения, в каком порядке расположены элементы. Сочетания считаются различными, если они отличаются хотя бы одним элементом.
Так, например, такие два букета
являются размещениями. Так как в их состав входят одни и те же элементы, только с разным расположением.
А два таких букета
являются сочетаниями, ведь они отличаются составом элементов.
В рассмотренном примере мы составили все сочетания из 5 элементов по 3. И выяснили, что их число равно 10.
Вспомним, как выводится формула числа сочетаний из элементов по .
Допустим, что имеется множество из элементов, и из них составлены все возможные сочетания по элементов. Число таких сочетаний равно . В каждом из этих сочетаний можно выполнить перестановок. В результате мы получим все размещения, которые можно получить из элементов по . Получим такую запись.
Из неё следует, что число сочетаний из элементов по равно частному «числа размещений из элементов по » и «числа перестановок из элементов».
Пользуясь уже известными формулами числа перестановок и размещений, получим такое равенство.
Так мы с вами получили формулу нахождения числа сочетаний из элементов по . При этом .
Рассмотрим пример: найти число сочетаний из 7 элементов по 4.
По формуле сочетаний имеем:
Задача.
Турист запланировал взять с собой в поездку 8 футболок, при этом всего их у него насчитывается 12. Сколькими способами он может сделать выбор?
Применим формулу сочетаний из элементов по . У вас мог возникнуть вопрос, почему мы не ищем число размещений? Но вспомнив отличие размещений от сочетаний, становится ясно, что туристу не важно, в каком порядке он соберёт футболки. Ему важно, какие именно из них он возьмёт с собой.
Итак, запишем формулу числа сочетаний из 12 элементов по 8. Получаем,
Итоги урока
На этом уроке мы рассмотрели тему «элементы комбинаторики». Вспомнили, что изучает комбинаторика. Повторили, основные виды комбинаций элементов: перестановки, размещения и сочетания. И вспомнили, как выводят формулы для их вычисления.
videouroki.net
9 класс. Алгебра. Элементы комбинаторики, статистики и теории вероятности. — Комбинаторные задачи.
Комментарии преподавателя
Тема урока: «Комбинаторные задачи». Человеку часто приходится сталкиваться с задачами, когда ему нужно посчитать число способов реализации некоторого действия. Например: вы забыли пароль на вашем компьютере, сколько вариантов вам придется перебрать, прежде чем вы сможете восстановить доступ? На данном уроке рассматривается раздел математики, который позволяет ответить на вопросы: сколькими способами, сколько вариантов и так далее. Этот раздел носит имя «комбинаторика».
Для начала рассмотрим простой пример. Пусть в некотором регионе решили ввести формат номера автомобиля в виде числа. Вопрос: какое количество автомобилей мы сможем снабдить различными номерами? Внимательный учащийся сразу заметит неполноту формулировки задачи, не правда ли? И действительно, во-первых, не указано, какое количество знаков должно находиться в номере автомобиля, во-вторых, какие значения могут принимать отдельные цифры такого номера. Ну и конечно, как принято при решении подобных задач, начнем мы решение с рассмотрения самых простых случаев.
Пусть приняты только трехзначные номера, причем формируются они только цифрами 1, 2 и 3. Также вводится несколько нестандартное требование: пусть одна и та же цифра в номере будет встречаться не более одного раза. Это нужно для упрощения решения. В этом случае ответить на вопрос задачи совсем просто. Нужно перечислить все возможные комбинации из трех цифр. Вот они: , , , , , .
Всего 6 штук. Согласитесь, маловато для автомобильных номеров. Давайте теперь будем нумеровать машины четырехзначными числами. Причем каждая цифра числа будет меняться в диапазоне от одного до четырех. Также сохраним требование к однократному присутствию каждой цифры в номере. Здесь перебирать номера вручную уже заметно тяжелее, если не верите, убедитесь самостоятельно. А пока воспользуемся следующим приемом:
первая цифра номера – 4 значения;
вторая – 3 значения;
третья – 2 значения.
У последней цифры остается только одна возможность. Тогда общее количество вариантов равно произведению . Этот перебор можно проиллюстрировать при помощи так называемого дерева возможных вариантов (Рис. 1.). Номера машин можно получить, если прочитать каждую ветку данной схемы сверху вниз.
Рис. 1. Дерево вариантов автомобильных номеров
24 – это уже значительно лучше, чем 6, однако все равно нам этого мало. В предыдуще
www.kursoteka.ru
Элементы комбинаторики
Цели занятия.
Образовательные:
познакомить обучающихся с новым разделом математики: «Комбинаторика», основными понятиями и задачами, использованием в практических целях и в жизни человека;
Развивающие:
развивать умения решать комбинаторные задачи на «перестановки», «сочетания», «размещения» по формулам, практических навыков и умений, аналитические способности, логическое мышление,
Воспитывающая:
формировать активность личности обучающегося, умение работать в группе
показать, что решения комбинаторных задач возникли из практических потребностей человека.
Оборудование: компьютеры, проектор, экран, презентация, тесты, книги.
Ход занятия
- Организационный момент.
Класс разделен на группы. В группе может быть 4 или 5обучающихся.
Каждый обучающийся отвечает за свое поручение. (Тем самым он учится быть и руководителем, и секретарем и т.д). Переходя от каждого нового задания, обучающиеся меняются поручениями.
Проверка д/з.
Туристическая фирма планирует посещение туристами в Италии трех городов: Венеции, Рима и Флоренции. Сколько существует вариантов такого маршрута?
ВРФ ВФР РФВ РВФ ФРВ ФВР (6)
Задачи такого типа называются комбинаторными.
Комбинаторика – раздел математики, который занят поисками ответов на вопросы: сколько всего есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать наилучшую. Слово «комбинаторика» происходит от латинского слова «combinare», что в переводе на русский означает – «сочетать», «соединять». Термин «комбинаторика» был введён знаменитым Готфридом Вильгельмом Лейбницем, — всемирно известным немецким учёным.
Комбинаторные задачи делятся на несколько групп.
-
Сообщение новых знаний.
- Задача:
Сколькими способами можно расставить 3 различные книги на книжной полке?
abc acb
bac bca
cab cba ответ:6
Это задача на перестановки
Перестановкой из n элементов называется каждое расположение этих элементов в определённом порядке.
Pn = n(n-1)(n-2)∙…∙3∙2∙1
Pn = n!
Произведение всех последовательных натуральных чисел от 1 до n обозначается n! n! = 1 · 2 · 3 · … · n.
Факториалы растут удивительно быстро.
n 1 2 3 4 5 6 7 8 9 10
n! 1 4 6 24 120 720 5040 40 320 362 880 3 628800
Задача. Сколькими способами можно расставить 8 участниц финального забега на восьми беговых дорожках?
P8 = 8!= 1 ∙2∙ 3 ∙4∙ 5 ∙6∙ 7 ∙8 = 40320
Задача.
Квартет
Проказница Мартышка
Осёл,
Козёл,
Да косолапый Мишка
Затеяли играть квартет
…
Стой, братцы стой! –
Кричит Мартышка, — погодите!
Как музыке идти?
Ведь вы не так сидите…
И так, и этак пересаживались – опять музыка на лад не идет.
Вот пуще прежнего пошли у них разборы
И споры,
Кому и как сидеть…
Сколькими способами можно рассадить четырех музыкантов?
P = 4! = 1 * 2 * 3 * 4 = 24
Задача. У нас имеется 5 книг, что у нас всего одна полка, и что на ней вмещается лишь 3 книги . Сколькими способами можно расставить на полке 3 книги?
Выбираем одну из 5-ти книг и ставим на первое место на полке. Это мы можем сделать 5-ю способами. Теперь на полке осталось два места и у нас осталось 4 книги. Вторую книгу мы можем выбрать 4-мя способами и поставить рядом с одной из 5-ти возможных первых. Таких пар может быть 5·4. Осталось 3 книги и одно место. Одну книгу из 3-ёх можно выбрать 3-мя способами и поставить рядом с одной из возможных 5·4 пар. Получится 5·4·3 разнообразных троек. Значит всего способов разместить 3 книги из 5-ти 5·4·3 = 60.
Это размещения .
Размещением из n элементов по k (k≤n) называется любое множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.
Ank=n!/(n-k)!
Задача. Учащиеся второго класса изучают 9 предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета?
A94 =9!/5! = 6∙ 7∙ 8∙ 9 = 3024
Задача. Сколькими способами можно расставить 3 тома на книжной полке, если выбирать их из имеющихся в наличии внешне неразличимых 5 книг?
Книги внешне неразличимы. Но они различаются, и существенно! Эти книги разные по содержанию. Возникает ситуация, когда важен состав элементов выборки, но несущественен порядок их расположения.
123 124 125 134 135 145
234 235 245
345 ответ: 10
Это сочетания .
Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов.
Cnk=n!/((n-k)!k!)
Задача. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
C72 =21
Особая примета комбинаторных задач – вопрос, который можно сформулировать так, чтобы он начинался словами «Сколькими способами…»
- Физкультминутка.
- Закрепление темы.
Тест по комбинаторики ( 8 обучающихся выполняют тест на компьютере, остальные на бумаге, взаимопроверка)
Вариант 1.
1. Сколькими способами можно составить расписание одного учебного дня из 5 различных уроков?
1) 30 2) 100 3) 120 4) 5
2. В 9«Б» классе 12 учащихся. Сколькими способами можно сформировать команду из 4 человек для участия в математической олимпиаде?
1) 128 2) 495 3) 36 4) 48
3. Сколько существует различных двузначных чисел, в записи которых можно использовать цифры 1, 2, 3, 4, 5, 6, если цифры в числе должны быть различными?
1) 10 2) 60 3) 20 4) 30
№ задания 1 2 3
№ ответа 3 2 4
Вариант 2.
1. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5?
1) 100 2) 30 3) 5 4) 120
2. Имеются помидоры, огурцы, лук. Сколько различных салатов можно приготовить, если в каждый салат должно входить 2 различных вида овощей?
1) 3 2) 6 3) 2 4) 1
3. Сколькими способами из 8 учебных предметов можно составить расписание учебного дня из 4 различных уроков.
1) 10000 2) 1680 3) 32 4) 1600
№ задания 1 2 3
№ ответа 4 1 2
Вариант 3.
1. Сколькими способами можно расставить 4 различные книги на книжной полке?
1) 24 2) 4 3) 16 4) 20
2. Сколько диагоналей имеет выпуклый семиугольник?
1) 30 2) 21 3) 14 4) 7
3. В футбольной команде 11 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами это можно сделать?
1) 22 2) 11 3) 150 4) 110
№ задания 1 2 3
№ ответа 1 2 4
Вариант 4
1. Сколькими способами могут встать в очередь в билетную кассу 5 человек?
1) 5 2) 120 3) 25 4) 100
2. Сколькими способами из 15 учеников класса можно выбрать трёх для участия в праздничном концерте?
1) 455 2) 45 3) 475 4) 18
3. В теннисном турнире участвуют 10 спортсменов. Сколькими способами теннисисты могут завоевать золото, серебро и бронзу?
1) 600 2) 100 3) 300 4)720
№ задания 1 2 3
№ ответа 2 1 4
2) Проблемный вопрос:
Может ли нам комбинаторика помочь в реальной жизни?
Решение комбинаторных задач развивает творческие способности, помогает при решении олимпиадных задач, задач из ГИА, ЕГЭ.
Области применения комбинаторики:
-учебные заведения ( составление расписаний)
-сфера общественного питания (составление меню)
-лингвистика (рассмотрение вариантов комбинаций букв)
-спортивные соревнования (расчёт количества игр между участниками)
-агротехника (размещение посевов на нескольких полях)
-география (раскраска карт)
-биология (расшифровка кода ДНК)
-химия (анализ возможных связей между химическими элементами)
-экономика (анализ вариантов купли-продажи акций) азартные игры (подсчёт частоты выигрышей)
-криптография (разработка методов шифрования)
-доставка почты (рассмотрение вариантов пересылки)
-военное дело (расположение подразделений)
Необыкновенно популярной головоломкой стал кубик Рубика, изобретенный в 1975 году преподавателем архитектуры из Будапешта Эрне Рубиком для развития пространственного воображения у студентов.
Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 секунды.
Кубик Рубика служит не только развлечением, но и прекрасным наглядным пособием по комбинаторике.
Вывод:
Комбинаторика повсюду.
Комбинаторика везде.
Комбинаторика вокруг нас.
VI. Д/з:
1.В коробке находится 10 белых и 6 черных шаров.
Сколькими способами из коробки можно вынуть один шар любого цвета?
2.Ольга помнит, что телефон подруги оканчивается тремя цифрами 5, 7, 8 но забыла, в каком порядке эти цифры расположены. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге.
3. В магазине “Филателия” продается 8 разных наборов марок, посвященных спортивной тематике. Сколькими способами можно выбрать из них 3 набора?
4. Проект «История комбинаторики»
VII.Итог, рефлексия.
Определи своё настроение в конце урока.
videouroki.net
Элементы комбинаторики
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Процесс получения навыков подсчета комбинаторных объектов можно расчленить на три этапа в зависимости от времени обучения и методов подсчета:
подсчет методом непосредственного перебора;
подсчет с использованием комбинаторных принципов;
подсчет с использованием формул комбинаторики.
Справочный материал Перебор возможных вариантов в комбинаторных задачах
Рисунок 1. Виды комбинаторных задач
Пример.
В магазине продают шарфы трех цветов: зеленый, голубой и розовый. Подружки покупают себе по одному шарфу. Сколько существует различных вариантов покупок для этих девочек?
Решение.
Что дано? Шарфы трех цветов.
Что нужно сделать? Узнать количество способов покупки двух шарфов.
Поскольку в условии задачи не сказано о том, что подружки покупают шарфы различных цветов, то они могут купить либо два шарфа одного цвета, либо два шарфа различных цветов.
Могут быть куплены следующие шарфы:
зеленый, зеленый
зеленый, голубой
зеленый, розовый
голубой, голубой
розовый, розовый
розовый, голубой
Ответ. Возможно 6 способов покупки двух шарфов.
Перебор объектов с помощью графов в комбинаторных задачах
Пример.
Сколько различных трехзначных чисел можно записать с помощью цифр 1, 2, 3 при условии, что цифры в числе могут повторяться?
Решение.
Что дано? Цифры 1, 2, 3.
Что нужно сделать? Узнать количество способов составления трехзначных чисел.
Перебор вариантов можно организовать следующим образом. Выписать все числа, начинающиеся с цифры 1 в порядке их возрастания; затем – начинающиеся с цифры 2; после чего – начинающиеся с цифры 3 (см. Рисунок 2). Таких комбинаций получим 27. При переборе легко было упустить какую–нибудь из них.
Рисунок 2. Перебор объектов при помощи графа–дерева
Ответ. Возможно 27 способов записи трехзначных чисел.
Пример.
При встрече каждый из друзей пожал другому руку. Сколько рукопожатий было сделано, если друзей было четверо?
Решение.
Что дано? 4 друга.
Что нужно сделать? Узнать количество способов рукопожатия рук другу.
Четырех друзей поместим в вершины графа и проведем все возможные ребра, которые будут обозначать рукопожатия каждой пары друзей (см. Error: Reference source not found). Из рисунка видно, что граф имеет 6 ребер, значит, и рукопожатий было сделано 6.
Ответ. Возможно 6 способов рукопожатий.
Перебор объектов с помощью составления таблиц вариантов в комбинаторных задачах
Пример.
Сколько различных двухзначных чисел можно записать с помощью цифр 1, 2, 3 при условии, что цифры в числе могут повторяться?
Решение.
Что дано? Цифры 1, 2, 3.
Что нужно сделать? Узнать количество способов составления двухзначных чисел.
Составим таблицу всевозможных вариантов составления двухзначных чисел следующим образом:
Таблица 1. Таблица вариантов
вторая цифра
первая цифра
1
2
3
1
11
12
13
2
21
22
23
3
31
32
33
Из Таблица 1 видно, что можно образовать 9 различных двухзначных чисел.
Ответ. Возможно 9 способов составления двухзначных чисел.
studfiles.net