Let $\sigma$ be a permutation of $[k]=\{1,2, \dots , k\}$. Consider all the ordered triples $(\pi, s_{1},s_{2})$, such that $\pi$ is a permutation of length $2k-1$ that is a union of its two subsequences $s_{1}$ and $s_{2}$, each of which is of length $k$ and is order-isomorphic to $\sigma$.

Example:

$\sigma = 312$,

If $\pi = 54213$, then there are $4$ such triples:

$(\pi, 523,413)$

$(\pi, 513,423)$

$(\pi, 413,523)$

$(\pi, 423,513)$

Indeed, each of the listed sequences $s_{1}$ and $s_{2}$, namely $523$, $413$, $513$ and $423$ are order isomorphic to $\sigma=312$, i.e., if the triple is $xyz$, then $x>z>y$.

Denote the number of these triples by $N_{2k-1}^{\sigma}$. Prove that $N_{2k-1}^{\sigma}>\binom{2k-1}{k}^{2}$ for every $\sigma$.

Example: $k=2$. It suffices to show that $N_{3}^{21}>\binom{3}{2}^{2}=9$ since $N_{3}^{21}=N_{3}^{12}.$ In fact, we have 10 triples that are listed below:

$\sigma = 321$: $(321,32,31)$, $(321,31,32)$, $(321,32,21)$, $(321,21,32)$, $(321,31,21)$, $(321,21,31)$.

$\sigma = 312$: $(312,31,32)$, $(312,32,31)$.

$\sigma = 231$: $(231,21,31)$, $(231,31,21)$.

Conjectured generalisation [showed to be false in the answer of @Ilya Bogdanov]: For $1\leq v \leq k$, denote by $N_{2k-v}^{\sigma}$ the number of the triples $(\pi, s_{1},s_{2})$ for which $\pi$ is of length $2k-v$ and $s_{1}$ and $s_{2}$ have $v$ common elements. Is it true that $N_{2k-v}^{\sigma}>\binom{2k-v}{k}^{2}$ for every $\sigma$. Note that for $v=k$, we always have $1$ triple and the conditions holds trivially. When $v=0$, we obviously have $N_{2k}^{\sigma} = \binom{2k}{k}^{2}$ for every $\sigma$ of length $k$.

**LAST EDIT: 2020-04-13.** Below is an interpretation of the right-hand side that may lead to a new, intuitive proof:

Denote by $N_{2k-1}^{\sigma , \sigma'}$ the number of merges of length $2k-1$ for the two patterns $\sigma = \sigma_{1}\cdots\sigma_{k}$ and $\sigma'=\sigma'_{1}\cdots\sigma'_{k}$ of length $k$. Furthermore, let $f(i,j,k) = \binom{i+j-2}{i-1}\binom{2k-i-j}{k-i}$. Note that there exist exactly $f(i,j,k)$ merges of $\sigma$ and $\sigma'$, which have a common element corresponding to $\sigma_{i}$ and $\sigma'_{j}$. Consider a fixed $\sigma$ and $\sigma'$ chosen uniformly at random from $S_{k}$. By linearity of expectation:

$$ \mathbb{E}(N_{2k-1}^{\sigma , \sigma'}) = \sum\limits_{i=1}^{k}\sum\limits_{j=1}^{k}[\mathbb{E}(f(\sigma_{i},\sigma'_{j},k))\cdot f(i,j,k)]. $$ Since $\sigma'_{j}$ has a uniform distribution over $[k]$, for every $j\in [k]$, we have: $$ \mathbb{E}(f(\sigma_{i},\sigma'_{j},k)) = \frac{1}{k}\sum\limits_{u=1}^{k}f(\sigma_{i},u,k) = \binom{2k-1}{k}, $$ since for every fixed $\sigma_{i} = x\in [k]$, $$ \sum\limits_{u=1}^{k}f(x,u,k) = \sum\limits_{u=1}^{k}\binom{x+u-2}{x-1}\binom{2k-x-u}{k-x} = \binom{2k-1}{k}. $$ Then, $$ \mathbb{E}(N_{2k-1}^{\sigma , \sigma'}) = \frac{1}{k}\binom{2k-1}{k}\sum\limits_{i=1}^{k}\sum\limits_{j=1}^{k}f(i,j,k) = \frac{1}{k}\binom{2k-1}{k}\sum\limits_{i=1}^{k}\binom{2k-1}{k} = \\ \frac{1}{k}\binom{2k-1}{k}k\binom{2k-1}{k} = \binom{2k-1}{k}^{2}. $$

Therefore, we have to prove that $$ N_{2k-1}^{\sigma} > \mathbb{E}(N_{2k-1}^{\sigma , \sigma'}), $$ when $\sigma'$ is chosen uniformly at random. Is there a way to use this new form of the statement?

Note: The same interpretation of the RHS, as the given expectation, can be obtained combinatorially, as well.

7more comments