Истории давние и недавние

Комбинаторика у Плутарха

Обедая как-то раз с Р. Стэнли в Стенфорде, я услышал его удивительный рассказ о комбинаторике древних. Плутарх в «Застольных беседах» пишет: «Хрисипп (ни сам не исследовав дела тщательно, ни разузнав истину у людей сведущих) говорит, что число комбинаций, которые можно получить из десяти предложений, превосходит один миллион. На это возразил Гиппарх, указав, что одно утвердительное предложение охватывает включённых в него 103 049, а отрицательное — 309 952».

Стэнли сосчитал, что первое шестизначное число — это число скобочных символов с 10 буквами (внутри каждой скобки может стоять любое число членов, например, символ (а, (b, с), (d, е, f), ((q, h), (i, j))) допустим). А что такое «отрицательная сторона» — неясно!

Вернувшись в Москву, я рассказал участникам своего семинара в качестве задачи предложенный Стэнли вопрос о расшифровке слов «на отрицательной стороне». Уже через несколько дней М. Казарян и С. Ландо нашли ответ (они использовали компьютер, чтобы отвергнуть конкурирующие гипотезы): «на отрицательной стороне» стоят сложные предложения, в котором одно из предложений (либо простое, либо сложное) отрицается (например, для трёхчленных предложений, пригодны (не a, (d, с)), (а, не (d, с)), не (а, (d, с)), если мне не изменяет память). Полная теория опубликована Казаряном и Ландо в American Mathematical Monthly совместно с учениками Стэнли, получившими тот же ответ (расходящийся, впрочем, с указанным Плутархом на 2 единицы — видимо, у Плутарха опечатка). Вычисления требовали решения рекуррентных уравнений с сорока членами — видимо, во времена Плутарха такие вычисления никого не смущали.