Given a set of coins find number of way to get a sum

Question

What is the way to solve the following kinds of problem:

Give coins of 2, 4, 6 find a number of ways to get n as a sum.

Say n = 6

We can get n = 6 answer is 4.

[2, 2, 2], [2, 4], [4, 2] , [6]

For a small number, I can solve it simple factorization but for large numbers this approach is not feasible.

Answer 1

@JMoravitz's comment is correct: the result can be obtained by looking at a particular coefficient in the generating function.

Alternatively, since the order in which the coins were used is important in your problem, you can solve the homogeneous recurrence $f(n) = f(n-2) + f(n-4) + f(n-6)$ with initial conditions $f(0)=1$ and $f(k)=0$ for $k<0$.

n   f(n)
02  1
04  2
06  4
08  7
10  13
12  24
14  44
16  81
18  149
20  274
22  504
24  927
26  1705
28  3136
30  5768
32  10609
34  19513
36  35890
38  66012
40  121415
42  223317
44  410744
46  755476
48  1389537
50  2555757

Here is the Python code I used to make the table above.

from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
    if n == 0: return 1
    if n  < 0: return 0
    return f(n-2) + f(n-4) + f(n-6)

Answer 2

Here we calculate the number $a_n$ of ways to represent even $n$ using generating functions. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

Since the coins $\{2,4,6\}$ are multiples of $2$, we set $n=2N$ and obtain

\begin{align*} \color{blue}{a_n}&=[x^{2N}]\sum_{k=0}^\infty\left(x^2+x^4+x^6\right)^k\\ &=[x^{2N}]\sum_{k=0}^Nx^{2k}\left(1+x^2+x^4\right)^k\tag{1}\\ &=\sum_{k=0}^N[x^{2N-2k}]\sum_{j=0}^k\binom{k}{j}\left(x^2+x^4\right)^j\tag{2}\\ &=\sum_{k=0}^N[x^{2k}]\sum_{j=0}^{N-k}\binom{N-k}{j}x^{2j}\left(1+x^2\right)^j\tag{3}\\ &=\sum_{k=0}^N\sum_{j=0}^{\min\{N-k,k\}}\binom{N-k}{j}[x^{2k-2j}]\left(1+x^2\right)^j\tag{4}\\ &\,\,\color{blue}{=\sum_{k=0}^N\sum_{j=0}^{\min\{N-k,k\}}\binom{N-k}{j}\binom{j}{k-j}}\tag{5} \end{align*} resulting in \begin{align*} (a_{2N})_{N\geq 1}=(1,2,4,7,13,24,44,81,149,274,504,\ldots) \end{align*} in accordance with the answer from @parsiad.

Comment:

• In (1) we factor out $x^{2k}$.

• In (2) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and apply the binomial theorem to $(1+(x^2+x^4))^k$. We also set the upper limit of the outer sum to $N$ since other terms do not contribute to $[x^{2N-2k}]$.

• In (3) we change the order of summation $k\to N-k$.

• In (4) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ again by also setting the upper limit of the inner sum accordingly.

• In (5) we select the coeffient of $x^{2k-2j}$.