Элементы комбинаторики: размещение, сочетание, перестановки и комбинации с повторением
Элементы комбинаторики – это разные подмножества, которые образованы из каких-нибудь элементов и отличаются друг от друга, либо самими элементами, либо порядком их расположения, называются соединениями .Элементы, из которых образовываются соединения и обозначаются буквами a, b, c, … .
Среди соединения различают основные виды: размещения, перестановки, комбинации, а также их виды с повторениями. Дальше мы более подробно рассмотрим каждый из этих видов соединения.
Размещение элементов комбинаторики
Пусть даны три элемента . Из них можно создать такие соединения:
1) по одному элементу: ;
2) по два элемента: ;
3) по три элемента: .
Если, например, рассматривать соединения по два элемента, тогда некоторые из них отличаются элементами ( и ), другие – порядком элементов и . Такие соединения называются размещением из 3 элементов по 2.
Число размещений обозначается . Из вышеописанного, мы видим, что , , .
Число всех возможных размещений из элементов по равняется произведению последовательных натуральных чисел, из которых большее число , то есть:
Действительно, пусть нам дано элементов: .
Рассмотрим размещение по одному элементу. Понятно, что их будет , то есть .
Теперь рассмотрим, какие возможные размещения по 2 элемента. Чтобы их получить, мы допишем к каждому из данных элементов ещё по одному, которые брались из остальных элементов. Так, к элементу допишем последовательно остальные элементы: ; к элементу последовательно остальные элементы: и т. д.
Получим все размещения из элементов по 2:
Записано строк, а число всех размещений в каждом из этих строк . Общее количество всех размещений равняется произведению на , то есть:
Чтобы получить рзмещение по 3 элемента в каждом, нам нужно к каждой из записанных пар элементов приобщить ещё по одному элементу из элементов, что остались.
Например, к необходимо приобщить один из элементов . Тогда всех размещений по 3 элемента будет:
Иногда встречаются задачи на размещение с повторениями.
Число размещений с повторениями обозначаются через и вычисляются по формуле:
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
Перестановка элементов комбинаторики
Согласно с определением:
Произведение всех натуральных чисел от до обозначается , а читается ( факториал).
Тогда формула для вычисления количества перестановок запишется:
При этом имеется ввиду, что .
Комбинации или сочетание элементов комбинаторики
Сочетание элементов (комбинации) из элементов по (обозначается ) называется то размещение из элементов по , которые отличаются хотя бы одним элементом.
Число комбинаций вычисляется по формуле:
Формулу (4) объясним на таком примере:
Пусть даны 4 элемента , комбинациями из этих элементов по будут:
Порядок элементов в комбинации роли не играет. Если в каждой из этих комбинаций сделать всевозможные перестановки, тогда у нас получатся всевозможные размещения из 3 элементов:
Число таких размещений равняется .
Таким образом, число всех размещений из элементов по равняется числу всех возможных сочетаний элементов по , умноженному на число всех перестановок, которые можно сделать из элементов, то есть:
откуда получается формула (4).
Умножим числитель и знаменатель в формуле (4) на . Тогда получим:
В итоге получаем:
По определению принимают . Это определение можно получить из формулы (5), если принять во внимание, что .
При вычислении числа комбинаций иногда удобно пользоваться соотношением:
Действительно, если по формуле (5) записать , тогда получим:
Последнее выражение совпадает с правой частью в формуле (5).
Отметим ещё, что числа – это коэффициенты в биноме Ньютона:
причём согласно с равенством (6) коэффициенты, равноотдалённые от окончания в формуле (8), равные между собой, то есть:
Перестановки и комбинации с повторениями
Иногда бывают перестановки с повторениями: , которые можно образовать из элементов, среди которых одинаковых элементов 1-го типа, одинаковых элементов 2-го типа, и т. д. одинаковых элементов к-го типа, причём находятся по формуле:
Теперь рассмотрим комбинации с повторениями.
Число комбинаций с повторениями (обозначается ) из по элементов есть такие соединения по элементов в каждой (элементы могут повторяться), которые выбираются из элементов типов, причём порядок элементов не учитывается, и находится по формуле:
Примеры решения задач с элементами комбинаторики
Задача
Студенты группы изучают 9 дисциплин по 3 пары ежедневно. Сколько существует способов, чтобы распределить пары на один день?
Решение
Все возможные способы распределения пар на день представляют собой, очевидно, все возможные размещения из 9 элементов по 3. Поэтому их количество равняется:
Ответ
Существует 504 размещений.
Задача
Автомобильный номер состоит из 5 цифр (из такого набора: и двух букв. В соединении из букв для номеров автомобилей, какие зарегистрированы в Московской области, на первом месте стоит буква , а на втором месте одна из букв А, Б. В, И. К, Н. Сколько автомобильных номеров можно составить в области?
Решение
Числовая часть номера – один из размещений из по с повторениями. И количество:
Из них необходимо исключить размещение 000-00, так как такой номер не используется, то есть, всех числовых соединений будет:
Количество соединения букв 7. Первая буква фиксированная, тогда остаётся шесть. Общее число всех автомобильных номеров при изложенной системе равняется:
Ответ
Автомобильных номеров в одной области можно составить по числам – 99 999, а по буквам – 599994.
Задача
Сколько пятизначных телефонных номеров можно составить используя цифры 3, 4, 5, 6, 7 (без повторений)?
Решение
Так как каждый номер телефона складывается из 5 цифр, тогда такие номера будут отличаться только порядком цифр, то есть это будут перестановки, и их количество равняется:
Ответ
Всего можно составить 120 пятизначных номеров.
Задача
Сколько есть способов, чтобы заполнить карточку спортлото, в которой из 49 чисел необходимо выбрать 6?
Решение
Две заполненные карточки считаются разными, если среди выбранных 6 чисел они отличаются хотя бы одним числом, то есть это будут комбинации, и их количество равняется:
Ответ
Задача
Сколько есть способов, чтобы в данном тайме тренер смог бы выставить на поле 5 баскетболистов, если в команде 10 игроков, причём одного из ведущих игроков тренер планирует задействовать в игре не заменяя на другого игрока весь тайм?
Решение
Так как один из ведущих игроков должен находится на поле в игре весь тайм, тогда менять придётся только 4 игрока из оставшихся 9, то есть у нас получается:
Ответ
Есть 126 способов.
Задача
Сколько есть способов, чтобы расставить на первой горизонтальной шахматной доски такие фигуры: две ладьи, два коня, два слона, одного ферзя и одного короля?
Решение
Всего 8 фигур, причём , , , , , тогда:
Ответ
На первой горизонтальной шахматной доске с перестановками фигур можно расставить 5 040 раз.
Задача
Сколько разных соединений букв можно образовать, переставляя эти буквы:
2. в слове параллелограмм.
Записать соединения букв.
Решение
1. В слове “мама” буквы, при этом две буквы “м”, и две буквы “а”. По формуле (9) всех перестановок будет:
Ответ
Всевозможных перестановок будет – .
Задача
На складе нужно получить 5 однотипных деталей, каждая из которых может быть покрашена в один из трёх цветов: красный, чёрный, зелёный. Сколько имеется способов, чтобы выбрать 5 деталей трёх цветов?