Задача про скобковые последовательности

[Nikys]

Не прошу решить за меня задачу, просто прошу помочь.
Задача состоит в следующем. Есть три типа скобковых последовательностей. Пусть это будут, к примеру, () ($k_1$), {} ($k_2$), [] ($k_3$).
Их можно комбинировать произвольно в правильные последовательности, типа
{}(), [{}([])]{}, и т.д.
Задача состоит в том, чтобы найти все возможные перестановки при известных $k_1$, $k_2$ и $k_3$.
Предположение №1. Если задать программно количество возможных способов расставить одинаковые скобки при количестве скобок (k1+k2+k3), то, опираясь на правила комбинаторики, можно будет спокойно вывести нужное число (если не ошибаюсь, то при l - количестве способов, $S=l \cdot \frac {(k_1+k_2+k_3)!}{(k_2+k_3)!} \cdot \frac{(k_1+k_2+k_3)!}{(k_1+k_3)!} \cdot \frac{(k_1+k_2+k_3)!}{(k_1+k_2)!}$, но я, мне кажется, ошибаюсь).

Предположение №2. В высчитании количества l способов для $k_1+k_2+k_3$ скобок присутствует рекурсивная логика. Тут я, может быть, тоже ошибаюсь.
Второе предположение - есть моя самая мучительная проблема. Прошу помочь идеями и подсказками. Заранее благодарен.

[Alexu007]

Пока не очень понятно, что нужно сделать, вот так что-ли?

abc
[a]bc
a[b]c
ab[c]
[a][b]c
[a]b[c]
a[b][c]
[a][b][c]

[Nikys]

Alexu007, нет, малость иное.
Вот смотрите, у вас $k_1 = 1$:
$().$
$s_{1(1,0,0)}=1.$
$k_1 = 2:$
$()();$
$( () ).$
$s_{2(2,0,0)}=2.$
$k_1 = 1, k_2 = 1:$
$()[];$
$[]();$
$( [] );$
$[ () ];$
$s_{2(1,1,0)}=4.$
Причем, как можно подметить, было комбинаторное размещение с 1 по 2 (а может я ошибаюсь, и это была комбинация, т.е.:
$s_{2(1,1,0)} = s_{2(2,0,0)} \cdot C^1_2 $)
Предположение слегка было заступорено за счет того, что не будет ли при каком-нибудь способе повторение.
Да и тем более, мою неправильную логику дополняет следующее:
"Односкобочность" вида ()()() можно заменять различным
$()[]\lbrace \rbrace, \lbrace \rbrace[](),()\lbrace \rbrace[], \lbrace \rbrace()[], []\lbrace \rbrace(), []()\lbrace \rbrace = 3!$ способов.
Но если они пойдут по две штуки, скажем, то уже просто перестановкой не обойтись...

-- 05.02.2012, 11:03 --

Да и может, у этой задачи есть другая, некомбинаторная логика решения? Иной я просто пока не заметил...

[arseniiv]

Nikys, поглядите здесь: http://ru.wikipedia.org/wiki/%D0%9F%D1% ... 1%82%D1%8C.

Оттуда писал(а):

Легко показать, что если в скобочной последовательности имеется $k$ типов скобок, то количество возможных правильных скобочных последовательностей с $n$ открывающими скобками равно произведению $C_n$ на $k^n$. Действительно, для каждой открывающей скобки из $n$ существует $k$ различных вариантов её выбора. Выбор закрывающей скобки однозначно определён уже выбранной парной ей открывающей и не учитывается.

Число последовательностей с одним видом скобок для $2n$ скобок ($n$ открывающих) равно $C_n$ (числа Каталана), это можно считать определением этих чисел. Выражение их через биномиальные коэффициенты можно получить, используя производящие функции.

-- Вс фев 05, 2012 19:00:45 --

Чтобы вывести рекуррентную формулу для чисел Каталана, можно заметить, что все ПСП с одним видом скобок могут быть порождены вот такой грамматикой:

\begin{array}{rcll} S & \to & \varepsilon & \quad\text{// \emph{пустая последовательность}} \\ S & \to & \mathbf( S \mathbf) S & \quad\text{// \emph{ПСП в скобках с приписанной справа другой ПСП}} \end{array}

Из первого правила мы получаем $C_0 = 1$, из второго $C_n = \sum\cdots$ (складываем все варианты составления последовательности).

[Nikys]

arseniiv в сообщении #535470 писал(а):

Nikys, поглядите здесь: http://ru.wikipedia.org/wiki/%D0%9F%D1% ... 1%82%D1%8C.

Оттуда писал(а):

Легко показать, что если в скобочной последовательности имеется $k$ типов скобок, то количество возможных правильных скобочных последовательностей с $n$ открывающими скобками равно произведению $C_n$ на $k^n$. Действительно, для каждой открывающей скобки из $n$ существует $k$ различных вариантов её выбора. Выбор закрывающей скобки однозначно определён уже выбранной парной ей открывающей и не учитывается.

Огромное спасибо, работает количество скобок при одном виде, всё совпадает... Только у меня с их логикой не сходится.

А то по этой логике, $C_2=2$, что верно.
Когда две скобки, по одной разной:
[]()
()[]
[()]
([])
$s=C_2\cdot2^2=8$
Фейл...

Или эта формула подразумевает также последовательности вида [(])?

[arseniiv]

Вы забыли добавить ещё (()), ()(), [[]], [][]. Ведь если какие-то виды скобок не использованы — последовательность формально всё равно будет оттуда же, откуда и ([]). Если вам такие не нужны, просто вычтем их. Их будет $kC_n$, $k$ — кол-во типов скобок.

-- Вс фев 05, 2012 20:01:34 --

Ой. У вас задача-то более специфическая. Прочитал и забыл. Когда количества разных открывающих скобок заданы, $k^n$ заменится на нечто другое, но зато не надо будет вычитать то, что я написал выше. Сейчас напишу, что именно будет.

-- Вс фев 05, 2012 20:10:27 --

Итак, поступим как там, но по-своему. Распределим сначала открывающие скобки первого типа. Это можно сделать $\binom n{k_1}$ способами ($n = k_1 + k_2 + k_3$). Потом распределим скобки второго типа $\binom{n-k_1}{k_2}$ способами, и последние оставшимся единственным способом. [Можно сказать, что их можно распределить $\binom{n-k_1-k_2}{k_3} = \binom{k_3}{k_3}$ способами, но это ведь как раз и равно 1. ] В общем, получаем при раскрытии всего этого $\frac{n!}{k_1! k_2! k_3!}$. Иногда такую штуку записывают $\binom n{k_1, k_2, k_3}$ и зовут мультиномиальным коэффициентом (потому что можно обобщить это на любое число типов скобок).

В общем, получается $\frac{n!}{k_1! k_2! k_3!} C_n$.

[Nikys]

arseniiv
Спасибо большущее)) Я как раз сел, вывел, решил написать - а вы расписали) Хоть буду знать, что в правильном направлении подумал)

[arseniiv]

(Оффтоп)

Да не за что.

[Alexu007]

Задача состоит в том, чтобы найти число перестановок, или в том, чтобы найти сами перестановки и вывести на экран?

[Nikys]

Alexu007
Число. К тому же, в задаче прибавлялось, что вдобавку к самой программе должно присутствовать решение при определенных значениях. Но код уже написан, и задача пока что не возбуждает во мне никакого нового интереса)

[arseniiv]

Даже если бы и не число, генерировать сочетания есть алгоритм. Для генерации скобочных последовательностей тоже, наверно, есть. Во всяком случае, можно было бы расположить открывающие скобки как попало, добавить соответствующее количество закрывающих, а потом отсеять неправильные.