# Number of Combinations from 1 to 100

Without using a loop / recursive computational methodology, How many ways can I combine the numbers 1 to 100, with another set 1 to 100, so that the sum between set A and B equals 100.

If there were 3 sets, ie A=1..100, B=1..100, C=1..100, how many ways can I combine A, B and C so that A + B + C == 100

-
What are your thoughts on this? – MJD Aug 6 '13 at 3:43
Probably something like the total number of combinations, multiplied by a coefficient representing 1 - the probability of exceeding the limit. – ADP Aug 6 '13 at 3:46
Do you to count the representation $42+58$ as different from $58+42$? If you do, for the general problem, not just $A+B$, but also $A+B+C$, $A+B+C+d$, anything like that, see the Wikepedia article on Stars and Bars. For just $A+B$, just thinking in detail about the possibilities will give you the answer. – André Nicolas Aug 6 '13 at 4:09
Yes they are different. – ADP Aug 6 '13 at 4:19
Then you can just list and count: $(1,99)$, $(2,98)$, and so on to $(49,51)$, $(50,50)$, and so on to $(99,1)$, a total of $99$. For more terms, like $5$ instead of $2$, you would want to use the Stars and Bars idea. For $5$ it is $\binom{99}{4}$. – André Nicolas Aug 6 '13 at 4:37

Solution: using stars and bars and the final key to what you wanted. Ok so suppose that you want to make a paint in a bucket and you have m base colors. How many colors can you make if you can only add paint in quantities of 1/n at a time?

Then each paint is uniquely determined by $a_1,a_2,a_3..a_m$, where $a_i$ is the quantity of paint of the i'th color you add to the bucket(where the quantity is measured in n'ths of bucket. SInce you must fill the bucket then $m_1+m_2+...+m_n=n$

To find this number we use the stars and bars method. where we have the to divide the portions of paint to each color. To do this suppose each portion of paint is a capital $P$ and the portions of paint that are of the i'th color are to the left of the i'th bar but to the right of the (i-1)'th bar.

for example

|PPP|PP|P is the case where there are 0 of the first color, three of the second, two of the third and one of the fourth.

So in how many ways can we select the n-1 bars to divide the n portions into P piles? well there are m-1 bars and n portions. So m+n-1 objects in total. so there are m+n-1 places and we must chose m-1 for the bars so that gives us $\frac{(m+n-1)!}{m!(n-1)!}$

-
OMG. That is just ridiculously easy when you present it like that. Thanks. – ADP Aug 6 '13 at 5:53
Glad I could help, although to be fair André Nicolas had already mentioned it before. – Carry on Smiling Aug 6 '13 at 15:33

Create equations representing the combinations of the sets. For example, your two set equation would look like $A+B=100$. Then you can determine the minimum and maximum values available to each variable and how many combinations will arise.

-