1
$\begingroup$

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!

1 Answers 1

1

$$\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.

  • 0
    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!2012-06-17
  • 0
    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.2012-06-17
  • 0
    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.2012-06-17
  • 0
    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?2012-06-18
  • 0
    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.2012-06-18
  • 0
    I typed it into Maple as count:=0; for a from 0 to 90 do for b from a+1 to 120 do for c from max(b+1,50) to 150 do for d from max(c+1,20) to 200 do if max(d+1,30)<=635-a-b-c-d and a+b+c+d<=385 then count:=count+1 fi od od od od; It will probably run all week, since it has to do something like 100,000,000 operations. Maybe they'll come up with something faster on the programming site; maybe it just needs to be done in some other language. Hold on a sec - it halted after just 5 minutes! It says 26,117,655. Anyway, yes, it's nested loops.2012-06-18
  • 0
    Now I understand! I really appreciate it! Thank you. So this is essentially counting the combinations. Using binomial coefficients would find the number of combinations quicker, I think, as you would not have to count/test them. How to do it using this problem proves difficult. Thank you very much!2012-06-18