На «Средняя высота посаженных самолетов» Кнут, де Бруйн и Райс (1972)

Question

Я пытаюсь получить Классическая бумага В заголовке только элементарными средствами (без генерирующих функций, нет сложного анализа, нет анализа Фурье), хотя и с гораздо меньшей точностью. Короче говоря, я «только» хочу доказать, что средняя высота $ h_n $ дерева с узлами $ n $ (то есть максимальное количество узлов от корня до листа) удовлетворяет $ h_n sim sqrt { pi n} $.

Схема заключается в следующем. Пусть $ a_ {nh} $ будет количеством деревьев с высотой меньше или равным $ h $ (с соглашением $ a_ {nh} = a_ {nn} $ для всех $ h geqslant n $) и $ b_ {{ nh} $ Количество деревьев узлов $ n $ с высотой или равным $ h+1 $ (то есть $ b_ {nh} = a_ {nn} - a_ {nh} $). Тогда $ h_n = s_n/a_ {nn} $, где $ s_n $ - конечная сумма $$ s_n = sum_ {h geqslant 1} h (a_ {nh} - a_ {n, h -1}) = sum_ {h geqslant 1} h (b_ {n, h -1} - b_ {nh}) = sum_ {h geqslant 0} b_ {nh}. $$ хорошо известно, что $ a_ {nn} = frac {1} {n} binom {2n-2} {n-1} $, для набора общих деревье Набор бинарных деревьев с узлами $ N-1 $, подсчивленный каталонскими номерами.

Следовательно, первый шаг - найти $ b_ {nh} $, а затем основной термин в асимптотическом расширении $ s_n $.

В этот момент авторы используют аналитическую комбинаторию (три страницы) для получения $$ b_ {n+1, h-1} = sum_ {k geqslant 1} left [ binom {2n} {n+1-kh} -2 binom {2n} {n-kh} + binom {2n} {n-1-kh} right]. $$

Моя собственная попытка заключается в следующем. Я рассматриваю битву между деревьями с узлами $ n $ и монотонными путями на квадратной сетке $ (n-1) times (n-1) $ от $ (0,0) $ до $ (N-1, N-1 ) $, которые не пересекают диагональ (и сделаны из двух видов шагов: $ uparrow $ и $ rightarrow $). Эти пути иногда называют Dyck Paths или же экскурсии. Анкет Теперь я могу выразить $ b_ {nh} $ с точки зрения пути решетки: это количество путей DYCK длины 2 (n-1) и высота больше или равна $ H $. (Примечание: дерево высоты $ h $ находится в биении с Dyck Path of Height $ H-1 $.)

Без потери общности я предполагаю, что они начинаются с $ uparrow $ (следовательно, оставайтесь выше диагонали). Для каждого пути я рассматриваю первый шаг, пересекающий строку $ y = x + h - 1 $, если таковой имеется. С точки зрения выше, вплоть до начала происхождения, я меняю $ uparrow $ на $ rightarrow $ и наоборот (это отражение wrt строка $ y = x+h $). Становится очевидным, что пути, которые я хочу считать ($ b_ {nh} $), находятся в битве с монотонными путями от $ (-h, h) $ до $ (n-1, n-1) $, которые избегают границ $ y = x+2h+1 $ и $ y = x-1 $. (Видеть фигура.)

В классической книге Подсчет пути решетки и приложения Mohanty (1979, стр. 6) Формула $$ sum_ {k in mathbb {z}} Left [ binom {m+n} {mk (t+s)} - binom {m+n} {n+k (t+s)+t} right], $$ считает количество монотонных путей в решетке от $ (0,0) $ до $ (m, n) $, которые избегают границ $ y = x - t $ и $ y = x + s $, с $ t> 0 $ и $ s> 0 $. (Этот результат был впервые установлен российскими статистиками в 50-х годах.) Поэтому, рассмотрев новое происхождение в $ (-h, h) $, мы удовлетворяем условия формулы: $ s = 1 $, $ t = 2H+ 1 $ и пункт назначения (верхний правый угол) теперь $ (n+H-1, NH-1) $. Тогда $$ b_ {nh} = sum_ {k in mathbb {z}} left [ binom {2n-2} {n+h-1-k (2h+2)}- binom {2n- 2} {nh-1+k (2h+2)+2h+1} right]. $$ это можно упростить в $$ b_ {n+1, h-1} = sum_ {k in mathbb {z}} Left [ binom {2n} {n+1- (2k+1) h}- binom {2n} {n- (2k+1) h} right], $$, которые, в свою очередь, эквивалентны $$ b_ {n+1, h-1} = sum_ {k geqslant 0} left [ binom {2n} {n+1- (2k+1) h}-2 binom {2n} {n- (2k+1) h}+ binom {2n} {n-1 -(2k+1) h} right]. $$ Разница с ожидаемой формулой заключается в том, что я суммирую нечетные числа (2 тыс. Долл. США+1 $), вместо всех положительных целых чисел ($ K $).

Есть идеи, где проблема?

Answer 1

Монотонные пути от $ ( - h, h) $ to $ (n - 1, n - 1) $, которые вы строите только. в первый раз. Таким образом, формула, которую вы используете, не применима.