Сколькими способами можно поставить на полке 4 различные вазы
Добавил пользователь Валентин П. Обновлено: 19.09.2024
Часто в жизни возникает потребность определить количество возможных вариантов развития событий. Существует специальная математическая дисциплина, посвященная подобным вопросам. Она называется комбинаторикой.
План урока:
Комбинаторика и ее основные принципы
Очевидно, что если в конечном множестве содержится n элементов, то есть ровно n способов выбрать один из них.
Пример. В классе 15 человек. Сколькими способами учитель может назначить одного из них ответственным за чистоту доски?
Ответ. Таких способов ровно 15.
В комбинаторике существует два основных правила. Первое из них называется правилом сложения.
Несмотря на формулировку, по сути это очень простое правило.
Пример. В магазине продается 14 телевизоров Panasonic и 17 телевизоров Sony. Петя хочет купить один телевизор. Сколько у него вариантов покупки?
Решение. По правилу сложения Петя может выбрать один из 14 + 17 = 31 телевизоров.
Ответ: 31 телевизор.
Особое значение имеет второе правило, которое называют правилом умножения.
Проиллюстрируем это правило.
Решение. Тренер может составить 15•20= 300 разнополых пар из своих воспитанников.
Пример. Пете нужно купить технику для компьютера. В магазине продается 20 различных клавиатур, 25 моделей геймпадов и 30 компьютерных мышей. Купить надо по одному экземпляру каждого из этих устройств. Сколько вариантов покупки есть у него?
Правила сложения и умножения можно комбинировать.
Пример. Сколько слов не более чем из трех букв можно составить, используя алфавит, содержащий ровно 30 букв?
Решение. Очевидно, что слов из одной буквы можно составить ровно 30. Количество двухбуквенных слов равно количеству пар, которые можно составить из этих букв, то есть 30•30 = 900. Трехбуквенных слов можно составить 30•30•30 = 27000. Всего же слов длиною не более 3 букв будет
30 + 900 + 27000 = 27930
Далее мы изучим основные понятия комбинаторики – перестановки, размещения, сочетания.
Перестановки
Рассмотрим простейшую комбинаторную задачу. На полке расставляют по порядку книги. Их ставят вертикально друг за другом. Сколькими способами можно расставить на полке 2 книги? Очевидно, что двумя:
Либо синяя книжка будет первой слева, либо она будет находиться в конце полки, третьего варианта здесь нет. Здесь условно считается, что варианты, когда между книгами есть зазоры, идентичны вариантам без зазоров:
То есть нас интересует исключительно порядок, в котором стоят книги. Каждый из найденных вариантов называется перестановкой книг. Перестановкой называют любое конечное множество, для элементов которого указан порядок элементов.В комбинаторике перестановки являются одними из основных объектов изучения.
Например, если в забеге на 100 метров стартует 8 спортсменов, то они образуют множество участников забега. После финиша становится известно, кто занял 1-ое место, кто оказался вторым или третьим, а кто стал последним. Результат забега будет перестановкой, ведь он представляет собой список спортсменов с указанием их мест, то есть он определяет порядок между ними.
Вернемся к примеру с книгами. Обозначим количество возможных перестановок n элементов как Рn. Две книжки можно расставить двумя разными способами, поэтому Р2 = 2. Обозначим эти перестановки как АБ и БА. Сколько способов расстановки есть в случае трех книжек? Их все можно получить из вариантов с 2 книжками, добавляя между ними книгами ещё один том:
Видно, что между 2 книгами есть три позиции, на которые можно поставить 3-ий том. Общее количество вариантов равно произведению числа этих позиций и количества вариантов для 2 книг, то есть Р3 = 3•Р2 = 3•2 = 6:
Итак, мы имеем 6 перестановок для 3 книг:
А сколько перестановок существует для 4 книг? Снова-таки, между тремя книгами 4-ый том можно поставить четырьмя способами:
То есть из перестановки трех книг АБВ можно получить 4 перестановки:
Всего существует 6 перестановок для 3 книг (Р3 = 6), и для каждой из них можно построить 4 перестановки из 4 книг. Получается, что общее количество перестановок 4 книг равно
Продолжая подобные рассуждения, можно убедиться, что количество перестановок 5 предметов в 5 раз больше, чем перестановок для 4 объектов:
И вообще, если число перестановок n объектов равно Рn, то количество перестановок (n + 1)объекта равно в (n + 1)раз больше:
При этом отметим, что 1 книгу можно расставить на полке только одним способом:
То есть Р1 = 1. Теперь выпишем значения чисел Р при разном количестве переставляемых предметов, используя формулуРn+1 = (n + 1)Рn
Видно, что количество перестановок n объектов равно произведению всех натуральных чисел от 1 до n. В математике есть специальная функция для вычисления значения этого произведения. Она называется факториалом и обозначается восклицательным знаком.
Например, факториал 6 вычисляется так:
Мы убедились на примере с книгами, что количество перестановок из n различных объектов, которое обозначается как Рn, равно n!.
Относительно факториала надо заметить несколько важных моментов. Во-первых, очевидно, что факториал единицы равен 1:
Во-вторых, иногда в комбинаторных задачах приходится вычислять факториал нуля. По ряду соображений эта величина также принимается равной единице
Объяснить это можно так. Факториал числа можно представить как произведение этого числа и факториала предыдущего числа, например:
5! = 1•2•3•4•5 = (1•2•3•4)•5 = 4!•5
7! = 1•2•3•4•5•6•7 = (1•2•3•4•5•6)•7 = 6!•7
В общем случае формула выглядит так:
Из неё несложно получить, что
Подставив в эту формулу единицу, получим
Пример. Сколькими способами тренер может расставить 4 участников эстафеты 4х400 м по этапам эстафеты?
Решение. Количество таких способов равно числу перестановок 4 различных объектов Р4:
Пример. Вася решил изучать сразу 7 иностранных языков, причем на занятия по каждому из них он собирается выделить ровно один день в неделе. Сколько вариантов расписаний занятий может составить себе Вася?
Решение. В данном случае расписание занятий – это порядок, в котором Вася в течение недели будет изучать иностранные языки, например:
Такое расписание можно описать последовательностью символов:
Ф, Ан, И, К, Я, Ар, П
Создавая расписание, Вася переставляет 7 языков, поэтому общее количество расписаний равно 7!:
Пример. Сколько пятизначных цифр можно записать, используя цифры 0, 1, 2, 3, 4, причем каждую не более одного раза?
Решение. Общее количество перестановок 5 цифр составляет Р5. Однако нельзя начинать запись числа с нуля. Так как, перестановка 12340 – это пятизначное число (двенадцать тысяч триста сорок), а перестановка 03241 – не является пятизначным числом.
Расстановок, начинающихся с нуля, ровно Р4, поэтому общее количество допустимых цифр равно Р5 – Р4:
Р5 – Р4 = 5! – 4! = 120 – 24 = 96
Пример. На полке расставляют 7 книг, однако 3 из них образуют трехтомник. Тома трехтомника должны стоять друг за другом и в определенном порядке. Сколько существует способов расстановки книг?
Решение. Будем считать трехтомник одной книгой. Тогда нам надо расставить 5 книг
Пример. Необходимо расставить 7 книг на полке, но три из них принадлежат одному автору. Их надо поставить друг с другом, но они могут стоять в любом порядке. Сколько возможно перестановок книг.
Решение. Снова будем считать три книги как один трехтомник. Получается, что существует 5! = 120 вариантов. Однако каждому из них соответствует 3! = 6 расстановок книг внутри трехтомника, например:
В итоге на каждую из 120 расстановок приходится 6 вариантов расстановки трехтомника, а общее число расстановок равно, согласно правилу умножения, произведению этих чисел:
Перестановки с повторениями
До этого мы рассматривали случаи, когда все переставляемые объекты были различными. Однако порою некоторые из них не отличаются друг от друга. Пусть на полке надо расставить 3 книги, но две из них одинаковые. Сколько тогда существует перестановок? Общее число перестановок 3 книг составляет 3! = 6:
1-ая группа: БАА1А2, БАА2А1, БА1АА2, БА1А2А, БА2АА1, БА2А1А
2-ая группа: АБА1А2, АБА2А1, А1БАА2, А1БА2А, А2БАА1, А2БА1А
3-ая группа: АА1БА2, АА2БА1, А1АБА2, А1А2БА, А2АБА1, А2А1БА
4-ая группа: АА1А2Б, АА2А1Б, А1АА2Б, А1А2АБ, А2АА1Б, А2А1АБ
И снова для подсчета числа оригинальных перестановок надо из общее число расстановок поделить на количество дубликатов в каждой группе:
Для обозначения перестановок с повторениями используется запись
где n – общее количество объектов, а n1, n2, n3,… nk – количество одинаковых элементов. Например, в задаче с 4 книгами мы искали величину Р4(3, 1), потому что всего книг было 4, но они были разбиты на две группы, в одной из которых находилось 3 одинаковых тома (буквы А, А1, А2), а ещё одна книга (Б) составляла вторую группу. Мы заметили, что для вычисления числа перестановок с повторениями надо общее число перестановок делить на количество дублирующих перестановок. Формула в общем случае выглядит так:
Пример. Вася решил, что ему стоит изучать только два иностранных языка. Он решил 4 дня в неделю тратить на английский, а оставшиеся три дня – на испанский. Сколько расписаний занятий он может себе составить.
Решение. Вася должен расставить 3 урока испанского и 4 урока английского, тогда n1 = 3, а n2 = 4. Общее количество уроков равно 3 + 4 = 7. Тогда
Обратите внимание, что для удобства при делении факториалов мы не вычисляли их сразу, а пытались сократить множители. Так как в ответе любой комбинаторной задачи получается целое число, то весь знаменатель дроби обязательно сократится с какими-нибудь множителями в числителе.
Пример. У мамы есть 3 яблока, 2 банана и 1 апельсин. Эти фрукты она распределяет между 6 детьми. Сколькими способами она может это сделать, если каждый должен получить по фрукту?
Решение. Всего есть три группы фруктов. В первой находится 3 яблока, поэтому n1 = 3. Во второй группе 2 банана, поэтому n2 = 2. В третьей группе только 1 апельсин, поэтому nk = 1. Общее число фруктов равно 6. Используем формулу:
В знаменателе формулы для перестановок с повторениями мы записываем число объектов в каждой группе одинаковых предметов. Так, если переставляются 3 яблока, 2 банана и 1 апельсин, то в знаменателе мы пишем 3!•2!•1!. Но что будет, если в каждой группе будет находиться ровно один уникальный объект? Тогда мы запишем в знаменателе произведение единиц:
В итоге мы получили ту же формулу, что и для перестановок без повторов. Другими словами, перестановки без повтора могут рассматриваться просто как частный случай перестановок с повторами.
Размещения
Пусть в футбольном турнире участвуют 6 команд. Нам предлагают угадать те команды, которые займут призовые места (то есть первые три места). Сколько вариантов таких троек существует?
Сначала запишем ту команду, которая выиграет турнир. Здесь есть шесть вариантов, по количеству участвующих команд. Запишем эти варианты:
Далее выберем один из вариантов и для него укажем серебряного призера соревнований. Здесь есть только 5 вариантов, ведь 1 из 6 команд уже записана на 1-ом месте:
В данном случае из некоторого множества команд мы выбрали несколько и расположили их в каком-то порядке. То есть мы выбрали упорядоченное множество. В комбинаторике оно называется размещением.
Если общее число команд обозначить как n (в этом примере n = 6), а количество упорядочиваемых команд равно k, то количество таких размещений в комбинаторике обозначается как
В примере с командами количество размещений равнялось 120:
Для нахождения этого числа мы перемножили k (3)множителей. Первый из них был равен n(6), так как каждая из n команд могла занять первая место. Второй множитель был равен (n– 1), так как после определения чемпиона мы могли поставить на вторую позицию одну из (n– 1) команд. Третий множитель был равен (n– 2). По этой логике каждый следующий множитель будет меньше предыдущего на единицу. Например, чтобы вычислить число размещений из 7 по 4, надо перемножить 4 множителя, первый из которых равен 7, а каждый следующий меньше на 1:
Однако математически удобнее представлять это произведение как отношение двух факториалов. Для этого умножим количество размещений на дробь 3!/3!, равную единице. Естественно, число размещений из-за умножения на единицу не меняется:
Число 3 в данном случае можно получить, если из 7 вычесть 4. В общем случае из числа n надо вычесть число k. Тогда формула для вычисления количества размещений примет вид:
Решение. Для составления расписания нужно выбрать 5 предметов и расставить их по порядку. Поэтому нам необходимо найти размещение из 12 по 5:
Пример. В вагоне 10 свободных мест. В него зашло 6 пассажиров. Сколькими способами они могут расположиться в вагоне?
Решение. Из десяти мест надо выбрать шесть и указать для каждого, какому пассажиру оно соответствует. То есть каждый вариант рассадки пассажиров – это размещение из 10 по 6. Найдем их количество:
Заметим, что перестановка – это частный случай размещения, когда k = n. Действительно, если нам надо указать тройку призеров турнира, в котором участвуют 6 команд, то мы указываем размещение из 6 по 3. Но если мы указываем для каждой из 6 команд, какое место она займет в чемпионате, то это размещение из 6 по 6. С другой стороны, это расстановка одновременно является и перестановкой 6 команд. Убедимся, что в этом частном случае формула для подсчета количества размещений покажет тот же результат, что и формула для перестановок
Для примера с 6 командами это будет выглядеть так:
Здесь мы использовали тот факт, что факториал нуля принимается равным единице. Данное рассуждение можно, наоборот, использовать для того, чтобы доказать, что факториал нуля – это единица.
Сочетания
Однако порою этот порядок не имеет значения. Так, существует известная лотерея, где предлагается угадать 7 чисел из 49, которые выпадут во время розыгрыша из барабана. При этом порядок их выпадения не играет никакой роли. Игрок, выбирая эти 7 чисел, с точки зрения математики формирует сочетание из 49 по 7.
Количество возможных сочетаний из n по k обозначается буквой С:
Для вычисления количеств сочетаний из n по k сначала найдем количество аналогичных размещений. Оно вычисляется по формуле:
Однако ясно, что, как и в случае с перестановками с повторениями, некоторые сочетания мы посчитали несколько раз. Вернемся к примеру с командами. Если мы выбрали команды Л (Локомотив) , З (Зенит) и К (Краснодар), то мы можем составить ровно 3! = 6 размещений из них:
Однако все они соответствуют только одному сочетании – ЛКЗ. Таким образом, считая количество размещений, мы посчитали каждое сочетание не один, а 3! раз. Поэтому для нахождения количества сочетаний в комбинаторике надо поделить число размещений на число перестановок k элементов:
Эта формула связывает важнейшие понятия комбинаторики – перестановки, сочетания и размещения. Подставим в неё формулы для размещений и перестановок и получим:
Пример. Сколько троек призеров турнира можно составить, выбирая три футбольные команды из шести?
Решение. Посчитаем число сочетаний из 6 по 3:
Решение. В каждом из этих случаев игрок выбирает сочетание нескольких чисел. Посчитаем их число:
Ответ: 376992; 8145060; 85900584
Пример. На плоскости отмечены 8 точек, причем никакие три из них не лежат на одной прямой. Сколько различных прямых можно провести через них? Сколько треугольников и четырехугольников можно построить с вершинами в этих точках?
Решение. Для того чтобы провести прямую, достаточно выбрать любые 2 точки из 8. Общее количество прямых будет равно числу сочетаний из 8 по 2:
Заметим принципиальную важность того условия, что никакие три точки не лежат на одной прямой. Оно гарантирует, что при выборе двух различных точек мы будем получать различные прямые. Если бы, например, точки АВС лежали бы на одной прямой, то при выборе сочетаний АВ, ВС и АС мы получали бы одну и ту же прямую:
Это же условие гарантирует, что, выбрав любые 3 и 8 точек, мы сможем построить треугольник с вершинами в этих точках, а выбрав 4 точки, получим четырехугольник. Поэтому для подсчета количества треугольников и четырехугольников следует искать число сочетаний по 3 и 4:
Ответ: 28 прямых, 56 треугольников и 70 четырехугольников.
Пример. В одной урне находится 10 различных шаров с номерами от 0 до 9, а в другой – 8 различных шаров с первыми восемью буквами алфавита. По условиям лотереи ведущий вытаскивает из первой урны два шара с числами, а из второй – три шара с буквами. Для победы в лотерее надо угадать выпавшие шары. Сколько комбинаций шаров может выпасть в игре?
Решение. Посчитаем отдельно, сколькими способами можно выбрать 2 шара с цифрами из 10 и 3 шара с буквами из 8:
По правилу умножения мы должны перемножить эти числа, чтобы найти общее количество возможных вариантов:
Заметим, что выбирая, например, сочетание из 49 по 7, мы одновременно выбираем и сочетание из 49 по 49 – 7 = 42. Действительно, игрок, обводящий в кружок в лотерейном билете свои 7 счастливых чисел, одновременно и определяет остальные 42 числа, какие числа он НЕ считает счастливыми. Для наглядности запишем число сочетаний в обоих случаях:
Получили одну и ту же дробь, в которой отличается лишь последовательность множителей в знаменателе. Можно показать, что и в общем случае число сочетаний из n по k совпадает с количеством сочетаний из n по (n– k):
1. Сколько существует способов избрания председателя профкома, заместителя, секретаря и
казначея среди членов профкома, включающего 8 студентов последнего курса, 12 студентов
предпоследнего курса, 13 второкурсников и 10 первокурсников, если:
а) отсутствуют какие-либо ограничения,
б) председателем профкома должен быть студент последнего курса,
в) студент последнего курса не может быть заместителем,
г) первокурсники могут быть избраны только на должность секретаря.
2. Сколькими способами можно рассадить класс, если присутствует 26 человек, а мест 28?
3. Сколькими способами можно вытянуть 4 карт пиковой масти из колоды, содержащей 52
карты?
4. Сколько трехзначных чисел можно составить из цифр 2, 4, 6 так, чтобы цифры в записи числа
не повторялись?
5. В кухне 5 лампочек с отдельными выключателями. Сколько существует способов освещения?
6. Сколькими способами можно расставить на полке 10 книг, включающих 3 одинаковых
учебника по математике, 4 одинаковых учебников по информатике, 3 одинаковых учебника по
биологии?
7. Автомобильные номера состоят из трех букв, за которыми идут 4 цифры, например
МКМ-07-37.Сколько машин можно снабдить различными номерами, если используется 25 букв?
1. Всех студентов - 43. Выбираем 4 человека.
а) С (43,4)
б) Выбираем председателя среди 8 студентов: C(8,1)
а остальных 3 среди 42 чел. : C(42,3). Следовательно, получаем С (8,1)С (42,3) возможных выборов.
в) Заместителя выбираем среди 35 студ. , а остальных 3 среди 42 студентов: С (35,1)С (42,3)
г) Таким же образом: С (33,3)*С (40,1)
2. Первый человек может выбрать место среди 28 свободных мест. Второй - среди 27 (одно место уже занято) . третий - среди 26 и. т. д. Получаем 28* 27*26*. * 4*3 способов. Другими словами: С (28,26)* 26!
4. Цифру сотен можем выбрать 3 способами. Цифру десятков - двумя (цифры не могут повторяться) , а цифру единиц - одним способом. Поэтому получаем 3*2*1 способов.
5. Можем зажечь:
одну лампочку С (5,1)=5 способами.
две - С (5,2) способами
три - С (5,3) способами
четыре - С (5,4) способами
пять С (5,5) =1 способом.
Следовательно, существует С (5,1) + С (5,2) + С (5,3) + С (5,4) + С (5,5) способов освещения.
6. 10 РАЗНЫХ книг можно расставить 10! способами. Но так как у нас 3, 4 и 3 одинаковые книги, то получаем
7. Среди 25 выбираем 3: С (25,3) способов
А среди 10 цифр выбираем 4 цифры: С (10,4) способов.
Подборка задач по комбинаторике (с ответами) для 11 класса.
Задачи по комбинаторики
Задача 1: Сколькими способами можно составить список из 5 учеников?
Ответ: перестановки, 5! = 120.
Задача 2: В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?
Ответ: размещения из 11 по 2, А 2 11= 110.
Задача 3: Расписание на день содержит 5 уроков. Определить количество возможных расписаний при выборе из 14 предметов, при условии, что ни один предмет не стоит дважды.
Ответ: размещения из 14 по 5, 1320.
Задача 4: Сколько различных трехцветных флагов можно сделать, комбинируя синий, красный и белый цвета?
Ответ: перестановки, 6 способов.
Задача 5: В классе 24 ученика. Сколькими способами можно сформировать команду из 4 человек для участия в математической олимпиаде?
Ответ: сочетания из 24 по 4,
Задача 6: Сколько трехзначных чисел можно составить из цифр 1, 2, 3, если каждая цифра входит в изображение числа только 1 раз?
Ответ: перестановки, 6 способов.
Задача 7: Сколькими различными способами можно избрать из 15 человек делегацию в составе 3 человек?
Ответ: сочетания, 455 способами.
Задача 8: Из ящика, где находится 15 шаров, нумерованных последовательно от 1 до 15, требуется вынуть 3 шара. Определить число возможных комбинаций при этом?
Ответ: размещения, 2830 способами.
Задача 9: Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, если каждая цифра входит в изображение числа только 1 раз?
Ответ: перестановки, 4! – 3! =18.
Задача 10: Сколькими способами можно разместить 6 пассажиров в четырехместной каюте?
Ответ: размещения из 6 элементов по 4, 360 способами.
Задача 11: Сколькими способами можно выбрать 2 детали из ящика, содержащего 10 деталей?
Ответ: сочетания из 10 элементов по 2, 45 способами.
Ответ: сочетания из 13 по 4, 715 бригад.
Задача 13: При встрече 16 человек обменялись рукопожатиями. Сколько всего было сделано рукопожатий?
Ответ: сочетания из 16 по 2, 120 рукопожатий.
Задача 14: Группа учащихся в 30 человек пожелала обменяться своими фотокарточками. Сколько всего фотокарточек потребовалось для этого?
Ответ: сочетание из 30 по 2, 435 фотокарточек.
Задача 15: Сколько различных плоскостей можно провести через 10 точек, если никакие три из них не лежат на одной прямой и никакие четыре точки не лежат в одной плоскости?
Ответ: сочетание из 10 по 3; 120 точек
Задача 16: Сколько существует различных семизначных телефонных номеров?
Ответ: 10 7 .
Задача 17: Сколько существует различных семизначных телефонных номеров, если в каждом номере нет повторяющихся цифр?
Ответ: размещение из 10 по 7.
Задача 18: Сколько существует таких перестановок 7 учеников, при которых 3 определенных ученика находятся рядом друг с другом? Ответ: 720 = 3! · 5!
Задача 19: На книжной полке стоит собрание сочинений в 30 томах. Сколькими различными способами их можно переставить, чтобы: а) тома 1 и 2 стояли рядом; б) тома 3 и 4 рядом не стояли?
Ответ: а)2∙29!; б)28∙29!
Задача 20: Сколько существует трёхзначных чисел, все цифры которых нечётные и различные?
Ответ: размещение из 5 по 3, 60.
Задача 21: У одного мальчика имеется 10 марок для обмена, а у другого – 8. Сколькими способами они могут обменять 2 марки одного на 2 марки другого?
лишишься”. С какой проблемой сталкивается добрый молодец на перепутье?
Конечно, с проблемой выбора дальнейшего пути движения.
А дальше уже говорится, как он выходит из
того положения, в которое попал в результате
выбора. Но выбирать разные пути или варианты
приходится и современному человеку. Это сделать
очень трудно не потому, что его нет или оно одно и
поэтому его трудно найти, а приходится выбирать
из множества возможных вариантов, различных
способов, комбинаций. И нам всегда хочется, чтобы этот выбор был наилучшим.
Оказывается, существует целый раздел математики, именуемый
есть комбинаций в том или ином случае, как из всех этих комбинаций выбрать
Комбинаторика позволяет ответить на вопросы: сколькими
происходит от латинского слова combinare, которое означает «соединять,
Можно научить маленького человека считать, как счетная машина,
проштудировать с ним горы энциклопедий. И это будет только
определѐнное количество информации, которой ребенок не сумеет
воспользоваться. Гораздо важнее воспитать его мышление так, чтобы он
сам сумел находить и отбирать нужную информацию. Вот комбинаторика
и формирует такие качества мышления, как системность, вариативность,
гибкость. Все эти качества характеризуют комбинаторный стиль
В науке и практике часто встречаются задачи, решая которые
приходится составлять различные комбинации, подчинѐнные тем или
другим условиям, из заданных объектов и подсчитывать число
комбинаций. Такие задачи получили название комбинаторных задач.
Решение комбинаторных задач таит в себе большие развивающие
возможности: на их основе совершенствуются приемы умственной
деятельности, формируется важная для человека способность
комбинировать. Задачи по комбинаторике включают в математические
олимпиады и конкурсы.
Комбинаторика возникла в XVI веке и первоначально в ней
рассматривались комбинаторные задачи, связанные в основном с
азартными играми. В карты и кости выигрывались золото и
бриллианты, дворцы, породистые кони и дорогие украшения.
Широко были распространены всевозможные лотереи. Одним из
первых занялся подсчетом числа возможных комбинаций при игре в
кости итальянский математик Тарталья. Он составил таблицу,
показывающую, сколькими способами могут выпасть r костей. Однако
при этом не учитывалось, что одна и та же сумма очков может быть
получена разными способами.
Вот одна из комбинаторных задач: У кассы кинотеатра стоят четверо
ребят. У двух из них сторублевые купюры, у двух других– пятидесятирублевые.
Билет в кино стоит 50 рублей. В начале продажи касса пуста. Как должны
расположиться ребята, чтобы никому не пришлось ждать сдачи?
Можно найти два варианта решения:
1) 50 рублей, 100 рублей, 50 рублей, 100 рублей;
2) 50 рублей, 50 рублей, 100 рублей, 100 рублей.
При решении комбинаторных задач можно использовать разные методы.
2. Методы решения комбинаторных задач:
метод перебора (подбираются задачи на развитие мышления);
табличный метод (все условия вносятся в таблицу, в ней же
построение дерева возможных вариантов решений;
построение граф - схемы.
2.1. Метод перебора возможных вариантов
Простые задачи решают обыкновенным полным перебором
возможных вариантов без составления различных таблиц и схем.
Способ перебора может применяться в простых задачах, например в
Задача 1. Для своих двух книг Маша купила три разные обложки.
Сколькими различными способами она может обернуть книги
Ответ: Для решения обозначим обложки буквами а, б, в. Составим из букв
всевозможные пары: аб, ав, бв, ба, ва, вб. Всего получилось 6 способов.
Какие двузначные числа можно составить из цифр 1, 2, 3, 4, 5?
Ответ: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43,
44, 45, 51, 52, 53, 54, 55.
В финальном забеге на 100 м участвуют Иванов, Громов и Орлов.
Назовите возможные варианты распределения призовых мест.
Вариант1: 1) Иванов, 2) Громов, 3) Орлов.
Вариант2: 1) Иванов, 2) Орлов, 3) Громов.
Вариант3: 1) Орлов, 2) Иванов, 3) Громов.
Вариант4: 1) Орлов, 2) Громов, 3) Иванов.
Вариант5: 1) Громов, 2) Орлов, 3) Иванов.
Вариант6: 1) Громов, 2) Иванов, 3) Орлов.
В кружок бального танца записались Петя, Коля, Витя, Олег, Таня, Оля,
Наташа, Света. Какие танцевальные пары девочки и мальчика могут
1) Таня - Петя, 2) Таня - Коля, 3) Таня - Витя, 4) Таня - Олег, 5) Оля -
Петя, 6) Оля - Коля, 7) Оля - Витя, 8) Оля - Олег, 9) Наташа - Петя, 10)
Наташа - Коля, 11) Наташа - Витя, 12) Наташа - Олег, 13) Света - Петя,
14) Света - Коля, 15) Света - Витя, 16) Света - Олег.
А теперь рассмотрим варианты организованного перебора.
2.2. Табличный метод
Решить комбинаторные задачи можно с помощью таблиц. Они, как
и дерево возможных вариантов, наглядно представляют решение таких
Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4,
Решение. Составим таблицу: слева первый столбец - первые цифры
искомых чисел, вверху первая строка - вторые цифры.
Маша, Оля, Вера, Ира, Андрей, Миша и Игорь готовились стать
ведущими на Новогоднем празднике. Назовите возможные варианты,
если ведущими могут быть только одна девочка и один мальчик.
Решение. Составим таблицу: слева первый столбец - имена девочек,
вверху первая строка - имена мальчиков.
Андрей Миша Игорь
Маша Маша - Андрей Маша - Миша Маша - Игорь
Оля Оля - Андрей Оля - Миша Оля - Игорь
Вера Вера - Андрей Вера - Миша Вера - Игорь
Ира Ира - Андрей Ира - Миша Ира - Игорь
Ответ: Все возможные варианты перечисляются в строках и столбцах
таблицы. Всего 12 вариантов.
Задача 3. В школьной столовой приготовили на завтрак плов (П),
кашу (К), блины (Б), а из напитков – сок (С), чай (Ч) и молоко (М).
сколько различных вариантов завтрака можно составить?
Ответ: 9 вариантов.
2.3. Метод построения дерева возможных вариантов
Подбирая различные комбинации, можно запутаться. В этом случае
приходит на помощь метод построения дерева возможных вариантов
решений. Внешне такая схема напоминает дерево, отсюда и название.
Если его правильно построить, ты не упустишь ни один из возможных
Рассмотрим задачу 1. Учитель попросил Олега разложить на полке
3 волшебных шара - жѐлтый, красный, синий. Сколькими способами Олег
может это сделать?
Начать можно и с жѐлтого, и с красного, и с синего шара. Дерево
вариантов будет выглядеть так:
Эта схема действительно похожа на дерево, правда, "вверх ногами" и
без ствола. Каждый первый шар - это "корень" дерева, а ветви дерева - это
различные варианты расположения шаров. По этой схеме несложно
посчитать, что возможных комбинаций всего 6.
Схему-дерево возможных рассуждений можно располагать поразному (корень вверху или внизу).
Задача 2. Катя собирается на каникулы. Она может поехать с бабушкой
или с родителями. Если Катя поедет с бабушкой, то она сможет провести
каникулы или на даче, или в городе, или в деревне. Если она поедет с
родителями, то она сможет провести каникулы или отдыхая в санатории,
или путешествия по горам, или путешествуя на теплоходе. Сколько
разных вариантов есть у Кати, чтобы провести свои каникулы?
ВСЕГО: 6 вариантов
2.4. Метод построения граф-схемы
Все видели схему станций метрополитена, трамвайных путей или карту
ДАЧА ГОРОД ДЕРЕВНЯ САНАТОРИЙ ГОРЫ ТЕПЛОХОД
которые их соединяют — железнодорожные пути. Такие схемы и
Итак, если произвольные точки пространства соединены между
собой отрезками или дугами (не обязательно все), то такое
соединение (схема) называется графом.
Граф — это набор точек, некоторые из которых соединены линиями.
Эти точки называются вершинами. Соединяющие их линии называются
Граф - это геометрическая фигура, состоящая из точек
(вершины графа) и линий, их соединяющих (рѐбра графа).
При этом с помощью вершин изображают элементы некоторого
множества (предметов, людей и т.д.), а с помощью рѐбер - определѐнные
связи между элементами. Для удобства иллюстрации условия задачи,
вершины графа могут быть заменены кругами или прямоугольниками.
Задача 1. В парке 4 пруда. Было решено засыпать песком дорожки между
ними так, чтобы можно было пройти от одного пруда к другому
кратчайшим путем, т.е. не нужно было идти в обход. Задание: покажи,
какие дорожки надо сделать.
Это пример полного графа Ответ: 6 дорожек
Задача 2. Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый
сыграл с каждым по одной партии. Сколько партий было сыграно?
Ответ: сыграно 6 партий
Задача 3. Вася, Коля, Петя, Аня и Наташа - лучшие лыжники в пятом классе.
Для участия в соревнованиях нужно выбрать из них одного мальчика и
одну девочку. Сколькими способами это можно сделать?
Решение: Эту задачу можно решить с помощью следующей схемы.
Ответ: 6 способов.
Итак, комбинаторика изучает, сколько различных комбинаций можно
составить из данных объектов по определѐнным правилам.
3. ТИПЫ КОМБИНАТОРНЫХ ЗАДАЧ
Комбинаторные задачи бывают трѐх типов. Давайте рассмотрим первый
Рассмотрим решение задач.
Задача 1. На столе лежат яблоко, груша и банан.. Выкладываем
фрукты слева направо в следующем порядке:
яблоко / груша / банан
Вопрос первый: сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не
яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко
Итого: 6 комбинаций или 6 перестановок.
Задача 2. Имеются шары. Их всего 3 - жѐлтый, красный и синий. Олег
должен разложить их на полке всеми возможными способами. Ответ
Составляя комбинации, мы учитывали порядок шаров. И на первое,
и на второе, и на третье место мы могли положить любой шар. Отсюда и
такое разнообразие вариантов. Если в комбинациях участвуют все
объекты и важен их порядок - речь идѐт о перестановках.
При сочетаниях комбинаций, как правило, получается меньше, чем при
перестановках и размещениях. Почему? Дело в том, что порядок
элементов не важен, да и в комбинациях участвуют не все элементы.
Давайте снова рассмотрим конкретный пример.
На полке лежат три волшебных шара - жѐлтый, красный, синий. Учитель
попросил Олега принести ему два шара. Сколькими способами Олег
может это сделать?
Например, Олег возьмѐт жѐлтый и красный шары:
А так ли важно, жѐлтый и красный или красный и жѐлтый? Это как при
перемене мест слагаемых - сумма же не меняется. Всѐ равно Олег
принесѐт именно эти шары учителю и не возьмѐт синий. Порядок шаров
не имеет значения.
Оставшиеся способы выглядят так:
При сочетаниях нам не важен порядок элементов. Запомни эту
Задача 1. Из цифр 1,2,3,4,5,6 составить все возможные трехзначные числа.
При этом мы должны рассмотреть случаи:
1) когда цифры в записи числа повторяются
2) когда цифры в записи числа не повторяются.
Рассмотрим первый случай, когда цифры повторяются (размещение с
повторением). Сколько цифр претендует на первое место? На второе
место? На третье?
Отметим место каждой цифры
Рассмотрим второй случай, когда цифры не повторяются (размещение
без повторения). Сколько цифр претендует на первое место? На второе
место? На третье?
Отметим место каждой цифры
Задача 2. Сколько двузначных чисел можно получить из цифр 0, 1, 2, 3
при условии, что цифры в записи числа не повторяются?
Решение: На первом месте могут стоять цифры 1, 2, 3. Тогда на втором
месте в каждом случае могут стоять 3 цифры. Всего получаем 9 чисел: 10,
12, 13, 20, 21, 23, 30, 31, 32.
Размещением называется расположение ―предметов‖ на некоторых
―местах‖ при условии, что каждое место занято в точности одним
предметом и все предметы различны.
В размещении учитывается порядок следования предметов. Так,
например, наборы (2,1,3) и (3,2,1) являются различными.
В этом типе задач комбинации составляют не из всех элементов, а только
из некоторых. Но обязательно важен их порядок.
Снова наша задача с шарами, только теперь Учитель попросил Олега
один шар отнести Юре, а другой — Алисе. Сколькими способами Олег
может это сделать?
Можем изобразить комбинации вот так:
Или построить дерево вариантов, ведь мы уже научились это делать.
В этом задании каждый раз участвовало только 2 шара, а не 3. Но при
этом был важен их порядок.
В размещениях всегда участвует только часть элементов, но важен их
4.ОСНОВНЫЕ КОМБИНАТОРНЫЕ ПРИНЦИПЫ
Иногда подсчитать комбинации в задачах можно быстро и легко. Для
этого используются правило суммы и правило произведения.
Правило суммы и правило произведения — основные комбинаторные
принципы, которые используются в комбинаторике.
4.1. ПРАВИЛО СУММЫ
Обобщения рациональных приемов систематического перебора целесообразнее
начать с комбинаторных задач на правило суммы. Проиллюстрируем правило
суммы на элементарных задачах.
Задача 1. В вазе 4 яблока и 3 груши. Сколькими способами можно взять из
Что значит «взять 1 из фруктов? Это значит взять яблоко или грушу.
Сколькими способами можно взять 1 яблоко? Почему? (Четырьмя способами,
так как яблок всего 4 они разные).
Сколькими способами можно взять 1 грушу и почему? (Тремя способами, так
как груш всего 3 и они разные).
Сколькими способами можно взять один из фруктов?( Семью способами 7=4+3).
Ответ: 7 способов
Задача 2. На полке стоят десять томов Пушкина, четыре тома
Лермонтова и шесть томов Гоголя. Сколькими способами можно выбрать
с полки одну книгу?
Решение. Понятно, что 10 + 4 + 6 = 20 способами.
Задача 3. На подносе лежат 5 яблок и 3 груши. Сколькими способами
можно выбрать фрукт с подноса?
Решение. Яблоко можно выбрать пятью способами. Грушу можно
выбрать тремя способами.
Стало быть, один из этих фруктов можно выбрать 5 + 3 = 8 способами.
ЗАПОМНИТЕ! Правило суммы применяется, когда нужно
выбрать один предмет из нескольких различных множеств.
4.2. Правило произведения
При решении комбинаторных задач часто приходится умножать
число способов выбора одного объекта на число способов выбора другого
объекта. Рассмотрим некоторые примеры.
Задача 1. Имеются три города: A, B и C. Из A в B ведут три дороги,
из B в C — пять дорог. Сколько различных путей ведут из A в C? Прямого
пути между A и C нет.
Решение. Обозначим дороги буквами и цифрами. Именно, дороги из
A в B назовѐм a, b, c; дороги из B в C назовѐм 1, 2, 3, 4, 5.
Тогда любой маршрут из A в C получает уникальное имя в виде пары
из буквы и цифры. Например, маршрут b4 означает, что из A и B мы
пошли по дороге b, а из B в C — по дороге 4. Выпишем все такие пары в
виде таблицы: a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 c1 c2 c3 c4 c5
Всего получилось 3 · 5 = 15 маршрутов. Как видим, число маршрутов
равно произведению числа дорог из A в B на число дорог из B в C.
Заметим, что строить каждый раз дерево вариантов не обязательно.
Чтобы найти число комбинаций, достаточно перемножить
число предметов одного вида на количество предметов другого
вида. Это правило называется правилом произведения.
Правда, работает оно не всегда. Зато при перестановках смело его
Когда речь идѐт о выборе всех возможных вариантов, т.е. нет условий
и ограничений - перед нами задача на перестановку.
Задача 3. У Алисы есть 4 разных платья и 3 разных пары туфель.
Она собирается на вечеринку и думает, что ей надеть. Сколько у Алисы
Нам надо составить все возможные комбинации. В каждой из них
будут участвовать и платье, и туфли.
Предположим, платье Алиса выбрала. Тогда к нему она может
подобрать одну из 3-х пар туфель. Таким образом, есть 3 набора "платьетуфли" с этим первым платьем.
Читайте также: