number of combinations sum of combinations
1 1 1
2 3 3 10
4 5 6 7 60
7 8 9 10 15 272
total: 26 total: 343
The above layout shows numbers 1-10 arranged in triangle with the numbers descending from 1 to 10, left to right. Next to the triangle are two columns: one with the number of combinations per row, one with the sum of combinations.
I am unsure how the numbers in the column are determined. I assume that it would use the math formula (n choose r) nCr, where nCr is the formula for permutations of n objects taken r at a time. However if this is correct, I'm not sure how to apply the formula to the problem.
If this is not correct. I am unsure how the author determined the number of combinations and sum of combinations. Any assistance would be appreciated.
In the first row, we have $1$ element, which is $1$. We can choose this $\binom{1}{1}=1$ ways (this notation is the same as nCr, where n is the upper value and r is the lower value), i.e. there is only $1$ combination. The sum of all the combinations is just $1$.
In the second row, we have $2$ elements, $2$, and $3$. We can choose from the set $\{2, 3\}$ in the following ways: $\binom{2}{1}$ (where we select one of $2$, or $3$) and $\binom{2}{2}$ (where we select both $2$, and $3$). Thus the total number of (non-zero) selections from the set with these two elements is $\binom{2}{1}+\binom{2}{2}=2+1=3$. To find the sum, we must consider each selection individually. We can select $\{2\}$, or $\{3\}$, or $\{2, 3\}$. Then the sum is $2+3+2+3=10$.
Now in general, the total number of (non-zero sized) selections from a set with $n$ elements is $2^n-1$. This follows from the binomial theorem.
$$(x+y)^n=\sum_{i=0}^n\binom{n}{i}x^{n-i}y^i$$
If we set $x=y=1$, then
$$(1+1)^n=2^n=\sum_{i=0}^n\binom{n}{i}1^{n-i}1^i=\sum_{i=0}^n\binom{n}{i}$$
But this equation includes the choice of zero elements from the set, $\binom{n}{0}=1$. Subtracting from both sides we see the sum of all non-zero sized selections from a set with $n$ elements is
$$2^n-1=\sum_{i=1}^n\binom{n}{i}$$
To find the "sum of combinations" column, we again simply consider every one of the $2^n-1$ possible selections and sum them. A simple formula for this comes from considering how many times each element will appear in a selection. For instance, in the fourth row, consider only $7$. It will appear in $1$ subset of size $1$, $\binom{3}{1}=3$ subsets of size $2$ (why?), $\binom{3}{1}=3$ subsets of size $3$, and $1$ subset of size $4$. Thus it appears in $1+3+3+1=8$ subsets. In fact, each number (in the fourth row) appears in $8$ subsets exactly once. This can be generalized to show that a formula for the "sum of combinations" column is $2^{n-1}\cdot(\frac{q(q+1)}{2}-\frac{(p-1)(p)}{2})$ where $q$ is the rightmost value of the row, and $p$ is the leftmost value.