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

Что такое комбинаторика
ЧТО ТАКОЕ КОМБИНАТОРИКА

7

А.ЛЕВИН
Что такое счастье
Вернемся к уравнению (6) x1 + x2 + K + xn = m . Уместно посмотреть, что произойдет, если игнорировать порядок слагаемых. Для определенности будем считать слагаемые положительными и рассмотрим следующую задачу. Задача 13. Сколькими способами можно разбить число m на n ( m) натуральных слагаемых, если разбиения, отличающиеся лишь порядком слагаемых, считаются тождественными? Решили? Нет? Это и неудивительно: задача не решается в привычном смысле. Хотелось бы, чтобы, как и ранее, ответ давался в виде явно выписываемой функции f m, n . Но на этот раз сколько-нибудь 'явно' выразить ответ через параметры задачи m, n не удается. Разумеется, для любых конкретных чисел m, n мы в принципе можем вычислить численное значение f m, n хотя бы перебором, на худой конец. Например, легко убедиться, что f 8, 3 = 5, ибо существует 5 способов разбиения (с точностью до порядка) числа 8 на 3 слагаемых: 1 + 1 + 6, 1 + 2 + 5, 2 + 2 + 4, 1 + 3 + 4, 2 + 3 + 3. С помощью компьютера можно быстро вычислять и такие значения, как, например, f 100, 10 . Только перебором не стоит заниматься, существует куда более эффективный алгоритм. Полезно заметить, что отождествление разбиений, отличающихся порядком, можно заменить требованием упорядоченности xi , скажем, в неубывающем порядке: темы, состоящий из уравнения (6) и неравенств (8). Такая переформулировка удобна во многих отношениях; она может помочь и при выборе эффективного алгоритма вычисления f. Разработка и программная реализация алгоритма а заодно и вычисление f 100, 10 предоставляется читателю в качестве полезного и интересного самостоятельного задания. Заметим лишь, что алгоритм будет носить рекуррентный характер от меньших значений параметров к бульшим. Относится ли данное задание к комбинаторике или к информатике? К тому и к другому. Можно назвать это компьютерной комбинаторикой. Жаль, что в русском языке пока нет слова 'алгоритмика'. Оно было бы кстати. (Впрочем, скорее всего, оно появится в недалеком будущем). Разумеется, для вычислений с n! при заданном n также можно написать программу (причем число операций будет расти вместе с n). Почему же мы относим выражения n!, n и т.п. к 'явным' аналитичесm ким выражениям в отличие от f m, n ? Обозначения здесь ни при чем: ведь при желании можно и для f m, n придумать какое-нибудь специальное обозначение (скажем, m?n). Суть в том, что особая простота 'факториального' алгоритма и в самом деле позволяет обращаться с факториалами как с аналитическими выражениями подставлять в формулы и проводить преобразования. Об этом наглядно свидетельствует, например, приводимая ниже выкладка (15). С произвольными программами такое, разумеется, невозможно. При первом знакомстве с комбинаторикой 'нерешабельные' задачи обычно не затрагиваются. Мы нарушили эту традицию, чтобы читатель с самого начала имел правильное представление о предмете. Он должен почувствовать, что наличие 'явного' ответа для комбинаторной задачи с параметрами (т.е. для задачи, в формулировку которой входят буквы) это удача, счастливый случай, который надо ценить. Такие случаи осуществляются в комбинаторике довольно часто. Но, к сожалению, не всегда.

b

g

b

g

Знак 5
Те, кто знаком с этим обозначением, могут данный пункт пропустить. Они ведь и так знают, что эта прописная греческая буква (сигма) является общепринятым символом суммирования. Обычно суммирование идет по одному или нескольким целочисленным индексам. Если индекс пробегает значения 'от и до', то нижняя и верхняя границы указываются, соответственно, внизу и вверху; в более сложных случаях область изменения индексов обычно указывается под буквой . Вот несколько примеров: 1) 4) 6)

bg

bg

bg

FI GH JK bg bg


j= 0 k =1

n

ak ; 2 ) aq =
j


k

ak ; 3 )


k =1

n

ak = m ; x

a 1-q

; 5) .

b

g

n1 ,n2 ,n3 0 n1 + n2 + n3 = 2



1 n1 ! n2 ! n3 !

1 i < j 4



i, j

;

b1 g

x1 x2 K xn .

Таким образом, f m, n есть число решений в натуральных числах сисОкончание. Начало см. в 'Кванте' ?5.
2*

bg

(8)

В случае 1) записана сумма a1 + + a2 + + an (здесь легко заменить многоточием, но так дело обстоит не всегда). В 2) указан индекс суммирования k, но не его границы; они, следовательно, должны быть ясны из контекста. В 3) читатель узнает уже знакомое нам 'уравнение дележа' (6), а в 4) формулу для суммы членов геометрической прогрессии (при |q| < 1); здесь число слагаемых, очевидно, бесконечно. В 5) записано выражение x12 + x13 + x14 + x23 + x24 + x34 ,