Formula to to calculate number of combinations?

Question

I'm trying to find a formula for counting number combinations in a set. For example: how many ways can 4 numbers, each between 1 and 6, be added together to get the sum of 16? I apologize if I am not phrasing this well. I've been doing these combinations individually; I just finished writing out all 1296 combinations of 4 numbers 1-6, and the idea of writing out all 7776 combinations of 5 numbers 1-6 to find the percentage of each number 5-30 in that 7776 makes me want to cry. I've tried to find the answer on my own, but I'm just stumped.

Answer 1

(to avoid confusion of word "number" between "number of ways" and "get $6$ using $3$ numbers" lets say that we want to get some sum using $n$ coins, each coin has nominal from $1$ to $6$)

You can greatly simplify the problem by noting that if you add another coin you don't need to remember all ways to get some sum from previous coins - only the number of such ways.

So, to start - there obviously is exactly $1$ way to get each sum from $1$ to $6$ using one coin. What if we use two coins?

It's impossible to get $1$ from two coins. To get $2$, we need to get $1$ from the first coin and $1$ from the second, thus 1 way to get $2$.

To get, say, $4$, we can get $1$ from the first and $3$ from the second, $2$ from the first and $2$ from the second, or $3$ from the first and $1$ from the second - thus $3$ ways.

So far this is not better then just list all pairs. But what when we switch to three coins?

To get, say, $7$ from $3$ coins, we can get $2$ from the first two and $5$ from the last, or $3$ and $4$, or $4$ and $3$, or $5$ and $2$, or $6$ and $1$. For example, we already know that there are $5$ ways to get $6$ from two coins - but note that we don't need to list all of them again when we calculate number of ways for $3$ coins.

This way to switch from $n$ coins to $n + 1$ will require just $6 \cdot 5n$ operations, instead of $6^n$ - it's already manageable by hands.

And we can improve it even further! Lets say that for any sum from $3$ to $18$ we know number of ways to get this sum from $2$ or $3$ coins. Then if we want to know number of ways to get say $10$ from $5$ coins, we can write all possible ways to split this $10$ into first $3$ and last $2$ coins, and then multiply corresponding number of ways from $3$ and $2$ coin problems.

Formally, if $f_n(k)$ is number of ways to get sum of $k$ using $n$ coins, the first solution uses $f_{n + 1}(k) = \sum_{i = 1}^6 f_n(k - i)$ ($i$ is nominal of the last coin), and the second $f_{n + m}(k) = \sum_{i=0}^k f_n(i) f_m(k - i)$ [the first is just special case of the second - $m = 1$].

Answer 2

Note: I assume you want integers as your solutions, and that order is not important.

This method is fairly general but possibly overkill and above your level, and you'll perhaps find yourself using calculus results if going by hand. However, I don't myself know of any easier method offhand that has the same generality.

To recollection this method can be brought into the case where order is relevant by using exponential generating function; the overall approach is fairly similar.

---

Generally, I often see generating functions as a mean of solving such "combinations with restrictions" problems. This isn't a general "formula" to solving them, though, so much as a method.

For example, using your scenario, we want the number of integer solutions to

$$x_1 + x_2 + x_3 + x_4 = 16$$

where $1 \le x_i \le 6$ for $i=1,...,4$. To approach this by generating functions, first we define a polynomial for the restrictions on each variable. Define the polynomial corresponding to $x_i$ by

$$P_i(x) = \sum_{n\ge 0} x^n$$

where the $n$'s used are tied to the allowed values for $x_i$. Thus, if $x_i$ can be any even integer, $P_i(x) = x^0 + x^2 + x^4 + ...$ (an infinite sum; we often let $x^0=1$ for simplicity). If $x_i$ can be, say, any prime from $2$ to $11$, we'd have $P_i(x) = x^2 + x^3 + x^5 + x^7 + x^{11}$.

(Note: sometimes, if the pattern permits, we might leave $P_i$ as an infinite sum instead of finite. This can make calculations easier but it simply all depends, and cannot always be done.)

Relevant to your scenario, each $P_i$ is $P_i(x) = 1+x+x^2 + ... + x^6$. Then we define a generating function $g$ by

$$g(x) = \prod_i P_i(x)$$

In your case, we take the product of the four polynomials and thus have

$$g(x) = (1+x+x^2+...+x^6)^4$$

Okay, so what is the importance of $g$? Let's say we were in the more general scenario, seeking the number of solutions for $x_1+x_2+...+x_n = r$. Then we would construct the $P_i$ and $g$ as above, and then we would do whatever manipulations we can to get $g$ into the form of

$$g(x) = \sum_{n\ge 0} a_n x^n$$

for whatever values $a_n$ are. Then, after doing so, we find the coefficient of $x^r$ (i.e. $a_r$); that will be the desired number of solutions. Note, in your case, $r=16$, so we seek the coefficient of $x^{16}$ in the product above.

We can arguably do this by hand, for example, or use various formulas and identities to make the sum nicer: convenient ones include the binomial expansion, (finite and infinite) geometric series, and generalized binomial series. For example, in your case, the finite geometric series gives us

$$g(x) = \left(\frac{1-x^{7}}{1-x} \right)^4 = (1-x^{7})^4 \cdot (1-x)^{-4}$$

We then can apply binomial expansion and the infinite geometric series to the left and right factors respectively:

$$g(x) = \left( \sum_{k=0}^{4} \binom{4}{k}((-x)^7)^k \right) \cdot \left( \sum_{k=0}^\infty \binom{4+k-1}{4-1} x^k \right) = \left( \sum_{k=0}^{4} \binom{4}{k}(-1)^{k}x^{7k} \right) \cdot \left( \sum_{k=0}^\infty \binom{k+3}{3} x^k \right)$$

and then the rules of polynomial multiplication, when focusing on $x^{16}$'s term, give the result.

Alternatively, you could just dump the polynomial into a calculator, e.g. Wolfram Alpha, and see if that helps. In this case, Wolfram gives an expanded form of the polynomial, with $125$ as the coefficient of $x^{16}$.