Пракикум «Решение задач по комбинаторике»
Разделы: Математика
Комбинаторика – это раздел математики, посвящённый решению задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами. Комбинаторика изучает комбинации и перестановки предметов, расположение элементов, обладающее заданными свойствами. Обычный вопрос в комбинаторных задачах: сколькими способами….
К комбинаторным задачам относятся также задачи построения магических квадратов, задачи расшифровки и кодирования.
Рождение комбинаторики как раздела математики связано с трудами великих французских математиков 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 способа
Источник статьи: http://urok.1sept.ru/articles/616160
Сколькими способами можно разделить 6 разных игрушек и 5 разных книжек между тремя детьми?
Есть 4 задачи на комбинаторику, помогите решить, пожалуйста:
1.Сколькими способами можно разделить 6 разных игрушек и 5 разных книжек между тремя детьми?
2.Сколькими способами можно поделить 9 одинаковых яблок и 6 одинаковых груш между тремя мужиками?
3.Пять учеников решили написать все 15 билетов на экзамен. При этом количество написанных билетов разделили так: первый — 4, второй — 3, третий — 2, четвёртый — 1, пятый — 5. Сколькими способами можно разделить все билеты меж ними?
4.Сколько четырёхзначных чисел делится хотя бы на одно из чисел 12,8?
Сколькими способами можно разделить 5 подарков между 14 детьми
1.Сколькими способами можно разделить 5 разных подарков между 14 детьми, если ребенку может.
Сколькими способами можно разделить 27 одинаковых шаров между семью детьми
Сколькими способами можно разделить 27 одинаковых шаров между семью детьми? Та же задача, но если.
Сколькими способами можно купить 8 разных листовок?
В почтовом отделении связи продаются листовки 10 видов. Сколькими способами можно купить 8 разных.
1. Если нет требования, чтобы каждый ребенок получил игрушку и книгу, то рассуждаем так. Первая игрушка отдается одному из трех детей. Независимо от этого вторая игрушки отдается одному из трех детей, и т.д. Результат есть число размещений с повторениями из 3 по 6, которое иногда обозначается . Количество способов для игрушек и книг комбинируется с помощью правила произведения.
2. Количество способов разделить k одинаковых предметов между n людьми есть число сочетаний с повторениями из n по k, которое иногда обозначается . По определению равно количеству неупорядоченных выборок (мультимножеств) размера k, где элементы берутся из <1, . n>. Действительно, k раз делается выбор, кому из n людей отдается очередной предмет. Известно, что . Яблоки и груши интегрируются по правилу произведения.
3. Количество способов разделить n предметов на k подмножеств по n1, . nk элементов, где n = n1 + . + nk, есть .
4. Воспользуйтесь принципом включений-исключений. Рассмотрите множество делителей 12 и множество делителей 8.
Источник статьи: http://www.cyberforum.ru/combinatorics/thread1972244.html
Урок — математический турнир по теме: «Решение комбинаторных задач»
Урок — математический турнир по теме:
« Решение комбинаторных задач»
· Отработка практических умений и навыков решения комбинаторных задач.
· Развитие внимания, логического мышления.
· Формирование активной жизненной позиции учащихся и умения работать в группе.
1. Объединение учащихся в 4 группы.
2. Подготовка раздаточного материала:
· Схемы выбора формул и выбора правил для решения комбинаторных задач,
· набор цветных карточек,
· Таблица с игровым полем.
· Таблица значений n.
· Таблица с формулами соединений.
I. Актуализация знаний учащихся по теме « Комбинаторика»
· Какие задачи называются комбинаторными? ( задачи выбора и размещения элементов конечного множества).
· Что изучает комбинаторика? ( это раздел математики, который изучает методы решения комбинаторных задач).
· Что такое соединения? (это конечные множества, в которых существенным является либо порядок элементов, либо их состав, либо то и другое одновременно).
· Какие виды соединений мы изучаем? ( Перестановки, размещения, сочетания).
· Определение перестановок. ( любое упорядоченное множество, состоящее из n элементов, называется перестановкой из n элементов Р
= n !).
Определение размещения.( Упорядоченное подмножество из m элементов данного множества, содержащего n элементов (m 
n) называется размещением из n элементов и обозначается A = n*( n – 1 ) …( n – m + 1 )
· Определение сочетания. ( Любое подмножество из m элементов данного множества, содержащего n элементов, называется сочетанием из n по m
C
=
C
=
· Чем отличаются размещение и сочетание?
B A
— важен порядок элементов
B С
— порядок выбора элементов не имеет значения.
II. Сообщение темы занятия и условий проведения турнира.
Ребята, вы объединены в 4 группы. Сегодня между группами состоится математический турнир.
Задача группы – заполнить карточками своего цвета как можно больше секций игрового поля. Карточку имеет право прикрепить та группа, которая первой решит задание. О выполнении задания группа сообщает поднятием сигнального флажка.
На каждом столе есть задание и схема выбора правил и формул. Это ваши подсказки. Представитель группы, которая первой подняла сигнальный флажок, должен выйти к доске, записать и объяснить решение задач. При правильном решении карточка команды прикрепляется на игровое поле.
Все решения должны быть записаны в тетради каждого ученика. Объяснять решение должны выходить по очереди все члены группы.
III. Ход математического турнира
Задания турнира с решениями и ответами:
1. В спортивной команде 25 человек. Сколькими способами можно выбрать олимпийскую команду в составе трех человек?
C 
=
= 2300
2. Сколькими способами можно рассадить четырех учеников на 25 местах?
A
= 25 · 24 · 23 · 22= 303600
3. Сколько разных пятизначных чисел можно составить из цифр 0, 1, 2, 3, 4, если в каждом числе ни одна из цифр не повторяется?
4. Сколькими способами можно выбрать 2 карандаша и 3 ручки из 6 разных карандашей и 8 разных ручек?
C · C = 
·
= 840
5. Сколькими способами можно составить трехцветный полосатый флаг, если есть ткань из пяти разных цветов?
А 
= 5 · 4 ·3 = 60
6. Сколькими способами можно выбрать двух дежурных в классе, в котором28 человек?
7. Сколько 6-значных чисел, кратных 5, можно составить из цифр 1, 2, 3, 4, 5, 6, при условии, что цифры в числе не повторяются?
Число должно оканчиваться 5, значит, осталось 5 цифр:
8. Сколько существует двухзначных чисел, в которых цифра десятков и цифра единиц разные и нечетные?
Нечетные цифры: 1, 3, 5, 7, 9 ( всего 5)
A 
=5 · 4 = 20
9. Ученику нужно сдать 4 экзамена за 8 дней. Сколькими способами это можно сделать, если последний экзамен – в восьмой день?
A 
·4 = 7 · 6 ·5·4 = 840
10. Сколькими способами можно распределить 6 разных предметов между тремя людьми так, чтобы каждый получил по 2 предмета?
C 
· C 
· C
= · 
· 1=90
11. Сколько существует шестизначных телефонных номеров, в каждом из которых ни одна цифра не повторяется?
A
= 151200
12. Сколькими способами из 9 учебных предметов можно составить расписание учебного дня из 6 различных предметов?
A
= 9 ·8 ·7 ·6 ·5 ·4 = 60480
13. Во взводе 5 сержантов и 30 солдат. Сколькими способами можно составить наряд из одного сержанта и трех солдат?
C 
· C 
= 5· 
= 20300
14. Сколькими способами можно группу из 15 человек разделить на 2 группы так, чтобы в одной группе было 4 человека, а в другой — одиннадцать?
C 
= C 
= 
= 1365
15. Из 20 человек на собрании выбирают председателя, секретаря и 2-х членов комиссии. Сколькими способами это можно сделать?
A — председателя и секретаря
A
· C = 
= 58140
16. 45 человек обмениваются рукопожатиями. Сколько рукопожатий было сделано?
C = 
= 990
17. На школьном вечере в танцевальном конкурсе участвуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них 4 танцевальные пары?
C
· A = C
· A = 16216200
18. Из 10 разных цветов нужно составить букет так, чтобы в нем было не меньше двух цветков. Сколькими способами можно составить такой букет?
2
– C — C 
= 1024 – 1 – 10 = 1013
IV. Подведение Итогов.
19. В спортивной команде 25 человек. Сколькими способами можно выбрать олимпийскую команду в составе трех человек?
20. Сколькими способами можно рассадить четырех учеников на 25 местах?
21. Сколько разных пятизначных чисел можно составить из цифр 0, 1, 2, 3, 4, если в каждом числе ни одна из цифр не повторяется?
22. Сколькими способами можно выбрать 2 карандаша и 3 ручки из 6 разных карандашей и 8 разных ручек?
23. Сколькими способами можно составить трехцветный полосатый флаг, если есть ткань из пяти разных цветов?
24. Сколькими способами можно выбрать двух дежурных в классе, в котором28 человек?
25. Сколько 6-значных чисел, кратных 5, можно составить из цифр 1, 2, 3, 4, 5, 6, при условии, что цифры в числе не повторяются?
26. Сколько существует двухзначных чисел, в которых цифра десятков и цифра единиц разные и нечетные?
27. Ученику нужно сдать 4 экзамена за 8 дней. Сколькими способами это можно сделать, если последний экзамен – в восьмой день?
28. Сколькими способами можно распределить 6 разных предметов между тремя людьми так, чтобы каждый получил по 2 предмета?
29. Сколько существует шестизначных телефонных номеров, в каждом из которых ни одна цифра не повторяется?
30. Сколькими способами из 9 учебных предметов можно составить расписание учебного дня из 6 различных предметов?
31. Во взводе 5 сержантов и 30 солдат. Сколькими способами можно составить наряд из одного сержанта и трех солдат?
32. Сколькими способами можно группу из 15 человек разделить на 2 группы так, чтобы в одной группе было 4 человека, а в другой — одиннадцать?
33. Из 20 человек на собрании выбирают председателя, секретаря и 2-х членов комиссии. Сколькими способами это можно сделать?
34. 45 человек обмениваются рукопожатиями. Сколько рукопожатий было сделано?
35. На школьном вечере в танцевальном конкурсе участвуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них 4 танцевальные пары?
36. Из 10 разных цветов нужно составить букет так, чтобы в нем было не меньше двух цветков. Сколькими способами можно составить такой букет?
Схема выбора формул
 |
Все ли элементы входят в соединение?
C
=
C
= 
P
= n!
A
=
A= n
(n-1)…(n-m+1)
Схема выбора правил для решения комбинаторных задач.
Источник статьи: http://pandia.ru/text/80/273/32964.php