Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 30, 2012 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Oct 30, 2012 #2


    User Avatar
    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
  4. Oct 30, 2012 #3
    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?
  5. Oct 30, 2012 #4


    User Avatar
    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?
  6. Oct 31, 2012 #5


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook