Number of ways of making a sum of $k$ by choosing $n$ integers from a multiset

Question

Problem

Suppose that we are given a multiset of integers $A$ with the property that all elements in $A$ are between $a$ and $b$ (inclusive) where $a < b$. It is guaranteed that for all $i$ in $[a,b]$ that there is at least one integer in $A$ with a value of $i$ (i.e. if $a=2$ and $b=5$ then it is guaranteed that a $2$, $3$, $4$, and $5$ will appear at least once in $A$).

How many ways can we select $n$ integers from $A$ such that the sum of these integers is $k$?

Attempt

Forgetting the restriction that there are a limited number of integers from which we can take, then we are looking for the numbers of solutions to $x_1+x_2+\cdots+x_{n-1}+x_n$ where $a \leq x_i \leq b$ for all $i$ in $[1, n]$. Fortunately, I know how to solve problems like these using a generation function: $$\left(x^a+x^{a+1}+\cdots+x^{b-1}+x^b\right)^n.$$ The coefficient of the $k$-th degree term in the generating function tells us the number of ways of making a sum of $k$.

However, the problem is that we can't use the generating function since the number of integers in the interval is limited. For example, if $A=\{3,4,5\}$ where $a=3$ and $b=5$ then we can make a sum of $12$ with $3$ integers in exactly three ways: $3+4+5=12$ or any permutation of that; however, according to the generation function, we can make a sum of $12$ in $7$ ways since we can use multiple of the same integer---though, that is obviously not the case.

Answer 1

First of all we have better to reduce the parametrs in play by reconducting the problem to the elements in $\{ 0,b-a \}$ $$ \left\{ \matrix{ a \le x_{\,j} \le b \hfill \cr x_{\,1} + x_{\,2} + \cdots + x_{\,n} = k \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matrix{ 0 \le y_{\,j} \le b - a = r \hfill \cr y_{\,1} + y_{\,2} + \cdots + y_{\,n} = k - na = s \hfill \cr} \right. $$

Then
a) if repetitions were allowed in whichever number (from $0$ to $n$), so that we can write $$ \left\{ \matrix{ 0 \le y_{\,1} ,y_{\,2} , \cdots ,y_{\,n} \le r \hfill \cr y_{\,1} + y_{\,2} + \cdots + y_{\,n} = s \hfill \cr} \right. $$ then the number of solutions to that would be encoded by the ogf you correctly indicated, and that can be computed by the finite sum $$ 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 this post.

Instead , with
b) no repetitions, we are to find the number of solutions to $$ \left\{ \matrix{ y_{\,j} \ne y_{\,k} \quad \left| {\;j \ne k} \right. \hfill \cr 0 \le y_{\,1} ,y_{\,2} , \cdots ,y_{\,n} \le r \hfill \cr y_{\,1} + y_{\,2} + \cdots + y_{\,n} = s \hfill \cr} \right. $$ and since the parts are all different, these will be $n!$ times the number of solutions to $$ \left\{ \matrix{ 0 \le y_{\,1} < y_{\,2} < \cdots < y_{\,n} \le r \hfill \cr y_{\,1} + y_{\,2} + \cdots + y_{\,n} = s \hfill \cr} \right.\quad \Leftrightarrow \quad \left\{ \matrix{ 1 \le z_{\,1} < z_{\,2} < \cdots < z_{\,n} \le r + 1 \hfill \cr z_{\,1} + z_{\,2} + \cdots + z_{\,n} = s + n \hfill \cr} \right.\quad \Leftrightarrow \quad \left\{ \matrix{ 1 \le v_{\,1} \le v_{\,2} \le \cdots \le v_{\,n} \le r + 2 - n \hfill \cr v_{\,1} + v_{\,2} + \cdots + v_{\,n} = s - {{n\left( {n - 3} \right)} \over 2} \hfill \cr} \right. $$ where the second derives from the first by adding $1$ to all parts, and the third from the second by subtracting $0$ from $z_1$, $1$ from $z_2$, and so on till $n-1$ from $z_n$.
Therefore that is the number of partitions of $s+n$ into $n$ distinct parts, with the greatest part not exceeding $r+1$,
or also the number of partitions of $s- n*(n-3)/2$ into $n$ parts not greater than $r+2-n$.
For solutions to exist we shall have in all cases that $$ \left\{ \matrix{ n \le r + 1 \hfill \cr \left( \matrix{ n \cr 2 \cr} \right) \le s \le {{n(2r - n + 1)} \over 2} \hfill \cr} \right. $$ and it is profitable to include the case $n=0, s=0$ for which we take the solution to be $1$: the empty set.

Now, the development of this polynomial $$ f(x,r) = \left( {1 + x} \right)\left( {1 + x^{\,2} } \right) \cdots \left( {1 + x^{\,r + 1} } \right) = \cdots + x^{0 \cdot \left( 1 \right) + 1 \cdot \left( 2 \right) + 1 \cdot \left( 3 \right) + \cdots + 0\left( {r + 1} \right)} + \cdots $$ turns out in the sum of powers of $x$, where the exponent add or not each one of the elements of $\{1, \cdots, r+1\}$, and thus $f(x,r)$ is the ogf of the above system in $z$, but with an unspecified number of parts.
We can find the ogf for the system in $v$ as well, but it will also miss a parameter and it is more complicated to handle.

The only way is that from the $f(x,r)$ above we take only $n$ terms in $x$ and sums over every possible $n$-subset of $\{ 1, \cdots, r+1 \}$. $$ \eqalign{ & g(x,r,n) = \sum\limits_{0\, \le \,s} {N(s,r,n)\,x^{\,s + n} } = \cr & = \sum\limits_{\left\{ {k_{\,1} ,\,k_{\,2} ,\, \ldots ,\,k_{\,n} } \right\}\, \subset \,\left\{ {1,\,2,\, \ldots ,r + 1} \right\}} {x^{\,k_{\,1} } x^{\,k_{\,2} } \cdots x^{\,k_{\,n} } } \cr} $$ but since it requires the generations of the subsets it is of no practical advantage over counting those for which the sum of the elements is the required one.

Yet, it helps to easily define a recurrence relation $$ \eqalign{ & g(x,r,n) = \sum\limits_{0\, \le \,s} {N(s,r,n)\,x^{\,s + n} } = \cr & = \sum\limits_{n\, \le \,k_{\,n} \, \le \,r + 1} {x^{\,k_{\,n} } \sum\limits_{\left\{ {k_{\,1} ,\,k_{\,2} ,\, \ldots ,\,k_{\,n - 1} } \right\}\, \subset \,\left\{ {1,\,2,\, \ldots ,k_{\,n} - 1} \right\}} {x^{\,k_{\,1} } x^{\,k_{\,2} } \cdots x^{\,k_{\,n - 1} } } } = \cr & = \sum\limits_{n\, \le \,k\, \le \,r + 1} {x^{\,k} g(x,k - 2,n - 1)} + \left[ {n = 0} \right] = \cr & = \left[ {n = 0} \right] + \sum\limits_{n\, \le \,k\, \le \,r + 1} {x^{\,k} \sum\limits_{0\, \le \,s} {N(s,k - 2,n - 1)\,x^{\,s + n - 1} } } = \cr & = \left[ {n = 0} \right] + \sum\limits_{0\, \le \,s} {\left( {\sum\limits_{n\, \le \,k\, \le \,r + 1} {N(s,k - 2,n - 1)\,x^{\,s + n - 1 + k} } } \right)} = \cr & = \left[ {n = 0} \right] + \sum\limits_{0\, \le \,s} {\left( {\sum\limits_{n\, \le \,k\, \le \,r + 1} {N(s - k + 1,k - 2,n - 1)\,} } \right)x^{\,s + n} } \cr} $$ which leads to: $$ \bbox[lightyellow] { \eqalign{ & N(s,r,n) = \left[ {n = 0} \right]\left[ {s = 0} \right] + \sum\limits_{n\, \le \,k\, \le \,r + 1} {N(s - k + 1,k - 2,n - 1)\,} = \cr & = \left[ {n = 0} \right]\left[ {s = 0} \right] + \sum\limits_{n - 2\, \le \,k\, \le \,r - 1} {N(s - k - 1,k,n - 1)\,} \cr} }$$ where the condition in square brackets $[P]$ denotes the Iverson bracket

Also, taking out the bias and putting $$ s \to s + \left( \matrix{ n \cr 2 \cr} \right)\quad r \to r + \left( {n - 1} \right) $$ the recursion becomes more neat $$ \bbox[lightyellow] { N_{\,s\,c} (s,r,n) = \left[ {n = 0} \right]\left[ {s = 0} \right] + \sum\limits_{0\, \le \,k\, \le \,r} {N_{\,s\,c} (s - k,k,n - 1)\,} }$$ with the understanding that the parametrs of $N_{\,s\,c}$ are the unbiased ones of those appearing in $N$ above.

Finally, when
c) repetitions are allowed and limited then we are in between case a) and b).
I am not aware of any "easy" way to compute the number of solutions in this case, other than the clumsy o.g.f. $$ \eqalign{ & H(x,r,n) = \sum\limits_{0\, \le \,s} {N_{\,rep} (s,r,n)\,x^{\,s} } = \cr & = \sum\limits_{\left( {k_{\,1} ,\,k_{\,2} ,\, \ldots ,\,k_{\,n} } \right)\,\; \leftarrow \,\,{\rm multiset}\,\left\{ {1,\,2,\, \ldots ,r + 1} \right\}} {x^{\,k_{\,1} } x^{\,k_{\,2} } \cdots x^{\,k_{\,n} } } \cr} $$ where the $n$-tuples $\left( {k_{\,1} ,\,k_{\,2} ,\, \ldots ,\,k_{\,n} } \right)$ are constructed from the multiset respecting the multiplicities assigned.

Answer 2

Generating functions are the correct approach here. In fact, your solution is very much on the right track. I'm going to use the example you gave and then we can generalize. The generating function for the multiset $A=\{3,4,5\}$ is $$ G(x,y)=(1+x^3y)(1+x^3y)(1+x^4y)(1+x^5y), $$ which can be thought of choosing any combination of elements (where $y^m$ represents choosing $m$ elements) to get some exponent of $x$. Therefore, the coefficient of the term in the form of $x^k y^n$ describes the number of ways to make a sum of $k$ by choosing $n$ integers from $A$. Using WolframAlpha to expand $G(x,y)$, we indeed find that the coefficient of $x^{12}y^3$ is $1$, the expected result.

In fact, this approach works regardless of the restriction posed in the original problem statement. For any multiset $M$, we can determine the number of solutions to $a_1+a_2+\ldots+a_n=k$ where $a_i \in M$ for all $1 \leq i \leq n$ based on the coefficient of the term $x^k y^n$ in the expansion of the bivariate generating function, $G_M(x,y)$, $$ G_M(x,y)=\prod_{i\in M}(1+x^iy). $$

We are thus interested in determing a formula for the coefficient of the term in the form $x^k y^n$ which we will denote as $[x^ky^n]G_M(x,y)$. At this point, we need to pay extra attention. Perhaps I am wrong though it doesn't seem as we can determine a general formula for $[x^ky^n]G_M(x,y)$; however, it just may be possible by the restriction of the original problem: we know that $A$ will contain at least a consecutive series of elements from $a$ to $b$. Unfortunately, I have not been able to derive a formula for $[x^ky^n]G_A(x,y)$ but I will present my current work:

We can write the generating function for $A$ as $$ \begin{align*} G_A(x,y)&=\prod_{i=a}^b(1+x^iy)^{m_A(i)},\\ &=\prod_{i=a}^b(1+x^iy)\prod_{i=a}^b(1+x^iy)^{m_A(i)-1},\\ &=\frac{(-y;x)_{b+1}}{(-y;x)_a}\prod_{i=a}^b(1+x^iy)^{m_A(i)-1}, \end{align*} $$ where $m_A(i)$ is the multiplicity of element $i$ in the multiset $A$ and $(a;q)_n$ denotes the $q$-Pochhammer symbol [1]. We can rewrite the $q$-Pochammer symbol in terms of a sum: $$ G_A(x,y)=\frac{\sum^{b+1}_{i=0}x^\binom{i}{2}y^i\genfrac{[}{]}{0pt}{}{b+1}{i}}{\sum^a_{i=0}x^\binom{i}{2}y^i\genfrac{[}{]}{0pt}{}{a}{i}}\prod_{i=a}^b(1+x^iy)^{m_A(i)-1}.$$ Notice that the multiplicands are binomial series which means that we can equivalently write as $$ G_A(x,y)=\frac{\sum^{b+1}_{i=0}x^\binom{i}{2}y^i\genfrac{[}{]}{0pt}{}{b+1}{i}}{\sum^a_{i=0}x^\binom{i}{2}y^i\genfrac{[}{]}{0pt}{}{a}{i}}\prod_{i=a}^b\left(\sum_{j=0}^{m_A(i)}\binom{m_A(i)-1}{j}x^{ij}y^j\right). $$

One observation that I have made is that $G_A(x,y)$ can be rewritten recursively: we can continue to pull out a full sequence of binomials (i.e. $\prod_{i=a}^b(1+x^iy)$) so long as all integers between $a$ and $b$ are still in $A$. In other words, $$ G_A(x,y)=\left(\frac{\sum^{b+1}_{i=0}x^\binom{i}{2}y^i\genfrac{[}{]}{0pt}{}{b+1}{i}}{\sum^a_{i=0}x^\binom{i}{2}y^i\genfrac{[}{]}{0pt}{}{a}{i}}\right)^r\prod_{i=a}^b(1+x^iy)^{m_A(i)-r}, $$ if and only if $m_A(x)=r,\forall x \in [a,b]$, where $m_A(x)$ is the multiplicity of element $x$ in the multiset $A$. The recursive definition follows from the fact that we can rewrite the product as the same generating function on a subset of $A$.

Perhaps someone else can take over...