Подсчет количеств

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C_n^k -- число всех k -элементных подмножеств n -элементного множества -- можно найти, заполняя таблицу по формулам $\begin{displaymath} \begin{array} {rcll} C_n^0&\!\!\!=\!\!\!&C_n^n = 1 \qquad &... ...{n-1}^{k-1} + C_{n-1}^k \qquad &(n \gt 1, 0 < k < n)\end{array}\end{displaymath}$ или по формуле $\begin{displaymath} C_n^k=\frac{n!}{k!\cdot (n-k)!}.\end{displaymath}$ (Первый способ эффективнее, если надо вычислить много значений C_n^k .)

Приведем другие примеры.

$\scriptstyle{\blacktriangleright}$ 2.7.1 (число разбиений). (Предлагалась на Всесоюзной олимпиаде по программированию 1988 года.) Пусть P(n) -- число разбиений целого положительного n на целые положительные слагаемые (без учета порядка, 1+2 и 2+1 -- одно и то же разбиение). При n=0 положим P(n) = 1 (единственное разбиение не содержит слагаемых). Построить алгоритм вычисления P(n) для заданного n .

Решение. Можно доказать (это нетривиально) такую формулу для P(n) : $\begin{displaymath} \begin{array} {rcl} P(n) &=& P(n-1)+P(n-2)-P(n-5)-P(n-7)+\\ &&\qquad+P(n-12)+P(n-15) +...\end{array}\end{displaymath}$ (знаки у пар членов чередуются, вычитаемые в одной паре равны (3q²-q)/2 и (3q²+q)/2 ).

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

Обозначим через R(n,k) (для $n\geqslant0$ , $k\geqslant0$ ) число разбиений n на целые положительные слагаемые, не превосходящие k . (При этом R(0,k) считаем равным 1 для всех $k\geqslant0$ .) Очевидно, P(n)=R(n,n) . Все разбиения n на слагаемые, не превосходящие k , разобьем на группы в зависимости от максимального слагаемого (обозначим его i ). Число R(n,k) равно сумме (по всем i от 1 до k ) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i . А разбиения n на слагаемые не более k с первым слагаемым, равным i , по существу представляют собой разбиения n-i на слагаемые, не превосходящие i (при $i\leqslant k$ ). Так что $\begin{eqnarray*} R(n,k)&=&\sum\limits_{i=1}^{k} R (n-i,i) \hbox{\ \ \ при $k\leqslant n$};\\ R(n,k)&=&R (n,n) \hbox{\ \ \ при $k \geqslant n$},\end{eqnarray*}$ что позволяет заполнять таблицу значений функции R . $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 2.7.2 (счастливые билеты). (Предлагалась на Всесоюзной олимпиаде по программированию 1989 года). Последовательность из 2n цифр (каждая цифра от до 9 ) называется счастливым билетом, если сумма первых n цифр равна сумме последних n цифр. Найти число счастливых последовательностей данной длины.

Решение. (Сообщено одним из участников олимпиады; к сожалению, не могу указать фамилию, так как работы проверялись зашифрованными.) Рассмотрим более общую задачу: найти число последовательностей, где разница между суммой первых n цифр и суммой последних n цифр равна k ( $k = -9n,\ldots, 9n$ ). Пусть T(n,k) -- число таких последовательностей.

Разобьем множество таких последовательностей на классы в зависимости от разницы между первой и последней цифрами. Если эта разница равна t , то разница между суммами групп из оставшихся n-1 цифр равна k-t . Учитывая, что пар цифр с разностью t бывает 10 - |t| , получаем формулу $\begin{displaymath} T(n,k) = \sum\limits_{t=-9}^{9} (10-\vert t\vert) T(n-1, k-t).\end{displaymath}$ (Некоторые слагаемые могут отсутствовать, так как k-t может быть слишком велико.) $\scriptstyle\blacktriangleleft$

В некоторых случаях ответ удается получить в виде явной формулы.

$\scriptstyle{\blacktriangleright}$ 2.7.3. Доказать, что число Каталана (количество последовательностей длины 2n из n единиц и n минус единиц, в любом начальном отрезке которых не меньше единиц, чем минус единиц) равно C_2nⁿ/(n+1) .

[Указание. Число Каталана есть число ломаных, идущих из (0,0) в (2n,0) шагами (1,1) и (1,-1) , не опускающихся в нижнюю полуплоскость, т.е. разность числа всех ломаных (которое есть C_2nⁿ ) и числа ломаных, опускающихся в нижнюю полуплоскость. Последние можно описать также как ломаные, пересекающие прямую y=-1 . Отразив их кусок справа от самой правой точки пересечения относительно указанной прямой, мы установим взаимно однозначное соответствие между ними и ломаными из (0,0) в (2n,-2) . Остается проверить, что C_2nⁿ-C_2nⁿ⁺¹=C_2nⁿ/(n+1) .] $\blacktriangleleft$

pvv
1/8/1999