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.



Choosing k pairs l distance apart from n numbers
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}}
$$


