IntegerSolution Intermediate

Problem - 4410

Let $\mathbb{S}=\{1,\ 2,\ 3,\ \cdots,\ n\}$ and positive integer $m$ satisfying $n + 1\ge 2m$. Find the number of subsets of $\mathbb{S}$ which has $m$ elements and no two elements are consecutive.


Let the elements in a subset be $x_1$, $x_2$, $\cdots$, $x_m$, and $$a_1=x_1 - (-1),\ a_2=x_2-x_1,\ a_3=x_3-x_2,\ \cdots,\ a_m=x_n-x_{n-1},\  a_{m+1}=(n+2)-x_m$$

Then $$a_1 + a_2 + a_3 +\cdots + a_m + a_{m+1} = n+3$$

where $a_k \ge 2$ for $k=1,\ 2,\ \cdots,\ m,\ m+1$.

Letting $b_k=a_k-1$ gives $$b_1+b_2+b_3+\cdots + b_m + b_{m+1} = n-m+2$$

This equation has $\boxed{\binom{n-m+1}{m}}$ positive integer solutions which is also the number of qualified subsets.

report an error