Основные задачи, обозначения и правила
Среди многочисленных проблем, решаемых средствами комбинаторики, основное внимание уделим следующим задачам.
1. Выбор из некоторого, обычно конечного, множества некоторого подмножества (комбинации) элементов, обладающих заданными свойствами.
2. Подсчет числа таких комбинаций.
3.Определение элемента комбинации, обладающего оптимальными свойствами.
Введем следующие понятия и обозначения.
n-множество – множество из n различных элементов:
Х = {х1, х2, …, хn}, хi ¹ хj, при i ¹ j.
(n) -множество – множество, содержащее n различных типов элементов:
Х = {х1, х1, …, х1, х2, х2, …, хn}.
r-выборка множества – совокупность из r элементов данного множества (если выборка из n-множества, то повторяющихся элементов нет, если из (n)-множества, то есть повторения).
Размещения – упорядоченные r-выборки (элементы прямого произведения Х1 ´Х2 ´… ´ Х r).
Сочетания – неупорядоченные r-выборки (r-элементные подмножества данного множества).
Пример 1.1.
а) На диске секретного замка 12 букв. Замок открывается после набора пароля из 5 букв.
В пароле буквы могут повторяться. Следовательно, каждый пароль – это 5-размещение из (12)-множества, т.е. размещение с повторениями.
б) Из 25 человек, членов комитета, надо выбрать: председателя, вице-председателя, секретаря и казначея (4 человека). Совмещение должностей не допускается.
В задаче повторение элементов невозможно, т.к. не допускается совмещение должностей. Кроме того, в данной 4-выборке важен порядок выбора, т.к. надо не просто выбрать заданное число человек, но необходимо связать каждого выбранного с определенной должностью. Следовательно, здесь речь идет о размещении без повторений.
в) Из 125 человек надо выбрать 6 делегатов на конференцию.
В данном случае порядок выбора не играет роли, следовательно, имеет место 6-сочетание из 125-множества.
Многие простые задачи комбинаторики решаются с помощью двух основных аксиоматических правил.
1. Правило суммы. Если все комбинации можно разбить на несколько непересекающихся классов, то общее число комбинаций равно сумме чисел комбинаций во всех классах:
.
2. Правило произведения. Пусть объект А можно выбрать n способами, а при каждом таком выборе объект В можно выбрать m способами. Тогда выбор упорядоченной пары (А, В) можно сделать n×m способами. В общем случае:
.
На практике оба правила часто используются в комбинации.
Пример 1.2. Сколькими способами можно из 28 костей домино выбрать 2 кости, которые можно приложить друг к другу?
Решение. 1-ю кость можно выбрать 28-ю способами. Из них в 7 случаях кость будет дублем, а в 21 случаях – с различными числами. Если 1-я кость является дублем, 2-ю кость можно выбрать 6-ю способами, а если – нет, то 12-ю способами. В соответствии с правилами суммы и произведения общее число случаев равно N = 7×6 + 21×12 = 294.
Простейшие конфигурации
2.1. Размещения с повторениями. Так называются упорядоченные r-выборки из (n)-множества.
Дадим более подробное определение. Пусть дано неограниченное число предметов, относящихся к n различным видам. r-размещениями с повторениями называются различные расстановки из этих предметов по r штук в каждой, образованные по следующим правилам.
1. 2 расстановки считаются различными, если они отличаются либо видом входящих в них предметов, либо порядком следования этих видов.
2. В каждую расстановку может входить несколько предметов одного вида.
Свойство. Число r-размещений с повторениями из предметов n типов обозначается и равно nr.
Доказательство. На 1-м месте может быть предмет одного из n видов. Следовательно, существует n способов выбрать 1-й предмет. При каждом фиксированном таком способе имеется n способов выбрать 2-й предмет, и т.д. В соответствии с правилом произведения всю группу из r предметов можно выбрать nrспособами, что и требовалось доказать.
В примере 1.1.а) существует 125» 250 тыс. различных паролей. (Если взломщик будет тратить по 1 секунде на проверку комбинации, то ему понадобиться 69 часов для проверки всех паролей).
Пример 1.3. В азбуке Морзе самый длинный код буквы состоит из 5 символов. Можно ли использовать коды длиной не более 4-х символов?
Решение. В соответствии с правилом суммы число различных кодов длиной не более 4 символов при использовании 2 видов символов (точка и тире) равно = 2 + 4 + 8 + 16 = 30. Значит, 4-х символьных кодов не хватит для кодирования даже всех букв кириллицы, не говоря о служебных символах. При использовании же 5-ти символьных кодов N = 30 + = 62, т.е. такой длины кода достаточно.
2.2. Размещения и перестановки без повторений. Размещениями без повторений называются упорядоченные r-выборки из n-множества. Такие расстановки по r элементов составляются из n неповторяющихся предметов.
Свойство. Число r-размещений без повторений из n предметов обозначается и равно n×(n – 1)…(n – r + 1) =.
Доказательство. 1-й предмет можно выбрать n способами, 2-й – (n – 1) способами, т.к. число кандидатов на это место уже n – 1, и т.д. В соответствии с правилом произведения получаем выражение из r сомножителей:
.
В примере 1.1.б) число способов выбора 4-х членов в руководство комитета из 25 человек равно = 25×24×23×22 = 303600.
В частном случае при r = n получаем = Рn = n! Данная конфигурация называется перестановкой из n неповторяющихся предметов – упорядоченная n-выборка из n-множества.
2.3. Перестановки с повторениями. Так называют упорядоченные n-выборки из (m)-множества (n > m). Если некоторые элементы такой выборки совпадают, то могут существовать неразличимые (совпадающие) перестановки.
Найдем количество различных перестановок. Обозначим a, b,…, z – переставляемые объекты; nj – количество повторений j-го элемента, j = 1,…,m,; Р(n1,n2,…, nm) – число таких перестановок. Рассмотрим 1-ю перестановку:.
Объекты “а” можно переставлять n1! способами, но поскольку все они одинаковы, то такие перестановки не дают новых комбинаций. Следовательно, число действительно различных перестановок за счет совпадения первых n1 элементов будет в n1! раз меньше, чем в случае всех различающихся элементов. Аналогично, совпадение n2элементов “b” уменьшает число различных перестановок в n2! раз, и т.д. Поскольку при несовпадении всех n элементов количество перестановок было бы равно n!, то
Р(n1, n2,…, nm) =.
Пример 1.4. Найти все перестановки букв в слове “мама”.
Решение. В данном слове есть объекты 2-х типов – “м” и “а”. Всего множество содержит 4 элемента. Следовательно, число перестановок равно. Действительно, имеем следующие комбинации: ”аамм”, “мама”, “амам”, “ммаа”, “амма”, “маам”.
Пример 1.5. Найти число перестановок букв в слове “Миссисипи”.
Решение. Длина этого слова – 9 букв. Из них буква “м” встречается 1 раз, “и” – 4 раза, “с” – 3, “п” – 1. Следовательно, число перестановок равно
Р(1, 4, 3, 1) = = 2520.
2.4. Сочетания без повторений. Так называются неупорядоченные r-выборки изn-множества (r < n).
Свойство. Число r-сочетаний без повторений из n предметов обозначается и равно.
Доказательство. Каждое неупорядоченное r-сочетание можно упорядочить r! способами и получить r-размещение. Следовательно, сочетаний в r! раз меньше, чем размещений, т.е.
= Р(r, n – r).
В примере 1.1.в) 6 делегатов из 125 человек можно выбрать = 4.691×10 9способами
Пример 1.6. В лотерее из 36 номеров будут выбраны 5. Какова вероятность угадать ровно 3 номера из 5?
Решение. 3 номера из 5 верных можно выбрать способами. На каждый угаданный номер могут приходиться любые 2 из 31 невыбранных номеров, т.е. сочетаний. Окончательное число благоприятных случаев равно. Общее же число случаев равно количеству выпадения 5 номеров из 36, т.е..
Отсюда вероятность угадывания равна» 0.0123 – немногим более 1%.
2.5. Сочетания с повторениями. Это неупорядоченные r-выборки из (n)-множества. Они получаются, например, если необходимо r неразличимых предметов разместить по n ящикам, в частности возможно n > r.
Свойство. Число r-сочетаний с повторениями из n предметов обозначается и равно.
Доказательство. Обозначим rj ³ 0 – количество элементов j-го типа в сочетании, (rj можно интерпретировать как количество предметов в j-м ящике). Набор значенийrj однозначно определяет текущее сочетание. Представим этот набор в виде следующей бинарной последовательности. Числа rj отобразим в группы из rj единиц, каждую такую группу отделим от соседних одним нулем (если rj = 0, то несколько нулей могут стоять подряд). Число промежутков равно n – 1. Например, набор (2, 0, 3, 1), n = 4, r = 6 соответствует последовательности (1, 1, 0, 0, 1, 1, 1, 0, 1).
Построенная конструкция – не что иное, как набор перестановок с повторениями объектов 2-х видов – 0 и 1. Число нулей в этих сочетаниях равно n – 1, а единиц – r. Следовательно,, что и требовалось доказать.
Пример 1.7. Определить количество N возможных сочетаний из 8 пирожных 4-х сортов.
Решение. В данном случае rj– число пирожных j-го сорта. Следовательно, r = 8,n = 4 и N = = = 165.
2.6. Свойства чисел сочетаний
1. =. Это свойство вытекает из формулы числа сочетаний.
2. = +.
Доказательство. Разобьем все r-сочетания на два класса. К первому классу отнесем сочетания, содержащие объект an, ко второму классу – не содержащие an. Так как в первом классе меняются только r – 1 элементов из n – 1 возможных, то он содержит r – 1-сочетания из n – 1-множества, следовательно, в нем элементов. Второй класс содержит все r-сочетания из n – 1-множества, т.к. в них нет одного элемента – an. Следовательно, в нем элементов. Общее число сочетаний, согласно правилу суммы равно +, что и требовалось доказать.
Данное свойство позволяет легко построить рекуррентный процесс вычисления всех чисел сочетаний. Положим по определению для любого n ³ 0 (ноль элементов из любого множества, в том числе – пустого, можно выбрать 1 способом, кроме того, по определению 0! = 1 – см. формулу из 2.4) и (отрицательное количество элементов выбрать невозможно). Организуем двойной цикл для вычисления всех, r £ m £ n:
for m:= 1 to n do
for r:= 0 to m do:= +
Описанный процесс удобно представить в виде таблицы, называемой треугольником Паскаля:
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
…………………….
В таблице каждая m-я строка состоит из чисел, r = 0, … m, каждый элемент равен сумме двух элементов, расположенных над ним (пустое место считается нулем).
3.
Доказательство. Пусть имеем последовательность из n двоичных разрядов, содержащих 0 или 1. Очевидно, что каждую такую последовательность можно рассматривать, как n-размещение с повторениями из элементов 2-х типов, значит, количество этих размещений равно 2n.
Теперь рассмотрим некоторое множество из n объектов – а1, … аn, из которого будем образовывать все возможные сочетания без повторений, включая: 0-сочетания (не выбирается ни один объект), 1-сочетания и т.д., n-сочетания. При этом любую из упомянутых выше последовательностей из 0 и 1 можно интерпретировать, как перечень элементов, отбираемых в сочетание – если на k-м месте последовательности стоит 1 – элемент аk отобран, если 0 – не отобран. Очевидно, что таким образом будут перечислены все бинарные n-последова-тельности. По правилу суммы общее число таких сочетаний, а, значит – и бинарных последовательностей равно Свойство доказано.
Замечание. Каждая отбираемая в сочетание группа элементов представляет собой некоторое подмножество исходного множества из n объектов. Следовательно, число всех подмножеств (включая пустое) множества из n элементов равно 2n.
Комбинаторные конфигурации в алгебре и анализе
Многие важные формулы алгебры и математического анализа (и других разделов математики) имеют наглядную комбинаторную интерпретацию или доказываются с использованием правил комбинаторики.
3.1. Бином Ньютона. – формула бинома Ньютона. В частности, (х + у)2 = х2+ 2ху + у2; (х + у)3 = х3 + 3х2у + 3ху2 + у3 и т.д.
