задача по комбинаторике

Сообщение №31518 от igrgorgor 30 сентября 2009 г. 08:58
Тема: задача по комбинаторике

Рассмотрим правильные скобочные последовательности, состоящие из трех видов скобок: круглых (), квадратных [] и угловых <>. Назовем последовательность хорошей, если между любой парой соответствующих друг другу открывающейся и закрывающейся круглых скобок не встречается квадратных скобок.
Требуется подсчитать число хороших последовательностей длины 2Н (то есть состоящих из Н пар скобок).

если Н=1 то число хороших последовательностей равно 3, если Н=2, то число хороших последовательностей равно 17.
1≤Н≤100

[Перевод с транслит]


Отклики на это сообщение:

> Рассмотрим правильные скобочные последовательности, состоящие из трех видов скобок: круглых (), квадратных [] и угловых <>. Назовем последовательность хорошей, если между любой парой соответствующих друг другу открывающейся и закрывающейся круглых скобок не встречается квадратных скобок.
> Требуется подсчитать число хороших последовательностей длины 2Н (то есть состоящих из Н пар скобок).

Обозначим это число N(n). Нам еще понадобится число правильных скобочных структур из n пар скобод двух типов скобок: () и <>. Понятно, что оно равно M(n)=C(n)*2^n, где C(n) - число Каталана.
Нетрудно проверить, что выполняется следующие рекуррентное соотношение:

N(n) = (2 * N(n-1) + M(n-1))*N(0) + (2 * N(n-2) + M(n-2))*N(1) + ...

или в терминах производящих функций:

F(x) = 1 + 2*x*F(x)^2 + x*G(x)*F(x),

где
F(x) = \sum N(n)*x^n
и
G(x) = \sum_n M(n)*x^n = (1-sqrt(1-8x))/4x

Решая квадратное уравнение относительно F(x), получаем:

F(x) = ( 1 - x*G(x) - sqrt( (1 - x*G(x))^2 - 8*x ) ) / 4x =

= 1 + 3*x + 17*x^2 + 117*x^3 + 887*x^4 + 7131*x^5 + 59661*x^6 + 513897*x^7 + 4526603*x^8 + 40588263*x^9 + 369277481*x^10 + 3400840845*x^11 + 31644776383*x^12 + 297079014771*x^13 + 2810553697989*x^14 + 26770090211793*x^15 + O(x^16)

Из производящей функции можно явно выразить коэффициенты, но формула будет громоздка.

> если Н=1 то число хороших последовательностей равно 3, если Н=2, то число хороших последовательностей равно 17.

Все так - коэффициент при x равен 3, при x^2 равен 17.


спасибо:)


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100