# Combinations of groups of contiguous items

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!

• This is the so called Stirlings number second kind, see en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind – Student Nov 9 '17 at 14:06
• 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? – Matthew Nov 9 '17 at 14:16
• Now I understand what you mean, but I have no idea yet o.O – Student Nov 9 '17 at 14:21

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$.