2
$\begingroup$

Given two $k$-subsets $I$ and $J$ of $\{1 \dots n\}$, denote by $\min(J)$ the minimal element in $J$ and by $\max(I)$ the maximal element in $I$, we write $I \prec J$ if $\max(I)<\min(J)$. The sets $I$ and $J$ are called weakly separated if at least one of the following two conditions holds:

(1) $J-I$ can be partitioned into a disjoint union $J-I = J' \sqcup J''$ so that $J' \prec I-J \prec J''$;

(2) $I-J$ can be partitioned into a disjoint union $I-J = I' \sqcup I''$ so that $I' \prec J-I \prec I''$.

This condition is introduced in Leclerc and Zelevinsky's paper Quasi-commuting families of quantum minors.

Let $N$ be the number of all weakly separated pairs $I, J$ where $|I|=|J|=k$ and $I, J \subset {1, \ldots, n}.

I have counted certain special cases. In the case of $k=2$, $n$ arbitrary, $N$ is the number of diagonal dissections of an $n$-gon into two regions. In the case of $k=3, n=6$, $N=54$. In the case of $k=3, n=7$, $N=224$. In the case of $k=3,n=8$, $N=652$. In the case of $k=3,n=9$, $N=1557$.

Are there some method in combinatorics to count the number $N$? Thank you very much.

Edit: I forgot to say that I assume that $I \ne J$, $I$ and $J$ are not of the form $a, a+1, \ldots, a_k$ (mod $n$). I counted the pair $I, J$ as a set. So I counted $(I, J)$, $(J, I)$ as one pair (not two pairs). I am sorry about the confusion.

$\endgroup$
11
  • $\begingroup$ It's a certain binomial sum. You may write some generating function in a closed form. But not the entire sum, I am afraid. $\endgroup$ Jan 12, 2021 at 10:05
  • $\begingroup$ @FedorPetrov, thank you very much for your suggestions. $\endgroup$ Jan 12, 2021 at 11:49
  • 1
    $\begingroup$ If we exclude $I=J$ case, and denote $|I-J|=|J-I|=s$, then if we fix the sets $I\cap J$ and $I\Delta J$ (that may be done by ${n\choose k-s,2s,n-k-s}$ ways), there are $2s$ choices of $I-J$. So the answer is $\sum_{s=1}^n 2s\cdot {n\choose k-s,2s,n-k-s}$. $\endgroup$ Jan 12, 2021 at 11:58
  • $\begingroup$ @FedorPetrov, thank you very much. What is the value of ${n \choose k-s,2s,n-k-s}$? $\endgroup$ Jan 12, 2021 at 15:25
  • $\begingroup$ $n!/((k-s)!(2s)!(n-k-s)!)$ $\endgroup$ Jan 12, 2021 at 15:40

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.