Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
1  
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}]. –  J. M. Nov 7 '11 at 4:25
2  
@J.M. Or, equivalently, using Mathematica's built-in command IntegerPartitions[10, All, {1, 3}]. –  Sasha Nov 7 '11 at 19:10

4 Answers 4

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

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.