• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter ptolema
  • Start date
  • #1
83
0

Homework Statement



Let k and n be positive integers. In how many ways are there integers a1≤ a2≤ ... ≤ ak≤ 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 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.
 

Answers and Replies

  • #2
lanedance
Homework Helper
3,304
2
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
 
  • #3
83
0
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?
 
  • #4
lanedance
Homework Helper
3,304
2
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?
 
  • #5
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,503
5,435
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?
 

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

Replies
3
Views
375
Replies
5
Views
1K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
4
Views
979
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
22
Views
1K
Replies
3
Views
1K
Top