Skip to main content
MathOverflow

Return to Question

Grammar
Link
Rnd
Rnd
  • 31
  • 3

Regarding left-to-right minimasminima

Grammar.
Source Link
Rnd
Rnd
  • 31
  • 3

Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minimasminima in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is the value $E[max(l_1, l_2, \ldots, l_n)]$ known ? If not, what would be a good direction to compute or simply upper-bound it ? I suspect it is $\mathcal{O}(H_n)$.

Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minimas in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is the value $E[max(l_1, l_2, \ldots, l_n)]$ known ? If not, what would be a good direction to compute or simply upper-bound it ? I suspect it is $\mathcal{O}(H_n)$.

Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minima in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is the value $E[max(l_1, l_2, \ldots, l_n)]$ known ? If not, what would be a good direction to compute or simply upper-bound it ? I suspect it is $\mathcal{O}(H_n)$.

Source Link
Rnd
Rnd
  • 31
  • 3

Regarding left-to-right minimas

Let $\rho$ be a permutation on $[1,n]$ and $l_i$ be the number of left-to-right minimas in $\rho_{i\ldots n}$, I know that for a random permutation $E[l_1] = H_n$ (the $n$-th Harmonic number) but is the value $E[max(l_1, l_2, \ldots, l_n)]$ known ? If not, what would be a good direction to compute or simply upper-bound it ? I suspect it is $\mathcal{O}(H_n)$.