0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – joriki Feb 3 '20 at 11:29
  • $\begingroup$ 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. $\endgroup$ – apkg Feb 3 '20 at 12:38
  • $\begingroup$ 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. $\endgroup$ – joriki Feb 3 '20 at 12:49
  • $\begingroup$ 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. $\endgroup$ – apkg Feb 3 '20 at 12:54
  • $\begingroup$ Maybe don't use the equivalence class idea? And just use a set partition? I edited the question. $\endgroup$ – apkg Feb 3 '20 at 12:55
1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Hmm -- I just realized that you wanted the counts for specific $k_i$, not just the total count. I'll edit the answer later... $\endgroup$ – joriki Feb 3 '20 at 13:46
  • $\begingroup$ 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. $\endgroup$ – apkg Feb 3 '20 at 14:11
  • $\begingroup$ 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. $\endgroup$ – apkg Feb 6 '20 at 5:03

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.