СЕМЁНОВА Т.А. МОУ СОШ 82 Г. ЧЕРНОГОЛОВКА Элементы комбинаторики

Примеры комбинаторных задач

Пример 1 Из группы теннисистов, в которую входят четыре человека-Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары? АГ, АС, АФ ГС, ГФ СФ Значит, всего существует шесть вариантов выбора Способ рассуждений, которым мы воспользовались, называют перебором возможных вариантов

Пример 2 Сколько трехзначных чисел можно составить из цифр 1, 3, 5, 7,используя в записи числа каждую из них не более одного раза? Чтобы ответить на вопрос задачи, выпишем все такие числа. Полученные результаты запишем в четыре строки, в каждой из которых шесть чисел:

Способ второй Проведенный перебор вариантов проиллюстрирован на схеме Такую схему называют деревом возможных вариантов

Способ третий Первую цифру можно выбрать четырьмя способами. Так как после выбора первой цифры останутся три, то вторую цифру можно выбрать уже тремя способами. Наконец, третью цифру можно выбрать двумя способами. Следовательно, общее число искомых чисел равно произведению 4*3*2,т.е.24 Использовалось комбинаторное правило умножения: Пусть имеется п элементов и требуется выбрать из них один за другим k элементов. Если первый элемент можно выбрать п 1 способами, после чего второй элемент можно выбрать п 2 способами из оставшихся, затем третий элемент можно выбрать п 3 способами из оставшихся и т. д., то число способов, которыми могут быть выбраны все k элементов, равно произведению п 1 · п 2 · п 2 · … · пк.

Пример 3 Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани-две дороги. Туристы хотят проехать из города А через В и С к пристани. Сколькими способами они могут выбрать маршрут? Решение: 2*3*2=12

Задачи 1. В кафе предлагают два первых блюда :борщ, рассольник-и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из двух блюд, которые может заказать посетитель. Построить дерево возможных вариантов 2. Стадион имеет четыре входа: А, В, С, D. Укажите все возможные способы, какими посетитель может войти через один вход, а выйти через другой. Сколько таких способов? Ответ:12 способов 3. Используя цифры 0,2,4,6 составьте все возможные трехзначные числа, в которых цифры не повторяются.

Задачи 4. В шахматном турнире участвуют 9 человек. Каждый из них сыграл с каждым по одной партии. Сколько всего партий было сыграно? Ответ:36 партий 5. При встрече 8 человек обменялись рукопожатиями. Сколько всего было сделано рукопожатий? Ответ:28 рукопожатий 6. Учащиеся 9 класса решили обменяться фотографиями. Сколько фотографий для этого потребуется, если в классе 24 учащихся? Ответ:552 фотографии

Задачи 7. В кафе имеются три первых блюда, пять вторых блюд и два третьих. Сколькими способами посетитель кафе может выбрать обед, состоящий из первого, второго и третьего блюд? Ответ:30 способов 8. Петр решил пойти на новогодний карнавал в костюме мушкетера. В ателье проката ему предложили на выбор различные по фасону и цвету предметы: пять видов брюк, шесть камзолов, три шляпы, две пары сапог. Сколько различных карнавальных костюмов можно составить из этих предметов? Ответ:180 костюмов

Перестановки Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки Число перестановок из n элементов обозначают символом Рn(читается «Р из n») Для произведения первых n натуральных чисел используют специальное обозначение: n! ( читается n факториал) 2!=2; 5!=120; 1!=1

Примеры задач Таким образом, число всевозможных перестановок из n элементов вычисляется по формуле: Рn=n! Пример 1. Сколькими способами могут быть расставлены 8 участниц финального забега на восьми беговых дорожках? Р 8 =8!=40320 Пример 2. Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, 6? Из цифр 0,2,4,6 можно получить Р 4 перестановок. Из этого числа надо исключить те перестановки, которые начинаются с 0.Получаем: Р 4 -Р 3 =4!-3!=18

Пример 3. Имеется 9 различных книг, четыре из которых- учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом? Сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 9,а 6 книг. Это можно сделать Р 6 способами. В каждой из полученных комбинаций можно выполнить Р 4 перестановок учебников. Значит, искомое число способов расположения книг на полке равно произведению Р 6 *Р 4. Получаем: Р 6 *Р 4 =6!*4!=720*24=17280

Задачи 1. Сколькими способами 4 человека могут разместиться на четырехместной скамейке? Ответ:24 2. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать? Ответ: Сколько шестизначных чисел(без повторения цифр) можно составить из цифр: а)1,2,5,6,7,8; б)0,2,5,6,7,8 ? Ответ : а)720;б) В расписании на понедельник шесть уроков:алгебра,геометрия,биология,история,физкультура,химия.С колькими способами можно составить расписание уроков на этот день так, чтобы два урока математики стояли рядом? Ответ:240

Задачи 5. Делится ли число 14! На: А)168; б)136;в)147;г)132? Ответ на 6) :15; 1/90; 1722; 40

1 вариант 2 вариант 1. Комбинаторные задачи 2. Способы решения комбинаторных задач 3. Вычислить 1. Перестановки, формула 2. Комбинаторика 3. Вычислить Проверочная работа

Размещения Пусть имеется 4 шара и 3 пустых ячейки. В пустые ячейки можно по- разному разместить три шара из этого набора шаров. Выбирая разными способами первый, второй и третий шары, будем получать различные тройки шаров. Каждую упорядоченную тройку, которую можно составить из четырех элементов, называют размещением из четырех элементов по три Размещением из n элементов по к (к

Примеры 1. Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета? В этом примере речь идет о размещениях из 8 элементов по 4. Имеем: 2. Сколько трехзначных чисел ( без повторения цифр в записи числа) можно составить из цифр 0,1,2,3,4,5,6? Среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому:

Задачи 1. Сколькими способами может разместиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет? Ответ: Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать? Ответ: Сколькими способами организаторы конкурса могут определить, кто из 15 его участников будет выступать первым, вторым и третьим? Ответ: На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места: а)2 фотографии; б) 4 фотографии; в) 6 фотографий? Ответ: 30;360;720

Сочетания Сочетанием Сочетанием из n элементов по к называется любое множество, составленное из данных n элементов В отличие от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы.Два сочетания из элементов по к отличаются друг от друга хотя бы одним элементом Обозначают Читают «С из n по к» Формула числа сочетаний из n элементов по к,где к

Примеры 1. Из 15 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор? Каждый выбор отличается от другого хотя бы одним дежурным. Значит, здесь речь идет о сочетаниях из 15 элементов по 3 Имеем: 2. Из вазы с фруктами, в которой лежит 9 яблок и 6 груш, надо выбрать 3 яблока и 2 груши. Сколькими способами можно сделать такой выбор? Имеем:

Задачи 1. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде? Ответ:21 2. Учащимся дали список из 10 книг, которые рекомендуется прочитать во время каникул. Сколькими способами ученик может выбрать из них 6 книг? Ответ: В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется выделить четырех мальчиков и трех девочек. Сколькими способами это можно сделать? Ответ: В библиотеке читателю предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами он может выбрать из них 3 книги и 2 журнала? Ответ:720

Самостоятельная работа 1 вариант 1. Сколькими способами 9 участников конкурса могут выступить в порядке очередности в финале ? 2. Делится ли число 40! на: а)410;б)500;в)780? 3. Используя цифры 0,3,7,8 составьте все возможные двузначные числа, в которых цифры не повторяются 4. В городской думе 10 депутатов моложе 30 лет. Сколькими способами можно выбрать из них троих для работы в комитете по молодежной политике? 2 вариант 1. Курьер должен развести пиццу по шести адресам. Сколько маршрутов он может выбрать? 2. Делится ли число 50! на: а)400;б)98;в)510? 3. Используя четные цифры 0,2,4,6,8, составьте все возможные трехзначные числа, в которых цифры не повторяются 4. В группе 9 студентов хорошо владеют иностранным языком. Сколькими способами можно выбрать из них четверых для работы на практике с иностранцами?

Ответы 1 вариант 1. 9!= а) нет б) да в) да вариант 1. 6!= а) да б) да в) да чисел