How would you find the number of combinations for a set of elements, where the elements have minimum and maximum values and the set is in lexicographic order.

As an example:

$a+b+c+d+e=635$, which may be...

${[0-90] + [1-120] + [50-150] + [20-200] + [30-250] = 635}$

where elements b, c, d and e must be greater than the element that precedes it. As in, "b" must be greater than "a" by at least one, etc.

I have tried using inclusion-exclusion principle but I'm having trouble getting the correct answer. If I use ${639\choose4}$ and inclusion-exclusion, I get the number of combinations obeying the max/min constraints, but including those not in lexicographic order. If I use ${150\choose5}$, I have a number of combinations in order, but includes combinations that do not sum to 635 or that obey all constraints.

Thank you very much for all your help!


$$\sum_{a=0}^{90}\sum_{b=a+1}^{120}\sum_{c=\max(b+1,50)}^{150}\sum_{d=\max(c+1,20)}^{200}x$$ where $x=1$ if $\max(d+1,30)\le635-a-b-c-d\le250$, $x=0$ otherwise. Shouldn't be so hard to program a computer to do that sum.

  • $\begingroup$ Thank you very much! How would the order of operations and steps be to program and solve those summations with those indexes that depend on the summation before it in the series? How does this solution compare with inclusion-exclusion? Wonderful equation! $\endgroup$ – user33836 Jun 17 '12 at 23:08
  • $\begingroup$ How to program it is a good question for the programming website. In pseudocode, maybe something like this. For a from 0 to 90, for b from a+1 to 120, for c from max(b+1, 50) to 150, for d from max(c+1, 20) to 200, if max(d+1,30) at most 635-a-b-c-d and a+b+c+d at most 385, then add 1 to count. Compared to inclusion-exclusion (hereinafter, i-e), it has the advantage that I could write it down without thinking much, whereas two minutes' thought was not enough for me to see an i-e way to do it. If there is an i-e way to do it, the i-e way will have the advantage of being hand-computable. $\endgroup$ – Gerry Myerson Jun 17 '12 at 23:39
  • $\begingroup$ Would you want to give the i-e way a go as answer #2? Seems like it would be an easier/faster way to solve. Thank you for explaining the possible code. $\endgroup$ – user33836 Jun 17 '12 at 23:53
  • $\begingroup$ Since you have tried i-e two different ways without success, what makes you think i-e would be easier or faster? Can you use i-e for a much simpler problem, say, $a+b=100$, $10\le a\le 40$, $b\ge a+1$, $20\le b\le85$? If you can figure out how to use i-e to do that one, I bet you can figure out how to use it for the original problem; and if you can't do the simpler problem using i-e, what hope is there of using it for the original problem? $\endgroup$ – Gerry Myerson Jun 18 '12 at 4:23
  • $\begingroup$ I guess I was only hoping it would be, since you said i-e would be hand-computable. I asked how to code this on the programming site. It still don't understand the procedure of this summation equation, especially the indexes c=max(b+1,50) and d=max(c+1,20). Are we adding the four summations once they are solved or is each summation an indexed variable of the one to the left, where x is 1? If so, then it sounds like it would be nested loops, where "a" gets incremented for b=a+1, as for the others. Difficult for me to visualize the code in all this. I appreciate your assistance. $\endgroup$ – user33836 Jun 18 '12 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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