Повторение основных методов решения комбинаторных задач и формул комбинаторики

Комбинаторика – это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности, например конструктору, разрабатывающему новую модель механизма, ученому-агроному, планирующему распределение с/х культур на нескольких полях, химику, изучающему строение органических молекул, имеющих данный атомный состав.

Методы решения комбинаторных задач 1. Правило суммы. 2. Правило произведения 3. Таблицы. 4. Графы (деревья). 5. Формулы.

Правило суммы Правило суммы Если элемент А может быть выбран к 1 способами, а элемент В – к 2 способами, причем выборы А и В являются взаимно исключающими, то выбор «либо А, либо В» может быть осуществлен к 1+к 2 способами. Задача 1. Сколько существует способов выбрать кратное двум или трем число из множества чисел : 2,3,4,15,16,20,21, 75,28 ? Решение: к 1=5 –кратное 2 (2,4,16,20,28), к 2=4 – кратное 3 (3,15,21,75) к 1+к 2 = 5+4 = 9

Правило произведения Правило произведения Если элемент А может быть выбран к 1 способами, а элемент В – к 2 способами, то выбор «А и В» может быть осуществлен к 1 кк 2 способами Задача 2. а) Сколько различных двузначных чисел можно составить из цифр 1,3,5,7,9? Решение: N= 5 х 5 = 25 ( Если не сказано, что элемент не повторяется, то выборка с повторениями) б) Сколько среди них чисел, кратных 5? Решение: Число кратно 5, если оканчивается цифрой 5 или 0. В нашем случае – 5. На первой позиции фиксируем одну из пяти цифр, на второй – 5. N= 5 х 1 =5 в) Сколько среди них чисел, кратных 11? Решение: Двузначное число кратно 11, если обе его цифры одинаковы. N= 5

г) Сколько среди них чисел, кратных 3? Решение: Число кратно 3, если сумма его цифр делится на 3. Составим всевозможные пары: – 5 7 – – 7 7 – – 9 1 – 9 Таких пар 15. Среди них 5 пар, сумма которых делится на 3, причем три пары допускают перестановку, т.е. могут образовать по два разных числа. Всего 5+3=8 различных двузначных чисел.

Задача 3. Сколько существует способов занять 1-ое, 2-ое и 3-е места на чемпионате по футболу, в котором участвуют а) 10 команд Решение: N=10 х 9 х 8=720 б) 11 команд? Решение: N=11 х 10 х 9 х 8=990 Задача 4. Сколько различных трехзначных чисел можно составить из цифр 0, 1,2,3,4, если а) цифры не повторяются? Решение: На первом месте одна из 4-х цифр ( 0 не может быть), на 2-ом – одна из оставшихся 4-х: N=4 х 4= 16. б) цифры могут повторяться? Решение: На 1-ом месте может быть одна из 4-х цифр, на 2-ом – одна из 5 (0 входит): N=4 х 5= 20

Задача 5. В клетки квадратной таблицы 2 х 2 произвольно ставят крестики и нолики. а) Сколькими способами можно заполнить эту таблицу? Решение: Для заполнения первой клетки есть 2 способа ( крестик или нолик); для заполнения каждой последующей – тоже 2 способа; общее количество способов заполнить таблицу по правилу произведения равно 2 х 2 х 2 х 2=16. б) В скольких случаях в левой нижней клетке будет стоять крестик? Решение: Если в левой нижней клетке фиксируем крестик, то остальные 3 клетки можно заполнить 2 х 2 х 2=8 различными способами. в) В скольких случаях в верхней левой и нижней правой будут разные значки? Решение: Если в верхней клетке – крестик, а нижней – нолик, то остальные клетки можно заполнить 2 х 2=4 способами. Если в верхней клетке – нолик, в нижней – крестик, то еще 4 способа заполнения. Всего 4+4=8 способов.

Задача 6. В контрольной работе будет 5 задач – по одной из каждой пройденной темы. Задачи будут взяты из общего списка по 10 задач в каждой теме, а всего было пройдено 5 тем. При подготовке к контрольной работе Вова решил только по 8 задач в каждой теме. Найдите: а) общее число всех возможных вариантов контрольной работы Решение: Каждая задача может быть выбрана 10 способами. По правилу произведения N=10 х 10 х 10 х 10 х 10= б)число тех вариантов, в которых Вова умеет решать все 5 задач Решение: N=8 х 8 х 8 х 8 х 8=32768 в) число тех вариантов, в которых Вова не сможет решить ни одной задачи Решение: N=2 х 2 х 2 х 2 х 2=32 г) число тех вариантов, в которых Вова умеет решать все задачи, кроме первой. Решение: N=2 х 8 х 8 х 8 х 8=8192

Задача 7. Три вершины правильного 10-угольника покрасили в рыжий цвет, а остальные – в черный. Сколько можно провести отрезков с разноцветными концами? Решение: Первую рыжую вершину можно соединить отрезком с любой из 10 – 3 = 7 черных вершин, после этого вторую рыжую вершину можно соединить отрезком с любой из 6 оставшихся черных вершин, а третью рыжую – с любой из 5 оставшихся черных вершин. Общее число вариантов (отрезков с разноцветными концами) по правилу произведения равно: 7 х 6 х 5=210 Задача 8. Сколько ребер имеет полный граф (каждая вершина соединена с каждой), если количество его вершин 12? Решение: Первую вершину можно выбрать из 12, вторую – из 11; всего 12 х 11=132 пары. Но они учитывают порядок выбора (каждая пара входит дважды). Поэтому количество ребер равно 12 х 11:2=66

Таблицы вариантов Задача 9. Составляя расписание уроков на понедельник для 7 а класса, завуч хочет первым уроком поставить либо физику, либо алгебру, а вторым – либо русский язык, либо литературу, либо историю. Сколько существует вариантов составления расписания на первые два урока? Решение: Составим таблицу вариантов: Всего существует 2 х 3 = 6 вариантов 2 урок 1 урок русский литера тура история физика Физика русский Физика литература Физика история алгебра Алгебра русский Алгебра литература Алгебра история

Таблицы вариантов Задача 10. Сколько двузначных чисел, кратных 3, можно получить из цифр 1,3,5,7,9? а) цифры не повторяются - 6 вариантов (15,39,57,51,75,93) б) цифры могут повторяться – 8 вариантов (еще 33,99)

Подсчет вариантов с помощью графов Задача 11. При встрече каждый из друзей пожал другому руку. Сколько было рукопожатий, если друзей: а) трое б) четверо в) пятеро N=3 N=6 N=

Построение графов Построение графов Задача 12. По окончании деловой встречи специалисты обменялись визитными карточками. Сколько всего визитных карточек было роздано, если во встрече участвовали: А) 3 человека б) 4 человека в) 5 человек 3 ребра, 6 стрелок 6 ребер, 12 стрелок 10 ребер, 20 стрелок N=6 N=12 N=

Граф-дерево Задача 13. Из 4-х тузов поочередно выбирают два. А) Нарисуйте дерево возможных вариантов (12 вариантов) Б) В скольких случаях среди выбранных будет бубновый туз? (6) В) В скольких случаях вторым выбранным будет туз пик? (3) Г) В скольких случаях тузы будут разного цвета? (8) Б Ч П К 1-ый выбор Ч П К Б П К Ч Б К Б Ч П 2-ой выбор ТУЗЫ

Граф-дерево Задача 14. Маше на день рождения подарили 3 букета цветов: из роз (р), астр (а) и гвоздик (г). В доме было 2 вазы: хрустальная (х) и керамическая (к). Маша пробовала устанавливать каждый букет в каждую вазу. Перечислить все полученные сочетания букета с вазой. варианты керамическая.хрустальная Г А Р Исходы: к-г, к-а, к-р, х-г, х-а, х-а – всего 6 вариантов

Виды выборок: Перестановки Размещения Сочетания Размещения с повторениями Перестановки с повторениями Сочетания с повторениями

Формулы комбинаторики Формулы комбинаторики Факториал числа Произведение n первых натуральных чисел называется факториал числа n и обозначается n! 5!=1*2*3*4*5=120; n!=1*2*3*…*(n-1)*n Перестановка без повторений. Даны цифр: 1,2,3,4,5,6,7. Сколько различных чисел можно составить из этих цифр? Каждое число является перестановкой из 7 элементов. Примеры: , , Перестановка-упорядоченное множество. Число перестановок из n элементов вычисляют по формуле Pn=n!. По условию n=7 Так из 7 цифр можно 7!=1*2*3*4*5*6*7=5040 различных чисел. Перестановка с повторениями. Даны цифр: 1,2,2,3,3,3,4,. Сколько различных чисел можно составить из этих цифр? Каждое число является перестановкой из 7 элементов. Примеры: , , Некоторые числа при перестановке одинаковых цифр не меняется. Число таких перестановок вычисляется по формуле Pn=n!/(n1!*n2!*n3!). По условию n=7, n1=2, n2=3 Получаем 7!/(2!*3!)=5040/12=420 различных чисел.

Формулы комбинаторики. Формулы комбинаторики. Сочетание. Имеется 7 цветных карандашей. Выбирается 3 карандаша. Сколько существует способов выбрать 3 карандаша, чтобы не было повторяющихся наборов? Выборка из трёх карандашей – это сочетание из 7- ми по 3 элемента в каждом. Сочетание - неупорядоченная выборка из данного множества элементов. Число сочетаний из n элементов по m в каждом находим по формуле: Cn = n!/(m!*(n-m)!). Пример. В классе обучается 20 человек. Сколько существует способов выбрать актив, состоящий из 4 человек? Решение. Находим число сочетаний из 20 элементов по 4 в каждом: 20!/(4!*16!)=17*18*19*20/24=4845 способов выбрать актив. Размещение. Буквы алфавита записаны на карточках. Выбирается 4 карточки и затем из набора составляют различные слова. Под словом будем понимать порядок следования букв. Например: плот, лотп, лпот- разные слова. Каждое полученное слово-это размещение. Размещение –упорядоченная выборка из данного множества элементов. Число размещений из n элементов по m в каждом находим по формуле: An =n!/(n-m)!. Сколько слов можно получить в предложенной задаче? По формуле получаем решение 32!/(32-4)!=32!/28!=29*30*31*32= слов можно получить.