Ways to choose $m$ distinct natural numbers from set of first $n$ natural numbers, s.t. the chosen natural numbers differ by at least $k$.
Request vetting for my approach:
The numbers to be chosen are $m$, with at least $k$ 'buffer' contiguous numbers.
Say, if $n=25, m=4, k=3$, then few possible choices are stated below with chosen $m$ elements 'outside of brackets', while $\ge (k-1)$ buffers in brackets. :
#1: $1,(2,3), 4, (5,6), 7, (8,9), 10, (11,12,13,14,15,16,17,18,19,20,21, 22,23,24,25)$
#2: $(1),2,(3,4), 5, (6,7,8,9), 10, (11,12), 13, (14,15,16,17,18,19,20,21, 22,23,24,25)$
#3: $1,(2,3,4,5), 6, (7,8,9,10,11,12,13,14,15,16,17,18,19), 20, (21,22,23),24,(25)$
#4: $(1),2,(3,4,5), 6, (7,8,9,10,11,12,13,14,15,16,17,18,19), 20, (21,22,23,24),25$
As can be seen, the $m$ chosen ones form $m+1$ slots, with two 'border ones' (one before the first marker element, & one after the last marker) possibly being empty or can have $\lt k-1$ buffer elements.
Need choose $m$ markers defining boundary of $m+1$ slots, with at least $k-1$ elements in non-empty slots.
So, need reserve for non-empty slots (all apart from 'border ones') at least $k-1$ elements, leading to reserving $(m-1)(k-1)$ elements from $n$. From the left out elements, need choose $m$ elements. Simply, need to subtract from the $n$ elements, $(m-1)(k-1)$ elements. This makes available needed buffer elements.
(Kindly note that it covers cases where the first (or, any other element) is a marker, as well as the cases where the first (or, any other element) element is a buffer.)
Then, choose $m$ markers. So, need choices for that first.
Need choose later from the free elements.
So, get in the first step ${n-(m-1)(k-1) \choose m}$ choices.
To see, a small example, for $n=6, m=2,k=3$, get the #choices as : ${6-(2-1)(3-1) \choose 2}= {4 \choose 2}= 6$. These choices are:
#1. $1(23)4(56)$,
#2. $1(234)5(6)$,
#3. $1(2345)6$,
#4. $(1)2(34)5(6)$,
#5. $(1)2(345)6$,
#6. $(12)3(45)6$,
Also, in second step need place $n – m – (n-1)(m-1)$ elements in their proper slots.
But, there are no choices available for the second step, as the values of elements (due to some sort of ordering, which indicates the need of ordering, or classification for elements) dictate their slot. In other words, the second step is completed in the first one.
Hence, the choices of the first step dictate the answer.
This gels with the multisets based star-and-bars approach's answer.
Edit:
But, the elements are indistinguishable for that, so indistinguishability (as in answer by @ChristianBlatter, by taking one set of selection as $1$, others as $0$) is w.r.t. the possibility of elements being in a class. Here, the elements are ordered (as in the selected answer), yet indistinguishable in a class! The abstraction of class is marked by slots' value, and the slot is chosen based on any left $m$ choices after taking $(m-1)(k-1)$ values from $n$, with no arrangements as ordering cannot be changed for elements chosen as slots ($m$).
The formula for multisets will be ${(n'+m-1) \choose m}$ choices.
This can be viewed as $n' = (n – (m-1)(k-1))+1$, and the size of multiset =$m$, which is fixed. The #of multisets gives all possible choices of getting a given size multiset for a given $n'$.
The factor $n'-1$ in the formula for multisets : ${(n'-1+m) \choose m}$, shows that we take/adapt multisets' formula to mean that the roles of marker is being taken by free elements, and the slots formed by the free elements is given by $n'$. So, the actual markers/ #free elements are given by: $n'-1$.
Taking the above small example, to show the adaptation of logic to make free elements act as markers is:
$n=6, m=2,k=3, n'= 6-(2)(1)= 4.$
#1. Taking $2,5$ as buffer, get free elements as: $1,3,4,6$.
$3$ forms the first boundary, and $6$ the second one. The chosen elements in set $m= 1,4$: $1(23)4(56)$,
#2. Taking $2,3$ as buffer, get free elements as: $1,4,5,6$.
$4$ forms the first boundary, and $6$ the second one. The chosen elements in set $m= 1,5$: $1(234)5(6)$,
and so on by taking suitably buffer elements, free elements as markers, and chosen elements; for the rest three cases.
Best Answer
i think its correct,however we could rewrite diffrently
Suppose we select the $m$ numbers $x_1<x_2......<x_m$,
let $y_{i}$ denote the number of integers between $x_{i},x_{i+1}$ Easy to see $y_i\ge k-1$ for $1\le i\le m-1$ Also let $y_0,y_{m}$ be the number of integers before $x_1$ and after $x_m$.Again $y_{0},y_{m+1}\ge 0$.
Hence we have to find number of solutions of $$y_0+y_1..+y_m=n-m$$ with the condition $y_0,y_m\ge 0$ and $y_i\ge k-1 $ for $1\le i\le m-1$.We sub $y_0=t_0,y_m=t_m,y_i=t_i-k+1$ for $1\le i\le m-1$
$$t_0+t_1+t_2....t_m=n-m-(m-1)(k-1)$$ where $t_i\ge 0$ which is just the stars and bars problem to get $$\binom{n-(k-1)(m-1)}{m}$$