MHB Look for help with combinations

  • Thread starter Thread starter RaTawer
  • Start date Start date
  • Tags Tags
    Combinations
AI Thread Summary
The discussion focuses on calculating the number of combinations of 16 whole numbers that sum to 240 or less, emphasizing the importance of whether the order of numbers matters. An example is provided with three whole numbers summing to 6 or less, illustrating the use of Triangular Numbers to derive combinations. The formula for the number of combinations when order matters is presented as N = (1/6)n(n+1)(n+2). The conversation also raises the complexity of adjusting calculations for four numbers and the need to account for scenarios where order does not matter. Overall, the thread explores mathematical approaches to solving combinatorial problems involving sums and order.
RaTawer
Messages
1
Reaction score
0
I'm working on a project and I need to know how many possible combinations of 16 whole numbers there are that have a sum of 240 or less. How would I achieve this sort of thing?
 
Physics news on Phys.org
One thing that will matter quite a bit is whether the order matters. Well, let's see if we can poke around a bit at the answer. Suppose we wanted to find out how many combinations there were of 3 whole numbers that add to 6 or less. I think we could list them:

0+0+0
0+0+1
0+0+2
0+0+3
0+0+4
0+0+5
0+0+6
0+1+0 (Here you can see, by comparing with the second line, that I'm assuming order matters.)
0+1+1
0+1+2
0+1+3
0+1+4
0+1+5
0+2+0
0+2+1
0+2+2
0+2+3
0+2+4
0+3+0
0+3+1
0+3+2
0+3+3
0+4+0
0+4+1
0+4+2
0+5+0
0+5+1
0+6+0
1+0+0
At this point, we are starting to see a pattern. Up until the last line, I'd say we had 7+6+5+4+3+2+1 = 28 ways to write it. If we change the first digit to a 1, then each possibility is going to go down by 1. So we'd have 6+5+4+3+2+1 = 21 ways to write it. These are the Triangular Numbers, denoted by $T_n$. The definition of the Triangular Number $T_n$ is that
$$T_n=1+2+3+\dots+n,$$
and thanks to Gauss, we know that
$$T_n=\frac{n(n+1)}{2}.$$
To get our final result, we must sum the Triangular Numbers from $T_7$ down to $T_1$. That is, the answer to this smaller question is
$$N=\sum_{j=1}^7 T_j=\sum_{j=1}^7 \frac{j(j+1)}{2}=84.$$
In general,
$$N=\sum_{j=1}^n T_j=\frac16 n(n+1)(n+2).$$
This is the number of ways to get a sum of $n$ or less from three whole numbers where order matters.

But now, supposing we were to change the number of numbers to 4. How would that change our result? Well, for each value $f$ of the fourth number, we'd have $N-f$ ways to write the new sum. So, we'd have to do
$$\sum_{j=1}^7 \left[\frac16 n(n+1)(n+2)\right].$$
So, how would this work for 16 numbers?

Moreover, if we need to eliminate the idea that order matters, how could we correct these (too large) values?
 

Similar threads

Back
Top