Множество всех способов ассоциировать композицию бинарных оп

[Maxim19]

Здравствуйте, смотрю тут про ассоциативность, и мне стало интересно, сколькими способами можно ассоциировать n число компонентов. По сути, вопрос в этом: сколькими способами можно расставить правильно скобки(чтоб скобка открывалась и закрывалась и не было случаев $(a)b$ или $(ab)$ ведь это бессмысленно) у последовательного допустим произведения из n элементов. Мне кажется, что тут комбинаторно никак не решить, только перебирать. Может существует формула?

[svv]

Пусть $S_n$ — число способов расставить скобки для $n$ элементов.
Рассмотрим для примера $n=5$ элементов $abcde$. Скобки можно расставить многими способами, например, $((ab)c)(de)$.
Выражение $((ab)c)(de)$ не определяет, какая из операций $ab$, $de$ выполняется раньше. Но всегда определено однозначно, какая операция совершается последней — в данном случае это операция с операндами $(ab)c$ и $de$. Пусть известно, что в левый и правый операнды последней операции входят соответственно $k$ первых и $n-k$ последних элементов (в нашем примере $k=3$ и $n-k=2$). Тогда в левом операнде скобки можно расставить $S_k$ способами, а в правом $S_{n-k}$ способами. Всего $S_kS_{n-k}$ способов. Это нужно просуммировать по всем возможным значениям $k$ от $1$ до $n-1$. Получаем рекуррентную формулу
$S_1=1$
$S_n=\sum\limits_{k=1}^{n-1} S_k S_{n-k}$
Программа, составленная по этой формуле, выдаёт последовательность $1,1,2,5,14,42,132,429,...$

Эту последовательность ищем на сайте OEIS и находим — это A000108. Оказывается, это числа Каталана, которые имеют много комбинаторных интерпретаций, в том числе скобочную.

[Maxim19]

А разве мы не перебираем одно и то же? Например для случая $a(bc)def$ можно смотреть разделения хоть 1 5, 3 3, 4 2, 5 1

[svv]

Надо ещё уточнить, что если $C_n$ — $n$-е число Каталана, то при наших правилах расстановки скобок $S_n=C_{n-1}$.

Maxim19 в сообщении #1590226 писал(а):

Например для случая $a(bc)def$ можно смотреть разделения хоть 1 5, 3 3, 4 2, 5 1

Я исходил из того, что скобки должны полностью устранять неоднозначности. А $a(bc)def$ можно "доопределить" и до $(a(bc))((de)f)$ (3+3), и до $((a(bc))d)(ef)$ (4+2). Так как это разные выражения в отсутствие ассоциативности, запись $a(bc)def$ незаконна.

[Maxim19]

А что там про перебирание одних и тех же элементов? Я что-то не понял

-- 19.04.2023, 02:34 --

Я почитал про эти числа. Так там скобки то без знаков между. Поэтому и не подходит

-- 19.04.2023, 02:38 --

svv
Понятно. А про мой случай ничего нет?

-- 19.04.2023, 02:39 --

В моём случае не должно быть только $a(b)c$ и $(abc)$

-- 19.04.2023, 02:44 --

Ну мой случай тоже можно рекуррентной формулой записать. Пусть S_n - количество такого для n элементов. S_n=2S_{n-1} - 2

[svv]

Давайте, действительно, договоримся о том, какие расстановки мы считаем законными.
Для $n=3$ есть две расстановки: $(ab)c$ и $a(bc)$. Они полностью регламентируют, что надо делать с операндами в отсутствие ассоциативности, и это, по-моему, обязательное требование.
Для $n=4$ есть пять расстановок:
$a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d, ((ab)c)d$
Согласны?

[Maxim19]

Ошибка, вот другая версия $S_n=S_{n-1}+\sum\limits_{k=2}^{n-1}S_{k}S_{n-k}$

-- 19.04.2023, 02:51 --

svv
Да согласен.

[svv]

Всё это ещё очевидным образом переводится на язык бинарных деревьев.
По правильной расстановке скобок однозначно строится бинарное дерево.

[Maxim19]

Думаю, что рекуррентное соотношение выше определяет эти числа. Я вывел так: пусть не ставили в самом начале скобку, тогда сводится к такому же, но на одну букву из строки меньше, а если поставили, то в той сумме смотрим, где закрываем

-- 19.04.2023, 02:58 --

$S_n=S_{n-1}+\sum\limits_{k=2}^{n-1}S_{k}S_{n-k}$
Я правильно вывел рекуррентное соотношение?

[svv]

Maxim19 в сообщении #1590231 писал(а):

вот другая версия $S_n=S_{n-1}+\sum\limits_{k=2}^{n-1}S_{k}S_{n-k}$

Правильно. Но поскольку $S_1=1$, это можно записать как
$S_n=S_1S_{n-1}+\sum\limits_{k=2}^{n-1}S_{k}S_{n-k}=\sum\limits_{k=1}^{n-1}S_{k}S_{n-k}$
А это то же самое, что я написал.

[Maxim19]

Что то в голове не укладывается. Ваше же решение несколько раз считает случай, который я выше показал. Как тогда это получается?

[svv]

Случай $a(bc)def$? Тут надо ещё добавить скобки, чтобы это получило однозначную интерпретацию. А сделать это можно многими способами.

[Maxim19]

Нет, мы же вроде вначале обговорили, что смотрим именно способы расставить скобки вне контекстов. Просто в последовательности из n символов поставить правильно скобки. То есть $a(bc)df$ и $a((bc)d)f$ это разные случаи

[svv]

Возьмём более простой случай $a(bc)d$. Тут уже не хватает скобок. Ведь в отсутствие ассоциативности могут быть разные результаты для $(a(bc))d$ и $a((bc)d)$.
Для выражения $a(bc)d$ нельзя однозначно нарисовать бинарное дерево.

[Maxim19]

Я считал рекуррентно именно из этого условия. Поэтому удивился, что получилось одно и то же

-- 19.04.2023, 03:09 --

Я понял, что сам же своим способом так же, как и Вы считал несколько раз. Придётся думать ещё