344
правки
Изменения
→Правила вывода в языке Дика
Ясно, что для каждого слова такое представление единственно.
== Производящая функция для языка Дика ==
Вычислим с помощью правил вывода производящую функцию для языка Дика. Для этой цели выпишем '''некоммутативный производящий ряд''', перечисляющий слова языка. Этот ряд представляет собой формальную сумму всех слов языка, выписанных в порядке возрастания длины:
Решение <tex>d(s) = \dfrac{1 - \sqrt{1 - 4s^2}}{2s^2}</tex>
этого уравнения совпадает с производящей функцией для [[Числа Каталана#Вычисление производящей функции чисел Каталана | чисел Каталана]]. Необходимость подстановки <tex>s^2</tex> вместо <tex>s</tex> объясняется тем, что в языке Дика длина слова, составленного из <tex>n</tex> пар скобок, равна <tex>2n</tex>: мы перечисляем слова по числу скобок, а не ''пар'' скобок.
