Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:
Введение. Множества и выборки.
В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество.
Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме "Понятие множества. Способы задания множеств".
Очень краткий рассказ про множества
Если вкратце: множеством именуют некую совокупность объектов. Записывают множества в фигурных скобках. Порядок записи элементов роли не играет; повторения элементов не допускаются. Например, множество цифр числа 11115555999 будет таким: \(\displaystyle{\{1,5,9 \}}\). Множество согласных букв в слове "тигрёнок" таково: \(\displaystyle{\{т, г, р, н, к\}}\). Запись \(\displaystyle{5\in A}\) означает, что элемент 5 принадлежит множеству \(\displaystyle{A=\{1,5,9 \}}\). Количество элементов в конечном множестве называют мощностью этого множества и обозначают \(\displaystyle{|A|}\). Например, для множества \(\displaystyle{A=\{1,5,9 \}}\), содержащего 3 элемента, имеем: \(\displaystyle{|A|=3}\).
Рассмотрим некое непустое конечное множество \(\displaystyle{U}\), мощность которого равна \(\displaystyle{n}\),\(\displaystyle{|U|=n}\) (т.е. в множестве \(\displaystyle{U}\) имеется \(\displaystyle{n}\) элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема \(\displaystyle{k}\) из \(\displaystyle{n}\) элементов (сокращённо \(\displaystyle{(n,k)}\)-выборкой) будем понимать набор элементов \(\displaystyle{(a_1, a_2,\ldots, a_k)}\), где \(\displaystyle{a_i\in U}\). Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.
Заметьте, что в определении выборки ничего не сказано про повторения элементов. В отличие от элементов множеств, элементы выборки могут повторяться.
Для примера рассмотрим множество \(\displaystyle{U=\{a,b,c,d,e\}}\). Множество \(\displaystyle{U}\) содержит 5 элементов, т.е. \(\displaystyle{|U|=5}\). Выборка без повторений может быть такой: \(\displaystyle{(a,b,c)}\). Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это \(\displaystyle{(5,3)}\)-выборка.
Выборка с повторениями может быть такой: \(\displaystyle{(a,a,a,a,a,c,c,d)}\). Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это \(\displaystyle{(5,8)}\)-выборка.
Рассмотрим ещё две \(\displaystyle{(5,3)}\)-выборки: \(\displaystyle{(a,b,b)}\) и \(\displaystyle{(b,a,b)}\). Если мы полагаем наши выборки неупорядоченными, то выборка \(\displaystyle{(a,b,b)}\) равна выборке \(\displaystyle{(b,a,b)}\), т.е. \(\displaystyle{(a,b,b)=(b,a,b)}\). Если мы полагаем наши выборки упорядоченными, то \(\displaystyle{(a,b,b)\neq(b,a,b)}\).
Рассмотрим ещё один пример, немного менее абстрактный :) Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете – цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: \(\displaystyle{U=\{1,2,3,4,5,6\}}\). Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты – это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.
Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество \(\displaystyle{U}\) в этой ситуации таково: \(\displaystyle{U=\{1,2,3,4 \}}\) (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока – повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.
Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество \(\displaystyle{U=\{к,о,н,ф,е,т,а\}}\). Допустим, из данных кубиков мы хотим составить "слова" из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: \(\displaystyle{(к,о,н,ф,е)}\),\(\displaystyle{(т,е,н,к,о)}\) и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.
Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество \(\displaystyle{U}\) таково: \(\displaystyle{U=\{1,5,7,8\}}\). Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.
Размещения без повторений из \(\displaystyle{n}\) элементов по \(\displaystyle{k}\)
Размещение без повторений из \(\displaystyle{n}\) элементов по \(\displaystyle{k}\) – упорядоченная \(\displaystyle{(n,k)}\)-выборка без повторений.
Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: \(\displaystyle{n≥ k}\). Количество размещений без повторений из \(\displaystyle{n}\) элементов по \(\displaystyle{k}\) определяется следующей формулой:
Запись "n!" (читается "эн факториал") обозначает произведение всех чисел от 1 до n, т.е.
\[
n!=1\cdot2\cdot 3\cdot \ldots\cdot n
\]
По определению полагается, что \(\displaystyle{0!=1!=1}\). Для примера найдём 5!:
\[
5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120.
\]
Задача №1
Условие
Алфавит состоит из множества символов \(\displaystyle{E=\{+,*,0,1,f\}}\). Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.
Решение
Под трёхсимвольными словами будем понимать выражения вида "+*0" или "0f1". В множестве \(\displaystyle{E}\) пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:
\[
(+,*,f), \; (*,+,f), \; (1,+,0)
\]
Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:
Сколько пятизначных чисел можно составить из множества цифр \(\displaystyle{\{5,7,2\}}\)?
Решение
Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: \(\displaystyle{(5,5,5,5,5)}\),\(\displaystyle{(7,5,2,2,2)}\). Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 – разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):
\[
\bar{A}_{3}^{5}=3^5=243.
\]
Следовательно, из заданных цифр можно составить 243 пятизначных числа.
Ответ:
243.
Перестановки без повторений из \(\displaystyle{n}\) элементов
Перестановка без повторений из \(\displaystyle{n}\) элементов – упорядоченная \(\displaystyle{(n,n)}\)-выборка без повторений.
По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из \(\displaystyle{n}\) элементов определяется следующей формулой:
\[
\begin{equation}
P_{n}=n!
\end{equation}
\]
Эту формулу, кстати, легко получить, если учесть, что \(\displaystyle{P_n=A_{n}^{n}}\). Тогда получим:
В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?
Решение
Пусть первому мороженому соответствует цифра 1, второму – цифра 2 и так далее. Мы получим множество \(\displaystyle{U=\{1,2,3,4,5\}}\), которое будет представлять содержимое морозилки. Порядок съедения может быть таким: \(\displaystyle{(2,1,3,5,4)}\) или таким: \(\displaystyle{(5,4,3,1,2)}\). Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:
\[
P_5=5!=120.
\]
Следовательно, существует 120 порядков выбора очередности съедения.
Ответ:
120.
Перестановки с повторениями
Перестановка с повторениями – упорядоченная \(\displaystyle{(n,k)}\)-выборка с повторениями, в которой элемент \(\displaystyle{a_1}\) повторяется \(\displaystyle{k_1}\) раз, \(\displaystyle{a_2}\) повторяется \(\displaystyle{k_2}\) раза так далее, до последнего элемента \(\displaystyle{a_r}\), который повторяется \(\displaystyle{k_r}\) раз. При этом \(\displaystyle{k_1+k_2+\ldots+k_r=k}\).
Общее количество перестановок с повторениями определяется формулой:
Слова составляются на основе алфавита \(\displaystyle{U=\{a,b,d\}}\). Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" – 1 раз, а буква "d" – 4 раза?
Решение
Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: \(\displaystyle{(a,a,b,d,d,d,d)}\),\(\displaystyle{(d,a,d,d,a,b,d)}\) и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, \(\displaystyle{k_1=2}\),\(\displaystyle{k_2=1}\),\(\displaystyle{k_3=4}\). Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. \(\displaystyle{k=k_1+k_2+k_3=7}\). Подставляя эти данные в формулу (4), будем иметь:
В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?
Решение
Итак, в данной задаче исходное множество таково: \(\displaystyle{U=\{1,2,3,4,5,6,7,8,9,10\}}\). Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки \(\displaystyle{(1,2,7,10)}\) и \(\displaystyle{(10,2,1,7)}\) или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке \(\displaystyle{(1,2,7,10)}\) и выборке \(\displaystyle{(10,2,1,7)}\) будет соответствовать одно и то же число \(\displaystyle{1+2+7+10=10+2+1+7=20}\). Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений. Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):
Представьте себе, что мы находимся на конфетном заводе, – прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных "конфетных комбинаций" может оказаться в горсти?
Решение
Если принять, что первому сорту соответствует число 1, второму сорту – число 2 и так далее, то исходное множество в нашей задаче таково: \(\displaystyle{U=\{1,2,3,4\}}\). Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):