# Calculating possible combinations with restrictions

I have five additives that can be mixed into a chemical. Each one can be mixed in at a discrete percentage from 0.02% to 0.22% of the chemical (i.e. 0.02%, 0.03%, 0.04%,...0.22%). Each additive must be present, so mixed in at least 0.02%. The restriction is that the sum of all percentages cannot exceed 0.3%, but the sum can be less than that, so long as each additive is present. Without the restriction the answer is easy. But I can't figure out how to eliminate the number of combinations that would exceed the maximum allowed. If one additive is mixed at 0.22%, then the other four must be 0.02% each and only that.

Thanks!

• Wolfram Alpha solves this problem magically.
– whuber
Jun 21, 2012 at 14:57
• BTW: this problem has little to do with statistics, math.stackexchange.com would be more appropiate Jun 21, 2012 at 19:26
• I actually just discovered this site and didn't know of the math version. I'll check there next time. Thanks. Jun 21, 2012 at 20:01
• If you are new here, you are invited to read this stats.stackexchange.com/faq#howtoask Jun 21, 2012 at 20:06

We must count the number of integer points in a 5-D space ($i=1\cdots 5$) with

$n_i=2\cdots 22$ and $\sum n_i \le 30$

A trivial simplification: let $m_i = n_i-2$, so now we have

$m_i=0\cdots 20$ and $\sum m_i \le 20$

This corresponds to an equilateral 5-D tetraedron (standard simplex). And the number of points if given by the 5-simplex number (generalization of triangular-tetraedral numbers to five dimensions) :

${21 + 5 -1 \choose 5} = 53130$

(Notice that the problem was eased because the restrictions eactly coincide with the simplex. If the maximum number were 31 or 29 instead of 30, it would have been a little more difficult)

I made a 5 dimension array of the sums and then counted which ones were below 31. In R:

a=b=c=d=e=2:22


all combinations of a + b

ab=outer(a,b,FUN="+")


all combinations of a + b + c

abc=outer(ab,c,FUN="+")


...

abcd=outer(abc,d,FUN="+")

abcde=outer(abcd,e,FUN="+")


So the size of abcde is 21x21x21x21x21 about 4million entries

length(
which(abcde<31)
)


Gives:

53130


If you want the combinations listed use:

mixes=(which(abcde<31,arr.ind=T)+1)/100

• It may be instructive to compare the computational effort of this solution to f <- function(t) zapsmall(convolve(t,rep(1,21),type="open")[1:21]); sum(f(f(f(f(s))))), which requires only a few hundred basic operations.
– whuber
Jun 21, 2012 at 19:22
• Not sure what you mean @whuber. It takes .3 seconds to run. many times more seconds to type.
– Seth
Jun 21, 2012 at 19:44
• Seth, try generalizing your solution to, say, an eight dimensional array or to sums of 2:102 instead of 2:22 :-). I will await your answer.
– whuber
Jun 21, 2012 at 19:46
• @whuber is correct; if the question was different my answer would be wrong.
– Seth
Jun 21, 2012 at 19:54
• Seth, you answer is not wrong per se: indeed, it nicely illustrates how the combinations can be enumerated. I was only pointing out that the same enumerations can be carried out in a much more efficient way, which could be helpful for future visitors with similar questions.
– whuber
Jun 21, 2012 at 19:56