Глава 2. Общие правила (принципы) комбинаторики
2.1. Правило сложения (суммы)
Формулировка правила сложения (суммы) применительно к двум множествам объектов: если некоторый объект a можно выбрать M способами, а другой объект b можно выбрать N способами, причем ни один способ выбора объекта a не совпадает с каким-нибудь способом выбора объекта b, то выбор либо a, либо b можно осуществить M + N способами.
Из формулировки следует - применение данного правила возможно в ситуациях, когда множество C всех изучаемых комбинаций (объектов) удается разбить на два непересекающихся класса A, B, т.е. представить в виде разбиения S = { A, B } (A∙B = Ø). Тогда искомое число | C | комбинаций и числа | A | , | B | комбинаций, содержащихся в классах A и B соответственно, будут связаны равенством
| C | = | A | + | B |= | A | + | B | , ( A∙B= Ø ) . ( 2.1 )
Обобщение правила сложения для произвольного числа классов: если множество U возможных комбинаций представлено в виде разбиения S = { A,B,C,...,G }, то
| U |= | A | + | B | + | C | + … + | G | . ( 2.2 )
Основная трудность использования правила сложения при решении конкретной комбинаторной задачи состоит, очевидно, в построении разбиения. Иногда это сделать достаточно просто (классы разбиения вытекают из рассматриваемой комбинаторной ситуации).
Так, если поток П студентов (например, второго курса), обучающихся по одной из специальностей, состоит из двух групп Г1, Г2 с численностью | Г1 | = 28, | Г2 | = 26, то число способов выбора одного студента из всего потока П (т.е. обучающегося либо в группе Г1, либо в группе Г2 ) будет в соответствии с формулой (2.1) равно | П | = | Г1| + | Г2 | = 54.
Справедливость равенства очевидна, так как система множеств S = { Г1,Г2 } является разбиением потока П (любой студент потока, с одной стороны, не может обучаться одновременно в двух группах и, с другой стороны, он входит в списочный состав одной из групп потока). К сожалению, такие простые комбинаторные ситуации встречаются достаточно редко.
Довольно часто построение разбиения является только начальным (хотя и очень важным) этапом решения комбинаторной задачи. Фактически разбиение является предпосылкой (см. пример 2.1) для получения рекуррентного уравнения, описывающего исследуемую комбинаторную ситуацию (динамику ее изменения, развития).
С помощью рекуррентных уравнений решается, в частности, целый ряд задач, связанных с разбиением натуральных чисел на слагаемые. Большой набор такого рода задач и примеров их решения предложен в [ 1 ]. Одна из таких задач формулируется следующим образом:
Сколькими способами можно разбить натуральное число N на n слагаемых, если, во-первых, любое из слагаемых равно одному из k элементов заданного множества K = { m,l,…,s } (| K | = k ) натуральных чисел и, во-вторых, способы разбиения, отличающиеся порядком слагаемых, считаются различными ?
Если обозначить множество способов разбиения произвольного натурального числа J на j слагаемых через F (j,J) , а его мощность | F (j,J) | – через f (j,J), то в качестве базового соотношения, предназначенного для решения сформулированной задачи, можно использовать равенство
f (n,N) = f (n-1,N-m) + f (n-1,N-l) +…+ f (n-1,N-s), (2.3)
в котором
f (n,N) – искомое число различных способов разбиения, определяющее мощность полного множества F (n,N) всевозможных разбиений;
f (n-1,N-i) – число способов разбиения, в которых в качестве первого слагаемого фигурирует число i є K;
n-1, N-i – аргументы, отражающие следующую ситуацию: после того, как первое слагаемое i выбрано, количество слагаемых, на которые разбивается оставшаяся часть (N-i) числа N, должно быть равно (n-1), т.е. должно уменьшиться на единицу.
Обоснование формулы (2.3). Запишем для полного множества F (n,N) способов разбиения аналогичную (2.3) сумму
F (n,N) = F (n-1,N-m) + F (n-1,N-l) +…+ F (n-1,N-s),
где F (n-1,N-i) – подмножество способов разбиения, в которых в качестве первого слагаемого фигурирует число i є K.
Так как в качестве первого слагаемого используются все числа из множества К (и только они), то справедливость записанной суммы очевидна. Не вызывает также сомнений тот факт, что система подмножеств
S = { F (n-1,N-m), F (n-1,N-l), …, F (n-1,N-s) },
объединение которых определяет множество F (n,N), будет представлять собой разбиение этого множества:
каждый способ разбиения числа N на слагаемые принадлежит одному из подмножеств системы - классу разбиения;
подмножества (классы) попарно не пересекаются, так как составляющие их способы разбиения имеют разные первые слагаемые.
Применяя формулу (2.2) правила сложения к элементам системы S, получим равенство (2.3).
Для того, чтобы воспользоваться формулой (2.3), которая фактически является рекуррентным соотношением, связывающим число способов разбиения на n слагаемых с числом способов разбиения на (n-1) слагаемое, необходимо иметь начальные условия.
Так как любое число представить в виде одного слагаемого можно, очевидно, единственным способом (причем по условиям задачи это слагаемое должно принадлежать заданному множеству K), то для рассматриваемой комбинаторной ситуации начальные условия можно записать следующим образом:
f (1,i) = 1, если i є K; f (1,i) = 0, если i K. (2.4)
Порядок применения формулы (2.3) :
1. Используя заданное множество K допустимых значений слагаемых, записываем в виде суммы (2.3) исходное выражение для искомого числа способов f (n,N) .
2. Записываем аналогичные выражения для всех составляющих (слагаемых) f (n-1, N-i) (i є K) и подставляем их в выражение для f (n,N) .
3. Преобразуем полученную сумму, приводя подобные члены. В результате будем иметь выражение для f (n,N) через некоторый набор составляющих f (n-2,J).
4. Повторяем пункты 2, 3 до тех пор, пока не получим выражение для f (n,N) через составляющие f (1,J).
5. Применяя начальные условия (2.4), вычисляем последовательно f (2,J), f (3,J),…,f (n-1,J); подставив их в исходное выражение (2.3), находим искомую величину f (n,N).
Решение одной из задач на разбиение натурального числа на натуральные слагаемые рассматривается в примере 2.2.