You are here:

Advanced Math/Combination

Advertisement


Question
QUESTION: In Excel,
A1=3 (Spaces of Timeline) [say 6hrs before sunrise to sunrise=1, Sunrise to next Sunrise=2, Next sunrise to 6 hrs after next sunrise=3)
A2=7 (Interval Points of a Flexible-stretchable-Time-span)

What are the possibilities of Time-Span points to be in different Spaces of the Timeline? [say all 7 points of that timespan can be in the space 1, or 6 in space 1 and the seventh in space 2 or in space 3 etc.]

What is the formula to generate below 36 unique combinations?
It should also work when I change the numbers in cell A1 or A2.
If A1=4 then one more column should be added, if A2=9 then combinations should be displayed for 9 'n's.


  1   2   3
1   nnnnnnn      
2   nnnnnn   n   
3   nnnnnn      n
4   nnnnn   nn   
5   nnnnn   n   n
6   nnnnn      nn
7   nnnn   nnn   
8   nnnn   nn   n
9   nnnn   n   nn
10   nnnn      nnn
11   nnn   nnnn   
12   nnn   nnn   n
13   nnn   nn   nn
14   nnn   n   nnn
15   nnn      nnnn
16   nn   nnnnn   
17   nn   nnnn   n
18   nn   nnn   nn
19   nn   nn   nnn
20   nn   n   nnnn
21   nn      nnnnn
22   n   nnnnnn   
23   n   nnnnn   n
24   n   nnnn   nn
25   n   nnn   nnn
26   n   nn   nnnn
27   n   n   nnnnn
28   n      nnnnnn
29      nnnnnnn   
30      nnnnnn   n
31      nnnnn   nn
32      nnnn   nnn
33      nnn   nnnn
34      nn   nnnnn
35      n   nnnnnn
36         nnnnnnn

Waiting for your reply.
Thanks

ANSWER: Interesting question! When I first looked at it, I thought the solution would immediately use some standard statistics/combinatorics formula, but it a little more tricky. The general solution involves Stirling numbers, which are a little more obscure. Here's a link

http://mathforum.org/library/drmath/view/51550.html.

For the example you give with 3 bins (spaces of timeline) where (in my notation now), A = # of objects (time-span points) in first bin, B = # in 2nd bin and C = # in 3rd bin. For 7 objects and 3 bins, the formula is

M(7,3) = # of ways to distribute 7 objects in 3 bins = ∑(j=1,N+1)・j = ∑(j=1,8)・j = 1+2+...+7+8 = 36.
Here is an explanation of how I came up with this formula.

The solution breaks down into asking how many objects out of N can be put into any arbitrary bin (the Stirling number derivation asks how N people can be seated around M tables). The answer is 0 or 1 or 2, etc. up to N. This means there are N+1 ways to put objects in a bin. For your example then, there are 8 ways to put objects into the 1st bin. As in your list, we can start with putting all the 7 objects in the 1st bin which leaves 0 objects for the other bins and thus no other distributions in those bins (combinations) to worry about for this first case. The next case is to put 6 objects in the 1st bin, which leaves 1 object to distribute into the other 2 bins. So, considering the 2nd bin, there is 1 object to either put in or not. Using the N+1 rule, this means that there are 2 ways to do this (either the object is in the 2nd bin or not). This situation is reflected in your list.

The next case is to put 5 objects into the 1st bin, leaving 2 objects to distribute into the other 2 bins. We can simplify the process by again just think of how many ways can the 2 objects be put into the 2nd bin, sort of ignoring the 3rd bin (and any other subsequent bins that you may want to add later). The N+1 rule says there are 3 ways to put the 2 objects in the 2nd bin; the leftovers end up in the 3rd bin, but we don't have to worry about them yet. Continuing on, you can see that there will be more objects to put into the 2nd bin as fewer objects out of the total are put into (assigned to) the 1st bin. This procedure gives rise to the table you list and can be summarized by the formula above.



---------- FOLLOW-UP ----------

QUESTION: Thanks Randy,

It was quick and satisfying reply.
Can you make 2 things more clear?

1. What is j in your formula? (I mean how to read the formula.)
2. What would be the answer if there are 3 objects and 4 bins?
One more example will make things clearer.
(3 objects 4 bins = 20 combinations. Is it correct?)

  1   2   3   4
1   nnn         
2   nn   n      
3   nn      n   
4   nn         n
5   n   nn      
6   n   n   n   
7   n   n      n
8   n      nn   
9   n      n   n
10   n         nn
11      nnn      
12      nn   n   
13      nn      n
14      n   nn   
15      n   n   n
16      n      nn
17         nnn   
18         nn   n
19         n   nn
20          nnn

Thanks.

Answer
combinations
combinations  
The symbol j in my answer is an index, so that the expression

∑(j=1,N+1)・j = ∑(j=1,8)・j = 1+2+...+7+8 = 36

can be interpreted as "the sum as j goes from 1 to N+1 of j". The expression to the right of the summation symbol, ∑, is known as its argument, which in this case, is simply the index j.

In the attached pdf file, I have fleshed out the number of combinations in a table and as formulas. You will see summation symbols and various indices like j, k, n and l. These indices are all integers and just serve to keep track of the terms in the summation. You will also notice the definition of various arguments, "arg", in the pdf file, which should be interpreted as described above.

The full solution involves higher order nested summations as the number of bins, M, and objects, N, increases. The bad news is that the formulas for generating an entry in the table (i.e., for given Ms and Ns) look complicated (though elegant in their own right). The good news is that table entries are easily generated recursively, as I have tried to indicate. Your best bet is to look at the table carefully and you will see the pattern as to how higher order entries are generated.

Note that your example of 7 objects and 3 bins is shown in the table (36 combinations). It also answers your question about 3 objects and 4 bins (20 is correct).

Have fun and keep the questions coming!

Advanced Math

All Answers


Answers by Expert:


Ask Experts

Volunteer


randy patton

Expertise

college mathematics, applied math, advanced calculus, complex analysis, linear and abstract algebra, probability theory, signal processing, undergraduate physics, physical oceanography

Experience

26 years as a professional scientist conducting academic quality research on mostly classified projects involving math/physics modeling and simulation, data analysis and signal processing, instrument development; often ocean related

Publications
J. Physical Oceanography, 1984 "A Numerical Model for Low-Frequency Equatorial Dynamics", with M. Cane

Education/Credentials
M.S. MIT Physical Oceanography, B.S. UC Berkeley Applied Math

Past/Present Clients
Also an Expert in Oceanography

©2016 About.com. All rights reserved.