Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: Cnk -- число всех k -элементных подмножеств n -элементного множества -- можно найти, заполняя таблицу по формулам или по формуле (Первый способ эффективнее, если надо вычислить много значений Cnk .)
Приведем другие примеры.
2.7.1 (число разбиений). (Предлагалась на Всесоюзной
олимпиаде по программированию 1988 года.) Пусть P(n) -- число
разбиений целого положительного n на целые положительные
слагаемые (без учета порядка, 1+2 и 2+1 -- одно и то же
разбиение). При n=0 положим P(n) = 1 (единственное разбиение не
содержит слагаемых). Построить алгоритм вычисления P(n) для
заданного n .
Однако и без ее использования можно придумать способ вычисления P(n) , который существенно эффективнее перебора и подсчета всех разбиений.
Обозначим через R(n,k) (для , ) число разбиений n на целые положительные слагаемые, не превосходящие k . (При этом R(0,k) считаем равным 1 для всех .) Очевидно, P(n)=R(n,n) . Все разбиения n на слагаемые, не превосходящие k , разобьем на группы в зависимости от максимального слагаемого (обозначим его i ). Число R(n,k) равно сумме (по всем i от 1 до k ) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i . А разбиения n на слагаемые не более k с первым слагаемым, равным i , по существу представляют собой разбиения n-i на слагаемые, не превосходящие i (при ). Так что что позволяет заполнять таблицу значений функции R .
2.7.2 (счастливые билеты). (Предлагалась на
Всесоюзной олимпиаде по программированию 1989 года).
Последовательность из 2n цифр (каждая цифра от до 9 )
называется счастливым билетом, если сумма первых n цифр равна
сумме последних n цифр. Найти число счастливых
последовательностей данной длины.
Разобьем множество таких последовательностей на классы в зависимости от разницы между первой и последней цифрами. Если эта разница равна t , то разница между суммами групп из оставшихся n-1 цифр равна k-t . Учитывая, что пар цифр с разностью t бывает 10 - |t| , получаем формулу (Некоторые слагаемые могут отсутствовать, так как k-t может быть слишком велико.)
В некоторых случаях ответ удается получить в виде явной формулы.
2.7.3. Доказать, что число Каталана (количество
последовательностей длины 2n из n единиц и n минус единиц,
в любом начальном отрезке которых не меньше единиц, чем
минус единиц) равно C2nn/(n+1) .