Дайте определение размещения и сочетания кратко

Обновлено: 07.07.2024

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

Определение. Перестановкой из n элементов называется каждое расположение этих элементов в определённом порядке.

P_n = 1 · 2 · 3 · … · (n - 2) · (n - 1) · n.

Пример 1. 5! = 1×2×3×4×5 = 120.

Пример 2. Сколькими способами можно расставить 6 бегунов и 6 беговых дорожках?

Число способов, очевидно, равно числу перестановок из 6 элементов:

P₆ = 1 · 2 · 3 · 4 · 5 · 6 = 720.

Если среди n элементов есть повторяющиеся, то число перестановок из n элементов обозначают символом P_n (n₁, n₂, …, n_s) (перестановки с повторениями) и вычисляют по формуле:

Здесь n₁, n₂, …, n_s – количество одинаковых элементов по группам.

Определение. Размещением из n элементов по k (k £ n) называется любое множество, состоящее из любых k элементов, взятых в определённом порядке из данных n элементов.

= n · (n - 1) · (n - 2) · … · (n – k + 1).

Заметим, что = n · (n - 1) · (n - 2) · … · (n - (n - 1)) = n · (n - 1) · … · 2 · 1 = P_n.

Пример. Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета?

Любое расписание на один день, составленное из 4 различных предметов, отличается от другого либо самыми предметами, либо порядком их следования, то есть важен и порядок, и сами элементы, - это размещения: = 8 · 7 · 6 · 5 = 1680.

Если один и тот же элемент можно использовать более одного раза, то число размещений из n элементов по k обозначают (размещение с повторениями) и вычисляют по формуле: . Здесь s – количество различных элементов среди n элементов.

Определение. Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов. Здесь не важен порядок следования элементов, в отличие от размещений и перестановок.

Заметим, что связь между сочетаниями, размещениями и перестановками выражается формулой

Пример. Из 12 членов группы надо выбрать трёх для поездки в магазин. Сколькими способами это можно сделать?

Очевидно, что здесь важны только сами элементы (конкретные люди), следовательно, это сочетания: .

Если среди n элементов есть повторяющиеся, то число сочетанийобозначают (сочетания с повторениями) и вычисляют по формуле: .Здесь s – количество различных элементов среди n элементов.

Заметим, что связь между сочетаниями, размещениями и перестановками выражается формулой

Пример. Из 12 членов группы надо выбрать трёх для поездки в магазин. Сколькими способами это можно сделать?

Очевидно, что здесь важны только сами элементы (конкретные люди), следовательно, это сочетания: .

P_n = 1 · 2 · 3 · … · (n - 2) · (n - 1) · n.

Пример 1. 5! = 1×2×3×4×5 = 120.

Пример 2. Сколькими способами можно расставить 6 бегунов и 6 беговых дорожках?

Число способов, очевидно, равно числу перестановок из 6 элементов:

P₆ = 1 · 2 · 3 · 4 · 5 · 6 = 720.

Здесь n₁, n₂, …, n_s – количество одинаковых элементов по группам.

= n · (n - 1) · (n - 2) · … · (n – k + 1).

Заметим, что = n · (n - 1) · (n - 2) · … · (n - (n - 1)) = n · (n - 1) · … · 2 · 1 = P_n.

Заметим, что связь между сочетаниями, размещениями и перестановками выражается формулой

Пример. Из 12 членов группы надо выбрать трёх для поездки в магазин. Сколькими способами это можно сделать?

Очевидно, что здесь важны только сами элементы (конкретные люди), следовательно, это сочетания: .

Заметим, что связь между сочетаниями, размещениями и перестановками выражается формулой

Пример. Из 12 членов группы надо выбрать трёх для поездки в магазин. Сколькими способами это можно сделать?

Очевидно, что здесь важны только сами элементы (конкретные люди), следовательно, это сочетания: .

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

Введение. Множества и выборки.

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

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств".

Очень краткий рассказ про множества: показать\скрыть

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\$. Множество согласных букв в слове "тигрёнок" таково: $\$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$. Например, для множества $A=\$, содержащего 3 элемента, имеем: $|A|=3$.

Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,\ldots, a_k)$, где $a_i\in U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.

Заметьте, что в определении выборки ничего не сказано про повторения элементов. В отличие от элементов множеств, элементы выборки могут повторяться.

Для примера рассмотрим множество $U=\$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.

Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.

Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)\neq(b,a,b)$.

Рассмотрим ещё один пример, немного менее абстрактный :) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете – цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты – это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока – повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=\$. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.

Размещения без повторений из $n$ элементов по $k$

Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:

Запись "n!" (читается "эн факториал") обозначает произведение всех чисел от 1 до n, т.е.

$$ n!=1\cdot2\cdot 3\cdot \ldots\cdot n $$

По определению полагается, что $0!=1!=1$. Для примера найдём 5!:

$$ 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120. $$

Алфавит состоит из множества символов $E=\$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:

Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:

Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.

Размещения с повторениями из $n$ элементов по $k$

Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:

Сколько пятизначных чисел можно составить из множества цифр $\$?

Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 – разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):

Следовательно, из заданных цифр можно составить 243 пятизначных числа.

Перестановки без повторений из $n$ элементов

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

Эту формулу, кстати, легко получить, если учесть, что $P_n=A_^$. Тогда получим:

В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?

Пусть первому мороженому соответствует цифра 1, второму – цифра 2 и так далее. Мы получим множество $U=\$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:

Следовательно, существует 120 порядков выбора очередности съедения.

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

Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.

Общее количество перестановок с повторениями определяется формулой:

Слова составляются на основе алфавита $U=\$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" – 1 раз, а буква "d" – 4 раза?

Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:

Следовательно, общее количество искомых слов равно 105.

Сочетания без повторений из $n$ элементов по $k$

Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Следовательно, общее количество искомых наборов равно 210.

Сочетания с повторениями из $n$ элементов по $k$

Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:

Представьте себе, что мы находимся на конфетном заводе, – прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных "конфетных комбинаций" может оказаться в горсти?

Если принять, что первому сорту соответствует число 1, второму сорту – число 2 и так далее, то исходное множество в нашей задаче таково: $U=\$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):

Следовательно, общее количество искомых комбинаций равно 1771.

Ответ: 1771.

Заметили ошибку, опечатку, или некорректно отобразилась формула? Отпишите, пожалуйста, об этом в данной теме на форуме (регистрация не требуется).

О сочетании и размещении говорят, когда из множества необходимо выбрать какое-либо подмножество. Понятия эти весьма близки по своему смыслу, поэтому так трудно бывает понять разницу между ними. Но она существует (причем принципиальная!). Ниже об этом достаточно простым языком написано в статье.

Сочетания

Сочетание – это подмножество, состоящее из К элементов, выбранных из множества, включающего в себя N элементов. При этом выполняется такое условие: N > К.

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

Образно проиллюстрировать понятие можно на примере лотереи. Предположим, человеку предлагается угадать 3 выпавшие цифры из 15-ти. Он выбрал следующий набор – 1, 6, 10. И уже не важно, в каком порядке они выпадут: 1, 6, 10; 1, 10, 6; 10, 1, 6; 10, 6, 1; 6, 10, 1; 6, 1, 10. Главное – состав комбинации. Если он совпадает с загаданным накануне набором цифр, игрок считается победителем.

Сочетания обозначаются следующим образом: С К _N. Где N – количество элементов в множестве, а К – количество объектов в производимой выборке. Для нашего примера N = 15, а К = 3.

Существует формула для определения числа возможных сочетаний в множестве. Выглядит она так: N!/((N-K)!*K!) подставим цифры из нашего примера:

Это означает, что из 15 чисел можно составить 455 различных комбинаций, включающих в себя три разных числа.

Такие подсчеты в нашем примере позволяют определить велики ли шансы субъекта на выигрыш.

Размещения

В самом названии этого термина присутствует корень, позволяющий понять его суть. Размещение – тоже подмножество, выбранное из первоначального множества. Но здесь уже существенное значение имеет место расположения элемента в комбинации. То есть если сочетания могут различаться только составом объектов, то размещения разнятся и составом, и порядком следования элементов.

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

Это легко проследить, если сделать выборку трех элементов из множества, состоящего всего из 4 объектов (от 1-го до 4-х).

Сочетаний здесь будет всего 4 (это легко проверить и по приведенной выше формуле):

123, 234, 134, 241

Размещений же окажется гораздо больше:

123, 132, 321, 312, 231, 213, 234, 243, 324, 342 и т.д.

Существует формула, позволяющая подсчитать возможное количество размещений в представленном множестве:

Для нашего примера посчитаем количество потенциальных размещений:

Получается, что для состоящего из 4-х элементов множества существует 4 сочетания и целых 24 размещения.

Для тех, кто увлекается спортивными ставками, эти знания могут пригодится для того, чтобы рассчитать шансы на выигрыш.

Например, в турнире участвует 6 команд. Необходимо определить количество возможных комбинаций троек призеров кубка.

Обозначим названия команд буквами: А, Б, В, Г, Д, Е.

Сначала определим команду, которая станет золотым призером чемпионата. Таких вариантов, очевидно, 6: А, Б, В, Г, Д, Е.

Затем выбираем один из вариантов (пусть это будет комбинация, в которой золото принадлежит команде А), и определяем для него потенциального серебряного призера. Таких комбинаций уже окажется всего 5, так как одна команда уже записана на 1-м месте: АБ, АВ, АГ, АД, АЕ.

Такую пятерку вариаций можно сформировать для каждой из команд. То есть всего претендентов на серебро оказывается 30 (5*6).

Для каждой двойки первых призеров (чемпион-серебряный призер) можно составить только 4 комбинации с бронзовым призером. Первые два места уже распределены, так что остается 4 команды (6-2). Подберем комбинации для варианта АБ: АБВ, АБГ, АБД, АБЕ.

Мы уже подсчитали выше количество возможных комбинаций для первых двух мест – их оказалось 30. Теперь это число умножаем на 4 – получаем 120.

Выходит, что если в турнире участвует 6 команд, вариантов их размещения по первым трем местам может быть целых 120. Угадать призеров не так просто.

Сочетания и размещения: в чем же разница?

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

Учитесь решать задачи по комбинаторике? На самом начальном этапе нужно изучить основные формулы комбинаторики: сочетания, размещения, перестановки (смотрите подробнее ниже) и научиться их применять для решения задач.

Как выбрать формулу комбинаторики?

Мы подготовили для вас наглядную схему с примерами решений по каждой формуле комбинаторики:

алгоритм выбора формулы (сочетания, перестановки, размещения с повторениями и без),
рекомендации по изучению комбинаторики,
6 задач с решениями и комментариями на каждую формулу.

Перестановки

Пусть имеется $n$ различных объектов.
Будем переставлять их всеми возможными способами (число объектов остается неизменными, меняется только их порядок). Получившиеся комбинации называются перестановками, а их число равно

$$P_n=n!=1\cdot 2\cdot 3 \cdot . \cdot (n-1) \cdot n$$

Символ $n!$ называется факториалом и обозначает произведение всех целых чисел от $1$ до $n$. По определению, считают, что $0!=1, 1!=1$.

Пример всех перестановок из $n=3$ объектов (различных фигур) - на картинке справа. Согласно формуле, их должно быть ровно $P_3=3!=1\cdot 2\cdot 3 =6$, так и получается.

С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно. Например, число перестановок из 10 предметов - уже 3628800 (больше 3 миллионов!).

Размещения

Пусть имеется $n$ различных объектов.
Будем выбирать из них $m$ объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из $n$ объектов по $m$, а их число равно

Пример всех размещений из $n=3$ объектов (различных фигур) по $m=2$ - на картинке справа. Согласно формуле, их должно быть ровно $A_3^2=3\cdot (3-2+1)=3\cdot 2 =6$.

Сочетания

Пусть имеется $n$ различных объектов.
Будем выбирать из них $m$ объектов все возможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из $n$ объектов по $m$, а их число равно

Пример всех сочетаний из $n=3$ объектов (различных фигур) по $m=2$ - на картинке справа. Согласно формуле, их должно быть ровно $C_3^2=\frac =3$. Ясно, что сочетаний всегда меньше чем размещений (так как при размещениях порядок важен, а для сочетаний - нет), причем именно в $m!$ раз, то есть верна формула связи:

Читайте также: