Different sum combinations of $L$ identical lists of consecutive natural numbers

Question

Given $L$ variables $k_i$ where each $k_{i} \in \{1, 2, 3, \ldots, N\}$ I want to obtain how many different sums $k_{1}+k_{2}+\cdots+k_{L}$ are generated and the value of these sums.

There are $L^N$ possible sums but many give the same result, e.g. for $L=2$ and $N=3$ we have

• 1 + 1 = 2 (one solution that gives 2)
• 1 + 2 = 2 + 1 = 3 (two solutions that give 3)
• 1 + 3 = 3 + 1 = 2 + 2 = 4 (three solutions that give 4)
• 2 + 3 = 3 + 2 = 5 (two solutions that give 5)
• 3 + 3 = 6 (one solution that gives 6)

Is there a general formula that given a result $s$ outputs the number of combinations of the $k_i$ for $i=1,\ldots,L$ variables with possible values $\{1,\ldots,N\}$ which sum gives $s$?

(taking the previous example, for $L=2$ and $N=3$ there are 3 possible ways to obtain $s=4$, 2 possible ways to obtain $s=5$, etc)

Edit (addendum): What if instead of a sum of $L$ terms now I want to obtain the difference between two of them? i.e. given $k_1=1,...,N$ and $k_2=1,...,N$, how many times I obtain each possible difference $k_{1}-k_2$? I am not sure how can I generalize the problem...

Answer 1

You are asking for the number of compositions of $s$ into $L$ parts, with largest part at most $N$. This is a classical problem, equivalent to finding the coefficient of $x^s$ in the polynomial $(x+x^2+\cdots+x^N)^L$. Write this polynomial as $x^L(1-x^N)^L/(1-x)^L$. Expand the numerator and denominator by the binomial theorem, multiply the two series, and extract the coefficient of $x^s$ to get a formula for what you want expressed as a finite sum. It is also possible to obtain this formula using the Principle of Inclusion-Exclusion. A closely related result (where 0 is allowed as a summand) appears in Enumerative Combinatorics, vol. 1, second ed., Exercise 1.28.