Choosing k pairs l distance apart from n numbers I need to choose $k$ pairs of numbers out of first $n$ natural numbers such that the elements in each pair are $l$ distance apart. For example, if $n = 10, k = 3$ and $l = 2$, $\{(1,3),(4,6),(7,9)\}$ is a valid choice. How many such valid choices are there? I worked out for $l = 1$ and it seems to be $\binom{n-k}{k}$.
It must be mentioned that no number can be repeated which means choosing $(1,2)$ and $(2,5)$ is not allowed because it has 2 in common. Also, the pairs are not ordered.
 A: Presumably $n > \ell$ to make this nontrivial.
Consider $V = \{1,\ldots, n\}$ as the vertices of a graph with edges $(i,i+\ell)$.
This has $\ell$ connected components corresponding to the congruence classes mod $\ell$, each of which is a path graph.  If $\ell \mid n$, each component has $n/\ell$ vertices, otherwise there are $\ell-c$ components of size
 $a = \lfloor n/\ell\rfloor$ and $c$ of size $a+1$, where $n \equiv c \mod \ell$.
In general, let's say the $j$'th component has size $n_j$.
Given your result in the case $\ell=1$, the number of possibilities in the general case is then
$$ \sum {{n_1 - k_1} \choose {k_1}} \ldots {{n_\ell - k_\ell}\choose k_\ell}$$
where the sum is over all $\ell$-tuples $(k_1, \ldots, k_\ell)$ with $k_j \ge 0$ and $k_1 + \ldots + k_\ell = k$.  Thus its ordinary generating function with 
respect to $k$ is $\prod_{j=1}^\ell F_{n_j}(x)$ where
$$ F_n(x) = \sum_{k=0}^n {n - k \choose k} x^k = \dfrac{(1 + \sqrt{1+4x})^{n+1} - (1 - \sqrt{1+4x})^{n+1}}{2^{n+1} \sqrt{1+4x}}
$$
