Глава VIII. Элементы комбинаторики
Глава VIII. Элементы комбинаторики
Комбинаторика это раздел математики, посвященный задачам выбора и расположения предметов из различных множеств. Типичной задачей комбинаторики является задача перечисления комбинаций, составленных из нескольких предметов.
39. Правило умножения
Пример 1. Предположим, что имеется белый хлеб, черный
хлеб, сыр, колбаса и варенье. Сколько видов бутербродов можно
приготовить?
Выпишем сначала бутерброды с белым хлебом. Это бутерброд с сыром (БС), с колбасой (БК) и вареньем (БВ). Столько
же бутербродов можно приготовить и с черным хлебом: ЧС, ЧК и ЧВ.
Всего получается 6 видов бутербродов. Это число можно найти с помощью так называемого комбинаторного правила 
умножения.
Правило умножения. Чтобы найти число комбинаций предметов двух типов, нужно число предметов первого типа умножить на число предметов второго типа. Если число предметов первого типа равно m, а число предметов второго типа равно n, то число их комбинаций равно mn.
Такое же правило действует, если имеются предметы трех, четырех или более типов.
Чтобы найти число комбинаций из предметов нескольких типов, нужно перемножить количества предметов каждого типа.
Поясним это на примере.
Пример 2. Государственные регистрационные автомобильные номера состоят из буквы, трех цифр, еще двух букв и номера региона. Буквы и цифры могут повторяться.
Буквы берутся не всякие. Можно использовать только 12 букв: А, В, Е, К, М, Н, О, Р, С, Т, У, Х. (Почему именно эти буквы? Попробуйте догадаться самостоятельно.) Цифры можно брать любые от 0 до 9. В качестве номера региона для московских автомобилей используется одно из чисел 77, 99 или 97.
Сколько всего можно составить регистрационных номеров для автомобилей в Москве?
Будем рассуждать так же, как и в предыдущем примере: первую букву можно взять одну из 12.
Первую цифру берем одну из 10, вторую — снова одну из 10 и третью снова одну из 10.
Затем две буквы подряд. Каждая выбирается из 12 разрешенных букв.
И наконец, номер региона. Он может оказаться одним из 3.
Вот сколько всего получилось вариантов:
12∙10∙10∙I0∙12∙12∙3 = 3∙103 ∙123 = 5
На самом деле номер региона не присваивается просто так. Сначала всем автомобилям присваивали номер региона 77. Впоследствии, когда эти номера были исчерпаны, стали давать номера 99, а в последнее время присваивают номера 97. Это не означает, что число машин в Москве настолько велико. Часть автомобилей снимается с регистрации, но их номера не присваиваются другим автомобилям во избежание путаницы.
Таким образом, в Москве всего может существовать более пяти миллионов автомобильных номеров. И это — не считая номеров старого образца, федеральных, дипломатических, именных и номеров автомобилей спецслужб.
Этот пункт рассказал нам о комбинаторном правиле умножения, с помощью которого можно найти число комбинаций из предметов двух, трех и более типов.
Вопросы
1. Сформулируйте комбинаторное правило умножения для подсчета числа комбинаций предметов двух типов.
2. Сформулируйте правило умножения для подсчета числа комбинаций предметов нескольких типов.
Упражнения 1. Сколько можно составить пар, выбирая:
а) первый предмет из 4, а второй из 8;
б) первый предмет из 6, а второй из 3;
в) первый предмет из 15, а второй из 12?
2. Сколько можно составить троек, выбирая:
а) первый предмет из 4, второй из 8, а третий из 5;
б) первый предмет из 7, второй из 4, а третий из 9;
в) первый предмет из 5, второй из 13, а третий из 21?
3. В школе есть все классы с 1 по 11. Каждый из них имеет дополнительную букву «а», «б», «в», «г» или «д». Например, класс 1а, 7б и тому подобное. Сколько всего классов в этой школе?
4. В автоматических камерах хранения на железнодорожных вокзалах применяется шифр, который состоит из одной буквы и трех цифр. Буквы берутся от А до К, исключая буквы Ё и И, а цифры могут быть любыми от 0 до 9, например, Д195. Сколько можно составить различных шифров?
5. На каждом барабане игрального автомата изображены символы: «вишня», «лимон» и числа от 1 до 9. Автомат имеет три одинаковых барабана, которые вращаются независимо друг от друга. Сколько всего комбинаций может выпасть?
6. Первый класс праздновал Новый Год. Каждая девочка подарила каждому мальчику открытку, а каждый мальчик подарил каждой девочке гвоздику. Чего было больше — подаренных открыток или подаренных гвоздик?
7*. Второй класс, в котором 23 ученика, но мальчиков меньше, чем девочек, отправился на экскурсию в музей. За время экскурсии каждый мальчик по одному разу дернул за косичку каждую девочку. Сколько мальчиков и девочек в классе, если всего было произведено 132 дергания за косички?
8*. На приеме в посольстве встретились две делегации, в каждой из которых было несколько дипломатов. Каждый дипломат одной делегации пожал руку каждому дипломату второй делегации, Сколько было членов в каждой делегации, если всего произошло 143 рукопожатия?
9*. Важные данные в компьютере часто защищают паролем. Предположим, что пароль содержит 8 символов: больших и малых латинских букв, цифр и некоторых знаков. Всего разрешенных символов 92. Составьте числовое выражение для общего числа возможных паролей. Пользуясь калькулятором, вычислите приближенно его значение.
40. Перестановки. Факториал
Подсчитаем, сколько существует разных способов каждому из троих людей присвоить номер от 1 до 3. Тот же самый вопрос можно задать иначе: сколькими способами можно построить трех человек в шеренгу?
На первое место можно поставить любого из трех человек. На второе — любого из двух оставшихся. И на последнее место можно поставить только одного оставшегося человека. Первого человека можно выбирать 3 способами, второго — двумя способами, а третьего — одним-единственным способом.
Таким образом, мы получили 3 ∙2∙ 1 = 6 способов перестановки трех человек. На рис. 1 показаны все эти способы.
Если людей четверо, то первый номер мы можем присвоить любому из четверых, а оставшиеся номера распределить 6 способами между тремя оставшимися. Получаем 4 ∙ 6 = 24 способа нумерации. Остается напомнить, что 6 мы получали как 3 ∙2∙ 1.
Продолжая рассуждения тем же способом, мы обнаружим, что если людей, например, семеро, то из них можно составить 7 ∙6∙ 5 ∙4∙ 3 ∙2∙ 1 = 5040 различных перестановок.
Обобщим полученные результаты. Если есть n предметов, то число способов перенумеровать их равно п∙ (п — 1)(п — 2)∙ …∙3∙2∙1
Определение. Факториалом натурального числа п называется произведение всех натуральных чисел от 1 до п. Обозначается факториал п!.
Перестановкой из п предметов называется любой способ нумерации этих предметов (способ их расположения в ряд).
Число перестановок п предметов равно п!.
Для того, чтобы в различных формулах не делать исключения для числа 0, принято соглашение
Источник
Пракикум «Решение задач по комбинаторике»
Разделы: Математика
Комбинаторика – это раздел математики, посвящённый решению задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами. Комбинаторика изучает комбинации и перестановки предметов, расположение элементов, обладающее заданными свойствами. Обычный вопрос в комбинаторных задачах: сколькими способами….
К комбинаторным задачам относятся также задачи построения магических квадратов, задачи расшифровки и кодирования.
Рождение комбинаторики как раздела математики связано с трудами великих французских математиков 17 века Блеза Паскаля (1623–1662) и Пьера Ферма (1601–1665) по теории азартных игр. Эти труды содержали принципы определения числа комбинаций элементов конечного множества. С 50-х годов 20 века интерес к комбинаторике возрождается в связи с бурным развитием кибернетики.
Основные правила комбинаторики – это правило суммы и правило произведения.
Если некоторый элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то выбор «либо А, либо В» можно сделать n + m способами.
Например, Если на тарелке лежат 5 яблок и 6 груш, то один плод можно выбрать 5 + 6 = 11 способами.
Если элемент А можно выбрать n способами, а элемент В можно выбрать m способами, то пару А и В можно выбрать n • m способами.
Например, если есть 2 разных конверта и 3 разные марки, то выбрать конверт и марку можно 6 способами (2 • 3 = 6).
Правило произведения верно и в том случае, когда рассматривают элементы нескольких множеств.
Например, если есть 2 разных конверта, 3 разные марки и 4 разные открытки, то выбрать конверт, марку и открытку можно 24 способами (2 • 3 • 4 = 24).
Произведение всех натуральных чисел от 1 до n включительно называется n – факториалом и обозначается символом n!
Например, 5! = 1 • 2 • 3 • 4 • 5 = 120.
Принято считать 0! равным 1.
Число перестановок из n равна n!
Например, если есть 3 шарика – красный, синий и зелёный, то выложить их в ряд можно 6 способами (3 • 2 • 1 = 3! = 6).
Иногда комбинаторная задача решается с помощью построения дерева возможных вариантов.
Например, решим предыдущую задачу о 3-х шарах построением дерева.
Практикум по решению задач по комбинаторике.
ЗАДАЧИ и решения
1. В вазе 6 яблок, 5 груш и 4 сливы. Сколько вариантов выбора одного плода?
2. Сколько существует вариантов покупки одной розы, если продают 3 алые, 2 алые и 4 жёлтые розы?
3. Из города А в город В ведут пять дорог, а из города В в город С ведут три дороги. Сколько путей, проходящих через В, ведут из А в С?
4. Сколькими способами можно составить пару из одной гласной и одной согласной букв слова «платок»?
гласные: а, о – 2 шт.
согласные: п, л, т, к – 4 шт.
5. Сколько танцевальных пар можно составить из 8 юношей и 6 девушек?
6. В столовой есть 4 первых блюда и 7 вторых. Сколько различных вариантов обеда из двух блюд можно заказать?
Ответ: 28 вариантов.
7. Сколько различных двузначных чисел можно составить, используя цифры 1, 4 и 7, если цифры могут повторяться?
1 цифра – 3 способа
2 цифра – 3 способа
3 цифра – 3 способа
Ответ: 9 различных двузначных чисел.
8. Сколько различных трёхзначных чисел можно составить, используя цифры 3 и 5, если цифры могут повторяться?
1 цифра – 2 способа
2 цифра – 2 способа
3 цифра – 2 способа
Ответ: 8 различных чисел.
9. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3, если цифры могут повторяться?
1 цифра – 3 способа
2 цифра – 4 способа
Ответ: 12 различных чисел.
10. Сколько существует трёхзначных чисел, у которых все цифры чётные?
1 цифра – 4 способа
2 цифра – 5 способов
3 цифра – 5 способов
Ответ: существует 100 чисел.
11. Сколько существует четных трёхзначных чисел?
1 цифра – 9 способов (1, 2, 3, 4, 5, 6, 7, 8, 9)
2 цифра – 10 способов (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
3 цифра – 5 способов (0, 2, 4, 6, 8)
Ответ: существует 450 чисел.
12.Сколько различных трёхзначных чисел можно составить из трёх различных цифр 4, 5, 6?
1 цифра – 3 способа
2 цифра – 2 способа
3 цифра – 1 способ
Ответ: 6 различных чисел.
13. Сколькими способами можно обозначить вершины треугольника, используя буквы А, В, С, D?
1 вершина – 4 способа
2 вершина – 3 способа
3 вершина – 2 способа
14. Сколько различных трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5,при условии, что ни одна цифра не повторяется?
1 цифра – 5 способов
2 цифра – 4 способа
3 цифра – 3 способа
Ответ: 60 различных чисел.
15. Сколько различных трёхзначных чисел, меньших 400, можно составить из цифр 1, 3, 5, 7, 9, если любая из этих цифр может быть использована только один раз?
1 цифра – 2 способа
2 цифра – 4 способа
3 цифра – 3 способа
Ответ: 24 различных числа.
16. Сколькими способами можно составить флаг, состоящий из трёх горизонтальных полос различных цветов, если имеется материал шести цветов?
1 полоса – 6 способов
2 полоса – 5 способов
3 полоса – 4 способа
17. Из класса выбирают 8 человек, имеющих лучшие результаты по бегу. Сколькими способами можно составить из них команду из трёх человек для участия в эстафете?
1 человек – 8 способов
2 человек – 7 способов
3 человек – 6 способов
18. В четверг в первом классе должно быть четыре урока: письмо, чтение, математика и физкультура. Сколько различных вариантов расписания можно составить на этот день?
1 урок – 4 способа
2 урок – 3 способа
3 урок – 2 способа
4 урок – 1 способ
19. В пятом классе изучаются 8 предметов. Сколько различных вариантов расписания можно составить на понедельник, если в этот день должно быть 5 уроков и все уроки разные?
1 урок – 8 вариантов
2 урок – 7 вариантов
3 урок – 6 вариантов
4 урок – 5 вариантов
5 урок – 4 варианта
8 • 7 • 6 • 5 • 4 = 6720
20. Шифр для сейфа составляется из пяти различных цифр. Сколько различных вариантов составления шифра?
1 цифра – 5 способов
2 цифра – 4 способа
3 цифра – 3 способа
4 цифра – 2 способа
5 цифра – 1 способ
5 • 4 • 3 • 2 • 1 = 120
21. Сколькими способами можно разместить 6 человек за столом, на котором поставлено 6 приборов?
22. Сколько вариантов семизначных телефонных номеров можно составить, если исключить из них номера, начинающиеся с нуля и 9?
1 цифра – 8 способов
2 цифра – 10 способов
3 цифра – 10 способов
4 цифра – 10 способов
5 цифра – 10 способов
6 цифра – 10 способов
7 цифра – 10 способов
8 • 10 • 10 • 10 • 10 • 10 • 10 = 8.000.000
23. Телефонная станция обслуживает абонентов, у которых номера телефонов состоят из 7 цифр и начинаются с 394. На сколько абонентов рассчитана эта станция?
№ телефона 394
10 • 10 • 10 • 10 = 10.000
24. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну перчатку на правую руку так, чтобы эти перчатки были различных размеров?
Левые перчатки – 6 способов
Правые перчатки – 5 способов (6 перчатка того же размера, что и левая)
25 . Из цифр 1, 2, 3, 4, 5 составляют пятизначные числа, в которых все цифры разные. Сколько таких чётных чисел?
5 цифра – 2 способа (две чётные цифры)
4 цифра – 4 способа
3 цифра – 3 способа
2 цифра – 2 способа
1 цифра – 1 способ
2 • 4 • 3 • 2 • 1 = 48
26. Сколько существует четырёхзначных чисел, составленных из нечётных цифр и делящихся на 5?
Нечётные цифр – 1, 3, 5, 7, 9.
Из них делятся на 5 – 5.
4 цифра – 1 способ (цифра 5)
3 цифра – 4 способа
2 цифра – 3 способа
1 цифра – 2 способа
27. Сколько существует пятизначных чисел, у которых третья цифра – 7, последняя цифра – чётная?
1 цифра – 9 способов (все, кроме 0)
2 цифра – 10 способов
3 цифра – 1 способ (цифра 7)
4 цифра – 10 способов
5 цифра – 5 способов (0, 2, 4, 6, 8)
9 • 10 • 1 • 10 • 5 = 4500
28. Сколько существует шестизначных чисел, у которых вторая цифра – 2, четвёртая – 4, шестая – 6, а все остальные – нечётные?
1 цифра – 5 вариантов (из 1, 3, 5, 7, 9)
2 цифра – 1 вариант (цифра 2)
3 цифра – 5 вариантов
4 цифра – 1 вариант (цифра 4)
5 цифра – 5 вариантов
6 цифра – 1 вариант (цифра 6)
5 • 1 • 5 • 1 • 5 • 1 = 125
29.Сколько различных чисел, меньших миллиона, можно записать с помощью цифр 8 и 9?
Однозначных – 2
Двузначных – 2 • 2 = 4
Трёхзначных – 2 • 2 • 2 = 8
Четырёхзначных – 2 • 2 • 2 • 2 =16
Пятизначных – 2 • 2 • 2 • 2 • 2 = 32
Шестизначных – 2 • 2 • 2 • 2 2 • 2 = 64
Всего: 2 + 4 + 8 + 16 + 32 + 64 = 126
30. В футбольной команде 11 человек. Нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?
Капитан – 11 способов
Заместитель – 10 способов
31.В классе учатся 30 человек. Сколькими способами из них можно выбрать старосту и ответственного за проездные билеты?
Староста – 30 способов
Ответ. за билеты – 29 способов
32. В походе участвуют 12 мальчиков, 10 девочек и 2 учителя. Сколько вариантов групп дежурных из трёх человек (1 мальчик, 1 девочка, 1 учитель) можно составить?
33. Сколько комбинаций из четырёх букв русского алфавита (в алфавите всего 33 буквы) можно составить при условии, что 2 соседние буквы будут разными?
1 буква – 33 способа
2 буква – 32 способа
3 буква – 32 способа
4 буква – 32 способа
Источник
