Решение комбинаторных задач
Презентация на тему : » Решение комбинаторных задач «.
Просмотр содержимого документа
«Решение комбинаторных задач»
Решение комбинаторных задач
Выполнила: ученица 9Б класса МБОУ «СОШ № 47» Советского р-на города Казани Николаева Светлана Андреевна 2017-2018 учебный год
- Это раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний (например, в генетике, информатике, статистической физике).
- Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
В кружок бального танца записались Петя, Коля, Витя, Олег, Таня, Оля, Наташа, Света. Какие танцевальные пары девочки и мальчика могут образоваться?
1) Таня — Петя, 2) Таня — Коля, 3) Таня — Витя, 4) Таня — Олег, 5) Оля — Петя, 6) Оля — Коля, 7) Оля — Витя, 8) Оля — Олег , 9) Наташа — Петя, 10) Наташа — Коля, 11) Наташа — Витя, 12) Наташа — Олег, 13) Света — Петя, 14) Света — Коля, 15) Света — Витя, 16) Света — Олег.
У мамы m яблок и n груш. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?
- Имеем набор <я, я, г, г, г>. Всего перестановок пятиэлементного множества
- 5, но мы не должны учитывать перестановки, в которых объекты одного типа меняются
- местами несколько раз, поэтому нужно поделить на возможное число таких перестановок:
- 2 · 3. Получаем в итоге
- 5/2*3=3*4*5/2*3=10 Ответ: 10 способов.
Сколькими способами может разместиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет?
Пронумеруем места в купе (с № 1 по № 4) и будем «выдавать» каждому из трех членов семьи номер места. Из 4 элементов (номеров мест) будут делаться выборки по 3 элемента, при этом важен не только состав выборки, но и порядок расположения в ней элементов (кто именно и на каком месте поедет). Число способов равно числу размещений из 4 по 3:
Можно рассуждать, непосредственно применяя правило произведения: для первого члена семьи можно выбрать любое из 4 мест, для второго — любое из 3 оставшихся, для третьего — любое из двух оставшихся, всего 4*3*2 = 24 способа рассадить семью в купе.
Ответ: 24 способа.
Сколькими способами можно расставить на полке 8 различных книг?
8! = 1*2*3*4*5 6*7*8= 40320. Ответ:40320
Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе повторяться не могут.
Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок учитывается и не все элементы одновременно выбираются. Значит, это соединение – размещение из 7 элементов по 3. Воспользуемся формулой для числа размещений: A7^3 = 7(7 – 1)(7 – 2) = 7 · 6 · 5 = 210 чисел.
- Ответ: 210.
У англичан принято давать детям несколько имен. Сколькими способами можно назвать ребенка, если общее число имел равно 300, а ему дают не более трех имен?
Решение. 1) если выбрали одно имя то количество способов его выбрать = 300
2) если два имени:
300!/(2!*(300-2)!)=44850 (комбинация из 300 по 2)
300!/(3!*(300-3)!)=4455100 (комбинация из 300 по 3)
Ответ: 4500250 способов
Сколько существует семизначных телефонных номеров, в которых все цифры разные, а номер не может начинаться с нуля?
На первый взгляд эта задача такая же, как и предыдущая, но сложность в том, что надо не учитывать те соединения, которые начинаются с нуля. Значит необходимо из существующих 10-ти цифр составить все семизначные номера телефонов, а потом от полученного числа отнять количество номеров, начинающихся с нуля. Формула будет иметь вид:
A107 – A96 = 10 · 9 · 8 · 7 · 6 · 5 · 4 – 9 · 8 · 7 · 6 · 5 · 4 = 544 320
В урне лежат 10 жетонов с числами 1,2,3, . 10. Из нее, не выбирая, вынимают 3 жетона. Во скольких случаях сумма написанных на них чисел не меньше 9
- Решение. Неблагоприятные исходы: (1,2,3), (1,2,4), (1,2,5), (1,3,4) (в этих случаях сумма чисел меньше 9). Всего исходов . Значит, всего благоприятных исходов С3\10. С3\10 – 4=120 – 4=116
Ответ: в 116 случаях
На загородную прогулку поехали 92 человека. Бутерброды с колбасой взяли 47 человек, с сыром – 38 человек, с ветчиной – 42 человека, и с сыром и с колбасой – 28 человек; и с колбасой и с ветчиной – 31 человек, и с сыром и с ветчиной – 26 человек. Все три вида бутербродов взяли 25 человек, а несколько человек вместо бутербродов захватили с собой пирожки. Сколько человек взяли с собой пирожки?
Решение задачи становится очевидно, если описать условие с помощью диаграммы Венна (в виде пересекающихся кругов, изображающих множества), приняв следующие обозначения:
- А — множество туристов, которые взяли с собой бутерброды с колбасой;
- В — множество туристов, которые взяли с собой бутерброды с сыром;
- С — множество туристов, которые взяли с собой бутерброды с ветчиной.
- Начертим диаграмму…
- На этой диаграмме видно:
- а) Количество туристов, взявших с собой бутерброды всех трех видов (25).
- б) Количество туристов, взявших с собой бутерброды каких-либо двух видов (с учетом туристов, взявших с собой бутерброды всех трех видов) – соответственно 3, 1 и 6 человек (чтобы общее число этих людей в соответствии с условием было равно 28, 26 и 31 человек).
- в) Количество туристов, взявших с собой бутерброды какого-либо одного вида (с учетом туристов, перечисленных в пунктах а и б) – соответственно 13, 9 и 10 человек (чтобы общее число этих людей в соответствии с условием было равно 47, 38 и 42 человека).
- Тогда общее число любителей бутербродов составит 25 + 3 + 1 + 6 + 13 + 9 + 10 = 67 человек, Следовательно, пирожки взяли с собой 92 – 67 = 25 человек.
Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну — на правую так, чтобы выбранные перчатки были разных размеров?
- На левую руку можно выбрать любую из 6 перчаток на левые руки. На правую – любую из пяти перчаток на правую руку. Значит, всего способов 6 * 5=30.
Ответ: 30 способов
На завтрак в школьной столовой любой ученик может выбрать булочку, ватрушку, кекс или сочник, а запить их он может соком, чаем или компотом. Сколько вариантов завтрака предлагается в школьной столовой?
Решение. Собираем все варианты в таблицу.
- Булочка (Б)Ватрушка (В)Пирожок (П)Сок (С)Чай (Ч)
- В таблице 2 строки и 3 столбца, которые образуют 6 клеток. Так как выбор еды и напитка происходит независимо, то в каждой клетке будет стоит один из возможных вариантов завтрака. Значит, всего вариантов столько, сколько клеток в таблице, то есть 6. Напиток можно выбрать двумя способами (сок или чай), а еду тремя способам.
2 ∙ 3 = 6 столовая предлагает 6 вариантов завтрака.
Ответ : 6 способов
Из города А в город В ведут пять дорог, а из города В в город С — три дороги. Сколько путей, проходящих через В, ведут из А в С?
- Представим задачу в виде графа. Очевидно, что какой бы путь не выбрал объект, продвигаясь из пункта А в пункт В, по достижении пункта В он может выбрать любой из трех путей, позволяющих ему добраться из В в С.
Следовательно, путей, ведущих из А в С и проходящих через В, существует 5 * 3 = 15. Ответ : 15 способ
В купе железнодорожного вагона имеются два противоположных дивана по 5 мест на каждом. Из 10 пассажиров этого купе четверо желают сидеть лицом к паровозу, 3 – спиной к паровозу, а остальным безразлично как сидеть. Сколькими способами могут разместиться пассажиры с учетом их желаний?
- Разместим четверых желающих пассажиров лицом к паровозу (на 5 местах). Это можно сделать А способами, разместим троих желающих пассажиров спиной к паровозу. Это можно А сделать способами, Осталось 3 «безразличных» пассажира и для них 3 места. Их можно разместить 3 способами. Значит, всего способов размещения А*А=43200.
Ответ: 43200 способов
В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить в нем 12 открыток? Сколькими способами можно купить 8 открыток? Сколькими способами можно купить 8 различных открыток?
число сочетаний из 10 по 8
В магазине «Все для чая» есть еще 4 чайные ложки. Сколькими способами можно купить комплект из чашки, блюдца и ложки?
Выберем любой из 15 комплектов предыдущей задачи. Его можно дополнить ложкой четырьмя различными способами. Поэтому общее число возможных комплектов равно 60 (60 = 15 • 4 = 5 • 3 • 4). Ответ : 60 способов
Источник
Комбинаторика. Размещения. Решение задач
Размещения. Формула для числа размещений
1) Размещения с повторениями
Если все элементы 
кортежа 
принадлежат одному и тому же множеству Х , то говорят о кортеже из элементов множества Х .
Пусть множество Х состоит из n элементов.
Определение. Кортеж длины k , составленный из элементов множества Х , называется размещением с повторениями из n элементов по k (в кортеже его элементы могут повторяться).
Число всех размещений с повторениями из n элементов по k зависит от n и от k (а не от природы множества Х ). Это число обозначается 
. Формула для его нахождения выводится с помощью правила произведения:
(1)
Пример. Сколько трёхзначных чисел может быть составлено из нечётных цифр?
Решение. Х = <1, 3, 5, 7, 9>, 
.
Трёхзначное число – это кортеж 
длины 3, составленный из элементов множества X , причем цифры в числе могут повторяться. Значит, этих чисел будет столько, сколько существует размещений с повторениями из 5 элементов по 3:
.
Заметим, что эту задачу можно было решить и с помощью правила произведения, которое работало бы и в том случае, если в условии поменять нечётные цифры на чётные. А вот понятие размещений и формула (1) в этом случае не сработали бы!
Замечание. Если повторения допускаются, то длина кортежа k может быть больше числа элементов множества Х .
2) Размещения без повторений
Пусть множество Х состоит из n элементов.
Определение. Кортеж длины k , в котором все элементы различны, составленный из элементов множества Х , называется размещением без повторений из n элементов по k (в кортеже элементы не повторяются!).
Так как повторения в кортеже не допускаются, то теперь k должно быть не больше n .
Найдём 
— число всех размещений без повторений из n элементов по k .
Для выбора элемента 
имеется n возможностей. После выбора элемента , элемент 
можно выбрать 
-м способом и так далее. Тогда
(2)
Пример. Сколько трёхзначных чисел может быть составлено из нечётных цифр так, чтобы цифры в каждом числе не повторялись?
Решение. Х = <1, 3, 5, 7, 9>, .
Трёхзначное число – это кортеж длины 3 без повторений, составленный из элементов множества X . Значит, этих чисел будет столько, сколько существует размещений без повторений из 5 элементов по 3:
.
1. Ф. Из трех стаканов сока — ананасового (а), брусничного (б) и виноградного (в) — Иван решил последовательно выпить два. Перечислить все варианты, которыми это можно сделать.
Это задача о выборе двух элементов из трех с учетом порядка выбора. Перечислим эти варианты:
Если учащимся известна формула для числа размещений, то количество вариантов равно: А 
вариантов.
Ответ: 6 вариантов.
2.Ф. Сколькими способами могут быть заняты первое, второе и третье места (по одному человеку на место) на соревнованиях, в которых участвуют: 1) 5 человек; 2) 6 человек?
Это задача о выборе трех элементов из 5 или 6 с учетом порядка выбора.
1)По правилу произведения 5 • 4 • 3 = 60 способов.
2)По правилу произведения 
= 120 способов. Если учащиеся знают формулу для числа размещений, то получаем соответственно:
A 
A 
Ответ: 1) 60 способов; 2) 120 способов.
М-задачи из уч. пособия А.Г.Мордковича
Т- под ред. С.А.Теляковского
3. Т. Сколькими способами может разместиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет?
Пронумеруем места в купе (с № 1 по № 4) и будем «выдавать» каждому из трех членов семьи номер места. Из 4 элементов (номеров мест) будут делаться выборки по 3 элемента, при этом важен не только состав выборки, но и порядок расположения в ней элементов (кто именно и на каком месте поедет). Число способов равно числу размещений из 4 по 3:
Можно рассуждать, непосредственно применяя правило произведения: для первого члена семьи можно выбрать любое из 4 мест, для второго — любое из 3 оставшихся, для третьего — любое из двух оставшихся, всего 
способа рассадить семью в купе.
Ответ: 24 способа.
4. Т. Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать?
Из 30 элементов выбираем 2, причем порядок выбора имеет значение. Количество способов выбора равно A 
= 30 • 29 = 870 способов.
Ответ: 870 способов.
5. Т. Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанции 100 м?
Выбор из 8 по 3 с учетом порядка: A 
= 336 способов.
Ответ: 336 способов.
6. Т. На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?
Выбираем из 7 запасных путей 4 пути для размещения на них поездов; порядок выбора имеет значение: A 
= 
840 способов.
Ответ: 840 способов.
7. Т. Сколькими способами можно изготовить трехцветный флаг с горизонтальными полосами, если имеется материал 7 различных цветов?
Выбираем из 7 разноцветных материалов 3 полосы для флага; порядок выбора имеет значение (флаги из трех одинаковых цветов, расположенных в разном порядке, — разные).
A 
= 210 способов.
Ответ: 210 способов.
8. Т. На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4×100 м на первом, втором, третьем и четвертом этапах?
Выбор из 12 по 4 с учетом порядка: A 
= 11 880 способов.
Ответ: 11880 способов.
9. М. Сколькими способами могут быть распределены первая, вторая и третья премии между 15 участниками конкурса?
Выбираем 3 призеров из 15 участников конкурса с учетом порядка (кому какая премия):
A 
= 2 730 способов.
10. Т. Сколькими способами 6 студентов, сдающих эк. замен, могут занять места в аудитории, в которой стоит 20 одноместных столов?
Выбираем 6 столов для студентов из 20 имеющихся: порядок выбора учитывается (кто сидит у окна, кто около преподавателя и т. п.):
А 
= 27 907 200 способов.
Ответ: 27 907 200 способов.
11. Т. На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места: а) 2 фотографии; б) 4 фотографии; в) 6 фотографий?
а) Выбираем 2 места для фотографий из 6 свободных мест в альбоме: А 
= 30 способов.
б) Выбираем 4 места для фотографий из А 
= 360 способов.
в) Выбираем 6 мест из 6 (делаем всевозможные перестановки из 6 фотографий):
А 
= 6! = 720 способов.
Ответ: а) 30 способов; б) 360 способов; в) 720 способов.
12. М. На плоскости отметили 5 точек. Их надо обозначить латинскими буквами. Сколькими способами это можно сделать (в латинском алфавите 26 букв)?
Выбираем 5 букв для обозначения точек из 26 букв в алфавите; порядок выбора имеет значение (какую точку какой буквой обозначим): А 
= 7 893 600 способов.
Ответ: 7 893 600 способов.
13. Т. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1, 3, 5, 7, 9; б) 0, 2, 4,
а) Выбираем 4 цифры из 5 данных; порядок выбора имеет значение: А 
= 120 чисел.
б) Выбираем 4 цифры из 5, но на первое место нельзя выбирать ноль.
Используем метод исключения лишних элементов: если на первое место выбран ноль, то после этого выбираем еще на 3 места цифры из 4 оставшихся, получаем А 
= 24 «нулевых» комбинаций, которые недопустимы.
Количество четырехзначных чисел, которые можно составить из данных 5 чисел, равно:
А 
= 120 — 24 = 96 чисел.
Можно рассуждать, непосредственно используя правило произведения: первый выбор — 4 варианта, второй выбор — 4 варианта (включая ноль), третий выбор — 3 варианта, четвертый выбор -2 варианта. Всего 4 • 4 • 3 • 2 = 96 чисел.
Ответ: а) 120 чисел; б) 96 чисел.
14. Т. Из трехзначных чисел, записанных с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 (без повторения цифр), сколько таких, в которых:
а) не встречаются цифры 6 и 7;
б) цифра 8 является последней?
а) Выбираем 3 цифры из 7 (без 6 и без 7) с учетом порядка выбора; число вариантов: А 
= 
= 210 чисел.
б) Фиксируем цифру 8 на последнем месте; на остальные два места перед ней можно выбрать любые 2 цифры из 8 оставшихся ( с учетом порядка выбора). Количество вариантов: А 
= 56 чисел.
Ответ: а) 210 чисел; б) 56 чисел.
15. М. Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от нуля?
Выбираем из 10 цифр семь, причем первый выбор делается из 9 цифр (без нуля). Используя метод исключения лишних вариантов, получаем: А 
А 
544 320 номеров.
Ответ: 544 320 телефонных номеров.
16. Т. Сколько различных трехзначных чисел (без повторения цифр) можно составить из цифр 1, 2, 3, 4, 5, таких, которые являются: а) четными; б) кратными 5?
Выбираем 3 цифры из 5 данных, причем:
а) последней цифрой должна быть 2 или 4; количество вариантов А 
(фиксирована 2) + А (фиксирована 4) = 
= 24 числа;
б) последней цифрой должна быть 5; количество вариантов равно А (фиксирована 5) = 
= 12 чисел.
Ответ: а) 24 числа; б) 12 чисел.
17. Т. Номер машины в некотором городе состоит из двух различных букв, взятых из набора М, Н, К, Т, С, и трех различных цифр. Сколько машин можно обеспечить такими номерами?
Выбираем (без повторений) 2 буквы из 5 и 3 цифры из 10; порядок выбора учитывается (номера 012 КТ и 102 ТК — разные). Количество способов: выбор букв: А 
= 20; выбор цифр: А 
= 720.
Каждый вариант выбора букв может сочетаться с каждым вариантом выбора цифр, поэтому по правилу произведения общее число способов равно: А 
720 = 14 400 способов.
Ответ: 14 400 способов.
18.Т. Сколько команд участвовало в финале первенства, если известно, что каждая команда сыграла с каждой из остальных по одной игре на своем поле и по одной игре на поле соперника, причем всего было сыграно 30 игр?
Поскольку каждая пара команд сыграла между собой по две игры (на своем и на чужом поле), то выбор пары осуществляется с учетом порядка, т. е. составляются всевозможные размещения из n по 2. По условию задачи А 
n 
= 
, n = 6.
19. Т. Из группы туристов требуется выбрать дежурного и его помощника. Если туристов было бы на одного больше, то возможностей выбора было бы в 1,25 раза больше. Сколько туристов в группе?
Выбор пары из совокупности с учетом порядка (размещения). По условию задачи: По условию задачи А 
(n — 1) , n+1=1,25 
; 4(n+1)=5(n-1); n=9
Ответ: 9 туристов.
20. Ф. Сколькими способами четыре пассажира -Алексеев, Смирнов, Федоров и Харитонов — могут разместиться в Девяти вагонах поезда, если:
а) все они хотят ехать в разных вагонах;
б) Алексеев и Смирнов хотят ехать в одном вагоне, а Федоров и Харитонов — в других вагонах, причем различных?
Вагоны поезда пронумерованы; осуществляется выбор 4 из 9 вагонов для размещения пассажиров; порядок выбора имеет значение (каждому пассажиру сообщаем номер вагона).
б) Двое едут в одном вагоне, а двое — в других, причем различных. «Склеиваем» два элемента из 4; количество способов размещения равно: А 
= 504.
Ответ: а) 3 024 способа; б) 504 способа.
21. Ф. Высказать гипотезу о числе всевозможных разбиений п элементов на 3 группы.
Поступим следующим образом. Сопоставим каждому из п элементов свою ячейку, в которую будем записывать номер группы, в которую будет помещен этот элемент. Получим линейку из п ячеек, в каждой из которых может быть записана либо 1, либо 2, либо 3:
Источник
