Inequality proof: how many ways are there a1 =< =< ak =< n?

[ptolema]

Homework Statement

Let k and n be positive integers. In how many ways are there integers a₁≤ a₂≤ ... ≤ a_k≤ n.

Homework Equations

The Attempt at a Solution

I don't really know where to begin. Simply using permutations doesn't seem to work. I know that for a₁, there are n integers to choose from. For the next number, there are 1 + (n-a₁) integers to choose from. I'm reasonable sure that I can generalise this to say that for a_k, there are 1+(n-a_k-1) integers to choose from. From that point, I'm afraid I'm lost as to where to go with this.

 

[lanedance]

well deciding on a set with a1≤ a2≤ ... ≤ ak≤ n effectively partitions n integers into k+1 groups, preserving order, so maybe you could see if you can figure how many ways there is to form k+1 partitions from n objects

 

[ptolema]

well deciding on a set with a1≤ a2≤ ... ≤ ak≤ n effectively partitions n integers into k+1 groups, preserving order, so maybe you could see if you can figure how many ways there is to form k+1 partitions from n objects

So you're saying that n integers have been partitioned into (k+1) element groups, just to be clear? Would it be _nC_k+1, then? Or rather, since the sets are ordered, _nP_k+1? Is it assumed that the set {a1, a2, ..., ak, n} may not have all distinct elements?

 

[lanedance]

Try to put some reasoning behind your arguments, rather than just throwing expressions. I haven't done the work so can't just tick a box, just trying to guide your thinking..

Another good way to start that may help is always to try a simple example, pick say n=5 and k=2. Now consider the ways to arrange 2 x's and 3 o's, how many different arrangements are there? Can you relate that to the problem at hand and are there any combinations that don't line up with the question?

 

[haruspex]

There seems to be a piece of information missing. can't just be integers since that allows negatives, and there'd be an infinity of solutions. So should we assume a1 >= 0 or a1 >= 1?
lanedance's suggestion is good, but there's a trick to solving that. Imagine the integers 1 to n in a line. Insert markers into the line to show where the ai are: the first marker lies to the right of a1 and left of a1+1; second marker lies to the right of a2 (and to the right of the first marker if a1=a2), and to the left of a2+1, etc.
Does each choice of a1...ak lead to a different arrangement of markers? And vice versa?