1
$\begingroup$

I am interested to find the number of non-crossing pair partitions on the set $\{1,2,...,2k\}$ such that none of these pair partitions has a pair of the form $(2r-1,2r)$ and there are exactly $t$ pairs of the form $(2i-1,2j)$ where $2i-1<2j$.

Let's go through this slowly. I think we understand what non-crossing pair partitions are, but briefly, a partition whose any block is a pair and if $i<j<k<l$ then $(i,k)$ and $(j,l)$ cannot be blocks, because if we join the elements in the same block by lines, we see that $i,k$ will be joined by a line, and $j,l$ will be joined by a line, which intersect. It is known that the number of non-crossing pair partitions on a set of size $2k$ is equal to $C_k$, the $k$-th Catalan number defined by $C_k=\dfrac{1}{k+1}{2k\choose k}$.

Clearly, since I am talking about pair partitions, my set has to be of even cardinality, hence the $2k$.

I am demanding that my non-crossing pair partitions will not have a pair of the form $(2r-1,2r)$ i.e. $(1,2),(3,4),...,(2k-1,2k)$ cannot be blocks in my partition. I can count the number of such non-crossing pair partitions, because it is easy to count the number of non-crossing pair partitions having at least one of these pairs as a block. That's because, say, we fix $(1,2)$ to be a block, then we are really counting the number of non-crossing pair partitions on a set of size $2k-2$ So this part is fine and can be tackled.

I am also demanding that my non-crossing pair partitions will have exactly $t$ pairs of the form $(2i-1,2j)$ where $2i-1$ is to the left of $2j$, that is, a line joining $2i-1$ and $2j$ begins at $2i-1$. It is well known that the number of such non-crossing pair partitions is equal to a Narayana number.

But can we compute the number of non-crossing pair partitions such that BOTH the above happen? Any help would be appreciated. All search results were giving me how to count 132 avoiding permutations, which I believe is unrelated to this problem.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ It would be helpful for you to list the partitions involved for small n. Even though you make it explicit otherwise, my mind says "avoid (2,3),(4,5)...". Maybe you can embed the list for 2n into the list for (2n+2)? Gerhard "Sometimes Likes It Very Slowly" Paseman, 2018.06.26 $\endgroup$ – Gerhard Paseman Jun 26 '18 at 15:49
  • $\begingroup$ Would a bijection to permutation tableaux yield anything interesting? Or, perhaps, tree-like tableaux would work even better. $\endgroup$ – Alexander Burstein Jun 26 '18 at 20:53
  • $\begingroup$ Don't you necessarily have that all pairs are of the form $(2i-1,2j)$ for some $i \leq j$? Or do you allow some points to be not connected to others? $\endgroup$ – Dirk Jun 28 '18 at 8:19
  • $\begingroup$ Can you give an example of a non-crossing pair partition that does “not have a pair of the form $(2r-1,2r)$? I may misunderstand the definitions, but it seems like none exist. If $(1,k)$ is a pair, $k>2$, and then the partition induces a non-crossing pair partition of $\{2,\dots,k-1\}$, where $k-1>3$, which induces one of $\{3,\dots,k-2\}$, where $k-2>4$, etc. $\endgroup$ – Steve Kass Jun 29 '18 at 23:42
1
$\begingroup$

So, the question is how many non-crossing partitions have exactly $t$ pairs of the form $(2i-1,2j)$, $2i-1 < 2j$ (i.e., $i\leq j$), none of which have $i=j$. By inclusion-exclusion, the number of such partitions equals $$\sum_{i=0}^t (-1)^i \binom{k}{i} N(k-i,t-i) = \frac{1}{k+1}\binom{k+1}{t}\binom{k-t-1}{k-2t},$$ where $N(,)$ are Narayana numbers.

Improve this answer
$\endgroup$

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.