1
$\begingroup$

For a list of elements, how many ways are there to make X groups of Y continuous elements? E.g.

2 groups of 2 elements for this list:

1 2 3 4 5

There are 3 ways:

(1,2)(3,4)

(1,2)(4,5)

(2,3)(4,5)

Is there a closed form way to compute this? Typical combination/permutation forumulas don't seem to apply because some choices of early elements aren't valid (if we choose (3,4) then we can't make a complete second group, choosing (1,2) would just be a duplicate of the earlier solution).

Any help is appreciated!

$\endgroup$
  • $\begingroup$ This is the so called Stirlings number second kind, see en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind $\endgroup$ – Student Nov 9 '17 at 14:06
  • $\begingroup$ That is very close, but Stirling numbers of the second kind don't restrict that the groups have equal size or be continuous. Is there a modification to the formula to accomplish that? $\endgroup$ – Matthew Nov 9 '17 at 14:16
  • $\begingroup$ Now I understand what you mean, but I have no idea yet o.O $\endgroup$ – Student Nov 9 '17 at 14:21
0
$\begingroup$

Treat each group of Y continuous elements as a dash, and the remaining individual elements as dots. Assuming there are N elements in the list, there is a bijection between the groupings you wish to count and strings of X dashes and N-XY dots; for example, for X=2, Y=3 and N=10, "..-.-." maps to (3,4,5)(7,8,9); on the other hand (2,3,4)(6,7,8) maps to ".-.-..". The number of such strings is ${N+X-XY} \choose X$.

$\endgroup$
  • $\begingroup$ That is very clever. Thank you for your help! It seems to check out for all the tests I throw at it. The problem I was trying to solve apparently has 2.4 x 10^25 possible cases. I was afraid it would a lot but I didn't know it would be that much! You saved the day $\endgroup$ – Matthew Nov 9 '17 at 15:16
  • $\begingroup$ To give credit where due, I borrowed the argument from @joriki in a different context. $\endgroup$ – Jeremy Dover Nov 9 '17 at 16:58

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.