# Is there a formula for nCr that considers a min/max range? (restricted composition estimation)

I'm bad at math and hope I explain this right(please don't be upset if I don't, I'm not trying to be lazy or a jerk, I really don't understand what information is sometimes required and focus on the wrong part I think is important).

Basically I have a program that looks for combinations. The best way to explain is it vai an example, say you have 4 items you want to buy at a store: apple,peach,pear and orange. You want to know how much percent you can fit of each into a basket but you tell yourself you want a min. of 20% of each item and a max of 60% of each item(so apple:25%, peach:25%, pear:25%, and orange:25% works perfectly but not apple:0%, peach:0%, pear:50%, and orange:50% because we set a min of 25%).

So my program seems to work and using the above example, I found this code that helps me figure out exactly how many results to expect:

import math

def nCr(n,r):
f = math.factorial
return f(n) / f(r) / f(n-r)

if __name__ == '__main__':
print nCr(20+4-1,20)  #percent+buckets(items)-1, percent


this gives me the correct answer(1771) because it doesn't need to factor in the max(60%) because its never reached(it only uses 20% as the input). But is there a way I could modify this formula(or use something else) that would tell me how many results to expect if I have something like 40 items with a range of 2-5% or something(something that factors in the max value as well).

Any help would be great..As I mentioned, I'm not good at math so if possible can you explain it as simply as possible?

-

This is a form of restricted composition (similar to a partition, but with order mattering), which you can calculate using recurrences. You seem to be assuming exact percentages.

I have a Java applet which does something similar and you can see the code (though it was not designed to be easy to read for anyone else: this particular calculation uses the fifth of the Composition methods).

The applet assumes each part is at least 1, so you would have to recast your problem: the number of compositions of 100 into exactly 4 parts with each part at least 20 and no more than 60 is the same [by taking 19 off each of the 4 parts] as the number of compositions of 24 into exactly 4 positive parts with each part no more than 41. As you say, the answer is 1771.

Similarly the the number of compositions of 100 into exactly 40 parts with each part at least 2 and no more than 5 is the same as the number of compositions of 60 into exactly 40 positive parts with each part no more than 4. The applet gives an answer of 1725325033144622.

-
Thanks so much Henry, this looks awesome..I understand the postive parts, no more than(is the range)..but what is composition how are you deriving 24 and 60? 24 in my example was min range(20%)-items(4), but in the second example min(2-40 is not 60)..I'm confused. Also are you running the code directly of via the site? its been running 15 minutes for me to test your examples. –  Lostsoul May 26 '12 at 0:20
come to think about it, if you have the formula it might be easier as I have a function that I can just plug the numbers into.. –  Lostsoul May 26 '12 at 1:11
@Lostsoul: Each time I reduced the minimum to $1$: I took $19$ off each of the $4$ parts and $100-19\times 4 = 24$. In the second case I took $1$ off each of the $40$ parts and $100-1\times 40 = 60$. –  Henry May 26 '12 at 8:39
Thanks for that Henry. Did you run this on the site you sent me? I have been trying to run the applet but I never get any results. I've tried it with both the latest firefox/chrome(I am using a mac). Is it working for you? and if so how long does it take(I stop it after 10 minutes)? –  Lostsoul May 29 '12 at 3:31
or better, do you know the formula for this? I think I can program it myself if I can see the logic. –  Lostsoul May 29 '12 at 3:42