Основы комбинаторики — перестановки, размещения, сочетания
Комбинаторика является важным разделом математики, который исследует закономерности расположения, упорядочения, выбора и распределения элементов с фиксированного множества.
При большом числе возможных последствий испытания способы прямого перебора возможных вариантов малоэффективны. На помощь приходят комбинаторные методы, в основе которых лежат два следующих правила.
ПРАВИЛО СУММИРОВАНИЯ
Если два взаимоисключающие действия могут быть выполнены в соответствии и способами, тогда какое-то одно из этих действий можно выполнить способами.
Пример 1. Из города А в город В можно добраться 12 поездами, 3 самолетами, 23 автобусами. Сколькими способами можно добраться из города А в город В?
Решение. Проезд из А в В на поезде, самолете или автобусе являются событиями, которые не могут выполняться одновременно одним человеком (взаимоисключающими), поэтому общее количество маршрутов можно вычислить суммированием способов передвижения
ПРАВИЛО ПРОИЗВЕДЕНИЯ
Пусть две выполняемые одно за другим действия могут быть осуществлены в соответствии и способами. Тогда обе они могут быть выполнены способами.
—————————-
Пример 2. В турнире принимают участие 8 хоккейных команд. Сколько существует способов распределить первое, второе и третье места?
Решение. Первое место займет одна из 8 команд, второе — одна из 7, третье — одна из 6, так как каждая из них не может претендовать одновременно на два призовых места. Поэтому таких способов будет ровно
Оба правила обобщаются на случай любого конечного количества действий. В комбинаторике различают три вида различных соединений (комбинаций) элементов фиксированной множества: перестановки, размещения, сочетания. Ниже будут даны их определения с обозначениями, которые наиболее употребительные
Перестановками из из элементов называются такие их совокупности, отличающихся друг от друга только порядком вхождения элементов. Их обозначают и определяют по формуле
— факториал числа , определяется по правилу
—————————-
Пример 3. Сколькими способами можно в детсадку поставить группу из 15 детей в ряд?
Решение. На первое место есть возможность поставить одного из 15 детей, на второе одного из 14 и т.д. Общее количество
Размещением из элементов по называются такие совокупности элементов, отличающихся друг от друга по крайней мере одним элементом или порядком их вхождения ():
—————————-
Пример 4. Сколько различных трехзначных чисел можно составить с помощью цифр от 1 до 9 ?
Решение. На первом месте есть возможность поставить одну из 9 цифр, на второе одного из 8 и т.д. Общее количество будет ровно
—————————-
Сочетаниями из элементов по называются такие комбинации из элементов, которые отличаются друг от друга по крайней мере одним элементом () :
Пример 5. Сколькими способами можно выбрать три цифры из девяти 1, 2, 3, …, 9?
Решение. Количество всех возможных способов определяем из формулы
—————————-
Приклад 6. Из одиннадцати букв азбуки составлено название украинской сказки «Котигорошок». Ребенок, не умеющий читать, рассыпал буквы, а затем собрал в произвольном порядке. Найти вероятность того, что он соберет слово «Котигорошок».
Решение. На здравый смысл получается, что такая вероятность равна нулю, однако это не так. Согласно теории, с одиннадцати букв можно составить различные буквосочетание, отличающиеся между собой только порядком букв, поэтому число всех возможных перестановок равно
Однако буквы «К» и «О» могут занимать одну из четырех, и одну из двух позиций соответственно, их можно переставлять. Поэтому число благоприятных событий равно
Искомая вероятность примет значение
—————————-
Хорошо разберитесь с приведенными примерами, которые показывают где применять на практике правило сложения, а где умножения; на их основе построен весь следующий материал. Впереди еще много нового следует изучить, здесь только основы теории вероятностей.
———————————————-
Social Like
Перестановка
Перестановка — это способ последовательно расположить составляющие множества. Например, 123, 312 и 213 — это перестановки трёх чисел: 1, 2 и 3.
Чтобы найти общее количество возможных перестановок, используют две формулы: для случаев с повторяющимися компонентами и без них. Давайте рассмотрим оба.
Перестановка без повторяющихся элементов
Если во множестве ни один элемент не повторяется, то используется следующая формула:
Пример: сколько перестановок символов можно составить из шести букв — q, w, e, r, t, y?
Решение: чтобы найти количество перестановок, нам нужно посчитать факториал числа 6 — то есть общего количества букв в наборе. Подставляем в формулу:
Перестановка с повторяющимися элементами
Если хотя бы один элемент во множестве повторяется, то используется следующая формула:
Формула выглядит довольно негуманно, поэтому объясним, в чём здесь логика. Сначала мы находим, сколько перестановок было бы, если бы все компоненты множества были разными. Потом мы делим это число на то, сколько раз можно переставить повторяющиеся элементы между собой. Это нужно, чтобы не считать одинаковые перестановки несколько раз. Дальше мы посмотрим на пример, чтобы лучше разобраться.
Пример. Допустим, у нас есть набор из восьми букв: p, a, s, s, w, o, r, d. Сколько всего перестановок символов можно составить из этих букв?
Решение. Видим, что буква s в этом наборе повторяется дважды. Значит, n = 8 и n1 = 2. Подставляем эти значения в формулу и получаем:
Сочетания
Выбирая размещение, мы должны были выбрать из множества несколько объектов и упорядочить их. В частности, мы выбирали три команды из шести и указывали, какая из них будет первой, какая второй, а какая третьей. Поэтому размещения «Локомотив, Зенит, Краснодар» и «Локомотив, Краснодар, Зенит» отличались друг от друга.
Однако порою этот порядок не имеет значения. Так, существует известная лотерея, где предлагается угадать 7 чисел из 49, которые выпадут во время розыгрыша из барабана. При этом порядок их выпадения не играет никакой роли. Игрок, выбирая эти 7 чисел, с точки зрения математики формирует сочетание из 49 по 7.
Количество возможных сочетаний из n по k обозначается буквой С:
Для вычисления количеств сочетаний из n по k сначала найдем количество аналогичных размещений. Оно вычисляется по формуле:
Однако ясно, что, как и в случае с перестановками с повторениями, некоторые сочетания мы посчитали несколько раз. Вернемся к примеру с командами. Если мы выбрали команды Л (Локомотив) , З (Зенит) и К (Краснодар), то мы можем составить ровно 3! = 6 размещений из них:
ЛЗК
ЛКЗ
ЗЛК
ЗКЛ
КЛЗ
КЗЛ
Однако все они соответствуют только одному сочетании – ЛКЗ. Таким образом, считая количество размещений, мы посчитали каждое сочетание не один, а 3! раз. Поэтому для нахождения количества сочетаний в комбинаторике надо поделить число размещений на число перестановок k элементов:
Эта формула связывает важнейшие понятия комбинаторики – перестановки, сочетания и размещения. Подставим в неё формулы для размещений и перестановок и получим:
Пример. Сколько троек призеров турнира можно составить, выбирая три футбольные команды из шести?
Решение. Посчитаем число сочетаний из 6 по 3:
Ответ: 20
Пример. Сколько комбинаций чисел может составить игрок, играющий в лотереи «5 из 36», «6 из 45», «7 из 49»?
Решение. В каждом из этих случаев игрок выбирает сочетание нескольких чисел. Посчитаем их число:
Ответ: 376992; 8145060; 85900584
Пример. На плоскости отмечены 8 точек, причем никакие три из них не лежат на одной прямой. Сколько различных прямых можно провести через них? Сколько треугольников и четырехугольников можно построить с вершинами в этих точках?
Решение. Для того чтобы провести прямую, достаточно выбрать любые 2 точки из 8. Общее количество прямых будет равно числу сочетаний из 8 по 2:
Заметим принципиальную важность того условия, что никакие три точки не лежат на одной прямой. Оно гарантирует, что при выборе двух различных точек мы будем получать различные прямые
Если бы, например, точки АВС лежали бы на одной прямой, то при выборе сочетаний АВ, ВС и АС мы получали бы одну и ту же прямую:
Это же условие гарантирует, что, выбрав любые 3 и 8 точек, мы сможем построить треугольник с вершинами в этих точках, а выбрав 4 точки, получим четырехугольник. Поэтому для подсчета количества треугольников и четырехугольников следует искать число сочетаний по 3 и 4:
Ответ: 28 прямых, 56 треугольников и 70 четырехугольников.
Пример. В одной урне находится 10 различных шаров с номерами от 0 до 9, а в другой – 8 различных шаров с первыми восемью буквами алфавита. По условиям лотереи ведущий вытаскивает из первой урны два шара с числами, а из второй – три шара с буквами. Для победы в лотерее надо угадать выпавшие шары. Сколько комбинаций шаров может выпасть в игре?
Решение. Посчитаем отдельно, сколькими способами можно выбрать 2 шара с цифрами из 10 и 3 шара с буквами из 8:
По правилу умножения мы должны перемножить эти числа, чтобы найти общее количество возможных вариантов:
56•45 = 2520
Ответ: 2520
Заметим, что выбирая, например, сочетание из 49 по 7, мы одновременно выбираем и сочетание из 49 по 49 – 7 = 42. Действительно, игрок, обводящий в кружок в лотерейном билете свои 7 счастливых чисел, одновременно и определяет остальные 42 числа, какие числа он НЕ считает счастливыми. Для наглядности запишем число сочетаний в обоих случаях:
Получили одну и ту же дробь, в которой отличается лишь последовательность множителей в знаменателе. Можно показать, что и в общем случае число сочетаний из n по k совпадает с количеством сочетаний из n по (n– k):
Размещение
Размещение — это способ выбрать и упорядочить элементы из множества. В отличие от операции сочетания, при размещении важен порядок составляющих множества.
Вопрос размещения: сколько упорядоченных наборов можно сделать из k элементов, выбранных из n?
Размещение без повторяющихся элементов
Если во множестве n ни один элемент не повторяется, то используется следующая формула:
Пример. В лототроне находится 90 шаров с номерами от 10 до 99. Ведущий последовательно достаёт три шара и кладёт их рядом так, чтобы получилось шестизначное число. Сколько вариантов шестизначных чисел может получиться?
Решение. Ведущий выбирает и упорядочивает 3 шара из 90. Подставляем числа в формулу выше и смотрим на результат:
Размещение с повторяющимися элементами
Если во множестве n один и тот же элемент можно взять несколько раз, то используется следующая формула:
Пример. В начале статьи мы писали о восьмисимвольном пароле, состоящем из латинских букв (заглавных и строчных) и цифр от нуля до девяти. Любой символ может использоваться сколько угодно раз. Сколько всего таких паролей можно составить?
Решение. Букв в латинском алфавите 26, следовательно, в пароле можно использовать 26 * 2 = 52 буквенных символа (26 для заглавных и 26 для строчных). Цифр от нуля до девяти — 10. В итоге получаем множество из 62 составляющие.
Комбинации вокруг нас
Задумайтесь, а как часто в повседневной жизни вы занимаетесь комбинированием, то есть составлением комбинаций из чего-либо?
Это вопрос с подвохом.
В такой формулировке возникает соблазн ответить «редко» или даже «никогда».
Но стоит лишь копнуть глубже и окажется, что все мы каждый день:
-
Прикидываем комбинации дел и задач, занимаясь планированием.
-
Пишем комбинации букв, получая слова.
-
Набираем комбинации цифр, чтобы кому-нибудь позвонить.
-
Выстраиваем комбинации мыслей, образуя рассуждения.
Выходит, что мы постоянно составляем комбинации, то есть наборы из самых разных объектов: задач, букв, цифр и даже мыслей!
Комбинации повсюду!
Лекция 2. Перестановки, сочетания, размещения
Пусть имеется n различных объектов. Будем переставлять их всеми различными способами ( число и состав объектов остается неизменным, меняется только порядок). Получившиеся комбинации называются перестановками, а их число равно
Символ называется факториалом и обозначает произведение всех целых чисел от 1 до n. По определению считают, что , . Факториал растет очень быстро (недаром он обозначается восклицательным знаком !), например:
Пример: Сколько способов рассадить шестерых гостей на шести стульях?
Решение.
Перестановки с повторениями
Задача1. Сколько различных “слов” можно получить, переставляя буквы слова “передача” ?
В этом слове буквы “е” и “а” встречаются два раза, остальные по одному разу. Речь идет о перестановке с повторением состава (2,2,1,1,1,1) длины n равно 2+2+1+1+1+1=8. Количество таких равно
Сочетания
В сочетанием из по называется набор элементов, выбранных из данных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Пусть имеется различных объектов
Чтобы найти число сочетаний из объектов по , будем выбирать комбинации из объектов всеми возможными способами, при этом будем обращать внимание на разный состав комбинаций, но не порядок (он тут не важен). Например, есть три объекта {1,2,3}, составляем сочетания по 2 объекта в каждом
Тогда {1,2} и {2,1} — это одно и то же сочетание (так как комбинации отличаются лишь порядком). А всего различных сочетаний из 3 объектов по 2 будет три: {1,2}, {1,3}, {2,3}.
На картинке наглядно проиллюстрировано получение всех возможных сочетаний из 4 различных объектов по 2
Формула для нахождения числа сочетаний имеет вид
Задача2. Сколько существует способов назначить двоих дежурных из семи человек?
Решение.
Сочетания с повторениями – это комбинации, составленные из различных элементов по элементов, среди которых встречаются одинаковые. Комбинации отличаются хотя бы одним элементом. Формула для вычисления числа сочетаний с повторениями:
Задача3. В кондитерском магазине продается 4 сорта пирожных: наполеон, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Решение.
Пусть имеется различных объектов.
Будем выбирать из них объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из объектов по , а их число равно
Чтобы найти размещения, надо взять все возможные сочетания, а потом в каждом еще поменять порядок всеми возможными способами (то есть фактически сделать еще перестановки). Поэтому число размещений еще выражается через число перестановок и сочетаний так:
Задача4. В группе туристов 9 человек. Сколько существует способов распределить между ними обязанности командира, его заместителя и кашевара?
Решение.
Если n различных элементов могут повториться m раз, оказавшись соответственно на m местах, то число размещений с повторениями вычисляется по формуле
Задача5. Сколько трехзначных чисел можно записать, используя любые цифры из набора 1,2,3,4,5?
Решение.
Основные элементы комбинаторики
Размещения
Это любое упорядоченное подмножество из элементов множества .
(Порядок важен).
Типичная смысловая нагрузка: сколькими способами можно выбрать объектов (из объектов) и в каждой переставить их местами (либо распределить между ними какие-нибудь уникальные атрибуты)?
Перестановки
Если , то эти размещения называются перестановками.
Типичная смысловая нагрузка: сколькими способами можно переставить nобъектов?
Сочетания
Это любое подмножество из элементов, которые принадлежат множеству, состоящему из различных элементов.
(Порядок не важен)
Типичная смысловая нагрузка: сколькими способами можно выбрать объектов из ?
Соединения с повторениями
1) Перестановки с повторениями
2) Сочетания с повторениями:
3) Размещения с повторениями:
Число размещений — это …
число способов переставить объектовчисло способов выбрать объектов из число способов выбрать объектов из и в каждой выборке переставить их местами
Формула для нахождения числа сочетаний:
Сколько существует способов рассадить четырех гостей на четыре стула?
81624120
В оперном театре 10 певцов и 8 певиц. В постановке участвуют три мужских голоса и два женских. Сколько существует способов распределить их роли между актерами?
1880336040320
В оперном театре 10 певцов и 8 певиц. В постановке участвуют три мужских голоса и два женских. Сколько существует способов выбрать актеров для постановки?
1880336040320
Основные принципы комбинаторики
Существует несколько основных принципов в комбинаторике, которые помогают нам решать различные задачи. Рассмотрим некоторые из них:
- Принцип умножения: Этот принцип утверждает, что если у нас есть несколько независимых выборов, то общее количество возможных вариантов будет равно произведению количеств выборов в каждом из них. Например, если у нас есть 3 различных футбольных формы и 4 различных футбольных шорт, то мы можем составить 3 * 4 = 12 различных комбинаций.
- Принцип сложения: Этот принцип утверждает, что если у нас есть несколько взаимоисключающих выборов, то общее количество возможных вариантов будет равно сумме количеств выборов в каждом из них. Например, если у нас есть 2 различных пути для достижения цели, то общее количество возможных вариантов будет равно 2 + 2 = 4.
- Принцип включения-исключения: Этот принцип утверждает, что для определения общего количества элементов в объединении нескольких множеств необходимо учесть количество элементов каждого множества, вычесть количество элементов, входящих в пересечение множеств, и добавить количество элементов, входящих в пересечение всех множеств. Например, если у нас есть 3 множества A, B и C, то количество элементов в их объединении будет равно |A| + |B| + |C| — |A∩B| — |A∩C| — |B∩C| + |A∩B∩C|.
Размещения без повторений
Подсчитаем количество способов расположить различных
элементов по различным позициям (). Такие расположения называются размещениями, а их количество,
от французского слова arrangement обозначается . В случае, если количество предметов совпадает
с количеством имеющихся мест, и это уже изученная задача о числе
перестановок.
Если из объектов выбирают штук, то число
выборов последнего объекта есть невыбранных объектов,
что означает наличие возможности выбора последнего
выбранного объекта. То же, другими словами: после выбора первых элемента остается выбрать
элемент.
Теорема: число размещений различных элементов
по различным позициям есть
,
или, в терминах факториалов,
.
Примечание: заметим, что в случае, когда число мест, по которым
размещают предметы, совпадает с количеством самих предметов,
т. е. когда , рассматриваемая задача
становится задачей о числе перестановок. В нашем случае при этом мы
получаем в знаменателе дроби ноль факториал, и для того, что бы разные
формулы, соответствующие одной и той же задаче, приводили к одинаковым
результатам, полагают, что .
архив записей
архив записейВыберите месяц Июль 2021 (2) Май 2021 (2) Май 2020 (2) Апрель 2020 (2) Март 2020 (1) Февраль 2020 (1) Январь 2020 (2) Декабрь 2019 (1) Ноябрь 2019 (2) Октябрь 2019 (9) Сентябрь 2019 (2) Август 2019 (5) Май 2019 (3) Апрель 2019 (2) Март 2019 (2) Февраль 2019 (2) Январь 2019 (2) Декабрь 2018 (4) Ноябрь 2018 (2) Октябрь 2018 (3) Сентябрь 2018 (4) Август 2018 (3) Июль 2018 (5) Июнь 2018 (2) Май 2018 (3) Апрель 2018 (10) Март 2018 (9) Февраль 2018 (3) Январь 2018 (1) Декабрь 2017 (4) Ноябрь 2017 (3) Октябрь 2017 (4) Сентябрь 2017 (6) Август 2017 (1) Июль 2017 (5) Июнь 2017 (13) Май 2017 (2) Апрель 2017 (48) Март 2017 (3) Февраль 2017 (11) Январь 2017 (9) Декабрь 2016 (2) Ноябрь 2016 (9) Октябрь 2016 (3) Сентябрь 2016 (2) Август 2016 (4) Июль 2016 (10) Июнь 2016 (14) Май 2016 (9) Апрель 2016 (26) Март 2016 (5) Февраль 2016 (4) Январь 2016 (16) Декабрь 2015 (6) Ноябрь 2015 (10) Октябрь 2015 (4) Август 2015 (3) Июль 2015 (3) Июнь 2015 (6) Май 2015 (1) Апрель 2015 (8) Март 2015 (10) Февраль 2015 (7) Январь 2015 (7) Декабрь 2014 (5) Ноябрь 2014 (16) Октябрь 2014 (4) Сентябрь 2014 (12) Август 2014 (1) Июль 2014 (8) Июнь 2014 (2) Май 2014 (10) Апрель 2014 (6) Март 2014 (9) Февраль 2014 (8) Январь 2014 (2) Декабрь 2013 (1) Ноябрь 2013 (9) Октябрь 2013 (10) Сентябрь 2013 (13) Июнь 2013 (3) Май 2013 (9) Апрель 2013 (11) Март 2013 (9) Февраль 2013 (8) Январь 2013 (9) Декабрь 2012 (3) Ноябрь 2012 (7) Октябрь 2012 (8) Сентябрь 2012 (12) Август 2012 (5) Июнь 2012 (3) Май 2012 (15) Апрель 2012 (17) Март 2012 (28) Февраль 2012 (23) Январь 2012 (32) Декабрь 2011 (15)
Перестановки
Рассмотрим следующую задачу.
Задача. 6 карточек пронумерованы числами 1, 2, 3, 4, 5, 6. Карточки наугад выкладываем в ряд. Сколько при этом можно получить различных шестизначных чисел?
Решение. Сначала слева направо пронумеруем места в ряду, куда выкладываем карточки: первое место, второе, третье, четвертое, пятое, шестое. На первое место можно положить одну из 6 карточек. Для этого есть 6 способов. В каждом из этих 6 способов на второе место можно положить одну из оставшихся 5 карточек. Таким образом, существует
способов, чтобы положить карточки на первое и второе места. В каждом из этих 30 способов на третье место можно положить одну из оставшихся 4 карточек. Следовательно, существует
способов, чтобы положить карточки на первое, второе и третье места. В каждом из этих 120 способов на четвертое место можно положить одну из оставшихся 3 карточек. Отсюда вытекает, что существует
способов, чтобы положить карточки на первое, второе, третье и четвертое места. В каждом из этих 360 способов на пятое место можно положить одну из оставшихся 2 карточек. Следовательно, существует
способов, чтобы положить карточки на первое, второе, третье, четвертое и пятое места. После этого у нас остается одна единственная карточка, которую мы и кладем на шестое место. Таким образом, при выкладывании карточек можно получить 720 различных шестизначных чисел.
Ответ: 720.
Замечание 1. В задаче мы рассмотрели 6 пронумерованных карточек и установили, что количество способов выкладывания этих карточек в ряд равно 6!
Если бы у нас было n пронумерованных карточек, то количество способов выкладывания их в ряд равнялось бы n ! .
Замечание 2. Каждое расположение n пронумерованных карточек в ряд является перестановкой из n элементов, к изучению которых мы сейчас и переходим.
Определение 1. Пусть n – натуральное число. Рассмотрим произвольное множество, содержащее n элементов. Говорят, что на этом множестве задано упорядочение (отношение порядка), если его элементы пронумерованы числами 1, 2, 3, … , n.
Множество с заданным упорядочением называют упорядоченным множеством.
Определение 2. Рассмотрим множество, содержащее n элементов. Перестановкой из n элементов называют любое упорядочение этого множества.
Число перестановок из n элементов обозначают символом Pn.
В соответствии с Замечанием 1, справедлива формула:
Pn = n !
В частности,
P6 = 6! = 720 .
Замечание 3. Введенные в данном разделе перестановки называют также перестановками без повторений.
С понятиями из n элементов по m элементов и из n элементов по m элементов можно познакомиться в разделе «Комбинаторика: размещения и сочетания» нашего справочника.
На нашем сайте можно также ознакомиться нашими учебными материалами для подготовки к ЕГЭ и ОГЭ по математике.
Литература[]
- Ерош И. Л. Дискретная математика. Комбинаторика — СПб.: СПбГУАП, 2001. — 37 c.
- Андерсон Джеймс Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. — М.: «Вильямс», 2006. — С. 960. — ISBN 0-13-086998-8
Р. Стенли Перечислительная комбинаторика = Enumerative Combinatorics. — М.: «Мир», 1990. — С. 440. — ISBN 5-03-001348-2
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.
Риордан Дж. Введение в комбинаторный анализ. — пер. с англ.. — М.: 1963.
Раизер Г. Дж. Комбинаторная математика. — пер. с англ.. — М.: 1966.
Липский В. Комбинаторика для программиста. — М.: Мир, 1988. — 213 с.
Виленкин Н.Я. Популярная комбинаторика. — М.: Наука, 1975.
Райгородский А. М. Линейно-алгебраические и вероятностные методы в комбинаторике. — Летняя школа «Современная математика». — Дубна: 2006.