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
    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