КОМБИНАТОРИКА
Комбинаторика – раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.
Пример 1.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?
Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.
По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.
Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены:
Пример 2.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?
Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.
После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.
По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.
Сочетания без повторений. Сочетания с повторениями
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?
Пример 3.
Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?
Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?
.
Пример 4.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.
.
Размещения без повторений. Размещения с повторениями
Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Пример 5.
В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?
Пример 6.
У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?
Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:
.
Перестановки без повторений. Перестановки с повторениями
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Пример 7.
Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?
Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k
Пример 8.
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»
Источник
Задачи комбинаторики.
Чтобы научиться быстро бегать, нужно много бегать. Чтобы научиться хорошо решать сложные задачи, нужно решать много простых задач. И то, и другое надо делать с умом. Последовательно тренировать определенные группы мышц, и постепенно вникать в смысл математических выражений.
Давайте рассмотрим несколько очень простых задач, сравнивая их между собой. Сравнение поможет нам понять и запомнить, как выбрать нужную формулу для подсчёта числа вариантов в той или иной ситуации. А чтобы никто не усомнился в том, что задачи действительно простые, я взяла за основу Сборник тестовых заданий к учебнику Н.Я. Виленкина и др. «Математика. 5 класс». Конечно, для пятиклассников это задания высокого уровня сложности «С», но они справляются. Дело в том, что эти задачи можно решить как простым перебором вариантов, тем быстрее, чем выше уровень обобщения, так и по формулам комбинаторики. Старшеклассникам рекомендую повторить формулы и правила комбинаторики, если вы попали на эту страницу из поисковика, миновав теорию.
Итак,
— внимательно читаем условия 2-ух задач из одной строки таблицы;
— решаем обе задачи любыми доступными способами (желательно не одним);
— открываем ответы нажатием на зеленые кнопки и сравниваем их со своими ответами;
— открываем решения и комментарии к ним нажатием на желтые кнопки.
Помните, что ваше решение не обязательно должно совпадать с моим, достаточно, чтобы оно было логичным и позволяло получить верный ответ.
Задачи и решения.
Задача 1a | Задача 1b |
---|---|
При окончании деловой встречи специалисты обменялись визитными карточками. Сколько всего визитных карточек перешло из рук в руки, если во встрече участвовали 6 специалистов? | При встрече каждый из друзей пожал другому руку. Сколько всего было рукопожатий, если встретились 6 друзей? |
Задача 2a | Задача 2b |
В хоровом кружке занимаются 9 человек. Необходимо выбрать двух солистов. Сколькими способами это можно сделать? | В спортивной команде 9 человек. Необходимо выбрать капитана и его заместителя. Сколькими способами это можно сделать? |
Два солиста равноправны. (Может быть, и петь планируют дуэтом.) Нас не волнует порядок следования в группе из 2-ух человек, выбранных из 9-ти. Значит определяем число сочетаний из 9 по 2. Казалось бы, мы снова выбираем 2-ух человек из 9-ти, но теперь между ними качественная разница. Они будут выполнять разные обязанности в команде. Мы выбираем капитана И заместителя независимо друг от друга. Поэтому применим правило умножения вариантов (И-правило). Из 9-ти человек капитана можно выбрать 9-тью способами. Его заместителя из оставшихся 8-ми человек — 8-мью способами. Общее число вариантов: 9·8 = 72. (Заметьте, что если сначала выбрать заместителя из 9 человек, а потом капитана из оставшихся 8-ми, результат будет тот же.) Можно рассуждать иначе. Есть два места для капитана и его заместителя, нужно разместить на них 2-ух человек, выбрав их из 9-ти. Такие группировки (выборки) называются размещениями. Число размещений определяем по формуле | |
Задача 3a | Задача 3b |
Сколько существует вариантов рассаживания вокруг стола 6 гостей на 6 стульях? | В понедельник в пятом классе 5 уроков: музыка, математика, русский язык, литература и история. Сколько различных способов составления расписания на понедельник существует? |
Легко понять, что в этой задаче речь идет о перестановках. 6 гостей занимают все 6 стульев и могут только меняться местами. Число перестановок из 6 определяем по формуле Может быть, не так очевидно, но это тоже перестановки. С точки зрения математики, вообще та же самая задача. Представьте себе, что расписание составляете вы. Чертите таблицу с пятью строками для пяти уроков («готовите стулья») и вписываете в каждую строку название одного из 5-ти предметов («рассаживаете гостей»). Число перестановок из 5 определяем по формуле | |
Задача 4a | Задача 4b |
Пятеро друзей сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно? | Сколькими способами 10 футбольных команд могут разыграть между собой золотые, бронзовые и серебряные медали? |
В шахматной партии 2 равноправных участника (точно также, как в задаче о рукопожатиях). Значит из 5-ти человек формируем группы по 2 без учета порядка следования — сочетания. Определяем число сочетаний из 5 по 2. На пьедестале почёта находятся 3 команды из 10, и для них очень существенно, кто какое место занял, т.е. порядок следования. Составление групп с учетом порядка следования — размещения. Число размещений определяем по формуле | |
Задача 5a | Задача 5b |
В меню столовой предложено на выбор 2 первых блюда, 6 вторых и 4 третьих блюда. Сколько различных вариантов обеда, состоящего из первого, второго и третьего блюда, можно составить? | Имеется 6 видов овощей. Решено готовить салаты из трёх видов овощей. Сколько различных вариантов салатов можно приготовить? |
Задача 6a | Задача 6b |
В магазине продаются блокноты 7 разных видов и ручки 4 разных видов. Сколькими разными способами можно выбрать покупку из одного блокнота и одной ручки? | В магазине продаются блокноты 7 разных видов и ручки 4 разных видов. Сколькими способами можно выбрать покупку из двух разных блокнотов и одной ручки? |
Выбираем одну ручку И один блокнот. Одну ручку из 4-ёх 4-мя способами, один блокнот из 7-ми — 7-ю способами. Применяем правило умножения Выбираем одну ручку И два блокнота. Снова можем применить правило умножения вариантов. Одну ручку из 4-ёх можем выбрать 4-мя способами, два блокнота из 7-ми — ? способами. | |
Задача 7a | Задача 7b |
На прививку в медпункт отправились 7 друзей. Сколькими разными способами они могут встать в очередь у медицинского кабинета? | Секретный замок состоит из 4 барабанов, на каждом из которых можно выбрать цифры от 0 до 9. Сколько различных вариантов выбора шифра существует? |
Число способов встать в очередь равно числу перестановок 7-ми друзей в пределах этой очереди. Задача такая же, как о гостях и стульях, но обратите внимание, насколько быстро растет число вариантов при увеличении числа переставляемых предметов. На каждом барабане можно выбрать 1-ну цифру из 10-ти 10-тью способами и независимо от других, поэтому применяем правило умножения: Можно также считать, что нужно разместить 10 цифр на 4-ёх местах с повторениями. В комбинаторике существует раздел «Выборки с повторениями» (см. подробнее). В данном случае нам нужна формула для размещений. Число размещений с повторениями определяется как n k , где n — количество элементов для выбора (здесь n = 10 цифр), k — объём выборки или количество возможных повторов одного элемента (здесь k = 4, одна и та же цифра может быть установлена на всех четырех барабанах). Таким образом, искомое число вариантов | |
Задача 8a | Задача 8b |
Сколько различных трёхзначных чисел можно составить при помощи цифр 4, 7, 9? (Цифры в записи числа не повторяются). | Сколько различных трёхзначных чисел можно составить с помощью цифр 1, 3, 7? (Цифры могут повторяться). |
Трёхзначное число состоит из 3-ёх цифр, которые нам даны. Поскольку цифры не могут повторяться, то получать различные числа можно только путем их перестановки. Число перестановок из 3-ёх определяем по формуле Если цифры могут повторяться, то по разрядам их можно размещать независимо от друг от друга. Значит можем применить правило умножения вариантов (И-правило). Одну цифру из трёх для разряда сотен можно выбрять 3-мя способами, И одну цифру из тех же трёх для разряда десятков — 3-мя способами, И одну из трёх для разряда единиц — 3-мя способами. Общее число вариантов | |
Задача 9a | Задача 9b |
Сколько различных трёхзначных чисел можно составить с помощью цифр 7 и 3? | Сколько различных двузначных чисел можно составить при помощи цифр 4, 7, 9? (Цифры в записи числа не повторяются). |
Задача 10a | Задача 10b |
Сколько нечетных трёхзначных чисел можно составить из цифр 3, 4, 8, 6? (Цифры в записи числа не могут повторяться). | Сколько различных трёхзначных чисел можно составить из цифр 7, 6, 5, 0, если цифры в записи числа не могут повторяться? |
Искомое число должно оканчиваться цифрой 3, так как 4, 6 и 8 делятся на 2 без остатка. Поэтому позиция единиц у нас уже занята, и остается разместить 3 цифры на 2-ух позициях — десятков и сотен. Число размещений из 3 по 2 определяем по формуле Сначала определим, сколько всего можно составить групп из 4-ёх заданных цифр по 3 с учётом порядка следования и без повторений. | |
Задача 11a | Задача 11b |
Сколько четных трёхзначных чисел можно составить из цифр 3, 4, 5, 6? (Цифры в записи числа не могут повторяться). | Сколько четных трёхзначных чисел можно составить из цифр 3, 4, 5, 6? (Цифры в записи числа могут повторяться). |
Четными будут числа, оканчивающиеся на 4 ИЛИ на 6. Поэтому подсчитаем количество вариантов, заканчивающихся на одну из этих цифр, а затем воспользуемся правилом сложения (ИЛИ-правилом), чтобы определить общее число вариантов. Так же, как в предыдущем случае рассмотрим отдельно числа, заканчивающиеся 4-кой и 6-кой, а затем воспользуемся правилом сложения вариантов. | |
Задача 12a | |
Сколько различных дробей можно составить с использованием цифр 2, 3, 4? (В числителе и знаменателе не может быть одна и та же цифра.) | |
Заметим, что не только в числителе и знаменателе не может быть одна и та же цифра, но цифры вообще не могут повторяться, иначе задача не имела бы смысла. В число дробей входили бы, например, 2/3, 2/33, 2/333, 2/3333 и т.п. Таких вариантов бесконечное число. Если вы получили ответ 12, а не 18, обязательно разберитесь почему. Это иначе понятое условие задачи? Забыты неправильные дроби? Ошибка в комбинаторике? Комментарии.O формуле для числа сочетаний. O формуле для числа размещений. Выборки с повторениями. | |
Перейти на главную страницу сайта. | |