I do not know if this problem has already been addressed in number theory known with another name, but I have been some time unsuccessfully trying to find an answer.
In turbo coding a $S$-random interleaver is a scrambling of the bits with the constraint that the distance of the previous $S$ indices of the scrambled sequence have distance $S$ with the next index, that is, $|\pi(i)-\pi(i-j)|> S,j=1,..., S$, where $\pi(i)$ refers to the index of the bit after the permutation. This problem is then to rearrange a sequence of natural numbers $1,...,N$ so that the distance between one of the numbers with its previous $S$ numbers is greater or equal to $S$.
Computational algorithms to obtain such sequences exist, with no guarantee of convergence, and with a reasonable computational time if $S$ is chosen such that $S\leq\sqrt{\frac{N}{2}}$.
I am wondering if it is possible to determine analytically how many $S$-random sequences can be constructed for a given value of $N$.