344
правки
Изменения
→Правила вывода в языке Дика
При этом такое представление единственно.
}}
Чтобы перейти от некоммутативного производящего ряда к обычному, сделаем подстановку <tex>a = s, b = s, \lambda = s^0 = 1</tex>. Уравнение <tex>D(a, b) = \lambda + aD(a, b)bD(a, b)</tex> примет вид <tex>D(s, s) = 1 + s^2D(s, s)</tex>.
Отсюда, обозначив <tex>D(s, s)</tex> через <tex>d(s),</tex> получим <tex>d(s) = 1 + s^2d(s)^2</tex>
Решение <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>: мы перечисляем слова по числу скобок, а не ''пар'' скобок.
