Среди соединения различают основные виды: размещения, перестановки, комбинации, а также их виды с повторениями. Дальше мы более подробно рассмотрим каждый из этих видов соединения.
О чем статья
Размещение элементов комбинаторики
Пусть даны три элемента . Из них можно создать такие соединения:
1) по одному элементу: ;
2) по два элемента: ;
3) по три элемента: .
Если, например, рассматривать соединения по два элемента, тогда некоторые из них отличаются элементами ( и ), другие – порядком элементов и . Такие соединения называются размещением из 3 элементов по 2.
Число размещений обозначается . Из вышеописанного, мы видим, что , , .
Число всех возможных размещений из элементов по равняется произведению последовательных натуральных чисел, из которых большее число , то есть:
.
(1)
Действительно, пусть нам дано элементов: .
Рассмотрим размещение по одному элементу. Понятно, что их будет , то есть .
Теперь рассмотрим, какие возможные размещения по 2 элемента. Чтобы их получить, мы допишем к каждому из данных элементов ещё по одному, которые брались из остальных элементов. Так, к элементу допишем последовательно остальные элементы: ; к элементу последовательно остальные элементы: и т. д.
Получим все размещения из элементов по 2:
Записано строк, а число всех размещений в каждом из этих строк . Общее количество всех размещений равняется произведению на , то есть:
.
Чтобы получить рзмещение по 3 элемента в каждом, нам нужно к каждой из записанных пар элементов приобщить ещё по одному элементу из элементов, что остались.
Например, к необходимо приобщить один из элементов . Тогда всех размещений по 3 элемента будет:
и т. д.
Иногда встречаются задачи на размещение с повторениями.
Число размещений с повторениями обозначаются через и вычисляются по формуле:
.
(2)
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.
Перестановка элементов комбинаторики
Согласно с определением:
.
Произведение всех натуральных чисел от до обозначается , а читается ( факториал).
Таким образом,
.
Тогда формула для вычисления количества перестановок запишется:
(3)
При этом имеется ввиду, что .
Комбинации или сочетание элементов комбинаторики
Число комбинаций вычисляется по формуле:
(4)
Формулу (4) объясним на таком примере:
Пусть даны 4 элемента , комбинациями из этих элементов по будут:
.
Порядок элементов в комбинации роли не играет. Если в каждой из этих комбинаций сделать всевозможные перестановки, тогда у нас получатся всевозможные размещения из 3 элементов:
Число таких размещений равняется .
Таким образом, число всех размещений из элементов по равняется числу всех возможных сочетаний элементов по , умноженному на число всех перестановок, которые можно сделать из элементов, то есть:
,
откуда получается формула (4).
Посмотрите пример:
.
Умножим числитель и знаменатель в формуле (4) на . Тогда получим:
В итоге получаем:
(5)
По определению принимают . Это определение можно получить из формулы (5), если принять во внимание, что .
При вычислении числа комбинаций иногда удобно пользоваться соотношением:
(6)
Действительно, если по формуле (5) записать , тогда получим:
(7)
Последнее выражение совпадает с правой частью в формуле (5).
Отметим ещё, что числа – это коэффициенты в биноме Ньютона:
(8)
причём согласно с равенством (6) коэффициенты, равноотдалённые от окончания в формуле (8), равные между собой, то есть:
, , и т. д.
Перестановки и комбинации с повторениями
Иногда бывают перестановки с повторениями: , которые можно образовать из элементов, среди которых одинаковых элементов 1-го типа, одинаковых элементов 2-го типа, и т. д. одинаковых элементов к-го типа, причём находятся по формуле:
(9)
Теперь рассмотрим комбинации с повторениями.
Число комбинаций с повторениями (обозначается ) из по элементов есть такие соединения по элементов в каждой (элементы могут повторяться), которые выбираются из элементов типов, причём порядок элементов не учитывается, и находится по формуле:
(10)
где может быть .