Разница между сочетанием и размещением
Перестановки, размещения и сочетания. Формулы
Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:
Введение. Множества и выборки
В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество.
Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме “Понятие множества. Способы задания множеств”.
Очень краткий рассказ про множества: показать\скрыть
Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$.
Множество согласных букв в слове “тигрёнок” таково: $\{т, г, р, н, к\}$. Запись $5\in A$ означает, что элемент 5 принадлежит множеству $A=\{1,5,9 \}$. Количество элементов в конечном множестве называют мощностью этого множества и обозначают $|A|$.Например, для множества $A=\{1,5,9 \}$, содержащего 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=\{a,b,c,d,e\}$. Множество $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)eq(b,a,b)$.
Рассмотрим ещё один пример, немного менее абстрактный 🙂 Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете – цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U=\{1,2,3,4,5,6\}$.Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты – это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений.
Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.
Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет).
Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка.
Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока – повторения сортов неизбежны.
При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.
Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить “слова” из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д.
Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков.
Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.
Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U=\{1,5,7,8\}$.Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная.
Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.
Размещения без повторений из $n$ элементов по $k$
Размещение без повторений из $n$ элементов по $k$ – упорядоченная $(n,k)$-выборка без повторений.
Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:
\begin{equation}A_{n}{k}=\frac{n!}{(n-k)!} \end{equation}
Что обозначает знак “!”? : показать\скрыть
Запись “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. $$
Пример №1
Алфавит состоит из множества символов $E=\{+,*,0,1,f\}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.
Решение
Под трёхсимвольными словами будем понимать выражения вида “+*0” или “0f1”. В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной.
Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3.
Вот примеры таких размещений:
$$ (+,*,f), \; (*,+,f), \; (1,+,0) $$
Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:
$$ A_{5}{3}=\frac{5!}{(5-3)!}=\frac{5!}{2!}=60. $$
Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.
Ответ: 60.
Размещения с повторениями из $n$ элементов по $k$
Размещение с повторениями из $n$ элементов по $k$ – упорядоченная $(n,k)$-выборка с повторениями.
Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:
\begin{equation}\bar{A}_{n}{k}=nk \end{equation}
Пример №2
Сколько пятизначных чисел можно составить из множества цифр $\{5,7,2\}$?
Решение
Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$.
Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 – разные числа.Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):
$$ \bar{A}_{3}{5}=35=243. $$
Следовательно, из заданных цифр можно составить 243 пятизначных числа.
Ответ: 243.
Перестановки без повторений из $n$ элементов
Перестановка без повторений из $n$ элементов – упорядоченная $(n,n)$-выборка без повторений.
По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из $n$ элементов определяется следующей формулой:
\begin{equation}P_{n}=n! \end{equation}
Эту формулу, кстати, легко получить, если учесть, что $P_n=A_{n}{n}$. Тогда получим:
$$ P_n=A_{n}{n}=\frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n! $$
Пример №3
В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?
Решение
Пусть первому мороженому соответствует цифра 1, второму – цифра 2 и так далее. Мы получим множество $U=\{1,2,3,4,5\}$, которое будет представлять содержимое морозилки.
Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений.
Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:
$$ P_5=5!=120. $$
Следовательно, существует 120 порядков выбора очередности съедения.
Ответ: 120.
Перестановки с повторениями
Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+\ldots+k_r=k$.
Общее количество перестановок с повторениями определяется формулой:
\begin{equation}P_{k}(k_1,k_2,\ldots,k_r)=\frac{k!}{k_1!\cdot k_2!\cdot \ldots \cdot k_r!} \end{equation}
Пример №4
Слова составляются на основе алфавита $U=\{a,b,d\}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква “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), будем иметь:
$$ P_7(2,1,4)=\frac{7!}{2!\cdot 1!\cdot 4!}=105. $$
Следовательно, общее количество искомых слов равно 105.
Ответ: 105.
Сочетания без повторений из $n$ элементов по $k$
Сочетание без повторений из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка без повторений.
Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:
\begin{equation}C_{n}{k}=\frac{n!}{(n-k)!\cdot k!} \end{equation}
Пример №5
В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?
Решение
Итак, в данной задаче исходное множество таково: $U=\{1,2,3,4,5,6,7,8,9,10\}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны.
Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится.
Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений.
Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):
$$ C_{10}{4}=\frac{10!}{(10-4)!\cdot 4!}=\frac{10!}{6!\cdot 4!}=210. $$
Следовательно, общее количество искомых наборов равно 210.
Ответ: 210.
Сочетания с повторениями из $n$ элементов по $k$
Сочетание с повторениями из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка с повторениями.
Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:
\begin{equation}\bar{C}_{n}{k}=\frac{(n+k-1)!}{(n-1)!\cdot k!} \end{equation}
Пример №6
Представьте себе, что мы находимся на конфетном заводе, – прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных “конфетных комбинаций” может оказаться в горсти?
Решение
Если принять, что первому сорту соответствует число 1, второму сорту – число 2 и так далее, то исходное множество в нашей задаче таково: $U=\{1,2,3,4\}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут.
Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями.Чтобы найти общее количество этих выборок используем формулу (6):
$$ \bar{C}_{4}{20}=\frac{(4+20-1)!}{(4-1)!\cdot 20!}=\frac{23!}{3!\cdot 20!}=1771. $$
Следовательно, общее количество искомых комбинаций равно 1771.
Ответ: 1771.
Онлайн-занятия по высшей математике
Элементы комбинаторики: размещение, сочетание, перестановки и комбинации с повторением
Среди соединения различают основные виды: размещения, перестановки, комбинации, а также их виды с повторениями. Дальше мы более подробно рассмотрим каждый из этих видов соединения.
Размещение элементов комбинаторики
Пусть даны три элемента . Из них можно создать такие соединения:
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)
где может быть .
Примеры решения задач с элементами комбинаторики
Пример 1
Задача
Студенты группы изучают 9 дисциплин по 3 пары ежедневно. Сколько существует способов, чтобы распределить пары на один день?
Решение
Все возможные способы распределения пар на день представляют собой, очевидно, все возможные размещения из 9 элементов по 3. Поэтому их количество равняется:
.
Ответ
Существует 504 размещений.
Пример 2
Задача
Автомобильный номер состоит из 5 цифр (из такого набора: и двух букв. В соединении из букв для номеров автомобилей, какие зарегистрированы в Московской области, на первом месте стоит буква , а на втором месте одна из букв А, Б. В, И. К, Н. Сколько автомобильных номеров можно составить в области?
Решение
Числовая часть номера – один из размещений из по с повторениями. И количество:
Из них необходимо исключить размещение 000-00, так как такой номер не используется, то есть, всех числовых соединений будет:
.
Количество соединения букв 7. Первая буква фиксированная, тогда остаётся шесть. Общее число всех автомобильных номеров при изложенной системе равняется:
.
Ответ
Автомобильных номеров в одной области можно составить по числам – 99 999, а по буквам – 599994.
Пример 3
Задача
Сколько пятизначных телефонных номеров можно составить используя цифры 3, 4, 5, 6, 7 (без повторений)?
Решение
Так как каждый номер телефона складывается из 5 цифр, тогда такие номера будут отличаться только порядком цифр, то есть это будут перестановки, и их количество равняется:.
Ответ
Всего можно составить 120 пятизначных номеров.
Пример 4
Задача
Сколько есть способов, чтобы заполнить карточку спортлото, в которой из 49 чисел необходимо выбрать 6?
Решение
Две заполненные карточки считаются разными, если среди выбранных 6 чисел они отличаются хотя бы одним числом, то есть это будут комбинации, и их количество равняется:
.
Ответ
Количество комбинаций =
Пример 5
Задача
Сколько есть способов, чтобы в данном тайме тренер смог бы выставить на поле 5 баскетболистов, если в команде 10 игроков, причём одного из ведущих игроков тренер планирует задействовать в игре не заменяя на другого игрока весь тайм?
Решение
Так как один из ведущих игроков должен находится на поле в игре весь тайм, тогда менять придётся только 4 игрока из оставшихся 9, то есть у нас получается:
Ответ
Есть 126 способов.
Пример 6
Задача
Сколько есть способов, чтобы расставить на первой горизонтальной шахматной доски такие фигуры: две ладьи, два коня, два слона, одного ферзя и одного короля?
Решение
Всего 8 фигур, причём , , , , , тогда:
.
Ответ
На первой горизонтальной шахматной доске с перестановками фигур можно расставить 5 040 раз.
Пример 7
Задача
Сколько разных соединений букв можно образовать, переставляя эти буквы:
1. В слове “мама”;
2. в слове параллелограмм.
Записать соединения букв.
Решение
1. В слове “мама” буквы, при этом две буквы “м”, и две буквы “а”. По формуле (9) всех перестановок будет:
.
А сами перестановки будут такими: “мама”, “маам”, амам”, “аамм”, “амма”.
2. В слове “параллелограмм” 12 букв, из них букв “а” – 3, “г” – 1, “е” – 1, “л” – 2, “м” – 1, “о” – 1, “п” – 1, “р” – 2. Всех перестановок будет:.
Ответ
Всевозможных перестановок будет – .
Пример 8
Задача
На складе нужно получить 5 однотипных деталей, каждая из которых может быть покрашена в один из трёх цветов: красный, чёрный, зелёный. Сколько имеется способов, чтобы выбрать 5 деталей трёх цветов?
Решение
.
Ответ
Для того, чтобы выбрать 5 деталей 3 цветов, мы нашли 21 способ.