How to analyze this expected number of a random tree?

Правка en2, от Y25t, 2021-09-30 10:51:01

In a rooted tree $$$T$$$, let $$$dep_u$$$ be the distance from $$$u$$$ to the root, $$$dis_u$$$ be the distance from $$$u$$$ to the deepest leaf in $$$u$$$'s subtree.

Let $$$f(T)=\sum_{u\in T} dep_u\times dis_u$$$.

Someone says that the expected number of $$$f(T)$$$ is $$$O(n\sqrt{n})$$$ when $$$T$$$ is uniformly randomly chosen from all $$$n$$$ vertices rooted tree.

How to prove it?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Y25t 2021-09-30 12:18:42 0 (published)
en3 Английский Y25t 2021-09-30 12:13:56 1 Tiny change: 'ooted tree.\n\nHow t' -> 'ooted trees.\n\nHow t' (saved to drafts)
en2 Английский Y25t 2021-09-30 10:51:01 216 Tiny change: 's subtree.' -> 's subtree.\nLet $f(T)=\sum_{u\in T} dep_u\times dis_u$, ' (published)
en1 Английский Y25t 2021-09-30 10:26:42 194 Initial revision (saved to drafts)