I wanted to find out in how many ways I can do something, but I don't know combinatorics enough. Can you help me and show or give advice, what we should do in such situations as presented below? Let's start with what I know and an example (I am very sorry if there are some stylistic errors):
Let's say that I want to obtain $n > 0$ as a sum of $k$ non-negative integers:
$$ x_1 + x_2 + ... + x_k = n$$
Number of possible ways to do this can be counted by using combinations with repetition:
$$\binom{n+k-1}{k-1}$$
If we want all of our $x_i$'s to be greater than some fixed integer $s>0$, we can do this:
$$ x_1 + x_2 + ... + x_k = (y_1+s) + (y_2+s) + ... + (y_k+s) = n$$ $$ y_1 + y_2 + ... + y_k = n - ks$$
where $y_i \ge 0$, thus the number of solutions is:
$$\binom{(n - ks) +k-1}{k-1} = \binom{n - k(s-1) -1}{k-1} $$
Example 1). In how many ways we can get number $17$, using (icosahedron) 20-sided dices?
Solution 1). Because $17$ is less than highest possible number we can get on dice, we are not really bounded from above, only from the beneath: number on dice cannot be less than $1$. So we have to sum up solutions of all equations $$ x_1 + x_2 + ... + x_k = n$$ from $k=1$ (we get $17$ in one roll) to $k=17$ (we get $17$ rolls with 'ones' on each of them), where $x_i \ge 1$. So we have:
$${\sum}_{k=1}^{n} \binom{(n - k) +k-1}{k-1} = {\sum}_{k=0}^{n-1} \binom{n-1}{k} = 2^{n-1} = 2^{17-1} = 2^{16} $$
Now we have a problem:
What if we would want to obtain e.g. number 873 using 20-sided dices?
Or, generalizing for non-negative integers $d \le u $, we want to use such $k$ positive integers $x_i$ that $ d \le x_i \le u$ , to get number $n$.
In other words, how many solutions have equation
$$ x_1 + x_2 + ... + x_k = n$$
for non-negative integers $ d \le x_i \le u$ ?
The classical form to solve this is to use generating functions. As you have one way each of throwing 1 to 20 in a 20-sided die, it gets represented by: $$ z + z^2 + \ldots + z^{20} = z \frac{1 - z^{20}}{1 - z} $$ If you want the number of ways to throw 56 when throwing 5 dice, it would be ($[z^k] f(z)$ is the coefficient of $z^k$ in (the series expansion of) $f(z)$): \begin{align} [z^{56}] \left( \frac{z (1 - z^{20})}{1 - z} \right)^5 &= [z^{51}] (1 - z^{20})^5 \cdot (1 - z)^{-5} \\ &= [z^{51}] (1 - 5 z^{20} + 10 z^{40} - \ldots) \cdot (1 - z)^{-5} \\ &= ([z^{51}] - 5 [z^{31}] + 10 [z^{11}]) \cdot (1 - z)^{-5} \\ &= \binom{55}{4} - 5 \binom{35}{4} + 10 \binom{15}{4} \\ &= 92905 \end{align} The ellipses stand for terms which don't affect the result. We also use: $$ \binom{-m}{k} = (-1)^k \binom{k + m - 1}{m - 1} $$ To get 873 throwing any number of dice is harder... call: $$ D(z) = \frac{z (1 - z)^{20}}{1 - z} $$ then you are looking for: $$ [z^{873}] (1 + D(z) + D^2(z) + \ldots) = [z^{873}] \frac{1}{1 - D(z)} = [z^{873}] \frac{1 - z}{1 - 2 z + z^{21}} $$ You could expand as $(1 - z) (1 - z (2 - z^{20}))^{-1} = (1 - z) \sum_{n \ge 0} z^n (2 - z^{20})^n$, pick out the relevant terms and add up, but unless there is a real need I'd leave it to that.