Local extrema in random trees (Q2368505)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Local extrema in random trees |
scientific article |
Statements
Local extrema in random trees (English)
0 references
19 April 2006
0 references
Consider the \(n^{n-2}\) labelled \(n\)-vertex trees \(T\) rooted at a given vertex \(r\). Suppose the path from the root of \(T\) to vertex \(k\) contains the path \(ijk\). Then \(T\) is said to have a local maximum at path \(ijk\) if \(j>i\), \(k\) and a local minimum if \(j<i\), \(k\). Let \(M_r\) and \(m_r\) denote the number of local maxima and local minima in such a tree. The author derives explicit expressions for the mean and variance of \(M_r\) and \(m_r\) when \(r=1\), \(n\) as rational functions of \(n\), assuming the \(n^{n-2}\) trees are equally likely; in particular, \(E(M_1)=E(m_n)= (2n^3-3n^2-5n+6)/6n^2\).
0 references
labelled trees
0 references
permutation statistics
0 references