Элементы комбинаторики (стр. 1 )

Глава 2 Элементы комбинаторики

Комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого обычного множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Простейшими примерами комбинаторных конструкций являются перестановки, размещения, сочетания и разбиения, рассматриваемые ниже. Вычисления на дискретных математических структурах – комбинаторные вычисления – требуют комбинаторного анализа для установления свойств и оценки применимости алгоритмов.

Пример 2.1 Агенство недвижимости, база данных. Запись – пара (предложение, спрос). Найти варианты обмена (т. е. такие пары, где первая компонента одной совпадает со второй компонентой другой). Простейший вариант поиска – «лобовой», трудоемкость n´(n–1)/2. Если на одну проверку нужна 1 миллисекунда, то при n = 100 потребуется около 5 секунд, при n=– 5´106 сек, т. е. около 1389 часов. Непригодный алгоритм!!!

2.1 Комбинаторные задачи и основные принципы

§ Комбинаторные задачи

Во многих практических задачах возникает необходимость подсчитать количество возможных комбинаций объектов, удовлетворяющих определенным условиям. Такие задачи называются комбинаторными.

Пример Некто одновременно бросает несколько игральных костей и подсчитывает сумму очков на верхних гранях. Спрашивается – сколько существует различных вариантов результата?
2. В районном городе проживает некоторое количество людей. Открывается телефонная станция. Спрашивается – сколько должно быть цифр в телефонном номере, чтобы всем абонентам хватило различных номеров, да еще и остались запасные с перспективой дальнейшего роста населения?

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

Среди всего многообразия таких задач есть ряд наиболее часто встречающихся, для которых известны способы подсчета.

Для формулировки и решения комбинаторных задач используются различные модели комбинаторных конфигураций. Рассмотрим две наиболее популярные.

1. Дано n предметов. Их нужно разместить по m ящикам так, чтобы выполнялись заданные ограничения. Сколькими способами это можно сделать?

2. Дано множество функций F : X ® Y, где |X| = n, |Y| = m, X = {1,2,…,n} (предметы – элементы множества X – перенумерованы, т. е. можно считать номер отличительным признаком предмета). Без ограничения общности можно считать, что элементы множества Y также перенумерованы: Y = {1,2,…,m}, F = [F(1),…,F(n)], 1 £ F(i) £ m. Сколько существует функций, удовлетворяющих заданным ограничениям?

Наиболее часто соответствие конфигураций 1-го и второго типа очевидно, поэтому анализ проблем и вывод формул можно проводить на любом языке.

§ Основные комбинаторные принципы

Утверждение 2.1 Если множества A и B не пересекаются и содержат по m и n элементов соответственно, то множество AÈB содержит m + n элементов: для множеств A и B | AÇB=Æ: |A È B| = |A| + |B|.

Теорема 2.1 (о произведении множеств):

Для любых множеств A и B |A´B|=|A|×|B|.

Доказательство: Множество C = A´B состоит из упорядоченных пар вида (a,b), aÎA, bÎB. Пуст8ь |A| = m, |B| = n. Первый компонент упорядоченной пары можно выбрать m способами. Если его зафиксировать, то второй элемент можно выбрать n способами. Следовательно, всего имеется m×n различных упорядоченных пар.<

Правило суммы (комбинаторный принцип сложения) Если объект aÎA можно выбрать m способами, а объект bÎB, отличный от a, n способами, причем a и b нельзя выбрать одновременно, то осуществить выбор «либо a, либо b» можно m+n способами.

Пример 2.3 Пусть в киоске имеется 5 различных книг по математике и 7 – по физике. Если студент может купить только одну книгу, то у него есть 5 вариантов выбора первой книги и 7 вариантов – второй, т. е. 12 вариантов.

Правило произведения (комбинаторный принцип умножения) Если объект aÎA можно выбрать m способами, а после каждого такого выбора можно выбрать n способами объект bÎB, отличный от a, то выбор обоих объектов a и b в указанном порядке можно осуществить m×n способами.

Пример 2.4 Пусть в салоне связи имеется 50 различных моделей сотовых телефонов и по три вида чехлов для каждой модели. Сколькими способами можно выбрать телефон и чехол к нему? Очевидно: Выбрав телефон (50 способов), можно 3 способами выбрать чехол, т. е. всего 50´3=150 вариантов.

Сравнивая утверждение 2.1 и теорему 2.1 с правилами суммы и произведения, заметим, что в них речь идет об одних и тех же закономерностях, хотя и используются различные формулировки. Очевидным образом эти правила распространяются на случай большего количества множеств.

§ Контрольные вопросы

1. Какие задачи относят к классу комбинаторных?

2. В чем состоит комбинаторный принцип сложения?

3. Как формулируется принцип умножения? Приведите пример.

2.2 Комбинаторные конфигурации

§ Перестановки и подстановки

Пусть дано множество M = {a1,a2,…,an}. Перестановкой элементов множества M называется любой упорядоченный набор из n различных элементов множества M.

Перестановки различаются только порядком входящих в них элементов.

Перестановка элементов множества M может быть задана посредством функции подстановки. Будем определять подстановку как биекцию s : M ® M и задавать ее с помощью матрицы, состоящей из двух строк.

Пусть множество M = {1,2,…,n}, а s(k) =sk, 1 £ sk £ n, k=1,…,n, {s1,s2,…,sn} = {1,2,…,n}. Тогда матрица подстановки s будет иметь вид: [s] º . Очевидно, что перестановка столбцов в этой матрице не меняет задаваемой ею подстановки.

Если заданы две подстановки s и t своими матрицами [s] и [t], то их произведение s×t определяется следующим образом. В матрице [t] столбцы переставляются так, чтобы ее первая строка совпала со второй строкой матрицы [s]: . В итоге получится:

[s]×[t] = =.

Пример 2.5 Если заданы подстановки [s] = , [t] = , то [s×t] =  =  = .

Тождественная подстановка – это такая подстановка e, что e(x)=x "x.

Пример 2.6 [e] = .

Обратная подстановка – это обратная функция, которая всегда существует (подстановка является биекцией). Для получения таблицы обратной подстановки нужно поменять местами строки таблицы исходной подстановки.

Пример 2.7 Для подстановки [s] =  [s–1] = .

Подстановка s называется циклом длины r, если матрицу [s] перестановкой столбцов можно привести к виду:

, т. е. первые r элементов сменяют друг друга, а остальные неподвижны: s(si) = si+1, для 1 £ i £ r –1 и s(sr) = s1.

Пример 2.8 Подстановка s с матрицей [s] = = является циклом (2 5 3 6), а подстановка с матрицей [t] =  циклом не является, т. к. из нее можно выделить два цикла (1 4) и (2 5 6 3).

Утверждение 2.2 Каждую подстановку можно однозначно (с точностью до порядка сомножителей) представить в виде произведения независимых циклов.

В примере 2.7 [s] = (2 5 3 6), [t] =  = (1 4)×(2 5 6 3).

Двухэлементный цикл (i j) называется транспозицией. При транспозиции меняются местами только i-й и j-й элементы, а остальные сохраняют свое положение.

Подстановку удобно изображать графически, соединяя стрелками элементы x и s(x): .

Используя только транспозиции, можно выполнить сортировку множества в определенном порядке (например, в лексикографическом). Известный алгоритм сортировки, основанный на этом принципе, на каждом шаге осуществляет перестановку только двух соседних элементов и носит название «пузырьковой сортировки».

Число перестановок объема n принято обозначать как Pn.

Утверждение 2.3 Число всех перестановок множества M (|M| = n) равно n!

Действительно, на первое место в n-ке можно поставить любой из n элементов множества, на второе место – любой из (n–1) оставшихся, и т. д. Для последнего места остается единственный элемент. Поэтому получаем:
Pn = n×(n–1)×(n–2)×…×2×1 = n!

Пример 2.9 Сколькими способами можно расставить на полке 6 томов книг? Это можно осуществить P6 = 6! = 720 способами.

§ Понятие выборки

Пусть дано множество M = {a1, a2, a3, ..., an}, m £ n. Набор, состоящий из m элементов множества М, называется выборкой объема m из n элементов.

Выборки классифицируются следующим образом:

1) По критерию повторяемости элементов: С возвращением объема (с повторениями) и без возвращения объема (без повторений).

2) По критерию упорядоченности:

Упорядоченные (размещения) и неупорядоченные (сочетания).

Пример 2.10 В ящике n≤10 нумерованных шаров, один достают, записывают номер и бросают обратно. Так делают три раза. Сколько разных трехзначных чисел может получиться? Для подсчета нужны размещения с повторениями.

§ Размещения и сочетания без повторений

Размещениями из n элементов по m называются упорядоченные выборки без повторений элементов множества, которые отличаются одна от другой либо составом элементов, либо порядком их расположения. Размещение можно рассматривать как разнозначную функцию f:{1,2,…,m}®M, для которой f(j)=aij.

Тогда числу размещений из n элементов по m соответствует число инъективных функций или число всех возможных способов разместить n предметов по m позициям («ящикам»), не более чем по одному в «ящик». Это число будем обозначать =A(n,m) (иногда обозначают P(n,m)).

Пример 2.11 Пусть дано множество M={1,2,3,4,5}. Тогда размещениями из 5 элементов по 2 будут, в частности, выборки (1,2), (2,1), (2,4), (4,2) и т. п.

Теорема 2.2 = n×(n–1)×(n–2)×…×(n–m+1).

Доказательство: Размещение m элементов из n имеющихся будем рассматривать как заполнение некоторых m позиций элементами множества M. Для первой позиции существует n различных способов. После того, как первая позиция заполнена, элемент для второй позиции можно выбрать (n–1) способами (комбинаторный принцип умножения). Если процесс продолжить, то после заполнения позиций с 1-й по (m–1)-ю останется (n–m+1) способ для последней, m-й позиции. Перемножив эти числа, получим формулу для .<

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

Пример 2.12 Пусть дано множество M={1,2,3,4,5}. Тогда сочетаниями из 5 элементов по 2 будут выборки (1,2), (2,4), (5,2) и т. п. (Здесь (2,4)~(4,2)…)

Число сочетаний без повторений будем обозначать или C(n,m).

.

Формула для числа размещений из n элементов по m была получена ранее. Если объединить размещения, отличающиеся только порядком элементов и совпадающие по составу, в классы эквивалентности, то получим, что мощность каждого из таких классов m! Тогда число сочетаний будет определяться как C(n,m)= .

Пример 2.13 На тренировках занимаются 8 баскетболистов. Сколько разных пятерок может быть образовано тренером? Т. к. при образовании пятерки важен только ее состав, то достаточно определить пятерок.

§ Размещения и сочетания с повторениями

Размещениями с повторениями (или упорядоченными выборками с возвращениями) из n элементов по k называются упорядоченные наборы из k элементов множества M, в которых элементы множества могут повторяться.

Пример 2.14 Пусть дано множество M={1,2,3,4,5}. Тогда размещениями с повторениями из 5 элементов по 2 будут (1,1), (1,2), (2,1), (2,2), …,(5,1) и т. п. – любые упорядоченные пары из 2 элементов множества М.

Количество всех размещений с повторениями обозначим =Â(n,k). Поскольку в таком наборе из k элементов на каждом из k мест может стоять любой из n элементов исходного множества, число размещений с повторениями равно n×n×…×n = nk. Þ . (2.1)

Пример 2.15 а) Сколько различных трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5? б) А при условии, что ни одна цифра не повторяется? Составить разные числа можно: способами (размещения с повторениями). Если ни одна цифра не должна повторяться, то таких способов будет (размещения без повторений).

В отличие от выборок без повторений, количество выбираемых объектов может быть больше, чем количество типов, т. е. может быть k ³ n. Если вернуться к примеру 2.12 (а), то можно рассматривать и 10-разрядные числа.

Теорема 2.3 (о мощности множества P(M) )

Для конечного множества M |2M| = 2|M|.

Доказательство:

Пусть конечное множество M состоит из n элементов, M = {x1, …, xn}. Сопоставим каждому его подмножеству двоичный вектор длины n. Если xi входит в подмножество, то на i-м месте в этом векторе будет стоять 1, иначе – 0. Поскольку каждая компонента вектора может принимать только значения 0 или 1, а всего таких компонент n, то число различных векторов составит 2n. <

Следствие:

Можно сгенерировать все подмножества конечного множества M, перечислив некоторым способом все наборы из нулей и единиц длины n.

Можно выполнять такую генерацию различными способами (например, все наборы с одной «1», все с двумя «1», …). Это можно сделать наиболее эффективно, используя т. н. бинарный код Грея. Алгоритм построения бинарного кода Грея позволяет генерировать последовательность всех подмножеств n-элементного множества таким образом, что каждое последующее подмножество получается из предыдущего добавлением или удалением единственного элемента. Подробно этот алгоритм рассматривается при выполнении лабораторной работы.

Определим отношение эквивалентности на множестве размещений с повторениями из n элементов по k: (a1,a2,…,ak) ~ (b1,b2,…,bk) Û "cÎM число элементов ai = c совпадает с числом элементов bj = c.

Тогда сочетанием с повторениями из n элементов по k или неупорядоченной выборкой с возвращениями из n элементов по k является множество, которое состоит из элементов, выбранных k раз из множества M, причем один и тот же элемент допускается выбирать повторно.

Пример 2.16 В примере с множеством M={1,2,3,4,5} сочетания с повторениями из 5 элементов по 2 будут отличаться от размещений тем, что одинаковые по составу наборы будут независимо от порядка элементов в них считаться эквивалентными: (1,1), (1,2)~(2,1), (2,2), (5,2) и т. п.

При рассмотрении выборок с повторениями число n более наглядно трактуется как количество имеющихся в наличии типов объектов, а k – количество непосредственно выбираемых объектов. Раз объекты выбираются с повторениями, неважно, каково их реальное количество для каждого из типов. Можно считать их неисчерпаемыми.

Число всех сочетаний с повторениями обозначается =Ĉ(n,k) и вычисляется по формуле: Ĉ(n,k)= (2.2)

Пример 2.17 Пусть в кондитерской продается 10 различных видов пирожных. (n=10 – число типов). Сколькими способами можно купить 12 пирожных? (k=12). Ĉ(10,12)=C(10+12–1,12)=C(21,12)=21!/(12! (10–1)!)= 21!/(12! 9!).

§ Контрольные вопросы

1. Что такое подстановка? Всегда ли существует обратная подстановка?

2. Какая перестановка элементов множества {1,2,3,4} задана функцией подстановки ? Является ли эта подстановка циклом?

3. Что такое транспозиция? В каком алгоритме она используется?

4. Как называется упорядоченная выборка без возвращения объема и по какой формуле вычисляется число различных таких выборок?

5. Сколько различных двузначных чисел можно получить, используя множество {1,2,3,4,5}? Как изменится результат, если цифры в числе не повторяются? Какая выборка (и формула) используется в каждом случае?

6. Сколько двузначных чисел с различной суммой цифр можно получить, используя множество {1,2,3,4,5}? Цифры в числе должны быть разными. В чем отличие от предыдущей задачи? Сочетания или размещения нужно использовать?