Число способов выбора из шести компьютеров четыре для теста равно
Комбинаторика – это раздел математики, посвящённый решению задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами. Комбинаторика изучает комбинации и перестановки предметов, расположение элементов, обладающее заданными свойствами. Обычный вопрос в комбинаторных задачах: сколькими способами….
К комбинаторным задачам относятся также задачи построения магических квадратов, задачи расшифровки и кодирования.
Рождение комбинаторики как раздела математики связано с трудами великих французских математиков 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 сливы. Сколько вариантов выбора одного плода?
6 + 5 + 4 = 15
Ответ: 15 вариантов.
2. Сколько существует вариантов покупки одной розы, если продают 3 алые, 2 алые и 4 жёлтые розы?
3. Из города А в город В ведут пять дорог, а из города В в город С ведут три дороги. Сколько путей, проходящих через В, ведут из А в С?
4. Сколькими способами можно составить пару из одной гласной и одной согласной букв слова «платок»?
гласные: а, о – 2 шт.
согласные: п, л, т, к – 4 шт.2 • 4 = 8
Ответ: 8 способами.
5. Сколько танцевальных пар можно составить из 8 юношей и 6 девушек?
6. В столовой есть 4 первых блюда и 7 вторых. Сколько различных вариантов обеда из двух блюд можно заказать?
Ответ: 28 вариантов.
7. Сколько различных двузначных чисел можно составить, используя цифры 1, 4 и 7, если цифры могут повторяться?
1 цифра – 3 способа
2 цифра – 3 способа
3 цифра – 3 способа3 • 3 = 9
Ответ: 9 различных двузначных чисел.
8. Сколько различных трёхзначных чисел можно составить, используя цифры 3 и 5, если цифры могут повторяться?
1 цифра – 2 способа
2 цифра – 2 способа
3 цифра – 2 способа2 • 2 • 2 = 8
Ответ: 8 различных чисел.
9. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3, если цифры могут повторяться?
1 цифра – 3 способа
2 цифра – 4 способа3 • 4 = 12
Ответ: 12 различных чисел.
10. Сколько существует трёхзначных чисел, у которых все цифры чётные?
Чётные цифры – 0, 2, 4, 6, 8.
1 цифра – 4 способа
2 цифра – 5 способов
3 цифра – 5 способов4 • 5 • 5 = 100
Ответ: существует 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)9 • 10 • 5 = 450
Ответ: существует 450 чисел.
12.Сколько различных трёхзначных чисел можно составить из трёх различных цифр 4, 5, 6?
1 цифра – 3 способа
2 цифра – 2 способа
3 цифра – 1 способ3 • 2 • 1 = 6
Ответ: 6 различных чисел.
13. Сколькими способами можно обозначить вершины треугольника, используя буквы А, В, С, D?
1 вершина – 4 способа
2 вершина – 3 способа
3 вершина – 2 способа4 • 3 • 2 = 24
Ответ: 24 способа.
14. Сколько различных трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5,при условии, что ни одна цифра не повторяется?
1 цифра – 5 способов
2 цифра – 4 способа
3 цифра – 3 способа5 • 4 • 3 = 60
Ответ: 60 различных чисел.
15. Сколько различных трёхзначных чисел, меньших 400, можно составить из цифр 1, 3, 5, 7, 9, если любая из этих цифр может быть использована только один раз?
1 цифра – 2 способа
2 цифра – 4 способа
3 цифра – 3 способа2 • 4 • 3 = 24
Ответ: 24 различных числа.
16. Сколькими способами можно составить флаг, состоящий из трёх горизонтальных полос различных цветов, если имеется материал шести цветов?
1 полоса – 6 способов
2 полоса – 5 способов
3 полоса – 4 способа6 • 5 • 4 = 120
Ответ: 120 способов.
17. Из класса выбирают 8 человек, имеющих лучшие результаты по бегу. Сколькими способами можно составить из них команду из трёх человек для участия в эстафете?
1 человек – 8 способов
2 человек – 7 способов
3 человек – 6 способов8 • 7 • 6 = 336
Ответ: 336 способов.
18. В четверг в первом классе должно быть четыре урока: письмо, чтение, математика и физкультура. Сколько различных вариантов расписания можно составить на этот день?
1 урок – 4 способа
2 урок – 3 способа
3 урок – 2 способа
4 урок – 1 способ4 • 3 • 2 • 1 = 24
Ответ: 24 варианта.
19. В пятом классе изучаются 8 предметов. Сколько различных вариантов расписания можно составить на понедельник, если в этот день должно быть 5 уроков и все уроки разные?
1 урок – 8 вариантов
2 урок – 7 вариантов
3 урок – 6 вариантов
4 урок – 5 вариантов
5 урок – 4 варианта8 • 7 • 6 • 5 • 4 = 6720
Ответ: 6720 вариантов.
20. Шифр для сейфа составляется из пяти различных цифр. Сколько различных вариантов составления шифра?
1 цифра – 5 способов
2 цифра – 4 способа
3 цифра – 3 способа
4 цифра – 2 способа
5 цифра – 1 способ5 • 4 • 3 • 2 • 1 = 120
Ответ: 120 вариантов.
21. Сколькими способами можно разместить 6 человек за столом, на котором поставлено 6 приборов?
6 • 5 • 4 • 3 • 2 • 1 = 720
Ответ: 720 способов.
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
Ответ: 8.000.000 вариантов.
23. Телефонная станция обслуживает абонентов, у которых номера телефонов состоят из 7 цифр и начинаются с 394. На сколько абонентов рассчитана эта станция?
№ телефона 394
10 • 10 • 10 • 10 = 10.000
Ответ: 10.000 абонентов.
24. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну перчатку на правую руку так, чтобы эти перчатки были различных размеров?
Левые перчатки – 6 способов
Правые перчатки – 5 способов (6 перчатка того же размера, что и левая)6 • 5 = 30
Ответ: 30 способов.
25 . Из цифр 1, 2, 3, 4, 5 составляют пятизначные числа, в которых все цифры разные. Сколько таких чётных чисел?
5 цифра – 2 способа (две чётные цифры)
4 цифра – 4 способа
3 цифра – 3 способа
2 цифра – 2 способа
1 цифра – 1 способ2 • 4 • 3 • 2 • 1 = 48
Ответ: 48 чётных чисел.
26. Сколько существует четырёхзначных чисел, составленных из нечётных цифр и делящихся на 5?
Нечётные цифр – 1, 3, 5, 7, 9.
Из них делятся на 5 – 5.
4 цифра – 1 способ (цифра 5)
3 цифра – 4 способа
2 цифра – 3 способа
1 цифра – 2 способа1 • 4 • 3 • 2 = 24
Ответ: 24 числа.
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
Ответ: 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
Ответ: 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
Ответ: 126 чисел.
30. В футбольной команде 11 человек. Нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?
Капитан – 11 способов
Заместитель – 10 способов11 • 10 = 110
Ответ: 110 способов.
31.В классе учатся 30 человек. Сколькими способами из них можно выбрать старосту и ответственного за проездные билеты?
Староста – 30 способов
Ответ. за билеты – 29 способов30 • 29 = 870
Ответ: 870 способов.
32. В походе участвуют 12 мальчиков, 10 девочек и 2 учителя. Сколько вариантов групп дежурных из трёх человек (1 мальчик, 1 девочка, 1 учитель) можно составить?
12 • 10 • 2 = 240
Ответ: 240 способов.
33. Сколько комбинаций из четырёх букв русского алфавита (в алфавите всего 33 буквы) можно составить при условии, что 2 соседние буквы будут разными?
1 буква – 33 способа
2 буква – 32 способа
3 буква – 32 способа
4 буква – 32 способа33 • 32 • 32 • 32 = 1.081.344
Ответ: 1.081.344 комбинаций.
Комбинаторика – раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.
Пример 1.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?
Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.
По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.
Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены:
Пример 2.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?
Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.
После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.
По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.
Сочетания без повторений. Сочетания с повторениями
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?
Пример 3.
Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?
Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?
.
Пример 4.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.
.
Размещения без повторений. Размещения с повторениями
Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Пример 5.
В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?
Пример 6.
У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?
Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:
.
Перестановки без повторений. Перестановки с повторениями
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Пример 7.
Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?
Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.
Пример 8.
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
Муниципальный координатор по работе с детьми с повышенной учебной мотивацией в области математики.
МБОУ «Лицей №6 имени М.А. Булатова»
Решение задач по комбинаторике.
Учитель
МБОУ «СОШ№10 им. Е.И. Зеленко» г. Курска
Коротковская О.С.
Курск – 2020
Вступление.
Так что же такое комбинаторика? И какими задачами она занимается? Комбинаторика и слово комбинация очень похожи и имеют прямое отношение друг к другу. В комбинаторике изучают различные комбинации элементов множества и отношения на этих множествах. Впервые термин "комбинаторика" ввел Лейбниц, который в 1666 году опубликовал большой труд "Рассуждения о комбинаторном искусстве".
Комбинаторика – раздел математики, который занимается решением комбинаторных задач.
Комбинаторные задачи – это задачи, в которых необходимо составить комбинации каких-либо элементов из заданного набора по определённым условиям и (или) подсчитать количество получившихся комбинаций.
В комбинаторике существует несколько способов решения комбинаторных задач. Сейчас мы их подробно рассмотрим.
Способ 1. Перебор всех возможных вариантов.
Рассмотрим сущность способа 1 на конкретном примере.
Пример 1. Из группы теннисистов, в которую входят четыре человека – Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары?
Решение. 1. Составим сначала все пары, в которые входит Антонов (для краткости будем писать первые буквы фамилий). Получим три пары: АГ, АС, АФ.
2. Выпишем теперь пары, в которые входит Григорьев, но не входит Антонов. Таких пар две: ГС, ГФ.
3. Составим пары, в которые входит Сергеев, но не входят Антонов и Григорьев. Такая пара только одна: СФ.
4. Делаем вывод, что других вариантов составления пар нет, так как все пары, в которые входит Федоров, уже составлены.
5. Итак, мы получили 6 пар: АГ, АС, АФ, ГС, ГФ, СФ. Значит, всего существует 6 вариантов выбора тренером пары теннисистов из данной группы.
Способ рассуждений, которым мы воспользовались при решении задачи, называют перебором возможных вариантов.
Примечание. В данном примере нам не важен порядок выбора пары: Антонов и Григорьев или Григорьев и Антонов,
Рассмотрим пример задачи, где порядок выбора пары важен.
Пример 2. Три друга – Антон, Борис и Виктор – приобрели два билета на футбольный матч на 1-е и 2-е места первого ряда стадиона. Сколько у друзей есть вариантов занять эти два места на стадионе?
Решение. 1. Если на матч пойдут Антон и Борис, то они могут занять места двумя способами: 1-е место – Антон, 2-е – Борис, или наоборот. Аналогично Антон и Виктор, Борис и Виктор.
2. Таким образом, мы получили 6 вариантов: АБ, БА, АВ, ВА, БВ, ВБ.
Рассмотрим пример на применение этого же способа на примере задачи с цифрами.
Пример 3. Сколько различных трехзначных чисел можно записать с помощью цифр 1, 2, 3 при условии, что цифры в числе могут повторяться?
Решение. Перебор вариантов можно организовать следующим образом. Выписать все числа, начинающиеся с цифры 1 в порядке их возрастания; затем – начинающиеся с цифры 2; после чего – начинающиеся с цифры 3. Таких комбинаций получим 27. При переборе легко было упустить какую-нибудь из них.
Способ 2. Подсчет вариантов с помощью графов.
Эффективным приемом, организующим подсчет, является построение графов. Так называют геометрические фигуры, состоящие из точек (их называют вершинами) и соединяющих их отрезков (называемых ребрами графа).
Пример 4. Сколько двузначных чисел можно составить, используя цифры 1, 4 и 7?
Решение. 1. Для того чтобы не пропустить и не повторить ни одно из чисел, будем выписывать их в порядке возрастания. Сначала запишем числа, начинающиеся с цифры 1, затем с цифры 4 и, наконец, с цифры 7: 11, 14, 17, 41, 44, 47, 71, 74, 77.
2. Таким образом, из трех данных цифр можно составить всего 9 различных двузначных чисел.
Рассмотрим два вида графов:
Граф-дерево (называют за внешнее сходство с деревом).
С помощью дерева проиллюстрируем проведенный перебор вариантов в примере 1.
Графы, позволяют в наглядной форме представить идею комбинирования и процесс подсчета комбинаторных объектов. Для подведения учащихся к следующим комбинаторным методам целесообразно рассмотреть задачу, в которой количество всевозможных комбинаций из данных элементов велико и процесс их подсчета затруднителен.
На первом месте в двузначном числе может стоять одна из цифр 1, 4 или 7; на втором – (при условии, что цифры могут повторяться) также любая из трех цифр. Таким образом из рисунка видно, что из трех цифр 1, 4, 7 можно составить 9 различных чисел.
Таким образом, с помощью графа-дерева подсчет вариантов гораздо легче производить. Также вычерчивать дерево вариантов полезно, когда требуется записать все существующие комбинации элементов.
Полный граф. Используется для решения задач, в которых все элементы множества взаимосвязаны.
Пример 5. При встрече каждый из друзей пожал другому руку (каждый пожал каждому). Сколько рукопожатий было сделано, если друзей было четверо?
Четырех друзей поместим в вершины графа и проведем все возможные ребра. В данном случае отрезки-ребра обозначают рукопожатия каждой пары друзей.
Из рисунка видно, что граф имеет 6 ребер, значит, и рукопожатий было сделано 6.
Способ 3. Перебор с помощью таблицы вариантов .
Ее можно использовать, когда составляемые комбинации состоят из двух элементов. Рассмотрим сущность способа на конкретной задаче.
Пример 6. Записать всевозможные двузначные числа, используя при этом цифры 0, 1, 2 и 3. Подсчитать их количество N .
Решение. Для подсчета образующих чисел составим таблицу 1:
Таблица 1 Таблица 2
Решением задачи будет таблица 2. всего вариантов чисел будет N =3·4=12
Способ 4. Использование правил суммы и произведения
Сущность способа рассмотрим на примере задачи 7.
Задача про «Суеверного председателя».
«Опять восьмерка!» - горестно воскликнул председатель клуба велосипедистов, взглянув на прогнутое колесо своего велосипеда. «А все почему? Да потому, что у меня членский билет № 888 – целых три восьмерки. И теперь не проходит и месяца, чтобы то на одном, то на другом колесе не появилась восьмерка. Надо менять номер билета! А чтобы меня не обвинили в суеверии, проведу ка я перерегистрацию всех членов клуба и буду выдавать только билеты с номерами, в которые не входит ни одна восьмерка. Не знаю только, хватит ли на всех номеров – ведь у нас в клубе почти 600 членов. Неужели придется сначала выписать все номера от 000 до 999, а затем вычеркивать из них все номера с восьмерками?»
Чтобы помочь председателю, нам нужно решить такую комбинаторную задачу (учащимся можно предложить ее сформулировать):
Задача 7. Сколько существует трехзначных номеров, не содержащих цифры 8?
Решение. 1) Сначала найдем количество однозначных номеров, отличных от 8. Ясно, что таких номеров девять: 0,1,2,3,4,5,6,7,9. 2) Найдем все двузначные номера, не содержащие восьмерок. Их можно составить так: взять любой из найденных однозначных номеров и написать после него любую из девяти допустимых цифр. В результате из каждого однозначного номера получится 9 двузначных, т. е. всего получится 9·9 = 9 2 двузначных номеров.
3) Итак, существует 9 2 = 81 двузначный номер без цифры 8. Но к каждому из этих номеров можно приписать справа любую из цифр 0,1,2,3,4,5,6,7,9 и получить трехзначный номер, не содержащий цифру 8. 4) При этом получаются все трехзначные номера с требуемым свойством. В результате мы нашли 9 2 ·9 = 9 3 = 729 трехзначных номеров без восьмерок.
Примечание. Если бы председатель клуба был еще суевернее и отказался и от цифры 0, поскольку она походит на вытянутое колесо, то он смог бы составить лишь 8 3 = 512 трехзначных номеров и их уже не хватило бы на всех членов клуба.
Пример 8. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?
Решение: 1) По условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. 2) Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу суммы, можно осуществить 5+4=9 способами.
Пример 9. Сколько трехзначных чисел можно составить, используя цифры 7, 4 и 5?
Решение: 1) В данной задаче рассматриваются трехзначные числа, так как цифры в записи этих чисел могут повторяться, то цифру сотен, цифру десятков и цифру единиц можно выбрать тремя способами каждую.
2)Поскольку запись трехзначного числа представляет собой упорядоченный набор из трех элементов, то, согласно правилу произведения, его выбор можно осуществить 27 способами, так как 3∙3∙3=27.
Правило умножения приводит к важному понятию факториала. Давайте на примере разберем это понятие.
Пример 10. Сколько существует комбинаций из шести букв: А, Б, В, Г, Д, Е. Буквы не повторяются.
Решение: На первое место мы можем поставить шесть букв, на второе место - уже пять, так как буквы не повторяются, на третье - соответственно четыре, на четвертое - три, на пятое - две, и на шестое - букву.
Используем правило умножения: 6*5*4*3*2*1=720.
Ответ: 720 способов расстановки букв без повторения.
Произведение подряд идущих первых n натуральных чисел обозначают n! (n факториал): n!=1 ∗ 2 ∗ … ∗ (n−1) ∗ n, n факториал – состоящий из n множителей.
Заметим важное свойство факториала: n!=(n−1)! ∗ n. Данное свойство значительно упрощает решение задач, где присутствует факториал. Например, для вычисления задач вот такого типа: . Совсем необязательно вычислять все факториалы. Можно все переписать вот в таком виде: . Сократив нашу дробь, получим гораздо более простое выражение: 4 ∗ 9 ∗ 10=360.
Способ 5. Решение комбинаторных задач с использованием формул
Кроме основных правил, способов перебора и графов пользуются основными понятиями комбинаторики, которые сопровождаются формулами для подсчета числа отдельных видов комбинаций, встречающиеся наиболее часто. При решении задач на комбинаторные соединения помогает таблица «Общая модель комбинаторной задачи и ее модификации», которая представлена ниже.
Комбинаторика – раздел математики, занимающийся изучением количества возможных комбинаций определенного типа, которые возможно сделать из некоторого набора элементов. Эти вычисления необходимы для решения различных задач в теории вероятностей и получения распределений случайных величин.
Правила в комбинаторике
Правило суммы: если есть взаимоисключающие друг друга действия A и B, которые можно выполнить способами m и n соответственно, то выполнить любое из этих действий можно m + n способами.
Правило произведения: если есть последовательность действий k, и первое действие его можно выполнить n1 способом, второе n2 и далее до nk, то все действия этой последовательности можно выполнить n1 · n2 · nk способами.
Элементы комбинаторики
Размещения из n по k – упорядоченное множество, состоящее из k элементов, которые выбраны из n элементов. Для расчета способов размещения следует воспользоваться формулой: P k n = n! / (n - k)!
Перестановки – конечное множество, в котором указан порядок его элементов. Количество перестановок вычисляется по формуле: Pn = n!
Сочетания из n по k – неупорядоченное множество, состоящее из k элементов, которые выбраны из n элементов. Число сочетаний из n элементов по k рассчитывается так: n! / (n - k)! · k!
Калькулятор разложения бинома Ньютона с использованием треугольника Паскаля.
Калькулятор числа перестановок позволяет вычислить число возможных сочетаний из заданного количества элементов.
Калькулятор числа размещений вычисляет число возможных размещений из заданного количества объектов n по k.
Калькулятор числа сочетаний позволяет вычислить число возможных сочетаний из заданного количества объектов n по k.
В повседневной жизни нередко встречаются задачи, которые имеют несколько различных вариантов решения. Чтобы сделать правильный выбор, важно не пропустить ни один из них. Для этого надо уметь осуществлять перебор всех возможных вариантов или подсчитывать их число.
Запишите тему: Элементы комбинаторики
Запишите определение: Задачи, в которых требуется осуществить перебор всех возможных вариантов решения или подсчитать их число называются комбинаторными.
Область математики, в которой изучают комбинаторные задачи, называется комбинаторикой.
Комбинаторика возникла в XVI в., и первоначально в ней рассматривались комбинаторные задачи, связанные в основном с азартными играми.
В процессе изучения таких задач были выработаны некоторые общие подходы к их решению, получены формулы для подсчета числа различных комбинаций.
Запишите правило суммы:
Если объект a можно выбрать m способами, а объект b − k способами (не такими, как a), то выбор «либо a, либо b» можно осуществить m + k способами.
Прочитайте пример задачи с решением, кратко запишите этот пример в тетрадь (рассуждения записывать не надо).
Задача 1. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?
Решение. По условию задачи яблоко можно выбрать пятью способами, апельсин — четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу сложения, можно осуществить 5 + 4 = 9 способами.
Запишите правило умножения:
Если объект a можно выбрать m способами, а объект b − k способами, то пару (a, b) можно выбрать mk способами.
Прочитайте примеры задач с решением, кратко запишите 2,4,5,6 задачи в тетрадь (рассуждения записывать не надо, только краткое условие и решение).
Задача 2. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать пару плодов, состоящую из яблока и апельсина?
Решение. По условию задачи, яблоко можно выбрать пятью способами, апельсин — четырьмя. Так как в задаче речь идет о выборе пары (яблоко, апельсин), то ее, согласно правилу умножения, можно выбрать 5 ⋅ 4 = 20 способами.
Задача 3. Сколько всего двузначных чисел можно составить из цифр 7, 4 и 5 при условии, что они в записи числа не повторяются?
Решение. Чтобы записать двузначное число, надо выбрать цифру десятков и цифру единиц. Согласно условию, на месте десятков в записи числа может быть любая из цифр 7, 4 и 5. Другим словами, выбрать цифру десятков можно тремя способами. После того как цифра десятков определена, для выбора цифры единиц остается две возможности, поскольку цифры в записи числа не должны повторяться. Так как любое двузначное число — это упорядоченная пара, состоящая из цифры десятков и цифры единиц, то ее выбор, согласно правилу умножения, можно осуществить шестью способами (3 ⋅ 2 = 6).
Правила сложения и умножения, сформулированные для двух объектов, можно обобщить и на случай t объектов.
Задача 4. Сколько трехзначных чисел можно составить, используя цифры 7, 4 и 5?
Решение. В данной задаче рассматриваются трехзначные числа. Так как цифры в записи этих чисел могут повторяться, то цифру сотен, цифру десятков и цифру единиц можно выбрать тремя способами каждую. Поскольку запись трехзначного числа представляет собой упорядоченный набор из трех элементов, то, согласно правилу произведения, его выбор можно осуществить 27 способами, так как 3 ⋅ 3 ⋅ 3 = 27.
Задача 5. Сколько всего четырехзначных чисел можно составить из цифр 0 и 3?
Решение. Запись четырехзначного числа представляет собой упорядоченный набор (кортеж) из четырех цифр. Первую цифру — цифру тысяч — можно выбрать только одним способом, так как запись числа не может начинаться с нуля. Цифрой сотен может быть либо ноль, либо три, т. е. имеется два способа выбора. Столько же способов выбора имеется для цифры десятков и цифры единиц.
Итак, цифру тысяч можно выбрать одним способом, цифру сотен — двумя, цифру десятков — двумя, цифру единиц — двумя. Чтобы узнать, сколько всего четырехзначных чисел можно составить из цифр 0 и 3, согласно правилу умножения, способы выбора каждой цифры надо перемножить: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8.
Таким образом, имеем 8 четырехзначных чисел.
Задача 6. Сколько трехзначных чисел можно записать с помощью цифр 0, 1, 3, 6, 7 и 9, если каждая из них может быть использована в записи только один раз?
Решение. Так как запись числа не может начинаться с нуля, то цифру сотен можно выбрать пятью способами; выбор цифры десятков можно осуществить также пятью способами, поскольку цифры в записи числа не должны повторяться, а одна из шести данных цифр будет уже использована для записи сотен; после выбора двух цифр (для записи сотен и десятков) выбрать цифру единиц из данных шести можно четырьмя способами. Отсюда, по правилу умножения, получаем, что трехзначных чисел (из данных шести цифр) можно образовать 5 ⋅ 5 ⋅ 4 = 100 способами.
Практическая часть
Используя правило произведения, решите самостоятельно следующие задачи:
Школьники из Волгограда собрались на каникулы поехать в Москву, посетив по дороге Нижний Новгород. Из Волгограда в Нижний Новгород можно отправиться на теплоходе или поезде, а из Нижнего Новгорода в Москву — на самолете, теплоходе или автобусе. Сколькими различными способами ребята могут осуществить свое путешествие? Назовите все возможные варианты этого путешествия.
Сколько различных двузначных чисел можно записать с помощью цифр 3, 4, 5 и 6? Сколько различных двузначных чисел можно записать, используя при записи числа каждую из указанных цифр только один раз? Чтобы ответить на первый вопрос задачи используйте задачу 4. Чтобы ответить на второй вопрос задачи используйте задачу 6, но учтите, что у вас нет нуля.
Девять школьников, сдавая экзамены по математике, русскому и английскому языку, получили отметки «4» и «5». Можно ли утверждать, что по крайней мере двое из них получили по каждому предмету одинаковые отметки? Сколько всевозможных трехзначных чисел можно составить из цифр 1, 2, 3 и 4 так, чтобы цифры в записи числа не повторялись? Изменится ли решение этой задачи, если вместо цифры 4 будет дана цифра 0?
Сколько всевозможных четырехзначных чисел можно составить, используя для записи цифры 1, 2, 3 и 4? Какова разность между самым большим и самым малым из них?
Из цифр 0,1,2,3,4 составляют всевозможные пятизначные числа, причем так, что в записи каждого числа содержатся все данные цифры. Сколько можно составить таких чисел? Чему будет равна разность между наибольшим и наименьшим из полученных чисел?
Проверьте себя:
В НН М
Из Волгограда в Нижний Новгород выбор из 2 видов транспорта (теплоход т и поезд п), а из Нижнего Новгорода в Москву – из 3 (самолет с, теплоход т, автобус а). Получаем 2•3=6. Ответ 6 вариантов. 6 это мало, можно все перебрать:
Двузначное число обозначим двумя точками: • •
Выпишем данные цифры: 3,4,5,6.
Ответим на первый вопрос. На первое место числа можно поставить любую из 4 цифр и на второе место любую из 4 цифр:
4•4=16. Получится 16 чисел.
Ответим на второй вопрос: если нельзя повторять цифры, то когда мы одну возьмем, останется только 3:
4•3=12. Получится 12 чисел. Можно убедиться в этом, выписав их все, используя метод перебора от меньшего к большему, чтобы ничего не пропустить:
3. Рассуждайте так: пришел школьник на экзамен по математике, сколько у него возможностей получить отметку (4 или 5, то есть 2 возможности)? Потом на экзамен по русскому, сколько вариантов получить отметку? И на английский… Итак 2•2•2=8. Всего 8 вариантов распределения отметок. Можно выписать их все, чтобы убедиться: 444;445;454;455;544;545;554;555. 8 вариантов распределения оценок. А учеников 9, значит, хотя бы у двоих оценки совпадут.
4. • • • • 1,2,3,4 -4 цифры
• • • • • 0,1,2,3,4 – 5 цифр, но есть 0!
На первое место в записи числа нельзя ставить 0! Поэтому чтобы поставить цифру на 1 место у нас выбор только из 4 цифр, когда одну возьмем, останется тоже 4, потому что теперь уже можно брать 0, возьмем цифру, поставим на 2 место, останется только 3 цифры, потом 2, потом 1. Потому что в этой задаче в условии сказано, что нельзя повторять цифры в записи числа = «в записи каждого числа содержатся все данные цифры»
5 – сделали четкий структурированный конспект, все поняли, самостоятельно верно решили 4-5 задач.
4 – сделали четкий структурированный конспект, все поняли, самостоятельно верно решили 2-3 задачи.
3 – сделали четкий структурированный конспект, все поняли только после знакомства с верными решениями.
2 – ничего не делали, ничего не поняли.
Физкультминутка:
Размещения и сочетания
Теоретическая часть
Размещение с повторениями из k элементов по m элементов — это кортеж длины m, составленный из m элементов k-элементного множества.
Вспомните, где вы встречали слово кортеж: свадебный кортеж, президентский кортеж – элементы следуют друг за другом в строгом порядке. Порядок важен!
Запишите примеры задач:
Сколько различных двузначных чисел можно записать с помощью цифр 3, 4, 5 и 6?
Эту задачу мы с вами уже решили по правилу произведения. Теперь решим по формуле. Порядок важен для нас, повторяться можно, поэтому это размещение с повторениями. Выбираем из 4 – внизу будет 4, выбираем 2 цифры – наверху будет 2.
Имеется лак двух цветов: красный и черный. Сколько существует вариантов распределения цветов на 10 ногтях?
Нам важно, ноготь, на каком пальце будет красный, а на каком - черный, поэтому порядок важен для нас. Мы можем все выкрасить в 1 цвет или один или 2 любых ногтя покрасить в красный, а остальные в чёрный или 3 или наоборот. Мы можем решить эту задачу по правилу произведения, выбирая для каждого из 10 ногтей из 2 цветов: 2•2•2•2•2•2•2•2•2•2=1024.
А можем выбрать формулу Внизу 2 – выбираем из 2, наверху – 10 – выбираем из 10:
Запишите определение, формулу и пример задачи:
Обратите внимание, что количество множителей m, поэтому можно не считать, сколько будет в 3 скобке, просто каждый следующий множитель на 1 меньше предыдущего, а их количество равно m. В задаче 3 множителя.
Запишите: Задача 2. Сколько всевозможных трехзначных чисел можно записать, используя цифры 7, 4 и 5, так, чтобы цифры в записи числа не повторялись?
Заметим, что в данном случае разные числа получаются в результате перестановки цифр. Поэтому размещения из k элементов по k элементов называют перестановками из k элементов без повторений.
Число перестановок без повторений из k элементов обозначают Pk и подсчитывают по формуле
Pk = k!, где k! = 1 ⋅ 2 ⋅ 3 ⋅ … ⋅ k
и k! читают «k факториал». Считают, что 1! = 1, 0! = 1. Например, 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120; 7! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 ⋅ 7 = 5040.
Запишите определение, формулу и пример задачи:
Сочетание без повторения из k элементов по m элементов — это m-элементное подмножество множества, содержащего k элементов.
Задача. На прямой взяли десять точек. Сколько всего получилось отрезков, концами которых являются эти точки?
В этой задаче порядок роли не играет (отрезок AВ и отрезок ВA — это один и тот же отрезок). Порядок не важен. Комбинации в этой задаче являются двухэлементными подмножествами, образованными из 10 данных элементов (точек). Такие подмножества в комбинаторике называются сочетаниями без повторений из 10 элементов по 2. Их число можно найти по формуле: .
Конечно, применение формул облегчает подсчет числа возможных вариантов решений той или иной комбинаторной задачи. Однако чтобы воспользоваться формулой, необходимо определить вид соединений (комбинаций), о которых идет речь в задаче, что бывает сделать не очень просто. Для этого воспользуемся алгоритмом (запишите алгоритм в тетрадь):
Порядок важен?
Да – это размещение. Нет – это сочетание.
Если это размещение. Второй вопрос: элементы могут повторяться? Да – размещение с повторениями. Нет – размещение без повторений.
Если элементы просто переставляются местами, то это перестановка.
Практическая часть
Решения задач записывайте на чистой странице тетради, четко, яркими чернилами для последующего фотографирования!
В следующих задачах рассматриваются размещения из k элементов по m; решите, используя формулы размещений и перестановки:
Из 20 учащихся класса надо выбрать старосту, его заместителя и редактора газеты. Сколькими способами это можно сделать?
В классе изучаются 7 предметов. В среду 4 урока, причем все разные. Сколькими способами можно составить расписание на среду?
В соревновании участвуют 10 человек. Сколькими способами могут распределиться между ними места?
Сколько всевозможных трехзначных чисел можно записать, используя цифры 3, 4, 5 и 6?
В следующих задачах рассматриваются сочетания из k элементов по m, решите, используя формулу для сочетаний:
Сколькими способами можно выбрать из 6 человек комиссию, состоящую из трех человек?
Сколькими способами можно выбрать 4 краски из 10 различных красок?
Решите следующие задачи, используя формулы. Выбирайте формулу по алгоритму:
Сколько словарей необходимо переводчику, чтобы он мог переводить текст с любого из четырех языков — русского, английского, немецкого и французского — на любой другой из этих языков?
Государственные флаги некоторых стран состоят из трех горизонтальных полос разного цвета. Сколько различных вариантов флагов с белой, синей и красной полосами можно составить?
Мальчик выбрал в библиотеке 5 книг. По правилам библиотеки одновременно можно взять только 2 книги. Сколько у мальчика вариантов выбора двух книг из пяти?
Аня, Боря, Вера и Гена — лучшие лыжники школы. На соревнования надо выбрать троих из них. Сколькими способами можно это сделать?
При изготовлении авторучки корпус и колпачок могут иметь одинаковый или разный цвет. На фабрике имеется пластмасса четырех цветов: белого, красного, синего и зеленого. Какие отличающиеся по цвету ручки можно изготовить?
На прямой взяли 4 точки. Сколько всего получилось отрезков, концами которых являются эти точки?
В соревнованиях участвуют 5 футбольных команд. Каждая команда играет один раз с каждой из остальных команд. Сколько матчей будет сыграно.
Самооценка по теме «правила суммы и произведения» - …
Сфотографируйте свои решения: условие-формула-вычисления (только решения задач); самооценку в 14 и загрузите этот файл под вашей фамилией в вашу папку 321 16.05 по ссылке:
Проверьте себя:
Читайте также: