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

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$$ ?

• I'd work recursively. Either the first element isn't in the selection, in which case you are down to selecting $k$ elements from $n-1$ total, or it is in the section, in which case you are selecting $k-1$ from $n-4$.
– lulu
Oct 21, 2023 at 17:07
• When you say differ by at least three, I am taking it that $(1,3)$, say, is unsuitable, but $(1,4)$ is ? Oct 21, 2023 at 20:46

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

• I like your argument, but I think you've under-counted! These types of blocks are allowed to be next to each other, which you aren't accounting for. You can fix it by using blocks of width $2$ instead. You should then only add one number at the end, but there are $(n + 1 - 2k) + 1$ spaces in between numbers to place a block, so our answers agree. (Sanity check: $k = 1$ should give $n$ sets) Oct 21, 2023 at 17:40
• @IzaakvanDongen: I had somehow misread the minimum differemce as $2$ instead of $3$, have amended, thanks. Oct 21, 2023 at 18:38
• To me "difference of at least $3$" means eg $\{1, 4\}$ is allowed, but $\{1, 3\}$ isn't. I actually thought your previous answer was closer! Am I right that your result is there's $\binom{n+3-4k}k$ such sets? I think in the extreme case $k = 1$, the answer should be $n$, and when $n=3k-2$, the answer should be $1$. This seems incompatible with your result! As I understand it, when you "place $k$ blocks in $\binom{n+3-4k}k$ ways", you are choosing $k$ gaps in between the remaining numbers. I thought the problem was that this didn't allow $\boxed{\bullet\circ\circ}\boxed{\bullet\circ\circ}$. Oct 21, 2023 at 18:45
• @IzaakvanDongen: Thanks, hurry never does any good, I have amended. Oct 21, 2023 at 19:50

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.