Курс по комбинаторике


Чтобы посмотреть презентацию с оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов:

1. Предмет комбинаторика. Исторические сведения 2. Основные правила комбинаторики 3. Элементы комбинаторики. Перестановки 4. Элементы комбинаторики. Размещения 5. Элементы комбинаторики. Сочетания 6. Сходства и различия в сочетаниях и размещениях 7. Способы вычисления количества заданных комбинаций 8. Практика решения комбинаторных задач 9. Калькулятор для вычисления Рn, Anm, Cnm 10. Самоконтроль 11. Тренинг с оцениванием правильности решения КОМБИНАТОРИКА – область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Комбинаторика происходит от происходит от латинского слова «combina», что в переводе на русский означает – «сочетать», «соединять». Комбинаторика как наука стала развиваться в XIII в. параллельно с возникновением теории вероятностей. Первые научные исследования по этой теме принадлежат итальянским ученым Дж. Кардано, Н. Чарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б.Пискамо (1623-1662) и П. Ферма. Ученые- исследователи комбинаторики Джероламо Кардано(1501–1576) Никокко Тарталья (1499-1557) Ученые- исследователи комбинаторики Галилео Галилей (1564-1642) Безу Паскаль(1623-1662) Пьер Ферма (1601-1665) Ученые- исследователи комбинаторики Л. Эйлер Я. Бернулли Комбинаторику, как самостоятельный раздел математики, первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666г. Он также впервые ввел термин «Комбинаторика». Очень часто встречаются задачи в которых необходим подсчет количества комбинаций, которые можно составить из заданных объектов конечного множества, безразлично какой природы, которые подчинены каким то условиям. Для успешных решений этих задач необходимо знать основные правила и формулы комбинаторики. Пусть задано множество, содержащее конечное число элементов. (Студенты в группе, яблоки в корзине, набор костей домино и т.д.). Пусть а1, а2, …,аn – элементы некоего конечного множества. Сформулируем два важных правила, которые применяются в комбинаторике: Если элемент а1 может быть выбран n1 способом, элемент а2 может быть выбран другими n2 способами, элемент а3 может быть выбран отличными от первых двух n3 способами и т.д., элемент аk – nk способами, отличными от первых (k-1) способа, то выбор одного из элементов: или а1, или а2,…, или ак может быть осуществлен n1+ n2 +…+ nk способами. (Объединение множеств n1 – nk) Знак U (сложение) 1. В ящике 300 деталей. Известно, что 180 из них – 1-го сорта, 100 – 2 –го сорта, а остальные – 3-го сорта. Сколько существует способов извлечения из ящика детали 1-го или 2-го сорта? Примеры. Решение. Деталь первого сорта может быть извлечена n1=180 способами, 2-го сорта – n2=100 способами. По правилу суммы существует n1+n2=280 способов извлечения из ящика детали 1-го или 2-го сорта. 2. В корзине 12 роз, 13 пионов и 23 гвоздики. Сколькими способами можно выбрать один любой цветок из корзины? Решение. Роза может быть извлечена n1=12 способами, пион – n2=13 способами, а гвоздика – n3=23 способами. По правилу суммы существует n1+n2+ n3=48 способов, которыми можно выбрать один цветок из корзины. Если элемент а1 может быть выбран n1 способом, после каждого такого выбора элемент а2 может быть выбран n2 способами, и т.д., элемент аk – nk способами, то выбор элементов а1 и а2,…,и ак может быть осуществлен n1 · n2…· nk способами. (Пересечение множеств n1 – nk) Знак ∩ (произведение) а) при подбрасывании трёх монет возможно 2 · 2 · 2=8 различных результата Орел - решка б) бросая дважды игральную кость, получим 6 · 6=36 различных результатов в) трёхзначных чисел бывает 9 · 10 · 10 = 900; Подразумеваются количество результатов при первом и втором бросках 1,2,3,4,5,6,7,8,9 0,1,2,3,4,5,6,7,8,9 0,1,2,3,4,5,6,7,8,9 г) трёхзначных чисел, все цифры которых различны, существует 9 · 9 · 8 = 648; 1,2,3,4,5,6,7,8,9 10 - 1 10 - 2 д) чётных трёхзначных чисел возможно 9 · 10 · 5 = 450; 1,2,3,4,5,6,7,8,9 0,1,2,3,4,5,6,7,8,9 2,4,6,8,0 Если выбор происходит либо из одного, либо из других, подразумевается ИЛИ. Надо складывать. Если выбор происходит из одного и из других, подразумевается И. Надо умножать. Комбинации из n-элементов, отличающихся друг от друга только порядком расположения в них элементов, называются перестановками из n элементов. Рn Исследуем количество перестановок из разноцветных квадратиков: Из двух цветов 2 варианта 3 цвета 1 3 4 5 6 2 Всего получили 6 возможных вариантов И так имеем 1, 2, 3 цвета Расставьте между числами знаки действия, чтобы получить 6 1 2 3 = 6 Проверим правильность действий: Каждый цвет на первом месте встречается два раза, таких цветов 3, следовательно, всего опытов 2 · 3 = 6 Правильный знак – умножение 4 цвета С К Ж З К С З Ж С Ж К З С К Ж З З С К Ж К Ж С З К С Ж З С К З Ж К Ж С З К С Ж З З К С Ж С Ж К З Ж С К З С Ж З К Ж К С З Ж С К З З Ж С К С К Ж З З К Ж З З Ж К С З К Ж С К З С Ж С З К Ж К Ж З С Попробуем вычислить количество вариантов (опытов): Каждый цвет на первом месте встречается 6 раз Всего цветов 4, следовательно, количество вариантов 6 · 4 =24 Заметим, что 6 = 1 · 2 · 3 Можем записать 1 · 2 · 3 · 4 = 24 Подсчитаем количество вариантов из 5 цветов. (синий, красный, желтый, зеленый, оранжевый Каждый цвет на первом месте встретится 24 раза С Ж С Ж С Ж С Ж Ж С С Ж С К Ж З С Ж К О К С О З Ж О С К О З Ж З С Ж К З О О С З К Ж С З С З С З С З З С С З С О С О С О С О О С С О Каждое сочетание С-К, С-Ж, С-З, С-О создает по 6 вариантов. 6 · 4 = 24 Всего цветов 5. Количество возможных опытов 24 · 5 = 120 Количество перестановок из: 2 цветов 3 цветов 4 цветов 5 цветов n цветов 1 · 2 · 3 · 5…(n – 1)n = Такое последовательное умножение называется n факториал и записывается Вывод Получили последовательное произведение натуральных чисел от 1 до n. Читается: n факториал. n! n-факториал-это произведение всех натуральных чисел от единицы до n, обозначают символом ! Используя знак факториала, можно, например, записать:1! = 1,2! = 2*1=2,3! = 3*2*1=6,4! = 4*3*2*1=24,5! = 5*4*3*2*1 = 120.Необходимо знать, что 0! = 1 Комбинации из n-элементов, отличающихся друг от друга только порядком расположения в них элементов, называются перестановками из n элементов. Перестановки из n элементов обозначают Pn и вычисляют по формуле: Pn=n!n!=1*2*3*4*…*n (n факториал) Свойство: 0!=1 Задача: Сколькими способами могут разместиться 5 пассажиров в пятиместной каюте?Решение: P5=5!=1*2*3*4*5=120 Задача. КвартетПроказница Мартышка Осёл, Козёл,Да косолапый МишкаЗатеяли играть квартет …Стой, братцы стой! – Кричит Мартышка, - погодите!Как музыке идти?Ведь вы не так сидите…И так, и этак пересаживались – опять музыка на лад не идет.Вот пуще прежнего пошли у них разборы И споры,Кому и как сидеть…Сколькими способами можно рассадить четырех музыкантов? Всего с мартышкой на первом месте – 6 вариантов Для 4 животных:6 · 4 = 24 Нам необходимо найти все варианты посадки - это перестановки из 4-х элементов Р = 4! =1 · 2 · 3 · 4 =24 Если в перестановках есть повторяющиеся элементы, то такие перестановки будем называть перестановками с повторением. Определение: Если в перестановке из общего числа элементов n есть k различных элементов, при этом 1-й элемент повторяется n1 раз, 2-й элемент повторяется n2 раз, k-й элемент - nk раз, причем n1+n2+…+nk=n, то такие перестановки называются перестановками с повторениями из n элементов. Число перестановок с повторениями из n элементов равно 2.Сколько существует пятизначных чисел, состоящих из цифр 7,8,9, в которых цифры 8 и 7 повторяются по 2 раза, а 9 по одному разу. Решение. Каждое пятизначное число можно составить 5! = 120 способов 8 можно переставить 2! способами, 7 тоже . Так как 8 и 7, то умножим. Получим: 120:4 = 30 Можно записать так: 1.Сколько существует пятизначных чисел, состоящих из цифр 7,8,9, в которых цифра 8 повторяется 3 раза, а цифры 7 и 9 по одному разу. Решение. Каждое пятизначное число можно составить 5! = 120 способов Расставить три 8 по местам можно 6 способами: 3! = 6 Следовательно, число способов равно 120 : 6 = 20 1. 2. 3. 8 8 8 1. 2. 3. 8 8 8 1. 2. 3. 8 8 8 1. 2. 3. 8 8 8 1. 2. 3. 8 8 8 1. 2. 3. 8 8 8 2. На карточках написаны буквы М,А,Т,Е,М,А,Т,И,К,А. Сколько различных 10-ти буквенных «слов» можно составить из этих карточек? (здесь и далее словом считается любая последовательность букв русского алфавита) А встречается 3 раза, Т – 2 раза, М – 2 раза. Остальные по разу Всего перестановок: Р10 = 10! Перестановок для А Р3 = 3!, для Т - Р2 = 2!, для М Р2 = 2! Определение: перестановки из общего числа элементов n , которые расположены по кругу называются перестановками по кругу из n элементов. А В С Заметим, что число перестановок из 3 в ряд Р3 = 3! = 6 Сделаем перестановки по кругу. А С В А,В,С 2. А,С,В В С А В А С 4. В,А,С 3. В,С,А С А В 1. А,В,С А,С,В В,А,С В,С,А С,В,А С,А,В С В А 5. С,А,В 6. С,В,А Но перестановки 3,4 и 5,6 – тождественны Получаем только 2 возможности Р = 2! Следовательно перестановок из n элементов по кругу равно (n – 1)! Рпо кругу = (n – 1)! Задача. 1. К одному человеку в гости пришли 6 его друзей. Все они ужинали за круглым столом. Время ужина пролетело незаметно, и хозяин сказал гостям, что он будет рад видеть их у себя за ужином столько раз, сколько различных перестановок за этим столом они смогут образовать. Друзья, конечно, согласились. Сколько раз придется кормить своих друзей ужином радушному хозяину, не знающему математику? Решение. Так как за круглым столом 7 человек, то Р по кругу = (7 – 1)! = 6! = 720 Задача 2. Подсчитав число ужинов, хозяин поставил условие, что он всегда сидит только на определенном месте. Решение. Пересаживаться могут только 6 гостей. Это перестановки в ряд: Р6 = 6! = 720 Задача 3. Двое гостей категорически не соглашаются сидеть вместе. Всего возможных рассадок Р по кругу = 6! = 720 Так кок двое не хотят сидеть вместе, примем их за одного, тогда Р по кругу = 5! = 120. Но двое могут пересаживаться двумя способами, т.е. 120 · 2 = 240. Всего способов будет 720 – 240 = 480 Размещением называется расположение «предметов» на некоторых «местах» при условии, что каждое место занято в точности одним предметом и все предметы различны. Более формально, размещением (из n по k) называется упорядоченный набор из k различных элементов некоторого m -элементного множества. k < n Если k = n , то = Рn k n A Число размещений из n элементов по k элементов обозначается (читается "А из n по k"). m n A Примеры задач, приводящих к необходимости подсчета размещенийСколькими способами можно выбрать из 15 человек 5 кандидатов и назначить их на 5 различных должностей?2) Сколькими способами можно из 15 книг отобрать 4 и расставить их в ряд на полке? Пример. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал четырех цветов? К С Ж З С красной верхней полосой можно составить 6 вариантов. Всего 4 цвета, следовательно, всего 6 · 4 = 24 варианта. Это размещения из 4 по3 Проверим! Размещения - это соединения, содержащие по m предметов из числа n данных, различающихся либо порядком предметов, либо самими предметами; 1) Сколькими способами можно выбрать из 15 человек 5 кандидатов и назначить их на 5 различных должностей? Это размещения из 15 по 5 2) Сколькими способами можно из 15 книг отобрать 4 и расставить их в ряд на полке? Это размещения из 15 по 4 3) Учащиеся 9 класса изучают 10 различных дисциплин. Определить – сколькими способами можно составить расписание на понедельник, если в понедельник планируется поставить 5 пар? Решение: Каждый вариант расписания представляет собой выборку 5 элементов из 10, причем эти варианты отличаются друг от друга не только выбором этих дисциплин, но и порядком их следования, т.е. является размещением из 10 элементов по 5. . 4) Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны? Решение: Каждый вариант выбора представляет собой выборку 4 элементов из 9, причем эти варианты отличаются друг от друга не только выбором этих кандидатур, но и порядком их следования, т.е. является размещением из 9 элементов по 4. . Определение: Пусть даны n различных видов предметов, которые можно разместить по k различным местам, причем выбирать предметы можно с повторениями (т.е. можно выбрать несколько предметов одного вида). Такие выборки называются размещениями с повторениями, а их количество вычисляется по формуле: 1. Среди 15 учащихся проводился конкурс на «Самого умного», «Самого доброго», «Самого смелого» и «Самого умелого». Сколько существует вариантов распределения призов, если по каждой номинации установлены различные призы? Решение: Каждый из вариантов распределения призов представляет собой комбинацию 4 участников из 15, отличающуюся от других комбинаций как составом номинантов, так и их порядком, причем один и тот же участник может быть номинантом несколько раз. Т.е. мы имеем дело с размещением с повторениями из 15 элементов по 4. . Способ 2. Первый приз могут получить любой из 15 участников. Второй тоже один из 15 участников. Также с третьем и четвертым призами. Так как призы должны быть и первый и второй и третий и четвертый, то для вычисления применим правило умножения: 2. Сколько всевозможных двузначных чисел можно записать, используя цифры 7, 4 и 5? Было бы ошибкой использовать формулу , так как она не учитывает возможных повторений. В самом деле: Это числа: 74, 75, 47, 45, 57, 54 Если учесть повторение цифр, то надо прибавить еще три: 77, 44, 55 Всего получим 9 Так как необходимо составить всевозможные числа, то лучше воспользоваться формулой 4. Сколько всевозможных трехзначных чисел можно записать, используя цифры 7, 4 и 5? Решение: пользуясь формулой = km, легко подсчитать, сколько двузначных чисел можно записать, используя цифры 7, 4 и 5. так как речь идет о размещениях с повторениями их трех элементов по два, то =33=27. 754 745 755 744 775 774 757 747 777 Составим таблицу возможных чисел на 7 с повторениями Таких чисел 9. Так как используем три числа, получим 9 · 3 = 27 Решим задачу другим способом Вывод Решать задачи с помощью формул значительно проще. Нужно только установить, какую формулу использовать в соответствие с условием. В размещениях учитывается порядок следования предметов. Так, например, наборы (2,1,3) и (3,2,1) являются различными. Формула сочетаний может быть получена следующим образом. Выберем по очереди m предметов из n. Мы это можем сделать способами. Однако нас не интересует в данном случае порядок выбранных предметов. От перестановки этих предметов наш выбор не меняется. Поэтому полученное выражение нужно разделить на m! Определение: Сочетаниями из n элементов по m элементов будем называть любое подмножество, состоящие из m элементов, множества , состоящего из n элементов. Число сочетаний из n элементов по т элементов обозначается (читается «эс из эн по эм"). 1. Из группы 35человек нужно выбрать троих для работы в колхозе. Сколькими способами это можно сделать? Решение. Для нас порядок выбора не имеет значения. Это сочетания из 35 по 3. 2. Хоккейная команда состоит из 2 вратарей, 7 защитников и 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря, двух защитников и трех нападающих? Выбор вратаря, защитников и нападающих – это сочетания, так как порядок не имеет значения. Вратаря можно выбрать Защитников можно выбрать способами способами Нападающих можно выбрать способами Всего, по правилу произведения, существует 2 · 21 · 120 = 5040 способов выбора стартовой шестерки. Сходства и различия в сочетаниях и размещениях. Сходства. Сочетания и размещения – это подмножества, состоящие из m элементов n-элементного множества. Различия. В размещении важен порядок расположения элементов, а в сочетаниях порядок не важен. СОЧЕТАНИЯ РАЗМЕЩЕНИЯ 1. Сколько рукопожатий получится, если здороваются 6 человек? {Дима, Антон} = {Антон, Дима} – одно и тоже. Значит, порядок неважен, значит это сочетание из шести по два 1. Сколькими способами шесть человек могут обменяться фотографиями?{ Дима, Антон }  { Антон, Дима } – разные обмены Значит, порядок важен, значит это последовательность по два элемента из 6, значит это размещение из шести по два СОЧЕТАНИЯ РАЗМЕЩЕНИЯ 2. Сколько аккордов можно сыграть с помощью трех клавиш из семи? {до, ми, соль} = { до, соль, ми } – одно и тожеЗначит, порядок неважен, значит это сочетание из семи по три 2. Сколько мелодий (трезвучий, проигрышей) можно сыграть с помощью трех клавиш из семи? {до, ми, соль}  { до, соль, ми } – разные мелодииЗначит, порядок важен, значит это размещение из семи по три Сколькими способами можно расставить 4-х игроков в две шеренги? Сколькими способами можно выбрать двух игроков их 4-х заявленных? Обозначим игроков A, B, C, D Это Это Сравним два вида задач: размещение сочетание Сколькими способами можно расставить 4-х игроков в две шеренги? Сколькими способами можно выбрать двух игроков их 4-х заявленных? Обозначим игроков A, B, C, D Это Это AB AC AD BA BC BD CA CB CD DA DB DC AB AC AD BA BC BD CA CB CD DA DB DC АВ и ВА учитываются как два варианта АВ и ВА - одна и та же пара Сравним два вида задач: 1 Вариант 2 Вариант размещение сочетание Способы вычисления количества заданных комбинаций Таблица для подсчета вариантов Дерево вариантов Правило умножения Правило сложения Формулы подсчета вариантов (Р, Аmn, Cnm) Аналитический способ Сколько команд приняло участие в чемпионате по футболу, если способов занять 1-ое, 2-ое и 3-е места равно 990? Всего команд 11. Алгебраическое решение: Пусть х – количество команд. Тогда 1место – х способов. 2-ое место – х – 1 способов.3- е место - х – 2. По правилу умножения получим: х(х – 1)(х – 2) = 990 Так как получили произведение трех последовательных натуральных чисел, то 990 = 11·10·9 Заметим, что в левой части уравнения стоит произведение трех последовательных натуральных чисел х = 11 Аналитический способ Ответ:15 чисел. 1 2 4 5 9 0 2 4 10 14 12 20 22 24 40 42 44 50 52 54 90 92 94 Таблица для подсчета вариантов Сколько четных двузначных чисел можно составить из цифр 0, 1, 2, 4, 5, 9? 1-1 1-2 1-3 1-4 1-5 1- 6 2-1 2-2 2-3 2-4 2-5 2- 6 3-1 3-2 3-3 3-4 3-5 3- 6 4-1 4-2 4-3 4-4 4-5 4- 6 5-1 5-2 5-3 5-4 5-5 5- 6 6-1 6-2 6-3 6-4 6-5 6- 6 Сколько случаев может быть при бросании двух костей, чтобы сумма выпавших очков была больше 7? Ответ:15. Из чисел 1, 5, 9 составить трёхзначное число без повторяющихся цифр. 1 159 195 5 9 519 591 915 951 2 комбинации 2 комбинации 2 комбинации Всего 2•3=6 комбинаций. Дерево вариантов Решение Ученик выполняет практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему? Наряд ученицы состоит из блузки, юбки и туфель. Она имеет в своем гардеробе четыре блузки, пять юбок и трое пар туфель. Сколько нарядов может иметь студентка? Задача  №1. а) б) 1. Анализ условия 2. Выбор метода подсчета Ученик может выбрать одну из тем алгебры или геометрии Ученица может выбрать одну из 4-х блузок и одну из 5-и юбок, и одну пару туфель из 3-х Правило сложения, правило умножения Ученик выполняет практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему? Наряд ученицы состоит из блузки, юбки и туфель. Она имеет в своем гардеробе четыре блузки, пять юбок и трое пар туфель. Сколько нарядов может иметь студентка? Задача  №1. а) б) 1. Анализ условия 2. Выбор метода подсчета Ученик может выбрать одну из тем алгебры или геометрии Ученица может выбрать одну из 4-х блузок и одну из 5-и юбок, и одну пару туфель из 3-х Использовать правило сложения Использовать правило умножения По алгебре ученик может выбрать тему 17 способами, по геометрии – 13. Всего: 17 + 13 = 30 способов. Ученица может выбрать блузку 4-мя способами, юбку – 5, туфли – 3. Всего: 4 · 5 · 3 = 60 способов. Правило сложения, правило умножения Сколько существует способов выбрать кратное двум или трем число из множества чисел : 2,3,4,15,16,20,21, 75,28 ? Задача  №2 а) б) 1. Анализ условия 2. Выбор метода подсчета Событие А – число кратное 2 Событие Б – число кратное 3 По условию необходимо или А U Б Правило сложения, правило умножения Событие А 1место – 10 способов Событие Б 2место – 9 способов Событие В 3 место – 8 способов По условию необходимо и А ∩ Б ∩ В Правило сложения Правило умножения Сколько существует способов занять 1-ое, 2-ое и 3-е места на чемпионате по футболу, в котором участвуют 10 команд Решение Сколько существует способов выбрать кратное двум или трем число из множества чисел : 2,3,4,15,16,20,21, 75,28 ? Задача  №2 а) б) 1. Анализ условия 2. Выбор метода подсчета Событие А – число кратное 2 Событие Б – число кратное 3 По условию необходимо или А U Б Правило сложения, правило умножения Событие А 1место – 10 способов Событие Б 2место – 9 способов Событие В 3 место – 8 способов По условию необходимо и А ∩ Б ∩ В Правило сложения Правило умножения Четных чисел 5. Их можно выбрать пятью способами Кратных 3 чисел 4. Их можно выбрать четырьмя способами Всего: 5 + 4 = 9 Всего: 8 ·9 · 10 = 720 Сколько существует способов занять 1-ое, 2-ое и 3-е места на чемпионате по футболу, в котором участвуют 10 команд При событии, состоящего из события А или В применять правило сложения. Объединение событий А U B В задачах предусматривается или При событии, состоящего из события А и В применять правило умножения. Пересечение событий А ∩ B В задачах предусматривается и Задание 1 1. Несколько стран в качестве символа своего государства решили использовать флаг в виде четырех горизонтальных полос, одинаковых по ширине, но разных по цвету: белый, синий, красный, зеленый. У каждой страны свой, отличный от других, флаг. а) Сколько всего стран могут использовать такую символику? б) Сколько стран могут использовать такую символику с верхней белой полосой? в) Сколько всего стран могут использовать такую символику с нижней белой полосой? Справка Подсказка г) Сколько стран могут использовать такую символику с синей и красной полосами, расположенными рядом? Задание 1 1. Несколько стран в качестве символа своего государства решили использовать флаг в виде четырех горизонтальных полос, одинаковых по ширине, но разных по цвету: белый, синий, красный, зеленый. У каждой страны свой, отличный от других, флаг. а) Сколько всего стран могут использовать такую символику? б) Сколько стран могут использовать такую символику с верхней белой полосой? в) Сколько всего стран могут использовать такую символику с нижней белой полосой? Справка г) Сколько стран могут использовать такую символику с синей и красной полосами, расположенными рядом? Это перестановки Р4. Ответ: 24 Это перестановки Р3 Ответ: 6 Это перестановки Р3 Ответ: 6 Две полосы, расположенные рядом, можно рассматривать как одну полосу, тогда полос останется 3. Но синяя и красная полосы, могут быть красной и синей. (2 способа) Поэтому общее количество вариантов по правилу суммы равно Р3 + Р3 Ответ: 12 Задание 2 2. Сколькими способами можно рассадить шестерых школьников: а) на скамейку? б) за круглый стол? в) на скамейку так, чтобы Коля и Оля сидели вместе? Справка Подсказка 3. Из цифр 1,2,3,5 составили все возможные четырехзначные числа (без повторения цифр). Сколько среди них таких чисел, которые больше 2000, но меньше 5000? Задание 2 2. Сколькими способами можно рассадить шестерых школьников: а) на скамейку? б) за круглый стол? в) на скамейку так, чтобы Коля и Оля сидели вместе? Справка 3. Из цифр 1,2,3,5 составили все возможные четырехзначные числа (без повторения цифр). Сколько среди них таких чисел, которые больше 2000, но меньше 5000? Это перестановки Р6 Ответ: 720 Это перестановки Рпо кругу = Р5 Ответ: 120 Колю и Олю будем считать как одно целое. Р5. Но перестановок между Колей и Олей 2. Всего будет 2Р5 Ответ: 240 Чисел будет: с двойкой 2135, 2153, 2315, 2351, 2513, 2531 – 6. Тоже с первой тройкой и четверкой. Ответ: 18 Задание 3 3. На входной двери дома установлен домофон, на котором нанесены цифры 0,1,2,…9.Каждая квартира получает кодовый замок из двух цифр типа 0-2, 3-7 и т.п. Хватит ли кодовых замков для всех квартир, если в доме а) 90, б)104 квартиры? (код 0-0 не существует): а) 99 квартир б) 104 квартиры 4. Три вершины правильного 10-угольника покрасили в рыжий цвет, а остальные – в черный. Сколько можно провести отрезков с разноцветными концами? Справка Подсказка Задание 3 3. На входной двери дома установлен домофон, на котором нанесены цифры 0,1,2,…9.Каждая квартира получает кодовый замок из двух цифр типа 0-2, 3-7 и т.п. Хватит ли кодовых замков для всех квартир, если в доме а) 90, б)104 квартиры? (код 0-0 не существует): а) 99 квартир б) 104 квартиры 4. Три вершины правильного 10-угольника покрасили в рыжий цвет, а остальные – в черный. Сколько можно провести отрезков с разноцветными концами? Справка Первую цифру можно выбрать 10 способами; вторую – 10 способами. Всего способов находим умножением, но один 0-0 не существует Ответ: хватит Ответ: не хватит Первая желтая вершина соединяется с черными 7 отрезками. Желтых вершин 3 всего отрезков 7·3 = 21. Каждая желтая вершина может занимать одну из 10 вершин. Всего отрезков 21 · 10 = 210. 2-ой способ. А73. Ответ: 210 Задание 3 5. Задача: Четыре города M,N,P,K соединены дорогами так, что из M в N ведут 5дорог, из N в K – 6 дорог, из M в P ведут 4 дороги, из P в К – 3 дороги. а) Сколькими способами можно проехать из М в К? б) Найдите вариант с наименьшим количеством дорог, чтобы попасть из М в К? Справка Подсказка Задание 3 5. Задача: Четыре города M,N,P,K соединены дорогами так, что из M в N ведут 5дорог, из N в K – 6 дорог, из M в P ведут 4 дороги, из P в К – 3 дороги. а) Сколькими способами можно проехать из М в К? б) Найдите вариант с наименьшим количеством дорог, чтобы попасть из М в К? Справка M P K N Путь MNK: правило умножения. Всего 30 способов. Путь MРK: правило умножения. Всего 12 способов. Всего путь MNK или MPK Ответ 42 12 < 30, следовательно, MPK Задание 4 7. Секретный замок состоит из 4 барабанов, на каждом из которых можно выбрать цифры от 0 до 9. Сколько различных вариантов выбора шифра существует? 6. Сколько различных трёхзначных чисел можно составить из цифр 7, 6, 5, 0, если цифры в записи числа не могут повторяться? 8. Сколько нечетных трёхзначных чисел можно составить из цифр 3, 4, 8, 6? (Цифры в записи числа не могут повторяться). Справка Подсказка 9. Из цифр 1, 2, 3, 4, 5 составить трехзначные числа. Сколько таких чисел можно составить? Задание 4 7. Секретный замок состоит из 4 барабанов, на каждом из которых можно выбрать цифры от 0 до 9. Сколько различных вариантов выбора шифра существует? 6. Сколько различных трёхзначных чисел можно составить из цифр 7, 6, 5, 1, если цифры в записи числа не могут повторяться? 8. Сколько нечетных трёхзначных чисел можно составить из цифр 3, 4, 8, 6? (Цифры в записи числа не могут повторяться). Справка 9. Из цифр 1, 2, 3, 4, 0 составить трехзначные числа. Сколько таких чисел можно составить? Это размещения. А43 Ответ: 24 Это размещения. А104 с повторениями Ответ: 10000 Число единиц равно 3. Значит осталось разместить числа 4,8,6 на 2-х местах. А32 =Р3 Ответ: 6 Всего разместить 5 числа по 3 можно А53 способами. Но 0 не может стоять впереди. Таких чисел А43. Чисел будет А53 – А42 Ответ: 48 Задание 5 11. В хоровом кружке занимаются 9 человек. Необходимо выбрать двух солистов. Сколькими способами это можно сделать? 10. При встрече каждый из друзей пожал другому руку. Сколько всего было рукопожатий, если встретились 6 друзей? 12. Пятеро друзей сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно? Справка Подсказка 13. Имеется 6 видов овощей. Решено готовить салаты из трёх видов овощей. Сколько различных вариантов салатов можно приготовить? Задание 5 11. В хоровом кружке занимаются 9 человек. Необходимо выбрать двух солистов. Сколькими способами это можно сделать? 10. При встрече каждый из друзей пожал другому руку. Сколько всего было рукопожатий, если встретились 6 друзей? 12. Пятеро друзей сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно? Справка 13. Имеется 6 видов овощей. Решено готовить салаты из трёх видов овощей. Сколько различных вариантов салатов можно приготовить? Это сочетания. С62 Ответ: 15 Это сочетания. С92 Ответ: 36 Это сочетания. С52 Ответ: 10 Это сочетания. С63 Ответ: 20 Заметим, что во всех задачах неважен порядок выбора. Задание 6 15. В первенстве страны по футболу участвуют 16 команд, а по итогам первенства высшую лигу покидают команды, занявшие последние два места. Каково может быть число различных «печальных» исходов футбольного первенства? 14. В магазине продаются блокноты 7 разных видов и ручки 4 разных видов. Сколькими способами можно выбрать покупку из двух разных блокнотов и одной ручки? 16. Из вазы с фруктами, где лежит 9 яблок и 6 груш, нужно выбрать 3 яблока или 2 груши. Сколькими способами это можно сделать? Справка Подсказка 17. Сколькими способами можно группу из 12 человек разбить на 2 подгруппы, в одной из которых должно быть не более 5, а во второй – не более 9 человек? Далее Подсказка Подсказка Задание 6 14. В магазине продаются блокноты 7 разных видов и ручки 4 разных видов. Сколькими способами можно выбрать покупку из двух разных блокнотов и одной ручки? Справка Блокноты можно выбрать С72 способами Ручки можно выбрать 4 – мя способами Покупка состоит из блокнотов И ручки – правило умножения Ответ: 84 Задание 6 15. В первенстве страны по футболу участвуют 16 команд, а по итогам первенства высшую лигу покидают команды, занявшие последние два места. Каково может быть число различных «печальных» исходов футбольного первенства? 16. Из вазы с фруктами, где лежит 9 яблок и 6 груш, нужно выбрать 3 яблока или 2 груши. Сколькими способами это можно сделать? Справка 17. Сколькими способами можно группу из 12 человек разбить на 2 подгруппы, в одной из которых должно быть не более 5, а во второй – не более 9 человек? Число печальных исходов будет С162 способами Ответ: 120 Яблок можно выбрать С93 способами. Груш – С62 . Всего ИЛИ – правило сложения Ответ: 99 Яблок можно выбрать С93 способами. Груш – С62 . Всего ИЛИ – правило сложения Ответ: 99 Задание 6 Справка 17. Сколькими способами можно группу из 12 человек разбить на 2 подгруппы, в одной из которых должно быть не более 5, а во второй – не более 9 человек? В первой группе может быть 1,2,3,4,5. Во второй – не более 9 человек. Если в первой группе 1 или 2человека, то во второй – 11 или 10 человек, что больше 9. И так в первой группе может быть 3,4,5 человек, то во второй – 11 или 10 человек, что больше 9. Их можно выбрать С123, С124, С125 способами. Так как предусматривается ИЛИ – правило сложения. С123 + С124 + С125 способами. Ответ: 1507 Перейдите в режим слайда;Щелкните по таблице два раза;Введите требуемое число n. m n A Перейдите в режим слайда;Щелкните по таблице два раза;Введите требуемые n и m. m n С Перейдите в режим слайда; 2. Щелкните по таблице два раза;3. Введите требуемые n и m. 1. Вычислить: а) Р4 ; б) Р6 ; в) Р10 Ответ: а) 24; б) 720; в) 3628800 2. Вычислить: а) А42 ; б) А63 ; в) А10 5 *Ответ: а) 12; б) 120; в) 30240 3. Вычислить: а) С42 ; б) С63 ; в) С10 5 *Ответ: а) 6; б) 20; в) 252 Для расчета лучше сокращать: С83 4. Вычислить: а) С42 · С53 ; б) С83 : С94 Ответ: а) 60; б) 4/9; 5. В магазине «Все для чая» есть 6 разных чашек и 4 разных блюдца. Сколько вариантов чашки с блюдцем можно купить? Ответ: 24 6. Сколькими способами можно расставить на книжной полке подряд друг за другом книги десятитомного собрания сочинений? Ответ: 3628800 7. Сколькими способами можно сделать трехцветный флаг с вертикальными полосами одинаковой ширины и различных цветов, если имеется материя 7 различных цветов? Ответ: 210 8. Сколько существует четырехзначных чисел, в которых две единицы стоят рядом, а остальные цифры различны и не равны 1? Ответ: 216 Указание: Рассмотрите на каких местах стоят 11. Подсчитайте число возможных способов расстановки оставшихся цифр, с учетом, что они не повторяются. А92 *6 9. Игральную кость бросают дважды. Сколько комбинаций может быть, чтобы сумма выпавших очков была не больше 8? Ответ: 15 10. Имеются девять различных книг, четыре из которых учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом? Ответ: 720. Указание 4 учебника как бы «склеить», считать как одну книгу 11. В расписании на понедельник шесть уроков : алгебра, геометрия, биология, история, физкультура, химия. Сколькими способами можно составить расписание уроков на этот день так, чтобы два урока математики стояли рядом. Ответ: 120 12. Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета? Ответ: 1680 13. Сколько трехзначных чисел ( без повторения цифр в записи числа) можно составить из цифр 0, 1, 2, 3, 4, 5, и 6? Ответ: 180. Указание: Определите сколько можно составить вариантов (А73), определите сколько вариантов с нулем на первом месте (А62) и вычтите, при этом 6 – количество цифр без 0, 2 – число оставшихся знаков в трехзначном числе. 14. Пятеро друзей сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно? Ответ: 15. Указание: порядок неважен. С62. Так как 1 – 2 и 2 – 1 одна и та же партия, то количество партий будет в два раза меньше. 15. Из 16 рабочих надо выбрать бригаду из 5 человек. Сколькими способами это можно сделать? Ответ: 4368 16. В классе 7 человек успешно занимаются математикой.Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде? Ответ: 21 17. Из трехзначных чисел, записанных с помощью цифр 1, 2, 3, 4,5, 6, 7, 8, 9 (без повторений цифр). Сколько таких в которых: a) не встречаются цифры 6 и 7; b) цифра 8 является последней? Ответ: а) 392. Указание: А93 – 2А62 , б) 23. Указание А82/2 18. У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги? Ответ: 756. Указание: найдите сколькими способами можно выбрать по 2 книги у каждого (порядок неважен), предусматривается И 19. Обезьяну посадили за пишущую машинку с 45 клавишами, определить число попыток, необходимых для того, чтобы она наверняка напечатала первую строку романа Л.Н. Толстого «Анна Каренина», если строка содержит 52 знака ? Ответ: А5245 = 5245 20. Сколько существует пятизначных чисел, которые  одинаково читаются слева направо  и справа налево?  Ответ: 900. Указание: Пусть число XYZYX. X – любое кроме 0(9 цифр), Y – любое (10 цифр), Z – любое (10 цифр). Правило произведения 21. В лаборатории, в которой работают заведующий и 10 сотрудников, надо отправить в командировку 5 человек. Сколькими способами это можно сделать, если: а) заведующий лабораторией должен ехать в командировку; б) заведующий должен остаться. Ответ: а) 210. Указание: с заведующим нужно выбрать 4 человека из 10; б) 252 22. В классе учатся 16 мальчиков и 12 девочек. Для уборки территории нужно выделить 4 мальчика и три девочки. Сколькими способами это можно сделать? Ответ: 400400. Указание: произведение сочетаний 1. В магазине «Все для дома» есть 7 видов чашек разных цветов и 5 видов блюдец разных цветов. Сколько вариантов чашки с блюдцем можно купить? 35 2. Сколькими способами можно расставить на полке подряд друг за другом 8 фигурок? 40320 3. Сколькими способами можно сделать трехцветный флаг с вертикальными полосами одинаковой ширины и различных цветов, если имеется материя 4 различных цветов? 24 4. Сколько существует четырехзначных чисел, в которых две тройки стоят рядом, а остальные цифры различны и не равны 3? 216 5. В течение 30 дней сентября было 12 дождливых дней, 8 ветреных, 4 холодных, 5 дождливых и ветреных, 3 дождливых и холодных, а один день был и дождливым, и ветреным, и холодным. В течение скольких дней в сентябре стояла хорошая погода. 15 12+8+4-(5+3+1) 6. Сколько существует четных пятизначных чисел, начинающихся нечетной цифрой? 25000 1-ое место 5ц,5-ое -5 3внутри – 10*10*10 7. Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе повторяться не могут. 210 А73 8. Сколько существует семизначных телефонных номеров, в которых все цифры разные, а номер не может начинаться с нуля? 544320 А107 – А96 9. Сколькими способами можно расставить на полке 12 книг, из которых 5 книг – это сборники стихотворений, так, чтобы сборники стояли рядом? (7+1)!* 5! 10. В классе 15 мальчиков и 11 девочек. Для уборки территории возле школы нужно 3 мальчика и 3 девочки. Сколькими способами можно их выбрать со всех учеников класса? 75075 С153*С113 11. Единицей цифровой информации в двоичной системе является байт – это «слово», состоящее из 8 бит (каждый бит – это двоичный разряд, состоящий из 0 или 1). Сколько знаков содержит кодовая таблица для шрифтов? 256 А 28 12. Сколько существует способов зачеркнуть 5 цифр из 36 в билете спортлото? 376992 С365 1. Сколько перестановок можно сделать из букв слова «Миссисипи».Ответ: 2520***2. Имеется пять различных стульев и семь рулонов обивочной ткани различных цветов. Сколькими способами можно осуществить обивку стульев.Ответ: 168073. На памятные сувениры в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные аппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры? Сколькими способами могут быть выбраны 9 предметов для участников игры?Ответ: 49, 2204. Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы ни одна из них не могла бить другую?Ответ: 403205. Сколько может быть случая выбора 2 карандашей и 3 ручек из пяти различных карандашей и шести различных ручек?Ответ: 2006. Сколько способов раздачи карт на 4 человека существует в игре «Верю – не верю» (карты раздаются полностью, 36 карт).Ответ: …7. В течение 30 дней сентября было 12 дождливых дней, 8 ветреных, 4 холодных, 5 дождливых и ветреных, 3 дождливых и холодных, а один день был и дождливым, и ветреным, и холодным. В течение скольких дней в сентябре стояла хорошая погода.Ответ: 158. На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?Ответ: 480, 4379. Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?Ответ: 910. Сколько существует четных пятизначных чисел, начинающихся нечетной цифрой?Ответ: 2500011. В книжный магазин поступили романы Ф. Купера «Прерия», «Зверобой», «Шпион», «Пионеры», «Следопыт» по одинаковой цене. Сколькими способами библиотека может закупить 17 книг на выбранный чек?Ответ: 2985 Задача 1.В магазине «Все для чая» есть 6 разных чашек и 4 разных блюдца. Сколько вариантов чашки и блюдца можно купить?Решение.Чашку мы можем выбрать 6-ю способами, а блюдце 4-я способами. Так как нам надо купить пару чашку и блюдце, то это можно сделать 6 · 4 = 24 способами (по правилу произведения).Ответ: 24.Для успешного решения комбинаторных задач надо еще и правильно выбрать формулу, по которой искать количество нужных соединений. В этом поможет следующая схема.Рассмотрим решение нескольких задач на разные виды соединений без повторений.Задача 2. Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе повторяться не могут.Решение.Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок учитывается и не все элементы одновременно выбираются. Значит, это соединение – размещение из 7 элементов по 3. Воспользуемся формулой для числа размещений: A73 = 7(7 – 1)(7 – 2) = 7 · 6 · 5 = 210 чисел.Ответ: 210.Задача 3.Сколько существует семизначных телефонных номеров, в которых все цифры разные, а номер не может начинаться с нуля?Решение.На первый взгляд эта задача такая же, как и предыдущая, но сложность в том, что надо не учитывать те соединения, которые начинаются с нуля. Значит необходимо из существующих 10-ти цифр составить все семизначные номера телефонов, а потом от полученного числа отнять количество номеров, начинающихся с нуля. Формула будет иметь вид:A107 – A96 = 10 · 9 · 8 · 7 · 6 · 5 · 4 – 9 · 8 · 7 · 6 · 5 · 4 = 544 320.Ответ: 544 320.Задача 4.Сколькими способами можно расставить на полке 12 книг, из которых 5 книг – это сборники стихотворений, так, чтобы сборники стояли рядом?Решение.Сначала примем 5 сборников условно за одну книгу, потому что они должны стоять рядом. Так как в соединении существенным есть порядок, и все элементы используются, значит это перестановки из 8 элементов (7 книг + условная 1 книга). Их количество Р8. Далее будем переставлять между собой только сборники стихотворений. Это можно сделать Р5 способами. Поскольку нам нужно расставить и сборники, и другие книги, то воспользуемся правилом произведения. Следовательно, Р8 · Р5 = 8! · 5!. Число способов будет большим, поэтому ответ можно оставить в виде произведения факториалов.Ответ: 8! · 5!Задача 5. В классе 16 мальчиков и 12 девочек. Для уборки территории возле школы нужно 4 мальчика и 3 девочки. Сколькими способами можно их выбрать со всех учеников класса?Решение.Сначала отдельно выберем 4 мальчика из 16 и 3 девочки из 12. Так как порядок размещения не учитывается, то соответственные соединения – сочетания без повторений. Учитывая необходимость одновременного выбора и мальчиков, и девочек, используем правило произведения. В результате число способов будет вычисляться таким образом:С164 · С123 = (16!/(4! · 12!)) · (12!/(3! · 9!)) = ((13 · 14 · 15 · 16) / (2 · 3 · 4)) ·((10 · 11 · 12) / (2 · 3)) = 400 400.Ответ: 400 400.Таким образом, успешное решение комбинаторной задачи зависит от правильного анализа ее условия, Единицей цифровой информации в двоичной системе является байт – это «слово», состоящее из 8 бит (каждый бит – это двоичный разряд, состоящий из 0 или 1). Почему кодовая таблица для шрифтов содержит именно 256 знаков?Количество мест для заполнения (т.е. k) по условию у на 8, видов элементов для заполнения мест (т.е. n) всего 2. Следовательно, А82 = 28 = 256 Пример 7. Из цифр 1, 2, 3, 4, 5 составить трехзначные числа. Сколько таких чисел можно составить?Решение. В данной задаче рассматриваются трехзначные числа. Записывая трехзначные числа, будем образовывать не что иное, как кортежи длины 3. Так как в записи этих чисел цифры могут повторяться, то цифру сотен, цифру десятков и цифру единиц можно выбрать пятью способами каждую. Поскольку запись трехзначного числа представляет собой упорядоченный набор из трех элементов, то, согласно правилу произведения, его выбор можно осуществить 125 способами, так как 5 Ч 5 Ч 5 = 53 = 125. Примеры чисел: 234, 551, 323, 222 и т.д.Записывая различные числа, состоящие из трех цифр, мы образовывали кортежи длины 3. В комбинаторике такие кортежи называются размещениями без повторений. В первом примере записан кортеж из пяти элементов по 3. Перейдите в режим слайда;Щелкните по таблице два раза;Введите требуемое число n. m n A Перейдите в режим слайда;Щелкните по таблице два раза;Введите требуемые n и m. m n С Перейдите в режим слайда; 2. Щелкните по таблице два раза;3. Введите требуемые n и m.

Приложенные файлы

  • ppt kombinatorika
    Курс по комбинаторике
    Размер файла: 4 MB Загрузок: 17