Способ перестановки сочетания размещения

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

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

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

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

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

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

Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 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=\$. Множество $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=\<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!» (читается «эн факториал») обозначает произведение всех чисел от 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,1,f\>$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

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

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

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

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

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

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

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

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

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

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

Слова составляются на основе алфавита $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 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Итак, в данной задаче исходное множество таково: $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):

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

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

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

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

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

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

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

Источник

Способ перестановки сочетания размещения

В разделе математики, который называется комбинаторикой, решаются некоторые задачи, связанные с рассмотрением множеств и составлением различных комбинаций из элементов этих множеств. Например, если взять 10 различных цифр 0, 1, 2, 3,… , 9 и составлять из них комбинации, то будем получать различные числа, например 143, 431, 5671, 1207, 43 и т.п.

Мы видим, что некоторые из таких комбинаций отличаются только порядком цифр (например, 143 и 431), другие — входящими в них цифрами (например, 5671 и 1207), третьи различаются и числом цифр (например, 143 и 43).

Таким образом, полученные комбинации удовлетворяют различным условиям.

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

Предварительно познакомимся с понятием факториала.

Произведение всех натуральных чисел от 1 до n включительно называют

Комбинация из n элементов, которые отличаются друг от друга только порядком элементов, называются перестановками.

Перестановки обозначаются символом Р _n , где n — число элементов, входящих в каждую перестановку. (Р — первая буква французского слова permutation — перестановка).

Число перестановок можно вычислить по формуле

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

Запишем эту формулу в факториальной форме:

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

Источник