# The number of ways to merge a permutation with itself

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.

• It's not a homework problem, but ok - I cross-posted here: math.stackexchange.com/questions/3885474/…
– sdd
Oct 28, 2020 at 23:54
• @sdd I think this question is on topic for MO. Oct 29, 2020 at 0:00
• @PietroMajer: It is posed like a homework problem, and no motivation is given. Oct 29, 2020 at 0:44
• There has been some discussion on meta about how the "prove that ..." phrasing might often be a result of English not being the native language of the question-asker (and so we should be more tolerant of questions phrased this way). Oct 30, 2020 at 18:45
• Idea 1 seems to be inapplicable literally if $x_k=y_1$, but there are other coincidences... Oct 31, 2020 at 11:16

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

• You are of course using that for a given matrix $A$, $tr(A)$ is the sum of its eigenvalues. For the last sentence, this link to this math.stackexchange post might be useful: math.stackexchange.com/questions/1365079/… A small typo is that $e$ is an eigenvector, not eigenvalue. Great observation! Thanks!
– sdd
Nov 12, 2020 at 10:23
• I added an interpretation that might be of interest and lead to some new ideas [see the text after "LAST EDIT: 2020-04-13"]
– sdd
Apr 13, 2021 at 8:24

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}$$

• This is what @Iliya Bogdanov mentioned in his answer. Using the rearrangement inequality afterwards is not easy, though..
– sdd
Oct 30, 2020 at 17:33
• Isn't the direction the opposite? For $\sigma=id$, we have the biggest value for the sum.
– sdd
Oct 30, 2020 at 18:28
• Yes, sorry. It's an upper bound then, which shows how tight is the inequality. Oct 30, 2020 at 18:31
• @MaxAlekseyev Every triple $(\pi, s_1, s_2)$ 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$. This gives an upper bound of $(2k-1)^2 \binom{2k-2}{k-1}^2$, which is much better than what the rearrangement inequality gives. This is the scheme I use to encode triples in my probabilistic "proof". Oct 31, 2020 at 2:24
• @sdd: Rearrangement inequality would not help if applied directly -- numerically it gives a bound weaker than needed. I've added a proof for another weaker bound. Oct 31, 2020 at 20:08

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

• Note though that the case of the identity permutation is probably the easiest since any two subsequences of it having the same length have the same relative order. Also, such inductive argument would not work for the other permutations /except the inverse identity/.
– sdd
Oct 29, 2020 at 19:28
• I agree that the identity permutation is probably the easiest, but perhaps there is a clever way to reduce the general case to it (I don't see how at the moment though). Oct 30, 2020 at 1:07
• The identity permutation maximizes the number of triples; see the second part of my answer (which is not an answer to the whole question though). Oct 30, 2020 at 7:24
• @IlyaBogdanov Thanks, I suspected that as well. This justifies the claim that the identify permutation is the easiest to prove the bound for. Oct 30, 2020 at 7:37
• @TonyHuynh Thanks. This idea might still be valuable. I described 2 other ideas in the post that you may check out :)
– sdd
Oct 30, 2020 at 22:56

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

• I have reached the same place in the past. I can only add that if we consider the matrix $a_{ij}=f(i,j)$, then in the sum, the elements of the $i$-th row are multiplied by the elements of $\sigma(i)-$th row. Thus, one may look at the ordering of the elements within a single row. However, the other two ideas that I have just described in the initial post look more promising to me.
– sdd
Oct 30, 2020 at 23:14

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