# Counting non-nesting multi-permutations

Given a sequence $1,1,2,2,3,3, …,k,k$, I am interested in counting the number of non-nesting permutations of the above sequence. Two intervals (determined by symbols $K$ and $L$) are nesting if one is completely contained inside the other. A multi-permutation is non-nesting if for any two symbols $K$ and $L$, the corresponding intervals ( $[K,K], [L,L]$) are non-nesting.

For instance, $122313$ is nesting permutation since the interval defined by the two copies of $2$ is contained inside the interval defined by $1$.

What is the count of non-nesting multi-permutations? What is known about these special multi-permutations?

P.S. I know that the total number of permutations of $1,1,2,2, ... ,k,k$ is given by $(2k)!/2^k$.

Update: I found this is equivalent to counting nonnesting matchings on [2n] which is equal to Catalan number$C_n$ . See reference: Catalan numbers by Stanley.

• Have you tried computing the first few values and seeing what OEIS has to say about it? – munchhausen Jun 19 '18 at 7:03
• @Munchhausen OEIS does not say anything about non-nesting multi-Permutations. – Mohammad Al-Turkistany Jun 19 '18 at 7:47

A pattern is of the form FSFFFSSS, and the only restriction on possible patterns is that every initial segment contains at least as many F as S. So these are just the Dyck paths of length $2k$.
• Thanks for your answer. Are you aware of any literature references to non-nesting permutations of $1,1,2,2, …, k,k$? – Mohammad Al-Turkistany Jun 19 '18 at 9:52
• I found this is equivalent to counting nonnesting matchings on [2n] which is equal to Catalan number$C_n$ . See reference: Catalan numbers by Stanley. – Mohammad Al-Turkistany Jun 21 '18 at 19:55