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

[svv]

Так Вы хотите считать и такие расстановки, которые не определяют результат однозначно? То есть допускают неоднозначность интерпретации?

[Maxim19]

Всё верно. Вас смутило про ассоциативность - моя вина. Я просто рассказал предысторию этого вопроса

[svv]

Ок, значит,
1) пара скобок не должна окружать 1 элемент $(a)$ и 0 элементов $()$ и
2) пара скобок не должна окружать всё выражение в целом.
Правильно?

[Maxim19]

Стоит наверное ещё раз сформулировать задачу: выразить как нибудь количество способов расставить скобки в последовательности из n букв, при этом соблюдая правила расстановки скобок по открытию-закрытию каждой и при этом нельзя открывать и закрывать скобки на одном знаке, то есть $a(b)$ и нельзя полность брать в скобки всю строку $(a_1...a_{n})$

-- 19.04.2023, 03:21 --

svv
Правильно

[svv]

Хорошо, давайте продолжим завтра.

[Maxim19]

Согласен, а я пока Кострикина продолжу. Я уверен, что это через формулы не выразить. Если перебирать, то даже непонятно, по какому правилу

-- 19.04.2023, 03:45 --

Было близко, но этот способ не учитывает, что скобки могут быть соседними(то есть между одной парой букв): пусть $Z_n$ - это те числа, о которых говорили сверху, они ещё рекуррентной формулой записаны. Это способ вообще правильно сконпоновать $2n$ скобок. Тогда в нашем случае $S_n=-n-1+\sum\limits_{k=0}^{(n+1)/2}Z_k\binom{2k}{n+1}$ при $n>1$

[svv]

https://oeis.org/A001003
Это — так называемая вторая проблема Шрёдера (Schroeder's second problem).

Цитата:

$a(n)$ is the number of ways to insert parentheses in a string of $n+1$ symbols. The parentheses must be balanced but there is no restriction on the number of pairs of parentheses. The number of letters inside a pair of parentheses must be at least $2$. Parentheses enclosing the whole string are ignored.

То есть точно, как Вы хотели. Только обратите внимание на первую фразу в цитате: $a(3)$ — это число способов расставить скобки для $4$ символов, и так далее.
Примеры:
$a(2) = 3: abc, a(bc), (ab)c$
$a(3) = 11: abcd, (ab)cd, a(bc)d, ab(cd), (ab)(cd), a(bcd), a(b(cd)), a((bc)d), (abc)d, (a(bc))d, ((ab)c)d$
Там же по ссылке найдёте и формулы (рекуррентную и через суммирование).

[Maxim19]

Можете их сюда скинуть? Найти не могу

[vpb]

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

Можете их сюда скинуть? Найти не могу

Да не, они находятся крайне быстро. А если не быстро --- пусть это будет небольшим упражнением на ориентацию в длинном (точнее, относительно длинном) тексте.

З.Ы. Вызывает сожаление, что у вас плохо работает точка на клавиатуре.

[Maxim19]

Да ну, что за токсичность? Вы бы лучше скинули, где формула. Мне действительно найти сложно, как минимум, из за того, что нет оформления формул