# Ways to select $m$ disjoint groups of consecutive elements from an $n$-element set

In how many ways can you select $$m$$ disjoint groups of consecutive elements (of any size $$\geq 1$$) from an $$n$$-element set?

As an example, I'm thinking of the following case: imagine $$S=\{1,3,5,7,9,11,15\}$$ so that $$n=|S|=7$$. The ways to select $$1$$ (disjoint has no sense here) group of consecutive elements from this set are $$\binom{7}{2} + \binom{7}{1}$$: all 1 element subsets and all subsets which are defined by the two ends for the consecutive elements to be included (e.g., the choice of $$3$$ and $$11$$ gives the set $$\{3,5,7,9,11\}$$).

In your general case, there are $$m$$ beginnings and $$m$$ ends applied to the ordered set of elements

so for example if $$m=2$$ you get $$.(.).(.).$$ with the possibility of putting elements in the $$.$$s

but each $$($$ must be followed by an element so actually you have $$.(x.).(x.).$$ reducing the number of free elements to place down to $$n-m$$. If $$m=2$$, say $$a,b,c$$, and $$n=3$$ then you can position one free element in the $$.$$s and so, since there are $$5$$ .s, there are $$5$$ possibilities:

• $$a(b)(c)$$ where the free element is $$a$$
• $$(ab)(c)$$ where the free element is $$b$$
• $$(a)b(c)$$ where the free element is $$b$$
• $$(a)(bc)$$ where the free element is $$c$$
• $$(a)(b)c$$ where the free element is $$c$$

So you need to choose the positions of the $$2m$$ things fixed by the beginnings and ends and the $$n-m$$ "free" elements, which you can do in $${2m+n-m \choose 2m} = {n+m \choose 2m}$$ ways.

For your example of $$n=7$$ and $$m=1$$ you would get $${7+1\choose 2\times 1}={8 \choose 2}=28$$ which is equal to your $$\binom{7}{2} + \binom{7}{1}$$.

• Could you expand on how the $\binom{2m+n-m}{2m}$ arises?
– Jay
Commented Dec 4, 2021 at 22:34
• You have to position the $2m$ beginnings and ends and the $n-m$ free elements. If you had to position $a$ apples and $b$ bananas then there would be ${a+b \choose a}$ ways of doing it. Here $a=2m$ and $b=n-m$ Commented Dec 4, 2021 at 22:37
• What would the difference in the counting argument be if I'd like all disjoint groups to be non-consecutive? E.g., in your example, the only valid positioning would be $(a)b(c)$.
– Jay
Commented Dec 5, 2021 at 0:31
• @Jay Then you also need all but the last of the $)$s to be followed by an element, so in my notation $.(x.)x.(x.).$, and there are then $n-2m+1$ free elements, making the number of possibilities ${2m+n-2m+1\choose 2m} = {n+1 \choose 2m}$. Commented Dec 5, 2021 at 0:53