# Non-crossing partitions on a line

If I have $$n$$ posts in the ground, arranged in a horizontal line, how many distinguishable placements of rings are there over the posts, where:

1. The $$i$$th ring encloses $$k_i$$ posts.
2. There are exactly $$\kappa$$ rings.
3. No two rings enclose the same post (a "non-overlapping" partition).
5. Every un-ringed post, by the end, is then assigned a null ring.

These would be "non-crossing" partitions of $$\{1,2,\dots,n\}$$ into equivalence classes, with specific counts $$k_1,\dots,k_\kappa$$ in each class.

So, in the language of set partitions:

If I want to partition an $$n$$-set into classes such that the first class has $$k_1$$ elements, the second $$k_2$$, and so on, with potentially some elements not in a class, and write this number

$$N(n;k_1,k_2,\dots,k_{\kappa})$$

then reject partitions where two classes overlap, such that if e.g. $$\{1,2,3,4,5\}$$ is partitioned into $$\{\{1,2\},\{3\},\{4,5\}\}$$, where $$k_1=2,k_2=1,k_3=2$$, then this does not overlap, but, $$\{\{1,3\},\{5\},\{2,4\}\}$$, where similarly $$k_1=2,k_2=1,k_3=2$$, does overlap, since there exists at least one class which contains non-adjacent integers. In fact, in the example there are two classes with this property: $$\{1,3\}$$ and $$\{2,4\}$$.

If I write this number

$$N^{\star}(n;k_1,k_2,\dots,k_{\kappa})$$

what is this number? It appears to be related to the Stirling numbers of the second kind, but this does not include the adjacency idea.

• Your list of $4$ criteria doesn't match what you describe afterwards. To get that, you'd have to include a fifth criterion that every post is enclosed by a ring. Please clarify which of these two versions of the question you intended. – joriki Feb 3 '20 at 11:29
• How do I describe a partition which doesn't necessarily include every element of the set being partitioned? So not every element of the set needs to be in the partition. – apkg Feb 3 '20 at 12:38
• I don't understand how the fifth criterion you added resolves the discrepancy. If I understand correctly, the "null rings" don't count towards the $\kappa$ rings? But then the "null rings" don't make a difference, and the five criteria are still not in correspondence with the description afterwards, which assigns all rings to $\kappa$ equivalence classes. – joriki Feb 3 '20 at 12:49
• How would I correct the second explanation, such that not all the posts need to be in a ring? Basically the union of the parts of the partition does not need to be the whole set. – apkg Feb 3 '20 at 12:54
• Maybe don't use the equivalence class idea? And just use a set partition? I edited the question. – apkg Feb 3 '20 at 12:55

I hope I’ve now correctly understood what you want to do. As I understand it, you want to count the compositions of $$n$$ with $$\kappa$$ parts coloured black and no two parts coloured white adjacent.
There are $$\binom{n-1}{j-1}$$ compositions of $$n$$ into $$j$$ parts. This needs to be multiplied by the number of ways to select $$w=j-\kappa$$ out of $$j$$ balls to be white without any white balls being adjacent. To count these, glue a black ball to the right of every white ball to obtain $$\binom{j-w}w$$ selections. But that misses the selections where the rightmost ball is white, so we have to add another $$\binom{j-w}{w-1}$$ selections, for a total of $$\binom{j-w}w+\binom{j-w-1}{w-1}=\binom{j-w+1}w$$. Then summing over $$j$$ yields a count of
$$\sum_{j=\kappa}^n\binom{n-1}{j-1}\binom{\kappa+1}{j-\kappa}\;.$$
According to Wolfram|Alpha, this is $$\binom{n+\kappa}{2\kappa}$$. This simple form suggests that there might be a more elegant way to derive it without the detour through a summation.
• Hmm -- I just realized that you wanted the counts for specific $k_i$, not just the total count. I'll edit the answer later... – joriki Feb 3 '20 at 13:46
• Yes the reason I ask here is I can’t see a way of using a multi set argument which conditions on the specific way in which the set is partitioned into subsets with multiplicities $k_i$. But this answer I can use as a foundation. – apkg Feb 3 '20 at 14:11
• I have discovered that I simply need the count of, as you say, compositions (this is what I was looking for) with specific counts of all multiplicities $k_i$. But in fact, there is only one of each which is unique up to permutation of the parts. – apkg Feb 6 '20 at 5:03