Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What is the source? The timing suggests a contest or test. –  Ross Millikan Apr 23 '12 at 22:11
1  
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

1 Answer 1

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.