The number of ways to merge a permutation with itself

Question

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.

Answer 1

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. 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

Answer 2

Not sure how it's useful but here is an explicit formula for $N_{2k-1}^{\sigma}$.

For a given permutation $\sigma=(\sigma_1,\dots,\sigma_k)$, we have $$N_{2k-1}^{\sigma} = \sum_{i=1}^k \sum_{j=1}^k \binom{i+j-2}{i-1}\binom{2k-i-j}{k-i}\binom{\sigma_i+\sigma_j-2}{\sigma_i-1}\binom{2k-\sigma_i-\sigma_j}{k-\sigma_i}.$$ Here:

• $i$ and $j$ stand for the indices of the common element in $s_1$ and $s_2$, respectively;
• the product of first two binomial coefficients is the number of ways to interweave $s_1$ and $s_2$ into $\pi$ (the first coefficients accounts for what comes before the common element, the second coefficients accounts for what comes after);
• the product of last two binomial coefficients accounts for the content of $s_1$ and $s_2$ (the first coefficient accounts for the choice of elements smaller than the common one, the second accounts for the choice elements larger than the common one).

Btw, it is easy to see that for the fixed $i$ and $j$, $s_1$ and $s_2$ must share element equal $\sigma_i+\sigma_j-1$.

---

Since when $(i,j)$ runs over $[k]\times [k]$, the pair $(\sigma_i,\sigma_j)$ does the same, we can apply the rearrangement inequality to obtain an upper bound: \begin{split} N_{2k-1}^{\sigma} &\leq \sum_{i=1}^k \sum_{j=1}^k \binom{i+j-2}{i-1}^2\binom{2k-i-j}{k-i}^2\\ &= \binom{4(k-1)+1}{2(k-1)} \end{split} as proved in Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$

---

ADDED 2020-10-31. I've checked the lower bound implied by the rearrangement inequality, and it turns out to be smaller than the required $\binom{2k-1}{k-1}^2$. Anyway, we can easily get another, also weaker, lower bound as follows.

From the explicit formula for $N_{2k-1}^\sigma$, it follows that $$N_{2k-1}^\sigma = \mathrm{tr}(M_kP_{\sigma}M_kP_{\sigma}^{-1}),$$ where $$M_k:=\left[ \binom{i+j-2}{i-1}\binom{2k-i-j}{k-i} \right]_{i,j=1}^k$$ and $P_{\sigma}$ is the permutation matrix corresponding to $\sigma$.

Since both matrices $M_k$ and $P_{\sigma}M_kP_{\sigma}^{-1}$ are symmetric, and share the set of eigenvalues $\left\{ \binom{2k-1}{i}\ :\ i=0..k-1\right\}$, we get this inequality: \begin{split} N_{2k-1}^\sigma &\geq \sum_{i=0}^{k-1} \binom{2k-1}{i}\binom{2k-1}{k-1-i} \\ & = \binom{4k-2}{k-1}. \end{split}

Answer 3

Here is a proof for when $\sigma$ is the identity permutation on $[k]$. Let $(\pi, s_1, s_2)$ be a valid triple for $k$. For each such triple, we can extend $\pi$ to a permutation $\pi'$ of $[2k+1]$ by placing $2k$ and $2k+1$ in positions $2k$ and $2k+1$ (in either order). So, there are two choices for $\pi'$. For each choice of $\pi'$, there are four ways to extend $(s_1,s_2)$ to $(s_1', s_2')$ since $s_1'$ can be either $s_1$ or $s_2$ extended by either $2k$ or $2k+1$ (and then $s_2'$ is fixed). Thus, each valid triple for $k$ can be extended to eight valid triples for $k+1$. Similarly, placing $2k$ and $2k+1$ in positions $2k-1$ and $2k+1$ (in either order), each valid triple for $k$ can be extended to two more valid triples for $k+1$. Thus, each valid triple for $k$ can be extended to ten valid triples for $k+1$. By induction, we get at least $10 \binom{2k-1}{k}^2$ such triples.

We now construct more valid triples for $k+1$.

Place $2k+1$ in position $2k+1$. Next choose a subset $X$ of $[2k]$ of size $k$ and a subset $I$ of $[2k]$ of size $k$ . Place the elements of $X$ in increasing order in the $k$ positions given by $I$. Place the elements of $[2k] \setminus X$ in increasing order in the positions given by $[2k] \setminus I$. This gives a permutation $\pi'$ of $[2k+1]$. Moreover, we can take $s_1'$ to be the elements of $X$ together with $2k+1$ and $s_2$ to be the elements of $[2k] \setminus X$ together with $2k+1$. This gives $\binom{2k}{k}^2$ more valid triples for $k+1$. Note that none of these triples is equal to the previously constructed triples since the common element of $s_1'$ and $s_2'$ in this case is $2k+1$, while the common element of $s_1'$ and $s_2'$ is at most $2k-1$ for the triples constructed by induction.

Finally, place $2k$ in position $2k$ and $2k+1$ in position $2k+1$. Choose a subset $X$ of $[2k-1]$ of size $k$ and a subset $I$ of $[2k-1]$ of size $k$. Place the elements of $X$ in increasing order in the $k$ positions given by $I$. Place the elements of $[2k-1] \setminus X$ in increasing order in the positions given by $[2k-1] \setminus I$. We can take $s_1'$ to be $X$ together with $2k$ and $s_2'$ to be $[2k-1] \setminus X$ together with $2k$ and $2k+1$. We can also interchange $s_1'$ and $s_2'$ (note that this is not symmetric). Thus, we obtain $2 \binom{2k-1}{k}^2$ more valid triples for $k+1$. Again, none of these triples is equal to a previously constructed triple since in this case the common element of $s_1'$ and $s_2'$ is $2k$.

Thus, there are more than $$12\binom{2k-1}{k}^{2}+ \binom{2k}{k}^2 =4 \binom{2k}{k}^2 > \left(\frac{2k+1}{k+1}\right)^2 \binom{2k}{k}^2=\binom{2k+1}{k+1}^2$$

triples for $k+1$.

For the general case, the first part of the above proof still works and gives a bound of at least $8^{k-1}$ triples for an arbitrary permutation $\sigma$ of length $k$.

Answer 4

Here are two observations. First, I show that the generalized conjecture is false for $v=k-1$. Second, I suggest some approach to an initial one.

---

1. Assume that $v=k-1$. Consider any triple $(\pi,s_1,s_2)$, and let $i$ be the position of $\pi$ absent in $s_1$, and $j$ be the position of $\pi$ absent in $s_2$. Then the subwords at positions $[i,j-1]$ in $s_1$ and $s_2$ map to each other under the order isomorphism; this easily yields that $\pi_1,\dots,\pi_j$ is a monotone run of consecutive integers. This run may be long enough only if $\sigma$ contains consecutive integers at consecutive positions.

So, if, say, $\sigma=(k/2+1,1,k/2+2,2,\dots,k,k/2)$ (for even $k\geq 4$), then the only triples you get are those where $i$ and $j$ are adjacent, as well as $\pi_i$ and $\pi_j$. There are two such triples for every pair $(i,j)$, so $2k$ triples at all. This is smaller than ${k+1\choose k}^2$ for all $k\geq 4$.

A concrete example: $k=4$, $\sigma=(3,1,4,2)$, $v=3$, the number of triples is $8$.

---

2. Now comes some (unfinished) approach for the case $v=1$.

Assume that $s_1$ and $s_2$ match at the $i$th term of $s_1$ which coincides with the $j$th term of $s_2$ and equals $a$. Then we know that $s_1$ contains $\sigma_i-1$ terms smaller than $a$, while $s_2$ contains $\sigma_j-1$ such. Hence, $a=\sigma_i+\sigma_j-1$ is reconstructed from $i$ and $j$, and $a=\pi_{i+j-1}$.

Now, for fixed $i$ and $j$, in order to reconstruct the whole triple, we need to split the numbers $1,2,\dots, a-1$ into sunsets of cardinalities $\sigma_i-1$ and $\sigma_j-1$ (which will go to $s_1$ and $s_2$), split the numbers $a+1,\dots, 2k-1$ into similar sets, and then split the positions $1,2,\dots,i+j-2$ into subsets of cardinalities $i-1$ and $j-1$ (which will participate in $s_1$ and $s_2$) and split the positions $i+j,\dots,2k-1$ similarly.

All in all, the number of triples becomes $$ \sum_{1\leq i,j\leq k} f(i-1,j-1)f(\sigma_i-1,\sigma_j-1), \quad \text{where}\quad f(x,y)={x+y\choose x}{2(k-1)-(x+y)\choose (k-1)-x}. $$

It may be possible now to investigate this sum by means of the rearrangement inequality. That inequality easily gives that the number of triples is maximal when $\sigma=\mathrm{id}$ (which has been considered in another answer). But, to reach the minimum, we need to know the ordering of $f(x,y)$, which does not seem to be that clear...

Answer 5

Here is a probabilistic 'proof' of the result. Let $\sigma$ be a permutation of $[k]$. Every triple $(\pi, s_1, s_2)$ for $\sigma$ is determined by the common element $a$ of $s_1$ and $s_2$, the position $i$ of $a$ in $\pi$, the positions $I \subseteq [2k-1] \setminus \{i\}$ in $\pi$ of $s_1 \setminus a$, and the elements $A \subseteq [2k-1] \setminus \{a\}$ placed in $I$.

Conversely, let $(a,i,A,I)$ be a quadruple such that $a \in [2k-1], i \in [2k-1], A \subseteq [2k-1] \setminus \{a\}$, and $I \subseteq [2k-1] \setminus \{i\}$. We want to know how many such quadruples generate a valid triple.

Let $(a,i,A,I)$ be a randomly chosen quadruple. Let $\rho_1=|I \cap [i-1]|+1$ and $\rho_2=i-\rho_1$. Sort both $A \cup \{a\}$ and $[2k-1] \setminus A$ according to $\sigma$ and let $\gamma_1 \in [k]$ and $\gamma_2 \in [k]$ be the respective positions of $a$ in these lists.

The key observation is that $(a,i,A,I)$ generates a valid triple if and only if $\rho_1=\gamma_1$ and $\rho_2=\gamma_2$. If we dubiously assume that each of $\rho_1,\rho_2,\gamma_1, \gamma_2$ are uniform distributions on $[k]$ and they are independent, then the probability that $(a,i,A,I)$ generates a valid triple is $\frac{1}{k^2}$. Therefore, under these dubious assumptions, the total number of valid triples for $\sigma$ is $\frac{1}{k^2}(2k-1)^2 \binom{2k-2}{k-1}^2=\binom{2k-1}{k}^2.$

On the other hand, this approach is completely general in the following sense. If the bound holds, then the probability that a random $(a,i,A,I)$ generates a valid triple must be at least $\frac{1}{k^2}$. Thus, it only remains to give a rigourous proof that the probability is always at least $\frac{1}{k^2}$.