Summing up Problem (Combinations) This is a part of a bigger problem I was solving.
Problem: $N$ is a positive integer. There are $k$ number of other positive integers ($\le N$)
In how many ways can you make $N$ by summing up any number of those $k$ integers. You can use any integer, any number of times.
For example: $N = 10$, $k=1: \{ 1 \}$
then there's only $1$ way of making $10$ using integers in braces: $1+1+1+1+\cdots+1 = 10$
another example: $N = 10$, $k = 2: \{ 1, 3\}$
number of ways $= 4$:
$1,1,1,1,1,1,1,1,1,1$
$1,1,1,1,1,1,1,3$
$1,1,1,1,3,3$
$1,3,3,3$
The question is to derive a generalized logic/formula to calculate the number of ways.
 A: There is a simple recursive formula for that problem.
$F(0, k) = 1$
$F(N, \emptyset) = 0$
$F(N, k) = F(N - \min(k), k) + F(N, k\backslash \{\min(k)\})$
A: You’re asking for the number $p_A(n)$ of partitions of the integer $n$ into parts that belong to a specified set $A=\{a_1,\dots,a_k\}$ of $k$ positive integers. The generating function for the sequence $\langle p_A(n):n\in\mathbb{N}\rangle$ is $$\prod_{i=1}^k\frac1{(1-x^{a_i})} = \prod_{i=1}^k(1+x^{a_i}+x^{2a_i}+x^{3a_i}+\dots)\;.\tag{1}$$ In other words, $p_A(n)$ is the coefficient of $x^n$ in the product $(1)$. For actual computation, however, a recursive approach is more efficient.
A: This sounds awfully like the Frobenius problem. There has been quite a number of threads on this, e.g. this and this. There are a number of algorithms for solving the coin problem; search around for details.
A: Using the recursion method, the problem will be solved very easily.
$F(0) = 1$;
$F(n<0) = 0$;
$F(N) = F(N - I_1) + F(N - I_2) + \cdots  + F(N - I_k)$
or,
$F(N) = ∑ F(N - I_i)$
But for larger values of N $( \approx 10^{18})$, the above method won't work.
Matrix Exponentiation will have to be used to solve the problem.
