Об одной комбинаторной задаче

Квант 1979, №9 с. 19-20 Тег ZY85

А. Ширцов

Как вы хорошо знаете, общное умножение ассоциативно: $(ab)c=a(bc)$ для любых чисел. Ассоциативно и умножение функций: $(f(x)g(x))z(x)=f(x)(g(x)z(x))$ .

Однако в ряде разделов математики рассматривают неассоциативные «умножения». Если умножение неассоциативно, приходит только娥аться скобками, чтобы указать порядок действия, подобно тому, как приходит именно娥аться в школьных примерах, содержащих сложение и умножение или деление.

Рассмотрим слова $a_1a_2a_3...a_n$ . Сколькими способами можно расставить в нем скобки, чтобы можно было вычислить неассоциативное «произведение» этих «букв»? Обозначим число таких способов через $\varphi(n)$ . Ясно, что $\varphi(1)=1$ и $\varphi(2)=1$ . Для трехбуквенного слова $a_1a_2a_3$ возможно две «хорошие» рассстановки скобок: $(a_1a_2)a_3$ и $a_1(a_2a_3)$ . Для четырехбуквенного — таких расстановок пять: $a_1(a_2(a_3a_4))$ , $a_1((a_2a_3)a_4)$ , $(a_1a_2)(a_3a_4)$ , $((a_1a_2)a_3)a_4$ и $(a_1(a_2a_3))a_4$ . Поэтому $\varphi(3)=2$ , $\varphi(4)=5$ . (Показите самостояльно, что $\varphi(5)=14$ , $\varphi(6)=42$ .) Числа $\varphi(n)$ называются числами Каталана. В «Кванте» № 7 за 1978 год подробно расссказывалось об этих числах. Упомянуто там и о связи между этим числами и расстановками скобок. В этой заметке я хочу привести простое доказательство следующей формулы для чисел

$\varphi(n) = \frac{1}{2n-1} C_{2n-1}^{n-1}.$ (*)

(Из этой формулы следует, что число $\frac{1}{2n-1} C_{2n-1}^{n-1}$ — целое при всех $n$ .)

Для начала мне нужно ввести понятие циклических сравнимых слов. Проще начать с примера. Из символов $a_1, a_2, a_3$ , взятых по одному, можно образовать два класса циклических сравнимых слов:

$\{a_1a_2a_3, a_2a_3a_1, a_3a_1a_2\}$

$\{a_1a_3a_2, a_3a_2a_1, a_2a_1a_3\}.$

Чтобы получить эти классы, нужно символы $a_1, a_2, a_3$ написать по кругу, как на циферблате часов, а затем начинать запись по часовой стрелке с любого из символов.

Дадим теперь точное определение. Два слова $A$ и $B$ называются циклическими сравнимыми, если

$A = b_1b_2...b_kb_{k+1}...b_n$

$B = b_kb_{k+1}...b_nb_1b_2...b_{k-1}.$

Поступим теперь следующим образом. Каждый неассоциативному слову (так мы будем называть слова с правильно расставленными скобками) из символов $a_1, a_2, ..., a_n$ поставим в соответствие ассоциативное слово (то есть слово без скобок) из символов $a_1, ..., a_n$ , $p$ по следующему правилу: $a_i \rightarrow a_i$ и, если $u \rightarrow A$ , $v \rightarrow B$ , то $u \cdot v \rightarrow ABp$ . Например, $a_1a_2 \rightarrow a_1a_2p$ , $a_1(a_2a_3) \rightarrow a_1a_2a_3pp$ , $a_1((a_2a_3)a_4) \rightarrow a_1a_2a_3pa_4pp$ , $(a_1a_2)(a_3a_4) \rightarrow a_1a_2pa_3a_4pp$ .

Легко понять, что каждому неассоциативному слову длины $k$ от символов $a_i$ соответствует некоторое ассоциативное слово длины $2k-1$ , в котором $p$ входит $k-1$ раз. Обратное, конечное, неверное. Например, слова $ppa_1a_2a_3$ или $a_1pa_2a_3p$ не могут быть получены с помощью описанной процедуры. Однако справедливо следующее утверждение:

Лемma. Пусть $A$ — некоморое ассоциативное слово длины $2n-1$ , со-

держание каждой из символов $a_i$ ( $i=1, 2, \dots, n$ ) по одному разу и символ $p$ $n-1$ раз. Тогда существует одно и только одно циклический сравнимое с словом $A$ (возможно, оно само) ассоциативное слово, которое соответствует некоторому неассоциативному слову длины $n$ из символов $a_1, a_2, \dots, a_n$ .

По своему характера эта лемма сродни многим простым задачам, публиковавшимся в «Кванте». Я приведу ее доказательство лишь для полотны изложения.

Очевидно, в классе циклических сравнимых с $A$ слов имеет смысл расматривать лишь те, которые не начинаются с символа $p$ , но кончаются с символом $p$ . Такие, конечно, существуют. В таком $A_1$ — это тоже легко понять — найдется подслово (часть слова) вида $a_i a_j p$ , соответствующое неассоциативному слову $a_i a_j$ . Обозначим этот кусочек слова $A_1$ через $a_i$ . Мы получили слово, в котором входят $a_1, a_2, \dots, a_n$ , не входит $a_j$ , а символ $p$ входит уже в количество $n-2$ раз. Из простой индекции по числу $n$ и следует доказательство леммы.

Основанием для индукции является рассмотрение слов типа $a_1 a_2 p$ или аналогичных.

Итак, лемма доказана. Тепер формула (*) становится почти очевидной. В самом деле, среди $2n-1$ мест мы можем в точности $C_{2n-1}^{n-1}$ способами выбрать расстановку $n-1$ символа $p$ , а на оставшиеся места расставить символы $a_1, a_2, \dots, a_n$ таким образом, чтобы в циклическом сравнимом «хорошем» ассоциативном слове индексы $y_i$ шли в порядке их последовательного возрастания от 1 до $n$ . Так как в каждом классе циклических сравнимых слов длины $2n-1$ оказетсяровно $2n-1$ раз и члены их (почему?) элементов, $\varphi(n) = \frac{1}{2n-1} C_{2n-1}^{n-1}$ .

Формула (*) доказана.

В заключение я хочу расссказать об интерсейной истории, произведенной с этой задачей.

Популярный американский математический журнал «The American Mathematical Monthly» (для краткости AMM) в 1935 году опубликовал проблему известного математика Г. Биркгофа (№ 3674) в следующей формулировке:

Показать, что для всякого положительного к выражение $\varphi(k) = \frac{1}{2k-1} C_{2k-1}^{k-1}$ есть целое число; доказать справедливость рекуррентного соотношения

$\varphi(k) = \varphi(1) \varphi(k-1) + \varphi(2) \varphi(k-2) + \dots + \varphi(k-1)\varphi(1)$ .

Легко понять, что Г. Биркгоф, занимаясь близкими вопросами, пришел к формуле (*) эмпирически. Рекуррентное же соответствие, при ближайшем рассмотрении, оченьindo.

Эта проблема была решена с помощью достаточно сильных средств математического анализа в октября 1935 года.

Позотому мне показалось весы страницы в том же журнале за 1941 г. увидеть напечатанной пробему (№ 3954) другого хорошего известного математика О. Оре:

Из трех элементов $a, b, c$ , заданы в указанном порядке, можно составить $\varphi(3)=2$ произведение $(ab)c$ и $a(bc)$ , если не считать, что закон ассоциативности имеет место. Аналоецно, из четырех элементов $a, b, c, d$ можно составить $\varphi(4)=5$ произведение

$[(ab)c]d, [a(bc)]d, a[(bc)d], a[b(cd)], (ab)(cd)$ .

Найти общее выражение $\varphi(n)$ для $n$ множеелей.

В такой формулировке эта задача была решена в том же 1941 г. Я с решением не знакомился, так как оно оченьindo вытекало из простой ссылки на предыдущего задачу.

Новот что интересно. В 1957 году редакция AMM решила посвятить отдельный номер журнала памятки О. Данкела, руководившего много лет отделом проблем. Жюри, составленное из 25 известных математических проблем из числа направанных в этом журнале для включения их в соответствующий выпуск. К моему удивлению, обе эти задачи, неависимо, оказались среди выборных.

(Окончание см. на с. 32)