You are here:

- Home
- Science
- Mathematics
- Advanced Math
- Combination

Advertisement

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.

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!

- Add to this Answer
- Ask a Question

Rating(1-10) | Knowledgeability = 10 | Clarity of Response = 10 | Politeness = 10 |

Comment | GREAT!! Thanks so much Randy. You guided perfectly the way I wanted. I have already Generated Many Tables manually, the final number of combinations will help me a lot. |

Advanced Math

Answers by Expert:

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

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