Longest subsequence for certain repeated up/down patterns in random permutations avoiding a pattern of length three

Ross G. Pinsky

Let $S_n$ denote the set of permutations of $[n]$ and let $\sigma ={\sigma }_1\cdots {\sigma }_n\in S_n$. For a subsequence $\{{\sigma }_{i_j}{\}}_{j=1}^k$ of $\{{\sigma }_i{\}}_{i=1}^n$ of length $k\ge 2$, construct the ``u…