Разница между сочетанием и размещением

Перестановки, размещения и сочетания. Формулы

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

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

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

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

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

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: $\{1,5,9 \}$.

Например, для множества $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)$.

Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты – это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений.

Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U=\{1,2,3,4 \}$ (каждая цифра отвечает за свой сорт конфет).

Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка.

Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока – повторения сортов неизбежны.

При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U=\{к,о,н,ф,е,т,а\}$. Допустим, из данных кубиков мы хотим составить “слова” из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д.

Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков.

Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.

Цифры каждого составленного числа образуют (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)$.

Следовательно, мы имеем дело с упорядоченными (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)$ и т.д.

$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)-выборку. Естественно, повторения сортов будут.

Чтобы найти общее количество этих выборок используем формулу (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)

, , и т. д.

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

 Иногда бывают перестановки с повторениями: , которые можно образовать из элементов, среди которых одинаковых элементов 1-го типа, одинаковых элементов 2-го типа, и т. д. одинаковых элементов к-го типа, причём находятся по формуле:

(9)

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

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

(10)

где может быть .

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

Пример 1

Задача

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

Решение

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

.

Ответ

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

Пример 2

Задача

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

Решение

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

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

.

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

.

Ответ

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

Пример 3

Задача

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

Решение

.

Ответ

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

Пример 4

Задача

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

Решение

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

.

Ответ

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

Пример 5

Задача

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

Решение

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

Ответ

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

Пример 6

Задача

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

Решение

Всего 8 фигур, причём , , , , , тогда:

.

Ответ

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

Пример 7

Задача

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

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

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

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

Решение

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

.

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

.

Ответ

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

Пример 8

Задача

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

Решение

.

Ответ

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