1
$\begingroup$

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\}$).

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Could you expand on how the $\binom{2m+n-m}{2m}$ arises? $\endgroup$
    – Jay
    Commented Dec 4, 2021 at 22:34
  • $\begingroup$ 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$ $\endgroup$
    – Henry
    Commented Dec 4, 2021 at 22:37
  • $\begingroup$ 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)$. $\endgroup$
    – Jay
    Commented Dec 5, 2021 at 0:31
  • $\begingroup$ @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}$. $\endgroup$
    – Henry
    Commented Dec 5, 2021 at 0:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .