Randomly selecting integers with prescribed minimal distance and estimations I am interested in sequences of  $M$ distinct integers in $[[1,N]]$ (integers from $1$ to $N$) such that  integers $I_m$ are separated by at least $\delta$ integers (taking into account the outer bounds $0$ and $N+1$)?  For instance with $N=11$, $M=3$ and $\delta=2$, we impose that $|I_m-I_{n}|\ge 3$ when $m\neq n$; only the sequence $(3,6,9)$ is valid. For $\delta=1$, there are more admissible sequences ($(2,4,6),(2,4,7),(2,4,8),(2,4,9),(2,4,10),(2,5,7),(2,5,8),\dots$). I imagine that this problem has been tackled. Yet I lack appropriate references, keywords and algorithms. I suspect this could be related to a concept of discrepancy.
The lazy approach I have used so far is to divide $N+1$ into $M+1$ intervals (when $\delta(M+1)+M\le N$) and pick the  $I_m$ inside those intervals. This is however totally suboptimal in the diversity of sequences.

*

*How to randomly pick (when this is possible) uniformly an admissible sequence?

*Can one compute the number of admissible sequences (with $N$, $M$ and $\delta$)?

*Or can one estimate asymptotics  in a regime where $M$ is sensibly smaller than $N$ (say $M \sim N^\lambda$, $\lambda \le \frac{1}{2}$)?

In practice, I would use such an algorithm on sequences with typically $N \in[10^3,\dots,10^6]$ and $\delta \in[[1,10]]$.
 A: This answer only addresses point (2), the combinatorics.

Can one compute the number of admissible sequences (with N, M and δ)?

Special case of $\delta=1$
In the special case of $\delta = 1$, your problem is equivalent to the $k$-composition of $N$ with $k = M+1$. If you think of the set of steps $a_i$ between elements of your sequence, you need the composition of $N+1$ into $k$ parts:
$$\sum_{i=0}^{k} a_i = N+1$$
It's $N+1$, because as I understand from your first example, you want to enforce that the last number in the sequence must be more than $\delta$ away from $N+1$
The binomial coefficient ${N\choose k-1}$ gives the number of such compositions.
Of course, the elements of the sequence that you care about would be $x_j = \sum_{i=0}^j a_i$.
General case
For arbitrary $\delta$, this becomes the $S$-restricted composition - $S$ is the set of integers that can be chosen to form the sum.  In your case $\{ s : s > \delta\}$ There is an expression for it in "Restricted Weighted Integer Compositionsand Extended Binomial Coefficients" (See Equation (3))
To summarize, form this polynomial of $x$:
$$ \sum_{s\in S}( x^s )^k$$
the coefficient of degree $x^{N+1}$ gives the number of $S$-restricted compositions of $N+1$.
Example
Your example of:
$N=11$, $M=3$, $\delta=2$, means $k=M+1=4$, and we know there is just one way to do this.
We need to form polynomial
$$ (x^3 + x^4 + x^5 + x^6 + ...)^4 $$
and find the coefficient in front of $x^{N+1} = x^{12}$. It's easy to see in this example that the coefficient is $1$, as expected.
