Enumeration problems associated with Donaghey’s transformation

Abstract

In this paper we consider enumeration problems associated with Donaghey’s transformation. We discuss two groups of questions. The first one is related to the enumeration of fragments of transformation orbits, which are referred to as the “arcs”. The second group of questions is concerned with finding the number of vertices in rotation graphs-a specific family of graphs that is by nature an approximation of Donaghey’s transformation. The basic results of this work are formulated in the form of generating functions and corresponding asymptotics.

Full Text

Введение Напомним, что преобразованием Донахью (см., например, [1]) называется преобразование плоских кубических деревьев с висячим корнем (для краткости будем использовать аббревиатуру ПКДВК). Между ПКДВК и плоскими некубическими деревьями с висячим корнем (далее - ПДВК) существуют два варианта биекции: правая биекция и левая биекция. При пра- вой биекции r правые цепи в ПКДВК переходят в вершины ПДВК; при левой биекции l левые цепи ПКДВК переходят в вершины ПДВК. Рис. 1 иллюстрирует эти биекции. В верхней части рисунка к дереву T применяется правая биекция, в нижней части рисунка к r(T) применяется биекция обратная к левой. Правые и левые цепи на этом рисунке выделены пунктиром. Цепи, содержащие сына корня, будем называть старшей правой и старшей левой цепями. Рис. 1: Биекции r и l между множествами ПКДВК и ПДВК О п р е д е л е н и е 0.1. Преобразованием Донахью ПКДВК T называется дерево (T) = l 1 r(T): Таким образом, на рис. 1 построен образ дерева T при преобразовании Донахью. Каждое ПКДВК можно разбить на фрагменты, которые назовјм триадами. Под триадой будем понимать вершину, не являющуюся листом и корнем, с тремя половин- ками смежных с нею рјбер. Листья с единственными смежными половинками рјбер по- глощаются. Для каждой триады естественно определены не более чем по одной другой триаде, играющих для неј роль отца, правого и левого сыновей. Триаду, содержащую сына корня, будем называть корневой триадой. ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 7 На деревья, представленные в виде наборов триад, также можно действовать пре- образованием Донахью. В качестве примера выполним преобразование Донахью для дерева T с рис. 1, разбитого на триады. Результат этой операции изображјн на рис. 2. Рис. 2: Преобразование Донахью дерева, разбитого на триады Технически преобразование Донахью является просто перестановкой деревьев, ко- торая может быть легко (правда, строго говоря, не однозначно) перенесена на любую другую комбинаторную интерпретацию чисел Каталана, точнее - семейством переста- новок деревьев каждого определјнного размера. Однако циклическая структура перестановок этого семейства настолько сложна, что позволяет говорить об обратимой комбинаторной динамической системе, представляю- щей самостоятельный интерес и заслуживающей отдельного изучения. При изучении преобразования Донахью естественно возникает большое количество перечислительных задач. Фактически многие основные проблемы, связанные с ним, изначально имеют форму перечислительной задачи. Таковыми, например, являются задачи об общем количестве циклов (орбит) этих перестановок, о количестве циклов с заданными длинами (наиболее интересными представляются задачи о перечислении циклов с длинами 2, 6 и 9). Примечательно, что эти просто формулируемые проблемы привлекали внимание многочисленных специалистов (см., например, [2]-[4], [5, c. 472]), однако обычной реакцией на возникающие при этом трудности являлось то, что автор отмечал какое-нибудь несложное свойство и переходил к некоторой смежной задаче. Проблемы, рассмотрению которых посвящена данная работа, формулируются не на- столько просто и возникают, когда при изучении преобразования Донахью замечается какой-либо эффект, вызывающий интерес, что неизбежно приводит к вопросу о том, является ли этот эффект массовым или экзотическим. Как правило, аккуратный ана- лиз структуры соответствующих деревьев позволяет явно вычислить соответствующую производящую функцию. При вычислении асимптотического характера роста коэффи- циентов (той самой массовости) систематически используется результат, иногда имену- емый теоремой Дарбу (см. [6, с. 252, предложение 12]). 1. Перечисление дуг преобразования Донахью Для формулирования результатов этого раздела нам потребуется понятие правой огибающей цепи. О п р е д е л е н и е 1.1. Правой огибающей цепью называется последовательность триад дерева, полученная по следующим правилам: 8 В. А. Бызов 1) первым элементом этой последовательности становится корневая триада; 2) если у последнего добавленного в последовательность элемента есть правый сын, то этот правый сын становится следующим элементом последовательности; 3) если у последнего добавленного в последовательность элемента нет правого сына, но есть левый сын, то этот левый сын становится следующим элементом последо- вательности; 4) если у последнего добавленного в последовательность элемента нет ни правого, ни левого сыновей, то формирование правой огибающей цепи завершается. Под левым и правым поддеревом исходного дерева будем понимать поддеревья, при- соединјнные соответственно слева и справа к корневой триаде. При помощи прямоли- нейной проверки доказывается следующее утверждение. Лемма 1.1. 1. Дерево (T) имеет пустое правое поддерево тогда и только тогда, когда стар- шая правая цепь дерева T заканчивается триадой, не имеющей левого сына. 2. Дерево 2(T) имеет пустое правое поддерево тогда и только тогда, когда правая огибающая цепь дерева T заканчивается триадой, являющейся левым сыном. Каждый цикл преобразования Донахью разбивается деревьями с пустым левым под- деревом на фрагменты. Будем называть эти фрагменты дугами преобразования. Есте- ственным образом возникает задача перечисления дуг заданной длины. О п р е д е л е н и е 1.2. Для дерева T с пустым левым поддеревом назовем ду- гой такую последовательность деревьев T; (T); 2(T); : : : ; k(T) , что k(T) обладает пустым правым поддеревом, и k минимально возможное. Число k назовем длиной дуги. Дерево с пустым правым поддеревом k(T) при однократном преобразовании пе- реходит в дерево k+1(T) с пустым левым поддеревом. Дугу дерева k+1(T) назовем второй дугой дерева T . Аналогично определяется третья дуга дерева, четвертая и т. д. В качестве иллюстрации введјнного определения на рис. 3 изображено дерево T , дли- на дуги которого равна трјм. Также данный рисунок демонстрирует тот факт, что при преобразованиях Донахью происходит перемещение триад из правого поддерева в левое через корневую триаду. Рассмотрим деревья, имеющие пустое левое поддерево и состоящие из n+1 триады (одна корневая триада и n некорневых). Обозначим через T(n; k1; k2; : : : ; ks) количе- ство таких деревьев, длина первой дуги которых равна k1 , второй k2 и так далее, длина s -ой дуги равна ks . ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 9 Рис. 3: Дерево с длиной дуги, равной трјм Некоторые утверждения о числах T(n; k1; k2; : : : ; ks) содержатся в статье [7]. В част- ности, там приведено следующее рекуррентное соотношение для чисел T(n; 1; 1; 1) . При n > 5 T(n; 1; 1; 1) = Xn 3 i=1 i T(n i; 1; 1; 1) Xn 4 i=1 i Cn i 3 + Cn 3; где Cn = 1 n+1 2n n число Каталана. Этот результат можно развить стандартным образом до производящей функции. Производящая функция для чисел T(n; 1; 1; 1) имеет вид X1 n=1 T(n; 1; 1; 1)xn = 2x4 2x3 2x2 + x x2 3x + 1 + x3 1 p 1 4x 2x : Выражение в скобках является производящей функцией для чисел Каталана, поэтому справедлива следующая асимптотика: T(n; 1; 1; 1) Cn 3: Среди множества всех ПКДВК можно выделить подмножество деревьев, замкнутое относительно преобразования Донахью, семейство примитивных деревьев. Дадим понятие примитивного дерева в терминах разбиения дерева на триады. О п р е д е л е н и е 1.3. Дерево называется примитивным, если оно не содержит триад , удовлетворяющих одному из следующих двух условий: 1) отец триады является левым, а еј единственный сын - правым; 2) отец триады является правым, а еј единственный сын - левым. Так, например, деревья на рис. 3 являются примитивными. А деревья с рис. 2 прими- тивными не являются: триады, нарисованные на этом рисунке утолщјнными линиями, удовлетворяют условиям из приведјнного выше определения. В работе [8] показано, что количество примитивных деревьев из n триад ( n > 2 ) равно mn 2 + mn 1 , где mn = [nP=2] k=0 n 2k Ck число Моцкина. Количество примитивных 10 В. А. Бызов деревьев из n триад, обладающих пустым правым поддеревом, равно mn 2 . Произво- дящая функция для чисел Моцкина (см., например, [9]) имеет следующий вид: M(x) = X1 n=0 mnxn = 1 x p 1 2x 3x2 2x2 : Перейдјм к анализу дуг примитивных деревьев. Пусть количество триад в деревьях равно n + 1 , левые поддеревья пусты. Обозначим через b T(n; k1; k2; : : : ; ks) количество таких деревьев, которые являются примитивными, и длина первой дуги которых рав- на k1 , второй k2 , и так далее, длина s -й дуги равна ks . Начнјм с рассмотрения случая s = 1 . Пусть дерево имеет вид, изображјнный на рис. 4 слева, где поддерево M (обведјнное пунктиром) содержит k триад. Рис. 4: Перемещение триад через корень примитивного дерева На этом рисунке проиллюстрирован процесс перемещения k+1 триады через корень дерева; 1; 2; : : : ; l триады старшей правой цепи дерева M . Введјм обозначение: Ai дерево, имеющее корневую триаду i и пустое правое поддерево ( i = 1; l ). Для того чтобы исходное дерево было примитивным, должны выполняться два условия: 1) триады i имеют левых сыновей при любом i = 1; l ; 2) деревья Ai являются примитивными при любом i = 1; l . Обозначим символом rk количество способов сформировать дерево M из k триад. Оно равно rk = X i1+i2+:::+il=k mi1 2 mi2 2 : : : mil 2; где сумма берјтся по всем упорядоченным разложениям k на слагаемые больше еди- ницы. Будем считать, что r0 = 1 , так как дерево M может быть пустым. Если дерево M состоит из одной триады, то исходное дерево не является примитивным, поэтому r1 = 0 . ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 11 Рассмотрим производящую функцию R(x) для чисел rk : R(x) = X1 n=0 rnxn = 1 + m0x2 + m1x3 + (m0m0 + m2)x4 + : : : = = 1 + x2 X1 n=0 mnxn + x4 X1 n=0 mnxn !2 + : : : = 1 + x2M(x)+ +x4M2(x) + : : : = 1 1 x2M(x) = 1 + x p 1 2x 3x2 2x(1 + x) : Эта производящая функция совпадает с производящей функцией для чисел Риордана. В работе [10] приведены различные интерпретации последовательности чисел rk; а также получена формула rk = Xk i=0 ( 1)k i k i Ci: Каждой дуге дерева соответствует композиция n = i1 + i2 + : : : + ik , где i1 триад перемещены через корень за первое преобразование, i2 за второе и так далее, ik триад за k -е преобразование. Таким образом, b T(n; k) = X i1+i2+:::+ik=n ri1 1 ri2 1 : : : rik 1; (1.1) где суммирование происходит по всем упорядоченным разложениям числа n на k сла- гаемых. Используя данное соотношение, можно получить производящую функцию для чисел b T(n; k) . Утверждение 1.1. 1. X1 n=k b T(n; k)xk = xkRk(x) ; 2. b T(n; k) k 3n+1 2 2k+2 p n 3 2 . Д о к а з а т е л ь с т в о. Справедливость первого пункта напрямую следует из фор- мулы (1.1). Перепишем производящую функцию в виде X1 n=k b T(n; k)xn = (x R(x))k = 1 2 1 2 p 1 + x r 1 x 1=3 k : Для вычисления асимптотик коэффициентов производящих функций такого вида умест- но использовать результат М. Дрмота, полученный в [11, теоремы 3 и 4]. В нашем случае g(x) = 1 2 , h(x) = 1 2 p 1+x , x0 = 1 3 . 12 В. А. Бызов Заметим, что при k = 2 получаем функцию x2R2(x) = 1 x p 1 2x 3x2 2(1+x) . Эта функ- ция совпадает с производящей функцией для 321-избегающих простых перестановок (см. [12]). Ещј несколько свойств чисел b T(n; k) напрямую следуют из соотношения (1.1) и из то- го, что r0 = 1 , r1 = 0 и r2 = r3 = 1 . Утверждение 1.2. 1. b T(n; n 1) = 0 при n > 2 ; 2. b T(n; n 2) = n 2 при n > 3 ; 3. b T(n; n 3) = n 3 при n > 4 . Перейдем к перечислению примитивных деревьев, у которых заданы длины несколь- ких дуг. Справедливо следующее утверждение. Утверждение 1.3. 1. b T(n; 1; 1) = b T(n 1; 3) при n > 2 ; 2. X1 n=1 b T(n; 1; 1)xn = x 3 + 3x p 1 2x 3x2 2(1 + x)2 ; 3. b T(n; 1; 1) 3n+1 2 32 p n 3 2 . Д о к а з а т е л ь с т в о. 1. Пусть длина первых двух дуг дерева T равна одному. Тогда преобразование Донахью дерева T должно выглядеть так, как показано на рис. 5. Здесь конечная триада правой огибающей цепи дерева ( e T) , по лемме 1.1 эта триада должна быть левым сыном. Рис. 5: Иллюстрация к доказательству утверждения 1.3 Заметим, что если убрать триаду из дерева T , то оставшееся дерево будет при- митивным, и длина его дуги будет равна трјм. Обратно: любое примитивное дерево, длина первых двух дуг которого равна одному, может быть получено из примитивного дерева с длиной дуги, равной трјм, путјм присоединения триады к старшей правой цепи. Таким образом, построенное соответствие является взаимнооднозначным. ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 13 З а м е ч а н и е 1.1. Аналогичные рассуждения для непримитивных деревьев не проходят. 2. Из предыдущего пункта следует, что производящая функция для чисел T(n; 1; 1) выражается через производящую функцию для чисел T(n; 3) . Так как b T(1; 1; 1) = 1 , то получаем X1 n=1 b T(n; 1; 1)xn = x + x X1 n=1 b T(n; 3)xn = x + x4R3(x); откуда и следует доказываемое утверждение. 3. Данная асимптотика получается прямым применением теоремы Дарбу к произ- водящей функции из предыдущего пункта. Следствие 1.1. При n > 1 верно, что b T(n; 1) = b T(n; 1; 1) + b T(n + 1; 1; 1) . Д о к а з а т е л ь с т в о. Равенство справедливо, потому что производящая функ- ция для последовательности b T(n; 1; 1)+ b T(n+1; 1; 1) совпадает с производящей функ- цией для последовательности b T(n; 1) . Для доказательства ещј одного соотношения нам потребуется вспомогательное утверждение. Пусть 'i i -й член последовательности Фибоначчи ( '1 = '2 = 1 , 'i+2 = 'i+1+'i ). Также будем считать, что слагаемое два в композиции числа может быть разных типов: 2 и 20 . Лемма 1.2. Количество представлений числа n в виде упорядоченной суммы n = n1 + n2 + : : : + nm , где nj 2 f2; 20; 3g , равно 'n + ( 1)n . Д о к а з а т е л ь с т в о. Пусть an количество описанных в формулировке лем- мы композиций числа n , a0 = 1 . Рассмотрим производящую функцию A(x) = 1P n=0 anxn . Так как возможны три типа слагаемых: 2 , 20 и 3 , то производящая функция равна A(x) = X1 k=0 (x2 + x2 + x3)k = 1 1 2x2 x3 : Заметим, что полученное выражение равно сумме x 1 x x2 + 1 1+x , где первое слагае- мое является производящей функцией для чисел Фибоначчи, а второе производящей функцией для последовательности ( 1)n . При помощи непосредственной проверки можно убедиться в том, что b T(1; 1; 1) = 1 , b T(2; 1; 1) = 0 , b T(3; 1; 1) = 0 . При больших n справедливо следующее утверждение. Утверждение 1.4. b T(n; 1; 1)= b T(n; 1; 1; 1)+b T(n+1; 1; 1; 1) 'n 3+( 1)n при n > 4: Д о к а з а т е л ь с т в о. Ограничимся изложением основных идей доказательства. Пусть у примитивного дерева T длина первых двух дуг равна одному. С одной стороны, количество таких деревьев равно b T(n; 1; 1) . С другой стороны, возможны два случая: 1) длина третьей дуги T тоже равна одному; 14 В. А. Бызов 2) длина третьей дуги T больше одного. Первому условию удовлетворяют b T(n; 1; 1; 1) деревьев. Предположим, что дерево T удовлетворяет второму условию. По лемме 1.1 старшая правая цепь дерева 4(T) за- канчивается триадой, имеющей левого сына. Добавим к этой триаде ещј и правого сына. Обозначим полученное примитивное дерево с n + 1 некорневой триадой через 4(T0) . Можно показать, что в этом случае у дерева T0 длины трјх первых дуг равны одному. С другой стороны, возьмјм примитивное дерево T0 с n + 1 некорневой триадой, у которого длины первых трјх дуг равны одному. Обозначим дерево, получающееся удалением конечной триады старшей правой цепи дерева 4(T0) через 4(T00) . Если бы тогда дерево T00 всегда удовлетворяло приведјнному выше второму условию, то было бы верно равенство b T(n; 1; 1) = b T(n; 1; 1; 1)+ b T(n+1; 1; 1; 1) . Но это не так. ѕПре- пятствиемї являются те деревья T00 , для которых дерево 2(T00) выглядит так, как показано на рис. 6. Рис. 6: Иллюстрация к доказательству утверждения 1.4 Назовјм такое дерево 2(T00) плохим. Плохое дерево обладает тем свойством, что все его правые цепи имеют длину 2 или 3. Причјм, если пронумеровать эти цепи так, как показано на рисунке, то первая правая цепь обязательно содержит три триады, а последняя - две. Представим, что мы формируем плохое дерево, присоединяя цепи в обратном по- рядке: к последней цепи присоединяем предпоследнюю и т. д. Можно увидеть, что цепь, состоящая из двух триад, может быть присоединена двумя способами к предыдущей добавленной цепи, а цепь из трјх триад - только одним. Например, на рис. 6 цепь 3 могла бы быть присоединена к цепи 4 через триады или , а цепь 2 к цепи 3 может быть присоединена только через триаду " . Иначе будет нарушено условие примитивности дерева. Если из плохого дерева с n+1 некорневыми триадами убрать первую и последнюю цепи (которые формируются однозначно), то останется n 3 триады. Таким образом, количество плохих деревьев с n некорневыми триадами равно числу упорядоченных ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 15 разложений числа n 3 в сумму двоек и троек, в которой слагаемое 2 бывает двух типов. По лемме 1.2 это число равно 'n 3 + ( 1)n 3 . Получаем доказываемую формулу. Применяя стандартную технику к доказанному соотношению, можно получить про- изводящую функцию для чисел b T(n; 1; 1; 1) . Кроме того, теорема Дарбу позволяет вы- вести асимптотику для этих чисел. Утверждение 1.5. 1. 1P n=1 b T(n; 1; 1; 1)xn = x(2+7x+5x2+2x3+2x4 x p 1 2x 3x2) 2(1+x)3 + x5 (1 x x2)(1+x) ; 2. b T(n; 1; 1; 1) 3n+1 2 128 p n 3 2 . 2. Производящие функции для количества вершин в графах поворотов Рассмотрим граф Gn , вершинами которого являются ПДВК с n некорневыми вер- шинами, а рјбрами - ПКДВК с n листьями. Скажем, что ориентированное ребро e идјт от вершины v1 к v2 , если образ дерева e при левой биекции l(e) равен v1 , и образ при правой биекции r(e) равен v2 . Назовјм полученный граф Gn графом преобразования Донахью. Компоненты связ- ности этого графа - циклы, соответствующие орбитам преобразования Донахью. Иссле- дование циклической структуры графа Gn - сложная задача. Для того чтобы прибли- зиться к еј решению, рассмотрим граф, вершинами которого являются не произвольные деревья, а деревья фиксированной высоты. О п р е д е л е н и е 2.1. Шаблоном k -го уровня ПДВК с n некорневыми верши- нами назовјм некубическое дерево, удовлетворяющее следующим условиям: 1) высота дерева, т. е. наибольшая длина пути от корня к листу, равна k + 1 ; 2) листья дерева, находящиеся на нижнем ярусе, помечены натуральными числами; 3) сумма меток и количества непомеченных некорневых вершин равна n . Договоримся, что шаблон k -го уровня, все метки которого равны одному, является одновременно шаблоном l -го уровня для любого l > k . На рис. 7 слева приведјн пример шаблона второго уровня для дерева с 14 некорневыми вершинами. Пусть v - шаблон k -го уровня. Скажем, что висячий корень v находится на нуле- вом ярусе, сын корня - на первом ярусе, сыновья сына корня - на втором ярусе и т. д. О п р е д е л е н и е 2.2. Поддеревья шаблона v , корнями которых являются вер- шины (s + 1) -го яруса ( 0 6 s 6 k ), назовјм компонентами s -го уровня в шаблоне v . Длиной компоненты назовјм количество сыновей у корневой вершины соответствую- щей компоненты. Например, на рис. 7 слева шаблон содержит три компоненты первого уровня, кото- рые имеют следующие длины: 3, 0, 1. Нумеровать компоненты первого уровня будем слева направо. 16 В. А. Бызов Рис. 7: Шаблон дерева Хорошо известна биекция между некубическими деревьями и расстановками ско- бок, при которой листьям деревьев, расположенным на нижнем ярусе, соответствуют внутренние пары скобок максимальной вложенности. Написав между такими скобка- ми метки соотвествующих листьев, получим биективный образ шаблона дерева. Бу- дем называть полученную расстановку скобок модифицированной. Например, шаблон, изображенный на рис. 7, отображается при данной биекции в модифицированную рас- становку скобок ((2)(1)(4))()((3)) . Такие расстановки понадобятся нам в дальнейшем для более компактного изображения графа поворотов. О п р е д е л е н и е 2.3. Дерево T соответствует шаблону P , если T получает- ся из P путјм добавления на позиции листьев нижнего яруса поддеревьев, количество вершин в которых равно меткам этих листьев. В качестве иллюстрации на рис. 7 изображены шаблон и соответствующее ему неку- бическое дерево. О п р е д е л е н и е 2.4. Некубические деревья T1 и T2 называются эквивалент- ными на уровне m, если они соответствуют одному шаблону уровня m. Для обозначения эквивалентности двух деревьев будем применять запись T1 m T2 . Проведјм факторизацию графа преобразования Донахью по данной эквивалентно- сти, т. е. ѕсклеимї вершины, обладающие одним шаблоном. О п р е д е л е н и е 2.5. Графом поворотов m-го уровня для деревьев с n некор- невыми вершинами назовјм ориентированный граф, вершинами которого являются шаблоны m-го уровня для деревьев с n некорневыми вершинами, а рјбрам соответ- ствуют кубические деревья. Ребро e идјт от вершины v1 к v2 , если образ дерева e при левой биекции l(e) соответствует шаблону v1 , а образ этого дерева при правой биекции r(e) шаблону v2 . Для графа поворотов будем применять обозначения Gmn = Gn= m Заметим, что в этом графе допускаются кратные рјбра. Как было отмечено выше, существует биекция между шаблонами деревьев и мо- дифицированными расстановками скобок. Поэтому, для более компактной записи, бу- дем маркировать вершины графа Gmn расстановками скобок. Графы поворотов первого и второго уровня для деревьев с пятью некорневыми вершинами приведены на рис. 8. ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 17 Рис. 8: Графы G15 и G25 Заметим, что количество рјбер в графах поворотов Gmn равно количеству ПКДВК с n листьями, т. е. равно числу Каталана Cn 1 . Обозначим символом vm n количество вершин в Gmn . Задачу вычисления чисел vm n можно свести к равносильной задаче нахождения ко- личества деревьев, не содержащих паттерны-гребјнки. Перечислением таких деревьев занимались авторы работы [13]. Продемонстрируем равносильность этих задач. В соответствии с [13] введјм следующие определения. Паттерном назовјм плос- кое кубическое дерево без висячего корня (корень имеет двух сыновей). Скажем, что ПКДВК T непрерывно содержит паттерн t , если дерево T содержит t как поддерево. Рис. 9 иллюстрирует данное определение: дерево T непрерывно содержит паттерн t , но не содержит непрерывно паттерн s . Рис. 9: Паттерны в деревьях Говорят, что дерево T разрывно содержит паттерн t , если существует дерево T , получаемое из T путјм применения конечного числа операций стягивания рјбер, такое что T непрерывно содержит паттерн t . Так, на рисунке 9 дерево T разрывно содер- жит паттерн s , так как дерево, получаемое из T стягиванием ребра e (обозначено пунктиром), содержит s непрерывно. Обозначим через avt(n) количество ПКДВК с n листьями, которые не содержат разрывно паттерн t . Будем рассматривать специальный вид паттерновгребјнки. При- меры левых гребјнок приведены на рис. 10. Деревья, симметричные левым гребјнкам назовјм правыми гребјнками. Обозначим левые гребјнки с i листьями через ci . 18 В. А. Бызов Рис. 10: Паттерны-гребјнки Утверждение 2.1. avcm+3(n) = vm n при m > 1 , n > 1 . Д о к а з а т е л ь с т в о. Будем строить биекцию между множеством вершин гра- фа поворотов Gmn и множеством деревьев, не содержащих разрывно паттерн cm+3 ин- дукцией по m. База индукции. Положим T дерево с n листьями, не содержащее разрывно пат- терн c4 . Пусть это дерево имеет вид, изображенный на рис. 11 слева. Заметим, что деревья T1; T2; : : : ; Ts в этом случае либо состоят из одной вершины, либо являют- ся правыми гребјнками. Пример дерева, удовлетворяющего этому условию, изображен на рис. 11 справа. Иначе, если к старшей правой цепи дерева T присоединено дерево, отличное от правой гребјнки, то стягиванием рјбер можно получить поддерево c4 . Ес- ли, например, на рис. 11 к листу x присоединить любое непустое кубическое дерево, то при стягивании рјбер e1 и e2 получается дерево, содержащее c4 . Рис. 11: Иллюстрация к доказательству утверждения 2.1 Дереву T поставим в соответствие вершину (a1)(a2) : : : (as) графа G1 n , где ai количество листьев в гребјнке Ti . Понятно, что разным деревьям, не содержащим разрывно c4 , соответствуют разные вершины в G1 n ; для любой вершины в G1 n можно построить еј прообраз при данном отображении. Поэтому построенное отображение является взаимно-однозначным и avc4(n) = v1n . Индукционный переход. Пусть доказано, что avck+3 = vkn . Рассмотрим дерево T , не содержащее разрывно паттерн ck+4 . Пусть это дерево имеет вид, изображенный на рис. 11 слева. Тогда ни одно из деревьев Ti не содержит разрывно паттерн ck+3 , иначе стягиванием рјбер получим паттерн ck+4 в дереве T . Пусть Pi вершина- шаблон в графе Gk n , соответствующая дереву Ti ( i = 1; s ). Тогда образом дерева T назовјм шаблон (P1)(P2) : : : (Ps) . Хорошо видно, что построенное отображение является биекцией. ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 19 Заметим, что при n > 2 и m > 2 количество вершин в графе Gmn может быть записано при помощи следующего рекуррентного соотношения: vm n = Xn 1 k=1 X i1+i2+:::+ik=n 1 vm 1 i1 vm 1 i2 : : : vm 1 ik : (2.1) Здесь внутреннее суммирование происходит по всем упорядоченным разложениям числа n 1 . Справедливость данной формулы иллюстрирует представление некуби- ческого дерева на рис. 12. Если исходное дерево T содержит n некорневых вершин, то деревья T1; T2; : : : ; Tk (без висячего корня) содержат суммарно n 1 вершину, так как сын корня дерева T не входит ни в одно из этих деревьев. Рис. 12: Некубическое дерево Для производящей функции последовательности чисел vm n будем использовать обо- значение Fm(x) = 1P n=1 vm n xn . Следующее утверждение представляет собой рекуррент- ную формулу для вычисления функций Fm(x) . Утверждение 2.2. 1. F1(x) = x x2 1 2x ; 2. Fm(x) = x 1 Fm 1(x) при m > 2 . Д о к а з а т е л ь с т в о. Вершины в графе поворотов первого уровня G1 n суть упо- рядоченные разложения числа n 1 на слагаемые, поэтому верно, что v1n = ( 1; n = 1; 2n 2; n > 1; откуда следует первый пункт утверждения. Используя формулу (2.1), при m > 2 получаем Fm(x) = x + X1 n=2 Xn 1 k=1 X i1+i2+:::+ik=n 1 vm 1 i1 vm 1 i2 : : : vm 1 ik ! xn = = x + x Fm 1(x) + x F2m 1(x) + x F3m 1(x) + : : : = x 1 Fm 1(x) ; что и требовалось доказать. 20 В. А. Бызов При помощи доказанного утверждения можно получить явное выражение для функ- ций Fm(x) . В работе [13] показано, что верна формула Fm(x) = [m+1 P2 ] i=0 ( 1)i m i+1 i xi+1 [m+2 2 P] i=0 ( 1)i m i+2 i xi : Хорошо известно, что производящую функцию для чисел Каталана можно пред- ставить в виде цепной дроби. Выпишем это разложение для производящей функции, домноженной на x : F(x) = X1 n=1 Cn 1xn = x 1 x 1 x . . . ; Заметим, что F1(x) = x 1 x 1 x ; F2(x) = x 1 x 1 x 1 x ; и т. д. Таким образом, получена следующая комбинаторная интерпретация подходящих дробей для производящей функции последовательности Каталана. Утверждение 2.3. Подходящие дроби для производящей функции 1P n=1 Cn 1xn рав- ны производящим функциям Fm(x) для количества вершин в графах поворотов. Этот результат хорошо согласуется с тем фактом, что при фиксированном коли- честве некорневых вершин n начиная с некоторого уровня m вершинами графа Gmn являются вообще все некубические деревья заданного размера. Отметим, что функция F2(x) совпадает с производящей функцией для чисел Фи- боначчи с нечјтными номерами, т. е. v2n = 2n 3 + 3 2n p 5 ; где золотое сечение, равное 1+ p 5 2 . В работе [14] была получена асимптотика для последовательностей vm n : vm n C 4n cos2n m + 3 ; где C - некоторая положительная константа. ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 21 3. Производящие функции для количества вершин в примитивных графах поворотов Образ примитивного дерева при преобразовании Донахью также является прими- тивным. Для изучения внутренней структуры графов поворотов целесообразно рас- смотреть их подграфы, соответствующие примитивным деревьям. О п р е д е л е н и е 3.1. Примитивным графом поворотов m-го уровня для де- ревьев с n листьями называется подграф графа Gmn , ребра которого соответствуют примитивным деревьям. Для примитивного графа поворотов будем применять обозначение bG mn , для количе- ства вершин в нјм - bvm n , для производящей функции числа вершин - b Fm(x) = 1P n=1 bvm n xn . Заметим, что количество рјбер в графе Gmn равно числу примитивных деревьев, т. е. mn 2 + mn 3 ( n > 3 ). Утверждение 3.1. b F1(x) = x 1 x x2 (т. е. bv1n равно числу Фибоначчи 'n ). Д о к а з а т е л ь с т в о. В графе bG 1 n вершины суть упорядоченные разложения числа n 1 на слагаемые, в которых единицы могут стоять только в начале или в кон- це. Запишем в ряд n 1 единицу. Поставив в образовавшиеся n 2 промежутков знаки ѕ+ї и ѕ,ї, получим композицию числа n 1 (элементы композиции отделены запятыми). Если запретить написание двух запятых подряд (в соседних промежутках), то получатся нужные композиции. То есть количество вершин в bG 1 n равно количеству последовательностей длины n 2 из символов ѕ+ї и ѕ,ї, где две запятые не идут подряд. Как известно, количество таких последовательностей равно числу Фибоначчи. Используя формулу Бине, получаем асимптотическую оценку для чисел bv1n . Следствие 3.1. bv1n n p 5 , где = 1+ p 5 2 . Найти производящую функцию для чисел bvm n при m > 2 позволяет следующее утверждение. Утверждение 3.2. При m > 2 верно, что b Fm(x) = x(1 + x + xbH m 1(x)) 1 + x bH m 1(x) ; где bH l(x) = Xl 1 i=0 ( 1)i xi b Fl i(x) + ( 1)l xl+1 + x2 1 + x + ( 1)l xl+2 1 x : 22 В. А. Бызов Д о к а з а т е л ь с т в о. Пусть шаблон m-го уровня, соответствующий вершине в примитивном графе поворотов, имеет вид, изображјнный на рис. 12 (напомним, что у деревьев T1; T2; : : : ; Tk нет висячего корня). Вследствие примитивности деревьев-рј- бер выполняются следующие условия: 1) только деревья T1 и Tk могут содержать по одной вершине; 2) у корней деревьев Ti ( i = 1; k ) больше одного сына (у корней T1 и Tk может не быть сыновей). Из второго условия следует, что для дальнейших расчјтов требуется рассмотрение вершин-шаблонов в графе bG mn , сын висячего корня которых обладает более чем одним сыном. Пусть bwm n количество таких вершин. Определим bwm 1 = bwm 2 = 1 . Действи- тельно, если деревья Ti содержат по одной или по две вершины, то приведјнные выше условия не нарушаются (по одной вершине может быть только в деревьях T1 и Tk ). Поскольку только у одного шаблона первого уровня (n 1) сын корня имеет одного сына, то bw1n = ( bv1n 1; n > 3; bv1n ; n < 3: Количество вершин графа bG 2 n , сын корня которых имеет одного сына, равно количеству вершин графа bG 1 n 1 , сын корня которых имеет двух и более сыновей (иначе нарушается примитивность). Поэтому bw2n = 8>>< >>: bv2n bv1 n 1 + 1; n > 4; bv2n bv1 n 1; n = 3; bv2n ; n < 3: В общем случае по индукции bwm n = 8>>>>>< >>>>>: bvm n + mP 1 i=1 ( 1)i bvm i n i + ( 1)m; n > m + 2; bvm n + nP 2 i=1 ( 1)i bvm i n i ; 3 6 n < m + 2; bvm n ; n < 3: Производящая функция для последовательности f bwm n g1 n=1 имеет вид bH m(x) = X1 n=1 bwm n xn = X1 n=1 bvm n xn x X1 n=2 bvm 1 n xn + x2 X1 n=2 bvm 2 n xn : : : : : : + ( 1)m 1xm 1 X1 n=2 bv1n xn + ( 1)m X1 n=m+2 xn = = b Fm(x) + mX 1 i=1 ( 1)i xi b Fm i(x) x + ( 1)m xm+2 1 x = ПЕРЕЧИСЛИТЕЛЬНЫЕ ЗАДАЧИ, СВЯЗАННЫЕ С ПРЕОБРАЗОВАНИЕМ ДОНАХЬЮ 23 = mX 1 i=0 ( 1)i xi b Fm i(x) + ( 1)m xm+1 + x2 1 + x + ( 1)m xm+2 1 x : Перейдјм к вычислению производящей функции для количества вершин в прими- тивном графе. Верно, что b Fm(x) = X1 n=1 bvm n xn = x + X1 n=2 Xn 1 k=1 X i1+:::+ik=n 1 bwm 1 i1 : : : bwm 1 ik ! xn; (3.1) где индексы суммирования i1; i2; : : : ; ik принимают значения, при которых только i1 и ik могут быть равны единице. Учитывая это ограничение, получаем: b Fm(x) = x + xbH m 1(x) + xbH 2m 1(x) + x bH 3 m 1(x) xbH 2 m 1(x) + + x bH 4 m 1(x) 2xbH 3m 1(x) + x2bH 2m 1(x) + : : : + x bH k m 1(x) k 2 1 xbH k 1 m 1(x) + k 2 2 x2bH k 2 m 1(x) k 2 3 x3bH k 3 m 1(x)+ +: : : + ( 1)kxk 2bH 2m 1(x) + : : : Действительно, если бы суммирование в формуле (3.1) происходило по всем упоря- доченным разложениям числа n 1 , то производящая функция была бы равна сумме слагаемых xbH km 1(x) . Здесь же из этих слагаемых мы должны вычесть компоненты, которые соответствуют разложениям, содержащим единицы в середине. Так, например, поставить единицу в середине трјхэлементной композиции числа можно единственным способом, поэтому четвјртое слагаемое равно x bH 3 m 1(x) xbH 2 m 1(x) . При формиро- вании других слагаемых в этой сумме использовалась формула включений-исключений. После перегруппировки получаем следующее: b Fm(x) = x + x bH m 1(x) + bH 2 m 1(x) + bH 3 m 1(x) + : : : x2 1 1 bH 2m 1(x) + 2 1 bH 3m 1(x) + 3 1 bH 4 m 1(x) + : : : + + x3 2 2 bH 2m 1(x) + 3 2 bH 3m 1(x) + 4 2 bH 4m 1(x) + : : : : : : Введјм обозначения: y = bH m 1(x) , S(y) = 1P k=0 yk . Тогда получившееся выражение можно переписать следующим образом: b Fm(x) = x + x(S(y) 1) x2y2S0(y) + x3 2! y2S00(y) x4 3! y2S000(y) + : : : 24 В. А. Бызов Так как S(y) = 1 1 y , то S(n)(y) = n! (1 y)n+1 . Следовательно, b Fm(x) = x + x y 1 y x2 y2 (1 y)2 + x3 y2 (1 y)3 : : : = x(1 + x + xy) 1 + x y :