# Number of ways to choose k people from an alphabetized list of n people, with “gap” g

Suppose I have an alphabetized list of n people, and I want to choose k from the list such that any two people are at least g away from each other on the list

(E.g if g=2, then none of the k people are next to each other on the list).

Is there a formula / general way to solve these types of problems, for any k,n, and g?

-

The problem has a solution only if \ceiling$(n/g)>=k$.
Form a directed graph with each of the $n$ people a ode. Put a directed edge $(u,v)$ whenever $v$ is at least $g$ positions after $u$ in the dictionary. Run a graph traversal algorithm starting at each one of the first $g$ nodes. Each resulting path with length $k-1$ is an answer.