Sergei Nickolaev написал(а) к Alexander Hohryakov в Apr 23 13:44:28 по местному времени:

Привет, Alexander!

SN>> 4. Докажите, что способов расстановки скобок (указывающих порядок
SN>> действий) в неассоциативном произведении из n элементов столько
SN>> же, сколько способов разбить выпуклый (n + 1)-угольник на
SN>> треугольники непересекающимися диагоналями. (Для произведения
SN>> трёх множителей есть два варианта (ab)c и a(bc); с другой
SN>> стороны, есть два способа разрезать четырёхугольник на два
SN>> треугольника, проведя диагональ. Для произведения четырёх
SN>> сомножителей и для пятиугольника имеется по 5 вариантов.)

AН> Глянув на формулу с факториалами, понял, что сходу мне эту задачу не
AН> решить и удалился думать.

Я доразобрался с этой задачей. Никаких факториалов не требуется :-).
Сначала необходимые пояснения: автор задачи явно предполагал, что задачу будут решать более-менее математики, для остальных некоторые вещи нужно рассказать. А именно, что автор понимает под "способами расстановки скобок, указывающих порядок действий, в неассоциативном произведении из n элементов".

Термин "произведение" здесь использован только в том смысле, что символ операции не пишется (реальные произведения так часто и записываются).
"Неассоциативное" означает, что строки с разной расстановкой скобок считаются разными. Скажем, обычное произведение всех более-менее привычных чисел - ассоциативно, (ab)c и a(bc) дают одинаковый результат и выражения не считаются разными. А операция "разность" для множеств - неассоциативная, выражения
(A \ B) \ C и A \ (B \ C) - разные, то есть могут давать разные результаты.

В этой задаче операция - совершенно абстрактная, про нее известно только то, что она неассоциативна.

Некоторые способы расстановки скобок просто бессмысленны, они не рассматриваются:
1. Пустая пара скобок ().
2. Неуравновешенный комплект: число открывающих скобок не равно числу закрывающих.

Существенно то, что некоторые варианты расстановки скобок не влияют на порядок выполнения операций, их следует исключить из рассмотрения.
1. Пара скобок вокруг всего выражения не меняет порядка операций. Выражение
((ab)c) с точки зрения порядка операций ничем не отличается от (ab)c.
Внешнюю пару скобок исключаем из рассмотрения.
2. Скобки с одним элементом внутри - исключаем. (ab)(c) не отличается от (ab)c.
3. Кратные скобки исключаем по тем же причинам. ((ab))c не отличается от (ab)c.

Есть такая вещь, как порядок выполнения операций "по умолчанию". Часто допускается писать abc, подразумевая выполнение операций слева направо. Исключаем. Требуем явного указания порядка, то есть вместо abc должно быть (ab)c. Обеспечение этого требования приводит к следующим правилам:
1. Все выражения должны иметь вид:
ЭЭ или СЭ или ЭС или СС (Э - элемент, С - скобки с содержимым).
2. Скобки с содержимым должны иметь вид (ЭЭ) или (СЭ) или (ЭС) или (СС).

Примеры:
(ab)c(de) - неправильное выражение, правильным будет ((ab)c)(de)
(abc)de - неправильное выражение, правильным будет (((ab)c)d)e

Еще существенная вещь - все элементы в выражении различны. Автор об этом не упоминает, но без такого условия - не выйдет.

Теперь идея доказательства (без ряда подробностей, остается несколько задач для решения):
Пусть в выражении будет n элементов a[1], a[2], ..., a[n]. Номера соответствуют положению элементов в выражении.
Берем выпуклый (n+1)-угольник (для рисования картинки лучше взять похожий на правильный). Выбираем произвольную вершину и пририсовываем к ней номер 1. В том направлении (по часовой стрелке или против) которое нам нравится последовательно нумеруем вершины. Диагональ из вершины i в вершину k обозначим как пару <i,k>. Чтобы диагональ имела одно обозначение (а не два), будем соблюдать условие i<k. На самом деле, для реальной диагонали будет выполняться условие i<k-1. Диагонали <i,k> сопоставим пару скобок в выражении: открывающая скобка перед a[i] и закрывающая скобка после a[k-1]. Такое соответствие взаимно-однозначно и в нем не появляются бессмысленные и не влияющие на порядок выполнения операций скобки (задача - доказать) и невозможные диагонали (задача - доказать). Если мы выберем какое-нибудь разбиение многоугольника на треугольники непересекающимися диагоналями, то соответствующее расположение скобок даст "правильное" выражение (задача - доказать); если мы возьмем любое "правильное" выражение, соответствующие диагонали не будут пересекаться и разбьют многоугольник на треугольники (задача - доказать).

С уважением - Sergei
--- GoldED+/W32-MINGW 1.1.5-b20120519 (Kubik 3.0)