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

## Homework Statement

Let k and n be positive integers. In how many ways are there integers a1≤ a2≤ ... ≤ ak≤ n.

## 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 a1, there are n integers to choose from. For the next number, there are 1 + (n-a1) integers to choose from. I'm reasonable sure that I can generalise this to say that for ak, there are 1+(n-ak-1) integers to choose from. From that point, I'm afraid I'm lost as to where to go with this.

Related Calculus and Beyond Homework Help News on Phys.org
lanedance
Homework Helper
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

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 nCk+1, then? Or rather, since the sets are ordered, nPk+1? Is it assumed that the set {a1, a2, ..., ak, n} may not have all distinct elements?

lanedance
Homework Helper
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