# Counting certain paths in a complete graph

Let $K_n$ be the complete graph with $n$ vertices, where the vertices are labelled $1,2,3,\dots,n$. How many paths are there between $v_1$ and $v_n$ that the labels on the path are strictly increasing?

I know that I need to first choose the possible vertices in the path, then consider the possible order of those vertices.

-
What is the source? The timing suggests a contest or test. – Ross Millikan Apr 23 '12 at 22:11
The timestamp appears to have come from the same question posted here: answers.yahoo.com/question/index?qid=20120422204450AAUDze9 – Henry T. Horton Apr 23 '12 at 22:14

Hint: the only choice you have to make is which vertices between $v_1$ and $v_n$ the path is going to stop at (once you know which vertices to stop at, there is exactly one path that visits them in increasing order). There are $v_n-v_1-1$ such vertices. How many ways are there to answer "stop" or "skip" for each of them?