Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1999/05/03.pdf Дата изменения: Fri Dec 23 19:25:25 2005 Дата индексирования: Tue Oct 2 00:09:34 2012 Кодировка: Windows-1251 Поисковые слова: ngc 1232

ЧТО

ТАКОЕ

КОМБИНАТОРИКА

3
(закодированных каким-либо образом). Число вариантов при этом превращается в число записей. А это уже нечто материальное и может интерпретироваться, например, как количество ячеек машинной памяти. Такая мысленная 'материализация' не имеет, конечно, ничего общего с решением задачи прямым подсчетом, требующим отнюдь не мысленного, а реального составления перечня. Да и речь идет не о решении, а лишь о лучшем понимании постановки задачи. Итак, Главное Правило Комбинаторики: прежде чем подсчитывать число различных вариантов, необходимо точно выяснить смысл слов 'различные варианты'. Само по себе это правило не позволит решить ни одной задачи, зато поможет избежать путаницы и недоразумений при решении множества задач.

Нельзя ли просто пересчитать?
Этот вопрос напрашивается. Если интересующих нас объектов конечное число, почему бы не составить полный их перечень и попросту пересчитать безо всяких там 'комбинаторных рассуждений'? Рассмотрим пример. Задача 1. Сколько существует различных двоичных (т.е. состоящих только из нулей и единиц) последовательностей длины m = 2? Перечень составляется без всякого труда: (0,0), (0,1), (1,0), (1,1). Задача, как видим, оказалась проста, как дважды два четыре (в данном случае буквально). Но если тем же методом решать задачу при m = 10, уйдет куда больше времени (в перечень войдет свыше тысячи последовательностей). При m = 20 осилить такой перечень сможет лишь компьютер. Ну а при m = 1000 окажутся бессильными все компьютеры мира, вместе взятые. Правда, в принципе такой перебор все же возможен (если отвлечься от таких 'мелочей', как миллиарды лет машинного времени). А как быть, если надо найти число двоичных последовательностей произвольной длины m? Здесь перебор невозможен в принципе. А между тем очень простые соображения общего характера позволяют мгновенно дать ответ: искомое число есть 2m . Это сразу вытекает из принципа умножения (см. ниже). Читатель, знакомый с двоичной системой счисления, может здесь обойтись и без этого принципа: все наши последовательности это записи в двоичной системе чисел 0, 1, 2, ..., 2m 1 (записи, содержащие менее m разрядов, дополняются нулями впереди). Данный пример ясно показывает мощь общих комбинаторных соображений по сравнению с примитивным перебором. Не следует, конечно, думать, что все комбинаторные задачи можно решить так же мгновенно. Рассмотренная задача относилась к числу простейших. В комбинаторике много трудных задач, а есть и такие, решения которых еще никому не удалось найти.
1*

Сколько вариантов у понятия 'вариант'
Теперь мы хотим предупредить об одной особенности комбинаторики: в ней исключительно большую роль играет точная формулировка (и точное понимание) задачи. Именно с этим связано большинство ошибок начинающих, да и не только начинающих; в некоторых задачниках можно встретить задачи, некорректные ввиду неопределенности формулировки. Разумеется, никакой неопределенности не возникает, когда речь идет о том, чтобы подсчитать число учеников в классе или число окон в комнате. Но когда речь идет о числе различных вариантов (или способов), ситуация бывает куда менее определенной. Приведем пример. Задача 2. Сколькими способами можно распределить три конфеты между тремя лицами? Тут впору искать ответ на другой вопрос: сколькими способами можно понимать эту задачу. В зависимости от ответа на него возможны шесть разных ответов на поставленный вопрос 1, 3, 5, 6, 10, 27! Первый источник неопределенности термин 'распределить'. Можно ли сказать, что конфеты распределены между тремя лицами, если, скажем, все они отданы одному? Примем, так сказать, социально-справедливый вариант распределения. Если же понимать распределение в широком смысле слова, по-прежнему считая конфеты тождественными, получаем 10 вариантов 3 варианта типа (3,0,0) (когда все конфеты отдаются кому-либо из трех) + 6 вариантов типа (2,1,0) + 1 вариант типа (1,1,1). Если же вдобавок и все конфеты различны, получаем максимальное 3 число 3 = 27 вариантов. Другие ответы предоставляем читателю получить самостоятельно. Отметим лишь, что цифры 3 и 5 получаются, если считать неразличимыми людей, что не особенно естественно (но становится вполне естественным при замене людей тремя одинаковыми коробками). Некоторая расплывчатость понятия о числе вариантов связана с тем, что варианты умозрительные понятия, их нельзя увидеть непосредственно (если нет перечня). Полезно поэтому мысленно представить себе полный перечень различных вариантов

Принцип сложения
Мы обсудили некоторые общие особенности комбинаторики. Теперь можно переходить к конкретным способам подсчета. Начнем с простейшего. Если все варианты делятся на k взаимоисключающих типов, причем имеется n1 вариантов 1-го типа, n2 вариантов 2-го типа, ..., nk вариантов k-го типа, то общее число вариантов есть n = n1 + n2 + ... + nk . Мы фактически уже применяли этот 'принцип сложения'. Он совершенно очевиден и выделен, главным образом, для того, чтобы читатель мог сопоставить его с 'принципом умножения' (см. ниже).

Кортежи, или упорядоченные наборы
Кортеж длины m
a1, a2 ,..., a
m

(1)

это просто упорядоченный набор (или, что то же, конечная последовательность) m элементов произвольной природы, при этом ak называется k-й компонентой кортежа (1). Если все компоненты числа, то кортеж длины m называется также mмерным вектором. Если все компоненты буквы некоторого алфавита, то кортеж длины m называется также m-буквенным словом в этом алфавите. Лингвистическая сторона дела здесь не учитывается; так, ЙЙЬЪ 4-буквенное слово в русском алфави-