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:


1. $(\pi, 523,413)$
2. $(\pi, 513,423)$
3. $(\pi, 413,523)$
4. $(\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.



The number of ways to merge a permutation with itself
By @Max Alexeyev's solution above $N\_{2k-1}^{\sigma}=tr(M\_{k}(P\_{\sigma}M\_{k}P\_{\sigma}^{-1}))$.


The eigenvalues and eigenvectors of $M\_k$ are given here: [Result attribution for eigenvalues of a matrix of Pascal-type](https://mathoverflow.net/questions/278400/result-attribution-for-eigenvalues-of-a-matrix-of-pascal-type).
In particular $\mathbf{e}:=(1,\ldots,1)$ (the all-ones vector) is an eigenvector to the eigenvalue ${2k-1 \choose k}$ for $M\_k$ (and then also for $P\_\sigma M\_k P\_\sigma^{-1}$). Hence $\mathbf{e}$ is an eigenvector of $M\_{k}(P\_{\sigma}M\_{k}P\_{\sigma}^{-1})$ to the eigenvalue ${2k-1 \choose k}^2$.
The desired inequality follows (since the product of symmetric positive definite matrices has only positive eigenvalues).


**UPDATE**: the inequality was already proved in the same way here (Lemma 4.3)
<https://doi.org/10.1016/j.ejc.2009.02.004>


