Среди соединения различают основные виды: размещения, перестановки, комбинации, а также их виды с повторениями. Дальше мы более подробно рассмотрим каждый из этих видов соединения.

Размещение элементов комбинаторики

Определение
Область математики, где изучается вопрос про количество разных соединений, которые подчинены тем или другим условиям, и которые можно составить из заданных элементов – это и есть комбинаторика. Размещение элементов – один из видов данной области.

Пусть даны три элемента a, b, c. Из них можно создать такие соединения:

1) по одному элементу: a, b, c;

2) по два элемента: ab, ac, bc,ba, ca, cb;

3) по три элемента: abc, acb, bac, bca, cab, cba.

Если, например, рассматривать соединения по два элемента, тогда некоторые из них отличаются элементами (ab и ca), другие – порядком элементов (ac и ca). Такие соединения называются размещением из 3 элементов по 2.

Определение
Размещенными из  n элементов по m называются такие соединения, в которых содержатся по m элементов, взятых из данных n элементов, и которые отличаются один от другого или элементами, или порядком элементов.

Число размещений обозначается A_{n}^{m}. Из вышеописанного, мы видим, что A_{3}^{1} = 3, A_{3}^{2} = 6, A_{3}^{3} = 6.

Число всех возможных размещений из n элементов по m равняется произведению m последовательных натуральных чисел, из которых большее число n, то есть:

A_{n}^{m} = n(n - 1)(n - 2)...(n - (m - 1)).

(1)

Действительно, пусть нам дано n элементов: a, b, c, ..., k, l.

Рассмотрим размещение по одному элементу. Понятно, что их будет n, то есть A_{n}^{1} = n.

Теперь рассмотрим, какие возможные размещения по 2 элемента. Чтобы их получить, мы допишем к каждому из n данных элементов ещё по одному, которые брались из остальных (n - 1) элементов. Так, к элементу a  допишем последовательно остальные элементы: b, c, ..., k, l; к элементу b последовательно остальные элементы: a, c, ..., k, l и т. д.

Получим все размещения из n элементов по 2:

\left\{ \begin{aligned} ab, ac, ad, ..., ak, al - (n - 1);\\ ba, bc, bd, ..., bk, bl - (n - 1);\\ ca, cb, cd, ..., ck, cl - (n - 1);\\  - - - - - - - - - - - -  \\ la, lb, lc, ..., lk - (n - 1) \end{aligned} \right

Записано n строк, а число всех размещений в каждом из этих строк (n - 1). Общее количество всех размещений равняется произведению n на (n - 1), то есть:

A_{n}^{2} = n(n - 1).

Чтобы получить рзмещение по 3 элемента в каждом, нам нужно к каждой из записанных пар элементов приобщить ещё по одному элементу из (n - 2) элементов, что остались.

Например, к ab необходимо приобщить один из (n - 2) - x элементов c, d, ..., k, l. Тогда всех размещений по 3 элемента будет:

A_{n}^{3} = n(n - 1)(n - 2) и т. д.

Иногда встречаются задачи на размещение с повторениями.

Определение
Размещение из n элементов по m с повторениями называются такие соединения, которые содержат по m элементов, взятых из данных n элементов, причём отдельные элементы могут появляться 0, 1, 2, ..., m раз.

Число размещений с повторениями обозначаются через \overline{A}_{n}^{m}  и вычисляются по формуле:

\overline{A}_{n}^{m} = n^{m}.

(2)

Перестановка элементов комбинаторики

Определение
Перестановка элементов – это размещение из n элементов по n и обозначаются P_{n}.

Согласно с определением:

P_{n} = A_{n}^{n} = n(n - 1)(n - 2)...(n - (n - 1)) = n(n - 1)(n - 2)...1.

Произведение всех натуральных чисел от 1 до n обозначается n!, а читается (n факториал).

Таким образом,

n! = 1 * 2 * 3...(n - 1)n = (n - 1)!n.

Тогда формула для вычисления количества перестановок запишется:

P_{n} = n!

(3)

При этом имеется ввиду, что 1! = 1.

Обратите внимание!
Иногда встречается обозначение 0!. Принято считать, что 0! = 1.

Комбинации или сочетание элементов комбинаторики

Определение

Сочетание элементов (комбинации) из n элементов по m (обозначается C_{n}^{m}) называется то размещение из n элементов по m, которые отличаются хотя бы одним элементом.

Число комбинаций вычисляется по формуле:

{C_{n}^{m}} = {A_{n}^{m}\over{P_{m}}} = {n(n - 1)(n - 2)...(n - (m - 1))\over{1 * 2 * 3 ... * m}}

(4)

Формулу (4) объясним на таком примере:

Пусть даны 4 элемента a, b, c, d, комбинациями из этих элементов по будут:

abc, abd,acd, bcd.

Порядок элементов в комбинации роли не играет. Если в каждой из этих комбинаций сделать всевозможные перестановки, тогда у нас получатся всевозможные размещения из 3 элементов:

 \begin{vmatrix} abc\quad{abd}\quad{acd}\quad{bcd}\\ acb\quad{adb}\quad{adc}\quad{bdc}\\ bac\quad{bda}\quad{cad}\quad{cbd}\\ bca\quad{bad}\quad{cda}\quad{cdb}\\ cab\quad{dab}\quad{dac}\quad{dbc}\\ cba\quad{dba}\quad{dca}\quad{dcb}. \end{vmatrix} \right

Число таких размещений равняется 6 * 4 = 24.

Таким образом, число всех размещений из n элементов по m равняется числу всех возможных сочетаний элементов по m, умноженному на число всех перестановок, которые можно сделать из m элементов, то есть:

A_{n}^{m} = C_{n}^{m} * P_{m},

откуда получается формула (4).

Посмотрите пример:

C_{4}^{3} = {4 * 3 * 2\over{1 * 2 * 3}} = 4.

Умножим числитель и знаменатель в формуле (4) на 1 * 2 * 3 * ... * (n - m) = (n - m)!. Тогда получим:

{C_{n}^{m}} = {n(n - 1)...(n - (m - 1))\over{1 * 2 * 3...m}} * {(n - m)...3 * 2 * 1\over{(n - m)...3 * 2 * 1}}

В итоге получаем:

{C_{n}^{m}} = {n!\over{(n - m)!m!

(5)

По определению принимают C_{n}^{0} = 1. Это определение можно получить из формулы (5), если принять во внимание, что 0! = 1.

При вычислении числа комбинаций иногда удобно пользоваться соотношением:

C_{n}^{m} = C_{n}^{n - m}

(6)

Действительно, если по формуле (5) записать C_{m}^{n - m}, тогда получим:

{C_{n}^{n - m}} = {n!\over{(n - (n - m))!(n - m)!}} = {n!\over{{m!(n - m)!

(7)

Последнее выражение совпадает с правой частью в формуле (5).

Отметим ещё, что числа C_{n}^{0}, C_{n}^{1}, C_{n}^{2}, ..., C_{n}^{n - 2}, C_{n}^{n - 1}, C_{n}^{n} – это коэффициенты в биноме Ньютона:

(a + b)^{n} = C_{n}^{0}a^{n}b^{0} + C_{n}^{1}a^{n - 1}b^{1} + C_{n}^{2}a^{n - 2}b^{2}+...+\\ + C_{n}^{n - 2}a^{2}b^{n - 2} + C_{n}^{n - 1}ab^{n - 1} + C_{n}^{n}a^{0}b^{n}

(8)

причём согласно с равенством (6) коэффициенты, равноотдалённые от окончания в формуле (8), равные между собой, то есть:

{C_{n}^{0}} = {C_{n}^{n} = 1}, {C_{n}^{1}} = {C_{n}^{n - 1}} = {n}, {C_{n}^{2}} = {C_{n}^{n - 2}} = {n(n - 1)\over{1 * 2}} и т. д.

Перестановки и комбинации с повторениями

 Иногда бывают перестановки с повторениями: P_{n}(m_{1}, m_{2}, ..., m_{k}), которые можно образовать из n элементов, среди которых m_{1} одинаковых элементов 1-го типа, m_{2} одинаковых элементов 2-го типа, и т. д. m_{k} одинаковых элементов к-го типа, причём m_{1} + m_{2} + ... + m_{k} = n находятся по формуле:

P_{n}(m_{1}, m_{2}, ..., m_{k}) = {n!\over{m_{1}! * m_{2}! * ... * m_{k}!}

(9)

Теперь рассмотрим комбинации с повторениями.

Число комбинаций с повторениями (обозначается \overline{C}_{n}^{m}) из n по m элементов есть такие соединения по m элементов в каждой (элементы могут повторяться), которые выбираются из элементов n типов, причём порядок элементов не учитывается, и находится по формуле:

\overline{C}_{n}^{m} = C_{n + m - 1}^{m}

(10)

где может быть m > n.

Примеры решения задач с элементами комбинаторики

Пример 1

Задача

Студенты группы изучают 9 дисциплин по 3 пары ежедневно. Сколько существует способов, чтобы распределить пары на один день?

Решение

Все возможные способы распределения пар на день представляют собой, очевидно, все возможные размещения из 9 элементов по 3. Поэтому их количество равняется:

A_{9}^{3} = 9 * 8 * 7 = 504.

Ответ

Существует 504 размещений.

Пример 2

Задача

Автомобильный номер состоит из 5 цифр (из такого набора: (0, 1, 2, 3, ..., 9) и двух букв. В соединении из букв для номеров автомобилей, какие зарегистрированы в Московской области, на первом месте стоит буква A, а на втором месте одна из букв А, Б. В, И. К, Н. Сколько автомобильных номеров можно составить в области?

Решение

Числовая часть номера – один из размещений из n = 10 по m = 5 с повторениями. И количество:

\overline{A}_{10}^{5} = 10^5

Из них необходимо исключить размещение 000-00, так как такой номер не используется, то есть, всех числовых соединений будет:

10^5 - 1 = 99 999.

Количество соединения букв 7. Первая буква фиксированная, тогда остаётся шесть. Общее число всех автомобильных номеров при изложенной системе равняется:

(10^{5} - 1) * 6 = 599994.

Ответ

Автомобильных номеров в одной области можно составить по числам – 99 999, а по буквам – 599994.

Пример 3

Задача

Сколько пятизначных телефонных номеров можно составить используя цифры 3, 4, 5, 6, 7 (без повторений)?

Решение

Так как каждый номер телефона складывается из 5 цифр, тогда такие номера будут отличаться только порядком цифр, то есть это будут перестановки, и их количество равняется:

P_{5} = 5! = 1 * 2 * 3 * 4 * 5 = 120.

Ответ

Всего можно составить 120 пятизначных номеров.

Пример 4

Задача

Сколько есть способов, чтобы заполнить карточку спортлото, в которой из 49 чисел необходимо выбрать 6?

Решение

Две заполненные карточки считаются разными, если среди выбранных 6 чисел они отличаются хотя бы одним числом, то есть это будут комбинации, и их количество равняется:

{C_{49}^{6}} = {49 * 48 * 47 * 46 * 45 * 44\over{1 * 2 * 3 * 4 * 5 * 6}} = 13 983 816.

Ответ

Количество комбинаций = 13 983 816.

Пример 5

Задача

Сколько есть способов, чтобы в данном тайме тренер смог бы выставить на поле 5 баскетболистов, если в команде 10 игроков, причём одного из ведущих игроков тренер планирует задействовать в игре не заменяя на другого игрока весь тайм?

Решение

Так как один из ведущих игроков должен находится на поле в игре весь тайм, тогда менять придётся только 4 игрока из оставшихся 9, то есть у нас получается:

{C_{9}^{4}} = {9 * 8 * 7 * 6\over{1 * 2 * 3 * 4}} = 126.

Ответ

Есть 126 способов.

Пример 6

Задача

Сколько есть способов, чтобы расставить на первой горизонтальной шахматной доски такие фигуры: две ладьи, два коня, два слона, одного ферзя и одного короля?

Решение

Всего 8 фигур, причём m_{1} = 2, m_{2} = 2, m_{3} = 2, m_{4} = 1, m_{5} = 1, тогда:

{P_{5}} = {(2, 2, 2, 1, 1)} = {8!\over{(2!)}^{3}(1!)^{3}} = 5 040.

Ответ

На первой горизонтальной шахматной доске с перестановками фигур можно расставить 5 040 раз.

Пример 7

Задача

Сколько разных соединений букв можно образовать, переставляя эти буквы:

1. В слове “мама”;

2. в слове параллелограмм.

Записать соединения букв.

Решение

1. В слове “мама” n = 4 буквы, при этом две буквы “м”, и две буквы “а”. По формуле (9) всех перестановок будет:

{P_{4}(2, 2)} = {4!\over{2!2!}} = {4 * 3 * 2 * 1\over{2 * 2}} = 6.

А сами перестановки будут такими: “мама”, “маам”, амам”, “аамм”, “амма”.

2. В слове “параллелограмм” 12 букв, из них букв “а” – 3, “г” – 1, “е” – 1, “л” – 2, “м” – 1, “о” – 1, “п” – 1, “р” – 2. Всех перестановок будет:

{P_{12}(3, 1, 1, 2, 1, 1, 1, 2)} = {12!\over{3!(2!)^{2}(1)^{5}}} = 19 958 400.

Ответ

Всевозможных перестановок будет – 19958400.

Пример 8

Задача

На складе нужно получить 5 однотипных деталей, каждая из которых может быть покрашена в один из трёх цветов: красный, чёрный, зелёный. Сколько имеется способов, чтобы выбрать 5 деталей трёх цветов?

Решение

\overline{{C}_{3}^{5}} = {C_{3 + 5 - 1}^{5}} = {C_{7}^{5}} = {C_{7}^2}} = {7 * 6\over{1 * 2}} = 21.

Ответ

Для того, чтобы выбрать 5 деталей 3 цветов, мы нашли 21 способ.