Поделиться
Комбинаторика. Перестановки.pptx
Элементы комбинаторики
10 класс
Комбинаторика – раздел математики, который занимается перечислением и подсчетом комбинаций элементов разных множеств.
Комбинации могут быть составлены из фигур, чисел, событий, предметов.
В теории вероятностей комбинаторика применяется тогда, когда случайный опыт большой и количество событий в нем велико настолько, что их невозможно выписать или даже просто перечислить без применения специальных методов.
Слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать, комбинировать».
Пример . Из группы теннисистов, в которую входит четыре человека – Антонов, Григорьев, Сергеев и Федотов, тренер выделяет пару, для участия в соревнованиях. Сколько существует вариантов выбора такой пары?
Составим все пары, в которые входит Антонов (А). Получим три пары: АГ, АС, АФ.
Запишем теперь пары, в которые входит Григорьев, но не входит Антонов ( пары не должны повторяться): Это две пары: ГС, ГФ.
Составим пары, в которые входит Сергеев, но не входят Антонов и Григорьев: Такая пара только одна СФ. Других вариантов нет, мы перебрали все. Мы получили 6 пар: АГ, АС, АФ, ГС, ГФ, СФ. Значит существует 6 вариантов выбора тренером пары человек из этой группы.
Способ рассуждений, которым мы воспользовались в этом примере, называют перебором возможных вариантов.
Пример . Пусть у нас есть 2 множества. Например, на переговоры приезжают две делегации из двух разных стран. В первой делегации 3 человека, а во второй – 4 человека. Каждый человек из первой делегации пожимает руку каждому из второй делегации. Сколько всего рукопожатий? Построим граф. Сколько элементов в этом множестве? Достаточно подсчитать соединительные линии или ребра этого графа. Их 12. 3 *4 =12. Правило умножения. Если множество А состоит из n элементов, а множество В – из K элементов, то множество упорядоченных пар ( e, r ), где е € А, r € В, состоит из N * K элементов.
Задача 1. Пусть в группе детского сада 11 мальчиков и 9 девочек. Сколько можно составить пар « мальчик – девочка»?
Задача 2. В множестве А восемь элементов, а в множестве В пять элементов. Сколько можно составить пар, взяв по одному элементу из каждого из этих множеств?
Задача 3. В кафе предлагают два первых блюда: борщ и рассольник и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из двух блюд, которые можно заказать в кафе. Постройте граф.
Задача 4. У Ирины 5 подруг: Вера, Зоя, Марина, Полина, Светлана. Она решила двух из них пригласить в кино. Укажите все возможные варианты выбора подруг, Сколько таких вариантов? Постройте граф (дерево).
Ответы на задачи.
Задача 1. 99.
Задача 2. 40.
Задача 3. 8.
Задача 4. 10.
Перестановки. Факториал. Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки.
Пример 3. Трех участников забега надо расположить на трех беговых дорожках. Сколько существует способов их размещения? Решение.
На первую беговую дорожку можно поставить любого из трех человек. На вторую – любого из двух оставшихся, а на последнюю можно поставить только одного оставшегося. Первого можно выбирать тремя способами, второго - двумя способами, а третьего – одним единственным способом. Имеем 3 * 2 * 1 = 6
6 способов перестановки трех человек.
Пример 4. Если участников четверо, то первый номер мы можем присвоить любому из четырех, а оставшиеся номера распределить между тремя остальными 6 способами ( см. предыдущий пример).
Решение.
4 * 6 = 4*3*2*1 = 24 ; 24 способа.
Пример 5. Если участников семеро, то количество перестановок будет: 7*6*5*4*3*2*1 = 5040 способов.
Определение Перестановкой из n элементов называется любой способ нумерации этих элементов ( способ их расположения в ряд). Если есть n элементов, число способов переставить их равно Pn = n*(n - 1)*(n - 2)* …*3*2*1. Факториалом натурального числа N называется произведение все натуральных чисел от 1 до N. Обозначается факториал N! N! = 1*2*3*…* (N-1)*N 0! =1 Число перестановок N элементов равно N! . Pn = N!
Таблица факториалов чисел от 0 до 10
N 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
N! 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40 320 | 362 880 | 3 628 800 |
Пример 6. Сколькими способами могут быть расставлены 8 участников финального забега на 8 дорожках?
Решение.
(для вычисления воспользуемся таблицей факториалов).
P8 = 8! = 1*2*3*4*5*6*7*8 = 40320.
Пример 7. Вычислить выражение ( 15!)/ (13! ∙2!)
Решение.
( 15!)/ (13! ∙2!)= (13! ∙ 14 ∙ 15) / (13! ∙ 1 ∙2) = (14 ∙ 15) / (1 ∙2) =
7 ∙ 15 = 105.
Пример 8. Сколько различных последовательностей можно составить из букв слова «программа»?
Решение.
Слово «программа» содержит 9 букв. P9 = 9! = 362 880.
ЗАДАЧА 3.
В расписании сессии 5 экзаменов. Сколько вариантов экзаменов можно составить?
Решение
1. Р4 = 4! = 1 ∙ 2 ∙ 3 ∙ 4 = 24
Ответ: 24
2. Р10 = 10! = 1∙2∙3∙4∙5∙6∙7∙8∙9∙10 = 3 628 800
Ответ: 3 628 800
3. Р5 = 5! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120
Ответ: 120
Решите задачи.
1. Вычислить выражения: а) 5! / 2!; б) 3! ∙ 4!;
в) 10! / 8! ;
г) 100! / 99!;
д) 12! / ( 3! ∙ 9!) ;
е)45! / ( 44! ∙ 3!).
2. Саша, Ваня и Петя получили номера 1,2 и 3
для участия в соревнованиях. Перечертить таблицу в тетрадь и а)записать все возможные варианты распределения этих номеров между ними; б) вычислить с использованием факториала количество
1 способ | 2 | 3 | 4 | 5 | 6 | |
Саша | ||||||
Ваня | ||||||
Петя | ||||||
3. Сколько различных последовательностей можно составить из букв слов: а)автор; б) учебник; в) качели. 4. В автосервис одновременно приехали 5 машин для ремонта. Сколько существует способов выстроить их в очередь для ремонта? 5. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать? 6. Сколькими способами можно расставить 8 участников соревнования на 8 дорожек? 7. Что больше и во сколько раз : а) 6! ∙ 5 или 5! ∙6; б) 9! ∙ 10 или 10! ∙ 9 ? 8. Сколькими способами 9 человек могут встать в очередь в театральную кассу? 9. Делится ли число 14! на а) 168; б) 136; в) 147; г) 132 ? 10. Сколькими способами 5 мальчиков и 5 девочек могут занять места в театре в одном ряду с1 по 10 номер?
Ответы на задания самостоятельной работы.
1. а) 60; б) 144; в) 90; г) 100; д) 220; е) 7,5
2. С 1 2 3 3 1 2
В 2 1 2 1 3 3
П 3 3 1 2 2 1 1* 2* 3 =6
3. а) 120; б) 5040; в) 720
4. 120.
5. 5040
6. 40320
7. а) в 5 раз; б) в 9 раз.
8. 362880
9. Делится ли 14! а) 168=2*2*2*3*7 (да); б) 136= 2*2*2*17 (нет); в) 147= 3*7*7 (да);
г) 132=2*2*3*11 (да).
10. 3628800.
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
