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.

A multi-permutation is non-nesting if and only if the first occurrences of each symbol come in the same order as the second occurrences. So the multi-permutation is uniquely determined by two pieces of information:

1. the order of the first occurrences
2. the pattern of firsts and seconds



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