Selecting $k$ elements from the set $[n]$ such that the numbers selected differ by at least three

Question

How many ways are there to select $k$ elements from the set $[n]$ such that the numbers selected differ by at least three?

I thought of considering two cases: $n-k$ is even or $n-k$ is odd. If $n-k$ is even, then I arrived at ${\frac{n-k}{2}+1}\choose{k}$ ways and if $n-k$ is odd, then there are ${\left\lfloor \frac{n-k}{2} \right\rfloor +1} \choose {k}$ possibilities. To answer this question, I was analysing the ways of choosing k elements from the empty spaces that exist when considering an array on $n-k$ $\textbf{0's}$. Any suggestions for a better argument and what's the answer for a more general case: the k selected numbers should differ by at least $d$ ?

Answer 1

The method that comes to my mind is similar to this: https://math.stackexchange.com/a/1396968/473276. Count the number of functions $f: [k] \to [n]$ such that $f(i + 1) \ge f(i) + 3$ for all $i$ (these functions correspond exactly to subsets of size $k$ with all elements differing by at least $3$). Observe that $f$ is such a function if and only if the function $g: [k] \to [n - 2k + 2]$ given by $g(i) = f(i) - 2i + 2$ is strictly increasing.

So the total number of such functions is $\binom{n - 2k + 2}k$. (Take this to be $0$ if $n - 2k + 2 < k$).

This obviously generalises to $\binom{n - (d - 1)k + d - 1}k$.

PS: if $k = 1$, the answer should be $n$, right? Your formula gives $\binom{\frac{n - 1}2 + 1}{1} = \frac{n - 1}2 + 1$, which is smaller in general.

Answer 2

I had mistakenly the difference as $2$ instead of $3$, amended

• For a difference of $3$, after every chosen number (bullet) except the last , there must be at least two spacers (circles), $\boxed{\bullet\circ\circ}\circ\circ\circ\boxed{\bullet\circ\circ}\bullet$

• From $n$ unnumbered tokens, take out $2(k-1),\;\; (n-2k+2)$ remain

• Choose any $k$ from the above in $\binom{n-2k+2}{k}$ ways, mark them, but don't number them yet.

• Insert from the taken out tokens, $2$ immediately after each of the chosen tokens (except the last), and now allot serial numbers

• This generalises to $\dbinom{n-(d-1)(k-1)}{k}$

---

First Approach added back (simpler?)

• Add $2$ elements [total now $(n+2)$] and form $k$ blocks of one chosen and two unchosen $\boxed{\bullet\circ\circ}$

• There are now $(n+2-2k)$ entities $(k$ blocks plus $(n+2-3k)$ "singles")

• Place the blocks in $\binom{n+2-2k}{k}$ ways and discard the last $2$ elements