Non-crossing partitions on a line

Question

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).
4. Each ring encloses only adjacent posts (partition into adjacent elements).
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.

Answer 1

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.