Su “La media Altezza piantato Platani” di Knuth, de Bruijn e Rice (1972)

Question

Sto cercando di ricavare il carta classica nel titolo solo con mezzi elementari (non funzioni generatrici , nessuna analisi complessa, nessuna analisi di Fourier) anche se con molta precisione meno. In breve, ho "solo" Voglio dimostrare che l'altezza media $ H_n $ di un albero con $ n $ nodi (cioè il numero massimo di nodi dalla radice ad una foglia) soddisfa $ H_n \ sim \ sqrt {\ PI n} $.

Lo schema è il seguente. Sia $ A_ {nh} $ essere il numero di alberi di altezza inferiore o uguale a $ h $ (con la convenzione $ A_ {nh} = A_ {nn} $ per tutti i $ h \ geqslant n $) e $ B_ { nh} $ il numero di alberi di $ n $ nodi con maggiore altezza o uguale a $ h + 1 $ (cioè, $ B_ {} nh = A_ {nn} - {A_ NH} $). Poi $ H_n = S_n / A_ {nn} $, dove $ S_n $ è la somma finita $$ 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}. $$ E 'ben noto che $ A_ {nn} = \ frac {1} {n} \ binom {2n-2} {n-1} $, per l'insieme di alberi generali con $ n $ nodi è in corrispondenza biunivoca con il set di alberi binari con $ n-1 $ nodi, contate dai numeri di Catalan.

Quindi, il primo passo è quello di trovare $ B_ {nh} $ e quindi il termine principale per l'espansione asintotico di $ S_n $.

A questo punto gli autori usano combinatoria di analisi (tre pagine) per ricavare $$ 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]. $$

La mia tentativo è la seguente. Considero la corrispondenza biunivoca tra gli alberi con $ n nodi $ e percorsi monotona su una griglia quadrata $ (n-1) \ volte (n-1) $ da $ (0,0) $ a $ (n-1, n-1) $ che non attraversano la diagonale (e sono costituito da due tipi di operazioni: $ \ uparrow $ e $ \ rightarrow $). Questi percorsi sono a volte chiamati percorsi Dyck o escursioni . Posso esprimere ora $ B_ {nh} $ in termini di percorsi reticolari: è il numero di percorsi di Dyck di lunghezza 2 (n-1) e l'altezza maggiore o uguale a $ h $. (Nota:. Un albero di altezza $ h $ è in corrispondenza biunivoca con un percorso di Dyck di altezza $ h-1 $)

Senza perdita di generalità, presumo che cominciano con $ \ uparrow $ (da qui rimanere al di sopra della diagonale). Per ciascun percorso, ritengo il primo passo che attraversano la linea $ y = x + h - 1 $, se presente. Dal punto di cui sopra, tutto il ritorno all'origine, cambio $ \ uparrow $ in $ \ rightarrow $ e viceversa (questo è un riflessione wrt linea $ y = x + h $) . Diventa evidente che i percorsi Voglio contare ($ B_ {NH} $) sono in corrispondenza biunivoca con i percorsi monotone da $ (- h, h) $ a $ (n-1, n-1) $ che evitano i confini $ y = x + 2h + 1 $ e $ y = x-1 $. (Vedere .)

Nel classico libro Lattice Percorso di conteggio e Applicazioni di Mohanty (1979, pagina 6) la formula $$ \ Sum_ {k \ in \ mathbb {Z}} \ left [\ binom {m + n} {mk (t + s)} - \ binom {m + n} {n + k (t + s) + t} \giusto], $$ conta il numero di percorsi monotoni in un reticolo da $ (0,0) $ a $ (m, n) $, che evitano i confini $ y = x - t $ e $ y = x + s $, con $ t> 0 $ e $ s> 0 $. (Questo risultato è stato stabilito in primo luogo dagli statistici russi negli anni '50.) Pertanto, considerando una nuova origine a $ (- h, h) $, soddisfiamo le condizioni della formula: $ s = 1 $, $ t = 2h + 1 $ e il punto di destinazione (in alto a destra) è ora $ (n + h-1, NH-1) $. Poi $$ 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]. $$ Questo può essere semplificata in $$ 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], $$ che, a sua volta, è equivalente a $$ 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]. $$ La differenza con la formula previsto è che riassumo nei numeri dispari ($ 2k + 1 $), al posto di tutti gli interi positivi ($ k $).

Hai idea di dove sia il problema?

Answer 1

The monotonic paths from $(−h,h)$ to $(n−1,n−1)$ that you construct only avoid the boundary $y=x+2h+1$ before they cross $y=x+h$ for the first time. Thus the formula you use is not applicable.