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

О чем статья

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

Определение

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

Пусть даны три элемента $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 способ.

Добавить комментарий Отменить ответ

Эльвира на Как оформить презентацию к диплому правильно (с примерами)Простите, но чем выступать с такой презентацией, я предпочту провалить защиту. Самое главное, рекомендации из статьи, там тоже не соблюдены.
Ноунейм на Правильное оформление титульного листа презентации за 5 минутСпасибо, очень помогли в создании презентации!
Василиса на ТОП-14 видов шпаргалок на экзамен и зачет (палим тему)Моя однокласница у которой был диктант по английскому просто написала слова на руке и спрятала под рукав кофты.Часто пользуюсь ее
Александр на Теорема ПифагораП.1: (a+b)2=4? На самом деле (a+b)2 = 4-м треугольникам
Диоген на Бакалавр это высшее образование или нет? Разбираемся в уровнях высшего образованияСборище клоунов. Обсуждают тут про недоучек и ПТУшное образование, при этом будучи не в состоянии открыть закон об образовании и

Элементы комбинаторики: размещение, сочетание, перестановки и комбинации с повторением

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

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

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

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

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