3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Thanks for your answer. Are you aware of any literature references to non-nesting permutations of $1,1,2,2, …, k,k$? $\endgroup$ – Mohammad Al-Turkistany Jun 19 '18 at 9:52
  • $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Jun 21 '18 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.