2
$\begingroup$

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.

  • 1
    The timestamp appears to have come from the same question posted here: http://answers.yahoo.com/question/index?qid=20120422204450AAUDze$9$2012-04-23

1 Answers 1

6

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?