# 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.

-
–  HbCwiRoJDp Nov 6 '11 at 20:34
Pretty simple to do in Mathematica: subsetPartitions[n_Integer?Positive, vec_List] := Flatten[MapThread[ConstantArray, {vec, #}]] & /@ FrobeniusSolve[vec, n] /; VectorQ[vec, IntegerQ] && Apply[And, Thread[0 < vec <= n]] does the job. Try subsetPartitions[10, {1, 3}]. –  Guess who it is. Nov 7 '11 at 4:25
@J.M. Or, equivalently, using Mathematica's built-in command IntegerPartitions[10, All, {1, 3}]. –  Sasha Nov 7 '11 at 19:10

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)\})$

-
By min(k) you mean, the smallest given integer, right? I tried your way. For N = 4, k = 2 { 2,3 }. the answer is coming out to be more 1, which is wrong. –  Rushil Nov 12 '11 at 2:07
for N = 4, and integers {2,3}, there's only one way to make 4 (2+2). –  Rushil Nov 12 '11 at 2:12

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.

-

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.

-

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.

-