Combinatorics - What is the number of ways $K$ elements sum to $N$?

Question

Given $K$ elements between $1$ and $7$ (inclusive), how many ways can you arrange the elements s.t. their sum adds to $N$?

I can brute-force my way to counting the number of ways for small $K$ and $N$, but is there a general formula that addresses this problem? I feel like this is a commonly discussed problem, but I just don't know what the solution is. This came out of something I'm working on (programming stuff). Thanks.

Answer 1

The best way to solve this is via a generating function. We treat the powers of $x$ as the values of $k$

So, to represent the fact that each element can take on any value from 1 to 7, we introduce a polynomial with 1 term for each power between 1 and 7, i.e., $x+x^2+x^3+x^4+x^5+x^6+x^7=\frac{x^8-1}{x-1}$. Then, since there are $k$ elements, we raise this polynomial to the $k$th power, and find the coefficient of $x^n$ in the result.

So, our answer will be the coefficient of $x^n$ in $$\bigg(\frac{x^8-1}{x-1}\bigg)^k$$

Answer 2

You are looking for $$ \eqalign{ & N_{\,b} (s,r,m) = \cr & = {\rm No}\,{\rm of}\,{\rm integer}\;{\rm solutions}\,{\rm to}\left\{ \matrix{ 1 \le x_{\,j} \le r + 1 = 7 \hfill \cr x_{\,1} + x_{\,2} + \cdots + x_{\,m = K} = s + K = N \hfill \cr} \right.\quad = \cr & = {\rm No}\,{\rm of}\,{\rm integer}\;{\rm solutions}\,{\rm to}\left\{ \matrix{ 0 \le y_{\,j} \le r = 6 \hfill \cr y_{\,1} + y_{\,2} + \cdots + y_{\,m = K} = s = N - K \hfill \cr} \right.\quad \cr} $$ which is the number of (weak) compositions of $s$, into exactly $m$ parts, restricted to $\{0,1,\dots\,r\}$.

The general formula is given by $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ as explained in detail in this related post and in this article.