1

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

ADP
  • 135
  • 1
  • 7
  • What are your thoughts on this? – MJD Aug 06 '13 at 03:43
  • Probably something like the total number of combinations, multiplied by a coefficient representing 1 - the probability of exceeding the limit. – ADP Aug 06 '13 at 03: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 06 '13 at 04:09
  • Yes they are different. – ADP Aug 06 '13 at 04: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 06 '13 at 04:37
  • I didn't get you. You want to find the number of pairs of integers (a,b) such that a+b=100 or the number of subsets A,B of[1,100] such that the sum of all numbers in A plus the sum of all numbers in B gives you 100? – Asinomás Aug 06 '13 at 04:57
  • @Omnitic, not subsets, pairs. But I seek to generalize for more than 3 sets, and, where the increment is smaller (say if the set is: 0, 0.5, 1, 1.5, ... 100) – ADP Aug 06 '13 at 05:01
  • Oh. so you want make n permutations of the set [1,100] and then add all the nth terms of all of the permutations and get 100. for all 100 sums? – Asinomás Aug 06 '13 at 05:04
  • Yes, and for example (1,99) != (99,1), the case of 2 sets is rather trivial (can do it by hand), but when there are 5 or more sets... – ADP Aug 06 '13 at 05:07
  • Consider this, say I want to create a chemical mixture of 5 constituents (ie I mix together 5 different chemicals) for some sort testing. How many experiments am I required to to run, to cover all mixtures, if I am to create a grid with a concentration step (for each constituent) of 0.5%, noting that in each experiment, A + B + C + D + E = 100% – ADP Aug 06 '13 at 05:15

2 Answers2

1

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)!} $

Asinomás
  • 105,651
0

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.

abiessu
  • 8,115