Suppose I have a set S with $N$ elements, $S = \{1,2, ..., N\}$.
Let $S^M$ be the set of all subsets of S with size M, with generic element $s^M$. ($S^M$ has of course $\binom{N}{M}$ elements).
I am interested in orderings of $S^M$ with the following property:
Any element that appears in the $i$th subset, $s_i^M$, must not reappear in the next $T$ subsets, where $T$ is a given natural number.
Formally, $e \in s^M_i \, \,\rightarrow \, \, e \notin \cup_{t=1}^T s_{i+t}^M $
(Of course, the existence of such sequences is not guaranteed for arbitrary $(M,N,T)$).
I am interested in the fowllowing questions:
- Is there a way to check for a given triplet (M,N,T) whether such sequences exist?
- If so, can one also compute the number of existing sequences? (either with or without permutations of the basic elements of $S$.)
- Given some $M,T$, what is the minimum $N$ such that at least one sequence exists?
- Is there a straightforward way to generate one/some/all such subsequences?
I would also generally be happy about any pointers regarding fruitful ways to (re-)formalize the problem, which mathematical fields have appropriate tools or something like this.
(Excuse my likely imprecisions, I'm a layman in terms of mathematics. The last question was meant to ask whether there is a reformulation of the problem in terms of e.g. graph theory, ... , which could be helpful.)
It takes at least $\left\lceil \frac{N}M\right\rceil$ sets for all elements to appear at least once. Each element appears on $\binom{N-1}{M-1}$ subsets, and these subsets must be $T$ apart from each other. Therefore, we must have
$$ \left(\left\lceil \frac{N}M\right\rceil-1\right)+\binom{N-1}{M-1}+T\cdot\left[\binom{N-1}{M-1}-1\right]\leq \binom{N}M,$$
which one can rearrange into
$$T\leq\frac{\left(\frac{N}M-1\right)\binom{N-1}{M-1}\,-\,\left(\left\lceil \frac{N}M\right\rceil-1\right)}{\binom{N-1}{M-1}-1}. $$
Now, whenever $p$ and $q$ are integers with $p\neq 0$ and $q>0$ we have $\left\lceil \frac{p}q\right\rceil=\left\lfloor\frac{p-1}q\right\rfloor + 1$. Letting $\{x\}=x-\lfloor x \rfloor$ denote the fractional part of $x$, we see that
$$\left\lceil \frac{N}M\right\rceil-1 = \left(\frac{N}M-1\right) + \left(1-\frac1M-\left\{\frac{N-1}M\right\}\right)$$
Then the inequality above can be rewritten as
$$T\leq \left(\frac{N}M-1\right)-\underbrace{\frac{1-\frac1M-\left\{\frac{N-1}M\right\}}{\binom{N-1}{M-1}-1}}_{(*)}$$
and $(*)$ should generally be a tiny number, since the numerator lies in $\big(-\frac1M,1-\frac1M\Big]$. A perhaps decent approximation is hence $T\leq\left\lceil\frac{N}M\right\rceil-1$.