Dan Asimov wrote (by his own admission, too early in the morning!)
Given the two integers X1 and Xk with 1 <= X1 <= Xk <= N, the above sequence is determined by the placement of the I = Xk - X1 increments among the k-1 locations the increments can occur: going from X1 to X2, or X2 to X3, etc. [etc]
Better: always allow N-1 increments. They may come before the first element of the sequence, or after the last.
Think of the I increments as dots in a row. The number of ways they can be distributed into k-1 bins is the same as the way we can separate the I dots using k-2 vertical lines each before, between, or after the I dots. (Two or more separators are allowed to have 0 dots between them.)
Now we have k dots and N-1 lines, for (N+k-1 choose k) possibilities. Sanity check: when k=1 we have (N choose 1) = N possibilities, which is right (N choices of 1-element sequence). When N=2 we have (k+1 choose k) = k+1 possibilities, which is right (some 0s then some 1s, and we can have any number of 0s from 0 to k). -- g